بخشی از پاورپوینت
اسلاید 1 :
برنامه ریزی خطی _ قالب گیری
اسلاید 2 :
موضوع فصل :
بررسی اینکه برای یک شی داده شده قالب مناسبی وجود دارد که بتوان شی را به راحتی از قالب بیرون اورد؟
تبدیل مسئله قابگیری به مسئله هندسی :
یک مجموعه از نیم صفحه ها داده شده می خواهیم یک نقطه در اشتراک آنها را پیدا کنیم ؟
اسلاید 3 :
در مسئله قالب گیری نیاز نیست که همه جواب های مجموعه محدودیت های خطی را به دست آوریم ، فقط یک جواب که یک نقطه در اشتراک نیم صفحه ها است ،کافی می باشد .پس می توان الگوریتم بهتری داشته باشیم .
نشان دادیم که اشتراک نیم صفحه ها را می توان در زمان O(nlogn) به دست آورد.
به عبارت دیگر محاسبه همه جواب های یک مجموعه از nمحدودیت در مسئله قالبگیری.
اسلاید 4 :
4.3 Incremental Linear Programming
تبدیل مساله قالب گیری به مساله برنامه ریزی خطی
حل مساله برنامه ریزی خطی به کمک روش های هندسه محاسباتی
پیدا کردن یک جواب خاص برای مجموعه محدودیت ها
اسلاید 5 :
مساله ی پیدا کردن یک جواب از یک مجموعه محدودیت های خطی ، بهینه سازی خطی یا برنامه ریزی خطی نامیده می شود .
به تابع خطی ماکزیمم کنند از متغیرها ، تابع هدف می گویند.
به عبارتی مسئله بهینه سازی خطی به صورت زیر است :
ci ، aij و bi اعدادحقیقی هستند و d بعد مسئله است .
هدف پیدا کردن یک جواب خاص برای مجموعه محدودیت ها است.
اسلاید 6 :
در مسئله مورد بحث ما d=2 یعنی مسئله دو بعدی است .
اشتراک نیم صفحه ها مجموعه نقاطی است که در همه محدودیت ها صدق می کند.
این ناحیه را feasible regionمی گویند
نقاط خارج از ناحیه را نقاط infeasible گوییم .
نقاط داخل ناحیه را نقاط feasible می نامند.
اسلاید 7 :
تابع هدف را می توان به عنوان یک بردارجهتدار در نظر گرفت.
تابع هدف تعریف شده توسط بردار C را نشان می دهد . برای ماکزیمم کردن تابع هدف باید دورترین نقطه در روی بردار C که در ناحیه feasible قرار دارد را پیدا کرد
اسلاید 8 :
برای حل این مساله در تحقیق در عملیات روش های مختلفی وجود دارد. مهم ترین این روش ها که در عمل نیز بسیار مورد استفاده قرار می گیرد، روش سیمپلکس است.
روش کار :
تعیین یک تابع هدف دلخواه
حل مسئله خطی با توجه به آن تابع هدف و محدودیت ها
اسلاید 9 :
مجموعه n محدودیت خطی در مسئله خطی دو متغیره را با
نشان می دهیم .
بردار تابع هدف را تعریف می کند و است .
هدف پیدا کردن یک نقطه مانند است به طوریکه و ماکزیمم باشد .
مسئله خطی را با و ناحیه feasible را با C نشان می دهیم .
اسلاید 10 :
4 حالت کلی برای جواب مسئله وجود دارد :
مسئله خطی غیر شدنی است ,در این حالت جوابی برای مجموعه محدودیت ها وجود ندارد .
ناحیه شدنی بیکران است که در این مورد پرتوی وجود دارد که کاملا در ناحیه feasible قرار دارد ،به طوریکه تابع هدف درجهت ماکزیمم خواهد شد .در این حالت جوابی که مورد نظر است توصیف می باشد .
اسلاید 11 :
ناحیه feasible یک یال e دارد, در این حالت جواب برای مسئله خطی وجود دارد اما یکتا نیست .
اگر هیچ یک از سه حالت بالا رخ ندهد
یک جواب یکتا وجود دارد که یک راس از C می باشد .
اسلاید 12 :
روش ما برای حل مسئله برنامه ریزی خطی دو بعدی استفاده از یک الگوریتم افزایشی است.
در هر مرحله یک محدودیت اضافه می شود و برای مساله جدید یک جواب بهینه بدست می آید.بنابراین نیاز است که جواب هریک از مسائل میانی خوب و یکتا باشد .
به عبارت دیگر فرض می شود که هر ناحیهfeasible میانی ، یک راس بهینه یکتا دارد اما ممکن همیشه این شرط برقرار نشود.
اسلاید 13 :
بنابراین برای تضمین اینکه مسئله کراندار باشد دو محدودیت جدید به صورت زیر اضافه می کنیم :
با انتخاب m1 و m2 که به نیم صفحه های مجموعه H بستگی ندارند
ناحیه یک ناحیه گوشه دار است .
Mباید به اندازه کافی بزرگ باشد که محدودیت های اضافه شده روی
جواب بهینه تاثیر نگذارد .
اسلاید 14 :
2)اگر مسئله بی نهایت جواب داشته باشد، در این حالت کوچکترین نقطه در ترتیب قاموسی نقطه بهینه خواهد بود .
با این دو قرارداد هرمسئله خطی که feasible بشود یک جواب یکتا دارد که راس ناحیه
feasible است و این راس ، راس بهینه نامیده می شود .
اسلاید 15 :
اگر برای یک i ، 𝐶𝑖=∅ آنگاه برای هر j≥ i ، 𝐶𝑗=∅ و مسئله خطی infeasible می شود.
فرض کنید یک مسئله خطی باشد و نیم صفحه های h1,h2,.,hn را داشته باشیم و مجموعه ای از i محدودیت اول همراه با دو محدودیت m1 و m2باشد و Ci ناحیه feasible تعریف شده توسط این محدودیت ها می باشد .
با انتخاب C0 هر ناحیه شدنی Ci یک راس بهینه یکتا دارد که با Vi نشان داده می شود.
اسلاید 16 :
دو حالت پس از اضافه کردن نیم صفحه جدید برای راس بهینه Vi رخ می دهد.
با اضافه کردن نیم صفحه h5 راس بهینه همان v4 باقی می ماند .
با اضافه کردن نیم صفحه h6 راس بهینه در v4 باقی نمی ماند .، بنابراین باید یک راس بهینه جدید(v6) پیدا شود .
راس بهینه v4 بعد از اضافه کردن 4 نیم صفحه اول بدست می آید
اسلاید 17 :
لم 4.5 :
فرض کنید 1≤i≤n و Ci وvi به صورت قبل تعریف شده باشند ، آنگاه داریم :
آنگاه
اگر آنگاه 𝐶𝑖=∅ یا که خط کران است .
اثبات :
فرض کنید ، چون و در نتیجه . بعلاوه نقطه بهینه در نمی تواند بهتر از نقطه بهینه در چون ، بنابراین راس بهینه در می باشد .
اسلاید 18 :
ii) فرض کنید ، برای رسیدن به تناقض فرض کنید تهی نباشد و نیز روی خط قرار نگیرد ,پاره خط را در نظر بگیرید .
, چون است و همچنین داریم .
چون محدب است ،پاره خط داخل قرار دارد و نقطه ی
نقطه بهینه است و تابع هدف در جهت پاره خط افزیش می یابد . (حرکت از به ) .
قطعاً پاره خط و نقطه برخوردی مثل q دارند زیرا و
چون پاره خط در داخل قرار دارد نقطه q نیز باید در قرار داشته باشد ، اما مقدار تابع هدف در طول پاره خط افزایش می یابد
بنابراین در تناقض با تعریف است .
اسلاید 19 :
پیدا کردن راس بهینه :
برای این کار باید نقطه p روی را به دست آوریم بطوریکه ماکزیمم شود و
1) اگر آنگاه قرار می دهیم.
2) اگر آنگاه باید Vi را روی li به دست آوریم.
می توانیم را با یک مختص x نشان دهیم.
اسلاید 20 :
اگر محدودیت hj برای همه نقاط روی برقرار باشد میتوان آن محدودیت را نادیده گرفت .
مختص x نقطه برخورد hj و li را xj می نامیم.
xj = li Ç hj
