652. Дана транспортная задача в сетевой постановке. Задача изображена в виде неориентированного связного графа. На ребрах записаны значения удельных стоимостей сi, на вершинах (кружках) значения запасов-потребностей bi.
6
-30
Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
9
-28
18
12
37
4
-22
3
8
0
1
-10
7 2 10
10
43
1
3
-20
3 2
23
12 4 3 30
24 1 20
11
35
13
42
7
23
5
-40
2
-30
16 3
15 6
Решение:
Пронумеруем вершины слева направо. Из 11 пункта все 37 единиц отправим в пункт 10.
6
-30
9
-28
α11=0
18
12
37
30
4
-22
3 28
8
0
77 99
1
-10
7 2 10 37
10
43
1 52
3
-20
3 67 2
23
12 4 3 77 30
47
24 1 20
11
35
13
42
7
23
5
-40
2
-30
30 23 16 42 3
15 6
Из пункта 10 28 единиц отправляем в пункт 9, а 52 единицы – в пункт 8. Из пункта 8 30 единиц отправляем в пункт 6, а остальные в пункт 4 (22 единицы). И так продолжаем пока все грузы не будут вывезены, а все потребности не удовлетворены, с учетом того, что выбираем ребра с наименьшей стоимостью.
Получили 1-й допустимый опорный план (все грузы вывезены и все потребности удовлетворены). Значение функции, которое соответствует построенному плану равно:
f =2*37+1*52+10*28+3*30+3*42+3*77+6*23+2*98+7*77+3*67+1*47+15*30= =2516.
Проверим план на оптимальность методом потенциалов.
Вычислим потенциалы. Для вершины α12=0. Затем, двигаясь по базисным ребрам, вычисляем потенциалы других вершин:
α10=0+2=2 α9=2+10=12 α8=2+1=3
Коммуникация (8,11) также является базисной, но здесь перевозка направлена из 11 вершины в 8, поэтому для определения искомого потенциала необходимо из известного потенциала вычесть тариф
α11= 3–3=0 α13=0 – 3 = -3 α6=3+3=6 α4=3+2=5 α1=5+7=12 α3=12+3=15 α5=15+1=16 α2=16+15=31 α7=16-6=10.
После вычисления потенциалов находим оценки для небазисных ребер (12,13), (10,11), (7,11), (7,8), (6,9), (4,7), (4,5), (2;3).
γ2,3 =|15-31|-24=-8 γ4,5 =|16-5|-23=-12
γ4,7 =|10-5|-12=-5 γ6,9 =|12-6|-18=-12
γ7,8 =|3-10|-4=3 γ7,11 =|0-10|-16=-6
γ10,11 =|0-2|-20=-18 γ12,13 =|-3-0|-30=-27
План не оптимален, так как есть положительная оценка. Строим новый опорный план.
6
-30
9
-28
α12=0
18
12
37
30
4
-22
3 28
8
0
10 32
1
-10
7 2 10 37
10
43
1 52
3
-20
3 2
23
12 4 3 77 30
67
24 1 20 20
11
35
13
42
7
23
5
-40
2
-30
30 90 16 42 3
15 6
f =2*37+1*52+10*28+3*30+3*42+3*77+4*47+6*70+15*30+2*52+7*30+3*20 = =2265.
Проверим план на оптимальность методом потенциалов.
Вычислим потенциалы. Для вершины α12=0. Затем, двигаясь по базисным ребрам, вычисляем потенциалы других вершин:
α10=0+2=2 α9=2+10=12 α8=2+1=3
Коммуникация (8,11) также является базисной, но здесь перевозка направлена из 11 вершины в 8, поэтому для определения искомого потенциала необходимо из известного потенциала вычесть тариф
α11= 3–3=0 α13=0 – 3 = -3 α6=3+3=6 α4=3+2=5 α1=5+7=12 α7=3+4=7 α5=7+5=12 α2=12+15=27 α3=12+1=13.
После вычисления потенциалов находим оценки для небазисных ребер (12,13), (10,11), (7,11), (6,9), (4,7), (4,5), (2;3), (1,3).
γ1,3 =|12-13|-3=-2 γ2,3 =|12-27|-24=-9
γ4,5 =|12-5|-23=-16 γ4,7 =|7-5|-12=-10
γ6,9 =|12-6|-18=-12 γ7,11 =|0-7|-16=-9
γ10,11 =|0-2|-20=-18 γ12,13 =|-3-0|-30=-27
План оптимален, так как все оценки отрицательны.
