Page 107 - 6197

розв’язування якої здійснюємо за симплекс-таблицею (табл.
2.7). Безпосередньо із таблиці 2.7 отримуємо оптимальний
1 1
*
*
3
розв’язок підзадачі:   13Z x *  , x  2 , x  . Знайдене
1
2
2 4
*
Z x
значення   менше нижньої межі (=14) . Тому вершина 4
3
у подальшому не розглядається і пошук вздовж ребра x 
2
слід припинити.
Слід відмітити, що неможливо наперед спрогнозувати, що
вибір вершини 2 ( x  ) є вигіднішим, ніж вибір вершини 5
2
2
( x  ). Можна переконатись, що початковий вибір вершини
3
2
5 зумовив би необхідність розв’язання дев’яти підзадач, тоді
як вибір вершини 2 - тільки п’яти підзадач.
Розглянутий приклад наглядно демонструє основний
недолік методу гілок і меж, який полягає у відсутності даних
про кількість підзадач, яні необхідно розв’язати для
знаходження і верифікації цілочислового оптимуму задачі. Це
приводить до збільшення часу обчислень.
Таким чином, оптимальний розв’язок задачі -   14Z x *  ,
*
*
2
x  4, x  .
1 2
Не дивлячись на відмічений недолік методу гілок і меж, на
теперішній час цей метод є найбільш надійним засобом
розв’язання цілочислових задач, які зустрічаються у
практичних застосуваннях. Це не означає, що будь-яка задача
цілочислового програмування може бути розв’язана за
допомогою цього методу.
У тому випадку, коли вникає проблема вибору між
методом відтинань та методом гілок і меж у більшості
випадків вирішується на користь останнього.

107