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

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

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

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

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

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

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

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

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

1) якщо дробові числа Алгоритм Гоморі або Алгортм Гоморіє додатніми числами, то Алгоритм Гоморі та Алгоритм Гоморі є цілими додатніми числами і дорівнюють цілій частині числа  Алгоритм Гоморі або Алгортм Гоморі відповідно. Приклад:

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

2) якщо дробові числа Алгоритм Гоморі або Алгортм Гоморіє від’ємними числами, то Алгоритм Гоморі та Алгоритм Гоморі є від’ємними цілими числами, які по абсолютній величині на одиницю більші за абсолютну величину цілої частини числа  Алгоритм Гоморі або Алгортм Гоморі. Приклад:

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

3) якщо  Алгоритм Гоморі або Алгортм Гоморіє цілими числами, то Алгоритм Гоморі і Алгоритм Гоморі;

4) додаткова нерівність (2) повинна містити лише додатні коефіцієнти. Вона множенням на -1 спочатку приводиться до вигляду, який повинна мати нерівністьу симплекс-методі згідно із стандартною формою:

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

а потім за допомогою додаткової змінноїАлгоритм Гоморі перетворюється у наступне рівняння:

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

яке додається до оптимального опорного плану системи (1) і сумусно з ним створює псевдоплан, який містить одне від’ємне значення Алгоритм Гоморі;

5) даний псевдоплан розв’язується двоїстим симплекс-методом. В результаті отримують новий оптимальний опорний план з додатніми значеннями Алгортм Гоморі та Алгоритм Гоморі. Якщо в новому оптимальному опорному плані існують змінні Алгоритм Гоморі, значення яких містять дробову частину, то знову додають одне додаткове обмеження, і процес розрахунків повторюється до отримання цілочисельних значень базисних змінних.

Ознакою відсутності розв’язку задачі є наявність у таблиці хоча б одного рядка з цілими величинами Алгоритм Гоморі та вільним членом Алгортм Гоморі, значення якого містить дробову частину. Дана ознака вказує на відсутність розв’язку у цілих кислах.

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

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

де величини Алгоритм Гоморі визначається з наступних співвідношень:

1) для нецілочисельних значень змінних Алгоритм Гоморі:

Алгоритм Гоморі2) для цілочисельних змінних Алгоритм Гоморі:

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

Залишити коментар

Your email address will not be published. Required fields are marked *

*