Метод ветвей и границ. Задача коммивояжера

Классическая задача коммивояжера состоит в следующем. Имеется n населенных пунктов, соединенных дорогами. Расстояния (или в другом варианте – стоимость проезда) между всеми пунктами заданы матрицей A=(a_ij). Если между пунктами i и j нет соединяющей их дороги, то a_ij=∞.

Требуется составить маршрут, проходящий через все пункты ровно по одному разу (с возвратом в исходную точку), имеющий минимально возможную длину (или, соответственно, маршрут с минимальной стоимостью проезда).

Для решения данной задачи методом ветвей и границ выберем следующий способ ветвления: будем выбирать одну из дорог (например, из пункта k в пункт m) и к одному из подмножеств отнесем все маршруты, проходящие через данную дорогу, а к другому – все маршруты, не использующие ее.

В первом случае (когда мы заявим, что во всех маршрутах будет присутствовать дуга (k,m)), удалим из матрицы А k-ю строку и m-й столбец, после чего остальные звенья маршрута будем искать по оставшимся элементам матрицы.

Во втором случае (когда мы заявим, что во всех маршрутах не будет использоваться дуга (k,m)), положим a_km = ∞, т.е. рассмотрим аналогичную исходной задачу, в которой дуги (k,m) просто нет.

Поскольку при ветвлении все задачи получаются однотипными исходной, то достаточно указать способ нахождения оценки для начальной задачи.

В k-й строке матрицы А указываются длины путей, выходящих из пункта k. В каждом из маршрутов мы используем ровно один из них. Поэтому, если мы вычтем из всех элементов строки число N, то мы получим другую задачу, в которой длины всех маршрутов уменьшатся ровно на N (по сравнению с такими же маршрутами в исходной задаче). То же самое касается и столбцов.

В итоге для вычисления оценки в начальной задаче необходимо:

1) в каждой строке найти минимум b(i) и вычесть его из всех элементов строки;

2) в каждом столбце получившейся матрицы найти минимум c(j) и вычесть его из всех элементов столбца;

3) сумма Z всех b(i) и c(j) дает значение оценки, которая показывает, на сколько мы уменьшили длины всех маршрутов.

28. Методы перебора вариантов. Метод вариаций.

Дискретная оптимизация занимается исследованием задач, в которых необходимо сделать оптимальный выбор из конечного числа возможных вариантов. Задачи, имеющие конечное множество допустимых планов, называют комбинаторными.

C теоретической точки зрения простейшим методом поиска экстремального значения в комбинаторных задачах является метод полного перебора всех вариантов. Применение компьютеров позволяет осуществлять перебор достаточно большого количества вариантов, однако существуют задачи, в которых такой метод не позволяет получить решение за приемлемое время. С другой стороны, в некоторых задачах представляет интерес сам алгоритм организации перебора.

Для преодоления этих трудностей разработаны различные методы, позволяющие теоретически обосновать отсутствие необходимости в рассмотрении большей части вариантов.

В качестве первого примера рассмотрим метод вариаций.

Пусть M – конечное множество, содержащее все допустимые планы задачи. Определим множество правил, согласно которым можно переходить от одного плана к другому. Каждый такой переход будем называть вариацией. Полный набор вариаций должен позволять за конечное число шагов переходить от любого начального плана к произвольно выбранному конечному плану. Суть метода вариаций состоит в следующем.

Пусть x₀ – план задачи, такой что для любого другого плана x* найдется последовательность вариаций x* → x_n → x_n-1 → … → x₁ → x₀, на которой целевая функция задачи монотонно убывает, то x₀ – точка минимума в данной задаче.

Проиллюстрируем работу этого метода на задаче минимизации штрафов при обслуживании заявок.

Рассмотрим n заявок, которые нужно обслужить на одном приборе (в одной точке обслуживания). Известно время T(i) обслуживания i-й заявки и c(i) – приоритет заявки (величина штрафа за единицу времени, в течение которого i-я заявка находится в очереди). Требуется найти порядок обслуживания заявок, при которой общий штраф будет минимальным.

Множество всех допустимых планов задачи состоит из множества всех перестановок {i₁, i₂, …, i_n} чисел от 1 до n. В качестве вариаций рассмотрим транспозиции – перестановки двух номеров, находящихся в списке рядом друг с другом. Как уже отмечалось в алгебре, поскольку из любой данной перестановки можно получить любую другую при помощи конечной серии транспозиций, основное требование к набору вариаций выполнено.

Для решения задачи рассмотрим произвольную последовательность расположения заявок i₁, i₂, …, i_n. и изучим, как на величину штрафа влияет одна транспозиция.

Поменяем местами заявки i_k и i_k+1. Время ожидания заявки i_k возрастет на T(i_k+1), время ожидания заявки i_k+1 уменьшится на T(i_k). Следовательно, штраф изменится на величину T(i_k+1) c(i_k) – T(i_k) c(i_k+1).

Если последовательность заявок является оптимальной, никакая транспозиция не может уменьшить штраф, т.е. T(i_k+1) c(i_k) – T(i_k) c(i_k+1) ≥ 0, откуда c(i_k) / T(i_k) ≥ c(i_k+1) / T(i_k+1). Таким образом, в оптимальной последовательности заявок выполняется условие:

c(i₁)/T(i₁) ≥ c(i₂)/T(i₂) ≥ … ≥ c(i_n)/T(i_n).

Нетрудно доказать, что условие (4.12) является не только необходимым, но и достаточным для оптимальности последовательности обслуживания заявок.

Задачей целочисленного программирования называется задача линейного программирования, в которой имеется дополнительное условие, требующее, чтобы часть переменных принимала только целые значения.

z=c^Tx→max
Ax =b, (2.4.1)x ≥ 0, x_i∈Z, i∈I.

Примером такой задачи может служить задача о рюкзаке, в которой все переменные должны быть целыми и имеется одно ограничение-равенство.

Для решения задачи (2.4.1) можно применять метод ветвей и границ.

1. Способ вычисления оценок. Для вычисления оценки в задаче (2.4.1) уберем условия целочисленности переменных (получится обычная задача линейного программирования). Поскольку число допустимых планов увеличится, следовательно, оптимальное значение целевой функции в полученной задаче будет оценкой сверху для целевой функции в задаче (2.4.1). Если при этом решение x* новой задачи будет иметь целочисленные координаты x*_i, i∈I, то этот же вектор будет и решением (2.4.1).

2. Способ ветвления. Пусть координата x*_J не является целой, C=[x*_J]≠x*_J. Все допустимые планы в задаче (2.4.1) можно разбить на две части по следующему признаку: одни планы удовлетворяют условию

x_J≤ С, (2.4.2)

другие – условию x_J≥ С+1(2.4.3)

Для получения оценок мы также будем решать задачи линейного программирования. При этом найденное на предыдущем шаге решение x* не является допустимым планом ни для одной из этих задач. Однако в каждой из них возможно применение двойственного симплекс-метода.

Поиск по сайту: