ТОП 10:

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



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

Строим граф GE,V,Hñ, в котором E=EÈ{i0}, где i0 – дополнительная вершина, V=VÈV1ÈV2, где

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

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

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

для vÎV1полагаем cv=1;

для vÎV2 полагаем cv=1.

Полагаем.

В качестве исходного базисного дерева берется подграф GE,V1ÈV2, Hñ. Если в результате решения этой задачи оказалось, что оптимальное значение функционала строго больше нуля, то исходная задача(6.1) –(6.3) решения не имеет, в противном случае будет получено базисное дерево исходной задачи.

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

Рис. 6.1.

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

b1=3; b2=1; b3=7; b4=0; b5=0; b6=5; b7=2; b8=4; b9=0.

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

Дуга v v3 v2 v1 v11 v10 v4 v5 v7 v6
cv
Дуга v v9 v8 v13 v12 v15 v14 v17 v16 v18
cv

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

Шаг 1.

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

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

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

u9:= 0;

u7= u9 = 3;

u8= u7+ = 2;

u4= u7 = 7;

u5= u4+ = 6;

u6= u5+ = 5;

u3= u4 = 8;

u1= u4 = 9;

u2= u4 = 8;

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

На дуге v10 u7 > u2+ , следовательно, дугу v10 вводим в базис. Возникший цикл (см. Рис. 6.2) обходим в направлении дуги v10.

Рис. 6.2

q ; 1 – q ; 6 – q ;

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

Шаг 2.

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

3; 1; 7; 4; 5; 5; 61=5; 0; f=48.

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

u1=9; u2=8; u3=8; u4=7; u5=6; u6=5; u7=3; u8=2; u9:=0;

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

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

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

Шаг 3.

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

.

Определим потенциалы вершин u1=9; u2=8; u3=8; u4=7; u5=6; u6=6; u7=3; u8=2; u9:=0. Полученное решение оптимально. Дерево перевозок изображено на рис. 6.3. Стоимость перевозок составит:

Рис. 6.3

 

 

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

Задание.

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

Номер v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18

 







Последнее изменение этой страницы: 2016-06-29; Нарушение авторского права страницы

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.234.254.115 (0.006 с.)