Реферат: Транспортная задача

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

Высшего профессионального образования

«Волгоградский государственный технический университет»

Камышинский технологический институт (филиал)

Волгоградского государственного технического университета

Кафедра «Высшей математики»

Типовой расчет

Часть III

по дисциплине: «Экономико-математические методы»

на тему:

«Транспортная задача»

Выполнила:

студентка гр. КБА-081(вво)

Титова Мария Дмитриевна

Проверила:

Старший преподаватель каф. ВМ

Мягкова Светлана Васильевна

Камышин — 2009 г.

Задача I

Составитьплан перевозок зерна из районов А1, А2, А3, запасы которых составляютсоответственно 250, 150 и 100 тыс. ц. в 5 пунктов В1, В2, В3, В4, В5,потребности которых 70, 110, 90, 130, 100 тыс. ц. Затраты на перевозку 1 тыс. ц.зерна приведены в таблице.

В1 В2 В3 В4 В5 А1 4 11 6 5 15 А2 8 7 9 13 10 А3 10 5 12 7 20

Минимизироватьобщие затраты на реализацию плана перевозок.

Решение:

а). Метод“северо-западного угла”. Установим характер задачи:

/> />, итак

/> /> Þ модель задачи закрытая.

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

B1 B2 B3 B4 B5 ai A1

10

70

4

110

6

70

8 20 250 A2 5 11

12

20

7

130

4 150 A3 9 7 15 10

5

100

100 bj 70 110 90 130 100

500

500

Итак,получили план X1 такой, что в пункт В1 надо отправить зерна 70 тыс. ц., а в В2110 тыс. ц. из района А1. В пункт В3 70 тыс. ц. из района А1 и 20 тыс. ц. израйона А2. В пункт В4 130 тыс. ц. из района А2 и наконец в пункт В5 100 тыс. циз района А3. Суммарные расходы на перевозку зерна составляют:

Z(X1) =70×10+110×4+70×6+20×12+130×7+100×5=

=700+440+420+240+910+500=3210 руб.

б). Метод “минимального элемента “. Составим распределительную таблицу:

B1 B2 B3 B4 B5 ai A1

10

10

4

110

6

8

130

20 250 A2

5

50

11 12 7

4

100

150 A3

9

10

7

5

90

10 5 100 bj 70 110 90 130 100

500

500

В результатеполного распределения зерна получаем план X2, для которого значение целевойфункции:

Z(X2) =10×10+110×4+130×8+50×5+100×4+10×9+90×5=

=100+440+1040+250+400+90+450=2770руб.

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

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

B1 B2 B3 B4 B5 ai ui A1

10

10

4

110

6

8

130

20 250 A2

+ 5

/>50

11 12 7

— 4

100

150  - 5 A3

— 9

10

7

5

90

10 + 5 100  - 1 bj 70 110 90 130 100

500

500

uj 10 4 6 8 9

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

Дляопределения потенциалов составляем уравнения:

u1+u1=10 Пусть u1=0, тогда u1=10

u1+u2=4 u2=4

u1+u4=8 u4=8

u2+u1=5 u2=5-10=-5

u2+u5=4 u5=4-(-5) =9

u3+u1=9 u3=9-10=-1

u3+u3=5 u3=5-(-1) =6

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

S13=6-(6+0) =0 S23=12-(6-5) =11 S34=10-(8-1) =4

S15=20-(9+0) =11 S24=7-(8-5) =4 S35=5-(9-1) =-3

S22=11-(4-5) =12 S32=7-(4-1) =4

Так как невсе Sij³0, то план не оптимальный.Наиболее перспективной клеткой является клетка (3;

5), так какS35 — наименьшая. С вершиной в клетке (3;

5) строимзамкнутый цикл. В него войдут вершины: (3;

5), (3;

1), (2;

1), (2;

5).

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

B1 B2 B3 B4 B5 ai ui A1

— 10

/>10

4

110

+ 6

8

130

20 250 A2

+ 5

60

11

/>12

7

— 4

90

150  - 5 A3 9 7

— 5

90

10

+ 5

10

100  - 4 bj 70 110 90 130 100

500

500

uj 10 4 9 8 9

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

S13=-3 S22=12 S24=4S32=7

S15=11 S23=8 S31=3S34=6

Так как невсе Sij³0, то план не оптимальный.Наиболее перспективной клеткой является клетка (1;

3), так какS13 — наименьшая. С вершиной в клетке (1;

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

Найдем l=min(90; 90;

10) =10,после пересчета получим новый цикл. Заменяя старый цикл на новый, получимследующую таблицу:

Таблица.

B1 B2 B3 B4 B5 ai ui A1 10

4

110

6

10

8

130

20 250 A2

5

70

11 12 7

4

80

150  - 2 A3 9 7

5

80

10

5

20

100  - 1 bj 70 110 90 130 100

500

500

uj 7 4 6 8 6

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

S11=3 S22=9 S24=1S32=4

S15=14 S23=8 S31=3S34=3

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

min Z=110×4+10×6+130×8+70×5+80×4+80×5+20×5=

=440+60+1040+350+320+400+100=2710руб.

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

Задача II

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

 6  30  25  7  15  35  5  29  21  4  13  40  18  22  5  28  1  25  19  23  8  2  14  15  24  25  30  20  21

Решение:

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

/> />, итак

/> > /> Þ

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

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

B1 B2 B3 B4 B5 ai A1 6

30

25

25

10

7 15 35 A2

5

19

29

21

16

4

5

13 40 A3 18 22

5

4

28

1

21

25 A4 19 23 8

2

15

14 15 A5

5

5 bj 24 25 30 20 21

120

120

Итак, получили план 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 6

— 30

/>25

+ 25

10

7 15 35 A2

+ 5

/>19

29

— 21

16

4

5

13 40  - 4 A3 18 22

5

4

28

1

21

25  - 20 A4 19 23 8

2

15

14 15  - 6 A5

— 0

5

+ 0 5  - 9 bj 24 25 30 20 21

120

120

uj 9 30 25 8 21

Проверяем условие 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 6

30

20

25

15

7 15 35 A2

5

24

29

— 21

/>11

+ 4

5

13 40  - 4 A3 18 22

5

4

28

1

21

25  - 20 A4 19 23 + 8

— 2

15

14 15  - 6 A5

5

5  - 30 bj 24 25 30 20 21

120

120

uj 9 30 25 8 21

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

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

/>-

30

20

— 25

15

7 15 35 A2

— 5

24

29

21

/>-

+ 4

16

13 40  - 15 A3 18 22

5

4

28

1

21

25  - 20 A4 19 23

+ 8

11

— 2

4

14 15  - 17 A5

5

5  - 30 bj 24 25 30 20 21

120

120

uj 20 30 25 19 21

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

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

30

20

— 25

11

7 15 35 A2

— 5

20

29

21

/>-

4

20

+ 13 40  - 1 A3 18 22

+ 5

4

28

— 1

21

25  - 20 A4 19 23

8

15

2 14 15  - 17 A5

5

5  - 30 bj 24 25 30 20 21

120

120

uj 6 30 25 5 21

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

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

6

15

30

20

25 7 15 35 A2

5

9

29 21

4

20

13

11

40  - 1 A3 18 22

5

15

28

1

10

25  - 13 A4 19 23

8

15

2 14 15  - 10 A5

5

5  - 30 bj 24 25 30 20 21

120

120

uj 6 30 18 5 14

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

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 рубля.