Методическое пособие 577

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

Оптимальный план: F = 30*1+20*1+20*3+10*1+10*2 = = 140.

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

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

Таблица 15

Затем определяем потенциалы пунктов отправления и потенциалы пунктов назначения. Для этого составляем уравнения для занятых клеток таблицы:

U1 +V2 = 2, U1 +V4 = 1, U2 +V1 = 6;

U2 +V3 = 5, U3 +V1 = 3, U3 +V2 = 2.

Возьмем U1 = 0 и последовательно найдем значения остальных потенциалов. Получим

U1 = 0, U2 = 3, U3 = 0, V1 = 3, V2 = 2, V3 = 2, V4 = 1.

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

11 = 0 + 3 – 4 = −1, 13 = 0 + 2 – 3 = −1, 22 = 3 + 2 – 3 = 2,24 = 3 + 1 – 6 = −2, 33 = 0 + 2 – 6 = −4, 34 = 0 + 1 – 3 = −2.

40

Выбираем максимальную положительную оценку. Это

оценка 22 = 2. Следовательно, на следующем шаге будет заполняться клетка с индексом 22. Составим цикл пересчета для данной клетки и пометим его вершины последовательно знаками «+» и «–» (табл. 16).

Таблица 16

Определим величину перераспределения груза как минимальную из величин, стоящих в минусовых клетках. Это 40 единиц. Прибавляем данную величину к величинам перевозок, стоящим в клетках со знаком «+» и вычитаем ее из величин перевозок, стоящих в клетках со знаком «–» (табл. 17).

Таблица 17

Составляем систему уравнений для определения потенциалов и последовательно находим из нее значения всех потенциалов.

U1 +V2 = 2, U1 +V4 = 1, U2 +V1 = 6;

U2 +V2 = 3, U2 +V3 = 5, U3 +V1 = 3.

41

Тогда U1 = 0, U2 = 1, U3 = −2, V1 = 5, V2 = 2, V3 = 4, V4 = 1.

Пересчитываем оценки:

11 = 0 +5 – 4 =1, 13 =0 – 2 +3 = 1, 24 =1 +1 –6 = – 4,32 =–2+2 –2=–2, 33 =–2+4–6 =–4, 34 = −2+1–3=–4.

Имеем две максимальные положительные оценки

11= 13 =1. Для заполнения на следующем шаге целесообразно выбрать клетку с индексом 13, так как ей соответствует меньший тариф. Строим цикл пересчета для клетки 13 (табл. 18).

Таблица 18

Величина перераспределения груза равна 10. Перераспределяем груз (табл. 19).

Таблица 19

Находим потенциалы пунктов отправления иназначения:

U1 + V3 = 3, U1 + V4 = 1, U2 + V1 = 6,

U2 + V2 = 3, U2 + V3 = 5, U3 + V1 = 3.

42

U1 = 0, U2 = 2, U3 = −1, V1 = 4, V2 = 1, V3 = 3, V4 = 1.

Пересчитываем оценки:

11 =0+4–4=0, 12 =0+1–2=–1, 24 =2+1–6=–3,32 = –1 +1–2 = –2, 33 = –1+3– 6= –4, 34 = −1 + 1 – 3 = –3.

Все оценки неотрицательны. Следовательно, полученный план перевозок является оптимальным. Оптимальный план:

F = 10*3 + 70*1 +10*6 + 50*3 + 40*5 + 70*3 = 720.

КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 4

1.В чем заключаются основные особенности транспортной задачи?

2.Какие исходные данные необходимы для решения транспортной задачи?

3.Что такое открытая и закрытая транспортная задача?

4.Что определяют тарифы, заданные в условии?

5.К чему стремится значение целевой функции?

6.Как заполняется первоначальный опорный план?

7.В чем заключается метод потенциалов?

8.Как определяются потенциалы?

9.Как высчитываются оценки? Для каких клеток?

10.Как определяется целевая функция?

43

ГЛАВА 5. ЗАДАЧА КОММИВОЯЖЕРА

Одна из самых известных и важных задач транспортной логистики — задача коммивояжера. Также встречается название «задача о бродячем торговце». Суть задачи сводится к поиску оптимального, то есть кратчайшего пути, проходящего через некие пункты по одному разу. Например, задача коммивояжера может применяться для нахождения самого выгодного маршрута, позволяющего коммивояжеру объехать определенные города со своим товаром по одному разу и вернуться в исходную точку. Мерой выгодности маршрута будет минимальное время, проведенное в пути, минимальные расходы на дорогу или, в простейшем случае, минимальная длина пути. Кто и когда впервые начал исследовать задачу коммивояжера, неизвестно, но одним из первых предложил решение подобной проблемы выдающийся математик Уильям Гамильтон.

Для решения задачи коммивояжера методом ветвей

играниц необходимо выполнить следующий алгоритм:

построение матрицы с исходными данными;

нахождение минимума по строкам;

редукция строк;

нахождение минимума по столбцам;

редукция столбцов;

вычисление оценок нулевых клеток;

редукция матрицы;

если путь еще не найден, переходим к пункту 2, если найден — к пункту9;

вычисление итоговой длины пути и построение марш-

рута.

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок пути был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-го города к 1-му, от 2-го ко 2-муи т.п. в качестве отрезка маршрута.

44

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

