مقاله در مورد بهینه سازی و توابع دامنه متغیر در LINGO

بخشی از مقاله

بهينه سازي و توابع دامنه متغير در LINGO

واننده دور اندیش ممکن است چند پله بالاتر را در نظر بگیرد. هنگامی که ما سود مورد انتظار خود را افزایش می دهیم، خط چین نشان دهنده نقاط هم سود، بصورت موازی به سمت بالا انتقال پیدا می کند. این انتقال تا دورترین نقطه ممکنی است که بهترین سود را در یک نقطه شدنی حاصل نماید. این آخرین و بهترین نقطه، 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 )، در ادامه توضیح داده می شود: قسمت red

uct 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 واحد کاهش خواهد داد.
1 . 9 ) حل بهینه چند گانه و حالت تبهگنی:
بریا یک فرمولاسیون که حل بهینه محدودی داشته باشد، فقط یک مقدار بهینه برای تابع هدف وجود خواهد داشت. هر چند ممکن است مسالی وجود داشته باشند که در آنها ترکیبات مخ

تلفی از متغیرهای تصمیم و مقادیر قیمت های مزدوج متناظر آنها می توانند منجر به حل بهینه شوند. این گونه حل های به نام حلهای «تبهگن» نامیده می شوند. برای مثال در مسئله Enginoal، در نظر بگیرند سهم سود A به جای 20 دلار 15 دلار باشد. این مسئله و حل آن بدین قرارند:
MAX=15*A+30*C;
A<=60;
C<=50;
A+2*C<=120;
Optimal Solution found at step 1
Objective value: 1800.000
Variable Value Reduced Cost
A 20.00000 0.0000000
C 50.00000 0.0000000
Row Slack or surplus Dual price
1 1800.000 1.00000
2 40.00000 0.0000000
3 0.0000000 0.0000000
4 -30.000000 15.00000
منطقه شدنی و همچنین خط هم سود .
توجه کنید که خطوط و موازی اند. واضح است که کلیه نقاط بر روی خط نقاط بهینه اند.
اگر به طور خاص دقت کنید، برای محدودیت در سطر 3 گزارش حل، هر دو مقدار dual price , slack برابر با صفر است. این مطلب بیانگر این است که با کاهش کوچکی در تولید Cosmo، تغییری در سود کل حاصل نخواهد شد. البته باید یک افزایش متعادل کننده در تولید وجود داشته باشد. نتیجه گیریم که باید حل بهینه معادلی که در آن تعداد بیشتری Astro در مقابل تعداد کمتری Cosmo تولید می شود، وجود داشته باشد.می توانیم این حل را با افزایش سود آوری به Astro به میزان اندکی، کشف کنیم.

MAX=15.0001*A+30*C;
A<=60;
C<=50;
A+2*C<=120;
Optimal solution found at step 1
Objective value: 1800.006
Variable Value Reduced cost
A 60.00000 0.0000000
C 30.00000 0.0000000
Row Slack or surplus Dual Price

1 1800.006 1.00000
2 0.0000000 0.10000000E-03
3 20.00000 0.0000000
4 0.0000000 15.00000
همانطور که پیش بینی شد، سود کل همچنان 1800 دلار است. هر چند تولید Cosmo از 50 واحد به 30 واحد کاهش و تولید Astro از 20 واحد به 60 واحد افزایش یافت.
1 . 9 . 1 ) شرایط «چشم های مار»:

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

اگر بهینه هی متناوب داشته باشیم، ممکن است آنچه که در کامپیوتر شما نشان داده می شود با آنچه که ما در اینجا نوشته ایم متفاوت باشد. هر چند باید همیشه مقدار تابع هدف یکسانی بدست آورید.
در حقیقت از دو راه، حل بهینه چند گانه اتفاق می افتد. برای مثال ، دو گزارش حل بهینه فقط در مقادیر متغیرهای تصمیم (C, A) و متغیرهای کمبود یا Slack تفاوت دارند. حالتهایی نیز وجود دارند که در آن حلهای بهینه چند گانه، فقط در مقادیر قیمت های مزدوج اختلاف دارند. این شکل از مسئله Enginola را در نظر بگیرند که در آن ظرفیت خط تولید Cosmo به 30 واحد کاهش یافته است. فرمولاسیون مدل بدین صورت است:
MAX=20*A+30*C;
A<60;

Equivalent;are<=and < that! Note
!in LINGO
C<30;
A+2*C<120;
حل بهینه عبارت است از:
Optimal solution found at step 0

Variable Value ReducedCost
A 60.00000 0.0000000
C 30.00000 0.0000000
Row slack or Surplus Dual Price

1 2100.006 1.00000
2 0.000000 20.00000
3 0.000000 30.00000
4 0.000000 0.000000
مجدداً «چشم های مار»را در حل در نظر بگیرند (مثلاً جفت صفر، در یک سطر از گزارش حل.) این حالت نشان می دهد که ظرفیت خط تولید Cosmo (مقدار سمت راست یا RHS برای سطر سوم) می تواند بدون تغییر مقدار هدف، تغیر یابد. هر دو محدودیت یک نقطه را مشخص می کنند.
در حقیقت محدودیت به صورت ریاضی زائد است. پر واضح است که وقتی ، آنگاه خواهد بود. پس حذف آن تغییری دو مقدار هدف و منطقه شدنی ایجاد نمی کند و می توانیم آن را از آنها برداریم.
اگر مقدار سمت راست یا RHS سطر سوم را اندکی کاهش د

