Page 44 - 4168

Метод Гоморі
За допомогою відсікань виділяють цілочислові частини
області допустимих значень (ОДЗ). Існує можливість розв'яза-
ти дану задачу у певному розумінні частково, послідовно від-
сікаючи від множини ОДЗ деякі її частини за допомогою так
званих відсікаючих площин. Ідея методів відсікання полягає в
наступному: розв'язується ЗЛП, одержана з цілочислової
відкиданням умови цілочисловості змінних. Якщо її розв'язок є
цілочисловим, то він же є і розв'язком цілочислової задачі.
Якщо ж задача розв'язку не має, то і ЦЗЛП розв'язку не має.
Якщо розв'язок ЗЛП не є цілочисловими, то від розв'язаної
ЗЛП переходять до нової допоміжної ЗЛП шляхом додавання
лінійного обмеження, яке задовольняє усі цілочислові розв'яз-
ки ЦЗЛП, але не задовольняє одержаний нецілочисловий роз-
в'язок початкової ЗЛП. Це додаткове лінійне обмеження ви-
значає деяку відсікаючу площину і називається правильним від-
сіканням. Додавання нових правильних відсікань до початко-
вої допоміжної ЗЛП здійснюється доти, поки на деякому кроці
не буде одержаний цілочисловий розв'язок допоміжної задачі,
який, очевидно, буде оптимальним розв'язком вихідної ЦЗЛП.
Алгоритм першого методу Гоморі
1 Розв'язуємо допоміжну ЗЛП. Нехай х (0) — її оптимальний
розв'язок. Якщо оптимальний розв'язок не існує, то вихідна
ЦЗЛП також не має оптимального розв'язку.
2 Нехай на s -й ітерації розв'язана допоміжна ЗЛП, що має m
обмежень та n змінних, x(s) - її оптимальний розв'язок. Бу-
демо вважати, що канонічні обмеження останньої ітерації,
що визначають x ( s ) , мають вигляд:
n
x i + ∑ a ij x j = β (3.24)
,
i
j =m +1
де i = 2 , 1 ,..., . m
Розв'язком допоміжної ЗЛП є n-вимірний вектор
x (s ) = (β 1 ,...,β m 0 , , ,..., ) 0 .
3 Якщо β , і=1,...,m,- цілі, то x(s) є оптимальним розв'язком
i
задачі.
Якщо існує хоча б одне i таке, що β - дріб, то переходимо
i
до пункту 4.

44