"Волгоградский государственный технический университет"
Камышинский технологический институт (филиал)
Волгоградского государственного технического университета
Кафедра "Высшей математики"
Типовой расчет
Часть 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. Суммарные расходы на перевозку зерна составляют: