حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش

درس 13: حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش

تهیه شده توسط گروه بهینه یاب

 

تفاوت اصلی یک مسئله برنامه‌ریزی عدد صحیح و برنامه‌ریزی خطی در فرض صحیح بودن متغیرهای مسئله است. شاید در نگاه اول صحیح بودن متغیرها باعث می‌شود که تعداد جواب‌های امکان پذیر شمارا باشد که با کنترل تمامی آن‌ها می‌توان جواب بهینه را یافت. فرض کنید یک مدل دارای n متغیر دودویی (مقدار صفر یا یک می‌تواند اخذ نماید) باشد. اگر n=10 باشد، تعداد جواب‌های بیش از 1000 تا و اگر n=20 باشد، تعداد جواب‌ها، بیش از یک میلیون و اگر n=30 باشد، تعداد جواب‌ها بیشتر از یک میلیارد خواهد بود که حتی سریعترین کامپیوترها قادر به شمارش تمامی جواب‌ها نخواهند بود. حال اگر تعداد متغیرها از مقیاس میلیون باشند، دشوار به سرعت است بیشتر می‌شود.

پیچیدگی محاسبات یک مسئله برنامه ریزی عدد صحیح به دو عامل بستگی دارد:

1 – تعداد متغیرهای عدد صحیح

2 – ساختار مسئله

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

1- شاید جواب گرد شده دیگر موجه نباشد.

2- شاید جواب گره شده دیگر بهینه نباشد.

برای تشریح دو اشکال فوق، مثال زیر را در نظر بگیرید.

جواب بهینه مسئله فوق به صورت زیر می شود.

متغیری که غیر صحیح دارد یعنی x₂ را به عدد صحیح x₂=1 گرد می‌کنیم، جواب حاصل x₂=1 , x₁=1 و z=7 می‌شود که این جواب با جواب بهینه مدل اصلی، یعنی z=10، x₂=2,x₁=0 اختلاف زیادی دارد.

یکی از روش‌های متداول برای حل مسائل برنامه‌ریزی عدد صحیح، روش صفحه برش یا Cutting plane است که در ادامه معرفی می‌شود.

روش صفحه برش Cutting plane

برنامه‌ریزی خطی عدد صحیح زیر را در نظر بگیرید:

ایده روش صفحه برش اضافه کردن محدودیت‌های جدید به مسئله برنامه‌ریزی خطی مربوطه به منظور حذف نقاط بهینه غیر صحیح بدون حذف نقاط صحیح S از ناحیه امکان پذیر است یعنی آزاد کردن شرط صحیح بودن از S و در عین حال اضافه کردن محدودیت‌های جدید به فرم ̄āx=b به نحوی که نقاط S حذف شوند. یعنی مدل زیر را حل نمایید.

مثال: مدل زیر را در نظر بگیرید:

حل:

با اضافه کردن محدودیت x₁≤3 و x₁+x₂≤4 به مدل اصلی و حل مدل آزاد شده، به جواب مدل با متغیرهای عدد صحیح می‌رسیم. حل ترسیمی مدل فوق به صورت زیر می‌شود.

فرم عمومی یک برش یا cut

مدل خطی زیر را در نظر بگیرید:

فرض کنید که x_B یک جواب امکان پذیر پایه ( نه لزوما بهینه) باشد، یعنی:

و همچنین برای جواب‌های غیر پایه داریم: x_j=0 با ضرب 0≠h در رابطه (2) داریم:

چون x_j≥0 و a⌋ ≤ a⌋ و پس خواهیم داشت.

لذا خواهیم داشت:

از آن جاییکه سمت چپ رابطه بالا صحیح است، لذا رابطه فوق را می‌توان به صورت زیر هم نوشت:

از طرفی با ضرب رابطه (2) در ⌊h⌋ و با کم کردن از رابطه فوق داریم:

رابطه فوق اساس خیلی از برش ها است که بستگی به نحوه انتخاب h دارد.

برش های کسری یا Gomory

این برش‌ ها از حذف شرط صحیح بودن متغیرها بدست می‌آید. در این قسمت h=1 در نظر بگیرید. در این صورت رابطه (3) به صورت زیر می‌شود:

فرض کنید:

در این صورت داریم:

می‌توان x_Bi را به صورت زیر بازنویسی کرد:

