Стратегия управления доставкой груза на транспорте

Таблица 1.11 – Второй опорный план

Пункты отправления	Пункты назначения
	А (410)	В (560)	Д (250)	Е (315)	И (390)	Избыток вагонов
Г (100)	50	35	30			115
Ж (225)		15		30	40	85
Недостаток вагонов	50	50	30	30	40	200

 

L = (50·310 + 35·460 + 30·150 + 15·335 + 30·90 + 40·165) = 50425 ваг-км.

Осуществляем проверку:

U₁ + L₁₄ = 100 + 100 = 200 < 315 – условие не выполняется;

U₁ + L₁₅ = 100 + 290 = 390 ≥ 390 – условие выполняется;

U₂ + L₂₁ = 225 + 245 = 470 ≥ 410 – условие выполняется;

U₂ + L₂₃ = 225 + 275 = 500 ≥ 250 – условие выполняется.

Для улучшения плана (целевая  функция L = 50425 ваг-км) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, то есть разность потенциалов максимальная (ячейка с индексом 14). Будем использовать ячейку с индексом 14. Третий опорный план представим в таблице 1.12.

Таблица 1.12 – Третий опорный план

Пункты отправления	Пункты назначения
	А (410)	В (560)	Д (250)	Е (200)	И (390)	Избыток вагонов
Г (100)	50	5	30	30		115
Ж (225)		45			40	85
Недостаток вагонов	50	50	30	30	40	200

 

L=(50·310+5·460+30·150+30·100+45·335+40·165)=46975 ваг-км.

Осуществляем проверку:

U₁ + L₁₅ = 100 + 290 = 390 ≥ 390 – условие выполняется;

U₂ + L₂₁ = 225 + 245 = 470 ≥ 410 – условие выполняется;

U₂ + L₂₃ = 225 + 275 = 500 ≥ 250 – условие выполняется;

U₂ + L₂₄ = 225 + 90 = 315 ≥ 200 – условие выполняется.

Выполнив проверку по свободным ячейкам, видим, что условие  выполняется. Количество занятых клеток равно 6, что также удовлетворяет требованиям. Следовательно, данный план является оптимальным.

 

2 Определение оптимального замкнутого маршрута

2.1 Общие теоретические  положения

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

 

 

 

 

 

 

 

Рисунок 2.1 – Схема размещения транспортных узлов, посещаемых

коммивояжерами.

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

Дня решения этой задачи необходимо составить математическую модель. Введем обозначения: i и j – номера пунктов выезда и въезда, l_ij – расстояние от пункта i до пункта j. Из таблицы 2.1 видно, что l_ij в общем случае может быть не равно расстоянию в обратном направлении l_ij ≠ l_ji.

Таблица 2.1 – Расстояния между пунктами

Из пункта i	В пункт j
	1	2	3	4	5	6
1	l11	l12	l13	l14	l15	l16
2	l21	l22	l23	l24	l25	l26
3	l31	l32	l33	l34	l35	l36
4	l41	l42	l43	l44	l45	l46
5	l51	l52	l53	l54	l55	l56
6	l61	l62	l63	l64	l65	l66

 

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

