Page 169 - 5637

Таблиця 8.2 Перетворення симплекс-таблиця

** * 1 − − … − … −

̃ … …

̃ … …

… … … … … … … …

̃ … …

… … … … … … … …

̃ … …

̃ ̃ ̃ … ̃ … ̃

Елементи табл. 8.2 розраховують за формулами
1

= , = , = , ≠ ,

= − , ≠ , ̃ = − ;

= , ≠ , ≠ ;

= , ≠ ;

̃ = , ≠ ,

з наступною заміною місцями змінних і .

Нехай в результаті послідовних ітерацій по симплекс-методу знайдена
оптимальна точка і отримана симплекс-таблиця типу табл. 8.2, але з коефіцієнтами,
відповідними оптимальному вирішенню. Оптимальне рішення, знаходиться зі стовпця
вільних членів , … , або дорівнює нулю, залежно від того, залежимо чи компонент

чи ні.
Далі перевіряємо знайдену оптимальну точку на цілочисельності. З цією метою
переглядаємо всі ( = 1, … , ). Якщо всі – цілі, то задача вирішена. Якщо ж серед

чисел є дробове, наприклад , то у оптимального рішення є хоча б одна неціле

координата. У цьому випадку перевіряється наявність цілих точок в допустимому
многограннике. Якщо в якій-небудь рядку з дробовим членом і всі інші коефіцієнти

виявляться цілими, то в допустимому многограннику немає цілих точок, і завдання

цілочисельного програмування не має рішення. В іншому випадку складаємо