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

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

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

نگاهی عمیق تر به روش سیمپلکس: اصطلاحات فضای سه بعدی
نویسنده : محسن رحیمی - ساعت ٥:٥٧ ‎ب.ظ روز ۱۳٩٠/۱٠/٢۳
 

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

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

(1260 کلمه)

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

مطلب مرتبط قبلی: قوانین ترکیب روش سیمپلکس با روش نقاط داخلی


برای شروع برخی از اصطلاحات اولیه در مسائل برنامه ریزی خطی با n متغیر تصمیم را معرفی می کنیم. برای درک بهتر این اصطلاحات توصیه می کنیم از شکل شماره 1 به منظور تفسیر و یادآوری این تعاریف در حالت دو بعدی استفاده نمایید.

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

برای هر محدودیت، معادله مرز محدودیت (Constraint boundary equation)، با جایگزین نمودن علامت مساوی به جای علائم کوچکتر مساوی، مساوی و بزرگتر مساوی بدست می آید.

بنابراین شکل معادله مرز محدودیت برای محدودیت های ساختاری به صورت

و برای محدودیت های غیر منفی بودن به صورت

خواهد بود.

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

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

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

مرز منطقه موجه شامل همه جواب های موجهی (جواب هایی که در همه محدودیت ها صدق کنند) است که در یک یا چند معادله مرز محدودیت صدق کنند.

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

اکنون تعریفی عمومی از جواب CPF در فضای n بعدی ارائه می دهیم.

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

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

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

جدول 1. معادلات مشخصه مربوط به جواب های CPF مسئله شرکت ویندور

معادلات مشخصه

جواب CPF

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

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

جدول 2. معادلات مشخصه جواب های گوشه ای غیر موجه در مسئله شرکت ویندور

معادلات مشخصه

جواب CPF

علاوه بر حالت بالا، یک دستگاه معادلات متشکل از n معادله مرز محدودیت ممکن است اصلاً دارای جواب نباشد. در مثال بالا این شرایط در مورد دو مجموعه از معادلات مصداق دارد، نمونه اول زوج معادله x1=0 و x1=4 است و نمونه دوم مربوط به زوج معادله x2=0 و 2x2=12 می باشد. چنین دستگاه معادلاتی در حل مسئله به هیچ وجه مورد توجه نیست.

آخرین حالت ممکن (در این این مثال با آن روبرو نشدیم) آن است که دستگاه معادلات متشکل از n معادله مرز محدودیت، به دلیل وجود معادله زاید، چندین جواب داشته باشد. البته روش سیمپلکس به خودی خود این حالت را در نظر می گیرد و ضرورتی در توجه به این مورد و انجام کار اضافه وجود ندارد.

به طور خلاصه می توان گفت، مثال بالا با پنج محدودیت و دو متغیر تصمیم، دارای 10 جفت معادله مرز محدودیت است که پنج جفت از آنها معادلات مشخصه جواب های CPF (جدول 1)، سه جفت از آنها معادلات مشخصه جواب های گوشه ای غیر موجه (جدول 2) هستند و دو جفت از این معادلات مشخصه بدون جواب می باشند.

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

مطلب مرتبط قبلی: قوانین ترکیب روش سیمپلکس با روش نقاط داخلی