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