Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ѕримеры решени€ транспортных задач




ѕример є1

”словие: —туденческие отр€ды —ќ-1, —ќ-2 и —ќ-3 численностью 70, 99 и 80 человек принимают участие в сельскохоз€йственных работах. ƒл€ уборки картофел€ на пол€х ѕ1, ѕ2, ѕ3 и ѕ4 необходимо выделить соответственно 47, 59, 49 и 43 человека. ѕроизводительность труда студентов зависит от урожайности картофел€, от численности отр€да и характеризуетс€ дл€ указанных отр€дов и полей в центнерах на человека за рабочий день и представлена в матрице:

 

—умма = 198

Bj Ai ѕ1 ѕ2 ѕ3 ѕ4
       
—ќ-1   3 7 2 5
—ќ-2   2 3 4 6
—ќ-3   6 4 3 5

 

—умма = 249

 

“ребуетс€:

1) –аспределить студентов по пол€м так, чтобы за рабочий день было собрано максимально возможное количество картофел€;

2) ќпределить, сколько центнеров картофел€ будет убрано с четырех полей при оптимальном распределении студентов

 

–ешение:

ѕровер€ем задачу на сбалансированность.

 

ќбщее количество человек в студенческих отр€дах на 51 больше требуемого общего количества человек дл€ уборки картофел€.

«адача €вл€етс€ не сбалансированной.

„тобы сбалансировать задачу, добавл€ем фиктивное картофельное поле, дл€ уборки которого нужно выделить 51 человека. ѕроизводительность труда студентов на фиктивном поле принимаем равной Ќ”Ћё.

 

—оставл€ем исходную таблицу

табл.1

—умма = 249

Bj Ai ѕ1 ѕ2 ѕ3 ѕ4 ѕ5
         
—ќ-1   3 7 2 5 0
—ќ-2   2 3 4 6 0
—ќ-3   6 4 3 5 0

—умма = 249

 

ќбозначени€:

ѕ5 Ц фиктивное картофельное поле;

ij Ц производительность труда студентов i -го —ќ на j Ц м картофельном поле;

Xij Ц количество студентов, направл€емое из i -го —ќ на j-ое картофельное поле;

Ui Ц условные оценки —ќ;

Vj Ц условные оценки картофельных полей

 

 

—оставл€ем математическую модель пр€мой и двойственной задач.

ћатематическа€ модель пр€мой задачи :

 

÷елева€ функци€ (на максимум)

—истема ограничений:

ћатематическа€ модель двойственной задачи.

–ешаем задачу по методу максимального элемента.

 

—оставл€ем опорный план (табл. 2)

“абл.2

Bj Ai ѕ1 ѕ2 ѕ3 ѕ4 ѕ5 Ui
         
—ќ-1   3 59 7 2 11 Ц W +W U1 =-1
5 0
—ќ-2   18 -W   49 32 +W 6   0 U2= 0
2 3 4
—ќ-3   29 +W       51 -W U3 =4
6 4 3 5 0
Vj V1 =2 V2 =8 V3 =4 V4 =6 V5 = -4 W=11

 

 

ѕровер€ем на вырожденность.

 

Z= m+n-1=3+5-1=7

Ѕазисных клеток 7. ѕлан не вырожден.

ѕровер€ем опорный план на оптимальность.

 

«адаем U2 = 0 и определ€ем значени€ потенциалов.

¬ычисл€ем оценки дл€ всех незаполненных клеток (Dij)

 

 

ќпорное решение не €вл€етс€ оптимальным, так как имеютс€ отрицательные оценки.

ѕереходим к следующему плану.

ƒл€ клетки (1,5) с наименьшей оценкой (-5) строим цикл. —тавим в эту клетку коэффициент W со знаком Ђ+ї и примен€€ метод наибольшего элемента находим цикл, (табл. 2). ќпредел€ем из цикла W =11

 

ќсуществл€ем сдвиг по циклу и строим следующий план (табл. 3)

.

“абл.3

Bj Ai ѕ1 ѕ2 ѕ3 ѕ4 ѕ5 Ui
         
—ќ-1   3 59 7 2   11 U1 =4
5 0
—ќ-2   7 -W   49 43 +W U2= 0
2 3 4 6 0
—ќ-3   40 +W       40 -W U3 =4
6 4 3 5 0
Vj V1 =2 V2 =3 V3 =4 V4 =6 V5 = -4  

 

 

ѕровер€ем план на оптимальность методом максимального элемента, как в п.«.

 

«адаем U2 = 0 и определ€ем значени€ потенциалов.

 

¬ычисл€ем оценки дл€ всех незаполненных клеток (Dij)

 

 

 

ќпредел€ем из цикла W=7

ќсуществл€ем сдвиг по циклу и строим следующий план (табл. 4).

“абл. 4

 

Bj Ai ѕ1 ѕ2 ѕ3 ѕ4 ѕ5 Ui
         
—ќ-1   3 59 7 2   11 U1 =0
5 0
—ќ-2   2 3 49 4 43 6 7 0 U2= 0
—ќ-3   47 6 4 3 5 33 0 U3 =0
Vj V1 =6 V2 =7 V3 =4 V4 =6 V5 = 0  

 

ѕровер€ем план на оптимальность методом максимального

элемента, как в п.«.

 

 

«адаем U2 = 0 и определ€ем значени€ потенциалов.

¬ычисл€ем оценки дл€ всех незаполненных клеток (Dij)

план табл. 4 оптимален.

 

ќпредел€ем значение целевой функции пр€мойидвойственной задачи:

 

»сход€ из первой теоремы двойственности в условии нашей задачи Zmax=Zmin=1149 (Z=ZТ) последний план оптимален

ќтвет:

1) „тобы за рабочий день было убрано максимально возможное количество картофел€, следует распределить студентов по пол€м следующим образом:

Ц »з —ќ-1 выделить 59 человек дл€ уборки картофел€ на втором поле ѕ2, а 11 человек останутс€ в —ќ;

Ц из —ќ-2 выделить 49 человек дл€ уборки картофел€ на ѕ« и 43 человека дл€ уборки картофел€ на ѕ4, а 7 человек останутс€ в —ќ;

Ц из —ќ-3 выделить 47 человек дл€ уборки картофел€ на ѕ1, а 33 человека оставить в —ќ.

2) ѕри данном оптимальном распределении студентов с четырех полей будет убрано 1149 центнеров картофел€.

 

 

ѕример є 2

ѕлан перевозок:

 

ѕоставщики јi ѕотребители ¬j:
  «апасы аi —ебестоимость ¬1 ¬2 ¬3 ¬4
       
ј1            
ј2            
ј3            

 

 

–ешение:

 

ѕровер€ем на сбалансированность

 

 

«адача не сбалансированна€. ¬ведем фиктивного потребител€ ¬5 с потребностью в грузе, равной 200 ед. —тоимость перевозки дл€ фиктивного потребител€ определим равной нулю.

¬ качестве общей стоимости будем брать сумму затрат на доставку единицы продукции из соответствующего пункта и ее себестоимость в этом пункте.





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 550 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

—амообман может довести до саморазрушени€. © Ќеизвестно
==> читать все изречени€...

1746 - | 1595 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.033 с.