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

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

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

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

z=7x1+9x2

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

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

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

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