هید، در اصل حل زیر را خواهید داشت.
Optimal solution found at step 0

Variablr Value Reduced cost
A 60.00000 0.0000000
C 30.00000 0.0000000
Row Slack or Surplus Dual Price
1 2100.006 1.00000

2 0.0000000 5.00000
3 0.0000000 0.0000000
4 0.0000000 15.00000
توجه کنید که این حل، فقط دو مقادیر دو گان با حل قبلی تفاوت دارد. اکنون می توانیم این قانون را بیان کنیم که؛ اگر گزارش حل شامل ویژگی «چشم های مار» باشد (یعنی یک زوج صفر در یکی از سطرخای گزارش )، آنگاه ممکن است حل بهینه ای وجود داشته باشد که با این حال فقط در مقادیر متغیرهای اولیه (تصمیم) و متغیرهای دو گان و با هر دو اختلاف داشته باشند.
اگر همه محدودیتها بصورت نا مساوی باشند، آنگاه «چشم های مار» در واقع دلالت بر این مطلب دارند که یک حل متناوب وجود دارد. اما اگر یک یا چند محدودیت بصورت مساوی باشند، «چشم های مار» هیچ گونه تضمینی بر وجود یک حل متناوب نمی کنند. مثالی که در اینجا آورده ایم این مطلب را نشان می دهد :

]
MAX = 20*A
A < = 60
C = 30
تنها حل ممکن این است :
Optimal solution found at step 0
Objective value 1200.000
Variable Value Reduced Cost
A 60.00000 0.0000000
C 30.00000 0.0000000
Row Slack or Surplus Dual price
1 1200.000 1.000000
2 0.0000000 20.00000
3 0.0000000 0.0000000

اگر گزارش حل ترکیب «چشم های مار» را نشان می دهد، سئوالی که به ذهن می رسد این است : آیا می توانیم فقط از گزارش حل، برای تعیین اینکه حل بهینه متناوب ناشی از متغیرهای اولیه است یا متغیرهای دو گان استفاده کنیم؟ پاسخ این سئوال، چنانکه در این دو مسئله مرتبط با یکدیگر می بینید «خیر» می باشد :
هر دو مسئله شامل حلهای بهینه چند گانه هستند. آنچه که با روشهای حل استاندارد سیمپلکس مشخص می شود، بدین صورت است :

توجه داشته باشید که :

Solution 1 برای هر دو مسئله دقیقاً یکسان است.
مسئله D حل بهینه چند گانه را فقط در متغیرهای دو گان دارد.
مسئله P حل بهینه چند گانه را فقط در متغیرهای اولیه دارد.
بنابراین نمی توان از روی گزارش حل به تنهایی نوع حل بهینه متناوب را تعیین کرد. می توانید Solution 1 را فقط با تغییر اندکی در مقدار سمت راست سطر 3 و ضریب X در تابع هدف به میزان بیشتر از (مثلاً 001 .1) ایجاد کنید. به طریق مشابهی، Solution 2 را نیز می توانید با اندکی کاهش در مقدار سمت راست سطر 3 یا ضریب X در تابع هدف (مثلاً 0.9999) ایجاد کنید.
بعضی از نویسندگان به حل بهینه چند گانه ای که ناشی از متغیرهای اولیه باشد تبهگن دو گان ، و به حل بهینه چند گانه ای که ناشی از متغیرهای دوگان باشد، تبهگن اولیه گویند. نویسندگان دیگر، بهینگی چند گانه را فقط در حالتی که حل های بهینه چند گانه برای متغیرهای اولیه وجود دارد، ممکن می دانند.
1 – 9 – 2 ) تبهگنی و متغیرهای زائد :
در مسائل کوچک، تبهگنی معمولاً بدین معنی است که محدودیتهای زائدی وجود دارند. هر چند به طور کلی، مخصوصاً در مسائل بزرگ، تبهگنی دلالت بر وجود محدودیتهای زائد ندارد. مجموعه محدودیتهای زیر و متناظر با آن، این موضوع را بهتر نشان می دهد :
2x – y <1
2x – z <1

2y – x <1
2y – z <1
2z – x <1
2z – y <1
این محدودیتها، مخروطی را با یک قله یا نقطه x= y=z = 1 ایجا

د می کنند که 6 سر دارد. نقطه x= y=z = 1 تبهگن شده است، چرا که بیش از سه محدودیت از آن عبور کرده اند. با این وجود هیچ یک از محدودیتها زائد نیستند. در نظر داشته باشد که نقطه x = 0.6 , y = 0.2 , z = 0.5 اولین محدودیت را نقض می کند، اما سایر محدودیتها را ارضا می کند. از این رو اولین محدودیت زائد نیست. با امتحان تمام ترکیبات ممکن 0.6 , 0 , 0.5 می توانید تصدیق کنید که هیچ یک از این 6 محدودیت زائد نمی باشند.

