Page 83 - 6197

Алгоритм розв’язання задачі (2.2) – (2.5) такий.
Sp 1. Розв’язується задача (2.2) – (2.5) з відкинутими
умовами цілочисельності.
Sp 2. Отриманий оптимальний розв’язок (якщо він існує)
перевіряється на цілочисельність. Якщо всі змінні задачі (2.2)
– (2.5) цілі числа, то кінець алгоритму. У тому випадку, коли
хоча би одна із змінних не ціле число переходять до третього
кроку.
Sp 3. До обмежень початкової задачі долучаються нове
обмеження, яке має такі властивості:
 отриманий не цілочисловий план не задовольняє такому
новому обмеженню;
 будь-який цілочисловий план йому задовольняє
(рис.2.1).
Sp 4. Розв’язується задача лінійного програмування одним
із симплекс-методів з розширеною системою обмежень, яка
включає нове додаткове обмеження, що отримане на кроці Sp
3. Процес обчислень циклічно повторюється до отримання
цілочислового розв’язку задачі (2.2) – (2.5).
Допустимо, що розв’язана задача (2.2) – (2.5), у якій знята
умова цілочисельності. Розглянемо i -тий рядок кінцевої
симплекс-таблиці, якій відповідає неціле значення  базисної
i
змінної x Безпосередньо із симплекс-таблиці маємо
i
i 
x  a x  
ij
j
i
j T
Використовуючи останнє рівняння, виразимо змінну x
i
через небазисні змінні x :
j
i 
x    a x , (2.9)
i ij j
j T
де T - множина індексів j , які відповідають небазисним
змінним.

83