Online User سه ویژگی مهم جواب های گوشه ای موجه - مدیریت صنعتی Industrial Management

مدیریت صنعتی Industrial Management

مدیریت صنعتی - تحقیق در عملیات - مدیریت تولید - ...

سه ویژگی مهم جواب های گوشه ای موجه
نویسنده : محسن رحیمی - ساعت ۸:٤٤ ‎ب.ظ روز ۱۳٩۱/۱/٢۳
 

در اینجا قصد داریم به معرفی سه ویژگی مهم و کلیدی جواب های گوشه ای موجه (جواب های CPF) بپردازیم که در هر مسئله برنامه ریزی خطی دارای فضای موجه کراندار صدق می کند...

  

جهت مطالعه متن کامل مقاله روی "ادامه مطلب" کلیک کنید.

(1000 کلمه)

مطلب مرتبط بعدی: اثبات جبری قرار گیری جواب بهینه در حداقل یکی از نقاط گوشه ای

مطلب مرتبط قبلی: جواب های گوشه ای موجه مجاور در فضای چند بعدی


در اینجا قصد داریم به معرفی سه ویژگی مهم و کلیدی جواب های گوشه ای موجه (جواب های CPF) بپردازیم که در هر مسئله برنامه ریزی خطی دارای فضای موجه کراندار صدق می کند.

ویژگی اول:

(a) اگر مسئله مورد نظر تنها دارای یک جواب بهینه باشد، این جواب بهینه حتماً یکی از جواب های CPF مسئله است. (b) اگر مسئله دارای جواب بهینه چندگانه باشد و همچنین فضای موجه مسئله کراندار باشد، آنگاه حداقل دو عدد از جواب ها باید جواب CPF مجاور باشند.

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

شکل 1

حال حالت (b) را در نظر بگیرید که نمونه آن در شکل 2 با تغییر تابع هدف مسئله ارائه شده است. اتفاقی که در این حالت رخ می دهد این است که در حل هندسی این مسئله، زمانیکه خط تابع هدف را به سمت بهتر شدن حرکت می دهیم در انتها، روی پاره خط واصل بین دو جواب (2,6) و (4,3) که جواب های CPF هستند، قرار می گیرد. در مسائل دارای ابعاد بزرگتر نیز همین فرآیند رخ می دهد با این تفاوت که در چنین فضایی، ابر صفحه تابع هدف است که به سمت بهبود حرکت می کند و در نهایت بر پاره خط (یا پاره خط های) متصل کننده دو (یا بیشتر) جواب CPF مجاور منطبق می گردد. به عنوان یک نتیجه در چنین مواردی باید گفت همه جواب های بهینه را می توان به صورت میانگین های وزنی جواب های CPF نوشت.

شکل 2

اهمیت ویژگی اول این است که جستجوی جواب بهینه مسئله را ساده می کند زیرا اکنون می دانیم که جواب بهینه را باید تنها در میان جواب های CPF یافت. اهمیت این نکته با ویژگی دوم پر رنگ تر هم می شود.

ویژگی دوم:

تعداد جواب های CPF محدود و متناهی است.

برای درک این مطلب که چرا تعداد جواب های CPF متناهی است، با در نظر گرفتن اینکه n تعداد متغیرها m تعداد محدودیت های مسئله باشد، به خاطر آورید که هر جواب CPF در حقیقت حل دستگاه معادلاتی شامل n از تعداد کل n+m معادله مرز محدودیت است. تعداد ترکیبات nتایی مختلفی که می توان از n+m معادله استخراج نمود عبارت است از:

که عددی متناهی و محدود است. در حقیقت عددی که از رابطه بالا به دست می آید حداکثر تعداد جواب های CPF خواهد بود. در شکل 1 داریم m=3 و n=2، بنابراین تعداد 10 دستگاه معادلات که شامل دو معادله مرز محدودیت باشند وجود خواهد داشت اما تنها نیمی از آنها جواب CPF ارائه می دهند.

بر اساس ویژگی دوم می توان این مطلب را مطرح نمود که یک جواب بهینه را می توان با یافتن و مقایسه همه جواب های CPF که تعداد آنها متناهی نیز هست به دست آورد. متاسفانه با اینکه تعداد جواب های CPF متناهی می باشد اما می تواند عدد بسیار بزرگی باشد. برای نمونه یک مسئله برنامه ریزی خطی نسبتا کوچک را با تنها m=50 و n=50 در نظر بگیرید که بر اساس رابطه بالا حدود 1029 دستگاه معادلات برای حل دارد. در مقابل روش سیمپلکس برای یافتن جواب بهینه تقریباً حدود 100 جواب CPF را برای مسئله ای در این اندازه بررسی می کند. این مقدار صرفه جویی فاحش در اثر آزمون بهینگی حاصل می شود که در اینجا به شکل ویژگی سوم خود را نمایش می دهد.

ویژگی سوم:

اگر یک جواب CPF از همه جواب های CPF مجاور خود بهتر باشد (از نظر بهبود تابع هدف) آنگاه هیچ جواب CPF دیگری وجود ندارد که از آن بهتر باشد. بنابراین چنین جواب CPFای (با توجه به ویژگی اول) حتماً یک جواب بهینه مسئله خواهد بود با این فرض که مسئله حداقل یک جواب بهینه داشته باشد. (یعنی دارای فضای موجه کراندار باشد).

برای آشنایی بیشتر با این ویژگی، شکل 1 را دوباره در نظر بگیرید. در این شکل، جواب CPF (2,6)، دارای دو جواب CPF مجاور به مختصات (0,6) و(4,3) است که هیچ کدام از این دو نقطه دارای مقدار تابع هدف بهتری نسبت به (2,6) نیستند. بر اساس ویژگی سوم می توان نتیجه گرفت که هیچ جواب CPF دیگری نیز (در اینجا (0,0) و (4,0)) نمی توانند دارای مقدار هدف بالاتری باشند و در نتیجه (2,6) نقطه بهینه مسئله است.

در مقابل، شکل 3 که در زیر آمده است، فضای موجهی را نشان می دهد که هرگز برای یک مسئله برنامه ریزی خطی رخ نمی دهد، اما ویژگی سوم را نقض می کند. مسئله شکل نشان داده شده تقریباً شبیه به شکل 1 است با این تفاوت که فضای موجه در این مسئله جدید به سمت راست نقطه (8/3,5) کشیده شده است. در نتیجه جواب های CPF مجاور کنونی نقطه (2,6) عبارتند از (0,6) و (8/3,5) که هیچ کدام مقدار هدف بهتری را نسبت به مقدار هدف ناشی از نقطه (2,6) نشان نمی دهند. با این حال جواب CPF دیگری، (8/3,5)، وجود دارد که مقدار تابع هدف متناظر با آن بهتر از مقدار هدف متناظر با نقطه (8/3,5) است و این یعنی نقض ویژگی سوم.

شکل 3

نکته کلیدی در اینجا این مطلب است که وقوع موقعیت نمایش داده شده در شکل 3 و موقعیت های مشابه، در مسائل برنامه ریزی خطی امری غیر ممکن است. دلیل اصلی و منطقی برقرار بودن ویژگی سوم برای همه مسائل برنامه ریزی خطی آن است که فضای موجه این مسائل همیشه دارای خصوصیات یک مجموعه محدب می باشد. توضیح کامل مشخصات و ویژگی های مجموعه های محدب را در مطالب اینده ارائه خواهم نمود. اما به شکلی مختصر برای یک مسئله برنامه ریزی خطی با دو متغیر تصمیم، ویژگی محدب بودن به این معناست که زاویه داخلی فضای موجه در هر جواب CPF مقداری کوچکتر از 180 درجه است. این ویژگی را به راحتی در شکل 1 مشاهده می کنید. در مقابل می توان گفت فضای موجه شکل 3 یک مجموعه محدب نیست و ویژگی محدب بودن را ندارد، زیرا زاویه داخلی این فضا در نقطه (8/3,5) بیشتر از 180 درجه است.

مطلب مرتبط بعدی: اثبات جبری قرار گیری جواب بهینه در حداقل یکی از نقاط گوشه ای

مطلب مرتبط قبلی: جواب های گوشه ای موجه مجاور در فضای چند بعدی