مدلسازی مسائل تخصیص

مسئله تخصیص نوع خاصی از مسئله حمل و نقل است که در آن تصمیم گیرنده قصد تخصیص تعدادی کار را به تعدادی از افراد به صورت یک به یک دارد به طوریکه هیچ فردی بیش از یک کار را انجام ندهد و هیچ کاری نیز به بیش از یک نفر اختصاص نیابد. هزینه کل در مسئله تخصیص باید حداقل گردد. این مسئله را می توان به صورت زیر معادل مسئله حمل و نقل توضیح داد:

  • هر وظیفه را یک منبع یا ایستگاه مبداء در نظر بگیرید.
  • هر فرد را یک مقصد در نظر بگیرید.
  • عرضه هر مبداء یک واحد است.
  • تقاضای هر مقصد یک واحد است.
  • هزینه حمل و نقل نیز برابر است با هزینه تخصیص

مثالی از مسئله تخصیص

یک واحد خدماتی قصد دارد سه تیم خدمات درمانی را به سه روستای دور دست اعزام کند، هر تیم را به یک روستا. فرض کنید هر تیم روزانه باید مسیر بین دفتر مرکزی تا روستای مورد نظر را طی کند و همچنین هزینه های حمل و نقل و زمان لازم برای حدمت رسانی از روستایی به روستای دیگر متفاوت است. اطلاعات مربوط به هزینه ها در جدول زیر به صورت هزینه هر ساعت خدمت رسانی ارائه شده است. مسئله یافتن بهترین تخصیص به صورتی است که هزینه کل حداقل گردد.

جدول 1. اطلاعات مربوط به مثال تخصیص

تیم خدمت رسانی

روستای اول

روستای دوم

روستای سوم

تیم اول

25

20

30

تیم دوم

20

15

35

تیم سوم

18

19

28

 تعریف متغیرها:

تخصیص تیم iام (i=1,2,3) به روستای jام (j=1,2,3)

متغیر بالا به صورت زیر به شکل متغیر منطقی صفر و یک تعریف می شود:

یعنی اگر تیم iام به روستای jام تخصیص داده شود متغیر عدد یک را به خود می گیرد و در غیر این صورت مقدار متغیر عدد صفر خواهد بود. عبارت ow مخفف کلمه other wise به معنای در غیر این صورت است.

تابع هدف:

هدف مساله حداقل کردن هزینه کل تخصیص است.

محدودیت ها:

در این مسئله نیز مانند مسئله حمل و نقل دو نوع محدودیت وجود دارد.

محدودیت تیم خدماتی (محددیت عرضه): یک تیم خدمت رسانی تنها به یکی از سه روستا اختصاص می یابد.

: تیم خدمت رسانی اول

: تیم خدمت رسانی دوم

: تیم خدمت رسانی سوم

محدودیت روستا (محدودیت تقاضا): هر روستا تنها می تواند یک تیم خدمت رسانی داشته باشد.

: روستای اول

: روستای دوم

: روستای سوم

 جدول 2. حالت جدولی مسئله تخصیص

روستا

تیم 

عرضه 

25 

20 

30 

20 

15 

35 

18 

19 

28 

تقاضا

3=3 

 مدل نهایی به صورت زیر خواهد بود:

علاوه بر مشخصات مربوط به مسئله حمل و نقل در مسئله تخصیص همه اعداد سمت راست برابر با یک می باشند. مسئله را می توان هم به صورت یک مسئله برنامه ریزی خطی و هم به صورت یک مسئله برنامه ریزی عدد صحیح حل کرد. با این حال به طور معمول ترجیحاً مسئله تخصیص را بهتر است به صورت مسئله برنامه ریزی خطی مدلسازی نمود زیرا روش های حل موثری برای این نوع مسائل وجود دارد. البته الگوریتم های موثر بسیاری برای مسئله تخصیص وجود دارد که در آینده و در بخش مدلسازی همین وبلاگ به آنها خواهیم پرداخت.

 مطلب مرتبط بعدی: مدلسازی مسائل جابجایی (Transshipment Problem)

مطلب مرتبط قبلی: مدلسازی مسائل حمل و نقل

/ 5 نظر / 378 بازدید
بيننده

بسيار خوب ممنون

ati

چرا جواب مساله تخصیص همواره به صورت صفرو یک هست حتی اگر محدودیت صفر و یک اعمال نشود؟

ati

با تشکر از پاسخگویی تون اگر مساله تخصیص را به صورت برنامه ریزی خطی هم مدلسازی کنیم (همان طور که در مثالی که ذکر کردید این کارو کردید) یعنی شرط صفر و یکی بودن متغیرها را در نظر نگیریم (X>=0) باز هم به جواب های صفرویکی میرسیم. چرا؟

سمیرا

لطفا موضوع مدل سازی حمل ونقل و تخصیص رو هم بهم ایمیل کنید. ممنونتم.

سارا صمدی

با سلام و تشکر آیا میشه مسئله تخصیص را روی شبکه پیاده سازی و با روش های ماکزیمم جریان مثل الگوریتم فورد فولکرسون حل کرد و حالت اینورس مسئاه تخصیص به چه صورت خواهد بود.