Решение транспортной задачи линейного программирования

Математическая модель транспортной задачи:
F = ∑∑c_ijx_ij, (1)
при условиях:
∑x_ij = a_i, i = 1,2,…, m, (2)
∑x_ij = b_j, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

					Запасы
Потребности

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 100 + 200 + 400 + 200 = 900
∑b = 100 + 200 + 200 + 300 = 800
Занесем исходные данные в распределительную таблицу.

						Запасы
Потребности

Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.

						Запасы
	1[100]
		2[200]
			3[200]	6[200]
				3[100]	0[100]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:

						Запасы
		3[100]
	5[100]	2[100]
			3[200]	6[200]
				3[100]	0[100]
Потребности

2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.
Строим новый план.
Значение целевой функции для этого опорного плана равно:

						Запасы
			4[100]
	5[100]	2[100]
		4[100]	3[100]	6[200]
				3[100]	0[100]
Потребности

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=8	v2=5	v3=4	v4=7	v5=4
u1=0			4[100]
u2=-3	5[100]	2[100]
u3=-1		4[100]	3[100]	6[200]
u4=-4				3[100]	0[100]

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

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

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

						Запасы
	1[100]
	5[0]	2[200]
		4[0]	3[200]	6[200]
				3[100]	0[100]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=-2	v3=-3	v4=0	v5=-3
u1=0	1[100]
u2=4	5[0]	2[200]
u3=6		4[0]	3[200]	6[200]
u4=3				3[100]	0[100]

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

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

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

						Запасы
	1[100]
	5[0]	2[200]
	4[0]		3[200]	6[200]
				3[100]	0[100]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=-2	v3=0	v4=3	v5=0
u1=0	1[100]
u2=4	5[0]	2[200]
u3=3	4[0]		3[200]	6[200]
u4=0				3[100]	0[100]

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

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

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

						Запасы
	1[100]
		2[200]			0[0]
	4[0]		3[200]	6[200]
				3[100]	0[100]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=2	v3=0	v4=3	v5=0
u1=0	1[100]
u2=0		2[200]			0[0]
u3=3	4[0]		3[200]	6[200]
u4=0				3[100]	0[100]

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

						Запасы
	1[100]
		2[200]			0[0]
	4[0]		3[200]	6[200][-]	0[+]
				3[100][+]	0[100][-]
Потребности

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

						Запасы
	1[100]
		2[200]			0[0]
	4[0]		3[200]	6[100]	0[100]
				3[200]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=1	v2=-1	v3=0	v4=3	v5=-3
u1=0	1[100]
u2=3		2[200]			0[0]
u3=3	4[0]		3[200]	6[100]	0[100]
u4=0				3[200]

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

						Запасы
	1[100][-]			1[+]
		2[200]			0[0]
	4[0][+]		3[200]	6[100][-]	0[100]
				3[200]
Потребности

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

						Запасы
				1[100]
		2[200]			0[0]
	4[100]		3[200]	6[0]	0[100]
				3[200]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=-1	v2=-3	v3=-2	v4=1	v5=-5
u1=0				1[100]
u2=5		2[200]			0[0]
u3=5	4[100]		3[200]	6[0]	0[100]
u4=2				3[200]

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

						Запасы
				1[100]
		2[200]	2[+]		0[0][-]
	4[100]		3[200][-]	6[0]	0[100][+]
				3[200]
Потребности

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

						Запасы
				1[100]
		2[200]	2[0]
	4[100]		3[200]	6[0]	0[100]
				3[200]
Потребности

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=-1	v2=-2	v3=-2	v4=1	v5=-5
u1=0				1[100]
u2=4		2[200]	2[0]
u3=5	4[100]		3[200]	6[0]	0[100]
u4=2				3[200]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.
Минимальные затраты составят:
F(x) = 1*100 + 2*200 + 4*100 + 3*200 + 0*100 + 3*200 = 2100

Решение транспортных задач в электронных таблицах