задача 4

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

(3;3): -1 + 7 > 5; ∆₃₃ = -1 + 7 - 5 = 1

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

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

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2	2[325][-]	5[125][+]	6	450
3	7	3[125]	5[+]	9[25][-]	2[100]	250
Потребности	100	125	325	250	100

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

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

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100]	3	200
2	4	2	2[300]	5[150]	6	450
3	7	3[125]	5[25]	9	2[100]	250
Потребности	100	125	325	250	100

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

u₁ + v₁ = 5; 0 + v₁ = 5; v₁ = 5

u₁ + v₄ = 10; 0 + v₄ = 10; v₄ = 10

u₂ + v₄ = 5; 10 + u₂ = 5; u₂ = -5

u₂ + v₃ = 2; -5 + v₃ = 2; v₃ = 7

u₃ + v₃ = 5; 7 + u₃ = 5; u₃ = -2

u₃ + v₂ = 3; -2 + v₂ = 3; v₂ = 5

u₃ + v₅ = 2; -2 + v₅ = 2; v₅ = 4

	v1=5	v2=5	v3=7	v4=10	v5=4
u1=0	5[100]	8	7	10[100]	3
u2=-5	4	2	2[300]	5[150]	6
u3=-2	7	3[125]	5[25]	9	2[100]

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

(1;5): 0 + 4 > 3; ∆₁₅ = 0 + 4 - 3 = 1

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

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

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[100][-]	3[+]	200
2	4	2	2[300][-]	5[150][+]	6	450
3	7	3[125]	5[25][+]	9	2[100][-]	250
Потребности	100	125	325	250	100

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

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

	1	2	3	4	5	Запасы
1	5[100]	8	7	10[0]	3[100]	200
2	4	2	2[200]	5[250]	6	450
3	7	3[125]	5[125]	9	2	250
Потребности	100	125	325	250	100

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

u₁ + v₁ = 5; 0 + v₁ = 5; v₁ = 5

u₁ + v₄ = 10; 0 + v₄ = 10; v₄ = 10

u₂ + v₄ = 5; 10 + u₂ = 5; u₂ = -5

u₂ + v₃ = 2; -5 + v₃ = 2; v₃ = 7

u₃ + v₃ = 5; 7 + u₃ = 5; u₃ = -2

u₃ + v₂ = 3; -2 + v₂ = 3; v₂ = 5

u₁ + v₅ = 3; 0 + v₅ = 3; v₅ = 3

	v1=5	v2=5	v3=7	v4=10	v5=3
u1=0	5[100]	8	7	10[0]	3[100]
u2=-5	4	2	2[200]	5[250]	6
u3=-2	7	3[125]	5[125]	9	2

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Минимальные затраты составят:

F(x) = 5*100 + 3*100 + 2*200 + 5*250 + 3*125 + 5*125 = 3450

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (100), в 5-й магазин (100)

Из 2-го склада необходимо груз направить в 3-й магазин (200), в 4-й магазин (250)

Из 3-го склада необходимо груз направить в 2-й магазин (125), в 3-й магазин (125)

Задача имеет множество оптимальных планов, поскольку оценка для (1;4) равна 0.

Решение было получено и оформлено с помощью сервиса:

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

Вместе с этой задачей решают также:

Универсальная транспортная задача

Задача коммивояжера

Задача о назначениях

Copyright © Semestr.RU