8.3  . Графічна інтерпретація методів перерізу.

  Серед методів перерізу розрізняють прямі (ґрунтуються на застосуванні прямого симплексного методу) та двоїсті (мають в основі двоїстий симплекс-метод). У даному розділі будуть розглянуті два двоїстих методи, розроблені Р. Гоморі . Один з них (перший переріз Гоморі) застосовується до повністю цілочисельних задач, інший (другий переріз Гоморі) – до частково цілочисельних.

В основі методів перерізу лежить перетворення області допустимих розв’язків задачі з послабленими обмеженнями (ЗПО). Під останньою розуміють допоміжну задачу, отриману із вихідної цілочисельної задачі шляхом відкидання вимог цілочисельності. Дамо графічну інтерпретацію поняття перерізу на основі наведеного нижче прикладу.

Приклад 6.1. Потрібно знайти максимум функції:

Z=7x1+9x2

 При дотриманні системи обмежень:

 

           

Рис. 6.1. Графічне подання задачі цілочисельного лінійного програмування.

Задача з послабленими обмеженнями (ЗПО) буде відрізнятись від вихідної відсутністю обмежень цілочисельності (4). Чотирикутник ABCD на рис. 6.1 визначає область допустимих розв’язків, а його екстремальна точка С з координатами (9/2, 7/2) - оптимальний розв’язок ЗПО. Нехай деяким чином вдалося виділити область, що не містить точок з цілочисельними координатами (заштрихований багатокутник CЕFG на рис. 6.1). Цю область слід виключити з подальшого розгляду. Не заштрихована частина області допустимих розв’язків ЗПО являє собою опуклий багатокутник ABEFGD, одна з кутових точок якого (точка С з координатами (4, 3)) відповідає оптимуму вихідної цілочисельної задачі. У цій точці цільова функція свого набуває максимально допустимого значення, тобто z(С)= zmax=55.

 Прямі, що позначені штриховими лініями на рис. 6.1, відтинають від області допустимих розв’язків ЗПО підмножину нецілочисельних розв’язків,. При трьох змінних аналогічні обмеження являтимуть собою площини, при більшому числі змінних – гіперплощини. Звідси – термін: відтинаючі площини.

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

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

X1 +1/3x213/2

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

6x1 +2x239.

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

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

 

Sk      0          . . .        Xm      ...          -fk1      . . .        -f k n    . . .        0          -fk

У цій таблиці xi (  ) – змінні поточного базису; wj (  ) - небазисні змінні.

Розглянемо i-й рядок з нецілим значенням xi. Виразимо xi через небазисні змінні:

 , (6.1)

Де  i - неціле значення змінної; xi, ij - коефіцієнт при небазисній змінній wj  в i-му обмеженні.

Значення i  та ij  слід подати у вигляді сум цілої та дробової частин:

 , (6.2)

 

Де [а]- найближче до a ціле число, менше за a; f – дробова частина а  (f=a-[а]).

Приклад розкладання чисел на цілу й дробову частини (приклад 6.2) представлений у табл.

 

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

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

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

Si-  =  (6.4)

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

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

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

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

 

Таблиця 6.3. Симплекс-таблиця з розв’язком ЗПО

Базисні

Змінні            x1        x2        x3        x4        Розв’язок

Z       0          0          28/11   15/11   63

X2     0          1          7/22     1/22     7/2

X1     1          0          -1/22   3/22     9/2

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

  (6.5)

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

 

  .

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

 

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

 

Таблиця 6.4.

Базисні змінні           x1        x2        x3        x4        S1        Роз-в’язок

Z       0          0          28/11   15/11   0          63

X2     0          1          7/22     1/22     0          7/2

X1     1          0          -1/22   3/22     0          9/2

S1      0          0          -7/22   -1/22   1          -1/2

Використання двоїстого симплекса-методу приводить до розв’язку, представленого в табл. 6.5.

Таблиця 6.5.

Б.П.   x1        x2        x3        x4        S1        Роз-в’язок

Z       0          0          0          1          8          59

X2     0          1          0          0          1          3

X1     1          0          0          1/7      -1/7     44/7

X3     0          0          1          1/7      -22/7   14/7

 

Визначимо ведучий рядок:

  .

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

  S2 - .

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

 

Таблиця 6.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). Як тільки ця вимога порушується, одне з обмежень задачі стає надлишковим і не впливає ні на оптимальне, ні на проміжні розв’язки.