از آنجایی که x_Bi و رابطه زیر عدد صحیح است:

بنابراین S_i هم صحیح خواهد بود.

نکته: خاصیت مهم رابطه (4) که اگر f_i0>0 باشد، با اضافه کردن برش (4)، جواب بهینه غیر صحیح مربوط از مدل آزادشده (حذف شرط صحیح بودن متغیرهای عدد صحیح) حذف می‌شود.

نکته: محدودیت شماره (4) را به راحتی می‌توان به جدول بهینه با متغیر پایه S اضافه کرد و با توجه به این که شرط بهینگی بدون تغییر می ماند، تنها شرط امکان پذیری برای محدودیت جدید نقض می‌شود که می‌توان از روش سیمپلکس همزاد آن را برطرف کرد.

نکته: برش (4) را نه تنها برای ضرایب محدودیت‌ها، بلکه برای ضرایب تابع هدف هم می‌توان نوشت.

نکته: بر مبنای اضافه کردن یک برش به فرم (4) و استفاده از روش سیمپلکس همزاد تا حصول یک جواب بهینه صحیح می‌توان الگوریتمی برای حل مدل برنامه‌ریزی خطی عدد صحیح ارایه داد. البته هیچ دلیلی بر متناهی بودن این الگوریتم وجود ندارد.

نکته: برای انتخاب سطری که توسط آن برش بدست می‌آید، روش‌های ابتکاری متفاوتی وجود دارد که می‌توان به موارد زیر اشاره کرد:

موارد (2) و (3) بر مبنای حذف بیشترین ناحیه غیر صحیح و مورد (4) بر مبنای بیشترین مقدار کاهش تابع هدف است.

نکته: هیچ دلیل بر برتری یکی از چهار روش بر روش دیگری نیست.

نکته: در استفاده از روش سیمپلکس همزاد نیازی به نگه داشتن تمامی برش‌ها نیست. برشی که متغیر پایه آن در پایه بوده و ضریب تمامی متغیرهای آن صفر باشد می‌توان از جدول سیمپلکس حذف شود.

نکته: به علت خطاهایی که در اثر گرد کردن پیش می‌آید، نمی‌توان از این روش در کامپیوتر برای مثال‌های واقعی استفاده کرد.

مثال: مدل برنامه‌ریزی عدد صحیح زیر را از روش برش‌های کسری حل نمایید.

حل: فرم گسترده مدل فوق به صورت زیر است:

ابتدا جدول سیمپلکس نهایی را بدست می‌آوریم:

برش‌های کسری براساس جدول نهایی سیمپلکس به صورت زیر است:

برش معادله 0 (تابع هدف):

برش معادله 1:

برش معادله 2:

حال اینکه کدام برش را اضافه کرد می‌توان از اصول 4 گانه ای که قبلا اشاره شده استفاده کرد. با فرض استفاده از اصل (1)، برش شماره 3 مورد استفاده قرار می‌گیرد.

با اضافه کردن برش فوق به جدول سیمپلکس، جواب بهینه به صورت زیر بدست می‌آید.

همان طور که مشاهده می‌شود با یک بار تکرار عملیات سیمپلکس همزاد به جواب بهینه رسیدیم.
با توجه به این که این مدل دارای 2 متغیر اصلی است می‌توان از روش ترسیمی هم حل کرد. برای حل ترسیمی باید تمامی برش‌ها را برحسب x₁ و x₂ در آورد.

برش 1 و 2:

برش 3:

حل ترسیمی مدل فوق به صورت زیر است:

با اضافه کردن برش‌ های فوق، جواب (0,5) جواب بهینه مسئله خواهد بود. همان طور که از شکل بالا پیدا است این برش‌ ها هیچ جواب عدد صحیح از مجموعه جواب‌های امکان پذیر را حذف نمی‌کنند و فقط جواب‌های غیر صحیح کم می‌شود.حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش حل مسائل برنامه ریزی عدد صحیح به روش

برش های کاملا صحیح همزاد (Dual-All-Integer cut)

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

1- حفظ بهینگی: برای این کار کافی است از روش سیمپلکس همزاد استفاده کنیم.

