Транспортная задача.
Copyright © Semestr.RU

Математическая модель транспортной задачи:
F = ∑∑cijxij,    (1)
при условиях:
∑xij = ai,  i = 1,2,…, m,   (2)
∑xij = bj,  j = 1,2,…, n,   (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
	1	2	3	4	Запасы	
1	2	4	6	7	400	
2	6	2	7	1	300	
3	6	10	7	5	500	
Потребности	350	250	150	250		

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 400 + 300 + 500 = 1200
∑b = 350 + 250 + 150 + 250 = 1000
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 200 (1200—1000). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
	1	2	3	4	5	Запасы	
1	2	4	6	7	0	400	
2	6	2	7	1	0	300	
3	6	10	7	5	0	500	
Потребности	350	250	150	250	200		

Этап I. Поиск первого опорного плана.
1. Используя метод двойного предпочтения, построим первый опорный план транспортной задачи. В каждой строке находим минимальный элемент. Ставим напротив него знак V. Затем находим минимальный элемент каждого столбца. Ставим напротив него знак V.
Если таблица стоимостей велика, то перебор всех элементов затруднителен. В этом случае используют метод двойного предпочтения, суть которого заключается в следующем.
В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку VV.
В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки.
Затем распределяют перевозки по ячейкам, отмеченным знаком V. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.
Искомый элемент находится в клетке (2;4) и равен 1.
	1	2	3	4	5	
1	2[VV]	4	6[V]	7	0	
2	6	2[V]	7	1[VV]	0	
3	6	10	7	5[V]	0[V]	

Искомый элемент равен 1
Для этого элемента запасы равны 300, потребности 250. Поскольку минимальным является 250, то вычитаем его.
x24 = min(300,250) = 250.
2	4	6	x	0	400	
6	2	7	1	0	300 - 250 = 50	
6	10	7	x	0	500	
350	250	150	250 - 250 = 0	200	0	

Искомый элемент находится в клетке (2;2) и равен 2.
	1	2	3	4	5	
1	2[VV]	4	6[V]	7	0	
2	6	2[VV]	7	1	0	
3	6[V]	10	7	5	0[V]	

Искомый элемент равен 2
Для этого элемента запасы равны 50, потребности 250. Поскольку минимальным является 50, то вычитаем его.
x22 = min(50,250) = 50.
2	4	6	x	0	400	
x	2	x	1	x	50 - 50 = 0	
6	10	7	x	0	500	
350	250 - 50 = 200	150	0	200	0	

Искомый элемент находится в клетке (1;1) и равен 2.
	1	2	3	4	5	
1	2[VV]	4[V]	6[V]	7	0	
2	6	2	7	1	0	
3	6[V]	10	7	5	0[V]	

Искомый элемент равен 2
Для этого элемента запасы равны 400, потребности 350. Поскольку минимальным является 350, то вычитаем его.
x11 = min(400,350) = 350.
2	4	6	x	0	400 - 350 = 50	
x	2	x	1	x	0	
x	10	7	x	0	500	
350 - 350 = 0	200	150	0	200	0	

Искомый элемент находится в клетке (1;2) и равен 4.
	1	2	3	4	5	
1	2	4[VV]	6[V]	7	0	
2	6	2	7	1	0	
3	6	10	7[V]	5	0[V]	

Искомый элемент равен 4
Для этого элемента запасы равны 50, потребности 200. Поскольку минимальным является 50, то вычитаем его.
x12 = min(50,200) = 50.
2	4	x	x	x	50 - 50 = 0	
x	2	x	1	x	0	
x	10	7	x	0	500	
0	200 - 50 = 150	150	0	200	0	
Искомый элемент находится в клетке (3;5) и равен 0.
	1	2	3	4	5	
1	2	4	6	7	0	
2	6	2	7	1	0	
3	6	10[V]	7[V]	5	0[V]	

Искомый элемент равен 0
Для этого элемента запасы равны 500, потребности 200. Поскольку минимальным является 200, то вычитаем его.
x35 = min(500,200) = 200.
2	4	x	x	x	0	
x	2	x	1	x	0	
x	10	7	x	0	500 - 200 = 300	
0	150	150	0	200 - 200 = 0	0	

Искомый элемент находится в клетке (3;3) и равен 7.
	1	2	3	4	5	
1	2	4	6	7	0	
2	6	2	7	1	0	
3	6	10[V]	7[V]	5	0	

Искомый элемент равен 7
Для этого элемента запасы равны 300, потребности 150. Поскольку минимальным является 150, то вычитаем его.
x33 = min(300,150) = 150.
2	4	x	x	x	0	
x	2	x	1	x	0	
x	10	7	x	0	300 - 150 = 150	
0	150	150 - 150 = 0	0	0	0	

Искомый элемент находится в клетке (3;2) и равен 10.
	1	2	3	4	5	
1	2	4	6	7	0	
2	6	2	7	1	0	
3	6	10[VV]	7	5	0	

Искомый элемент равен 10
Для этого элемента запасы равны 150, потребности 150. Поскольку минимальным является 150, то вычитаем его.
x32 = min(150,150) = 150.
2	4	x	x	x	0	
x	2	x	1	x	0	
x	10	7	x	0	150 - 150 = 0	
0	150 - 150 = 0	0	0	0	0	

	1	2	3	4	5	Запасы	
1	2[350]	4[50]	6	7	0	400	
2	6	2[50]	7	1[250]	0	300	
3	6	10[150]	7[150]	5	0[200]	500	
Потребности	350	250	150	250	200		

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*350 + 4*50 + 2*50 + 1*250 + 10*150 + 7*150 + 0*200  = 3800
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 2; 0 + v1 = 2; v1 = 2
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u2 + v2 = 2; 4 + u2 = 2; u2 = -2
u2 + v4 = 1; -2 + v4 = 1; v4 = 3
u3 + v2 = 10; 4 + u3 = 10; u3 = 6
u3 + v3 = 7; 6 + v3 = 7; v3 = 1
u3 + v5 = 0; 6 + v5 = 0; v5 = -6
	v1=2	v2=4	v3=1	v4=3	v5=-6	
u1=0	2[350]	4[50]	6	7	0	
u2=-2	6	2[50]	7	1[250]	0	
u3=6	6	10[150]	7[150]	5	0[200]	

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
(3;1): 6 + 2 > 6; ∆31 = 6 + 2 - 6 = 2
(3;4): 6 + 3 > 5; ∆34 = 6 + 3 - 5 = 4
max(2,4) = 4
Выбираем максимальную оценку свободной клетки (3;4): 5
Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
	1	2	3	4	5	Запасы	
1	2[350]	4[50]	6	7	0	400	
2	6	2[50][+]	7	1[250][-]	0	300	
3	6	10[150][-]	7[150]	5[+]	0[200]	500	
Потребности	350	250	150	250	200		

Цикл приведен в таблице (3,4; 3,2; 2,2; 2,4; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 150. Прибавляем 150 к объемам грузов, стоящих в плюсовых клетках и вычитаем 150 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
	1	2	3	4	5	Запасы	
1	2[350]	4[50]	6	7	0	400	
2	6	2[200]	7	1[100]	0	300	
3	6	10	7[150]	5[150]	0[200]	500	
Потребности	350	250	150	250	200		

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
u1 + v1 = 2; 0 + v1 = 2; v1 = 2
u1 + v2 = 4; 0 + v2 = 4; v2 = 4
u2 + v2 = 2; 4 + u2 = 2; u2 = -2
u2 + v4 = 1; -2 + v4 = 1; v4 = 3
u3 + v4 = 5; 3 + u3 = 5; u3 = 2
u3 + v3 = 7; 2 + v3 = 7; v3 = 5
u3 + v5 = 0; 2 + v5 = 0; v5 = -2
	v1=2	v2=4	v3=5	v4=3	v5=-2	
u1=0	2[350]	4[50]	6	7	0	
u2=-2	6	2[200]	7	1[100]	0	
u3=2	6	10	7[150]	5[150]	0[200]	

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 2*350 + 4*50 + 2*200 + 1*100 + 7*150 + 5*150 + 0*200  = 3200

Решение было получено и оформлено с помощью сервиса:
Транспортная задача
Вместе с этой задачей решают также:
Универсальная транспортная задача
Задача коммивояжера
Задача о назначениях