Online User 6 مفهوم کلیدی حل در روش سیمپلکس - مدیریت صنعتی Industrial Management

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

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

6 مفهوم کلیدی حل در روش سیمپلکس
نویسنده : محسن رحیمی - ساعت ٩:٤٩ ‎ب.ظ روز ۱۳٩٠/٤/۳۱
 

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

از آنجا که تعداد جواب های موجه بی نهایت است، کاهش تعداد جواب هایی که باید بررسی شوند به تعدادی محدود و کوچک یکی از ویژگی های بسیار مطلوب این روش است.

مفهوم کلیدی 2: روش سیمپلکس یک الگوریتم تکراری است. این روش دارای یک رویه حل نظام مند است که در آن مجموعه ای از مراحل، که به آنها تکرار[1] می گویند، به طور متوالی انجام می شوند تا اینکه نتیجه مطلوب بدست آید. ساختار این تکرارها به صورت زیر است:

 

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

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

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

مفهوم کلیدی 4: با فرض قرار داشتن در یک نقطه CPF، از لحاظ محاسباتی بدست آوردن اطلاعات در رابطه با جواب های CPF مجاور بسیار سریع تر از کسب اطلاعات دیگر جواب های CPF است. بنابراین روش سیمپلکس در هر تکرار از نقطه جواب CPF حاضر همیشه به سمت یکی از جواب های CPF مجاور این نقطه که تابع هدف را بهتر می کند، حرکت می کند و در نتیجه مسیر دستیابی به جواب بهینه در این روش بر تعدادی از لبه های فضای موجه واقع می شود.

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

در تکرار اول حل مسئله شرکت ویندور، با در نظر داشتن تابع هدف Z=3x1+5x2، حرکت روی لبه واقع بر محور x2 تابع هدف را با سرعت بیشتری نسبت به حرکت روی لبه واقع بر محور x1 افزایش می دهد. هر یک واحد حرکت بر لبه واقع بر محور x2 تابع هدف را 5 واحد افزایش می دهد در صورتی که هر یک واحد حرکت بر لبه واقع بر محور x1 تابع هدف را 3 واحد افزایش می دهد. بنابراین حرکت باید بر لبه واقع بر محور x2 صورت گیرد. در مرحله تکرار دوم تنها لبه خروجی از (0,6) که نرخ رشد تابع هدف در مسیر آن مثبت است، لبه ای است که به (2,6) ختم می شود، در نتیجه حرکت در مسیر این لبه صورت می گیرد.

مفهوم کلیدی 6: در مفهوم کلیدی 5 اشاره شد که روش سیمپلکس چگونه هر یک از لبه هاب خروجی از جواب CPF جاری را بررسی می کند. این بررسی با تعیین نرخ رشد تابع هدف در جهت لبه ها صورت می گیرد. اگر نرخ رشد تابع هدف در مسیر یک لبه مثبت باشد به این معناست که نقطه CPF مجاور که در انتهای لبه مذکور قرار دارد بهتر از جواب CPF جاری است. به همین ترتیب اگر این نرخ منفی باشد جواب CPF مجاور انتهای لبه مورد نظر از جواب CPF جاری بدتر است. اگر هیچ کدام از لبه های خروجی از جواب  CPFجاری دارای نرخ رشد مثبت نباشند، این جواب بهینه است.

در مثال مرتبط قبل حرکت بر روی هر دو لبه خروجی از (2,6) باعث کاهش مقدار تابع هدف می شود و از آنجا که هدف ماکزیمم کردن تابع هدف است، در نتیجه نقطه (2,6) جواب بهینه خواهد بود.

پست مرتبط بعدی: آماده سازی مسئله برای حل با روش جبری سیمپلکس

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



[1] iteration