Page 78 - 6197

2 ДИСКРЕТНЕ ПРОГРАМУВАННЯ

2.1 Постановка задачі дискретного програмування
Особливістю задач дискретного програмування є те, що
змінні, які зумовлюють мінімум деякій цільовій функції
приймають лише цілочислові значення.
У загальному випадку задача дискретного програмування
формулюється у такий спосіб:
  
R x * min : R   x , (2.1)
x X
де X - скінчена множина допустимих розв’язків, яка
задовольняє умові 1 X  N ; X - число елементів множини

X .
  i
Множина X вміщує кінцеве число елементів x , i  1,N ,
які можна пронумерувати і обчислити відповідні значення
 
R x   i , i  1,N і в такий спосіб знайти найменше значення
R
цільової функції   x . Такий метод повного перебору при
великих значеннях N неможливо реалізувати на ЕОМ будь-
якої потужності.
Як частковий випадок задачі (2.1) можна навести задачу, у
якій цільова функція   x лінійна, а множина X утворена
R
лінійними обмеженням задачі. Така задача формулюється у
такий спосіб:
мінімізувати функцію
n
R   x   c x (2.2)
j
j
j 1 
при обмеженнях
n
 a x  b , (2.3)
j
ij
j
j 1 
x  0 , j  1,n (2.4)
j

78