Имеются пункты … поставки однородного груза и пункты

Исходные данные (запасы, потребности и цены)
Поставщик Потребитель Запасы
В1
В2
В3 В4
A1
28
17
18
27 200
A2
18
16
27
32 250
A3
17
13
13
21 140
Потребность 190 100 120 110
Проверим, является ли задача закрытой:
a=200+250+140=590;
b= 190+100+120+110=520 .
a ≠ b → Транспортная задача является открытой, так как запас груза больше потребностей на 70 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B5.
Находим начальный базисный план методом минимальной стоимости.
x32 = min(140,100) = 100; x14 = min(120,110) = 110;
x33 = min(40,120) = 40; x15 = min(10,70) = 10;
x13 = min(200,80) = 80; x25 = min(60,60) = 60.
x21 = min(250,190) = 190;
Получим первый опорный план:
Начальный план
Поставщик Потребитель Запасы
В1
В2
В3 В4
В5
A1
28
17
18
27
0 200
80
110
10
A2
18
16
27
32
0 250
190
60
A3
17
13
13
21
0 140
100
40
Потребность 190 100 120 110 70
Таким образом, все потребности удовлетворены и все запасы исчерпаны. Проверим, является ли план, составленный методом минимального элемента опорным, т.е. число базисных (заполненных) клеток должно быть m+n-1 = 7. Действительно, решение является опорным, так как базисных клеток в таблице 7.
Стоимость перевозок составляет:
F(x) = 18*80 + 27*110 + 0*10 + 18*190 + 0*60 + 13*100 + 13*40 = 9650.
Решаем задачу методом потенциалов.
1-й этап.
Полагая потенциал U1 = 0, определяем остальные потенциалы из соотношения
, просматривая все занятые клетки.
Потенциалы:
u1 + v3 = 18; u1 = 0; v1 = 18;u1 + v4 = 27; u2 = 0; v2 = 18;
u1 + v5 = 0; u3 = -5; v3 = 18;u2 + v1 = 18; v4 = 27;u2 + v5 = 0; v5 = 0;
u3 + v2 = 13;
u3 + v3 = 13.
Определяем значения оценок, для всех свободных клеток:
.
Значения оценок
В1
В2
В3 В4
В5
A1 10 -1
A2
-2 9 5
A3 4
-1 5
Выделенные оценки отрицательны:
S12 = C12 – (V2 + U1) = -1;
S22 = C22 – (V2 + U2) = -2;
S34 = C34 – (V4 + U3) = -1.
Следовательно, решение (начальный план) не является оптимальным.
Оценка S22 = -2 является максимальной по модулю . Выберем для изменения плана клетку (2, 2).
Строим для этой клетки цикл, помечая клетки цикла знаками "плюс" и "минус".
План грузоперевозок
Поставщик Потребитель Потенциалы Ui
В1
В2
В3 В4
В5
A1
28
17 - 18
27 + 0 0
80
110
10
A2
18 + 16
27
32 - 0 0
190
60
A3
17 - 13 + 13
21
0 -5
100
40
Потенциалы Vj
18 18 18 27 0
Перемещаем по циклу груз величиной в t = min {60;80;100} = 60 единиц. В результате перемещения по циклу получим новый план.
Новый план грузоперевозок
Поставщик Потребитель Запасы
В1
В2
В3 В4
В5
A1
28
17
18
27
0 200
20
110
70
A2
18
16
27
32
0 250
190
60
A3
17
13
13
21
0 140
40
100
Потребность 190 100 120 110 70
Стоимость перевозок при этом = 9530.
Значение стоимости перевозок изменилось на 120 единиц, по сравнению с предыдущей стоимостью.
2-й этап.
Полагая потенциал U1 = 0, определяем остальные потенциалы из соотношения
, просматривая все занятые клетки.
Потенциалы:
u1 + v3 = 18; u1 = 0; v1 = 20;u1 + v4 = 27; u2 = -2; v2 = 18;
u1 + v5 = 0; u3 = -5; v3 = 18;u2 + v1 = 18; v4 = 27;u2 + v2 = 16; v5 = 0;
u3 + v2 = 13;
u3 + v3 = 13.
Определяем значения оценок, для всех свободных клеток:
.
Значения оценок
В1
В2
В3 В4
В5
A1 8 -1
A2
11 7 2
A3 2
-1 5
Выделенные оценки отрицательны:
S12 = C12 – (V2 + U1) = -1;
S34 = C34 – (V4 + U3) = -1.
Следовательно, решение не является оптимальным.
Оценки S12 и S34 равны. Следовательно, можем выбрать любую оценку. Выбираем оценку S12 и строим для этой клетки цикл.
План грузоперевозок
Поставщик Потребитель Потенциалы Ui
В1
В2
В3 В4
В5
A1
28 + 17 - 18
27
0 0
20
110
70
A2
18
16
27
32
0 -2
190
60
A3
17 - 13 + 13
21
0 -5
40
100
Потенциалы Vj
20 18 18 27 0
Перемещаем по циклу груз величиной в t = min {40;20} = 20 единиц. В результате перемещения по циклу получим новый план.
Новый план грузоперевозок
Поставщик Потребитель Запасы
В1
В2
В3 В4
В5
A1
28
17
18
27
0 200
20
110
70
A2
18
16
27
32
0 250
190
60
A3
17
13
13
21
0 140
20
120
Потребность 190 100 120 110 70
Стоимость перевозок при этом = 9510.
Значение стоимости перевозок изменилось на 20 единиц, по сравнению с предыдущей стоимостью.
3-й этап.
Полагая потенциал U1 = 0, определяем остальные потенциалы из соотношения
, просматривая все занятые клетки.
Потенциалы:
u1 + v2 = 17; u1 = 0; v1 = 19;u1 + v4 = 27; u2 = -1; v2 = 17;
u1 + v5 = 0; u3 = -4; v3 = 17;u2 + v1 = 18; v4 = 27;u2 + v2 = 16; v5 = 0;
u3 + v2 = 13;
u3 + v3 = 13.
Определяем значения оценок, для всех свободных клеток:
.
Значения оценок
В1
В2
В3 В4
В5
A1 9
1
A2
11 6 1
A3 2
-2 4
Выделенные оценки отрицательны: S34 = C34 – (V4 + U3) = -2.
Следовательно, решение не является оптимальным