Page 84 - 4719

Алгоритм першого методу Гоморі
1 Розв'язуємо допоміжну ЗЛП. Нехай х (0) — її
оптимальний розв'язок. Якщо оптимальний розв'язок не існує,
то вихідна ЦЗЛП також не має оптимального розв'язку.
2 Нехай на s -й ітерації розв'язана допоміжна ЗЛП, що
має m обмежень та n змінних, x(s) - її оптимальний розв'язок.
Будемо вважати, що канонічні обмеження останньої ітерації,
що визначають x ( s ), мають вигляд:
n
x i + ∑ a ij x j = β (14.1)
,
i
j =m +1
де i = 2 , 1 ,..., . m
Розв'язком допоміжної ЗЛП є n-вимірний вектор
x (s ) = (β 1 ,...,β m 0 , , ,..., ) 0 .
3 Якщо β , і=1,...,m,- цілі, то x(s) є оптимальним
i
розв'язком задачі.
Якщо існує хоча б одне i таке, що β - дріб, то переходимо
i
до пункту 4.
4 Знаходимо I, що відповідає максимальні дробовій
частині коефіцієнта { β }, по всіх таких i, що β - дріб, і
i
i
формуємо додаткове обмеження, у якому коефіцієнти будуть
дробовими частинами {g} коефіцієнтів попередніх обмежень
n
x
x n + 1 ∑ {a Ij } = { − β I },
−
j
j =m + 1 (14.2)
x n + 1 ≥ , 0
де x n + 1 - додаткова змінна.
5 Розширюємо симплекс-таблицю за рахунок (m+1)-го
рядка (додаткове обмеження) та ( n +1) - го стовпця, що
відповідає додатковій змінній x n + 1 .
6 Розв'язуємо розширену таким чином ЗЛП двоїстим
симплекс-методом і переходимо до пункту 2, змінюючи s на
s+1. Якщо при цьому на якій-небудь ітерації двоїстого
симплекс-методу одна з додаткових змінних задачі (тобто,
тих, що з'явилися при побудові правильних відсіків) повторно

83