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


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

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






Пример решения транспортной задачи





Задача. Поставщик товара – оптовые коммерческие предприятия А1, А2, А3, А4 имеют запасы товаров а1=280, а 2=350, а 3=415, а 4=255 единиц и розничные торговые предприятия В1, В2, В3 – подали заявки на закупку товара в объемах b1=620, b2=490, b3=150 единиц.

Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы матрицей перевозок:

4 17 7

C= 14 20 8

18 5 4

3 2 11

Найти такой план перевозки груза от поставщиков к потребителю, чтобы совокупные затраты на перевозку были минимальными.

Решение.

1) Проверим необходимое и достаточное условие разрешимости задачи:

280 + 350 + 415 + 255 = 1300

 

630+490+150 = 1260

 

> , следовательно, модель исходной

транспортной задачи является открытой.

Чтобы получить закрытую модель, введем фиктивного потребите­ля В4 с заявкой на Ь4=40 единиц товара. Тарифы перевозки для В4 по­лагаем равными нулю. Занесем данные в таблицу 16.

Табл. 16

 

bj a i        
         
         
         
         

 

2) Используя метод «северо-западного угла» построим первый опорный план.

Табл. 17

 

bj   a i        
  2804 -17 -7 -0
  34014 1020 -8 -0
  -18 4155 -4 -0
  2553 652 15011 400

 

Число занятых клеток - 7, а должно быть т+п-1=4+4-1=7. Следо­вательно, опорный план является невырожденным. Значение целевой функции плана 1:

F ()= 280∙4+340∙14+10∙20 + 415∙5+65∙2+150∙ 11 + 40∙ 0 = 9935

 

3) Проверим оптимальность плана 1 для этого дополним таб­лицу 17 столбцом и строкой потенциалами.

 

Табл. 18

 

bj   a i         ui
  2804 -17 -7 -0 u1=0
  34014 1020 -8 -0 u2=10
  -18 4155 -4 -0 u3= - 5
  2553 652 15011 400 u4= - 8
v j v 1=0 v 2=10 v 3=19 v 4=8  

 

 

Найдем потенциалы по занятым клеткам uj + ui = cij и занесем в таблицу 18.

u1+ v 1=4 ] u1=0

u2+ v 1=14 v 1=4

u2+ v 2=20 u2=10

u3+ v 2=5 v 2=10

u4+ v 2=2 u3=-5

u4+ v 3=11 u4=-8

u4+ v 4=0 v 3=19

v4 =8

Оценим пустые клетки ij=cij – (ui + v j).

12=17 – (0+10) = 7

13=7 – (0+19) = - 12

14=0 – (0+8) = - 8

23= 8 – (10+9) = - 21

24=0 - (10+8)= - 18

31=18– (-5 – 4) =19

33=4 – (-5 +19) = -10

34=0- (-5+8) = -3

44=3 – (-8 +4) =7

Первый опорный план не является оптимальным, т.к. среди этих оце­нок есть отрицательные, поэтому переходим к улучшению плана 1 .

4) «Худшую» оценку 23= - 21 имеет клетка (2,3). Построим для нее цикл перераспределения груза.

 

 

10 0 0 10

+

 

 

65 150 75 140

+

В результате получим новый опорный план 2 :

Табл. 19

 

bj   a i         ui
  2804 -17 -7 -0 u1=0
  34014 -20 108 -0 u2=10
  -18 4155 -4 -0 u3= 16
  -3 752 14011 400 u4= 13
v j v 1=4 v 2=-11 v 3=-2 v 4=-13  

 

F () = 280∙4 + 340∙14 + 10∙8 + 415∙5 + 75∙2 + 140∙ll + 40∙0 = 9725

5) Проверим план 2 на оптимальность.

Оценим занятые клетки, дополним таблицу 19.

u1+ v 1=4 ] u1=0

u2+ v 1=14 v 1=4

u2+ v 3=8 u2=10

u3+ v 2=5 v 3=

u4+ v 2=2 u4=13

u4+ v 3=11 v 2= - 11

u4+ v 4=0 u3=16

v4 = - 13

Оценим пустые клетки.

12=17 – (0 - 11) = 28

13=7 – (0- 2) = 9

14=0 – (0- 13) = 13

