Page 33 - 6449

– при модифікації області не втрачається жодної точки з цілочисельними
координатами.
Нехай ОДР задачі має певну кількість цілочисельних точок

x , x , x ... x Це завжди справедливо, якщо ОДР – замкнута область обмежена
1 2 3 n
множина. Розглянемо множину відрізків-точок, що визначаються
 
рівностями  :  xxx   x 1 (   ),   1;0
i j
Зовнішня границя цієї множини, очевидно є випуклою множиною,
всі вершини її мають цілочисельні координати, тому знайдені графічним
методом розв’язок ЗЛП з модифікованою таким чином ОДР буде
цілочисельним. Схематично такий розв’язок і модифікована область
зображені на рисунку 1.7
ABCDEF – реальна ОДР задачі;
A, B, C, D, E, F – модифікована область з цілочисельними
координатами.

Рисунок 1.8 – Пошук цілочисельного розв’язку задачі з двома
невідомими і замкнутою обмеженою ОДР

На рисунку 1.8 цілочисельні точки – це точки перетину клітинок,
нецілочисельний розв’язок – точка D , цілочисельний – точка D .
1
Заштрихована область – це множина, що відсікається від початкової ОДР.
Розглянутий випадок є обмежений у використанні спеціальними
вимогами, що накладаються на область допустимих значень. Більш
загальним методом розв’язування задачі цілочисельного програмування є
метод гоморі, який базується на понятті цілої та дробової частини числа.
Цілою частиною числа називають найбільше ціле число, яке менше
за вказане, ціла частина числа, як відомо, називається [x]:  .10 3  10 ;   02.0  ;
  7.3   4

33