Транспортная задача
Составление плана перевозок зерна с учетом данных о потребности в нем и его запасах. Минимизация затрат на реализацию плана перевозок. Методы "северо-западного угла" и "минимального элемента". Новый улучшенный опорный план по методу потенциалов.
| Рубрика | Экономико-математическое моделирование |
| Вид | задача |
| Язык | русский |
| Дата добавления | 24.05.2009 |
| Размер файла | 48,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
12
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
Высшего профессионального образования
"Волгоградский государственный технический университет"
Камышинский технологический институт (филиал)
Волгоградского государственного технического университета
Кафедра "Высшей математики"
Типовой расчет
Часть 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) =7010+1104+706+2012+1307+1005 =
= 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) =1010+1104+1308+505+1004+109+905=
=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 |
||
|
j |
10 |
4 |
6 |
8 |
9 |
Проверяем условие m+n-1=3+5-1=7, число занятых клеток удовлетворяет этому условию.
Для определения потенциалов составляем уравнения:
u1+1=10 Пусть u1=0, тогда 1=10
u1+2=4 2=4
u1+4=8 4=8
u2+1=5 u2=5-10=-5
u2+5=4 5=4-(-5) =9
u3+1=9 u3=9-10=-1
u3+3=5 3=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
Так как не все Sij0, то план не оптимальный. Наиболее перспективной клеткой является клетка (3;
5), так как S35 - наименьшая. С вершиной в клетке (3;
5) строим замкнутый цикл. В него войдут вершины: (3;
5), (3;
1), (2;
1), (2;
5).
Найдем =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 |
||
|
j |
10 |
4 |
9 |
8 |
9 |
Для нового плана определяем новые потенциалы и находим новые оценки свободных клеток:
S13=-3 S22=12 S24=4 S32=7
S15=11 S23=8 S31=3 S34=6
Так как не все Sij0, то план не оптимальный. Наиболее перспективной клеткой является клетка (1;
3), так как S13 - наименьшая. С вершиной в клетке (1;
3) строим замкнутый цикл.
Найдем =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 |
||
|
j |
7 |
4 |
6 |
8 |
6 |
Для нового плана определяем новые потенциалы и находим новые оценки свободных клеток:
S11=3 S22=9 S24=1 S32=4
S15=14 S23=8 S31=3 S34=3
Так как все Sij0, то план оптимальный и единственный. Затраты на перевозки по оптимальному плану составляют:
min Z=1104+106+1308+705+804+805+205=
=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) =246+1130+1429+2621+45+2028+11+1514+50 =
= 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 |
||
|
j |
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) строим замкнутый цикл.
Найдем =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 |
||
|
j |
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) строим замкнутый цикл. Найдем =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 |
||
|
j |
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) строим замкнутый цикл. Найдем =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 |
||
|
j |
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) строим замкнутый цикл. Найдем =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 |
||
|
j |
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
Так как все Sij0, то план оптимальный и единственный. Затраты на перевозки по оптимальному плану составляют:
min Z=156+2030+95+204+1113+155+101+158+50=
=90+600+45+80+143+75+10+120+0=1163 руб.
Ответ: затраты на перевозки по оптимальному плану составляют 1163 рубля.
Подобные документы
Определение первичного опорного плана разными способами: методом северо-западного угла, методом минимальной стоимости, методом Фогеля. Перепланировка поставок с помощью метода потенциалов для каждого плана. Анализ эффективности их использования.
контрольная работа [67,2 K], добавлен 06.11.2012Основные подходы и способы решения транспортной задачи, ее постановка и методы нахождения первоначального опорного решения. Математическая модель транспортной задачи и алгоритм ее решения методом потенциалов. Составление опорного плана перевозок.
курсовая работа [251,0 K], добавлен 03.07.2012Типы транспортных задач и методы их решения. Поиск оптимального плана перевозок методом потенциалов. Решение задачи с использованием средств MS Excel. Распределительный метод поиска оптимального плана перевозок. Математическая модель, описание программы.
курсовая работа [808,7 K], добавлен 27.01.2011Математическая модель задачи (транспортная матрица с опорным планом северо-западного угла) и её решение вычислением потенциалов, графическим, фиктивного пункта методами. Проверка решений на оптимальность, нахождение новых схем пунктов перевозок.
контрольная работа [105,0 K], добавлен 15.12.2009Анализ чувствительности производственной программы предприятия к изменению уровня запасов сырья. Элементы теории графов. Алгоритм для нахождения пути с правильной нумерацией вершин. Транспортная задача, метод минимального элемента и северо-западного угла.
курсовая работа [986,8 K], добавлен 31.05.2013Понятие "транспортная задача", ее типы. Отыскание оптимального плана перевозок однородного груза, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок. Решения прямой и двойственной задачи линейного программирования.
контрольная работа [81,9 K], добавлен 14.09.2010Главные элементы сетевой модели. Задача линейного программирования. Решение симплекс-методом. Составление отчетов по результатам, по пределам, по устойчивости. Составление первоначального плана решения транспортной задачи по методу северо-западного угла.
контрольная работа [747,3 K], добавлен 18.05.2015Численные коэффициенты функции регрессии. Построение транспортной модели. Нахождение опорного плана методом Фогеля. Построение модели экономичных перевозок. Составление транспортной матрицы. Общая распределительная задача линейного программирования.
курсовая работа [1,3 M], добавлен 11.06.2010Математическая постановка и алгоритм решения транспортной задачи. Сбалансированность и опорное решение задачи. Методы потенциалов и северо-западного угла. Блок-схема. Формы входной и выходной информации. Инструкция для пользователя и программиста.
курсовая работа [113,8 K], добавлен 10.11.2008Понятие классической транспортной задачи, классификация задач по критерию стоимости и времени. Методы решения задач: симплекс, северо-западного угла (диагональный), наименьшего элемента, потенциалов решения, теория графов. Определение и применение графов.
курсовая работа [912,1 K], добавлен 22.06.2015
