Лабораторная работа 12. Решение транспортной задачи в сетевой постановке

Решим задачу, представленной графом, изображенным на рис. 5. 1.

 

-1 4

2 8

-3 0 2

1 4 7

0

5

3 6 9

-7 5 0

Рис. 5.1.

 

Вершины графа обозначены цифрами от 1 до 9, обведенными к кружочек. Рядом с каждой вершиной проставлены мощности вершин:

b₁=-3; b₂=-1; b₃=-7; b₄=0; b₅=0; b₆=5; b₇=2; b₈=4; b₉=0.

 

 

Стоимость перевозок задана таблицей 1.

Таблица 1

с12	с14	с13	с28	с27	с24	с34	с35	с36	с47	с45	с57	с56	с59	с69	с78	с79	с89
1	2	1	6	1	1	1	2	2	4	1	3	1	7	6	1	3	2

За исходный базис примем дерево, дуги которого выделены жирной линией (см. Рис. 1).

Шаг 1.

Определим объем перевозок для исходного базисного дерева.

x₁₄ =3; x₂₄=1; x₃₄=7; x₇₈=4; x₅₆=5;

x₄₅=5; x₄₇=2+0+4=6; x₇₉=0.

Общая стоимость перевозок составит

f(X) = c₁₄ ´ x₁₄ + c₂₄ ´ x₂₄ + c₃₄ ´ x₃₄ + c₇₈ ´ X₇₈+

+ c₅₆ ´ x₅₆+ c₄₅ ´ x₄₅ + c₄₇ ´ x₄₇ + c₇₉ ´ x₇₉= 52

Определим потенциалы вершин:

u₉: =0;

u₇= u₉ -c₇₉= - 3;

u₈= u₇ + c₇₈ =-2;

u₄=u₇ - c₄₇ =-7;

u₅ =u₄ + c₄₅ =-6;

u₆= u₅ + c₅₆ =-5;

u₃= u₄ - c₃₄ =-8;

u₁= u₄ - c₁₄ =-9;

u₂= u₄ - c₂₄ =-8;

Проверим полученное решение на оптимальность:

На дуге (2, 7) u₇ > u₂ + c_27, следовательно, дугу (2, 7) вводим в базис. Возникший цикл (см. Рис.5. 2) обходим в направлении дуги (2, 7).

-1 4

2 8

-3 0 2

1 4 7

0

5

3 6 9

-7 5 0

Рис. 5.2

x₂₇ = q; x₂₄ = 1 - q; x₄₇ = 6 - q;

q = min (1, 6)=1; x₂₄ =0 дугу (2, 4) выводим из базиса.

Шаг 2.

Пересчитаем объем перевозок для нового базиса:

x₁₄ =3; x₂₇=1; x₃₄=7; x₇₈=4;

x₅₆=5; x₄₅=5; x₄₇=6 -1 = 5; x₇₉=0;

f(X)=48.

Определим потенциалы вершин.

u₁=-9;

u₂=-8;

u₃=-8;

u₄=-7;

u₅=-6;

u₆=-5;

u₇=-3;

u₈=-2;

u₉: =0;

 

Проверим полученное решение на оптимальность:

На дуге (3, 6) u₆ > u₃ + c₃₆ Следовательно, дугу (3, 6) вводим в базис.

 

Возникший цикл обходим в направлении дуги (3, 6),

x₃₆ = q; x₃₄ = 7 - q; x₄₅ = 5 - q; x₅₆ = 5 - q;

q = min (7, 5, 5)=5. x₅₆ =0 дугу (5, 6) выводим из базиса.

Шаг 3.

Пересчитаем объем перевозок для нового базиса:

x₁₄ = 3; x₂₇=1; x₃₄=7-5=2;

x₇₈= 4; x₃₆=5; x₄₅=5-5=0; x₄₇=5; x₇₉=0

Определим потенциалы вершин.

u₁=-9;

u₂=-8;

u₃=-8;

u₄=-7;

u₅=-6;

u₆=-6;

u₇=-3;

u₈=-2;

u₉: =0;

 

Полученное решение оптимально.

Дерево перевозок изображено на рис.3.

Стоимость перевозок составит:

L(x)=x₁₄c₁₄ + x₂₇c₂₇+ x₃₄c₃₄+ x₇₈c₇₈+ x₃₆c₃₆+ x₄₅c₄₅+ x₄₇c₄₇+ x₇₉c₇₉₌43

-1 4

2 8

-3 0 2

1 4 7

0

5

3 6 9

-7 5 0

Рис. 5.3