Решение-цикл
Условие Сii=∞ принимается для того, чтобы исключить возможность появления в оптимальном решении значений Xii=I, не имеющих смысла.
Наилучшие результаты при решении поставленной задачи были получены при использовании метода ветвей и границ.
Существует несколько модификаций метода ветвей и границ. Здесь рассмотрим метод «задания маршрутов», так как для его применения нет необходимости решать предварительную задачу линейного программирования о назначениях. Для определения нижней оценки оптимального значения целевой функции применяется метод, основанный на том, что расстояние должно быть, по крайней мере, равно сумме Cij при Xij=1 плюс сумма наименьших Cij в остальных случаях.
Алгоритм определения оптимального цикла, реалиизующий метод задания маршрутов, имеет вид: Сформировать список задач и для каждой задачи из этого списка проделать следующие шаги.
Шаг 1.
Прекратить вычисления, если основной список пуст. В противном случае выбрать одну задачу и вычеркнуть ее из основного списка.
Шаг 2.
Определить нижнюю оценку целевой функции для любого цикла, порождаемого выбранной задачей. Если же нижняя оценка больше или равна X0t, то принять X0t+1 и вернуться к шагу 1. В противном случае перейти к шагу 3.
Шаг 3.
Если текущее решение определяет цикл, то зафиксировать его, принять X0t+1 равным соответствующему значению целевой функции и вернуться к шагу 1. В противном случае перейти к шагу 4.
Шаг 4.
При наличии возможности выбрать переменную Хhk, не входящую в текущее решение, такую, что Сhk<∞ при условии, что Хhk=1 не приводит к образованию подцикла на переменных, уже вошедших в решение. При таком выборе внести в основной список задач две задачи.
Рис. 3.17.
Каждую из этих задач принять идентичной задаче, выбранной на шаге 1, за исключением лишь того, что в одну из них ввести изменение Сhk=∞, а в другую – условие Хhk=1 и изменение Сkh=∞. Принять X0t+1= X0t и вернуться к шагу 1.
По приведенному алгоритму была составлена программа и проведен ряд экспериментов на электронно-вычислительной машине. Результаты экспериментов показали большую эффективность программы в смысле нахождения оптимального цикла, но при этом очень быстро возрастает время счета с увеличением размерности задачи.
На рис. 3.17 представлена траектория, сформированная с помощью этого алгоритма, для изображенной детали.