• بازدید : 42 views
  • بدون نظر
این فایل در ۶۸صفحه قابل ویرایش تهیه شده وشامل موارد زیر است:

اکنون با یک مثال آشنا شدیم. در ادامه مجدداً نیز به این مثال باز خواهیم گشت. این نمونه ای از یک برنامه ریزی خطی است که به اختصار LP نامیده می شود. حل برنامه های خطی بطور ذاتی به مراقب ساده تر از برنامه های کلی تر ریاضیاتی است. بنابراین ارزش این را دارد که در مورد ویژگی – های خطی بودن بیشتر بدانیم.
برنامه ریزی خطی بصورت مستقیم فقط در شرایطی به کار می رود که تاثیر فعالیتهای مختلف در جایی که ما با آن سر و کار داریم، بصورت خطی است. برای مقاصد کاربردی، می توانیم ملزومات خطی بودن را مشتمل بر سه خصوصیت زیر بدانیم :
۱ ) متناسب بودن : تاثیر یک متغیر مجزا به خودی خود متناسب است. مثلاً دو برابر شدن میزان فولاد خریداری شده، منجر به دو برابر شدن هزینه خرید آن می شود.
) جمع پذیری : روابط بین متغیرها باید بصورت جمع باشد. برای مثال مقدار دلاری فروش، مجموع فروش دلاری فولاد + فروش دلاری آلومینیم + … است.
۳ ) پیوستگی : متغیرها می بایست پیوسته باشند. برای مثال مقادیر اعشاری برای متغیرهای تصمیم همچون ۶٫۳۸ مجاز است. اگر ۲ و  3 هر دو جواب شدنی باشند، آنگاه ۵۱ . ۲ نیز شدنی است. مدلی که شامل دو متغیر تصمیم «قیمت هر واحد فروش رفته» و «مقدار واحد فروش رفته» می باشد، ممکن است متناسب بودن و جمع پذیری را ارضا کند، اما شرایط پیوستگی را نقض کند. فرمولاسیون ممکن برای مواردی که LP به کار می رود، بطور ذاتی بسیار کلی تر از مثال ارائه شده است. تابع هدف ممکن است به جای بیشینه سازی، کمینه سازی باشد. جهت محدودیتها می تواند به جای > ، < باشد و هر یا همه پارامترها می توانند منفی باشند.محدودیت اصلی در دسته مسائلی که می تواند تجزیه و تحلیل شود، از محدودیت خطی بودن منتج می شود.
برای مثال عبارت X * Y ، شرایط متناسب بودن را ارضا می کند، اما تاثیر X و Y بصورت جمع پذیری نیست. در عبارت  ، تاثیر X و Y بصورت جمع پذیری است، اما تاثیرات هیچ کدام از آندو بصورت متناسب بودن نیست.

۱ – ۵ ) تجزیه و تحلیل حل های LP 
هنگامی که از کامپیوتر حل یک مسئله ریاضی را می خواهید. برای یک مدل LP درست فرموله شده، مسیر منتها الیه سمت چپ به کار برده می شود. رویه حل ابتدا در پی یافتن یک حل شدنی است. برای مثال حلی که همه محدودیتها را ارضا کند، اما الزاماً بهترین حل نباشد. حل منتها الیه سمت راست که حل حل نشدنی است، در صورتیکه فرموله کننده مصر باشد به کار می رود . یعنی دو یا چند محدودیت که نمی توانند بطور همزمان ارضا شوند، بعنوان مثال دو محدودیت ۲ > x و ۳ <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
۱   2100.00000   1.00000
۲   0.00000   5.00000
۳   20.00000   0.00000
۴    0.00000    15.00000
خروجی مدل شامل سه بخش است: قسمت حاوی اطلاعات مفید؛ سمت متغیرها، قسمت سطرها، قسمت های دوم و سوم سر راست هستند. راه حل سود بهینه عبارت است از تولید ۶۰ دستگاه Astro و ۳۰ Cosmo برای دستیابی به سود ۲۱۰۰ دلار، این راه حل مقدار مازاد صفر را در سطر دوم مدل ( ) به جا می گذارد، مقدار مازاد ۲۰ در سطر سوم، ( )و عدم وجود مازاد در سطر چهارم مدل ( )را منجر می شود.
سومین ستون شامل تعدادی فرصت با صورتهای هزینه ای حاشیه ای است. تغییر این هزینه های تقلیل یافته (Reduced Cost )، در ادامه توضیح داده می شود: قسمت reduct cost/dual price اختیاری هستند و می توان آنها را در مسیر زیر فعال یا غیر فعال کرد.
LINGO | Options| General Solver| Dual Computations | prices
 1 . 6 ) تجزیه و تحلیل حساسیت، هزینه های تقلیل یافته و قیمت های مزدوج:
