Расстояние от полей до ферм, км

Поля	Фермы
1-я	2-я	3-я	4-я
1-е 2-е 3-е 4-е 5-е

Составить такой план перевозок, чтобы общие транспортные затраты были минимальными.

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

					Запасы





Потребности

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 600 + 800 + 1000 + 1200 + 400 = 4000
∑b = 800 + 1600 + 1000 + 600 = 4000
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.

					Запасы





Потребности

Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1
Для этого элемента запасы равны 1000, потребности 1600. Поскольку минимальным является 1000, то вычитаем его.
x₃₂ = min(1000,1600) = 1000.



x		x	x	1000 - 1000 = 0


	1600 - 1000 = 600

Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 1000. Поскольку минимальным является 600, то вычитаем его.
x₁₃ = min(600,1000) = 600.

x	x		x	600 - 600 = 0

x		x	x


		1000 - 600 = 400

Искомый элемент равен 2
Для этого элемента запасы равны 1200, потребности 600. Поскольку минимальным является 600, то вычитаем его.
x₄₂ = min(1200,600) = 600.

x	x		x
	x
x		x	x
				1200 - 600 = 600

	600 - 600 = 0

Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x₄₃ = min(600,400) = 400.

x	x		x
	x	x
x		x	x
				600 - 400 = 200

		400 - 400 = 0

Искомый элемент равен 4
Для этого элемента запасы равны 200, потребности 600. Поскольку минимальным является 200, то вычитаем его.
x₄₄ = min(200,600) = 200.

x	x		x
	x	x
x		x	x
x				200 - 200 = 0

			600 - 200 = 400

Искомый элемент равен 4
Для этого элемента запасы равны 400, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x₅₄ = min(400,400) = 400.

x	x		x
	x	x	x
x		x	x
x
x				400 - 400 = 0
			400 - 400 = 0

Искомый элемент равен 9
Для этого элемента запасы равны 800, потребности 800. Поскольку минимальным является 800, то вычитаем его.
x₂₁ = min(800,800) = 800.

x	x		x
	x	x	x	800 - 800 = 0
x		x	x
x
x
800 - 800 = 0

					Запасы
			2[600]
	9[800]
		1[1000]
		2[600]	2[400]	4[200]
				4[400]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*600 + 9*800 + 1*1000 + 2*600 + 2*400 + 4*200 + 4*400 = 13800
Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 1000. Поскольку минимальным является 600, то вычитаем его.
x₁₃ = min(600,1000) = 600.

x	x		x	600 - 600 = 0




		1000 - 600 = 400

Искомый элемент равен 1
Для этого элемента запасы равны 1000, потребности 1600. Поскольку минимальным является 1000, то вычитаем его.
x₃₂ = min(1000,1600) = 1000.

x	x		x

x		x	x	1000 - 1000 = 0


	1600 - 1000 = 600

x	x		x
	x
x		x	x
				1200 - 600 = 600

	600 - 600 = 0

x	x		x
	x	x
x		x	x
				600 - 400 = 200

		400 - 400 = 0

x	x		x
	x	x
x		x	x
x				200 - 200 = 0

			600 - 200 = 400

x	x		x
	x	x	x
x		x	x
x
x				400 - 400 = 0
			400 - 400 = 0

x	x		x
	x	x	x	800 - 800 = 0
x		x	x
x
x
800 - 800 = 0

					Запасы
			2[600]
	9[800]
		1[1000]
		2[600]	2[400]	4[200]
				4[400]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*600 + 9*800 + 1*1000 + 2*600 + 2*400 + 4*200 + 4*400 = 13800
Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 600. Поскольку минимальным является 600, то вычитаем его.
x₁₄ = min(600,600) = 600.

x	x	x		600 - 600 = 0
			x
			x
			x

			600 - 600 = 0

x	x	x
			x
x		x	x	1000 - 1000 = 0
			x

	1600 - 1000 = 600

x	x	x
	x		x
x		x	x
			x	1200 - 600 = 600

	600 - 600 = 0

Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 1000. Поскольку минимальным является 600, то вычитаем его.
x₄₃ = min(600,1000) = 600.

x	x	x
	x		x
x		x	x
x			x	600 - 600 = 0

		1000 - 600 = 400

Искомый элемент равен 3
Для этого элемента запасы равны 400, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x₅₃ = min(400,400) = 400.

x	x	x
	x	x	x
x		x	x
x			x
x				400 - 400 = 0
		400 - 400 = 0

x	x	x
	x	x	x	800 - 800 = 0
x		x	x
x			x
x
800 - 800 = 0

					Запасы
				2[600]
	9[800]
		1[1000]
		2[600]	2[600]
			3[400]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*600 + 9*800 + 1*1000 + 2*600 + 2*600 + 3*400 = 13000
Искомый элемент равен 2
Для этого элемента запасы равны 1200, потребности 1600. Поскольку минимальным является 1200, то вычитаем его.
x₄₂ = min(1200,1600) = 1200.




x		x	x	1200 - 1200 = 0

	1600 - 1200 = 400

Искомый элемент равен 1
Для этого элемента запасы равны 1000, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x₃₂ = min(1000,400) = 400.

	x
	x
				1000 - 400 = 600
x		x	x

	400 - 400 = 0

x	x		x	600 - 600 = 0
	x

x		x	x

		1000 - 600 = 400

x	x		x
	x	x
		x
x		x	x
x			x	400 - 400 = 0
		400 - 400 = 0

Искомый элемент равен 5
Для этого элемента запасы равны 600, потребности 600. Поскольку минимальным является 600, то вычитаем его.
x₃₄ = min(600,600) = 600.

x	x		x
	x	x	x
x		x		600 - 600 = 0
x		x	x
x			x
			600 - 600 = 0

x	x		x
	x	x	x	800 - 800 = 0
x		x
x		x	x
x			x
800 - 800 = 0

					Запасы
			2[600]
	9[800]
		1[400]		5[600]
		2[1200]
			3[400]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*600 + 9*800 + 1*400 + 5*600 + 2*1200 + 3*400 = 15400
Искомый элемент равен 2
Для этого элемента запасы равны 1200, потребности 1000. Поскольку минимальным является 1000, то вычитаем его.
x₄₃ = min(1200,1000) = 1000.

		x
		x
		x
				1200 - 1000 = 200

		1000 - 1000 = 0

		x
		x
x		x	x	1000 - 1000 = 0


	1600 - 1000 = 600

Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 600. Поскольку минимальным является 600, то вычитаем его.
x₁₄ = min(600,600) = 600.

x	x	x		600 - 600 = 0
		x	x
x		x	x
			x

			600 - 600 = 0

Искомый элемент равен 2
Для этого элемента запасы равны 200, потребности 600. Поскольку минимальным является 200, то вычитаем его.
x₄₂ = min(200,600) = 200.

x	x	x
		x	x
x		x	x
x			x	200 - 200 = 0

	600 - 200 = 400

Искомый элемент равен 4
Для этого элемента запасы равны 400, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x₅₂ = min(400,400) = 400.

x	x	x
	x	x	x
x		x	x
x			x
x				400 - 400 = 0
	400 - 400 = 0

x	x	x
	x	x	x	800 - 800 = 0
x		x	x
x			x
x
800 - 800 = 0

					Запасы
				2[600]
	9[800]
		1[1000]
		2[200]	2[1000]
		4[400]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*600 + 9*800 + 1*1000 + 2*200 + 2*1000 + 4*400 = 13400
Искомый элемент равен 3
Для этого элемента запасы равны 400, потребности 1000. Поскольку минимальным является 400, то вычитаем его.
x₅₃ = min(400,1000) = 400.





x	x		x	400 - 400 = 0
		1000 - 400 = 600



x		x	x	1000 - 1000 = 0

