Page 168 - 5637

симплекс-методу рішення задачі (8.4), (8.5), у якій знято вимогу цілочисельності

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

завдання також буде знайдено. В іншому випадку вводиться додаткове лінійне

обмеження

+. . . + ≤ , (8.6)

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

рішення задачі цілочислового програмування. Потім знову з допомогою симплекс-

методу вирішується завдання лінійного програмування при додатковому обмеженні

(8.6), і так до тих пір, поки за кінцеве число кроків не буде отримано цілочисельне

рішення задачі лінійного програмування, а отже, шукане.

Наведемо систему (8.4), (8.5), до наступного еквівалентному увазі:

, … , ≥ 0,

= − − −. . . − ≥ 0, (8.7)

. . . . . . . . . . . . . . . . . . . . . . . . .
= − ≥ 0,
−. . . −

= − −. . . − , (8.8)

де потрібно вже максимізувати функцію . Всі умови (8.7), (8.8) записуються за
допомогою наступної симплекс-таблиці (табл. 8.1), де перший рядок * – рядок
незалежних змінних, а стовпець ** – стовпець залежних змінних.

Симплекс-метод [56, 67] складається з послідовного перебору вершин

допустимого багатогранника, що визначається нерівностями (8.7) в просторі . Це

проводиться за допомогою змін ролями відповідних незалежної і залежною

змінних і відповідної цієї операції трансформації табл. 8.1 в табл. 8.2.

Таблиця 8.1 Вихідна симплекс-таблиця

** * 1 − − … − … −

… …

… …

… … … … … … … …
… …

… … … … … … … …
… …

… …