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

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

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

Читати повністю

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

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

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

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

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

Читати повністю

Метод Гоморі (метод відсікаючих площин)

Метод відсікаючих площин існує у двох варіантах: перший варіант призначений для розв'язку повністю цілочисельних задач (перший алгоритм Гоморі) і другий варіант —  призначений для розв'язку частково цілочисельних задач (другий алгоритм Гоморі). Основна відмінність між ними полягає у способі формування відсікання.

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

  1. Лінійна задача розв'язується класичним симплекс-методом, без врахування цілочисельності змінних Алгоритм Гоморі. В результаті отримують деякий оптимальний опорний план, який має наступний вигляд:

    Алгоритм Гоморі

  2. Якщо (1) містить рівняння для яких базисниі змінні Алгоритм Гоморі мають дробові значення, то серед них обирають таке рівняння, яке має найбільшу дробову частину. Дане рівняння перетворюють у додаткову нерівність:

    Алгоритм Гоморі

    де Алгоритм Гоморі.

Для обрання чисел Алгоритм Гоморі та Алгоритм Гоморі існують наступні правила:

Читати повністю