Метод відтинаючих площин

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

Додаткове обмеження, яке має вказані властивості, називається правильним відтинанням.

Після цього задача розв'язується з врахуванням нового обмеження. У випадку необхідності додається ще одне обмеження і т.д.

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

Приклад. Знайти максимум функції f (x ₁, x ₂)= x ₁+2 x ₂ при обмеженнях

Розв’язуючи графічним методом цю задачу, одержуємо, що максимум досягається в точці і дорівнює 7. Проведемо пряму х ₂=2, яка відтинає від області допустимих значень точку В. Ми отримали нову область допустимих значень A’B’CDO.

Рис. 2.30.

Функція f (x ₁, x ₂)= x ₁+2 x ₂ досягає найбільшого значення в точці B ¢(2,5;2), яке дорівнює f (2,5;2)=2,5+4=6,5.

Проводимо пряму х ₁=2, яка відтинає від області допустимих значень точку В ¢. Для області допустимих значень A'MC'DO функція f досягає максимального значення в точці М (2,2), яке дорівнює f (2,2)=2+4=6.

Таким чином, х ₁=2, х ₂=2 – цілочисельний розв'язок задачі.