1 – 10 ) مدلهای غیر خطی و بهینه سازی عمومی :
در طول این متن، تاکید بر روی فرموله سازی برنامه های خطی است. همواره سعی بر آن است که از مدلهای غیر خطی تا آنجا که ممکن است اجتناب شود. دو دلیل برای این کار وجود دارد :
1 ) حل این مدلها خیلی طولانی تر است.
2 ) به مجرد اینکه حل شدند، حل کننده های سنتی فقط می توانند تضمین کنند که شما یک حل بهینه موضعی دارید. یک حل زمانی موضعی است که حل بهتر دیگری در مجاورت آن موجود نباشد؛ هر چند حل خیلی بهتری در فاصله ای دورتر از آن داشته باشیم. حل کننده های غیر خطی سنتی شبیه به یک کوهنورد نزدیک بین هستند و می توانند به بالای نزدیکترین قله برسند اما شاید نتوانند بلند ترین قله رشته کوه را دیده و شما را بدان برسانند. نسخه های LINGO از 8 به بالا، گزینه Global Solver را دارا می باشند. اگر این گزینه را فعال کنید، آنگاه این تضمین وجود خواهد داشت که در صورت اجرای حل مدل به مدت کافی، حل کننده به حل بهینه عمومی دست یابد. فرض کنید مسئله ما از این قرار است :
Min = @ sin (x)+5* @ abs (x – 9.5) x < = 12

اگر حل کننده غیر خطی سنتی را در این مدل به کار گیرید، ممکن است یکی از سه جواب زیر را داشته باشید : x = 0 یا x= 5.23598 یا x = 10.47197 . اگر گزینه Global Solver را در LNGO بررسی کنید، حل x = 10.47197 را گزارش خواهد داد و آن را به عنوان بهینه عمومی معرفی می نماید. حل کننده های عمومی ممکن است زمان زیادی را صرف حل برای رسیدن به بهینگی تضمین شده نمایند. با این حال، حل کننده عمومی ممکن است جواب خیلی خوب و حتی بهینه ای را خیلی سریعتر بدهد اما زمان زیادی را صرف اثبات این کند که هیچ حل بهتری وجود ندارد.
توابع دامنه متغیر در LINGO
- مقدمه
- متغیرهای صحیح
فصل چهارم
4 – 1 ) مقدمه :
کلیه متغیرها در LINGO ، از نوع نا منفی پیوسته هستند، مگر اینکه خلاف آن قید شود. به طور کلی متغیرها می توانند هر مقداری از صفر تا مثبت بی نهایت را بپذیرند. ممکن است با موارد متعددی مواجه شوید که این دامنه پیش فرض، برای یک یا تعدادی از متغیرها مناسب نباشد. به عنوان مثال فرض کنید متغیرهایی وجود داشته باشند که بخواهیم مقادیر منفی اختیار کنند یا این

که ماهیت منفی داشته باشند؛ یا اینکه بخواهید متغیر فقط مقادیر صحیح را اختیار کند. برای دستیابی به این مهم، LINGO چهار تابع دامنه متغیر را برای اعمال این شرایط بر روی متغیرها در اختیار شما قرار می دهد تا بتوانید دامنه پیش فرض متغیر را تغییر داده، دامنه دلخواهتان را بر روی آن اعمال کنید. در ذیل، نام این توابع به همراه شرح مختصری از کارکردشان را ملاحظه می کنید :
متغیر را محدود به پذیرش یک مقدار صحیح می کند . @ GIN
متغیر را از نوع باینری (0 یا 1) قرار می دهد. @ BIN
به متغیر اجازه پذیرش هر مقدار حقیقی اعم از مثبت یا منفی یا صفر را می دهد. @FREE
در ادامه این فصل، روش استفاده از این توابع را آموخته، مثالهایی

از کاربرد آنها را خواهید دید.
4 – 2 ) متغیرهای صحیح :
LINGO به کاربر، امکان تعریف دو نوع متغیر صحیح را می دهد :
1 ) متغیر صحیح عمومی
2 ) متغیر صحیح صفر و یک
متغیرهای صحیح عمومی لازم است اعداد کاملی باشند (بدون رقم اعشار). متغیر صحیح ص

فر و یک نیز می بایست صفر یا یک باشد. هر مدلی که حداقل یک متغیر صحیح داشته باشد، به عنوان مدل برنامه ریزی (IP) شناخته می شود.
در بسیاری از پروژه های مدلسازی، با تصمیم گیری های بله یا خیر روبرو خواهید شد. یعنی از بین دو راهکار ممکن، فقط یکی قابل اجرا خواهد بود و با اجرای یکی، دیگری نشدنی خواهد شد. مثال هایی از این گونه تصمیم گیری ها، در دنیای واقعی پیرامون ما عبارتند از :
تولید یا عدم تولید، احداث کارخانه یا عدم احداث آن، تامین مشتری I از کارخانه J یا عدم تامین مشتری I از کارخانه J، متحمل هزینه ثابت شدن و یا عدم تحمل آن.
استفاده از متغیرهای باینری، روش استاندارد مورد استفاده در مدل کردن تصمیمات بله یا خیر است. استفاده از متغیرهای صحیح عمومی، هنگامی که ممکن است جوابهای صحیح حل مدل گیج کننده و یا مشکل ساز باشند، مفید خواهد بود. برای مثال در ابتدا فرض کنید مدلی دارید که جواب 5/5121787 مداد شمعی آبی را در کارخانه مداد شمعی سازی به دست می دهد. اینکه شما این جواب را به 5121787 قطع یا به 5121788 گرد کنید، چندان تفاوتی نمی کند. اما حال بیایید در سطحی بالاتر و حساس تر، فرض کنیم که مدل برنامه ریزی شده شما برای سازمان فضایی آمریکا (نا سا) جواب بهینه ساخت 5/1 ایستگاه فضایی را به دست می دهد.
از آنجا که ساخت 2/1 ایستگاه بی معنی و غیر ممکن است، می بایست کاملاً دقت کنید که چگونه نتایج را گرد یا قطع کنید؛ چرا که وقتی در نهایت با اعداد کاملی سرو کار داشته باشیم و گرد یا قطع کردن جوابها اختلاف قابل توجهی ایجاد می کند، اهمیت کاربرد متغیرهای صحیح عمومی بیشتر آشکار خواهد شد.
اینگونه نیست که LINGO بدون حساب و کتاب و به راحتی، اعداد اعشاری را برای رسیدن به جوابهای صحیح قطع یا گرد کند. گرد کردن جواب، به طور معمول ممکن است منجر به حل زیر بهینه یا نشدنی شود. جهت شفاف شدن مطلب، مدل ساده زیر را در نظر بگیرید :

