واننده دور اندیش ممکن است چند پله بالاتر را در نظر بگیرد. هنگامی که ما سود مورد انتظار خود را افزایش می دهیم، خط چین نشان دهنده نقاط هم سود، بصورت موازی به سمت بالا انتقال پیدا می کند. این انتقال تا دورترین نقطه ممکنی است که بهترین سود را در یک نقطه شدنی حاصل نماید. این آخرین و بهترین نقطه، C = 30 , A = 60 است و بر روی خط 20A + 30C 2100 قرار دارد. توجه داشته باشید که هر چند سهم سود هر واحد برای Cosmo بیشتر است، اما بیش از 30 دستگاه از آن تولید نکردیم، اگر چه تولید 50 دستگاه نیز شدنی بود. بطور شهودی این نقطه بهینه است و در واقع تنها این نقطه بهینه می باشد. تجزیه و تحلیل گرافیکی این مسئله به ما در فهم آنچه که در مدلهای بزرگتر اتفاق می افتد، کمک می کند.
1 – 4 ) خطی بودن :
اکنون با یک مثال آشنا شدیم. در ادامه مجدداً نیز به این مثال باز خواهیم گشت. این نمونه ای از یک برنامه ریزی خطی است که به اختصار LP نامیده می شود. حل برنامه های خطی بطور ذاتی به مراقب ساده تر از برنامه های کلی تر ریاضیاتی است. بنابراین ارزش این را دارد که در مورد ویژگی – های خطی بودن بیشتر بدانیم.
برنامه ریزی خطی بصورت مستقیم فقط در شرایطی به کار می رود که تاثیر فعالیتهای مختلف در جایی که ما با آن سر و کار داریم، بصورت خطی است. برای مقاصد کاربردی، می توانیم ملزومات خطی بودن را مشتمل بر سه خصوصیت زیر بدانیم :
1 ) متناسب بودن : تاثیر یک متغیر مجزا به خودی خود متناسب است. مثلاً دو برابر شدن میزان فولاد خریداری شده، منجر به دو برابر شدن هزینه خرید آن می شود.
2 ) جمع پذیری : روابط بین متغیرها باید بصورت جمع باشد. برای مثال مقدار دلاری فروش، مجموع فروش دلاری فولاد + فروش دلاری آلومینیم + ... است.
3 ) پیوستگی : متغیرها می بایست پیوسته باشند. برای مثال مقادیر اعشاری برای متغیرهای تصمیم همچون 6.38 مجاز است. اگر 2 و 3 هر دو جواب شدنی باشند، آنگاه 51 . 2 نیز شدنی است. مدلی که شامل دو متغیر تصمیم «قیمت هر واحد فروش رفته» و «مقدار واحد فروش رفته» می باشد، ممکن است متناسب بودن و جمع پذیری را ارضا کند، اما شرایط پیوستگی را نقض کند. فرمولاسیون ممکن برای مواردی که LP به کار می رود، بطور ذاتی بسیار کلی تر از مثال ارائه شده است. تابع هدف ممکن است به جای بیشینه سازی، کمینه سازی باشد. جهت محدودیتها می تواند به جای > ، < باشد و هر یا همه پارامترها می توانند منفی باشند.محدودیت اصلی در دسته مسائلی که می تواند تجزیه و تحلیل شود، از محدودیت خطی بودن منتج می شود.
برای مثال عبارت X * Y ، شرایط متناسب بودن را ارضا می کند، اما تاثیر X و Y بصورت جمع پذیری نیست. در عبارت ، تاثیر X و Y بصورت جمع پذیری است، اما تاثیرات هیچ کدام از آندو بصورت متناسب بودن نیست.
1 – 5 ) تجزیه و تحلیل حل های LP
هنگامی که از کامپیوتر حل یک مسئله ریاضی را می خواهید. برای یک مدل LP درست فرموله شده، مسیر منتها الیه سمت چپ به کار برده می شود. رویه حل ابتدا در پی یافتن یک حل شدنی است. برای مثال حلی که همه محدودیتها را ارضا کند، اما الزاماً بهترین حل نباشد. حل منتها الیه سمت راست که حل حل نشدنی است، در صورتیکه فرموله کننده مصر باشد به کار می رود . یعنی دو یا چند محدودیت که نمی توانند بطور همزمان ارضا شوند، بعنوان مثال دو محدودیت 2 > x و 3 <x عدم وجود حل شدنی به تابع هدف بستگی ندارد، بلکه تنها به محدویتها بستگی دارد.
در عمل خروجی No Feasible Solution یا «حل شدنی موجود نمی باشد» می تواند در مسائل بزرگ و پیچیده که در آن یک حد بالا بر روی تعداد ساعتهای در دسترس قابل استفاده است و تقاضای بالای غیر واقع بینانه بر روی تعداد واحدهای تولیدی می باشد. پیغام معادل برای «حل شدنی وجود ندارد» این است که «نمی توانید هم کیک را داشته باشید و هم آن را بخورید!».
اگر یک جواب پیدا شود. آنگاه حل کننده تلاش می کند حل بهینه را بیابد. اگر حالت «حل بیکران» اتفاق بیفتد، دلالت بر این دارد که فرمولاسیون مدل منجر به حالتی می شود که در آن سود بی نهایت امکان پذیر است.
نتیجه گیری واقع بینانه تر آن است که یک محدودیت مهم حذف شده است یا فرمولاسیون شامل خطایی در نوشتن مدل است.
برای نوشتن مدل مسئله Enginola در LINGO کافیست این گونه بنویسیم:
MODEL:
MAX=20 * A+30*C;
A<=60
C<=50
A+2*c<=120;
END
گزارش حل بدین صورت خواهد بود:
Objective value: 2100.000
Variable Value Reduced Cost
A 60.00000 0.00000
C 30.00000 0.00000
Row Slack or surplus Dual rice
1 2100.00000 1.00000
2 0.00000 5.00000
3 20.00000 0.00000
4 0.00000 15.00000
خروجی مدل شامل سه بخش است: قسمت حاوی اطلاعات مفید؛ سمت متغیرها، قسمت سطرها، قسمت های دوم و سوم سر راست هستند. راه حل سود بهینه عبارت است از تولید 60 دستگاه Astro و 30 Cosmo برای دستیابی به سود 2100 دلار، این راه حل مقدار مازاد صفر را در سطر دوم مدل ( ) به جا می گذارد، مقدار مازاد 20 در سطر سوم، ( )و عدم وجود مازاد در سطر چهارم مدل ( )را منجر می شود.
سومین ستون شامل تعدادی فرصت با صورتهای هزینه ای حاشیه ای است. تغییر این هزینه های تقلیل یافته (Reduced Cost )، در ادامه توضیح داده می شود: قسمت reduct cost/dual price اختیاری هستند و می توان آنها را در مسیر زیر فعال یا غیر فعال کرد.
LINGO | Options| General Solver| Dual Computations | prices
1 . 6 ) تجزیه و تحلیل حساسیت، هزینه های تقلیل یافته و قیمت های مزدوج:
مدل های LP واقعی نیاز به حجم بالایی از داده ها دارند. جمع آوری داده های دقیق هزینه بر است.
بنابراین ملزم به استفاده از داده ها در موارد ی هستیم که تقریباً اطمینان کمتری داریم. یک مثل معروف در جمع آوری داده می گوید: «زباله درون، زباله بیرون. کاربر در مدل باید بداند با تغییر در داده های ورودی، چه تغییراتی در خروجی های مدل رخ می دهد. تجزیه و تحلیل حساسیت، روشی برای پاسخگویی به این سوال است. خوشبختانه گزارش حل LP ، اطلاعات مکملی را که برای تجزیه و تحلیل حساسیت مفید است، ارائه می دهد.
این اطلاعات همان «Reduced Costs» و «Dual Prices» هستند. تجزیه و تحلیل حساسیت نشان می دهد که چه قسمتهایی از اطلاعات می بایست با بیشترین دقت تخمین زده شوند. برای مثال، اگر به وضوح مشخص باشد که محصول مشخصی سود آور نیست. آنگاه تلاش کمی برای تخمین دقیق هزینه های آن لازم خواهد بود. اولین قانون در مدل سازی این است که: وقت خود را برای یافتن مقدار دقیق پارامتری که خطای کوچکی در آن، تاثیر کمی در تصمیم توصیه شده دارد، تلف نکنید.
1 . 6 . 1 ) هزینه های تقلیل یافته:
متناظر یا هر متغیر در هر حلی، مقداری تحت عنوان هزینه تقلیل یافته وجود دارد. اگر واحدهای تابع هدف بر حسب دلار باشند و واحدهای متغیر بر حسب گالن، آنگاه واحدهای هزینه تقلیل یافته بر حسب دلار بر هر گالن خواهند بود. هزینه تقلیل یافته هر متغیر مقداری است که به ازای آن سهم سود آن متغیر باید بهبود یابد تا آن را واجد شرایط قرار گرفتن در حل بهینه با یک مقدار مثبت نماید. در مورد توابع هدف هزینه ای، این بهبود به معنی کاهش هزینه است. از تعریف هزینه تقلیل یافته واضح است که متغیرهای درون حل بهینه، هزینه تقلیل یافته صفر دارند.
تعبیر دیگری از هزینه تقلیل یافته، است که تابع هدف با غیر صفر شدن یکی از متغیرهای که در حل بهینه مقدار صفر را اختیار کرده است. افت می کند. برای مثال اگر هزینه تقلیل یافته متغیر x، که در حل بهینه مقدار صفر را اختیار کرده است، 2 دلار بر هر گالن باشد، بدین معناست که چنانچه سود آوری هر واحد متغیر x، 2 دلار افزایش یابد. با ورود 1 واحد از ان به حل بهینه (اگر 1 واحد یک متغیر کوچک باشد.) سود کلی تغییری نمی کند. واضح است که اگر x بدون تغییر در سهم سود خود (ضریب x در تابع هدف) تا یک واحد افزایش یابد، مقدار تابع هدف 2 دلار کاهش می یابد.
1 . 6 . 2 ) قیمت های مزدوج:
متناظر با هر محدودیت، کمیتی وجود دارد که آن را با نام قیمت مزدوج با قیمت دو گان می شناسیم. اگر واحدهای تابع هدف بر حسب دلار و واحد محدودیتها بر حسب کیلو گرم باشند، آنگاه واحدهای هزینه تقلیل یافته برابر با دلار بر کیلو گرم خواهد بود. قیمت دو گان یک محدودیت، نرخ بهبود تابع هدف به ازای تغییر کوچکی در مقدار سمت راست آن محدودیت است.
برنامه های مختلف بهینه سازی ممکن است از علائم متفاوتی در ارتباط با قیمت های مزدوج استفاده کنند. برای LINGO منظور از یک قیمت مزدوج مثبت بهبودی است که با افزایش مقدار سمت راست محدودیت در تابع هدف حاصل می شود. از سوی دیگر قیمت مزدوج منفی به معنی افت تابع هدف در صورت افزایش مقدار سمت راست محدودیت است. قیمت مزدوج صفر نیز به معنی این است که تغییر مقدار سمت راست محدودیت، هیچ تاثیری در مقدار حل ندارد.
با توجه به این قرار داد، محدودیت های کوچکتری مساوی ( ) قیمت های دو گان نا منفی و محدودیت های بزرگتر مساوی ( ) قیمت های دو گان نا مثبت خواهند داشت. محدودیتهایی که به صورت تساوی ارضا می شوند نیز می توانند هر نوع قیمت مزدوجی داشته باشند چرا؟
بهتر است در اینجا مفهوم قیمت های مزدوج را درک کنیم تا بتوانیم آنها را در حل مسئله Enginola تجزیه و تحلیل کنیم. قیمت مزدوج محدودیت برابر با 5 دلار به ازای هر واحد است. در وهله اول ممکن است شک کنید که این مقدار باید 20 دلار هر واحد باشد. چرا که اگر یک دستگاه بیشتر تولید شود، سهم سود این یک واحد اضافه 20 دلار خواهد بود. اما باید توجه داشت که برای تولید یک دستگاه Astro بیشتر، لازم است که سایر محدودیتها ارضا شوند.
هنگامی که تمامی موجودی نیروی کار مصرف شده است، تولید یک واحد Astro اضافه باعث کاهش تولید Cosmo خواهد شد. زیرا لازم است برای تولید Astro اضافه، مقداری از نیروی کار آزاد شود. نرخ مبادله نیروی کار برای Astro و Cosmo برابر با یعنی تولید 1 واحد اضافه Astro، باعث کاهش واحد از می شود. افزایش خالص سود برابر با دلار خواهد بود. چرا که سهم سود Cosmo برابر 30 دلار است.
اکنون قیمت مزدوج 15 دلار بر ساعت را برای محدودیت نیروی کار در نظر بگیرید. اگر 1 ساعت بیشتر نیروی کار داشته باشیم، فقط برای تولید محصول سود آور تر Cosmo مصرف می شد. هر واحد Cosmo، سهم سودی معادل 30 دلار دارد. از آنجا که یک ساعت نیروی کار فقط برای تولید واحد Cosmo کفایت می کند، ارزش یک ساعت نیروی کار اضافی برابر با دلار خواهد بود.
1 . 7 ) فرمولاسیونهای بیکران:
اگر فراموش کردیم که محدودیت نیروی کمار و محدودیت تولید Cosmo را وارد کنیم، آنگاه می توان مقدار نامحدودی سود با تولید، مقدار زیادی Cosmo به دست آوریم، این مساله در اینجا نشان داده شده است:
MAX=20*A+30*C;
A<=60;
این باعث ظاهر شدن پیغام خطای UNBOUNDED SOLUTION می شود، چرا که هیچ محدودیتی بر روی c برای اینکه به صورت نامحدود بزرگ نشود وجود ندارد. در مسائل بزرگتر، بطور معمول چند متغیر بیکران وجود دارد و نمی توان به راحتی تشخیص داد که بیکران تابع هدف از کجا ناشی شده است.
1 . 8 ) فرمولاسیون های نشدنی:
مثالی از فرمولاسیون نشدنی هنگامی است که مقدار سمت راست نیروی کاری به 190 تغییر یافته و جهت نامساوی نیز تغییر کند. در این مورد حداکثر نیروی کاری که می تواند برای تولید 60 واحد Astro و 50 واحد Cosmo مورد استفاده قرار گیرد، برابر با ساعت است؛ در صورتیکه در محدودیت باید بزرگتر مساوی 190 باشد:
MAX= (20*A)+(30*C);
A<=60;
C<=50;
A+2*C>=190;
پنجره ای با پیغام خطای NO FEASIBLE SOLUTION ظاهر خواهد شد. پنجره گزارش حل، اطلاعات زیر را تولید خواهد کرد:
Variable Value Reduced Cost
A 60.00000 0.00000
C 50.00000 0.00000
Row Slack or Surplus Dual price
1 2700.00000 0.00000
2 0.00000 1.00000
3 0.00000 2.00000
4 -30.00000 -1.00000
حل برای محدودیت نیروی کار، به میزان نفر ساعت نشدنی خواهد بود. قیمت هیا مزدوج در این حالت اطلاعات مفیدی در تعیین اینکه چگونه نشدنی بودن روی می دهد در اختیار ما قرار می دهند. برای مثال 1+ در سطر 2 بدین معناست که افزایش مقدار سمت راست آن، به میزان 1 واحد، نشدنی بودن به میزان 1 واحد کاهش خواهد داد. 2+ در سطر 3 یعنی اگر مجاز به تولید 1 واحد Cosmo اضافه باشیم، نشدنی بودن به میزان 2 واحد کاهش خواهد یافت. زیرا هر واحد Cosmo، 2 نفر ساعت از نیروی کار مصرف خواهد کرد. مقدار 1- متناظر با سطر 4 نیز بدین معناست که کاهش مقدار سمت راست محدودیت نیروی کار به میزان 1 واحد، نشدنی را به میزان 1 واحد کاهش خواهد داد.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 63 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلود مقاله بهینه سازی و توابع دامنه متغیر در LINGO
