ВУЗ:
Составители:
Рубрика:
6
Числа u
i
и v
j
называются потенциалами соответственно поставщиков и
потребителей.
Из теоремы следует, что для того чтобы первоначальный план был оп-
тимальным, необходимо выполнение следующих условий:
а) для каждой занятой клетки сумма потенциалов должна быть равна
стоимости единицы перевозки, стоящей в этой клетке:
u
i
+ v
j
= с
i j
;
б) для каждой незанятой клетки сумма потенциалов должна быть
меньше или равна стоимости единицы перевозки, стоящей в этой клетке:
u
i
+ v
j
≤
с
i j
.
Если хотя бы одна незанятая клетка не удовлетворяет последнему усло-
вию
u
i
+ v
j
≤
с
i j
, то план не оптимален.
Алгоритм метода потенциалов.
1. Построение системы потенциалов. Для построения системы потен-
циалов используем условие
u
i
+ v
j
= с
i j
. Заполненных клеток должно быть
точно
m+ n – 1. Если оказалось, что при составлении первоначального пла-
на заполненных клеток меньше чем
m+ n – 1, то добавим нужное количест-
во занятых клеток с
x
i j
= 0 таким образом, чтобы при этом не был образо-
ван цикл.
Используем план, полученный методом «наименьшей стоимости»:
B
A
40
25
20
50
60
5
4
1
20
2
40
u
1
40
4
5
2
25
6
3
10
u
2
35
7
35
3 5 4
u
3
v
1
v
2
v
3
v
4
u
1
+ v
3
= 1
u
1
+ v
4
= 2
u
2
+ v
1
= 4
u
2
+ v
2
= 2
u
2
+ v
4
= 3
u
3
+ v
1
= 7
6
Числа ui и vj называются потенциалами соответственно поставщиков и
потребителей.
Из теоремы следует, что для того чтобы первоначальный план был оп-
тимальным, необходимо выполнение следующих условий:
а) для каждой занятой клетки сумма потенциалов должна быть равна
стоимости единицы перевозки, стоящей в этой клетке:
ui + vj = сi j;
б) для каждой незанятой клетки сумма потенциалов должна быть
меньше или равна стоимости единицы перевозки, стоящей в этой клетке:
ui + vj ≤ сi j.
Если хотя бы одна незанятая клетка не удовлетворяет последнему усло-
вию ui + vj ≤ сi j, то план не оптимален.
Алгоритм метода потенциалов.
1. Построение системы потенциалов. Для построения системы потен-
циалов используем условие ui + vj = сi j . Заполненных клеток должно быть
точно m+ n – 1. Если оказалось, что при составлении первоначального пла-
на заполненных клеток меньше чем m+ n – 1, то добавим нужное количест-
во занятых клеток с xi j = 0 таким образом, чтобы при этом не был образо-
ван цикл.
Используем план, полученный методом «наименьшей стоимости»:
B
40 25 20 50
A
5 4 1 2
60 20 40 u1
4 2 6 3
40 5 25 10 u2
7 3 5 4
35 35 u3
v1 v2 v3 v4
u1 + v3 = 1
u1 + v4 = 2
u2 + v1 = 4
u2 + v2 = 2
u2 + v4 = 3
u3 + v1= 7
