Алгоритм методу Дальтона-Ллевелiна

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

2. Нехай на s -й iтерацiї розв’язана допоміжна ЗЛП, що має M обмежень та 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) задовольняє умову (4.19), то кінець: x (s) є розв’язком вихідної ЧДЗЛП.

4. Знаходимо r = min { i } за всіма i (i=1,...,p) такими, що для деякого t (t=1,...,n_{i - 1}) X_it < Q_i0 < X_i,t+1, i будуємо додаткове обмеження за формулами (4.20) – (4.21) при 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 границь

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

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

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

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

......................., (4.23)

a_m1x₁+... + a_mnx_n R_m a_m0,

xj0, j=1,...,n, (4.24)

xj – цілі, j=1,...,n. (4.25)

де символ Ri (i=1,...,m) замінює один із знаків:, =,.

Вважається також, що багатокутна множина, яка визначається співвідношеннями (4.23) – (4.24), обмежена, а коефіцієнти c_j цільової функції (4.22) – цілі числа.

Наведемо алгоритм методу Ленд-Дойг, яким є реалізація методу гілок та границь для сформульованої вище задачі.

Виклад методу Ленд-Дойг. Розв’язується ЗЛП (4.22) – (4.24), яка отримана з вихідної ДЗЛП (4.22) – (4.25) відкиданням умови дискретності змінних (4.25) (гілка 0;1). Якщо її розв’язок x (0;1) – дискретний, то він є розв’язком вихідної ДЗЛП. Інакше, величина (0;1)= L [ x (0;1)] дає нижню оцінку (границю) цільової функції ДЗЛП на множині D (0;1)= D, що визначається співвідношеннями (4.23), (4.24).

Нехай деяка координата x_j (0;1) (j=1,...,n) розв’язку x (0;1) не є дискретною. В цьому випадку здійснюється розгалуження множини D (0;1) на дві пiдмножини D (1;1) i D (1;2) додаванням до обмежень, що задають D (0;1), обмежень x_j [ x_j (0;1)] та x_j [ x_j (0;1)] + 1 відповідно, де [ z ] – ціла частина числа z. Далі розв’язуються нові допоміжні ЗЛП з обмеженнями, які визначаються пiдмножинами D (1;1) та D (1;2), знаходяться границі (1;1) та (1;2) i т. д.

Для подальшого розгалуження обирається перспективна множина D (k;r) з найменшою границею (k;r). Процес продовжується до тих пір, поки не буде отримано розв’язок, який задовольняє умову дискретності i для якого виконується ознака оптимальності (див. п.4 алгоритму). Внаслiдок обмеженості допустимої множини ЗЛП (скінченності допустимої множини ДЗЛП) метод Ленд-Дойг буде скiнченним.