8.5. Алгоритм розв’язання частково цілочисельної задачі (другий переріз Гоморі)

Нехай xk - змінна, що може приймати тільки цілі значення. Розглянемо відповідний цій змінній рядок симплекс-таблиці, що містить оптимальний розв’язок задачі з послабленими обмеженнями. Цей ведучий рядок породжує рівність:

 xk=b k -

xk -[b k ]=fk - .

Для цілочисельної змінної xk має виконуватися одна з двох наступних нерівностей:

xk £b k або xk ³b k+1.

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

 £ [b k ]

 ³ fk (8.6)

  ³ [bk]+1

 £ fk-1

Помноживши обидві частини нерівності (8.6) на  < 0, матимемо:

 ³ fk (8.7)

Введемо нові позначення. Нехай J+- підмножина значень j, для яких  ³0; J- - підмножина з  <0. Представимо (8.6) і (8.7) у наступному вигляді:

 ³ fk (8.8)

Перетворимо (6.8) на рівність шляхом введення балансової (залишкової) змінної Sk:

Sk -  -  = - fk (8.9)

Рівняння (8.9) являє собою переріз Гоморі для частково цілочисельної задачі. Однак воно не враховує того факту, що частина базисних змінних  може бути підлегла умові цілочисельності. Запишемо рівняння більш ефективного перерізу, що враховує цілочисельність деяких  :

 , (8.10)

де =

Розглянемо задачу, відмінну від попередніх тим, що вимога цілочисельності в ній накладається лише на змінну x1. Симплексна таблиця з початковим недопустимим розв’язком цієї задачі наводиться