x	x		x
	1600 - 1000 = 600

Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 600. Поскольку минимальным является 600, то вычитаем его.
x₁₃ = min(600,600) = 600.

x	x		x	600 - 600 = 0
		x
x		x	x
		x
x	x		x
		600 - 600 = 0

x	x		x
	x	x
x		x	x
		x		1200 - 600 = 600
x	x		x
	600 - 600 = 0

Искомый элемент равен 4
Для этого элемента запасы равны 600, потребности 600. Поскольку минимальным является 600, то вычитаем его.
x₄₄ = min(600,600) = 600.

x	x		x
	x	x	x
x		x	x
x		x		600 - 600 = 0
x	x		x
			600 - 600 = 0

x	x		x
	x	x	x	800 - 800 = 0
x		x	x
x		x
x	x		x
800 - 800 = 0

					Запасы
			2[600]
	9[800]
		1[1000]
		2[600]		4[600]
			3[400]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*600 + 9*800 + 1*1000 + 2*600 + 4*600 + 3*400 = 14200
Искомый элемент равен 4
Для этого элемента запасы равны 800, потребности 1000. Поскольку минимальным является 800, то вычитаем его.
x₂₃ = min(800,1000) = 800.


x	x		x	800 - 800 = 0



		1000 - 800 = 200


x	x		x
x		x	x	1000 - 1000 = 0


	1600 - 1000 = 600

Искомый элемент равен 2
Для этого элемента запасы равны 600, потребности 200. Поскольку минимальным является 200, то вычитаем его.
x₁₃ = min(600,200) = 200.

				600 - 200 = 400
x	x		x
x		x	x
		x

		200 - 200 = 0

Искомый элемент равен 2
Для этого элемента запасы равны 400, потребности 600. Поскольку минимальным является 400, то вычитаем его.
x₁₄ = min(400,600) = 400.

x	x			400 - 400 = 0
x	x		x
x		x	x
		x

			600 - 400 = 200

x	x
x	x		x
x		x	x
		x		1200 - 600 = 600

	600 - 600 = 0

Искомый элемент равен 4
Для этого элемента запасы равны 600, потребности 200. Поскольку минимальным является 200, то вычитаем его.
x₄₄ = min(600,200) = 200.

x	x
x	x		x
x		x	x
		x		600 - 200 = 400

			200 - 200 = 0

Искомый элемент равен 5
Для этого элемента запасы равны 400, потребности 800. Поскольку минимальным является 400, то вычитаем его.
x₄₁ = min(400,800) = 400.

x	x
x	x		x
x		x	x
		x		400 - 400 = 0

800 - 400 = 400

Искомый элемент равен 6
Для этого элемента запасы равны 400, потребности 400. Поскольку минимальным является 400, то вычитаем его.
x₅₁ = min(400,400) = 400.

x	x
x	x		x
x		x	x
		x
				400 - 400 = 0
400 - 400 = 0

					Запасы
			2[200]	2[400]
			4[800]
		1[1000]
	5[400]	2[600]		4[200]
	6[400]
Потребности

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 2*200 + 2*400 + 4*800 + 1*1000 + 5*400 + 2*600 + 4*200 + 6*400 = 11800
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2
u₂ + v₃ = 4; 2 + u₂ = 4; u₂ = 2
u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2
u₄ + v₄ = 4; 2 + u₄ = 4; u₄ = 2
u₄ + v₁ = 5; 2 + v₁ = 5; v₁ = 3
u₅ + v₁ = 6; 3 + u₅ = 6; u₅ = 3
u₄ + v₂ = 2; 2 + v₂ = 2; v₂ = 0
u₃ + v₂ = 1; 0 + u₃ = 1; u₃ = 1

	v₁=3	v₂=0	v₃=2	v₄=2
u₁=0			2[200]	2[400]
u₂=2			4[800]
u₃=1		1[1000]
u₄=2	5[400]	2[600]		4[200]
u₅=3	6[400]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(4;3): 2 + 2 > 2; ∆₄₃ = 2 + 2 - 2 = 2
(5;3): 3 + 2 > 3; ∆₅₃ = 3 + 2 - 3 = 2
(5;4): 3 + 2 > 4; ∆₅₄ = 3 + 2 - 4 = 1
max(2,2,1) = 2
Выбираем максимальную оценку свободной клетки (4;3): 2
Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

					Запасы
			2[200][-]	2[400][+]
			4[800]
		1[1000]
	5[400]	2[600]	2[+]	4[200][-]
	6[400]
Потребности

Цикл приведен в таблице (4,3 → 4,4 → 1,4 → 1,3).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 200. Прибавляем 200 к объемам грузов, стоящих в плюсовых клетках и вычитаем 200 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

					Запасы
				2[600]
			4[800]
		1[1000]
	5[400]	2[600]	2[200]	4[0]
	6[400]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2
u₄ + v₄ = 4; 2 + u₄ = 4; u₄ = 2
u₄ + v₁ = 5; 2 + v₁ = 5; v₁ = 3
u₅ + v₁ = 6; 3 + u₅ = 6; u₅ = 3
u₄ + v₂ = 2; 2 + v₂ = 2; v₂ = 0
u₃ + v₂ = 1; 0 + u₃ = 1; u₃ = 1
u₄ + v₃ = 2; 2 + v₃ = 2; v₃ = 0
u₂ + v₃ = 4; 0 + u₂ = 4; u₂ = 4

	v₁=3	v₂=0	v₃=0	v₄=2
u₁=0				2[600]
u₂=4			4[800]
u₃=1		1[1000]
u₄=2	5[400]	2[600]	2[200]	4[0]
u₅=3	6[400]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(5;4): 3 + 2 > 4; ∆₅₄ = 3 + 2 - 4 = 1
Выбираем максимальную оценку свободной клетки (5;4): 4
Для этого в перспективную клетку (5;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

					Запасы
				2[600]
			4[800]
		1[1000]
	5[400][+]	2[600]	2[200]	4[0][-]
	6[400][-]			4[+]
Потребности

Цикл приведен в таблице (5,4 → 5,1 → 4,1 → 4,4).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 4) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

					Запасы
				2[600]
			4[800]
		1[1000]
	5[400]	2[600]	2[200]
	6[400]			4[0]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2
u₅ + v₄ = 4; 2 + u₅ = 4; u₅ = 2
u₅ + v₁ = 6; 2 + v₁ = 6; v₁ = 4
u₄ + v₁ = 5; 4 + u₄ = 5; u₄ = 1
u₄ + v₂ = 2; 1 + v₂ = 2; v₂ = 1
u₃ + v₂ = 1; 1 + u₃ = 1; u₃ = 0
u₄ + v₃ = 2; 1 + v₃ = 2; v₃ = 1
u₂ + v₃ = 4; 1 + u₂ = 4; u₂ = 3

	v₁=4	v₂=1	v₃=1	v₄=2
u₁=0				2[600]
u₂=3			4[800]
u₃=0		1[1000]
u₄=1	5[400]	2[600]	2[200]
u₅=2	6[400]			4[0]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.
Минимальные затраты составят:
F(x) = 2*600 + 4*800 + 1*1000 + 5*400 + 2*600 + 2*200 + 6*400 = 11400
Анализ оптимального плана.
Из 1-го склада необходимо весь груз направить в 4-й магазин
Из 2-го склада необходимо весь груз направить в 3-й магазин
Из 3-го склада необходимо весь груз направить в 2-й магазин
Из 4-го склада необходимо груз направить в 1-й магазин (400), в 2-й магазин (600), в 3-й магазин (200)
Из 5-го склада необходимо весь груз направить в 1-й магазин
Задача имеет множество оптимальных планов, поскольку оценка для (5;4) равна 0.

⇐ Предыдущая 12