Page 97 - 6197

Алгоритм розв’язування задачі цілочислового
програмування методом гілок і меж покажемо на конкретному
прикладі.
Приклад 2.2. Максимізувати
Z   2x  x  3x
1
2
за умови
5x  7x  35,
1 2
4x  9x  36 ,
1 2
0
x  0 , x  - цілі числа.
1 2
Пом’якшуємо умови цлочисельності і розв’язуємо таку
задачу:
min : R   x  R  2x  3x 2  ,
0
1
5x  7x  x  35,
1 2 3
4x  9x  x  36,
1 2 4
x  0 , x  , x  , x  .
0
0
0
1 2 3 4
за допомогою симплекс-таблиці 2.3.
Оптимальний розв’язок задачі з пом’якшеними умовами:
8 * 13 * 6 * *
*
Z   14x  , x  3 , x  2 . Оскільки змінні x і x
1
2
2
1
17 17 17
приймають нецілі значення, то будь-яка із них може бути
вибрана такою, що породжує процес розгалуження.
Допустимо, що вибрана змінні x . Її вибір породжує дві
2
3
2
підзадачі, які визначаються умовами - x  і x  .
2 2
Отримані підзадачі вміщують всі допустимі цілочислові
рішення початкової задачі.
На наступному кроці здійснюємо вибір однієї із підзадач
x  2 або x  . Нехай це буде підзадача x  . Розв’язуємо
2
3
2 2 2
таку підзадачу лінійного програмування без вимоги
цілочисленності:
97