Page 139 - 6197

критерій розгалуження відповідних задач у процесі
розв’язування симетричної задачі комівояжера.
Таким чином, якщо у процесі розв’язання симетричної
задачі комівояжера отриманий цикл 1-дерева то відповідна
задача не підлягає розгалуженню і в подальшому вона не
розглядається.
Контрольні питання та завдання
1 Сформулюйте задачу цілочисловою програмування.
2 У яких випадках задача буде частково цілочисловою, а у
яких випадках – повністю цілочисловою?
3 Якими умовами характеризуються задачі, що мають
властивості регулярності?
4 Наведіть приклади задач цілочислового програмування.
5 Яка особливість методів розв’язування задач
цілочислового програмування?
6 Наведіть алгоритм розв’язання задач лінійного
цілочисельного програмування методом відтинання (методом
Гоморі).
7 Розв’язати задачу цілочислового лінійного
програмування
R
максимізувати   x  20x  10x  10x
1 2 3
при обмеженнях
2x  20x  4x  15,
1 2 3
6x  20x  4x  20 ,
1 2 3
x , x , x - невід’ємні цілі числа
1 2 3
методом відсікання.
8 Розкрийте суть методу меж і гілок.
9 Розв’яжіть задачу лінійного цілочислового
програмування
максимізувати   3R x  x  x  3x
1 2 3
при обмеженнях
 x  2x  x  4,
1 2 3

139