3.6.3. Метод відтинання.

Перший метод такого типу був запропонований Гоморі в 1958 році, що і стало основою подальшого розвитку декількох нових методів, таких як:

- метод розв’язування повністю цілочислових задач (дробовий алгоритм Гоморі);

- методи розв’язування частково цілочислових задач (другий алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).

Методи розв’язування повністю цілочислових задач і частково цілочислових задач в своїй основі мають одну ідею: якщо в оптимальному плані ЗЛП базисна змінна на яку накладено обмеження цілочисленості, має не цілочислене значення _і і це значення обмежене, тоді доцільно будувати обмеження «відтинання».

Розглянемо дробовий алгоритм Гоморі, для розв’язування повністю цілочислової задачі лінійного програмування, що ґрунтується на використанні симплексного методу і застосуванні досить простого способу відтинання.

Розглянемо задачу цілочислового програмування (3.19 – 3.21).

Вважаємо, що параметри — цілі числа.

Не враховуючи умови цілочисловості, знаходимо розв’язок задачі (3.19 – 3.21) симплексним методом. Нехай розв’язок існує і міститься в такій симплексній таблиці:

Таблиця 3.4

Змінні — базисні, а — вільні. Оптимальний план задачі: . Якщо — цілі числа, то отриманий розв’язок є цілочисловим оптимальним планом задачі (3.16 – 3.18). Інакше існує хоча б одне з чисел, наприклад, — дробове. Отже, необхідно побудувати правильне обмеження, що відтинає нецілу частину значення .

Розглянемо довільний оптимальний план задачі (3.19 – 3.21), представимо в цьому плані базисну змінну через вільні змінні:

. (3.22)

Коефіцієнти при змінних даного рівняння представимо у вигляді суми їх цілої та дробової частин. Введемо позначення: — ціла частина числа , — дробова частина числа . Отримаємо:

, (3.23)

або

. (3.24)

Рівняння (3.24) виконується для будь-якого допустимого плану задачі (3.19 – 3.21). Припустимо, що розглянутий план є цілочисловим оптимальним планом задачі. Тоді ліва частина рівняння (3.24) складається лише з цілих чисел і є цілочисловим виразом. Отже, права його частина також є цілим числом і справджується рівність:

, (3.25)

де N — деяке ціле число.

Величина N не може бути від’ємною,тому що при , від рівняння (3.25) перейдемо до нерівності:

.

Звідки . Тобто це означало б, що дробова частина числа перевищує одиницю, що неможливо.

Якщо від обох частин рівняння (3.25) відняти деяке невід’ємне ціле число N, то переходимо до нерівності:

, (3.26)

яка виконується за попереднім припущенням цілочисленності лівої частини рівності, для будь-якого цілочислового плану задачі (3.19 – 3.21). Тобто, нерівність (3.26) є шуканим додатковим обмеженням задачі.

Розв’язування повністю цілочислових задач дробовим алгоритмом Гоморі передбачає виконання наступних дій:

1. Симплексним методом розв’язується «послаблена» задача без вимог цілочисловості змінних — (3.19 – 3.21).

Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей план є оптимальним розв’язком задачі цілочислового програмування.

Якщо «послаблена» задача (3.196 – 3.21) не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача і з урахуванням цілочисенності також не має розв’язку.

2. Коли в умовно-оптимальному плані є дробові значення, то вибирається змінна, яка має найбільшу дробову частину. На базі цієї змінної (елементів відповідного рядка останньої симплексної таблиці, в якому вона міститься) будується додаткове обмеження Гоморі(3.26).

3. Додаткове обмеження (попередньо зведене до канонічного вигляду) приєднується до останньої симплексної таблиці, яка містить умовно-оптимальний план. Отриману розширену задачу розв’язують і перевіряють її розв’язок на цілочисловість. Якщо він не цілочисловий, то процедуру повторюють, повертаючись до п. 2. Так діють доти, доки не буде знайдено цілочислового розв’язку або доведено, що задача не має допустимих розв’язків на множині цілих чисел.

Розглянемо застосування дробового алгоритму Гоморі на прикладі.

Приклад 3.5. Розв’язати цілочислову задачу лінійного програмування:

Розв’язок.

Розв’яжемо «послаблену» задачу симплексним методом, попередньо звівши задачу до канонічного вигляду.

Маємо оптимальний план «послабленої» задачі (без урахування умови цілочисленості змінних):

X* = (x₁=0;x₂=5/3;x₃=7/3;x₄=0),

Min Z = -10/3

Так як отриманий оптимальний план не задовольняє умову цільчисленості, то будуємо додаткове обмеження Гоморі для змінної x₂:

Додамо обмеження Гоморі до останьої симплексної таблиці:

Розв’яжемо «розширену» задачу:

План оптимальний, але вимога цілочисленості змінних не виконана, в таблицю додаємо нове обмеження Гоморі для змінної х₂:

1/2x₁ + 0x₂ + 0x₃ + 0x₄ + 1/2x₅ + 1/2x₆ ≥ 1/2,

1/2x₁ + 0x₂ + 0x₃ + 0x₄ + 1/2x₅ + 1/2x₆ – 0x₇ + Mx₈ = 1/2

І знову розв’язуємо задачу симплексним методом

Отримали оптимальний план задачі цілочислового лінійного програмування :

X* = (x₁=1;x₂=1;x₃=0;x₄=0; x₅=0; x₆=0; x₇=0; x₈=0).

Min Z = -3

Теоретично, алгоритм Гоморі є скінченним, але процес розв’язування задач великої розмірності методом Гоморі досить громіздкий. Якщо в лінійному програмуванні спостерігається відносно жорстка залежність між кількістю обмежень задачі та кількістю ітерацій, що необхідна для її розв’язування, то для цілочислових задач такої залежності не існує. Загалом, процес розв’язання цілочислової задачі визначається не лише її розмірністю, а також особливостями багатогранника допустимих розв’язків, що являє собою набір ізольованих точок. Крім того, кількість ітерацій залежить від обраного правильного відтинання. Наведене правило (3.23) правильного відтинання не єдине і існують інші правила формування відтинання, які використовуються в інших алгоритмах Гоморі [12, 27], однак вибір залежить від окремої задачі та рівня знань фахівця.

28