Задачи ЛП и методы их решения
.pdf
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
200 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7.14.4. Метод потенциалов для решения |
Найдем базисный план перевозок для |
|||||||||||||||||||||||||||||||||
сетевой ТЗ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
основного примера, приведенного выше |
|||||||||||||||||||
Базисный план в СТЗ определяется из |
|
|
1 |
2 |
|
3 |
|
4 |
5 |
6 7 |
8 |
|
|
b |
||||||||||||||||||||
условий |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
-1 |
|
|
|
|
|
|
|
|
|
|
-1 |
|
||||
|
|
|
|
|
x[N \ N ']=0[N \ N '] |
|
1 |
|
1 -1 -1 |
|
|
1 1 |
|
|
|
0 |
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a[M, N '] x[N ']=b[M ] |
|
2 |
|
|
1 |
|
|
-1 |
|
-1 |
|
|
|
2 |
|
|||||||||||||||
|
|
|
|
|
3 |
|
|
|
|
1 |
|
|
|
|
-1 |
|
|
0 |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
где |
[M, N '] |
- |
связывающее дерево |
4 |
|
|
|
|
|
|
1 |
|
|
|
|
|
0 |
|
||||||||||||||||
(вспомним, |
|
что |
ранг |
a[M, N ] |
равен |
5 |
|
|
|
|
|
|
|
-1 |
|
|
|
|
-7 |
|
||||||||||||||
|
6 |
|
|
|
|
|
|
|
|
-1 |
|
|
|
-3 |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
N ' |
= |
M |
−1) |
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
1 |
|
|
|
4 |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
Решению |
|
последней |
системы |
очень |
8 |
|
|
|
|
|
|
|
|
|
1 |
|
|
5 |
|
|||||||||||||||
помогает |
правильная |
нумерация |
дуг |
Обратным |
ходом |
метода |
исключения |
|||||||||||||||||||||||||||
связывающего дерева, введенная выше. |
Гаусса находим |
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
Запишем двойственную ЗЛП к СТЗ |
|
[ |
] |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
x 8 =5 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
v[M ] b[M ]→ max |
|
|
|
|
|
|
|
|
x 7 |
=4 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[ |
] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
v[M ] a[M, N ]≤C[N ] |
|
x 6 |
=3 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
С учетом структуры матрицы инциденций |
[ |
] |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
x 5 =7 |
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||
(в каждом |
|
столбце ровно |
2 ненулевых |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
[ |
] |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
элемента: |
1 |
- |
соответствует |
|
|
концу |
дуги |
[ |
] |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
x 4 |
=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
j(u) |
и −1 |
- |
соответствует |
|
|
началу |
дуги |
x 3 |
=0+x 8 =5 |
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[ |
] |
|
[ |
] |
|
|
|
|
|
|
|
|
|
|
i(u)) получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
x 2 |
=2+x |
4 |
+x |
7 |
=6 |
|
|
|
|
|
|
|
||||||||
( ) ε[u]=v j(u) −v i(u) −C[u]≤0, u N |
[ |
] |
[ |
] |
[ ] |
|
|
|
|
|
|
|
||||||||||||||||||||||
x1 =0+x 2 +x |
3−x 5−x |
6 =5+6−7−3=1 |
|
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
[ |
] |
|
[ |
] |
[ |
] |
[ ] |
[ |
] |
|
|
|
|
|
Нетрудно видеть, что левая часть |
Начальный базисный план будет выглядеть |
|||||||||||||||||||||||||||||||||
последнего неравенства есть оценка дуги и |
так: |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
в текущем базисе N '. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-1 |
|
4 |
|
|
|
|
|
||||||||
Таким |
образом, |
критерий оптимальности |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
задается условием ( ), а сами компоненты |
|
|
|
|
|
|
|
1 |
|
4 |
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|||||||||||||||||||||
вектора |
|
двойственных |
|
|
переменных |
|
|
|
-3 |
|
3 |
|
|
6 |
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
0 |
|
2 |
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
(называемые |
|
здесь |
потенциальными) |
|
|
|
|
|
|
|
7 |
|
5 |
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
||||||||||||||||||||
определяются |
из |
условий равенства |
нулю |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||
оценок базисных дуг (дуг неравенства N '). |
|
|
|
|
|
|
|
-7 |
|
5 |
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
( ) v j(u) −v i(u) =C[u], u N ' |
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|||||||||||||||||
Система ( ) содержит уравнений на одно |
|
|
Определим потенциалы вершин |
|
|
|||||||||||||||||||||||||||||
меньше, чем переменных ( |
|
N ' |
|
= |
|
M |
|
−1), и |
|
|
|
|
|
|
|
0 |
|
7 |
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
это позволяет при нахождении потенциалов |
|
|
|
|
|
|
|
1 |
|
1 |
1 |
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
4 |
|
|
|
|
||
один |
из |
|
них |
выбрать |
произвольно. |
|
|
6 |
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
1 |
|
2 |
4 |
|
|
||||||||||||||||||||||
Используя |
|
|
правильную |
|
|
нумерацию, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
||||||||||||||||||
потенциалы удобно находить в порядке |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
||||||||||||||||||||
возрастания номеров вершин (двигаясь по |
|
|
|
|
|
|
|
5 |
|
1 |
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
ориентации |
к |
известному |
|
|
потенциалу, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
добавляем цену по дуге, двигаясь против |
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|||||||||||||||||||
ориентации дуги - цену вычитаем). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||
Теперь для каждой небазисной дуги (на рис. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
выделены |
|
|
пунктиром) |
|
|
проверяем |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
выполнение неравенства |
( ). Одна из дуг |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
u , для которой нарушается критерий оптимальности (штриховые линии на рис.)
|
|
|
|
|
|
202 |
|
|
|
|
|
|
|
|
|
0 |
|
8 |
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2-я итерация |
|||
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
1 |
|
1 |
|
|
|
2 |
|
|
|
1 |
|
1 |
|
1 |
|
|
1 |
|
|
||
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
7 |
2 |
|
4 |
1 |
6 |
2 |
|
4 |
|
|
1 |
6 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
-1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
4 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
0 |
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
2 |
|
1 |
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|
3 |
|
|
|
2 |
|
|
|
|
|
|
(1) |
u |
|
(4) |
|
|
|
(1) |
|
(4) |
|
|
|
|
(3) |
|
|
(0) |
|
(3) |
|
|
|
|
(0) |
|
|
|
|
(6) |
|
|
|
|
|
(5) |
|
|
|
|
|
|
(2) |
|
|
|
|
|
(2) |
|
|
|
|
|
|
|
|
(5) |
(0) |
|
|
|
|
(5) |
(0) |
|
|
|
= 4 |
|
|
|
|
|
|
|
|
|
|
|
|
f |
|
|
|
0 |
|
8 |
|
|
0 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
3-я итерация |
|
|
|
|
1 |
|
|
1 |
|
1 |
|
|
|
2 |
|
|
|
|
1 |
|
1 |
|
|
1 |
|
|
|||
|
|
|
|
|
-3 |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
2 |
|
4 |
1 |
6 |
2 |
|
4 |
|
|
1 |
2 |
|
|
2 |
|
|
|
|
|
|
|
|
|
|||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
-5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
5 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
-4 |
2 |
|
|
-3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
2 |
|
1 |
|
|
|
2 |
|
1 |
|
|
|
|
|
|
|
4 |
|
|
|
-2 |
|
|
|
|
|
u |
(4) |
(3) |
(4) |
(4) |
|
(1) |
|||||
|
|||||
(3) |
(0) |
|
|
(0) |
|
(5) |
|
|
(2) |
|
|
(2) |
|
|
(2) |
|
(5) |
(0) |
(5) |
(0) |
f = 12
|
|
|
|
|
203 |
|
|
|
|
|
|
|
|
1 |
|
8 |
|
|
1 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
4-я итерация |
|
|
|
1 |
|
|
1 |
|
1 |
|
|
|
2 |
|
1 |
|
1 |
|
1 |
|
|
1 |
|
|
|||
|
|
|
-2 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
4 |
1 |
7 |
2 |
|
4 |
|
|
1 |
3 |
|
3 |
|
|
|
|
|
|
|
|
|
|||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
6 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
|
-3 |
2 |
|
|
-2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
2 |
|
1 |
|
|
|
2 |
|
1 |
|
|
|
|
|
|
5 |
|
|
|
-1 |
|
|
|
|
|
|
(1) |
|
(4) |
|
(3) |
|
|
|
|
|
|
|
|
|
|
|
|
|
(4) |
|
(4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
(3) |
|
|
(0) |
|
|
|
|
|
|
|
|
|
|
(5) |
|
|
|
|
|
|
|
|
(0) |
|
|
|
|
|
|
|
|
|
(2) |
|
|
|
|
|
(2) |
|
u |
|
|
|
(2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(0) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(5) |
(0) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(5) |
|
|
|
|
= 0 |
|
|
|
|
|
|
|
|
|
|
|
f |
|
|
1 |
|
8 |
|
|
1 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
5-я итерация |
|
|
|
1 |
|
|
1 |
|
1 |
|
|
|
2 |
|
1 |
|
1 |
|
1 |
|
|
1 |
|
|
|||
|
|
|
-2 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
4 |
1 |
7 |
2 |
|
4 |
|
|
1 |
3 |
|
3 |
|
|
|
|
|
|
|
|
|
|||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
1 |
|
|
1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
4 |
|
6 |
|
|
-3 |
2 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
2 |
|
|
|
|
|
2 |
|
1 |
|
|
|
|
|
|
5 |
|
|
|
-1 |
|
|
|
|
|
|
(4) |
|
|
|
|
|
|
|
|
|
|
|
(3) |
|
|
(4) |
|
(3) |
|
(4) |
|
(4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
(0) |
|
|
|
|
|
|
(0) |
|
|
|
(2) |
|
|
|
|
|
|
|
|
|
|
|
|
u |
|
(0) |
|
|
(2) |
(2) |
|
|
|
|
|
(2) |
|
|
|
|
|
(2) |
|
|
|
|||
|
|
|
|
|
|
|
|
|
||||
|
(5) |
|
|
|
|
|
(5) |
|
|
|
f |
= 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
204 |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
8 |
|
|
|
1 |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6-я итерация |
|
|
|
1 |
|
|
|
|
1 |
|
|
1 |
|
|
|
2 |
|
1 |
|
1 |
|
|
|
|
1 |
|
|
1 |
|
|
|||
|
|
|
|
|
|
0 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
4 |
|
1 |
7 |
|
|
2 |
|
|
4 |
|
|
1 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
5 |
|
3 |
|
|
|
|
-1 |
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
2 |
|
|
|
|
|
|
|
|
2 |
|
1 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
1 |
|
|
|
|
|
(3) |
(4) |
|
(4) |
|
|
|
(3) |
|
|
(4) |
|
(4) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
(0) |
|
|
|
|
|
|
|
|
|
|
|
|
|
(2) |
|
u |
|
|
|
|
|
|
|
|
|
|
|
|
|
(2) |
(2) |
|
|
|
|
|
(2) |
(2) |
|
(2) |
|
(0) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(5) |
|
|
|
|
|
|
|
|
(5) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
= 0 |
|
1 |
|
8 |
|
|
|
1 |
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7-я итерация |
|
|
|
1 |
|
|
|
|
1 |
|
|
1 |
|
|
|
2 |
|
1 |
|
1 |
|
|
|
|
1 |
|
|
1 |
|
|
|||
|
|
|
|
|
|
0 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
4 |
|
|
7 |
|
|
2 |
|
|
4 |
|
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
|
|
|
|
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
5 |
|
3 |
|
|
|
|
-1 |
|
2 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
2 |
|
|
|
|
|
|
|
|
2 |
|
1 |
|
|
|
|
|
|
6 |
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
-1 |
|
|
|
|
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
(3) |
|
(4) |
1 |
(4) |
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
Текущее решение |
|
-3 |
|
0 |
|
|
|
|
2 |
|
0 |
|
|
|
|
оптимально |
|
|
|
|
|
(2) |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
(0) |
|
|
|
|
|
|||
|
|
|
|
|
(2) |
1 |
1 |
|
|
|
|
|
|
||
|
|
|
|
|
1 |
(2) |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
-7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
0 |
|
Стоимость плана перевозок – 27 ед. |
||||
|
|
|
|
|
|
(5) |
|
|
|
|
(уменьшилась на 25 ед.) |
|
|||
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
205
Опишем теперь построение начального допустимого базисного решения. Используем для этого метод искусственного базиса. Для этого построим расширение M, N графа
M, N :
M = M {i }, N = N Ni+ Ni−
Здесь: i - новая вершина
Ni+ - множество дуг, ведущих от пунктов производства к i
Ni− - множество дуг, идущих от i к остальным вершинам сети (потребления и промежуточным пунктам).
b |
|
|
=0, C N |
+ |
|
=0 N |
+ |
|
|
C |
N |
− |
|
= gz×1 N |
− |
|
|||||
i |
, |
||||||||||||||||||||
i |
|
i |
|
i |
|
i |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
(gz >C[N ] 1[N ]− достаточно большое число)
Вкачестве начального (искусственного) базиса можно принять
|
|
N ' = N \ N = N+ |
N− |
|
|
|
|
|
|
|
|
i |
i |
|
|
|
|
-1 |
|
|
|
|
-1 |
|
|
|
|
4 |
|
|
|
|
|
4 |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
GZ |
|
|
0 |
2 |
0 |
|
|
0 GZ |
|
2 |
0 |
-3 |
|
-3 |
|
|
|
|
||
|
|
|
|
|
|
GZ |
GZ |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
GZ |
|
||
|
|
|
|
|
|
|
|
|
-7 |
0 |
|
|
|
-7 |
|
0 |
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
GZ |
|
|
|
5 |
|
|
|
|
|
5 |
|
"Искусственные" дуги образуют дерево типа "звезда". Дуговые потоки определяются очевидным образом: x[u]=−b i(u) , для u Ni+ , x[u]=b j(u) , для u Ni− . Ясно также, что данное базисное решение не является оптимальным (за счет цен, равных gz ).
206
7.14.5. Варианты СТЗ и родственные ей задачи
Следуя [9], перечислим несколько вариантов СТЗ и родственных ей экстремальных задач на графах, иллюстрирующих плодотворность идеи потенциалов.
а) СТЗ с ограничениями на пропускные способности дуг
c[N] x[N] → min
A[M, N] x[N] = b[M ]
0[N]≤ x[N]≤ d [M ]
d [N] – ограниченные пропускные способности дуг.
Двойственная задача с учетом d [N] выглядит следующим образом:
v[M ] b[M ]− ρ [N] d [N] → max |
||
v[M ] A[M, N]− ρ [N] ≤ c[N] |
, |
|
ρ [N]≥ 0[N] |
||
|
||
откуда критерий оптимальности запишется в виде |
|
|
v[ j(u)]− v[i(u)] ≤ c[u]+ ρ [u], |
||
где |
|
|
v[i(u)],v[ j(u)] – потенциалы начала и конца дуги u , |
|
ρ[u] – "рента на дуге " u .
1. Критерий оптимальности может быть записан и без участия рент.
2.Преобразованием сети, при котором каждая "ограниченная" дуга заменяется тремя "неограниченными" дугами (см. рис.)
|
|
|
|
d[u] |
|
|
|
|
|
i+ |
|
|
d[u] |
|
|
c[u] |
|
i |
j |
|
i |
0 |
j |
|
|||||
|
c[u] |
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
j- |
|
|
|
|
|
-d[u] |
транспортная задача с ограничениями на пропускные способности дуг может быть сведена к СТЗ без ограничений пропускных способностей
б) Задача об оптимальном нормированном контурном потоке
c[N] x[N]→ min
A[M, N] x[N] = 0[M ] условие замкнутости потока
x[N]≥ 0[N]
l[N] x[N] =1 условие нормировки
208
v[ j(u)] = v[i(u)]+ c[u], u N ' [ j(u)]≤ v[i(u)]+ c[u], u N \ N '
v[ j(u)] = min{v[i(u)]+ c[u], u N+j } (*) Является вектором кратчайших длин путей.
Метод потенциалов для задачи о кратчайших путях несколько видоизменяется. Вопервых, нет смысла считать потоки по базисному дереву. Их структура совершенно ясна. Поток убывает на единицу с каждой пройденной дугой по мере удаления от i0 и равен единице на последней дуге каждой ветви дерева (числа в кружках – номера вершин).
|
|
2 |
4 |
|
|
1 |
4 |
7 |
|
|
|
|
|
|
|||
|
|
|
2 |
|
|
|
(2) |
(1) |
1 |
1 |
3 |
|
|
|
|
|
|
|
2 |
(3) |
|
|
|
|||
|
|
3 |
|
|
|
|
||
|
|
|
|
|
|
|
||
i0 |
2 |
2 |
3 |
|
|
2 |
5 |
8 |
|
|
|
|
(3) |
||||
|
|
|
|
|
|
(2) |
(1) |
|
|
1 |
2 |
1 |
|
i0 |
|
|
|
2 |
3 |
|
|
|
|
|||
|
3 |
|
|
|
|
|
||
|
|
|
|
|
(3) |
3 |
6 |
9 |
|
|
2 |
3 |
|
|
|
(2) |
(1) |
При вычислении потенциалов, здесь всегда потенциал конца дуги вычисляется по потенциалу начала дуги.
1 |
3 |
|
7 |
|
1 |
3 |
7 |
|
|
2 |
|
2 |
|
|
|
2 |
4 |
u |
7 |
u |
2 |
4 |
5 |
0 |
|
|
|
i0 |
0 |
|
|
2 |
4 |
|
7 |
|
2 |
2 |
7 |
Это дерево кратчайших путей
Вводимая в базис дуга u порождает цикл, состоящий из двух путей различной ориентации, идущих из i0 в конец дуги u . Из базиса удаляется дуга " отрицательной " части цикла, примыкающая к концу дуги u . Потенциалы пересчитываются для всех вершин, следующих за j(u ): они уменьшаются на одну и ту же величину
ε [u] = v[ j(u)]− v[i(u)]− c[u].
Одним из самых эффективных алгоритмов реализации метода потенциалов в данной задаче при положительном векторе c[N] (что, вообще говоря, не требуется при постановке задачи) является алгоритм Дейкстры