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

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

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

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

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

Приклад 1.10.Знайти найбільше значення функції при обмеженнях

, – цілі числа.

Розв’язок. Розв’язуючи задачу графічним методом, знайдемо, що найбільше значення досягається в точці і дорівнює 7. Проведемо пряму , яка відтинає від області допустимих значень точку В . Ми отримали нову область допустимих значень А^/В^/СDO.

Рис.1.11

Функція досягає найбільшого значення в точці , яке дорівнює

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Постановка задачі цілочислового програмування (ЗЦЛП)	\|	Метод гілок і границь

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.