Теоретичні відомості

Тема: Метод Гоморі знаходження цілочисельного розв’язку задач ЛП.

Мета: Засвоїти метод відсікаючих площин (Гоморі), знаходження цілочисельного розв’язку.

Теоретичні відомості

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

де - ціла частина числа. Тоді додаткове обмеження формується

таким чином:

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

Умова задачі:

12 Следующая ⇒