Второе приближение.

Транспортная задача.

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

					Запасы



Потребности

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 80 + 170 + 180 = 430

∑b = 120 + 90 + 150 + 70 = 430

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в таблицу.

1. Используем метод северо-западного угла сформируем первый план перевозок.

					Запасы
	2 80
	6 40	1 90	5 40
			4 110	0 70
Потребности

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

2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, таблица невырожденным.

Затраты : F(x) = 2*80 + 6*40 + 1*90 + 5*40 + 4*110 + 0*70 = 1130

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

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₂ + v₁ = 6; 2 + u₂ = 6; u₂ = 4

u₂ + v₂ = 1; 4 + v₂ = 1; v₂ = -3

u₂ + v₃ = 5; 4 + v₃ = 5; v₃ = 1

u₃ + v₃ = 4; 1 + u₃ = 4; u₃ = 3

u₃ + v₄ = 0; 3 + v₄ = 0; v₄ = -3

	v₁=2	v₂=-3	v₃=1	v₄=-3
u₁=0	2 80
u₂=4	6 40	1 90	5 40
u₃=3			4 110	0 70

Сформированный план перевозок не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(2;4): 4 + -3 > 0; ∆₂₄ = 4 + -3 - 0 = 1

(3;1): 3 + 2 > 1; ∆₃₁ = 3 + 2 - 1 = 4

max(1,4) = 4

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных«-», «+», «-».

					Запасы
	2 80
	6 40 -	1 90	5 40 +
	1 +		4 110 -	0 70
Потребности

Цикл приведен в таблице (3,1 → 3,3 → 2,3 → 2,1).

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

Второе приближение.

					Запасы
	2 80
		1 90	5 80
	1 40		4 70	0 70
Потребности

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₃ = 4; -1 + v₃ = 4; v₃ = 5

u₂ + v₃ = 5; 5 + u₂ = 5; u₂ = 0

u₂ + v₂ = 1; 0 + v₂ = 1; v₂ = 1

u₃ + v₄ = 0; -1 + v₄ = 0; v₄ = 1

	v₁=2	v₂=1	v₃=5	v₄=1
u₁=0	2 80
u₂=0		1 90	5 80
u₃=-1	1 40		4 70	0 70

(1;3): 0 + 5 > 2; ∆₁₃ = 0 + 5 - 2 = 3

(1;4): 0 + 1 > 0; ∆₁₄ = 0 + 1 - 0 = 1

(2;4): 0 + 1 > 0; ∆₂₄ = 0 + 1 - 0 = 1

max(3,1,1) = 3

Выбираем максимальную оценку свободной клетки (1;3): 2

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных «-», «+», «-».

					Запасы
	2 80 -		2 +
		1 90	5 80
	1 40 +		4 70 -	0 70
Потребности

Цикл приведен в таблице (1,3 → 1,1 → 3,1 → 3,3).

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

12 3 Следующая ⇒