MAX = X
X + Y = 25.5
X < Y
با امتحان این مدل، تنها حل ممکن X = Y = 12.75 خواهد بود. حال فرض کنید بخواهیم حل بهینه ای را که در آن X عدد صحیح باشد بیابیم. گرد کردن X به 13، به راحتی حل را نشدنی

خواهد کرد؛ چرا که به ازای آن هیچ مقداری برای متغیر Y یافت نخواهد شد تا هر دو محدودیت را در آن واحد ارضا کند. به وضوح مشخص است که حل بهینه X = 12 و Y = 13 تنها حل ممکن خواهد بود. متاسفانه گرد کردن جواب بهینه در مدلهای بزرگ با متغیرهای صحیح زیاد، در عمل غیر ممکن است.
برای اینگونه مشکلات که در بالا شرح آن داده شد، LINGO الگوریتم پیچیده ای به نام الگوریتم انشعاب و تحدید (Branch and Bound) را ارائه می کند که به طور ضمنی، کلیه ترکیبهای متغیرهای صحیح را، برای تعیین بهترین جواب شدنی مدل IP می شمارد. از آنجا که با استفاده از این الگوریتم، حجم محاسبات و به تبع آن زمان لازم برای انجام محاسبات افزایش خواهد یافت، توصیه می شود که مسئله تان را طوری فرموله کنید که حتی الامکان نیازی به استفاده از متغیرهای صحیح نباشد. اگر چه استفاده از متغیرهای صحیح، به حجم و زمان محاسبات به صورت تصاعدی می افزاید، اما اغلب منطقی است که از LINGO حلهای عدد صحیح را بخواهیم؛ چرا که معمولاً اعداد کسری، بی ارزش یا غیر قابل استفاده خواهند بود.
4 – 2 – 1 ) متغیرهای صحیح عمومی
LINGO به صورت پیش فرض، کلیه متغیرهای مدل را از نوع پیوسته در نظر می گیرد. موارد زیادی پیش خواهد آمد که استفاده از مقادیر کسری نا مطلوب یا غیر ممکن باشد. مثلاً شما نمی توانید 3/2 نفر را استخدام و یا نمی توانید نیمی از یک ماشین را بفروشید. در اینگونه موارد برای حل این مشکلات، از تابع دامنه متغیر عدد صحیح عمومی که با نام @ GIN شناخته می شود، استفاده خواهید کرد. ساختار این تابع، به صورت زیر است : @ GIN (variable - name)
که در آن variable – name نام متغیری خواهد بود که می خواهید از نوع عدد صحیح عمومی باشد. تابع @ GIN را می توان در هر جای مدل که محدودیتی را وارد می کنید، استفاده کرد. این تابع را می توان در دل عبارت @ FOR تعبیه کرد که با این کار به راحتی می توان کلیه متغیرهای یک مشخصه یا خصوصیت (Attribute) را مشمول استفاده از این تابع قرار داد. مثال هایی

