Page 95 - 6197

виконанні умови     множну G виключають із
  k
G 
R x

r
r
подальшого процесу розв’язання задачі.
Ознака оптимальності. Допустимо, що у процесі
  0
розв’язання задачі початкова множина G розбита на G ,
i
*
i  1,s множин. Серед них виділимо множину G . Тоді план
q
*
*
*
x буде оптимальним, якщо           , i  1,s ,
G
G
R x
i
q
q
i  .
2.3.3 Алгоритм розв’язання задачі цілочисельного
програмування
Розглядається задача (2.2) – (2.5), алгоритм розв’язання
*
якої ґрунтується на методі Ленда-Дойга . Він включає в себе
такі кроки.
St1. Знімаємо обмеження на цілочисельність змінних x ,
j
j  1,n і розв’язуємо задачу лінійного програмування (2.2) –
(2.4). Якщо отримана задача немає розв’язку, то і початкова
задача (2.2) – (2.5) також немає розв’язку. Допустимо, що для
задачі (2.2) – (2.4) існує оптимальний розв’язок
T
*
*
*
*
x ,x ,
*
x   1 2 ,x n  . Якщо виявиться, що змінні x , j  1,n -
j
цілі числа, то задача (2.2) – (2.5) розв’язана (кінець
алгоритму). Допустимо, що одна або декілька змінних не є
цілими числами. Вибираємо одну із них з номером j .
0
*
*
Позначимо через  x  цілу частину числа x . Тоді
 0 j  0 j
допустимий цілий розв’язок повинен задовольняти одному із
обмежень
x  x  *  або x  x  *   1. (2.13)
0 j  0 j  r  0 j 

*
Land A.H. An automatic method of solving discrete programming problems /
A. H Land, A. G. Doig // Econometrica. — 1960. — V. 28, № 3. — P. 497-
520.
95