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

1. Зводимо вихідну ЗЛП (4.11) – (4.13) до майже канонічної ЗЛП (МКЗЛП) з цiлочисловими коефіцієнтами, що визначає дискретний МДБР x (0), для якого j0, j=1,...,n.

2. Нехай на s -й iтерацiї отримана повністю дискретна МКЗЛП

x_i+_i,M+1x_M+1+...+_iNx_N=_i0, i= 1 ,...,M,

що визначає дискретний N -вимiрний МДБР x (s) = (₁₀,.., _M0, 0 ,.., 0).

3. Якщо _i0 0, i= 1 ,...,M, то кінець: x (s) – оптимальний розв’язок ДЗЛП.

4. Якщо для деякого i такого, що _i0 <0, _ij 0, j=1,...,N, то кінець: вихідна ДЗЛП не має допустимих розв’язкiв. Якщо таких i немає, то переходимо до пункту 5.

5. Знаходимо l = argmin { _i0 }, де i: _i0 <0. Визначаємо = max {– _lj }, j=M+1,...,N, і будуємо додаткове обмеження

x_N+1+_M+1,M+1x_M+1+...+_M+1,Nx_N=_M+1,0,

де x_N+1 0 – додаткова змінна, _M+1,j – ціла частина відношення _lj, j=0,M+1,...,N.

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

7. Знаходимо k = argmin { j }, де j: _M+1,j <0. Переходимо до нового цiлочисельного МДБР x (s+1), виконуючи симплекс-перетворення з глов-ними рядком M+1 та стовпцем k. Якщо k – індекс однієї з додаткових змінних, то переходимо до п. 8, iнакше – до п. 3, замінюючи M на M+1, N на N+1, s на s+1.

8. Виключаємо з подальшого розгляду (викреслюємо) k -й стовпець та (M+1)-й (останній) рядок симплекс-таблицi, перенумеровуємо решту додаткових змінних для збереження неперервної нумерації всіх змінних задачі i переходимо до п. 3, замінюючи s на s+1.

Задача частково дискретного ЛП. Метод Дальтона-Ллевелiна

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

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

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

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

......................., (4.17)

a_m1x₁+... + a_mnx_n= a_m0,

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

x_j { X_j1,...,X_j,nj }, j= 1 ,...,p, (pn), (4.19)

де 0 = X_j1 <...< X_j,nj.

Виклад методу Дальтона-Ллевелiна. Метод Дальтона-Ллевелiна, як i методи Гоморi, є одним з методів відсікання i його суть.

Розв’язується допоміжна ЗЛП (4.16)-(4.18), яку отримують з вихідної задачі (4.16) – (4.19) відкиданням умови дискретності змінних (4.19). Якщо її розв’язок задовольняє умову (4.19), то він i є розв’язком вихідної ЧДЗЛП. Інакше, від розв’язаної ЗЛП переходять до нової допоміжної ЗЛП приєднанням лінійного обмеження, що задовольняє дискретні (в розумінні умов (4.19) розв’язки вихідної ЧДЗЛП, але не задовольняє отриманий розв’язок вихідної ЗЛП. Це додаткове обмеження визначає деяку відсічну площину, i називається правильним вiдсіканням. Приєднання нових правильних вiдсікань до початкової ЗЛП здійснюється до тих пір, поки на деякому кроцi не буде отриманий дискретний розв’язок допоміжної ЗЛП, який, як очевидно, буде оптимальним розв’язком вихідної ЧДЗЛП.

В методі Дальтона-Ллевелiна правильне вiдсікання будується таким чином. Нехай на останній iтерацiї симплекс-методу під час розв’язування допоміжної ЗЛП її непрямі обмеження набули вигляду:

x_i + Q_i,m+1x_m+1 +...+ Q_inx_n = Q_i0, i=1,...,m,

i розв’язком допоміжної ЗЛП є вектор x = (Q₁₀,..., Q_m0, 0 ,..., 0).

Нехай існує номер r (rp) такий, що Q_r0 не задовольняє (4.19), до того ж X_rt < Q_r0 < X_r,t+1 для деякого t= 1 ,...,nr -1. Тоді правильне вiдсікання методу Дальтона-Ллевелiна має вигляд:

x_n+1 – D_r,m+1x_m+1 –...– D_rnx_n = – (Q_r0 – X_rt), (4.20)

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

(4.21)