_xij={

1,если коммивояжер  из пункта i переезжает в пункт j,

0, если не поедет,

где i,j - 1, 2, ..., n. Требуется минимизировать выражение:

                                                   (2.1)

при следующих ограничениях:

  

,

где U_i и U_j – произвольные вещественные значения.

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

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

• вычисление нижней границы (оценки);
• разбиение на подмножества, т. е. ветвление;
• пересчет оценок;
• нахождение решений;
• определение признака оптимальности;
• оценка точности приближенного решения.

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

Сущность метода ветвей и границ применительно к задаче коммивояжера состоит в следующем.

1. Обозначим через G⁰ множество всех циклов, среди которых отыскивается кратчайший цикл t^*: l(t^*)=min l(t). При этом под циклом будем понимать набор из n упорядоченных пар городов, образующих замкнутый маршрут, который проходит через каждый город только один раз:

t=[(i₁,i₂),(i₂,i₃),…,(i_n-1,i_n),(i_n,i₁)].

Длина цикла равна

                                                        (2.2)

2. Вычислим оценку  для множества G⁰.Для этого введем понятие приведенной матрицы и процесса приведения.

Пусть h_i=min_j С_ij, тогда C_ij'=С_ij-h_i³0 и l(t)= .

Пусть H_j=min_i C_ij', тогда C_ij''=C_ij'-H_j³0 и l(t)= .

Полученная  матрица С" называется приведенной. Она обладает тем свойством, что в каждой ее строке и столбце имеется по крайней мере один нуль. Процесс, позволяющий из неотрицательной матрицы С получить приведенную неотрицательную матрицу С", называется приведением. Сумма вычитаемых в процессе приведения элементов называется приводящими константами и обозначается h_Σ. Оптимальный план задачи о коммивояжере с матрицей С" является оптимальным и для задачи о коммивояжере с матрицей С. Длина цикла l(t) на приведенной матрице будет меньше длины цикла l(t) на исходной матрице на сумму приводящих констант: l(t)=l(t)+h_Σ.

Так как приведенная  матрица содержит только неотрицательные  элементы, то сумма приводящих констант может служить нижней границей длины цикла при исходной матрице С, т. е. является оценкой исходного множества G⁰: ξ(G⁰)=h_Σ.

3. Произведем ветвление  множества G⁰ на два непересекающихся подмножества G₁ и G₂:

• подмножество G₁ получается из множества G⁰ при добавлении следующего условия: из пункта r следует непосредственно идти в пункт s;
• подмножество G₂ получается из множества G⁰ при добавлении условия: из пункта r запрещается непосредственный переход в пункт s.

При этом пару городов (r, s) выбирают так, чтобы множество G₁ с наибольшей вероятностью содержало оптимальный цикл, а множество G₂ – не содержало. Следовательно, пара (r, s) выбирается из множества пар претендентов (i, j), которым соответствуют нулевые элементы матрицы С, то есть С_ij=0, таким образом, чтобы циклам, входящим в подмножество G₂, соответствовали как можно более длинные пути. Так как по определению подмножества G₂ путь по любому из этих циклов переходит из города r в некоторый промежуточный пункт j (j¹s), а в город s коммивояжер приезжает из некоторого пункта i (i¹r), длина этого пути будет не меньше чем

Θ(r, s)=

Поэтому необходимо выбрать пару (r, s) так, чтобы Θ(r, s) было максимально, т. е.

Θ(r,s)=                          (2.3)

при условии, что С_ij=0.

4. Выполним преобразование  матрицы расстояний при ветвлении  и пересчитаем оценки. Каждому подмножеству, полученному в результате ветвление, будет соответствовать своя приведенная матрица и своя оценка. Матрица С₂, соответствующая подмножеству G₂, получается из матрицы С в результате следующих преобразований:

• запрещается переезд из города r в город s: С_rs→¥;
• проводится процедура приведения матрицы. Оценка подмножества G₂ равна оценке исходного множества G⁰ и Θ(r, s):

ξ(G₂)=ξ(G⁰)+Θ(r, s).

Для построения матрицы  С₁ соответствующей подмножеству G₁ выполняются следующие преобразования матрицы С:

• вычеркивается строка r и столбец s из матрицы С, так как из каждого города можно выезжать только один раз и в каждый город можно въезжать только один раз;
• запрещается переезд из города s в город r (С_sr→¥), а также все другие переезды, которые приводят к образованию замкнутых подциклов;
• выполняется процесс приведения матрицы С.

Оценка подмножества G₁ равна оценке исходного множества G⁰ и сумме приводящих констант:

 ξ( G₁)=ξ( G⁰) + .

Для дальнейшего ветвления  на следующем шаге выбирается то из двух полученных подмножеств G₁ и G₂, которое имеет наименьшую оценку. Процесс построения и оценивания подмножеств продолжается до тех пор, пока не будет получена матрица размерности 2´2, которая содержит только две допустимые пары городов. Эти пары являются замыкающими для некоторого маршрута без петель.

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

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

2.2 Расчет оптимального замкнутого маршрута

 

Условие задачи. Имеется 6 городов, соединенных между собой дорогами так, что из любого транспортного узла можно проехать в любой другой пункт. Выезжая из одного пункта, коммивояжер должен побывать в других пунктах по одному разу и вернуться в исходный пункт. Поэтому маршрут коммивояжера образует замкнутый цикл без петель. Требуется найти такой маршрут, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы пройденное расстояние (время поездки) было минимальным. Расстояния между городами заданы матрицей C=(С_ij); i=1, 2, 3, 4, 5, 6; j=1, 2, 3, 4, 5, 6.