Page 81 - 6197

привалів різних типів, щоб прибуток від реалізації приладів
був максимальним.
Формалізований запис задачі буде таким:
n
max : R   x   c x ,
j
j
j 1
n
 a x  b , i  1,m ,
ij
i
j
j 1 
x  0 , x - цілі числа, j  1,n .
j j

2.3 Методи розв’язування задач дискретного
(цілочислового) програмування
Будемо розв’язувати задачу (2.2) – (2.5) лінійного
цілочислового програмування.
Якщо зняти умову цілочисельності (2.5), то обмеження
(2.3) визначають випуклу множину в n - вимірному просторі.
Приклад такої множини для двовимірного простору
показаний на рисунку 2.1. Вузли цілочислової решітки
відмічені крапками. Вони розміщені всередині області OABCD
і є допустимим розв’язком задачі цілочислового
програмування. Оптимальний розв’язок задачі лінійного
програмування завжди розміщений на межі області розв’язків.
Для випадку, який показаний на рисунку 2.1, ні одна із
граничних точок множини OABCD не є допустимою, оскільки
жодна із них не цілочислова.
Допустимо, що область OABCD допустимих рішень
звужена до випуклої оболонки OEFGH допустимих цілих
точок всередині допустимої області (рис. 2.1). Область
OEFGH можна розглядати як область допустимих розв’язків
деякої іншої задачі лінійного програмування.
Така нова область OEFGH володіє двома важливими
властивостями: по-перше, вона вміщує всі допустимі точки
початкової задачі лінійного програмування; по-друге, всі

81