Алгоритм поиска исходного базисного дерева.

При поиске исходного базисного дерева применяют описанный выше метод для следующей «искусственной» задачи.

Строим граф G =á E, V, H ñ, в котором E = E È{ i ₀}, где i ₀ – дополнительная вершина, V = V È V ₁È V ₂, где

V ₁ – множество дополнительных дуг, направленных от вершин – пунктов производства к дополнительной вершине i ₀,

V ₂ – множество дополнительных дуг, направляемых от i ₀ к промежуточным вершинам и вершинам–пунктам потребления.

Для v Î V полагаем c_v =0;

для v Î V ₁полагаем c_v =1;

для v Î V ₂ полагаем c_v =1.

Полагаем .

В качестве исходного базисного дерева берется подграф G =á E, V ₁ È V ₂, H ñ. Если в результате решения этой задачи оказалось, что оптимальное значение функционала строго больше нуля, то исходная задача(6.1) –(6.3) решения не имеет, в противном случае будет получено базисное дерево исходной задачи.

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

Рис. 6.1.

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

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

Стоимость перевозок по дугам задана следующей таблицей (каждая дуга задана парой инцидентных вершин).

Дуга v	v 3	v 2	v 1	v 11	v 10	v 4	v 5	v 7	v 6
cv
Дуга v	v 9	v 8	v 13	v 12	v 15	v 14	v 17	v 16	v 18
cv

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

Шаг 1.

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

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

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

u ₉:= 0;

u ₇= u ₉ – = – 3;

u ₈= u ₇ + = – 2;

u ₄= u ₇ – = – 7;

u ₅= u ₄ + = – 6;

u ₆= u ₅ + = – 5;

u ₃= u ₄ – = – 8;

u ₁= u ₄ – = – 9;

u ₂= u ₄ – = – 8;

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

На дуге v ₁₀ u ₇ > u ₂ + _, следовательно, дугу v ₁₀ вводим в базис. Возникший цикл (см. Рис. 6.2) обходим в направлении дуги v ₁₀.

Рис. 6.2

q; 1 – q; 6 – q;

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

Шаг 2.

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

3; 1; 7; 4; 5; 5; 6 – 1=5; 0; f =48.

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

u ₁= – 9; u ₂= – 8; u ₃= – 8; u ₄= – 7; u ₅= – 6; u ₆= – 5; u ₇= – 3; u ₈= – 2; u ₉:=0;

Проверим полученное решение на оптимальность. На дуге v ₆ u ₆ >u ₃ + , следовательно, решение не оптимально и дугу v ₆ вводим в базис. Возникший цикл обходим в направлении дуги v ₆,

= q; =7 – q; =5 – q; =5 – q;

q =min(7,5,5)=5. =0 дугу v ₁₂ выводим из базиса.

Шаг 3.

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

.

Определим потенциалы вершин u ₁= – 9; u ₂= – 8; u ₃= – 8; u ₄= – 7; u ₅= – 6; u ₆= – 6; u ₇= – 3; u ₈= – 2; u ₉:=0. Полученное решение оптимально. Дерево перевозок изображено на рис. 6.3. Стоимость перевозок составит:

Рис. 6.3

 

 

Самостоятельная работа 13.

Задание.

Определить объемы перевозок минимальной стоимости для графа, изображенного на рисунке примера, стоимости перевозок по вариантам приведены в таблице:

Номер

v 1

v 2

v 3

v 4

v 5

v 6

v 7

v 8

v 9

v 10

v 11

v 12

v 13

v 14

v 15

v 16

v 17

v 18