Page 105 - 6197

2 * * 3
*
5
Із таблиці 2.6 випливає, що   14Z x  , x  , x  1 .
7 1 2 7
 
Не дивлячись на те, що отримане значення max : Z x
перевищує нижню межу, подальше розгалуження здійснювати
 
не доцільно, оскільки різниця max : Z x -14 менша одиниці і
всі коефіцієнти цільової функції - цілі числа. Таким чином,
ребро, що виходить із вершини 4, у кращому випадку приведе
до нового цілочислового розв’язку, у якому   14Z x *  .
3
Перейдемо до вершини 5 (рис. 2.3), для якої x  і, яка є
2
результатом розгалуженням вершини 1. Таке розгалуження
приводить до такої підзадачі:
max : Z   2x  x  3x ,
1
2
5x  7x  35,
1 2
4x  9x  36 ,
1 2
0
0
x  3, x  , x  .
2 1 2
Оскільки підзадача вміщує обмеження «не менше» ( x  )
3
2
для її розв’язування застосуємо метод штрафних функцій.
Задачу подамо у канонічній формі
min : R   x  R  2x  3x 2  Mw 1 ,
1
0
5x  7x  x  35,
1 2 3
4x  9x  x  36,
1 2 4
x  x  w  3,
2 5 1
x  0 , x  , x  , x  , x  , w  .
0
0
0
0
0
1 2 3 4 5 1
Із цільової функції виключаємо штучну змінну w . У
1
результаті отримуємо підзадачу,
min : R   3x  M  2x  3 M x  2  Mx 5  ,
1
5x  7x  x  35,
1 2 3
105