Задача о нахождении кратчайшего пути в наше время является очень актуальной и находит широкое применение. Например, в туризме, являющимся важной отраслью экономики для любого города, страны — он приносит значительную долю дохода. Туристы тратят деньги на проживание, покупку сувениров, питание и, конечно же, на экскурсии, поэтому сейчас во многих городах туризм активно развивается. Создаются удобства: гостиницы, рестораны, кафе, и, конечно же, сами туристические маршруты. Их необходимо создавать с учетом занимаемого времени, охватываемых достопримечательностей, длины. Ведь вряд ли найдется человек, которому понравится, если его будут несколько часов водить по городу с экскурсией, которая при более рациональной организации заняла бы минут сорок. В связи с этим проложенный маршрут должен быть, прежде всего, кратчайшим. Таким образом, возникает задача — как обойти выбранные достопримечательности города по кратчайшему маршруту и вернуться в отправную точку. Такая задача, по сути, является задачей коммивояжера, для решения которой используется метод ветвей и границ. Все исследования

ирасчеты проведены в работе для Воронежской области.

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

Для удобства обозначим каждый санаторий цифрами: 1. Санаторий «Радон».

2. Санаторий им. Цюрупы.

3. Санаторий им. Горького.

4. Санаторий им. Дзержинского.

5. Сомовский санаторий.

45

6.Чертовицкий санаторий.

7.Графский санаторий.

Формируем матрицу расстояний по исходным данным

(табл. 20).

Таблица 20

Матрица исходных данных

Санаторий	1	2	3	4	5	6	7
1	M	29	110	120	120	115	130
2	31	M	100	110	99	100	120
3	115	130	M	30	21	25	57
4	110	100	24	M	20	3	66
5	110	110	24	45	M	20	47
6	120	97	30	5	18	M	67
7	140	160	60	57	40	58	M

Определяем минимум по каждой из строк (табл. 21), производим редукцию строк (табл. 22).

Таблица 21

Нахождение минимума по строкам

Санаторий	1	2	3	4	5	6	7	min
1	M	29	110	120	120	115	130	29
2	31	M	100	110	99	100	120	31
3	115	130	M	30	21	25	57	21
4	110	100	24	M	20	3	66	3
5	110	110	24	45	M	20	47	20
6	120	97	30	5	18	M	67	5
7	140	160	60	57	40	58	M	40

46

Таблица 22

Редукция строк

Санаторий	1	2	3	4	5	6	7	min
1	M	0	81	91	91	86	101	29
2	0	M	69	79	68	69	89	31
3	94	109	M	9	0	4	36	21
4	107	97	21	M	17	0	63	3
5	90	90	4	25	M	0	27	20
6	115	92	25	0	13	M	62	5
7	100	120	20	17	0	18	M	40

Определяем минимум по каждому из столбцов (табл. 23), производим редукцию столбцов (табл. 24). После этого определим оценки (табл. 25) для нулевых ячеек (сумма минимума по строке и минимума по столбцу, в котором находится нулевая ячейка, не считая самой ячейки). Максимальная оценка соответствует ячейке 1-2. Таким образом, мы нашли первый участок маршрута. Вычеркиваем первый столбец и вторую строку, а в ячейке 2-1 ставим М — бесконечность (табл. 26), чтобы не было возможным выбрать обратный маршрут.

Таблица 23

Нахождение минимума по столбцам

Санаторий	1	2	3	4	5	6	7
1	M	0	81	91	91	86	101
2	0	M	69	79	68	69	89
3	94	109	M	9	0	4	36
4	107	97	21	M	17	0	63
5	90	90	4	25	M	0	27
6	115	92	25	0	13	M	62
7	100	120	20	17	0	18	M
min	0	0	4	0	0	0	27

47

					Редукция столбцов														Таблица 24
	Санаторий			1			2			3		4	5			6			7
		1			M		0			77		91	91			86			74
		2		0			M			65		79	68			69			62
		3		94			109			M		9	0			4			9
		4		107			97			17		M	17			0			36
		5		90			90			0		25		M		0			0
		6		115			92			21		0	13			M			35
		7		100			120			16		17	0			18			M
	min			0			0			4		0	0			0			27
					Вычисление оценок														Таблица 25
Санаторий			1		2				3			4		5				6			7
1			M		0 [164]				77			91		91				86			74
2			0 [152]		M				65			79		68				69			62
3			94		109				M			9		0 [4]				4			9
4			107		97				17			M		17				0 [17]			36
5			90		90			0 [16]				25		M				0 [0]			0 [9]
6			115		92				21			0 [22]		13					M		35
7			100		120				16			17		0 [16]				18			M

Таблица 26

Редукция матрицы

Санаторий	1	3	4	5	6	7
2	M	65	79	68	69	62
3	94	M	9	0	4	9
4	107	17	M	17	0	36
5	90	0	25	M	0	0
6	115	21	0	13	M	35
7	100	16	17	0	18	M

48

Находим минимум по строкам (табл. 27), проводим редукцию строк (табл. 28), определяем минимум по столбцам (табл. 29) и выполняем редукцию столбцов (табл. 30).

Таблица 27

Нахождение минимума по строкам

Санаторий	1	3	4	5	6	7	min
2	M	65	79	68	69	62	62
3	94	M	9	0	4	9	0
4	107	17	M	17	0	36	0
5	90	0	25	M	0	0	0
6	115	21	0	13	M	35	0
7	100	16	17	0	18	M	0

Таблица 28

Редукция строк

Санаторий	1	3	4	5	6	7	min
2	M	3	17	6	7	0	62
3	94	M	9	0	4	9	0
4	107	17	M	17	0	36	0
5	90	0	25	M	0	0	0
6	115	21	0	13	M	35	0
7	100	16	17	0	18	M	0

Таблица 29

Нахождение минимума по столбцам

Санаторий	1	3	4	5	6	7
2	M	3	17	6	7	0
3	94	M	9	0	4	9
4	107	17	M	17	0	36
5	90	0	25	M	0	0
6	115	21	0	13	M	35
7	100	16	17	0	18	M
min	90	0	0	0	0	0

49