Page 14 - 6416

Об’єднання напівплощин, які вміщують точки, що задовольняють обмеженням задачі
утворюють множину допустимих розв’язків задачі лінійного програмування (на рис. 6.1 – це
затемнена область).
Тепер знайдемо градієнт цільової функції R x   . За визначенням
  R   x 
 x   1  
 R   x   1     .
  R   x   
3
 
  x  2  
На рис. 6.1 показаний графічний образ градієнта функції. Це вектор, компоненти якого
(1; 3). Отриманий вектор показує напрямок зростання цільової функції.
Якщо цільовій функції послідовно присвоювати значення c , c ,, то на площині 0x x
1 2 1 2
отримаємо сімейство прямих, які будуть переміщатись у напрямку протилежному до вектора
 R   x , якщо c  c  , . Проведемо пряму x  3x  , яка проходить через точку
c
2
1
2
1
утворену перетином прямих x  6x  50 та 2x  x  23 і перпендикулярна вектору R x  
1 2 1 2
R
(рис. 6.1). До тих пір поки прямі   x  c перетинають область допустимих розв’язків є
i
*
можливість зменшення цільової функції. Існує гранична точка x , через яку проходить
*
пряма   c , після якої зменшення цільової функції неможливе без порушення
R x
opt
обмежень. Для задачі, що розв’язується, такою точкою буде точка перетину прямих
x  x  20 і x  4x  20.
1 2 1 2
Отже, оптимум задачі лінійного програмування знайдемо як розв’язок системи лінійних
алгебраїчних рівнянь
 x  6x  21,
1 2
4x  x  16.
1 2
21 6  1 21
16 1 75 4 16 100
*
*
Маємо x    3, x    4 .
1 2
 1 6 25  25 25
4 1
Знаходимо   3 4 3 15R x *     .
*
Таким чином отримали такий розв’язок задачі лінійного програмування: x  3 4;  і
R   15x *  .

6.2 Приклад розв’язання задачі лінійного програмування двоетапним методом

Задача 2
Задача лінійного програмування
min : R   x  x  3x ,
1
2
x  6x  50 ,
1 2
2x  x  23,
1 2
4x  x  16 ,
1 2
 x  6x  21,
1 2
x , x  .
0
1 2
вміщує обмеження двох типів «не більше» і «неменше». Тому будемо розв’язувати її за
допомогою двоетапного методу.
11