برنامه ریزی عدد صحیحدرس های رایگان

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

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

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

برای دانلود بسته طلایی آموزش کامل حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش شامل : جزوه کامل آموزش این درس، فایل ویدیوی آموزش این درس، فایل صوتی آموزش این درس، فایل ارایه حین درس مدرس بر روی دکمه زیر کلیک کنید.

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

حل برنامه ریزی عدد صحیح

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

حل برنامه ریزی عدد صحیح

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

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

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

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

روش حل صفحه برش

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

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

روش حل صفحه برش

حل:

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

روش حل صفحه برش

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

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

روش حل صفحه برش

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

روش حل صفحه برش

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

روش حل صفحه برش

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

روش حل صفحه برش

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

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

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

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

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

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

روش حل صفحه برش
فرض کنید:

روش حل صفحه برش

روش حل صفحه برش
در این صورت داریم:
روش حل صفحه برش

می‌توان xBi را به صورت زیر بازنویسی کرد:
روش حل صفحه برش

از آنجایی که xBi و رابطه زیر عدد صحیح است:
روش حل صفحه برش

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

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

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

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

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

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

روش حل صفحه برش
روش حل صفحه برش
روش حل صفحه برش
روش حل صفحه برش

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

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

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

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

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

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

روش حل صفحه برش

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

روش حل صفحه برش

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

روش حل صفحه برش

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

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

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

برش 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 را از پایه خارج می‌کند. اگر xk بخواهد متغیر ورودی به پایه باشد،

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

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

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

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

روش حل صفحه برش

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

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

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

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

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

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

روش حل صفحه برش

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

روش حل صفحه برش

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

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

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

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

روش حل صفحه برش

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

روش حل صفحه برش

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

روش حل صفحه برش

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

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

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

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

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

توجه: برای مطالعه ادامه این درس و دانلود سایر محصولات مربوط به این درس می توانید به موارد زیر مراجعه کنید.

برای دانلود بسته طلایی آموزش حل مسائل برنامه ریزی عدد صحیح به روش صفحه برش شامل : جزوه کامل آموزش این درس، فایل ویدیوی آموزش این درس، فایل صوتی آموزش این درس، فایل ارایه حین درس مدرس بر روی دکمه زیر کلیک کنید.

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

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

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

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

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

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

دکمه بازگشت به بالا