بخشی از پاورپوینت
اسلاید 1 :
تحقیق در عملیات جنگل Forest Operation Research
اسلاید 2 :
روش سیمپلکس
متغیرهای کمبود Slack variables
اولین مرحلۀ روش سیمپلکس تبدیل تمامی نامساویهای مدل برنامهریزی خطی به معادلات تساوی است
روش گرافیکی که برای حل در مثال قبلی به کار بردیم محدود به مواردی است که حداکثر 2 تا 3 متغیر تصمیمگیری در مدل وجود دارد. برای مسائل عملی بزرگ نیاز به یک روش کلیتر داریم.
روش سیمپلکس، یک روش جبری است و هنگامی که به صورت یک برنامه کامپیوتری نوشته شود، میتوان با کمک آن مسائل بزرگی که حتی هزاران متغیر و محدودیت دارند را حل کرد.
به عنوان مثال، مسئلۀ شاعر جنگلدار را در نظر بگیرید، هدف پیدا کردن میزان سطحی از جنگل کاج قرمز (x1) و پهنبرگان (x2 ) که بایستی مدیریت شود تا حداکثر درآمد را برای شاعر تولید کند.
اسلاید 3 :
X1 + S1 = 40 ha s1 ≥ 0 مساحت کاج
اولین محدویت که به صورت یک معادلۀ نامساوی است، میتوان با معرفی یک متغیر اضافی ( S1) به نام متغیر کمبود Slack variables به یک معادلۀ تساوی تبدیل کرد
یادآوری میشود که (S1) در واقع نواحی از کاج قرمز است که مدیریت نمیشوند. به همین ترتیب، برای هر محدودیت این عمل انجام میگیرد و در نهایت مدل نهایی با 5 متغیر X1 , X2, S1, S2, S3 ) ) بدست میآید.
(S2, S3) متغیرهای کمبود برای اندازهگیری میزان مساحت پهنبرگان مدیریت نشده و زمان صرف نشده شاعر هستند
اسلاید 4 :
جواب عملی اساسی برای این برنامه خطی مطابق است با گوشههای پلیگون (OABCD)، گوشههای این پلیگون به عنوان نقاط حد یا انتهایی ناحیة عملی محسوب میشوند.
برای مثال، نقطة حد ( o ) مطابق است با جواب عملی
= (0, 0, 40.50, 180) x1 , x2, s1, s2, s3 از این رو در نقطة ( o )، ( 0= x1 , x2 ) و ( 40 = s1 )، (50 = s2)
(s3=180) خواهد بود. و به همین ترتیب جواب عملی اساسی در نقطة حد (A) برابر است با؛
= (0, 50, 40,0, 30) x1 , x2, s1, s2, s3،
توجه داشته باشیم که در هر جواب عملی اساسی، به همان تعداد محدودیتها، متغیرهای مثبت وجود دارند.
جوابهای عملی اساسی Basic feasible solutions
اسلاید 5 :
متغیرهای مثبت به عنوان متغیرهای اساسی نامیده میشوند، در حالی که، آنهایی که معادل صفر هستند را متغیرهای غیراساسی مینامیم.
در این مثال، سه متغیر اساسی و دو متغیر غیراساسی وجود دارند. این قاعده را برای نقاط حد B, C, D ، هم باید بپذیریم.
در یک برنامه خطی با ( n) متغیر (شامل متغیرهای کمبود هم است) و ( m ) محدودیت مستقل، یک جواب عملی دارای (m) متغیر اساسی و (n-m) متغیر غیر اساسی است
روش سیمپلکس در عوض، یک الگوریتم مرحله به مرحله است. این الگوریتم شامل حرکت از یک نقطه حد به نقطة حد مجاور در منطقة موجه و در مسیری که تابع هدف را به جواب هدایت میکند
نمودار الگوریتم سیمپلکس
اسلاید 6 :
برای تشریح اصول روش سیمپلکس، مسئلة شاعر جنگلدار را با مراحلی که توضیح دادیم حل خواهیم کرد
مرحلة اول: یافتن یک جواب عملی اساسی. سادهترین جواب عملی اساسی نقطة ( O ) در شکل است، یعنی
(0 = x1 , x2)
(s3=180)
(50 = s2)
( 40 = s1 )
متغیر اساسی
متغیر غیراساسی
Zo = 0
تابع هدف
در این جواب اولیه، سه متغیر کمبود به عنوان متغیر اساسی هستند
مرحلة دوم: از آنجایی که ضریب (x1) در تابع هدف برابر 90 در هر هکتار است و ضریب (x2) برابر 120 است، تابع هدف بیشتر با حرکت از نقطة مبدأ مختصات (O) به سمت مسیر (Ox2) تا نقطة حد (A) افزایش خواهد یافت، که با جواب عملی اساسی جدید مطابقت میکند:
اسلاید 7 :
(0 = x1 , s2)
(30 s3=)
(50 x2=)
( 40 s1= )
متغیر اساسی
متغیر غیراساسی
ZA = 6000
تابع هدف
در حرکت از نقطة (O) به نقطة حد (A) متغیر (x2) که غیر اساسی بود تبدیل به متغیر اساسی شد. و متغیر (s2) که یک متغیر اساسی بود، تبدیل به متغیر غیراساسی شد.
مرحلة سوم: از نقطة حد (A) به سمت (O x1) حرکت خواهیم کرد، از آنجایی که این تنها مسیری است که شاید تابع هدف افزایش پیدا کند، نقطة حد مجاور بعدی ( B ) است، و جواب عملی اساسی در این نقطه به صورت زیر محاسبه میشود
(0 s3 , s2=)
(50 x2=)
(15 x1=)
( 25 s1= )
متغیر اساسی
متغیر غیراساسی
ZA = 7350
تابع هدف
اسلاید 8 :
مرحلة چهارم: از آنجایی که در تکرار قبلی تابع هدف افزایش پیدا کرد باید تکرار دیگری از نقطة حد را امتحان کنیم. تنها مسیر بعدی هم حرکت به سمت نقطة حد ( C) است که جواب عملی اساسی آن به صورت زیر است
(0 s3 , s1=)
(33 x2=)
(40 x1=)
( 16/7 s2= )
متغیر اساسی
متغیر غیراساسی
ZA = 7600
تابع هدف
مرحلة پنجم: در آخرین نقطة حد ما افزایش در تابع هدف داشتیم، لذا، ما نقطة دیگری را آزمایش میکنیم. نقطة حد مجاور بعدی نقطة ( D) خواهد بود و جواب عملی اساسی آن هم به صورت زیر است
(0 x2 , s1=)
(40 x1=)
(100 s3=)
(50 s2= )
متغیر اساسی
متغیر غیراساسی
ZA = 3600
تابع هدف
در این نقطه حد ارزش تابع هدف کاهش پیدا کرد. بنابراین، جواب بهینه، همان جواب عملی اساسی در نقطة ( C) است که در تکرار قبلی به آن رسیدیم
