Page 34 - 6449

Дробовою частиною числа називають різницю між числом і його
цілою частиною. Дробову частину числа називають f[x] :

f  .10 3  10  3 . 10  3 . 0 ;   03.0f  3 .  0  3 . 0 ;  7f  3 .  7  3 . 7   3 . 7  8  7 . 0
Дробова частина числа має ряд властивостей, серед яких
використаємо лише дві: (f a  b )  a ( f ) ) b ( f , f n ( )  nf a ( ), де n – ціле
додатнє число.
На основі вказаних двох властивостей було встановлено нерівність
Гоморі: якщо
 n  j 1 a ij x j  i , b (1.37)

а x – ціле число, то
j
 n  j 1 x j f ( a )  f ( b ). (1.38)
ij
i
Рівняння (1.37) представляє собою одне з обмежень ОДР ЗЛП, а
нерівність Гоморі (1.38) дозволяє встановити додаткове обмеження в
систему обмежень ЗЛП, яке дозволяє відсікати від ОДР деяку множину ,
що не містить цілочисельні точки.
Алгоритм методу Гоморі розв’язування задач цілочисельного
програмування є таким: нехай потрібно розв’язати задачу цілочисельного
програмування:
min
z  xc c x c x ...c x  (1.39)
1 1 2 2 3 3 1n n
max
при умовах:
a 11 x 1  a 12 x 2  ...  a n 1 x n  b 1

 a 21 x 1  a 22 x 2  ...  a 2 n x n  b2
 (1.40)
 .......... .......... .......... .......... .......... .......... .
 a x  a x  ...  a x  b
 m1 1 m2 2 mn 1 n m
x  0 , x – цілі.
i i
Спочатку знаходимо розв’язок задачі звичайним симплекс-
методом. Якщо знайдений оптимальний розв’язок є цілочисельним, то
задача вважається розв’язаною. Зауважимо, що в системі обмежень (1.40)
умова цілочиселності може накладатися не на всі, а лише на деякі
невідомі, в цьому випадку задача вважається розв’язаною, якщо цілі
значення є в потрібних невідомих – інші невідомі можуть бути і
дробовими.
Якщо ж в оптимальному розв’язку не всі потрібні змінні є
цілочисельними, здійснюється наступна процедура: в симплекс таблиці,
яка відповідає оптимальному розв’язку задачі, знаходимо рівняння-
обмеження з найбільшою дробовою частиною. До цього рівняння
застосовуємо нерівність Гоморі, після чого додаємо цю нерівність до
системи обмежень задачі і знову розв’язуємо задачу симплекс-методом. За
скінченну кількість кроків вдається знайти розв’язок задачі
цілочисельного програмування або встановити його відсутність – в такому

34