Page 85 - 6197

Враховуючи ту обставину, що ліва частина останньої
нерівності повинна приймати лише цілочислові значення, то
необхідна умова її цілочисельності буде такою:
i 
a

0
     x  . (2.11)
ij
j
j T
Нерівність (2.11) утворює додаткове обмеження Гоморі та
відтинає знайдений оптимальний не цілочисловий розв’язок
задачі (2.2) – (2.5) і не відтинає жодного цілочислового плану
задачі.
Обмеження (2.11) перепишемо у вигляді рівняння
i 
w  q x  , (2.12)
q
i
ij
j
j T
 
a
де q    , q   ;
ij ij i i
w - невід’ємна надлишкова змінна, яка за визначенням
i
повинна приймати цілі значення.
Таке обмеження-рівність визначає відтинання Гоморі для
цілком цілочислової задачі. Оскільки у рівнянні (2.12) x
j
небазисні змінні, то прирівнявши їх до нуля, отримуємо
q
w   , тобто дана компонента розв’язку не є допустимою.
i i
Це означає, що не цілочисловий план не задовольняє нове
обмеження, а будь-який цілочисловий план йому задовольняє.
Якщо після чергової ітерації виявиться, що в
оптимальному плані задачі (2.2) – (2.5) є декілька не цілих
змінних, то для побудови наступної відтинаючої
гіперплощини потрібно вибрати рядок, який вміщує вільний
член з найбільшою дробовою частиною.
Приклад 2.1. Розв’яжемо задачу цілочислового
програмування:
максимізувати   4Z x  x  5x  x
1 2 3
за умови
3x  2x  10,
1 2

85