Математическая модель транспортной задачи: F = ∑∑cijxij, (1) при условиях: ∑xij = ai, i = 1,2, , m, (2) ∑xij = bj, j = 1,2, , n, (3) Стоимость доставки единицы груза из

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

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

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 51 + 16 + 37 + 26 = 130
∑b = 30 + 40 + 50 + 10 = 130
Занесем исходные данные в распределительную таблицу.

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

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

					Запасы
	2[30]	1[21]
		3[16]
		2[3]	3[34]
			5[16]	2[10]
Потребности

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

	v1=2	v2=1	v3=2	v4=-1
u1=0	2[30]	1[21]
u2=2		3[16]
u3=1		2[3]	3[34]
u4=3			5[16]	2[10]

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

					Запасы
	2[30]	1[21][-]		5[+]
		3[16]
		2[3][+]	3[34][-]
			5[16][+]	2[10][-]
Потребности

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

					Запасы
	2[30]	1[11]		5[10]
		3[16]
		2[13]	3[24]
			5[26]
Потребности

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

	v1=2	v2=1	v3=2	v4=5
u1=0	2[30]	1[11]		5[10]
u2=2		3[16]
u3=1		2[13]	3[24]
u4=3			5[26]

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

					Запасы
	2[30][-]	1[11][+]		5[10]
		3[16]
	5[+]	2[13][-]	3[24]
			5[26]
Потребности

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

					Запасы
	2[17]	1[24]		5[10]
		3[16]
	5[13]		3[24]
			5[26]
Потребности

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

	v1=2	v2=1	v3=0	v4=5
u1=0	2[17]	1[24]		5[10]
u2=2		3[16]
u3=3	5[13]		3[24]
u4=5			5[26]

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

					Запасы
	2[17][-]	1[24]	3[+]	5[10]
		3[16]
	5[13][+]		3[24][-]
			5[26]
Потребности

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

					Запасы
		1[24]	3[17]	5[10]
		3[16]
	5[30]		3[7]
			5[26]
Потребности

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

	v1=5	v2=1	v3=3	v4=5
u1=0		1[24]	3[17]	5[10]
u2=2		3[16]
u3=0	5[30]		3[7]
u4=2			5[26]

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

					Запасы
		1[24][-]	3[17][+]	5[10]
		3[16]
	5[30]		3[7]
		6[+]	5[26][-]
Потребности

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

					Запасы
			3[41]	5[10]
		3[16]
	5[30]		3[7]
		6[24]	5[2]
Потребности

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

	v1=5	v2=4	v3=3	v4=5
u1=0			3[41]	5[10]
u2=-1		3[16]
u3=0	5[30]		3[7]
u4=2		6[24]	5[2]

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

					Запасы
			3[41]	5[10]
		3[16][-]	4[+]
	5[30]		3[7]
		6[24][+]	5[2][-]
Потребности

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

					Запасы
			3[41]	5[10]
		3[14]	4[2]
	5[30]		3[7]
		6[26]
Потребности

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

	v1=5	v2=2	v3=3	v4=5
u1=0			3[41]	5[10]
u2=1		3[14]	4[2]
u3=0	5[30]		3[7]
u4=4		6[26]

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

					Запасы
			3[41][+]	5[10][-]
		3[14]	4[2]
	5[30]		3[7][-]	6[+]
		6[26]
Потребности

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

					Запасы
			3[48]	5[3]
		3[14]	4[2]
	5[30]			6[7]
		6[26]
Потребности

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

	v1=4	v2=2	v3=3	v4=5
u1=0			3[48]	5[3]
u2=1		3[14]	4[2]
u3=1	5[30]			6[7]
u4=4		6[26]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.
Максимальная прибыль составит:
F(x) = 3*48 + 5*3 + 3*14 + 4*2 + 5*30 + 6*7 + 6*26 = 557

Дата добавления: 2015-10-21