Постановка задачі дискретного програмування має вигляд

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

F = (c, x) ® max (min), (12.1)

a_ij x_j {£, =, ³} b_i, (12.2)

x_j A_j, j=1, n_1, n₁ £ n, (12.3)

де A_j, - дискретна (скінчена або злічена) множина. Умова дискретності може накладатися не на усі змінні.

Задача цілочисельного програмування

Якщо у обмеженнях (12.3) A_j = Z, де Z - множина цілих чисел, задачу (12.1 – 12.3) називають задачею цілочисельного програмування. У випадку, коли n₁ = n, задача називається повністю цілочисельною, а якщо n₁ < n, - частково цілочисельною.

Окремо виділяють клас задач, для яких у обмеженні (12.3) A_j = { 0, 1 }. Ці задачі складають клас задач бівалентного (булевого) програмування.

Надалі будемо розглядати задачу повністю цілочисельного програмування у канонічній формі.

F = (c, x) ® min, (12.4)

a_ij x_j = b_i, i = 1, m, (12.5)

x_j ³ 0, j = 1, n, (12.6)

x_j - ціле, j = 1, n. (12.7)

Оскільки задача (12.4 – 12.7) відрізняється від звичайної задачі лінійного програмування лише додатковим обмеження (12.7), природно виникає питання, чи можна цю задачу замінити еквівалентною задачею лінійного програмування і застосувати методи лінійного програмування. Принципову відповідь на це питання дає наступна теорема.

Теорема 12.1 (Про еквівалентність задачі цілочисельного програмування і задачі лінійного програмування) Якщо допустима область G задачі (12.4 – 12.6) – опуклий многогранник, G_ц – множина цілих точок з G, тобто допустима область задачі (12.4 – 12.7),і R – опукла оболонка G_ц , то мінімум F на R дорівнює мінімальному F на G_ц.

Доведення. З того, що область G- опуклий многогранник, тобто обмежена, прямує, що множина цілих точок G_ц - скінчена. Нехай G_ц має k цілих точок: {x¹, x², …, x^k}, xⁱ = (xⁱ₁, xⁱ₂, …, xⁱ_n), i = 1, k.

Кожна точка x = (x₁, x₂, …, x_n), що належить R, уявляється у вигляді

x = _i xⁱ, _i = 1, _i 0, i = 1, k.

Тому область R визначається системою рівнянь:

x_j = xⁱ_j l_i, j = 1, n.

l_i = 1,

l_i 0, i = 1, k.

Це означає, що задача пошуку екстремуму функції F = (c, x) на області R є задачею лінійного програмування. Оскільки кожна крайня точка x R є опуклою лінійною комбінацією точок x¹, x², …, x^k і одночасно не лежить у середині відрізку, що з’єднує дві різні точки з R, то x належить G_ц. Враховуючи, що функція F досягає екстремуму на R у крайній точці, отримуємо те, що требо було довести.

Теорема 12.1 показує принципову можливість зведення задачі цілочисельного програмування до задачі лінійного програмування, але не вказує практичного шляху побудови шуканої задачі лінійного програмування. На практиці знайшов застосування інший підхід до розв’язування задачі цілочисельного програмування, який базується на методі відтинань.

Ідея методу відтинань, який є ітераційною процедурою, полягає у тому, що на першій ітерації розв’язується задача (12.4 – 12.6) або задача пошуку мінімуму функції F на допустимій області G₀, що визначається обмеженнями (12.5, 12.6). Таким чином, на першій ітерації розв’язується звичайна задача лінійного програмування.

Якщо отриманий розв’язок x⁰ цілочисельний, то він є розв’язком вихідної задачі. Якщо ні, то у задачу (12.4 – 12.6) уводиться додаткове лінійне обмеження таким чином, щоб у результаті утворилася допустима областьG₁, якій розв’язок x⁰ не належить, а будь-який допустимий розв’язок вихідної задачі належить. На наступній ітерації відбувається пошук мінімуму функції F на області G₁ і т.д. Додаткові обмеження, що уводяться на кожній ітерації називаються відтинаннями, а метод розв’язування задачі – методом відтинань.

Відтинання називається правильним, якщо для нього виконуються дві умови:

1) поточний нецілочислений розв’язок відтинанню не задовольняє;

2) кожний допустимий розв’язок задачі (12.4 – 12.7) відтинанню задовольняє.

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

Ідея методу відтинань була запропонована американським математиком Данцигом, який є і автором симплекс-методу. Але форма правильного відтинання, запропонована Данцигом, виявилася недостатньо ефективною, і у результаті метод відтинань можна було застосовувати до відносно вузького класу задач з певними властивостями цільової функції і обмежень.

Більш досконалою формою правильного відтинання виявилася форма, запропонована іншим американським математиком Гоморі, на честь якого названо декілька алгоритмів розв’язування задачі цілочисельного програмування.

Дата добавления: 2014-01-13