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

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

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

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

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

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

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

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


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

Часть 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 тыс. ц., а в В2 110 тыс. ц. из района А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 0
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 0
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=4 S32=7

S15=11 S23=8 S31=3 S34=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 0
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=1 S32=4

S15=14 S23=8 S31=3 S34=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

0

5

0


0


0


0


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 0
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


0


0


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 0
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

0


0

5

0


0


0


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 0
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

0


0

5

0


0


0


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 0
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

0


0

5

0


0


0


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 0
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

0


0

5

0


0


0


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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: