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

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

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

جواب های گوشه ای موجه مجاور در فضای چند بعدی
نویسنده : محسن رحیمی - ساعت ۱۱:٠۱ ‎ب.ظ روز ۱۳٩٠/۱۱/۱۸
 

در مطالب گذشته به معرفی جواب های گوشه ای موجه (جواب های CPF) مجاور و نقش آنها در حل مسائل برنامه ریزی خطی پرداختیم، اما در این مقاله سعی داریم کمی تخصصی تر و عمیق تر به آنها نگاهی دوباره بیندازیم. قبلاً به این نکته اشاره کرده ایم که هر تکرار روش سیمپلکس، در حقیقت حرکت از یک جواب CPF به یکی از جواب های CPF مجاور آن است. در این فرآیند چه مسیری طی می شود؟ ...

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

(1500 کلمه)

مطلب مرتبط بعدی: سه ویژگی مهم جواب های گوشه ای موجه

مطلب مرتبط قبلی: نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی


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

قبلاً به این نکته اشاره کرده ایم که هر تکرار روش سیمپلکس، در حقیقت حرکت از یک جواب CPF به یکی از جواب های CPF مجاور آن است. در این فرآیند چه مسیری طی می شود؟ مفهوم جواب CPF مجاور چیست؟ برای پاسخ به این سوالات ابتدا از دیدگاه هندسی استفاده خواهیم نمود و سپس تفسیر جبری ان را نیز ارائه خواهیم کرد.

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

شکل 1. مرزهای محدودیت و نقاط گوشه ای موجه یک مسئله نمونه (مسئله شرکت ویندور)

این پاره خط ها لبه های (edges) منطقه موجه هستند. از هر جواب CPF دو لبه خارج می شود که در انتهای آن یک جواب CPF دیگر مسئله قرار دارد. (در شکل 1 مشاهده می کنید که هر جواب CPF دارای دو جواب CPF مجاور است.) مسیری که در هر تکرار در روش سیمپلکس طی می شود، حرکت در طول یکی از این لبه ها از ابتدا به انتهای آن است. با توجه به شکل 1، اولین تکرار در روش سیمپلکس، بر لبه خروجی از نقطه (0,0) به سمت نقطه (0,6) حرکت می کند و سپس در تکرار بعدی روی لبه خروجی از نقطه (0,6) به نقطه (2,6) حرکت می کند. این حرکت به سمت نقطه CPF مجاور تنها با تغییر یکی از معادلات مشخصه (که همان مرزهای محدودیتی هستند که CPF ها در نقاط تقاطع آنها واقع شده اند) انجام می گیرد.

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

شکل 2. فضای موجه و جواب های CPF یک مسئله برنامه ریزی خطی سه بعدی

پاره خط تیره تری که در شکل 2 مشخص شده است نشان دهنده مسیر حرکت روش سیمپلکس در یکی از تکرارهایش است که اینجا قصد بررسی آن را داریم. نقطه (2,4,3) جواب CPF اولیه در هنگام شروع تکرار است و نقطه (4,2,4) جواب CPF جدیدی خواهد بود که در انتهای تکرار به آن رسیده ایم. نقطه (2,4,3) در محل تقاطع مرزهای محدودیت x2=4، x1+x2=6 و -x1+2x3=4 قرار دارد و به عبارت دیگر این سه معادله معادلات مشخصه این جواب CPF هستند. اگر معادله مشخصه x2=4 را حذف کنیم، تقاطع دو مرز محدودیت دیگر (که به صورت صفحه هستند) یک خط را تشکیل خواهد داد. بخشی از این خط همان خط تیره ای است که در شکل 2 نقطه (2,4,3) را به نقطه (4,2,4) متصل نموده است و بر مرز منطقه موجه واقع شده است. غیر از این پاره خط، مابقی خط در فضای غیر موجه قرار دارد. این پاره خط یکی از لبه های فضای موجه است و دو نقطه انتهایی آن یعنی نقاط (2,4,3) و (4,2,4) جواب های CPF مجاور محسوب می شوند.

برای n=3 یعنی در فضای سه بعدی، مانند توضیحات بالا، همه لبه های فضای موجه در حقیقت بخشی از خطوطی هستند که در اثر تقاطع دو مرز محدودیت ایجاد شده و در کلیه محدودیت ها نیز صدق نمایند. نقاط انتهایی این پاره خط ها همان جواب های CPF مجاور می باشند. در شکل 2 تعداد 15 لبه برای فضای موجه وجود دارد و بنابراین می توان گفت تعداد 15 جفت جواب CPF مجاور در این فضا وجود دارد. در جواب CPF کنونی، (2,4,3)، از آنجا که سه معادله مشخصه وجود دارد لذا سه حالت ممکن برای حذف یکی از این معادلات و تشکیل خط تقاطع دو معادله باقیمانده (مرز محدودیت) وجود خواهد داشت. بنابراین می توان گفت از نقطه (2,4,3) سه لبه خارج می شود که انتهای دیگر این لبه ها جواب های CPF مجاور جواب کنونی هستند که عبارتند از (4,2,4)، (0,4,2) و (2,4,0).

برای تکرار بعدی، روش سیمپلکس یکی از این سه لبه را انتخاب خواهد کرد که در اینجا لبه ای خواهد بود که در شکل 2 با خط ضخیم تر نشان داده شده است و حرکت از جواب (2,4,3) شروع شده و تا رسیدن به اولین مرز محدودیت جدید، x1=4، در انتهای دیگر لبه ادامه خواهد داشت. (باید دقت داشت که نمی توان بیشتر از این خط را ادامه داد و مثلاً تا مرز محدودیت بعدی یعنی x2=2 کشید زیرا با این کار به یک جواب گوشه ای غیر موجه، (6,0,5)، خواهیم رسید.) قطع دادن مرز محدودیت جدید با دو مرز محدودیت قبلی، جواب CPF جدید (4,2,4) را نتیجه خواهد داد.

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

با فرض روبرو بودن با یک مسئله برنامه ریزی خطی که دارای n متغیر تصمیم و فضای موجه کراندار است، نقطه تقاطع n مرز محدودیت را در صورتیکه در دیگر محدودیت ها نیز صدق کند، یک جواب CPF می گویند. همچنین در فضای موجه عبارت لبه به یک پاره خط موجه اطلاق می شود که از تقاطع n-1 مرز محدودیت تشکیل می شود به طوریکه نقاط ابتدایی و انتهایی آن روی یک مرز محدودیت جدید دیگر واقع شوند (که در حقیقت این نقاط ابتدایی و انتهایی همان جواب های CPF هستند). دو جواب CPF را مجاور می گویند اگر خط واصل بین این دو جواب یک لبه از فضای موجه باشد. از هر جواب CPF تعداد n لبه خارج می شود که در انتهای هر لبه یک جواب CPF مجاور قرار گرفته است. در هر تکرار از روش سیمپلکس، در حقیقت با حرکت بر روی یکی از n لبه، از جواب CPF فعلی به یک جواب CPF مجاور منتقل می شویم.

هنگامی که با گذر از دیدگاه هندسی، از دیدگاه جبری به روش سیمپلکس نگاه کنیم، عبارت "تقاطع مرز های محدودیت" به عبارت "جواب دستگاه معادلات مرزهای محدودیت" تغییر خواهد کرد. تعداد n معادله مرز محدودیتی که حل آنها منجر به تولید جواب CPF می گردد را معادلات مشخصه این جواب CPF می نامند و حذف یکی از این معادلات منجر به ایجاد خطی می شود که بخش موجه آن یک لبه از منطقه موجه خواهد بود.

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

مطلب مرتبط بعدی: سه ویژگی مهم جواب های گوشه ای موجه

مطلب مرتبط قبلی: نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی