جزوه تحقیق در عملیات ۱

بخشی از متن فایل
روش ترسیمی
گام اول : پیدا کردن منطقه موجه با ترسیم محدودیت ها
گام دوم: پیدا کردن جواب بهینه با ترسیم تابع هدف
با ترسیم محدودیت ها ۵ حالت می تواند اتفاق بیافتد:
۱ .منطقه موجه محدود
۲ .منطقه موجه نامحدود
۳ .منطقه موجه نداریم
۴ .منطقه موجه یک نقطه
۵ .منطقه موجه یک پاره خط
با ترسیم تابع هدف چهار حالت اتفاق می افتد
۱ .جواب بهینه یکتا
۲ .جواب بهینه چندگانه
۳ .جواب بهینه نامحدود
۴ .جواب تبهگن
برای ترسیم محدودیت ها باید
۱ .همه نامعادله را به معادله تبدیل کرده و با پیدا کردن مشخصات دو نقطه خط
آن را ترسیم می کنیم.
۲ .برای پیدا کردن منطقه موجه مشخصات مبدا مختصات )۰،۰ )را در نامعادله
قرار داده در صورتی که در نامعادله صادق باشد جهت منطقه به طرف مبدا
مختصات در غیراینصورت منطقه موجه خالف مبدا مختصات می باشد.
نکته:
اگر محدودیت ها به فرم نامعادله مبدا سمت به جواب فضای باشد ≥
مختصات و در صورتی که محدودیت به فرم سمت به جواب فضای .باشد ≤
خارج مبدا مختصات می باشد و نهایتا اگر محدودیت معادله = باشد فضای
جواب دقیقا بر روی خط قرار می گیرد.
فضای موجه (ناحیه موجه) در یک مسئله LP عبارت است از مجموعه نقاطی که
در تمام محدودیت های مسئله صدق می کند. به نقاط موجود در این فضا نقاط
موجه یا جواب های موجه گویند.
در یک مسئله LP به دنبال یافتن جواب )یا جواب های( از مجموعه جواب های
موجه هستیم که تعداد تابع هدف را به بهترین تعداد خود )Min/Max )برساند
به این جواب، جواب بهینه گفته می شود.
در یک مسئله LP با تابع هدف Max( Min )به خطوط موازی هم که به ازای
تخصیص مقادیر مختلف به تابع هدف مسئله به دست می آید خطوط هم سود/
خطوط هم هزینه گفته می شود.
نقاط گوشه: پس از مشخص شدن فضای جواب مشترک نقاط گوشه ای فضای
جواب را که محل تقاطع دو محدودیت با یکدیگر یا برخورد یک محدودیت با
یکی از محورهای مختصات می باشد را مشخص نموده، مختصات هر یک از آنها
را به دست می آوریم
ترسیم تابع هدف
۳ .اگر تابع هدف Max باشد جهت حرکت از ۱ 𝑍به طرف ۲ 𝑍است و اگر
تابع هدف min باشد جهت حرکت از ۲ 𝑍به ۱ 𝑍جهت بهینه سازی را
مشخص می کنیم.
با مشخص کردن جهت تابع هدف را آنقدر ادامه می دهیم )به صورت
موازی حرکت می دهیم ( تا آخرین منطقه موجه را لمس نمائید .
اگر آخرین منطقه یک نقطه باشد: جواب بهینه یکتا
اگر یک پاره خط باشد: جواب بهینه چندگانه
و اگر از آخرین منطقه خارج نشویم به آن بهینه نامحدود می گوئیم: جواب
بهینه بی کران
نکته
پیدا کردن جواب بهینه به دو روش مختصات گوشه ای و ترسیم تابع هدف
امکان پذیر می باشد
در روش اول تابع هدف را در نقاط گوشه محاسبه می کنیم و بیشترین مقدار Z
تعیین کننده نقطه بهینه می باشد
در روش دوم خط تابع هدف را در منطقه موجه حرکت می دهیم اگر تابع هدف از
نوع Min باشد، اولین نقطه ای که قطع شود نقطه بهینه و اگر تابع هدف از نوع
Max باشد آخرین نقطه ای که قطع می کند نقطه بهینه است