مدل های LP واقعی نیاز به حجم بالایی از داده ها دارند. جمع آوری داده های دقیق هزینه بر است.
بنابراین ملزم به استفاده از داده ها در موارد ی هستیم که تقریباً اطمینان کمتری داریم. یک مثل معروف در جمع آوری داده می گوید: «زباله درون، زباله بیرون. کاربر در مدل باید بداند با تغییر در داده های ورودی، چه تغییراتی در خروجی های مدل رخ می دهد. تجزیه و تحلیل حساسیت، روشی برای پاسخگویی به این سوال است. خوشبختانه گزارش حل LP ، اطلاعات مکملی را که برای تجزیه و تحلیل حساسیت مفید است، ارائه می دهد. 
این اطلاعات همان «Reduced Costs» و «Dual Prices» هستند. تجزیه و تحلیل حساسیت نشان می دهد که چه قسمتهایی از اطلاعات می بایست با بیشترین دقت تخمین زده شوند. برای مثال، اگر به وضوح مشخص باشد که محصول مشخصی سود آور نیست. آنگاه تلاش کمی برای تخمین دقیق هزینه های آن لازم خواهد بود. اولین قانون در مدل سازی این است که: وقت خود را برای یافتن مقدار دقیق پارامتری که خطای کوچکی در آن، تاثیر کمی در تصمیم توصیه شده دارد،  تلف نکنید.
۱ . ۶ . ۱ ) هزینه های تقلیل یافته:
متناظر یا هر متغیر در هر حلی، مقداری تحت عنوان هزینه تقلیل یافته وجود دارد. اگر واحدهای تابع هدف بر حسب دلار باشند و واحدهای متغیر بر حسب گالن، آنگاه واحدهای هزینه تقلیل یافته بر حسب دلار بر هر گالن خواهند بود. هزینه تقلیل یافته هر متغیر مقداری است که به ازای آن سهم سود آن متغیر باید بهبود یابد تا آن را واجد شرایط قرار گرفتن در حل بهینه با یک مقدار مثبت نماید. در مورد توابع هدف هزینه ای، این بهبود به معنی کاهش هزینه است. از تعریف هزینه تقلیل یافته واضح است که متغیرهای درون حل بهینه، هزینه تقلیل یافته صفر دارند.
تعبیر دیگری از هزینه تقلیل یافته، است که تابع هدف با غیر صفر شدن یکی از متغیرهای که در حل بهینه مقدار صفر را اختیار کرده است. افت می کند. برای مثال اگر هزینه تقلیل یافته متغیر x، که در حل بهینه مقدار صفر را اختیار کرده است، ۲ دلار بر هر گالن باشد، بدین معناست که چنانچه سود آوری هر واحد متغیر x، ۲ دلار افزایش یابد. با ورود ۱ واحد از ان به حل بهینه (اگر ۱ واحد یک متغیر کوچک باشد.) سود کلی تغییری نمی کند. واضح است که اگر x بدون تغییر در سهم سود خود (ضریب x در تابع هدف) تا یک واحد افزایش یابد، مقدار تابع هدف ۲ دلار کاهش می یابد.
۱ . ۶ . ۲ ) قیمت های مزدوج:
متناظر با هر محدودیت، کمیتی وجود دارد که آن را با نام قیمت مزدوج با قیمت دو گان می شناسیم. اگر واحدهای تابع هدف بر حسب دلار و واحد محدودیتها بر حسب کیلو گرم باشند، آنگاه واحدهای هزینه تقلیل یافته برابر با دلار بر کیلو گرم خواهد بود. قیمت دو گان یک محدودیت، نرخ بهبود تابع هدف به ازای تغییر کوچکی در مقدار سمت راست آن محدودیت است.
برنامه های مختلف بهینه سازی ممکن است از علائم متفاوتی در ارتباط با قیمت های مزدوج استفاده کنند. برای LINGO منظور از یک قیمت مزدوج مثبت بهبودی است که با افزایش مقدار سمت راست محدودیت در تابع هدف حاصل می شود. از سوی دیگر قیمت مزدوج منفی به معنی افت تابع هدف در صورت افزایش مقدار سمت راست محدودیت است. قیمت مزدوج صفر نیز به معنی این است که تغییر مقدار سمت راست محدودیت، هیچ تاثیری در مقدار حل ندارد.
با توجه به این قرار داد، محدودیت های کوچکتری مساوی ( ) قیمت های دو گان نا منفی و محدودیت های بزرگتر مساوی ( ) قیمت های دو گان نا مثبت خواهند داشت. محدودیتهایی که به صورت تساوی ارضا می شوند نیز می توانند هر نوع قیمت مزدوجی داشته باشند چرا؟
بهتر است  در اینجا مفهوم قیمت های مزدوج را درک کنیم تا بتوانیم آنها را در حل مسئله Enginola تجزیه و تحلیل کنیم. قیمت مزدوج محدودیت   برابر با ۵ دلار به ازای هر واحد است. در وهله اول ممکن است شک کنید که این مقدار باید ۲۰ دلار هر واحد باشد. چرا که اگر یک دستگاه بیشتر تولید شود، سهم سود این یک واحد اضافه ۲۰ دلار خواهد بود. اما باید توجه داشت که برای تولید یک دستگاه Astro بیشتر، لازم است که سایر محدودیتها ارضا شوند

عتیقه زیرخاکی گنج