= 4
u
3 + v
3 = 6; 4 + v
3 = 6; v
3 = 2
u
1 + v
4 = 3; 0 + v
4 = 3; v
4 = 3
|
v1=-5
|
v2=4
|
v3=2
|
v4=3
|
u1=0
|
7
|
4[50]
|
9
|
3[350]
|
u2=7
|
2[450]
|
11[100]
|
8
|
4
|
u3=4
|
3
|
8[100]
|
6[200]
|
5
|
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u
i + v
j> c
ij (2;3): 7 + 2> 8; ∆
23 = 7 + 2 - 8 = 1> 0
(2;4): 7 + 3> 4; ∆
24 = 7 + 3 - 4 = 6> 0
(3;4): 4 + 3> 5; ∆
34 = 4 + 3 - 5 = 2> 0
max (1,6,2) = 6
Выбираем максимальную оценку свободной клетки (2;4): 4
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1
|
2
|
3
|
4
|
Запасы
|
1
|
7
|
4[50][+]
|
9
|
3[350][-]
|
400
|
2
|
2[450]
|
11[100][-]
|
8
|
4[+]
|
550
|
3
|
3
|
8[100]
|
6[200]
|
5
|
300
|
Потребности
|
450
|
250
|
200
|
350
|
|
Цикл приведен в таблице (2,4 → 2,2 → 1,2 → 1,4).
Из грузов х
ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Х
ij, стоящих в минусовых клетках. В результате получим новый опорный план.
|
B1
|
B2
|
B3
|
B4
|
Запасы
|
A1
|
7
|
4[150]
|
9
|
3[250]
|
400
|
A2
|
2[450]
|
11
|
8
|
4[100]
|
550
|
A3
|
3
|
8[100]
|
6[200]
|
5
|
300
|
Потребности
|
450
|
250
|
200
|
350
|
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы u
i, v
j. по занятым клеткам таблицы, в которых u
i + v
j = c
ij, полагая, что u
1 = 0.
u
1 + v
2 = 4; 0 + v
2 = 4; v
2 = 4
u
3 + v
2 = 8; 4 + u
3 = 8; u
3 = 4
u
3 + v
3 = 6; 4 + v
3 = 6; v
3 = 2
u
1 + v
4 = 3; 0 + v
4 = 3; v
4 = 3
u
2 + v
4 = 4; 3 + u
2 = 4; u
2 = 1
u
2 + v
1 = 2; 1 + v
1 = 2; v
1 = 1
|
v1=1
|
v2=4
|
v3=2
|
v4=3
|
u1=0
|
7
|
4[150]
|
9
|
3[250]
|
u2=1
|
2[450]
|
11
|
8
|
4[100]
|
u3=4
|
3
|
8[100]
|
6[200]
|
5
|
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u
i + v
j> c
ij (3;1): 4 + 1> 3; ∆
31 = 4 + 1 - 3 = 2> 0
(3;4): 4 + 3> 5; ∆
34 = 4 + 3 - 5 = 2> 0
max (2,2) = 2
Выбираем максимальную оценку свободной клетки (3;1): 3
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1
|
2
|
3
|
4
|
Запасы
|
1
|
7
|
4[150][+]
|
9
|
3[250][-]
|
400
|
2
|
2[450][-]
|
11
|
8
|
4[100][+]
|
550
|
3
|
3[+]
|
8[100][-]
|
6[200]
|
5
|
300
|
Потребности
|
450
|
250
|
200
|
350
|
|
Цикл приведен в таблице (3,1 → 3,2 → 1,2 → 1,4 → 2,4 → 2,1).
Из грузов х
ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Х
ij, стоящих в минусовых клетках. В результате получим новый опорный план.
|
B1
|
B2
|
B3
|
B4
|
Запасы
|
A1
|
7
|
4[250]
|
9
|
3[150]
|
400
|
A2
|
2[350]
|
11
|
8
|
4[200]
|
550
|
A3
|
3[100]
|
8
|
6[200]
|
5
|
300
|
Потребности
|
450
|
250
|
200
|
350
|
|
Проверим оптимальность опорного плана. Найдем
предварительные потенциалы u
i, v
j. по занятым клеткам таблицы, в которых u
i + v
j = c
ij, полагая, что u
1 = 0.
u
1 + v
2 = 4; 0 + v
2 = 4; v
2 = 4
u
1 + v
4 = 3; 0 + v
4 = 3; v
4 = 3
u
2 + v
4 = 4; 3 + u
2 = 4; u
2 = 1
u
2 + v
1 = 2; 1 + v
1 = 2; v
1 = 1
u
3 + v
1 = 3; 1 + u
3 = 3; u
3 = 2
u
3 + v
3 = 6; 2 + v
3 = 6; v
3 = 4
|
v1=1
|
v2=4
|
v3=4
|
v4=3
|
u1=0
|
7
|
4[250]
|
9
|
3[150]
|
u2=1
|
2[350]
|
11
|
8
|
4[200]
|
u3=2
|
3[100]
|
8
|
6[200]
|
5
|
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u
i + v
j ≤ c
ij.
Минимальные затраты составят: F(x) = 4*250 + 3*150 + 2*350 + 4*200 + 3*100 + 6*200 = 4450
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 2 у потребителя (250 ед.), к 4-у потребителя (150 ед.)
Из 2-го склада необходимо груз направить к 1-у потребителя (350 ед.), 4-у потребителя (200 ед.)
Из 3-го склада необходимо груз направить к 1-у потребителя (100 ед.), к 3-у потребителя (200 ед.)