مسئله تخصیص (Assignment Problem)، در ریاضیات (Mathematics)
انواع روش های بهینه سازی (Optimization Methods) را در آموزش زیر شرح دادیم :
مسئله تخصیص (Assignment Problem) :
📌 معرفی
مسئله تخصیص (Assignment Problem) حالت خاصی از مسئله حمل و نقل است که در آن تعداد منابع برابر تعداد مقاصد است و هر منبع باید دقیقا به یک مقصد تخصیص یابد (و برعکس). متغیرها باینری هستند.
📐 فرمول بندی
\[ \min \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij} \] \[ \text{s.t.} \quad \sum_{j=1}^n x_{ij} = 1 \quad \forall i \] \[ \quad \sum_{i=1}^n x_{ij} = 1 \quad \forall j \] \[ \quad x_{ij} \in \{0,1\} \]🔧 الگوریتم اصلی
الگوریتم مجارستانی (Hungarian Algorithm): با پیچیدگی
\[ O(n^3) \]، کارآمدترین روش برای حل مسائل تخصیص است. مراحل آن:
کاهش سطرها: از هر سطر، کوچکترین عنصر آن سطر کم کن.
کاهش ستون ها: از هر ستون، کوچکترین عنصر آن ستون کم کن.
پوشش صفرها با حداقل خطوط.
اگر تعداد خطوط برابر n نباشد، ماتریس را تنظیم کن و تکرار کن.
نویسنده علیرضا گلمکانی
شماره کلید 8791
گزینه ها 
نظرات 0 0 0