Метод гілок і меж – один з комбінаторних методів. На відміну від методу Гоморі застосовується як до повністю, так і частково цілочисельних задач. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками корисними для знаходження оптимального рішення.
Згідно загальній ідеї методу, на першому кроці поставлена задача розв’язується як задача лінійного програмування, тобто без урахування умови цілочисельності. Якщо отримано оптимальний цілочисловий розв’язок задачі лінійного програмування, то він є також розв’язком задачі цілочисельного лінійного програмування. Якщо ж не отримано цілочисельного розв’язку, то через позначають цілу частину змінної , значення якої в оптимальному розв’язку задачі лінійного програмування є дробовим. Після чого, інтервал виключається з розгляду, як такий, що не містить допустимих цілочисельних компонент розв’язку. Тому допустиме ціле значення повинно задовольняти одну з нерівностей або .
Дописавши кожну з цих умов до розв’язуваної задачі, дістанемо дві, не пов’язані між собою, задачі. У цьому випадку кажуть, що вихідна задача розбивається (розгалужується) на дві підзадачі. Потім кожна підзадача розв’язується як задача лінійного програмування. Якщо оптимальний розв’язок виявляється допустимим для цілочисельної задачі, то такий розв’язок слід зафіксувати як найкращий. При цьому немає необхідності продовжувати розгалуження підзадачі, оскільки покращити отриманий розв’язок, очевидно, не вдасться.
В іншому випадку підзадача в свою чергу повинна бути розбита на дві підзадачі знову при врахуванні умов (2)–(3). Зрозуміло, коли отримуємо допустимий цілочисловий розв’язок однієї з підзадач краще попереднього, то він фіксується замість зафіксованого раніше.
Процес розгалуження продовжується до тих пір, поки кожна підзадача не приведе до цілочислового розв’язку або доки не буде встановлена неможливість покращення зафіксованого розв’язку. У цьому випадку зафіксований допустимий розв’язок буде оптимальним.
Метод гілок та меж – приклад:
Для виготовлення товару A і В підприємство використовує два види сировини. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A та B, а також загальна кількість сировини наведені в наступній таблиці:
Необхідно скласти такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.
Нехай та – кількість комплектів товару типу А та В відповідно. Тоді економіко-математична модель даної задачі запишеться у наступному вигляді:
де та – цілі числаю. На першому кроці, як і для випадку з методом Гоморі, розв’яжемо дану задачу нехтуючи умовою цілочисельності. Для цього скористаємось симплекс методом, остання таблиця якого, для даної задачі, набуде наступного вигляду:
З даної таблиці бачимо, що для початкової задачі, з урахуванням умови цілочисельності змінних, отримане рішення не є оптимальним. Для пошуку цілочисельного оптимального рішення розділимо інтервал зміни змінної на дві області, а саме та , і розіб’ємо задану задачу на дві нові:
На першому кроці розв’яжемо, наприклад, задачу 3. Для цього, шляхом введення додаткових змінних, систему нерівностей приведемо до системи рівнянь (запишемо систему обмежень у канонічній формі), після чого перейдемо до побудови першого опорного плану:
Виходячи з того, що серед вільних членів системи обмежень задачі 3 існують такі, що приймають від’ємні значення, то для її розв’язку слід скористатись двоїстим симплекс методом. В результаті отримаємо таблицю, з допомогою якої бачимо, що дана задаче немає розв’язкуів (в рядку, з від’ємним значенням вільного члена усі елементи додатні):
Далі, переходимо до розв’язку задачі 2. Для цього, аналогічгим чином, запишемо систему обмежень у канонічній формі та побудуємо перший опорний план:
Після цього, скориставшись симплекс методом отримаємо:
Для отриманого оптимального плану задачі 2 умова цілочисельності також не виконується, тому дану задачу розбиваємо на дві нові. В результаті отримаємо:
Розв’язавши задачу 5 двоїстим симплекс методом, отримуємо перший цілочисельний розв’язок, тому фіксуємо його як найкращий і переходимо до задачі 4.
Для задачі 4, записавши систему обмежень у канонічній формі бачимо, що серед векторів міститься лише три одиничних. Тому в ліву частину останнього, четвертого, рівняння системи обмежень додаємо додаткову невід’ємну змінну , після чого переходимо до розгляду розширеної задачі:
для якої перший опорний план прийме наступного вигляду:
Розв’язавши дану задачу методом штучного базису, отримуємо новий цілочисельний розв’яок, який являється кращим за попередній, тому фіксуємо його замість зафіксованого раніше і таким чином, з допомогою двох розгалужень, знаходимо шуканий оптимальний розв’язок для заданої задачі цілочисельного програмування.