Page 82 - 6197
P. 82
крайні точки цієї області – цілочислові. Тому будь-який
базисний оптимальний розв’язок модифікованої задачі
лінійного програмування має своїми компонентами цілі числа і
є оптимальним розв’язком початкової задачі лінійного
програмування.
Рисунок 2.1 – Випукла множина обмежень
Саме алгоритми цілочислового програмування реалізують
метод систематичного введення додаткових обмежень з
метою трансформації початкової області до випуклої
оболонки її цілочислових точок.
Як тільки це буде зроблено, можна розв’язувати
модифіковану задачу лінійного програмування будь-яким
методом розв’язання задач лінійного програмування, і
отриманий базисний розв’язок автоматично стає
цілочисловим.
2.3.1 Метод відтинання (метод Гоморі)
Метод Гоморі дає змогу звести розв’язання задачі (2.2) –
(2.5) до розв’язання послідовності задач лінійного
програмування, кожна із яких може бути розв’язана одним із
симплекс-методів.
82
