Материал: Математические методы и модели в экономике. Амелин С.В
Поскольку среди значений ij есть отрицательные, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (3,1), перейти к новому плану.
|
V1 = 5 |
V2 = 4 |
V3 = 4 |
V4 = 3 |
|
Для занятых |
|||
U1 = 0 |
5 |
4 |
|
2 |
5 |
30 |
клеток |
||
10 |
|
20 |
|
|
|
U1 + V1 = 5, |
|||
|
|
|
|
|
|
|
|
||
|
|
6 |
1 |
|
1 |
3 |
|
||
U2 = -3 |
|
|
70 |
U1 + V2 = 4, |
|||||
|
|
70 |
|
|
|
||||
|
|
|
|
|
|
|
|
U2 + V2 = 1, |
|
U3 = -3 |
|
2 |
3 |
|
1 |
8 |
50 |
||
10 |
|
|
|
40 |
|
U3 + V1 = 2, |
|||
|
|
|
|
||||||
|
|
|
|
|
|
|
|
||
U4 = -2 |
6 |
3 |
2 |
1 |
|
||||
100 |
U3 + V3 = 1, |
||||||||
|
|
|
30 |
70 |
|||||
|
20 |
|
90 |
70 |
70 |
|
U4 + V3 = 2, |
||
|
|
|
|
|
|
|
|
U4 + V4 = 1. |
|
Положим U1 = 0, тогда
V1 = 5, V2 = 4, U2 = –3, U3 = –3, V3 = 4, U4 = –2, V4 = 3. |
||||
Подсчитаем ij для свободных клеток: |
||||
13 = 2 – (0 + 4) = –2, |
14 = |
5 |
– (0 + 3) = 2, |
|
21 = 6 – (– 3 + 5) = 4, |
23 = 1 – (–3 + 4) = 0, |
|||
24 = 3 – (–3 + 3) = 3, |
|
|
|
|
32 = 3 – (–3 + 4) = 2, |
34 = 8 – (–3 + 3) = 8, |
|||
41 = 6 – (–2 + 5) = 3, |
42 |
= 3 – (–2 + 4) = 1. |
||
Поскольку среди значений |
ij |
есть отрицательное, то план |
||
перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (1,3), перейти к новому плану.
|
V1 = 3 |
V2 = 4 |
V3 = 2 |
V4 = 1 |
|
Для занятых |
|||
|
5 |
|
4 |
2 |
|
5 |
|
клеток |
|
U1 = 0 |
|
20 |
|
|
10 |
|
|
30 |
|
|
|
|
|
|
U1 + V2 = 4, |
||||
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
6 |
|
1 |
|
1 |
|
3 |
|
|
U2 = -3 |
|
|
|
70 |
U1 + V3 = 2, |
||||
|
70 |
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
U2 + V2 = 1, |
U3 = -1 |
2 |
|
3 |
|
1 |
|
8 |
50 |
|
20 |
|
|
|
30 |
|
|
U3 + V1 = 2, |
||
|
|
|
|
|
|
|
|
|
|
U4 = 0 |
6 |
|
3 |
|
2 |
|
1 |
|
|
|
|
|
100 |
U3 + V3 = 1, |
|||||
|
|
|
30 |
|
70 |
||||
|
|
|
|||||||
|
20 |
90 |
|
70 |
|
70 |
|
U4 + V3 = 2, |
|
|
|
|
|
|
|
|
|
|
U4 + V4 = 1. |
|
|
|
|
140 |
|
|
|
||
Положим U1 = 0, тогда учитывая занятые клетки
V2 = 4, V3 = 2, U2 = –3, U3 = –1, V1 = 3, U4 = 0, V4 = 1.
Подсчитаем ij для свободных клеток:
11 = 5 – (0 + 3) = 2, |
14 |
= 5 |
– (0 + 1) |
= 4, |
21 = 6 – (– 3 + 3) = 6, |
23 = 1 – (–3 + 2) = 2, |
|||
24 = 3 – (–3 + 1) = 5, |
|
|
|
|
32 = 3 – (–1 + 4) = 0, |
34 = 8 – (–1 + 1) = 8, |
|||
41 = 6 – (0 + 3) = 3, |
42 |
= 3 |
– (0 + 4) |
= –1. |
Поскольку среди значений ij есть отрицательное, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (4,2), перейти к новому плану.
|
V1 = 3 |
V2 = 4 |
V3 = 2 |
V4 = 1 |
|
Для занятых |
|
|
5 |
4 |
2 |
5 |
|
клеток |
|
U1 = 0 |
|
|
30 |
|
30 |
||
|
|
|
U1 + V3 = 2, |
||||
|
|
|
|
|
|
||
|
6 |
1 |
1 |
3 |
|
||
U2 = -3 |
70 |
U2 + V2 = 1, |
|||||
|
70 |
|
|
||||
|
|
|
|
|
|
U3 + V1 = 2, |
|
U3 = -1 |
2 |
3 |
1 |
8 |
50 |
||
20 |
|
30 |
|
U3 + V3 = 1, |
|||
|
|
|
|
|
|
||
U4 = 0 |
6 |
3 |
2 |
1 |
|
||
100 |
U4 + V2 = 2, |
||||||
|
20 |
10 |
70 |
||||
|
20 |
90 |
70 |
70 |
|
U4 + V3 = 2, |
|
|
|
|
|
|
|
U4 + V4 = 1. |
Положим U1 = 0, тогда учитывая занятые клетки
V3 = 2, U3 = –1, U4 = 0, V1 = 3, V2 = 4, U2 = –3, V4 = 1.
Подсчитаем ij для свободных клеток:
11 = 5 – (0 + 3) = 2, |
12 = 4 – (0 + 4) = 0, |
14 = 5 – (0 + 1) = 4, |
|
21 = 6 – (– 3 + 3) = 6, |
23 = 1 – (–3 + 2) = 2, |
24 = 3 – (–3 + 1) = 5, |
|
32 = 3 – (–1 + 4) = 0, |
34 = 8 – (–1 + 1) = 8, |
41 = 6 – (0 + 3) = 3. |
|
Поскольку среди значений ij нет отрицательных, то найден оптимальный план перевозок.
f(х) = 30 2 + 70 1 + 20 2 + 30 1 + 20 3 + 10 2 + 70 1 = 350.
141
Решение транспортной задачи методом потенциалов, реализованным в ППП PRIMA показано на рис. 72 и 73.
Рис. 72. Заполнение диалоговой формы Транспортная задача
142
Рис. 73. Решение транспортной задачи в ППП PRIMA (начало)
143
Рис. 73. Решение транспортной задачи в ППП PRIMA (продолжение)
Этапы метода потенциалов:
1.Найти первоначальный опорный план. Число заполненных клеток равно m + n – 1.
2.Найти потенциалы Ui и Vj. Составить для базисных клеток m + n – 1 уравнений с m + n неизвестными.
144