Метод гілок і меж онлайн

Інструкція. Вкажіть кількість змінних і число обмежень. Отримане рішення зберігається в форматі MS Word з перевіркою рішення в MS Excel. При цьому обмеження типу xi ≥ 0 не зважайте.

Суть методу гілок і меж полягає в послідовному переборі варіантів, розгляді лише тих з них, які за певними ознаками виявляються перспективними, і відкиданні безперспективних варіантів. При використанні методу гілок і меж область допустимих рішень (ОДР) вихідної задачі певним способом розбивається на підмножини, і вирішуються підзадачі, тобто завдання на цих подмножествах з тієї ж ЦФ і без урахування умови целочисленности (як завдання ЛП). Якщо в результаті отримано оптимальне нецелочисленное рішення, ОДР підзадачі знову розбивається на частини і цей процес триває до тих пір, поки не буде знайдено оптимальне цілочисельне рішення вихідної задачі.
Якщо в задачі на максимум при вирішенні подзадач виходять оптимальні цілочисельні рішення, то запам'ятовуються ті з них, яким відповідають зростаючі значення ЦФ. Якщо отримане «безперервне» рішення підзадачі виявляється не краще збереженого цілочисельного рішення, то така подзадача виключається зі списку завдань. Назва цього методу пояснюється тим, що в процесі вирішення завдання послідовно «галузиться», розбиваючись на більш прості підзадачі.

Примітка. метод гілок і меж використовується також і в завданні комівояжера.

Приклад. У задачі методом Гоморі (або методом гілок і меж) знайти оптимальні рішення задач цілочисельного лінійного програмування. Дати геометричну інтерпретацію процесу рішень задач.
Z = 3x1 + 2x2 → max
при обмеженнях:
x1 + x2 ≤ 13
x1 - x2 ≤ 6
-3x1 + x2 ≤ 9
x1 ≥0, x2 ≥0
x1. x2 - цілі числа.