МІНІСТЕРСТВО ОСВІТИ
Державна освітня установа
Вищої професійної освіти
"Волгоградський державний технічний університет"
Камишинський технологічний інститут (філія)
Волгоградського державного технічного університету
Кафедра "Вищої математики"
Типовий розрахунок
Частина III
з дисципліни: "Економіко-математичні методи"
на тему:
"Транспортна задача"
Виконала:
студентка гр. КБА-081 (вво)
Тітова Марія Дмитрівна
Перевірила:
Старший викладач каф. ВМ
Мягкова Світлана Василівна
Камишин - 2009 р.
Мінімізувати загальні витрати на реалізацію плану перевезень.
Рішення:
а). Метод "північно-західного кута". Встановимо характер завдання:
Складемо розподільну таблицю:
Отже, отримали план 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 руб.
б). Метод "мінімального елементу". Складемо розподільну таблицю:
В результаті повного розподілу зерна отримуємо план 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 руб.
в). Побудова нового покращеного опорного плану за методом потенціалів.
Розглянемо опорний план, знайдений за методом "мінімального елементу".
Перевіряємо умову 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, після перерахунку отримаємо новий цикл. Замінюючи старий цикл на новий, отримаємо наступну таблицю:
Для нового плану визначаємо нові потенціали і знаходимо нові оцінки вільних клітин:
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, після перерахунку отримаємо новий цикл. Замінюючи старий цикл на новий, отримаємо наступну таблицю:
Таблиця.
Для нового плану визначаємо нові потенціали і знаходимо нові оцінки вільних клітин:
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 рублів.
Рішення:
а). Встановимо характер завдання:
модель задачі відкрита, значить, вводимо фіктивний пункт відправлення А5 із запасами вантажу a5 =
Складаємо розподільну таблицю за методом "мінімального елемента":
Отже, отримали план 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 руб.
б). Побудова нового покращеного опорного плану за методом потенціалів.
Розглянемо опорний план, знайдений за методом "мінімального елементу".
Перевіряємо умову 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, після перерахунку отримаємо новий цикл. Замінюючи старий цикл на новий, отримаємо наступну таблицю:
Визначаємо потенціали і знаходимо оцінки вільних клітин:
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, після перерахунку отримаємо новий цикл. Замінюючи старий цикл на новий, отримаємо наступну таблицю:
Визначаємо потенціали і знаходимо оцінки вільних клітин:
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.
Визначаємо потенціали і знаходимо оцінки вільних клітин:
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.
Визначаємо потенціали і знаходимо оцінки вільних клітин:
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 рубля.
Державна освітня установа
Вищої професійної освіти
"Волгоградський державний технічний університет"
Камишинський технологічний інститут (філія)
Волгоградського державного технічного університету
Кафедра "Вищої математики"
Типовий розрахунок
Частина 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 |
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 | 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 |
Для визначення потенціалів складаємо рівняння:
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 | 4 110 | + 6 | 8 130 | 20 | 250 | 0 |
| A2 | + 5 60 | 11 | 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 =
Складаємо розподільну таблицю за методом "мінімального елемента":
| 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 |
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 10 | 7 | 15 | 35 | 0 |
| A2 | + 5 | 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 |
Визначаємо потенціали і знаходимо оцінки вільних клітин:
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 | + 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 | 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 рубля.