پاورپوینت مسئله تخصیص نمایی(QAP) (pptx) 26 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 26 اسلاید
قسمتی از متن PowerPoint (.pptx) :
1
مسئله تخصیص نمایی(QAP)
2
Koopmans و Beckman در سال 1957 مسئله تخصیص نمایی را برای فعالیت های اقتصادی تعریف و فرمولبندی کردند. این مسئله به جهت ماهیت درجه دو آن به مسئله تخصیص نمایی شناخته شده است.
مسئله ای که حدوداً پنج دهه است که توجه محققان در زمینه های مختلف را به خود جلب نموده است و محققان و دانشمندان بسیاری در زمینه ریاضیات، کامپیوتر، تحقیق درعملیات و اقتصاد از آن برای مدلسازی مسائل بهینه سازی استفاده نمودند.
بیان تاریخچه:
3
منظور از تخصیص این است که هر یک از تسهیلات منطبق بر یک مکان شود و بالعکس. در QAP لازم است تعداد تسهیلات و مکان ها برابر باشد. اگر تعداد تسهیلاتی که باید به n مکان اختصاص داده شود از n کمتر(مثلاً m تا)باشد، آنگاه برای استفاده از فرمول بندی تخصیص نمایی، تعداد n-m تسهیلات مجازی در نظر می گیریم و بین هرکدام از اینها( تسهیلات فرضی) و بقیه تسهیلات جریان صفر منظور می کنیم. اگر تعداد مکان ها کمتر از تعداد تسهیلات باشند، آنگاه مسئله ناشدنی خواهد بود.
4
تخصیص:
برای معرفی و آشنایی بیشتر با این نوع مدل، کاربردهای آن در مسائل عملی عنوان می گردد.
کاربرد QAP در مسائل مکان یابی
کاربردها:
5
کاربردها:
6
:n تعداد کل تسهیلات و مکان ها
: 𝒂 𝒊𝒋 درآمد خالص حاصل از فعالیت وسیله i در مکان j
: 𝒇 𝒊𝒌 جریان مواد از وسیله i به وسیله k
: 𝒄 𝒋l هزینه حمل یک واحد از مواد از مکان j به مکان l
: 𝒅 𝒊𝒋 فاصله ی بین وسیله i تا j
: 𝒙 𝒊𝒋 = 𝟏 𝟎 متغیر تصمیم
نماد ها:
7
اگر وسیله i در مکان j قرار دارد
در غیر اینصورت
Max 𝑖=1 𝑛 𝑗=1 𝑛 𝑎 𝑖𝑗 𝑥 𝑖𝑗 − 𝑖=1 𝑛 𝑗=1 𝑛 𝑘=1 𝑛 𝑙=1 𝑛 𝑓 𝑖𝑘 𝑐 𝑗𝑙 𝑥 𝑖𝑗 𝑥 𝑘𝑙
s .t.
𝑗=1 𝑛 𝑥 𝑖𝑗 =1 𝑖=1,2,…,𝑛
𝑖=1 𝑛 𝑥 𝑖𝑗 =1 𝑗=1,2,…,𝑛
𝑥 𝑖𝑗 ∈ 0,1 𝑖,𝑗=1,2,…,𝑛
8
مدل QAP:
(1)
(2)
(3)
i≠𝑘 & 𝑗≠𝑙
تابع هدف عبارتست از بیشینه کردن حاصل تفاضل درآمد ناخالص از ورودی های اولیه و هزینه جابجایی مواد بین تسهیلات.
محدودیت های (2) و(3) باعث می شوند هر وسیله i تنها به یک مکان تعلق گیرد.
مشابه قبل محدودیت های (1) و (3) با هم تضمین می کنند که به هر مکان j دقیقاً یکی از تسهیلات تخصیص یابد.
9
مدل QAP:
