Транспортная задача
.pdf3.5. Метод потенциалов |
61 |
|
|
Для выбранной клетки строится замкнутый цикл, то есть замкнутый путь, соединяющий выбранную незаполненную клетку с ней же самой и проходящий через заполненные клетки.
Для каждой свободной клетки существует только один цикл.
|
В1 |
|
В2 |
В3 |
В4 |
|
запасы |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А1 |
|
|
|
3 |
|
2 |
|
4 |
|
|
|
6 |
50 |
|
|
|
|
|
|
|
|
|
|
|
|
||
20 |
|
|
|
25 |
|
- |
|
5 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||||
А2 |
|
|
|
2 |
|
3 |
|
1 |
|
|
|
2 |
40 |
10 |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
- |
|
30 |
|
- |
|
|
|
|
|
А3 |
|
|
|
3 |
|
2 |
|
7 |
|
|
|
4 |
20 |
- |
|
|
|
- |
|
- |
|
20 |
|
|
|||
|
|
|
|
|
|
|
|
|
|||||
спрос |
30 |
|
25 |
30 |
25 |
|
110 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.5. Метод потенциалов |
62 |
|
|
В каждой клетке цикла, начиная со свободной проставляются поочередно знаки «+» и «-». В клетках со знаком «-» (четные клетки) выбирается наименьший груз, который «перемещается» по клеткам замкнутого цикла, т.е.
прибавляется к поставкам xij в клетках со знакам «+» (включая свободную) и вычитается в клетках со знаком «-».
|
В1 |
|
В2 |
В3 |
В4 |
|
запасы |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
А1 |
+ |
|
3 |
|
2 |
|
4 |
- |
|
6 |
50 |
||
|
|
|
|
|
|
|
|
|
|
|
|
||
20 |
|
|
|
25 |
|
- |
|
5 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||||
А2 |
- |
|
|
2 |
|
3 |
|
1 |
|
|
|
2 |
40 |
|
|
|
|
|
|
|
|
|
|
|
|||
|
10 |
|
|
|
- |
|
30 |
|
- + |
|
|||
А3 |
|
|
|
3 |
|
2 |
|
7 |
|
|
|
4 |
20 |
- |
|
|
|
- |
|
- |
|
20 |
|
|
|||
|
|
|
|
|
|
|
|
|
|||||
спрос |
30 |
|
25 |
30 |
25 |
|
110 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
В результате такого перемещения груза по циклу получим новый план перевозок.
3.5. Метод потенциалов |
63 |
|
|
Строится новый план
|
В1 |
|
В2 |
В3 |
В4 |
|
запасы |
||||
|
|
|
|
|
|
|
|
|
|
|
|
А1 |
|
|
3 |
|
2 |
|
4 |
|
|
6 |
50 |
25 |
|
|
25 |
|
- |
|
- |
|
|
||
|
|
|
|
|
|
|
|
||||
А2 |
|
|
2 |
|
3 |
|
1 |
|
|
2 |
40 |
5 |
|
|
- |
|
30 |
|
5 |
|
|
||
|
|
|
|
|
|
|
|
||||
А3 |
|
|
3 |
|
2 |
|
7 |
|
|
4 |
20 |
- |
|
|
- |
|
- |
|
20 |
|
|
||
|
|
|
|
|
|
|
|
||||
спрос |
30 |
|
25 |
30 |
25 |
|
110 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
Вычисления по методу потенциалов повторяются с 1 этапа
3.5. Метод потенциалов |
64 |
|
|
|
В1 |
В2 |
В3 |
|
В4 |
запас |
|||
|
|
ы |
|||||||
|
|
|
|
|
|
|
|
|
|
А1 |
|
3 |
|
2 |
|
4 |
|
6 |
50 |
U1+V1=3 |
U1+V2=2 |
- |
|
- |
|
||||
|
|
|
|
||||||
А2 |
|
2 |
|
3 |
|
1 |
|
2 |
40 |
|
|
|
|
|
|
|
|
||
U2+V2=2 |
- |
|
U2+V3=1 |
U2+V4=2 |
|||||
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
А3 |
|
3 |
|
2 |
|
7 |
|
4 |
20 |
- |
|
- |
|
- |
|
|
|
||
|
|
|
U3+V4=4 |
||||||
|
|
|
|
|
|||||
спрос |
30 |
25 |
30 |
25 |
110 |
||||
|
|
|
|
|
|
|
|
|
|
3.5. Метод потенциалов |
65 |
|
|
Предполагается, что U1 = 0, тогда
U1 = 0 |
V1 = 3 |
U2 = 0 |
V2 = 2 |
U3 = 2 |
V3 = 1 |
|
V4 = 2 |
3.5. Метод потенциалов |
66 |
|
|
В1 |
В2 |
В3 |
В4 |
запас |
C’13 = U1+V3 = 0+1=1 |
|
ы |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C’14 = U1+V4 = 0+2=2 |
|
А1 |
|
|
3 |
|
2 |
|
4 |
|
|
6 |
50 |
||
25 |
|
|
25 |
|
- |
|
- |
|
|
C’22 |
= U2+V2=0+2=2 |
||
|
|
|
|
|
|
|
|
||||||
А2 |
|
|
2 |
|
3 |
|
1 |
|
|
2 |
40 |
C’31 = U3+V1=2+3=5 |
|
5 |
|
|
- |
|
30 |
|
5 |
|
|
C’32 |
=U3+V2=2+2=4 |
||
|
|
|
|
|
|
|
|
||||||
|
|
|
3 |
|
2 |
|
7 |
|
|
4 |
|
||
А3 |
|
|
|
|
|
|
20 |
C’33 |
= U3+V3= 2+1=3 |
||||
- |
|
|
- |
|
- |
|
20 |
|
|
||||
|
|
|
|
|
|
|
|
|
|
||||
спрос 30 |
|
25 |
30 |
25 |
|
110 |
|
|
|||||
13= C13 - C’13 = 4-1=3
14= C14 - C’14 = 6-2=4
22 |
= C22 |
- C’22 |
= 3-2=1 |
Полученный план перевозок |
|
не является оптимальным, |
|||||
|
|
|
|
||
31 = C31- C’31 = 3-5=-2 |
так как среди оценок ij имеется |
||||
32 = C32 - C’32 = 2-4=-2 |
отрицательная оценка 31, 32 |
||||
|
|||||
|
|||||
33 |
= C33 |
- C’33 |
= 7-3=4 |
|
|
3.5. Метод потенциалов |
67 |
|
|
План необходимо улучшить и построить новый
|
В1 |
В2 |
В3 |
В4 |
|
запасы |
||||
|
|
|
|
|
|
|
|
|
|
|
А1 |
|
3 |
|
2 |
|
4 |
|
|
6 |
50 |
25 |
|
25 |
|
- |
|
- |
|
|
||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
||||
А2 |
|
2 |
|
3 |
|
1 |
|
|
2 |
40 |
5 |
|
- |
|
30 |
|
5 |
|
|
||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
А3 |
|
3 |
|
2 |
|
7 |
|
|
4 |
20 |
- |
|
- |
|
- |
|
20 |
|
|
||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
||||
спрос |
30 |
25 |
30 |
25 |
|
110 |
||||
|
|
|
|
|
|
|
|
|
|
|
Загружается та клетка, у которой оценка отрицательная.
31 = C31- C’31 = 3-5=-2 32 = C32 - C’32 = 2-4=-2
3.5. Метод потенциалов |
68 |
|
|
|
|
В1 |
|
В2 |
В3 |
|
|
В4 |
|
запасы |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А1 |
|
|
|
3 |
|
2 |
|
4 |
|
|
|
|
6 |
50 |
25 |
|
|
|
25 |
|
- |
|
- |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
||||
А2 |
- |
|
2 |
|
3 |
|
1 |
|
|
|
|
2 |
40 |
|
5 |
|
|
|
|
|
|
|
|
|
+ |
|
|||
|
|
|
|
- |
|
30 |
|
5 |
|
|
|
|||
А3 |
+ |
|
|
3 |
|
2 |
|
7 |
|
|
|
|
4 |
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
20 - |
||||||||
|
- |
|
|
|
- |
|
- |
|
|
|||||
|
|
|
|
|
|
|
||||||||
спрос |
30 |
|
25 |
30 |
25 |
|
110 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.5. Метод потенциалов |
69 |
|
|
Строится новый план
|
В1 |
В2 |
В3 |
В4 |
|
запасы |
||||
|
|
|
|
|
|
|
|
|
|
|
А1 |
|
3 |
|
2 |
|
4 |
|
|
6 |
50 |
25 |
|
25 |
|
- |
|
- |
|
|
||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
||||
А2 |
|
2 |
|
3 |
|
1 |
|
|
2 |
40 |
- |
|
- |
|
30 |
|
10 |
|
|
||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
А3 |
|
3 |
|
2 |
|
7 |
|
|
4 |
20 |
5 |
|
- |
|
- |
|
15 |
|
|
||
|
|
|
|
|
||||||
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
||||
спрос |
30 |
25 |
30 |
25 |
|
110 |
||||
|
|
|
|
|
|
|
|
|
|
|
3.5. Метод потенциалов |
70 |
|
|
Предполагается, что U1 = 0, тогда
U1 = 0 |
V1 = 3 |
U2 = -2 |
V2 = 2 |
U3 = 0 |
V3 = 3 |
|
V4 = 4 |