Дискретне програмування

Під час розв’язання задач ЛП часто висувається вимога дискретності (цілочисельності) змінних, що входять у розв’язок. Множиною планів такої задачі буде система точок із цілочисловими координатами, що належать опуклому багатокутнику допустимих розв’язків відповідної недис­кретної задачі. Якби можна було визначити гіперплощини, що проходять через зовнішні точки такої системи точок цілочислової задачі, причому так, щоб зовнішні точки цієї системи потрапили до нового опуклого багатокутника, то задачу можна було б розв’язати за допо­могою звичайного симплекс-методу. У цьому випадку всі крайні точки опуклого багатокутника були б цілочисловими і розв’язок можна було б знайти за скінчене число кроків. Ця ідея послідовного відсікання частин вихідного багатокутника планів, що не містять допустимих цілочислових планів, покладена в основу методів Гоморі, які реалізуються за рахунок побудови додаткових обмежень-нерів­но­стей, які визначають відсічні гіперплощини. Ці обмеження мають задовольняти дві умови: відсікання, яке полягає у тому, що вони не повинні задовольняти план недискретної задачі; правильності відсікання, що полягає у тому, що вони ма­ють задовольняти всі цілочислові плани задачі.

Існує також широкий клас досить універсальних методів, основою яких є пошук оптимуму на дискретній множині пла­нів задачі, на кожному кроці якого виключається з розгляду значна кількість неоптимальних планів. Такі методи мають назву гілок і границь. Їх суть полягає в тому, що множину планів задачі розбива­ють на ряд підмножин, для кожної з яких знаходять оцінку цільової функції. Процедуру повторюють до тих пір, поки не знаходять підмножину, що містить оптимальний план.

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

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

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

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

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

......................., (4.2)

a_m1x₁+... + a_mnx_n= a_m0,

x_j0, j=1,...,n, (4.3)

xj цілі (4.4)

Виклад методу Гоморi-1. Розв’язується ЗЛП (4.1)-(4.3), яку отримують з вихідної задачі ДЗЛП (4.1)-(4.4) відкиданням умови дискретності змінних (4.4). Якщо оптимальний розв’язок ЗЛП – дискретний, то він буде і розв’язком вихідної ДЗЛП. Якщо ж отриманий розв’язок задачі не дискретний, то від розв’язаної ЗЛП переходять до нової ЗЛП, що отримується додаванням додаткового лінійного обмеження, яке задовольняє дискретні розв’язки вихідної ДЗЛП i яке не задовольняє отриманий недискретний розв’язок ЗЛП. Це додаткове лінійне обмеження визначає деяку відсічну площину i називається правильним відсіканням. Приєднання нових правильних відсікань до вихідної ЗЛП здійснюється до тих пір, поки на деякому кроцi не буде отримано дискретний розв’язок ЗЛП, який, як очевидно, буде оптимальним розв’язком вихідної ДЗЛП. В методі Гоморi-1 правильне відсікання будується таким чином.

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

x_i + a¢_i,m+1 x_m+1+...+ a¢_inx_n= a¢_i0, i=1,...,m,

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

Нехай існує номер r такий, що a¢_r0 – дріб, i, як завжди, { z } – дробова частина z. Тоді правильне вiдсікання за методом Гоморi-1 задається такою нерівністю:

{ a¢_r,m+1 } x_m+1+...+ { a¢_rn } x_n { a¢_r0 }.