از کاربرد این تابع عبارتند از :
@ GIN (X)
متغیر صحیح X را، از نوع عدد صحیح عمومی قرار می دهد.
@GIN (PPODUCE(5))
متغیر (PPODUCE(5) را، از نوع عدد صحیح عمومی قرار می دهد.
@ FOR (DAYS(I) : @GIN (START(I)))
کلیه ی متغیرهای خصوصیت START را در مجموعه DAYS ، از نوع عدد صحیح عموم

ی قرار می دهد.
مثالی از کاربرد متغیرهای صحیح عمومی :
برای نشان دادن کاربرد تابع @GIN در یک مدل کامل، تغییری را در مدل شرکت Comp Quick که در فصل 2 حل شده ایجاد کردیم. فرض کنید Comp Quickموفق می شود با ایجاد اصلاحاتی در خط مونتاژ کامپیوتر نوع STANDARD ، سه کامپیوتر بیشتر از قبل تولید کند و ظرفیت تولید این خط را به 103 کامپیوتر در روز برساند. در نتیجه، فرم اصلاح شده این محدودیت بدین صورت در خواهد آمد : 103 > STANDARD
با اعمال این محدودیت در مدل Comp Quick، مدل نهایی بدین صورت خواهد بود :
Here is the total profit objective function
100 * STANDARD + 150 * TURBO = MAX
Constraints on the production line capacity
؛ STANDARD < = 103
؛ TURBO < = 120
Our labor supply is limited
STANDARD + 2* TURBO< = 160
در این حالت گزارش حل زیر را خواهیم داشت :
Global optimal solution found
Objective value 14575.00

Total solver iterations : 0
Variable Value Reduced Cost
STANDARD 103.0000 0.0000000
TURBO 28.50000 0.0000000
توجه کنید که مقدار بهینه جدید برای کامپیوتر های نوع TURBO برابر با 5/28 خواهد بود که دیگر عدد صحیح نیست. Comp Quick می بایست تعداد صحیحی در هر روز تولید کند؛ پس برای تضمین این امر، عبارت @GIN را برای تبدیل نوع متغیرهای STANDARD و TURBO به متغیرهای صحیح عمومی، به مدل اضافه می کنیم. مدل اصلاح شد

Here is the total profit objective function
MAX = 100 * STANDARD + 150 * TURBO
؛ Constraints on the production line capacity !
STANDARD < = 103
TURBO < = 120
Our labor supply is limited !
TURBO < = 160 + 2 * STANDARD
Only values Integer
@GIN (STANDARD)
@GIN (TURBO)
حل این مدل اصلاح شده، جوابهای عدد صحیحی را می دهد که انتظارش را داشتیم :
Global optimal solution found at step : 4
Objective value 14550.00
Total solver iterations : 1
Variable Value Re duced Cost
STANDARD 102.0000 - 100.0000
TURBO 29.00000 – 150.0000

توجه داشته باشید که ما اکنون آماری جدیدی به نام Extended Solver Status داریم. برای مدل هایی با متغیرهای صحیح همچون این مدل، آماره مذکور برابر با شمارش تعداد دفعاتی است که متغیرهای صحیح مجبورند مقادیر عدد صحیح را، در خلال روال حل انشعاب و تجدید اختیار کنند.
به طور کلی این مقدار چندان به کارتان نمی آید؛ جز اینکه این مفهوم را به شما نشان دهد که LINGO با چه مشقتی در حال یافتن جواب صحیح است. هر چه تعداد مراحل بیشتر باشد، LINGO کار دشوارتری را برای یافتن جوابهای صحیح مناسب برای مدل شما، پیش رو خواهد داشت.
برنامه ریزی کارکنان، مثالی دیگر از کاربردهای عدد صحیح عمومی :
مسئله برنامه ریزی کارکنان (Staff Scheduling) را از فصل 3، در قسمت استفاده از مجموع

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

ای صحیح در مدل استفاده نکردیم. در این مسئله، به طور تصادفی و علی رغم عدم استفاده از متغیرهای صحیح، جواب ما دقیقاً عدد صحیح شد. بیایید بار دیگر مروری بر این مدل داشته باشیم تا این مطلب را مشاهده کنیم :
در مدل اصلی استخدام کارکنان، به ترتیب به این تعداد کارگر، در ابتدای هر روز هفته نیاز داریم (از شنبه تا جمعه) : 12، 14، 20، 16، 13، 16، 19. حال بیایید تعداد کارگر مورد نیاز در سه – شنبه را از 16 به 12 و در چهارشنبه از 13 به 18 تغییر دهیم. این تغییر را در مدل اعمال می کنیم :
MODEL:
SETS :
DAYS : REQUIRED , START
ENDSETS
DAYS :
DAYS = MON TUE WED THU FRI SAT SUN
REQUIRED = 20 12 18 16 19 14 12
ENDSETS
MIN = @ SUM (DAYS (I): START (I))
@FOR (DAYS(J):
@ SUM (DAYS(I)| I # LE # 5 :
START (@ WRAP(J – I + 1 , 7)))
> = REQUIRED (J))

END
بعد از ایجاد این تغییر کوچک و حل دوباره مدل، دیگر جواب عدد صحیح نخواهیم داشت. در واقع همانطور که اکنون مشاهده می کنید، متغیرهای START اعشاری هستند :
Global optimal solution found :
Objective value 23.66667
Total solver iterations : 0
Variable Value Re duced Cost

START (MON) 9.666667 0.000000
START (TUE) 2.000000 0.000000
START (WED) 1.666667 0.000000
START (THU) 5.66666 0.000000
START (FRI) 0.000000 0.000000
START (SAT) 4 . 666667 0.000000
START (SUN) 0.000000 0.3333333
در این مدل خاص، می توانیم جوابها را گرد کنیم و همچنان حل شدنی داشته باشیم. اگر چه در اکثر مدلها نمی توان تا این حد خوش شانس بود؛ چرا که گرد یا قطع کردن جوابهای پیوسته، می تواند به حل نشدنی منجر شود. ممکن است تعدادی کارگر اضافی در یک روز داشته باشیم اما با گرد کردن این تعداد، در هیچ روزی تعداد کارگر مورد نیاز تامین نشود. گرد کردن جوابهای پیوسته، مقدار هدف 25 = 5+6+2+2+10 کارگر را خواهد داد.
حال بیایید برنامه ریزی عدد صحیح را، برای مدل تجدید نظر شده کارکنان اعمال کنیم. ابتدا نیاز به استفاده از تابع @ GIN خواهیم داشت تا کلیه متغیرهای START را، از نوع عدد صحیح عمومی قرار دهیم. این کار را می توانیم با افزودن عبارات زیر به مدلمان انجام دهیم :
@GIN(@START(MON)) @GIN(@START(FRI))

@GIN(@START(TUE)) @GIN(@START(SAT))
@GIN(@START(WED)) @GIN(@START(SUN))
@GIN(@START(THU))
اگر چه راه ساده تر این است که تابع @GIN را در دل تابع @FOR تعبیه کنیم. در نتیجه می توانیم فقط به کمک یک جمله، تابع @GIN را بر روی هر یک از اعضای START اعمال کنیم : @FOR (DAYS(I): @GIN(START(I))
مفهوم این عبارت چنین است :
برای هر روز هفته، متغیر متناظر با تعداد افرادی را که در آن روز شروع به کار می کنند، از نوع عدد صحیح عمومی قرار بده. بعد از افزودن عبارت @FOR در انتهای مدل و بهینه سازی مجدد، گزارش حل عدد صحیح خالص زیر را خواهیم داشت :
Global optimal solution found :
Objective value : 24.00000

Extended solver steps : 0
Total solver iterations : 6
Variable Value Re duced Cost
START (MON) 10.00000 1.000000
START (TUE) 2.000000 1.000000
START (WED) 1.000000 1.000000
START (THU) 6.000000 1.000000
START (FRI) 0.000000 1.000000
START (SAT) 5.000000 1.000000
START (SUN) 0.000000 1.000000
ملاحظه می کنید که حل بهینه 24، بر حل بهینه 25 که با گرد کردن به دست می آید ارجح تر است. بنابراین اگر از روش گرد کردن استفاده می کردیم، یک کارگر مازاد بر نیازمان استخدام کرده بودیم.
یک متغیر عدد صحیح صفر و یک، حالت خاصی از متغیر صحیح می باشد که لازم است صفر یا یک باشد. اینگونه متغیرها، معمولاً در تصمیم گیری های بله یا خیر مورد استفاده قرار می گیرند. ساختار تابع @BIN برای استفاده از این متغیرها اینگونه است: @BIN (variable - name)
که در آن variable – name نام متغیری است که می خواهید مقدار صفر و یک را اختیار کند. می توانید از این تابع، در هر جای مدل که محدودیتی را وارد می کنید، استفاده نمایید. می توان این تابع را در دل عبارت @FOR تعبیه کرد که به راحتی امکان صفر و یک کردن متغیر را برای اعمال آن بر روی همه یا گزیده ای از متغیرهای یک خصوصیت در اختیار شما قرار می دهد. مثالهایی از کاربرد تابع @BIN عبارتند از : @ BIN (X)
متغیر عدد صحیح X را از نوع باینری قرار می دهد.
@ BIN (INCLUDE(4))
متغیر (4) INCLUDE را از نوع باینری قرار می دهد.
@ FOR (ITEMS:@BIN(INCLUDE))

کلیه متغیرهای خصوصیت INCLUDE را، از نوع صفر و یک قرار می دهد.
مثالی از متغیرهای عدد صحیح صفر و یک (مسئله کوله پشتی)
مسئله کوله پشتی، مدل کلاسیکی است که از متغیرهای باینری استفاده می کند. در این مسئله (یا این دسته از مسائل) ، تعدادی آیتم دارید که می خواهید در کوله پشتی قرار دهید. متاسفانه ظرفیت کوله پشتی محدود بوده و حمل کلیه آیتم ها با هم غیر ممکن است. هر آیتم، ارزش یا مطلوبیت مشخصی برای قرار گرفتن در کوله پشتی دارد. مسئله عبارت است از یافتن زیر مجموعه ای از آیتم ها که باید برای بیشینه سازی ارزش کل بار حمل شده، در کوله پشتی قرار گیرند؛ با این شرط که مجموع بار آنها از ظرفیت بار کوله پشتی بیشتر نشود.
هر چند که استفاده از لفظ کوله پشتی در اینگونه مسائل، نباید باعث نادیده گرفتن اهمیت این دسته از مسائل شود، مسئله کوله پشتی می تواند در وضعیتهای مختلفی به کار رود. مثالهایی از اینگونه مسائل، بارگیری وسایل نقلیه، بودجه بندی کلان و برنامه ریزی استراتژیک هستند.
مسئله :
فرض کنید می خواهید برای یک پیک نیک برنامه ریزی کنید و لیست موادی که می خواهید با خود حمل کنید را تهیه کرده اید. هر آیتم وزن مشخصی دارد و کوله پشتی شما قادر به ذخیره باری بیش از 15 کیلوگرم نیست. همچنین یک لیست رتبه بندی برای این آیتم

ها تهیه کرده اید، که در آن به هر آیتم نمره ای از 1 تا 10 داده اید که مشخص می کند قرار گرفتن هر آیتم خاص در کوله پشتی، تا چه حد برای شما مطلوبیت دارد.
فرمولاسیون مدل :
در این مدل فقط یک مجموعه داریم و آن هم مجموعه آیتم هایی است که می خواهیم با کوله پشتی حمل کنیم. این مجموعه اصلی ماست و می توانیم آن را در Sets Section تعریف کنیم.
SETS :
ITEMS / ANT – REPEL, SODA, BLANKET ,
BRATWURST , BROWNIES, FRISBEE, SALAD,

WATERMELON / :
INCLUDE, WEIGHT, RATING
ENDSETS
می توانیم خصوصیتهای WEIGHT INCLUDE و RATNG را، به مجموعه ITEMS تخصیص دهیم. متغیرهای INCLUDE از نوع باینری هستند و برای تعیین وجود یا عدم وجود یک آیتم در کوله پشتی استفاده می شوند. از WEIGHT برای در بر گرفتن وزن هر آیتم و از RATNG برای رده بندی هر آیتم استفاده می کنیم.
در ادامه نیاز خواهیم داشت که data section را، برای ورود اطلاعات مربوط به وزنها و رده بندی ایجاد کنیم. این قسمت پس از ورود اطلاعات مذکور، بدین صورت در خواهد آمد :
DATA:
RATNG WEIGHT
2 1
9 3
3 4
8 3
10 3
6 1
4 5
10 10
؛15 = KNAPSACK – CAPACITY

ENDDATA
توجه داشته باشید که ظرفیت کوله پشتی را نیز در این قسمت وارد کردیم که می تواند تمرین خوبی برای جدا سازی داده ها از محدودیتهای مدل باشد.
بعد از اینکه همه مجموعه ها و داده ها را تعریف کردیم، نوبت به ساخت تابع هدف می رسد. می خواهیم جمع رتبه بندی های آیتم های حمل شده در کوله پشتی را به حداکثر برسانیم. توجه کنید که (I) INCLUDE برابر با 1 خواهد بود اگر و تنها اگر I در کوله پشتی قرار گیرد، در غیر این صورت صفر خواهد بود. بنابراین اگر INCLUDE را درخصوصیت RATING ضرب کنیم، از حاصل ضرب آن دو، تابع هدف مدل به دست می آید. بدیهی است که اگر INCLUDE صفر باشد، یعنی

کالای مذکور حمل نشده و طبیعتاً در حاصل جمع RATINGها هیچ تاثیری ندارد و اگر 1 باشد، RATING مربوط به آن در این حاصل جمع دخیل خواهد بود (از طریق جمله INCLUDE RATING *) . در نهایت جمله بیان کننده تابع هدف، بدین صورت خواهد بود :

MAX = @SUM(ITEMS : RATING * INCLUDE )
لازم به ذکر است که از متغیر اندیس دار در تابع @SUM استفاده نکردیم. از آنجا که همه خصوصیتهای تابع (RATING و INCLUDE ) روی مجموعه ITEMS تعریف شده اند، می توانیم از اندیس گذاری ضمنی استفاده کنیم.
قدم بعدی وارد کردن محدودیتهاست. در این مدل فقط یک محدودیت وجود دارد و آن هم محدودیت ظرفیت کوله پشتی است. به طریق مشابهی، همانگونه که برای هدف دیدید، وزن ترکیب بهینه بار کوله پشتی را، از مجموع حاصل ضربهای خصوصیتهای INCLUDE در خصوصیتهای WEIGHT برای هر یک از آیتم ها به دست می آوریم. این حاصل جمع، می بایست کوچکتر یا مساوی ظرفیت کوله پشتی باشد. با استفاده از دستورات LINGO، این محدودیت را به شکل زیر وارد می کنیم :
@SUM (ITEMS: WEIGHT *INCLUDE) <= KNAPSACK – CAPACITY
در نهایت می بایست کلیه متغیرهای INCLUDE را، از نوع باینری قرار دهیم. دو روش برای این منظور وجود دارد. روش اول کمی ابتدایی و پیش پا افتاده است؛ ولی روش دوم س

اده تر و سریع تر می باشد. در اینجا هر دو روش را نشان خواهیم داد.
روش اول :
@BIN(INCLUDE(@INDEX(ANT - REPEL)))
@BIN(INCLUDE(@INDEX(SODA)))
@BIN(INCLUDE(@INDEX(BLANKET)))
@BIN(INCLUDE(@INDEX(BRATWURST)))

@BIN(INCLUDE(@INDEX(BROWNIES)))
@BIN(INCLUDE(@INDEX(FRISBEE)))
@BIN(INCLUDE(@INDEX(SALAD)))
@BIN(INCLUDE(@INDEX(WATERMELON)))
دقت کنید که در این روش، تابع @ INDEX، به سادگی اندیس یک عضو از مجموعه اولیه را، به خود آن مجموعه بر می گرداند.
روش دوم :
تابع @BIN را در تابع @FOR تعبیه می کنیم تا فقط با نوشتن یک جمله، آن را برای همه خصوصیتهای INCLUDE اعضای مجموعه ITEMS اعمال کنیم.
@FOR (ITEMS: @BIN(INCLUDE))
حل LINGO :
کل مدل مسئله کوله پشتی و حل آن با نرم افزار LINGO، در اینجا آورده شده است. فایل این مسئله را می توانید در پوشه SAMPLES با نام KNAPSACK بیایید.
SETS :
ITEMS / ANT – REPEL, SODA, BLANKET,
BRATWURST, BROWNIES, FRISBEE, SALAD,
WATERMELON / :
INCLUDE, WEIGHT, RATING
ENDSETS
DATA:
RATNG WEIGHT
2 1

9 3
3 4
8 3
10 3

6 1
4 5
10 10
KNAPSACK – CAPACITY = 15
ENDDATA
MAX = @SUM(ITEMS: RATING * INCLUDE)
@SUM(ITEMS: WEIGHT * INCLUDE ) < =
KNAPSACK – CAPACITY
@ FOR(ITEMS: @BIN(INCLUDE))
گزارش حل :
Global optimal solution found
Objective value : 38.00000
Extended solver steps : 0
Total solver iterations : 0
Variable Value Reduced Cost
INCLUDE (ANT - REPEL) 1.000000 - 2. 000000
INCLUDE (BEER) 1.000000 - 9. 000000
INCLUDE (BLANKET) 1.000000 - 3. 000000
INCLUDE (BRATWURST) 1.000000 - 8. 000000
INCLUDE (BROWNIES) 1.000000 - 10. 000000
INCLUDE (FRISBEE) 1.000000 - 6. 000000
INCLUDE (SALAD) 0.000000 - 4. 000000
INCLUDE (WATERMELON) 0.000000 - 10. 000000
همانطور که می بینید، کوله کشتی کاملاً پر شده و از کل ظرفیت 15 کیلوبی آن استفاده کرده اید و به جز آیتم های SALAD و ، همه چیز با خود برداشته اید.
توسعه ای بر مدل کوله پشتی، مدلسازی منطقی یا شرطی:
متغیرهای باینری، برای مدلسازی منطقی یا شرطی بسیار مناسب هستند. برای مثال فرض کنید متخصص تغذیه به شما گوشزد می کند که برای حفظ سلامتی خود لازم است حداقل یکی از دو آیتم SALAD و را، جزء برنامه غذایی پیک نیک قرار دهید. می تو.انید به سادگی این شرط را، به کمک جمله زیر به مدل اضافه کنید:
INCLUDE(@ I NDEX(SALAD))+INCLUDE@I NDEX (WATER MELON)>=T;
برای ارضای این محدویت، می بایست حداقل یکی از دو آیتم SALAD یا WATERMELON در کوله پشتی قرار گیرند. متاسفانه محدودیتهایی به این فرم، این عیب را دارند که مستقل از داده نسیتند و یا به عبارت بهتر، استقلال داده ندارند. حال فرض کنید لیست آیتم های پیک نیک عوض شود. شاید لازم شود این محدودیت را (که در بالا آوردیم) به تبع این تغییرات اصلاح کنیم یک مدل درست فرموله شده، بهتر است به هیچ تغییری در محدودیتهایش، در نتیجه تغییر داده نیاز نداشته باشد.
مدل زیر، روش استقلال از داده را در این مسئله (با همان شر افزوده شده) نشان می دهد. موارد اضافه شده نسبت به مدل اولیه، به صورت bold نشان داده شده اند:
SETS:
ITEMS/ANT _ REPEL, SODA, BLANKET,
BRATWURT,BROWNIES, FRISBEE, SALAd,
INCLUDE, WEIGHT, RATING;
MUST_EAT_ONE (ITEMS)
/SALAD, WATERMELON/;
ENDSETS
DATA:
WEIGHT RATING
1 2
3 9
4 3
3 8
3 10
1 6
5 4
10 10;
KNAPSACK_CAPACITY=15
ENDDATA
MAX=@ SUM (ITEMS: RATING*INCLUDE);
@SUM (ITEMS:WEIGHT*INCLUDE)<=
@ FOR (ITEMS:@BIN(INCLUDE))

@ SUM (MUST_EAT_ONE(I))>=1;

مجموعه ای به نام MUST_EAT_ONE را از مجموعه اصلی استخراج کردیم و به عنوان لیستی ضمنی، برای در بر گرفتن آیتم هایی که باید حتماً حمل شوند استفاده کردیم. سپس در انتهای مدل، محدودیتی را که وجود حداقل یکی از آیتم های «must eat» را در مدل الزامی می کند، اضافه کردیم.
برای مدل نشان داده شده در بالا، گزارش حل LINGO بدین صورت است:
Global optimal solution found

Objective value: 37.0000
Extended Solver steps: 0
Total solver iterations: 0
Variable Value Re duced costs
INCLUDE (ANT_REPEL)0.000000 -2.000000
INCLUDE (BEER) 1.000000 -9.000000
INCLUDE (BLANKET) 0.000000 -3.000000
INCLUDE (BRATWURST) 1.000000 -8.000000
INCLUDE (BROWNIES) 1.000000 -10.000000
InCLUDE (FRISBEE) 1.000000 -6.000000
INCLUDE (SALAD) 1.000000 -4.000000
INCLUDE (WATERMELON) 0.000000 -10.000000
همانطور که مشاهده می کیند، برای حمل سالاد (SALAD) مجبور شدیم از حمل ant repellent و blanket صرفنظر کنیم.
مثالی دیگر از متغیرهای باینری- ترکیب تولید با هزینه های ثابت:
موارد زیادی پیش خواهد آمد که برای فعالیت یا فعالیت های خاصی، منحمل هزینه های ثابت شویم.
مواردی همچون پرداخت هزینه ثابت در صورت احداث کارخانه، تولید یک محصول، پرداخت حق کمیسیون برای سفارش خرید سهام و یا تجهیز مجدد یک خط تولید، مثالهایی از این قبیل می باشند.
در ایم مثال، با هم مسئله تولید ترکیبی دیگری را که تقریباً مشابه مسئله CompuQuick است بررسی می کنیم. در این مثال، برای راه اندازی خط تولید هر یک از محصولات، هزینه ثابتی وجود دارد. به عبارت دیگر، حتی اگر تنها یکی از این محصولات را تولید کنیم، منحمل هزینه ثابتی مستقل از سطح تولید خواهیم شد. حال به بیان این مسئله می پردازیم.
فرض کنید مدیر یک کارخانه هواپیما سازی هستید و تصمیم گرفته اید به

ترین ترکیب تولید شش مدل محصول را پیدا کنید. شش مدلی که در حال حاضر زیر خط تولید هستند عبارتن از:
Biplane Jet, Comet, Streak, Meteor, Rocket هر هواپیما، سهم سود مشخصی دارد.
همچنین هزینه ثابتی برای تولید هر نوع از این هواپیما ها در هر دوره وجود دارد.
در تولید هر محصول، از شش ماده خام استفاده می شود.Plastic, Copper, Steel. Paint. Glassو Rubber اطلاعات مربوط به مقدار هر یک از این مواد خام نیاز برای تولید هر هواپیما، به همراه کل ظرفیت موجود آنها، فهرست شده است.

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

م، می توانیم این مجموعه ها را به شکل زیر بسازیم:
PLANES:
PROFIT, SETUP, QUANTITY, BUILD;
RESOURCES:AVAILABLE;
این چهار خصوصیت را، در مجموعه PLANES قرار دادیم:

سود مورد انتظار هواپیما را نشان می دهد. PROFIT