8.4. Дробовий алгоритм для розв'язання цілком цілочисельних задач (перший переріз Гоморі).

Необхідна передумова застосування дробового алгоритму – цілочисельність усіх коефіцієнтів вихідної моделі. Наприклад, обмеження:

x1 +1/3x2£13/2

необхідно замінити еквівалентною умовою з цілочисельними коефіцієнтами:

6x1 +2x2£39.

При розв'язанні ЗЦЛП зазначеним методом спочатку знаходять розв’язок задачі з послабленими обмеженнями. Якщо отриманий оптимальний розв’язок ЗПО є цілочисельним, то він буде оптимальним і для вихідної задачі; у протилежному випадку необхідно продовжити обчислення.

Представимо схему симплекс-таблиці з оптимальним розв’язком задачі з послабленими обмеженнями у вигляді табл. 8.1.

Таблиця 8.1. – Симплекс-таблиця з оптимальним розв’язком ЗПО (схема)

Оскільки всі xi та - цілочисельні, то права частина рівняння (8.3) також цілочисельна, а значить є цілочисельною і його ліва частина.

Так як fij³0, wj³0 для всіх i та j, то  ³0 . Звідси  <  . Оскільки  <1, то різниця  <1 і при цьому є цілочисельною. Звідси  £0.

Зведемо останнє обмеження до рівності, ввівши залишкову змінну Si:

Si-  =  (8.4)

Рівняння (8.4) визначає переріз Гомори для цілком цілочисельної задачі.

Застосуємо тепер дробовий алгоритм до розв’язання лінійної цілочисельної задачі (приклад 8.3):

максимізувати функцію: z=7x1+9x2 при обмеженнях:

 Симплекс-таблиця з розв’язком задачі з послабленими обмеженнями приведена нижче.

В якості ведучого доцільно вибрати такий рядок, що дозволить побудувати найефективніший переріз Гоморі, який виключав би максимально можливу область нецілочисельних розв’язків. Як критерій ефективності вибору ведучого рядка прийнято використовувати емпіричне правило, що вимагає виконання наступної умови:

 (8.5)

Для розглянутого прикладу:

  .

Оскільки  >  , то рядок, асоційований із змінною x2, варто прийняти в якості ведучого. Цьому рядку буде відповідати наступне обмеження (переріз): S1-

Введемо в симплекс-таблицю з розв’язком ЗПО рядок, обумовлений рівністю (8.5), а також нову змінну S1 (табл. 8.4).

Оскільки для обох поточних базисних змінних оцінки ефективності однакові, то ведучий рядок виберемо довільним чином. Рівняння перерізу Гоморі, побудоване на основі рядка змінної x1, буде мати такий вигляд:

 S2 - .

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

Таблиця 8.6.

Базисні

змінні            x1        x2        x3        x4        S1        S2        Роз-в’язок

z        0          0          0          0          2          7          55

x2      0          1          0          0          1          0          3

x1      1          0          0          0          -1         1          4

x3      0          0          1          0          -4         1          1

x4      0          0          0          1          6          -7         4

Можна наочно переконатися в тому, що побудовані перерізи виключають частину області припустимих розв’язків задачі з послабленими обмеженнями. Виразивши в першому та другому обмеженнях залишкові змінні (відповідно S1 і S2) через змінні x1 і x2, одержимо еквівалентні нерівності: x2£3, x1+x2£7.

Слід зазначити, що загальне число обмежень породженої задач не може перевищувати кількості змінних вихідної задачі, а саме (m+n). Як тільки ця вимога порушується, одне з обмежень задачі стає надлишковим і не впливає ні на оптимальне, ні на проміжні розв’язки.