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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.


Нажми чтобы узнать.
скачати

МІНІСТЕРСТВО ОСВІТИ
Державна освітня установа
Вищої професійної освіти
"Волгоградський державний технічний університет"
Камишинський технологічний інститут (філія)
Волгоградського державного технічного університету
Кафедра "Вищої математики"
Типовий розрахунок
Частина 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 × 29 +14 +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 рубля.
Додати в блог або на сайт

Цей текст може містити помилки.

Економіко-математичне моделювання | Завдання
198.4кб. | скачати


Схожі роботи:
Транспортна задача лінійного програмування
Транспортна задача з обмеженнями можливих транспортних засобів
Основна задача механіки
Задача про Ханойські вежі
Наскрізна задача з фінансового та управлінського обліку
Зміст поняття задача у навчанні математики в початкових класах
Лінійні різницеві рівняння із сталими коефіцієнтами Задача Коші
ЛІнійні різницеві рівняння зі сталими коефіцієнтами Задача Коші
Розв язок задач лінійного програмування Задача планування виробництва
© Усі права захищені
написати до нас
Рейтинг@Mail.ru