22= 20 – (10- 11) = 21

24=0 - (10 - 13)= 3

31=18– (16 + 4) = - 2

33=4 – (16 - 2) = -10

34=0- (16 - 13) = -3

44=3 – (13 +4) = - 14

 

Второй опорный план 2 так же не является оптимальным, продолжаем его улучшать.

 

6) Перезагрузим «худшую» клетку (4,1).

 

340 10 200 150

+

 

 

0 140 140 0

+ −

 

В результате получим новый опорный план 2:

 

Табл. 20

 

bj   a i         ui
  2804 -17 -7 -0 u1=0
  20014 -20 1508 -0 u2=10
  -18 4155 -4 -0 u3= 3
  1403 752 -11 400 u4= - 1
v j v 1=4 v 2=3 v 3=-2 v 4=1  

 

F ( 3) =280∙4 + 200∙14 + 150∙8 + 415∙5 + 140∙3 + 75∙2 + 40∙0 = 7765

7) Проверим план 3 на оптимальность.

Оценим занятые клетки, дополним таблицу 20.

 

u1+ v 1=4 ] u1=0

u2+ v 1=14 v 1=4

u2+ v 3=8 u2=10

u3+ v 2=5 v 3=

u4+ v 1=3 u4= - 1

u4+ v 2=2 v 2= 3

u4+ v 4=0 u3=3

v4 = 1

Оценим пустые клетки.

12=17 – (0 +3) = 14

13=7 – (0- 2) = 9

14=0 – (0+1) = - 1

22= 20 – (10+3) = 7

24=0 - (10 +1) = - 11

31=18– (3+ 4) = 11

33=4 – (3 - 2) = 3

34=0- (3 +1) = - 4

44=3 – (- 1 - 2) = 6

 

План 3 не является оптимальным.

 

 

8) Перезагрузим клетку (2,4).

200 0 160 40

+

 

 

140 40 180 0

+ −

Получим новый план 4.

Табл. 21

 

bj   a i         ui
  2804 -17 -7 -0 u1=0
  16014 -20 1508 400 u2=10
  -18 4155 -4 -0 u3= 2
  1803 752 -11 -0 u4= - 1
v j v 1=4 v 2=3 v 3=-2 v 4=-10  

 

 

F ( 4) = 280∙4+160∙14 + 150∙8 + 40∙0+415∙5 + 180∙3 + 75∙2 = 7325

9) Проверим план 4 на оптимальность.

Для занятых клеток:

u1+ v 1=4 ] u1=0

u2+ v 1=14 v 1=4

u2+ v 3=8 u2=10

u2+ v 4=0 v 3= -2

u3+ v 2=5 v 4= -10

u4+ v 1=3 u4= -1

u4+ v 2=2 v 2=3

u 3 = 2

Для пустых клеток:

12=17 – (0 +3) = 14

13=7 – (0- 2) = 9

14=0 – (0 - 10) = 10

22= 20 – (10+3) = 7

31=18– (2+ 4) = 12

33=4 – (2 - 2) = 4

34=0- (2 - 10) = 8

43=11- (- 1 - 2) = 14

44=0– (- 1 - 10) =11

Поскольку все оценки не отрицательны, то план оптимален.

280 0 0

160 0 150

опт.= 0 415 0

180 75 0

 

F опт.( 4) = 7325 тысяч рублей.

 

Анализ плана. Первому поставщику A1 следует весь товар отпра­вить первому заказчику B1, второй поставщик А2 должен отправить 160 ед. товара первому заказчику B1 и 150 ед. товара - третьему заказ­чику В3, третий поставщик А 3 отправит весь товар заказчику В2, а четвертый поставщик А4 отправит 180 ед. товара заказчику B1 и 75 ед. товара - заказчику В2. При этом плане 40 ед. товара второго постав­щика А2 остается нереализованным. Общая стоимость доставки това­ра заказчикам будет минимальной и составляет 7325 тысяч рублей.

Так как среди последних оценок - все строго положительные, то данный оптимальный план является единственным.

Замечание. Алгоритм и методы решения транспортной задачи мо­гут быть использованы при решении многих экономических задач, не имеющих отношение к транспортировке грузов.

 

 

Date: 2015-12-12; view: 433; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию