метод фогеля

Сведем все вычисления в одну таблицу.

	1	2	3	4	5	Запасы	d1	d2	d3	d4	d5	d6	d7
1	12	13	4	14	8[145]	145	4	4	-	-	-	-	-
2	9	8[108]	11	16	7[57]	165	1	1	1	1	1	1	1
3	14	8	12	6	7[200]	200	1	1	1	1	1	1	1
4	5[145]	7[47]	12	6[193]	9	385	1	1	1	1	1	2	-
5	15	12	5[182]	13	11[118]	300	6	1	1	1	-	-	-
Потребности	145	155	182	193	520
d1	4	1	1	0	0
d2	4	1	-	0	0
d3	4	1	-	0	0
d4	-	1	-	0	0
d5	-	1	-	0	0
d6	-	1	-	-	0
d7	-	0	-	-	0

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

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

Значение целевой функции для этого опорного плана равно:

F(x) = 8*145 + 8*108 + 7*57 + 7*200 + 5*145 + 7*47 + 6*193 + 5*182 + 11*118 = 8243

Этап II. Улучшение опорного плана.

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

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

u₂ + v₅ = 7; 8 + u₂ = 7; u₂ = -1

u₂ + v₂ = 8; -1 + v₂ = 8; v₂ = 9

u₄ + v₂ = 7; 9 + u₄ = 7; u₄ = -2

u₄ + v₁ = 5; -2 + v₁ = 5; v₁ = 7

u₄ + v₄ = 6; -2 + v₄ = 6; v₄ = 8

u₃ + v₅ = 7; 8 + u₃ = 7; u₃ = -1

u₅ + v₅ = 11; 8 + u₅ = 11; u₅ = 3

u₅ + v₃ = 5; 3 + v₃ = 5; v₃ = 2

	v1=7	v2=9	v3=2	v4=8	v5=8
u1=0	12	13	4	14	8[145]
u2=-1	9	8[108]	11	16	7[57]
u3=-1	14	8	12	6	7[200]
u4=-2	5[145]	7[47]	12	6[193]	9
u5=3	15	12	5[182]	13	11[118]

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

(3;4): -1 + 8 > 6; ∆₃₄ = -1 + 8 - 6 = 1

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

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

	1	2	3	4	5	Запасы
1	12	13	4	14	8[145]	145
2	9	8[108][-]	11	16	7[57][+]	165
3	14	8	12	6[+]	7[200][-]	200
4	5[145]	7[47][+]	12	6[193][-]	9	385
5	15	12	5[182]	13	11[118]	300
Потребности	145	155	182	193	520

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

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

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

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

u₂ + v₅ = 7; 8 + u₂ = 7; u₂ = -1

u₃ + v₅ = 7; 8 + u₃ = 7; u₃ = -1

u₃ + v₄ = 6; -1 + v₄ = 6; v₄ = 7

u₄ + v₄ = 6; 7 + u₄ = 6; u₄ = -1

u₄ + v₁ = 5; -1 + v₁ = 5; v₁ = 6

u₄ + v₂ = 7; -1 + v₂ = 7; v₂ = 8

u₅ + v₅ = 11; 8 + u₅ = 11; u₅ = 3

u₅ + v₃ = 5; 3 + v₃ = 5; v₃ = 2

	v1=6	v2=8	v3=2	v4=7	v5=8
u1=0	12	13	4	14	8[145]
u2=-1	9	8	11	16	7[165]
u3=-1	14	8	12	6[108]	7[92]
u4=-1	5[145]	7[155]	12	6[85]	9
u5=3	15	12	5[182]	13	11[118]

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

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

F(x) = 8*145 + 7*165 + 6*108 + 7*92 + 5*145 + 7*155 + 6*85 + 5*182 + 11*118 = 8135

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

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

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

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

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

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

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

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

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

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

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

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

Copyright © Semestr.RU