2- حفظ صحیح بودن: برای این کار کافی است که عملیات چرخش لولا را روی عناصر 1- انجام دهیم. برای این منظور می‌توان برش‌های خاصی در فرم عمومی ‌را استفاده کنیم.

فرض کنید یک پایه اولیه با داده‌های کاملا صحیح برای سیمپلکس همزاد در دست است که این جواب پایه شرایط بهینگی را داراست ولی امکان پذیر نیست( b<0 ). با انتخاب مناسب برای(h (0<h<1 از برش عمومی به فرم زیر، می‌توان برشی برای حذف این جواب امکان ناپذیر ایجاد کرد:

در انتخاب h باید به نحوی عمل کرد که عمل چرخش لولا روی 1- صورت گیرد. برای h بین صفر و یک برش (*) به صورت زیر می‌شود(0=⌊h⌋ ):

با اضافه کردن متغیر کمبود s داریم:

توجه کنید که اگر برای تمامی r داشته باشیم

جواب فعلی بهینه است. اگر یک r وجود داشته باشد که

بنابراین وقتی این برش با متغیر پایه s به جدول سیمپلکس اضافه می‌شود، روش سیمپلکس همزاد، s را از پایه خارج می‌کند. اگر x_k بخواهد متغیر ورودی به پایه باشد،

اولا باید (طبق روش سیمپلکس همزاد)

ثانیا برای حفظ شرط صحیح بودن جواب، h را باید به نحوی انتخاب کرد که داشته باشیم:

ثالثا، مقدار ̄c_j جدید پس از انجام چرخش لولا به صورت زیر است:

از آنجاییکه برای a_rj<0 و h>0، آنگاه داریم

بنابراین یک شرط لازم برای حفظ شرط بهینگی، عبارت است از:

اشاره شد که برای انتخاب h باید اولا شرط زیر برقرار باشد:

بنابراین:

از قبل داشتیم

ثانیا برای برقراری شرط بهینگی برای مقدار h داریم:

1- اگر ̄c_k برابر با صفر باشد، هر مقداری از h را می‌توان انتخاب کرد:

2- اگر ̄c_k بزرگتر از صفر باشد کافی است:

بنابراین h باید در محدوده زیر قرار بگیرید:حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش

نکته: توجه کنید که برای هر مقدار h*≥h شرایط بهینگی و صحیح بودن حفظ خواهد شد ولی بهتر است *h = h انتخاب شود تا تغییرات تابع هدف بیشتر شود.

نکته: برشی که در جدول سیمپلکس، متغیر مازاد آن در پایه با مقدار مثبت و مابقی متغیرها برابر صفر باشد را می‌توان از جدول سیمپلکس حذف کرد.

برش کاملا صحیح اولیه(Primal-All-Integer cut)

با استفاده از روش سیمپلکس به نحوه دیگر می‌توان مسائل برنامه‌ریزی خطی عدد صحیح را حل کرد. آن حفظ شرایط صحیح بودن و امکان پذیری اولیه و برقراری شرط بهینگی است. برای حفظ امکان پذیری، کافی است از روش سیمپلکس اولیه و تست نسبت استفاده کرد تا امکان پذیری پایه حفظ شود. برای حفظ صحیح بودن کافی است که عملیات چرخش لولا را روی ضریب +1 انجام داد. اگر شرط بهینگی در جدول سیمپلکس برقرار باشد( c_j≥0 ) مسئله حل شده است. فرض کنید c_k<0 باشد و x_k متغیر ورودی به پایه و x_r متغیر خروجی از پایه باشد که از تست زیر بدست می‌آید.حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش حل مسائل برنامه ریزی عدد

با وارد کردن x_k به جای x_r در پایه شرط امکان پذیری باقی خواهد ماند. حال اگر داشته باشیم:

آنگاه شرط صحیح بودن باقی خواهد ماند. بنابراین فرض کنید:

آنگاه خواهیم داشت:

و لذا برش عمومی به صورت زیر می‌شود:

با توجه به برش فوق می‌توان الگوریتم یافتن جواب بهینه صحیح را به صورت زیر بیان کرد:

با یک جواب امکان پذیر صحیح شروع می‌کنیم، اگر بهینه نبود یک برش برای حرکت به طرف جواب امکان پذیر صحیح دیگری با تابع هدف بهتر اضافه می‌کنیم. 

حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش