روش شاخه و کران برای حل مسائل عدد صحیح و عدد صحیح مختلط
برای مشاهده ویدیو روش برش کسری کلیک کنید
برای مشاهده ویدیو روش برش مختلط کلیک کنید
برای مشاهده ویدیو روش ترسیمی کلیک کنید
در روش شاخه و کران، همچون روش‌های برش ایده کلی بدین صورت می‌باشد که ابتدا باید مسئله LP آزاد شده مسئله برنامه‌ریزی عدد صحیح را حل کرد و سپس از روش شاخه و کران استفاده کرد. برخلاف برش‌های کسری و مختلط، در روش شاخه و کران مهم نیست که مسئله برنامه‌ریزی عدد صحیح محض یا مختلط باشد و می‌توان از روش شاخه و کران برای حل مسئله استفاده کرد و روش حل هیچ فرقی نمی‌کند.
مثال: مسئله زیر را با استفاده از روش شاخه و کران حل می‌کنیم و این روش را کامل روی آن توضیح خواهیم داد.
![\[\begin{array}{l} \max z = 7{x_1} + 9{x_2}\\ - {x_1} + 3{x_2} \le 6\\ 7{x_1} + {x_2} \le 35\\ {x_1},{x_2} \ge 0,{\mathop{\rm int}} \end{array}\]](https://optimamooz.com/wp-content/ql-cache/quicklatex.com-8e8a5238c0ae36c78013f700d4f440dc_l3.png "Rendered by QuickLaTeX.com")
ابتدا مسئله LP آزاد شده را حل می‌کنیم که جواب به صورت زیر می‌باشد:
با توجه به اینکه بایستی هر دو متغیر x1 و x2 عدد صحیح شوند و در حال حاضر به صورت کسری می‌باشند، یکی از این دو متغیر را انتخاب می‌کنیم تا برش اضافه نماییم. در این مثال ابتدا x1 را برای نوشتن برش انتخاب می‌کنیم.
واضح است که مقدار متغیر x1 برای اینکه عدد صحیح شود یا باید مقدار کمتر مساوی 4 و یا مقدار بزگتر مساوی 5 را اختیار نماید.
به عبارتی دو محدودیت
![\[{x_1} \le 4\]](https://optimamooz.com/wp-content/ql-cache/quicklatex.com-567ecd97d45bc26e6f048c9b98b3e4f8_l3.png "Rendered by QuickLaTeX.com")
یا
![\[{x_1} \ge 5\]](https://optimamooz.com/wp-content/ql-cache/quicklatex.com-430a5cfac386a762778c0710bcddcfba_l3.png "Rendered by QuickLaTeX.com")
را خواهیم داشت. یعنی شکل به صورت زیر خواهد شد:
اگر برش
را اضافه نماییم، فضای مسئله با هاشور سبز نشان داده شده است
همچنین اگر برش
را اضافه نماییم، فضای مسئله فقط نقطه (0و5) خواهد بود. چرا ؟؟؟
جواب‌های جدید با توجه به دو برش به صورت جداگانه به صورت زیر خواهند شد:
در شاخه سمت راست، تمام متغیرها عدد صحیح شده‌اند، پس می‌توانیم شاخه را ببندیم، اما هنوز شاید جواب نهایی ما نباشد و بتوانیم جواب‌های بهتری پیدا کنیم. چون شاخه سمت چپ مقدار تابع هدف 58 شده است و نسبت به شاخه سمت راست که 35 است بیشتر است، این امکان وجود دارد که با اضافه کردن برش به شاخه سمت چپ، مقدار متغیرها عدد صحیح شوند و جواب بهتری نسبت به شاخه بسته شده بالا داشته باشد (در مسئله حداکثرسازی یعنی مقدار بیشتر از 35).
نکته: اگر شاخه سمت چپ مقدار تابع هدف از 35 کمتر می‌شد، الگوریتم تمام بود و جواب بهینه بدست آمده بود، یعنی مقدار تابع هدف برابر 35 می‌شد و متغیرها نیز طبق شاخه سمت راست بالا مقدار داشتند.
اما چون این اتفاق نیافتاده است، باید شاخه سمت چپ را هنوز ادامه بدهیم.
در شاخه سمت چپ، مقدار متغیر x1 عدد صحیح شده است که نیاز به برش ندارد، اما متغیر x2 کسری است که باید برای آن برش بنویسیم.
به عبارتی دو محدودیت
![\[{x_2} \le 3\]](https://optimamooz.com/wp-content/ql-cache/quicklatex.com-b791c4d9ec800c8549ef4e41ded32ce7_l3.png "Rendered by QuickLaTeX.com")
و یا
![\[{x_2} \ge 4\]](https://optimamooz.com/wp-content/ql-cache/quicklatex.com-c3d6d8238cc40a32efd6787779a87513_l3.png "Rendered by QuickLaTeX.com")
را خواهیم داشت.
فضای جدید مسئله در شاخه سمت چپ به صورت زیر خواهد شد:
همانطور که مشخص است، اگر برش
را اضافه کنیم، مسئله نشدنی می‌شود، چرا ؟؟
اما با اضافه کردن برش دیگر فضای مسئله با هاشور قرمز نشان داده شده است.
همانطور که در شکل بالا مشخص است، با اضافه کردن محدودیت (برش)،
تمام متغیرها عدد صحیح شده‌اند
همچنین جواب بدست آمده از آن نسبت به شاخه سمت راست که قبلا بسته بودیم بهتر شده است، پس جواب نهایی مسئله (جواب بهینه) می‌باشد.
*(مرور) شرایط به انتها رسیدن شاخه در روش شاخه و کران:
1- شاخه نشدنی شود
2- جواب شاخه صحیح شود. از بین تمام جواب‌های صحیح بدست آمده بهترین جواب از نظر تابع هدف را انتخاب و مقدار تابع هدف آن را به عنوان کران در نظر می‌گیریم.
3- هر شاخه‌ای که مقدار تابع هدفش از کران عبور کند به انتها رسیده است. یعنی در ماکزیمم‌سازی مقدار تابع هدفش از کران کمتر و در می‌نیمم‌سازی مقدار تابع هدفش از کران بیشتر شود.
0
6