Задача

Задача на тему Транспортная задача

Работа добавлена на сайт bukvasha.net: 2014-11-09

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

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 8.11.2024


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
Высшего профессионального образования
"Волгоградский государственный технический университет"
Камышинский технологический институт (филиал)
Волгоградского государственного технического университета
Кафедра "Высшей математики"
Типовой расчет
Часть 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 рубля.

1. Реферат на тему Принципы уголовного судопроизводства
2. Курсовая на тему Понятие уголовного права
3. Реферат Управление конфликтами 17
4. Реферат Creationism Essay Research Paper Creationism Genesis 11In
5. Реферат Признаки и критерии сегментирования рынка
6. Диплом на тему Аналіз використання персоналу на промисловому підприємстві
7. Реферат Системи випадкових величин
8. Реферат на тему Hamlet Characters And Plot Essay Research Paper
9. Реферат Расчет и конструирование одноступенчатого редуктора
10. Реферат на тему Crude Operatons