Пример решения задачи о дилижансе

Постановка задачі: Знайти найкоротший маршрут з кінцевого пункту в початковий, якщо відома матриця транспортних витрат (см. табл 46).

Таблиця 46. Матриця транспортних витрат

Алгоритм рішення:

f_n(s) – вартість, що відповідає стратегії min витрат для шляху від пункту s, якщо до кінцевого пункту залишилося n кроків.

j_n(s) - рішення, що дозволяє досягти f_n(s).

Розраховувати будемо, користуючись рекурентним співвідношенням:

f_n(s) =min (c_sj+ f_n-1(j)) по всем s и j на сети.

Рішенне:

Шаг 1

в Из		f	j

Шаг 2

в Из				f	j
	11+8	13+7
	12+8		9+6

Шаг 3

в Из				f	j
	11+19	7+15	12+8
	8+19	5+15	9+8
	10+19	10+15	6+8

Шаг 4

в Из				f	j
	7+20	5+17	9+14

Рисунок 19 Транспортная сеть

Ответ: F=22, кратчайший путь 1-3-7-10.

Варианты задачи 1

«Задача о дилижансе»

1. Построить сеть.

2. Ручной расчет.

Варианты:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

15.

16.

17.

18.

19.

20.

М етод ветвей и границ

К задачам целочисленного программирования относятся задачи комбинаторного вида, т.е. такие задачи в которых решение ищется на конечном множестве возможных значений переменных.

Например. Задача Коммивояжера (конечное число маршрутов (n!), задача о ранце (конечное число предметов), задача о максимальном потоке или кратчайшем пути в сетевых задачах (конечное число вершин графа).

Метод Гомори решения целочисленных задач линейного программирования не всегда дает удовлетворительные результаты, из-за слабой сходимости или вообще расходится из-за накопления ошибок вычислений. Другим методом, который вообще не связан с накоплением вычислительной погрешности, является метод ветвей и границ (МВиГ). МВиГ впервые был предложен Лендом и Дойгом в 1960 г., но получил широкое распространение в связи с применением этого метода в работе Литтла, Мурти, Суини и Кэрел в 1963 г., посвященной задаче о коммивояжере.

Идея метода состоит в следующем.

Рассмотрим задачу дискретного программирования:

требуется min ® Z=f(Х) (1)

при условии, что ХÎG (2)

где G некоторое конечное множество.

Функция f(Х) и конечное множество G произвольного вида.

В основе метода лежат построения, позволяющие в ряде случаев существенно уменьшить число перебора вариантов. Введем обозначение G⁰ = G. Пусть нам удалось каким-либо образом найти такое значение x(G⁰), для которого можно сказать с уверенностью, что выполняется условие

f(x) ³ x(G⁰), при xÎG⁰ (3)

т.е. какое бы xÎG⁰ мы не взяли, значение f(x) всегда будет ³ x(G⁰), т.е. x(G⁰) является нижней граню для Z. Значение x(G⁰) может и не достигаться на G⁰, но если оно достигается, т.е. существует Х* такой, что f(Х*)= x(G⁰), т.е. Х* – оптимальное решение (f(x) не может быть > x(G⁰), к.к. это нижняя грань, но если мы вышли на эту нижнюю грань оставаясь в G⁰ то задача решена).

Производим разбиение G⁰ на подмножества так, чтобы

, " i, j, i¹j (4)

Для каждого из полученных определяем нижнюю грань . Причем, если

, то x(G0) нижняя грань x на множестве Gⁱ устанавливается более точно чем на G0.

Определяем:

(5)

Если существует план Х* Î Þ f(x*)= , то Х* оптимальный план (существенным является не только то, что Х* Î , но и то, что Х* является планом (1)-(2)).

Если , , то множество считается перспективным и его разбивают аналогично G⁰ (4) на подмножества . Переобозначим все множества и на .

(6)

и переходим к (5) и т.д., до тех пор пока не будет найден оптимальный план. Здесь следует отметить тот факт, что в первую очередь ветвлению подвергаются только перспективные подмножества, при этом к ранее не перспективным можно вернуться на одном из последующих шагов, когда их оценка нижней грани будет £ оценки перспективного множества на этом шаге.

Пример. Дана сеть:

Требуется найти кратчайший путь из вершины 1 в 7, проходящий через вершины 4 или 5.

Планом задачи здесь является путь ведущий из вершины 1, через вершину 4 или 5 в вершину 7.

Шаг 1. Разбиваем множество всех путей ведущих из вершины 1 на 2 не пересекающихся подмножества:G¹ – множество всех путей проходящих из вершины 1 в вершину 2 и далее к вершине 7;G² – множество всех путей проходящих из вершины 1 в вершину 3 и далее к вершине 7.

В качестве оценки x возьмем длину ребер [1,2] и [1,3], т.к. это части пути, то длина полного пути всегда ³ xi.

		не проходят через 4 или 5

На третьем шаге получен путь [1,3,5,7], являющийся планом, т.е. ведущим из начальной вершины 1 в конечную – 7 и проходящий через вершину 5, но его оценка хуже двух других возможных маршрутов: x[1,3,2] = x[1,3,4] = 5 < f([1,3,5,7]) = 7, поэтому процесс продолжаем, ветвлением вершин [1,3,2] и [1,3,4].

На четвертом шаге получен план [1,3,4,7] и f(X) = 6 т.к. x(Gn)=6 и существует план с f(X)=6, то решение найдено.

Пути из всех остальных вершин с x=6 могут только увеличиваться, т.к. эти маршруты еще не являются планами.

МВиГ является универсальным методом решения комбинаторных задач. Сложность практического применения метода заключается в трудности нахождения способа ветвления множеств на подмножества и вычисления соответствующих оценок, которые зависят от специфики конкретной задачи.

Методом ветвей и границ решаются классические задачи «О коммивояжере» и «Задача Джонсона».