Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Задача II. Решить ТЗ с открытой моделью, если дана матрица планирования перевозок:






 

Решить ТЗ с открытой моделью, если дана матрица планирования перевозок:

 

           
           
           
           
           

 

Решение:

а). Установим характер задачи:

 

, итак

> Þ

 

модель задачи открытая, значит, вводим фиктивный пункт отправления А5 с запасами груза a5= - = 120 - 115=5, а тарифы перевозки этого груза будут С51=С52=С53=С54= С55=0.

Составляем распределительную таблицу по методу " минимального элемента":

 

  B1 B2 B3 B4 B5 ai
A1            
A2            
A3            
A4            
A5            
bj            

 

Итак, получили план X1. Суммарные расходы на перевозку зерна составляют:

 

Z(X1) =24× 6+11× 30+14× 29+26× 21+4× 5+20× 28+1× 1+15× 14+5× 0 =

= 144+330+406+546+20+560+1+210=2217 руб.

 

б). Построение нового улучшенного опорного плана по методу потенциалов.

Рассмотрим опорный план, найденный по методу “минимального элемента”.

 

  B1 B2 B3 B4 B5 ai ui
A1   - 30 25 + 25        
A2 + 5 19   - 21       - 4
A3             - 20
A4             - 6
A5 - 0 + 0           - 9
bj              
uj              

 

Проверяем условие m+n-1=5+5-1=9, число занятых клеток удовлетворяет этому условию.

Определяем потенциалы и находим оценки свободных клеток:

 

S11=-3 S25=-4 S41=16 S52=-21

S14=-1 S31=29 S42=-1 S53=-16

S15=-6 S32=12 S43=-11 S54=-1

S22=3 S34=40 S45=-1 S55=-12

S52 - наименьшая оценка.

 

С вершиной в клетке (5;

2) строим замкнутый цикл.

Найдем l=min(5; 16; 25) =5, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

 

  B1 B2 B3 B4 B5 ai ui
A1              
A2     - 21 11 + 4     - 4
A3             - 20
A4     + 8   - 2     - 6
A5             - 30
bj              
uj              

 

Определяем потенциалы и находим оценки свободных клеток:

 

S11=-3 S25=-4 S41=16 S51=21

S14=-1 S31=29 S42=-1 S53=5

S15=-6 S32=12 S43=-11 S54=22

S22=3 S34=40 S45=-1 S55=9

S43 - наименьшая оценка. С вершиной в клетке (4;

 

3) строим замкнутый цикл. Найдем l=min(11; 15) =11, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

  B1 B2 B3 B4 B5 ai ui
A1 + 6 -   - 25        
A2 - 5   - + 4     - 15
A3             - 20
A4     + 8 - 2     - 17
A5             - 30
bj              
uj              

 

Определяем потенциалы и находим оценки свободных клеток:

 

S11=-14 S23=11 S34=29 S51=10

S14=-12 S25=7 S41=16 S53=5

S15=-6 S31=18 S42=10 S54=11

S22=14 S32=12 S45=10 S55=9

S11 - наименьшая оценка. С вершиной в клетке (1;

 

1) строим замкнутый цикл. Найдем l=min(24; 15;

4) =4.

 

  B1 B2 B3 B4 B5 ai ui
A1 + 6 4   - 25        
A2 - 5   -   + 13     - 1
A3     + 5   - 1   - 20
A4             - 17
A5             - 30
bj              
uj              

 

Определяем потенциалы и находим оценки свободных клеток:

 

S14=2 S25=-7 S41=30 S51=24

S15=-6 S31=32 S42=10 S53=5

S22=0 S32=12 S44=14 S54=25

S23=-3 S34=43 S45=10 S55=9

S25 - наименьшая оценка. С вершиной в клетке (2;

 

5) строим замкнутый цикл. Найдем l=min(20; 11; 21) =11.

 

  B1 B2 B3 B4 B5 ai ui
A1              
A2             - 1
A3             - 13
A4             - 10
A5             - 30
bj              
uj              

 

Определяем потенциалы и находим оценки свободных клеток:

 

S13=7 S23=4 S41=23 S51=24

S14=2 S31=25 S42=3 S53=12

S15=1 S32=39 S44=7 S54=25

S22=0 S34=36 S45=10 S55=16

Так как все Sij> 0, то план оптимальный и единственный. Затраты на перевозки по оптимальному плану составляют:

 

min Z=15× 6+20× 30+9× 5+20× 4+11× 13+15× 5+10× 1+15× 8+5× 0=

=90+600+45+80+143+75+10+120+0=1163 руб.

 

Ответ: затраты на перевозки по оптимальному плану составляют 1163 рубля.

 

Тестовая база


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.01 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал