Транспортна задача

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

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

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

Следующий этап состоит из серии  итераций:

Первая итерация:

Фиксируем множество всех маршрутов. Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет  играть роль значения на этом множестве  оценочной функции: это число  равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через , то сумму констант приведения матрицы весов обозначим через . Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M₁;

Вторая итерация:

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

Сопоставим  множеству  следующую матрицу M_1,1: в матрице M₁ заменим на ∞ число в клетке (j, i). Затем в полученной матрице вычеркнем строку  i и столбец j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M_1,1.

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

 

 

 

2. Решение практической задачи

Почтовому ведомству США потребовалось  определить экономный маршрут доставки почтовых грузов до открытия зимней Олимпиады  в Солт-Лейк-Сити по городам: Сиэтл, Чикаго, Нью-Йорк, Мемфис, Хьюстон, Сан-Франциско, Солт-Лейк-Сити, Сент-Луис. Расстояния между городами представлены в виде матрицы:

Таблица 2.1 Исходные данные

lij	Сиэтл	Чикаго	Нью-Йорк	Мемфис	Хьюстон	Сан-Франциско	Солт-Лейк-Сити	Сент-Луис
Сиэтл	0	120	-	-	-	50	45	-
Чикаго	120	0	55	35	-	-	80	25
Нью-Йорк	-	55	0	60	-	-	-	-
Мемфис	-	35	60	0	75	-	-	30
Хьюстон	-	-	-	75	0	95	85	30
Сан-Франциско	50	-	-	-	95	0	40	-
Солт-Лейк-Сити	45	80	-	-	85	40	0	75
Сент-Луис	-	25	-	30	30	-	75	0

 

Постройте маршрут минимальной  длины.

Решение

Заменим нули на бесконечности и  обозначим города цифрами:

1. Сиэтл
2. Чикаго
3. Нью-Йорк
4. Мемфис
5. Хьюстон
6. Сан-Франциско
7. Солт-Лейк-Сити
8. Сент-Луис

Таким образом, исходная таблица  примет следующий вид:

Таблица 2.2 Преобразованная матрица

lij	1	2	3	4	5	6	7	8
1	∞	120	∞	∞	∞	50	45	∞
2	120	∞	55	35	∞	∞	80	25
3	∞	55	∞	60	∞	∞	∞	∞
4	∞	35	60	∞	75	∞	∞	30
5	∞	∞	∞	75	∞	95	85	30
6	50	∞	∞	∞	95	∞	40	∞
7	45	80	∞	∞	85	40	∞	75
8	∞	25	∞	30	30	∞	75	∞

 

Инициализация

Выберем произвольный допустимый маршрут, состоящий, например, из звеньев (1, 7), (7, 8), (8, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1).

Вычислим стоимость данного  маршрута:

,

то есть, цена маршрута оптимального маршрута не может превышать значения .

Первая итерация

Выполним редукцию строк; для этого  в каждой строке i определим минимальный элемент, и найденное значение c_i вычтем из элементов соответствующей строки:

 

Таблица 2.3 Редукция строк в первой итерации

lij	1	2	3	4	5	6	7	8	ci
1	∞	75	∞	∞	∞	5	0	∞	45
2	95	∞	30	10	∞	∞	55	0	25
3	∞	0	∞	5	∞	∞	∞	∞	55
4	∞	5	30	∞	45	∞	∞	0	30
5	∞	∞	∞	45	∞	65	55	0	30
6	10	∞	∞	∞	55	∞	0	∞	40
7	5	40	∞	∞	45	0	∞	35	40
8	∞	0	∞	5	5	∞	50	∞	30

 

В полученной таблице проведём редукцию столбцов. Для этого в каждой строке j определим минимальный элемент, и найденное значение q_i вычтем из элементов соответствующей строки:

Таблица 2.4 Редукция столбцов в первой итерации

lij	1	2	3	4	5	6	7	8	ci
1	∞	75	∞	∞	∞	5	0	∞	45
2	90	∞	0	5	∞	∞	55	0	25
3	∞	0	∞	5	∞	∞	∞	∞	55
4	∞	5	0	∞	40	∞	∞	0	30
5	∞	∞	∞	40	∞	65	55	0	30
6	5	∞	∞	∞	50	∞	0	∞	40
7	0	40	∞	∞	40	0	∞	35	40
8	∞	0	∞	0	0	∞	50	∞	30
qi	5	0	30	5	5	0	0	0	H=340

Проверка:

Если бы в каждой строке и каждом столбце было ровно по одному элементу, то эти элементы и  образовывали бы оптимальный маршрут, и оптимальная стоимость была бы равна H.

 

` Выберем звено, на котором будет базироваться ветвление.

Таблица 2.5 Редуцированная матрица  с ячейками под вторичные штрафы

lij	1	2	3	4	5	6	7	8	ci	Ai
1	∞	75	∞	∞	∞	5	0	∞	45	5
2	90	∞	0	5	∞	∞	55	0	25	5
3	∞	0	∞	5	∞	∞	∞	∞	55	5
4	∞	5	0	∞	40	∞	∞	0	30	5
5	∞	∞	∞	40	∞	65	55	0	30	30
6	5	∞	∞	∞	50	∞	0	∞	40	5
7	0	40	∞	∞	40	0	∞	35	40	35
8	∞	0	∞	0	0	∞	50	∞	30	30
qi	5	0	30	5	5	0	0	0	H=340	-
Bj	5	5	30	5	5	5	50	35	-	-