Метод гілок та меж. Розв'язок задачі цілочисельного програмування методом гілок та меж

Метод гілок і меж — один з комбінаторних методів. На відміну від методу Гоморі застосовується як до повністю, так і частково цілочисельних задач. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками корисними для знаходження оптимального рішення.

Згідно загальній ідеї методу, на першому кроці поставлена задача розв’язується як задача лінійного програмування, тобто без урахування умови цілочисельності. Якщо отримано оптимальний цілочисловий розв’язок задачі лінійного програмування, то він є також розв’язком задачі цілочисельного лінійного програмування. Якщо ж не отримано цілочисельного розв’язку, то через Метод гілок та меж позначають цілу частину змінної Метод гілок та меж, значення якої в оптимальному розв’язку задачі лінійного програмування є дробовим. Після чого, інтервал Метод гілок та меж виключається з розгляду, як тауий, що не містить допустимих цілочисельних компонент розв’язку. Тому допустиме ціле значення Метод гілок та меж повинно задовольняти одну з нерівностей Метод гілок та меж або Метод гілок та меж.

Дописавши кожну з цих умов до розв'язуваної задачі, дістанемо дві, не пов’язані між собою, задачі. У цьому випадку кажуть, що вихідна задача розбивається (розгалужується) на дві підзадачі. Потім кожна підзадача розв’язується як задача лінійного програмування. Якщо оптимальний розв’язок виявляється допустимим для цілочисельної задачі, то такий розв’язок слід зафіксувати як найкращий. При цьому немає необхідності продовжувати розгалуження підзадачі, оскільки покращити отриманий розв’язок, очевидно, не вдасться.

В іншому випадку підзадача в свою чергу повинна бути розбита на дві підзадачі знову при врахуванні умов (2) — (3). Зрозуміло, коли отримуємо допустимий цілочисловий розв’язок однієї з підзадач краще попереднього,  то він фіксується  замість  зафіксованого раніше.

Процес розгалуження продовжується до тих пір, поки кожна підзадача не приведе до цілочислового розв’язку або доки не буде встановлена неможливість покращення зафіксованого розв’язку. У цьому випадку зафіксований допустимий розв’язок буде оптимальним.

Метод гілок та меж — приклад:

Для виготовлення товару A і В підприємство використовує два види сировини. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A та B, а також загальна кількість сировини наведені в наступній таблиці:

Метод гілок та меж приклад

Таблиця даних задачі цілочисельного програмування

Необхідно скласти такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.

Нехай Метод гілок та меж приклад та Метод гілок та меж приклад — кількість комплектів товару типу А та В відповідно. Тоді економіко-математична модель даної задачі запишеться у наступному вигляді:

Метод гілок та меж приклад

де Метод гілок та меж приклад та Метод гілок та меж приклад — цілі числаю. На першому кроці, як і для випадку з методом Гоморі, розв'яжемо дану задачу нехтуючи умовою цілочисельності. Для цього скористаємось симплекс методом, остання таблиця якого, для даної задачі, набуде наступного вигляду:

Метод гілок та меж приклад

Розв'язок задачі лінійного програмування без урахування умови цілочисельності

З даної таблиці бачимо, що для початкової задачі, з урахуванням умови цілочисельності змінних, отримане рішення не є оптимальним. Для пошуку цілочисельного оптимального рішення розділимо інтервал зміни змінної Метод гілок та меж приклад на дві області, а саме Метод гілок та меж приклад та Метод гілок та меж приклад, і розіб'ємо задану задачу на дві нові:

Метод гілок та меж приклад

На першому кроці розв'яжемо, наприклад, задачу 3. Для цього, шляхом введення додаткових змінних, систему нерівностей приведемо до системи рівнянь (запишемо систему обмежень у канонічній формі), після чого перейдемо до побудови першого опорного плану:

Перший опорний план задачі 3

Перший опорний план задачі 3

Виходячи з того, що серед вільних членів системи обмежень задачі 3 існують такі, що приймають від'ємні значення, то для її розв'язку слід сористатись двоїстим симплекс методом. В результаті отримаємо таблицю, з допомогою якої бачимо, що дана задаче немає розв'язкуів (в рядку, з від'ємним значенням вільного члена усі елементи додатні):

Розв'язок задачі 3 використовуючи двоїстий симплекс метод

Розв'язок задачі 3 використовуючи двоїстий симплекс метод

Далі, переходимо до розв'язку задачі 2. Для цього, аналогічгим чином, запишемо систему обмежень у канонічній формі та побудуємо перший опорний план:

Перший опорний план задачі 2

Перший опорний план задачі 2

Після цього, скориставшись симплекс методом отримаємо:

Розв'язок задачі 2 використовуючи симплекс метод

Розв'язок задачі 2 використовуючи симплекс метод

Для отриманого оптимального плану задачі 2 умова цілочисельності також не виконується, тому дану задачу розбиваємо на дві нові. В результаті отримаємо:

Метод гілок та меж приклад

Розв'язавши задачу 5 двоїстим симплекс методом, отримуємо перший цілочисельний розв'язок, тому фіксуємо його як найкращий і переходимо до задачі 4.

Розв'язок задачі 5 використовуючи двоїстий симплекс метод

Розв'язок задачі 5 використовуючи двоїстий симплекс метод

Для задачі 4, записавши систему обмежень у канонічній формі бачимо, що серед векторів Метод гілок та меж приклад міститься лише три одиничних. Тому в ліву частину останнього, четвертого, рівняння системи обмежень додаємо додаткову невід’ємну змінну Метод гілок та меж приклад, після чого переходимо до розгляду розширеної задачі:

Метод гілок та меж приклад

для якої перший опорний план прийме наступного вигляду:

Метод гілок та меж приклад

Перший опорний план задачі 4

Розв'язавши дану задачу методом штучного базису, отримуємо новий цілочисельний розв'яок, який являється кращим за попередній, тому фіксуємо його замість зафіксованого раніше і таким чином, з допомогою двох розгалужень, знаходимо шуканий оптимальний розв'язок для заданої задачі цілочисельного програмування.

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

Ров'язок задачі 4 методом штучного базису

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар