Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Лабораторная работа 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, обведенными к кружочек. Рядом с каждой вершиной проставлены мощности вершин:

b1=-3; b2=-1; b3=-7; b4=0; b5=0; b6=5; b7=2; b8=4; b9=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.

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

x14 =3; x24=1; x34=7; x78=4; x56=5;

x45=5; x47=2+0+4=6; x79=0.

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

f(X) = c14 ´ x14 + c24 ´ x24 + c34 ´ x34 + c78 ´ X78+

+ c56 ´ x56+ c45 ´ x45 + c47 ´ x47 + c79 ´ x79= 52

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

u9: =0;

u7= u9 -c79= - 3;

u8= u7 + c78 =-2;

u4=u7 - c47 =-7;

u5 =u4 + c45 =-6;

u6= u5 + c56 =-5;

u3= u4 - c34 =-8;

u1= u4 - c14 =-9;

u2= u4 - c24 =-8;

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

На дуге (2, 7) u7 > u2 + c27, следовательно, дугу (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

x27 = q; x24 = 1 - q; x47 = 6 - q;

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

Шаг 2.

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

x14 =3; x27=1; x34=7; x78=4;

x56=5; x45=5; x47=6 -1 = 5; x79=0;

f(X)=48.

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


u1=-9;

u2=-8;

u3=-8;

u4=-7;

u5=-6;

u6=-5;

u7=-3;

u8=-2;

u9: =0;


 

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

На дуге (3, 6) u6 > u3 + c36 Следовательно, дугу (3, 6) вводим в базис.

 

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

x36 = q; x34 = 7 - q; x45 = 5 - q; x56 = 5 - q;

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

Шаг 3.

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

x14 = 3; x27=1; x34=7-5=2;

x78= 4; x36=5; x45=5-5=0; x47=5; x79=0

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


u1=-9;

u2=-8;

u3=-8;

u4=-7;

u5=-6;

u6=-6;

u7=-3;

u8=-2;

u9: =0;


 

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

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

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

L(x)=x14c14 + x27c27+ x34c34+ x78c78+ x36c36+ x45c45+ x47c47+ x79c79=43

-1 4

2 8

           
   
 
   
 
 


-3 0 2

1 4 7

               
   
   
     
 
 
 
 


0

5

           
   
     


3 6 9

-7 5 0

Рис. 5.3







Дата добавления: 2014-12-06; просмотров: 658. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...


Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...


Вычисление основной дактилоскопической формулы Вычислением основной дактоформулы обычно занимается следователь. Для этого все десять пальцев разбиваются на пять пар...

Уравнение волны. Уравнение плоской гармонической волны. Волновое уравнение. Уравнение сферической волны Уравнением упругой волны называют функцию , которая определяет смещение любой частицы среды с координатами относительно своего положения равновесия в произвольный момент времени t...

Медицинская документация родильного дома Учетные формы родильного дома № 111/у Индивидуальная карта беременной и родильницы № 113/у Обменная карта родильного дома...

Основные разделы работы участкового врача-педиатра Ведущей фигурой в организации внебольничной помощи детям является участковый врач-педиатр детской городской поликлиники...

Гносеологический оптимизм, скептицизм, агностицизм.разновидности агностицизма Позицию Агностицизм защищает и критический реализм. Один из главных представителей этого направления...

Функциональные обязанности медсестры отделения реанимации · Медсестра отделения реанимации обязана осуществлять лечебно-профилактический и гигиенический уход за пациентами...

Определение трудоемкости работ и затрат машинного времени На основании ведомости объемов работ по объекту и норм времени ГЭСН составляется ведомость подсчёта трудоёмкости, затрат машинного времени, потребности в конструкциях, изделиях и материалах (табл...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия