Алгоритм методу Гоморi-2

1. Розв’язуємо допоміжну ЗЛП (4.5) – (4.7). Нехай x (0) – її оптимальний розв’язок. Якщо ця задача не має розв’язку, то вихідна ЧДЗЛП також не має розв’язку.

2. Нехай на s -й iтерацiї розв’язана допоміжна ЗЛП, що має M обмежень i N змінних, x (s) – її оптимальний розв’язок. Припустимо, що x (s) визначається канонічними обмеженнями останньої iтерацiї, а саме:

x_i + Q_i,M+1x_M+1+...+ Q_iNx_N= Q_i0, i=1,...,M,

звідки випливає, що x (s) = (Q₁₀,..., Q_M0, 0 ,..., 0).

3. Якщо Q_i0 (i= 1 ,...,p) – цілі, то кінець: x (s) є оптимальним розв’язком вихідної ЧДЗЛП. Якщо існує хоча б одне i таке, що Q_i0 – не цiле (i= 1 ,...,p), то переходимо до пункту 4.

4. Знаходимо r = min { i } за всіма i (i= 1 ,...,p) таких, що Q_i0 – не цiле і будуємо додаткове обмеження за формулами (4.9), (4.10) при m=M та n=N.

5. Розширюємо таблицю за рахунок (M+1)-го рядка (додаткове обмеження) та (N+1)-го стовпця, що відповідає додатковій змінній x_N+1.

6. Розв’язуємо розширену ЗЛП за допомогою двоїстого симплекс-методу (ДСМ) i переходимо до пункту 2 з заміною s на s+1, M на M+1, N на N+1. Якщо на деякій iтерацiї ДСМ одна з додаткових змінних задачі знову стає базисною, то з подальшого розгляду виключаються відповідні їй рядок та стовпець i при переході до пункту 2 замінюється лише s на s+1.

Задача дискретного ЛП. Метод Гоморi-3

Постановка задачі дискретного програмування (ДЗЛП). Знайти вектор x = (x₁,...,x_n), що мiнiмiзує цільову функцію

L (x) = c₁x₁+... + c_nx_n (4.11)

i задовольняє систему обмежень

a₁₁x₁ +... + a_1nx_n= a₁₀,

......................., (4.12)

a_m1x₁+... + a_mnx_n= a_m0,

x_j 0, j= 1 ,...,n, (4.13)

x_j – цілі, j= 1 ,...,n. (4.14)

Виклад методу Гоморi-3. Суть методу.

Нехай обмеження (4.12) ЗЛП (4.11) – (4.13) приведені до майже канонічного вигляду:

x_i+_i,m+1x_m+1+...+_inx_n=_i0, i= 1 ,...,m, (4.15)

де _ij, i= 1 ,...,m, j= 0 ,m+ 1 ,...,n, – цілі та симплекс-рiзницi j 0, j= 1 ,...,n.

Якщо _i0 0, i= 1 ,...,m, то обмеження (4.15) визначають оптимальний розв’язок ДЗЛП (4.11) – (4.14), інакше, визначається деякий дискретний майже допустимий базисний розв’язок (МДБР) вихідної ЗЛП. Можна було б вибрати один з індексів i, для якого _i0 <0, та виконати iтерацiю двоїстого симплекс-методу. Проте в цьому випадку дискретність нових параметрів була б порушена через необхідність ділення на головний елемент перетворення. Цього можна уникнути лише тоді, коли головний елемент дорівнює –1. Виявляється, що можна побудувати додаткове обмеження, яке задовольняє всі дискретні розв’язки ДЗЛП i яке разом з тим визначає головний рядок перетворення, що має головний елемент –1. Будується воно за l -м обмеженням системи (4.15), для якого _i0 мінімальне серед від’ємних _i0, i має вигляд:

x_n+1+_m+1,_m+1x_m+1+...+_m+1,nx_n=_m+1,₀,

де x_n+1 0 – додаткова змінна,

_m+1,j = [ _lj/ ], j=0,m+1,...,n,

= max { _lj }, j=m+1,...,n.

Отже, симплекс-таблиця розширюється за рахунок (m+1)-го рядка з елементами _m+1,j (_m+1,j =0, де j=1,...,m) та одиничного стовпця A _n+1, що відповідає додатковій змінній x_n+1. Потім, виконується iтерацiя двоїстого симплекс-методу з (m+ 1)-им головним рядком.