Page 12 - 6197

1 ЛІНІЙНЕ ПРОГРАМУВАННЯ

1.1 Постановка задачі лінійного програмування
Допустимо, що необхідно знайти мінімум (максимум)
функції
n
R   x   c x (1.1)
j
j
j 1 
при наявності обмежень на змінні x , j  1,n
j
n
 a x  b , i  1,k ,
j
i
ij
j 1 
n
 a x  , i   1,r , (1.2)
b
k
j
ij
i
j 1 
n
 a x  , i   1,m
b
r
i
j
ij
j 1 
x  0 , j  1,n ,
j
де a , b - коефіцієнти системи обмежень (1.2) – відомі
ij i
величини.
Додатково допускаємо, що b  , i  1,m . Якщо одне або
0
i
декілька значень b  , то помноживши відповідні обмеження
0
i
на (-1), доб’ємося виконання умови невід’ємності всіх
значення b . При цьому частина обмежень, що має умову «не
i
більше» перейде до групи обмежень з умовою «не менше» (і
навпаки).
Точка у n - вимірному просторі
T
x  x ,x , ,x n  , (1.3)
2
1
12