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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение Высшего профессионального образования

" Волгоградский государственный технический университет"

Камышинский технологический институт (филиал)

Волгоградского государственного технического университета Кафедра «Высшей математики»

Типовой расчет Часть III

по дисциплине: «Экономико-математические методы»

на тему:

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

Выполнила:

студентка гр. КБА-081(вво)

Титова Мария Дмитриевна Проверила:

Старший преподаватель каф. ВМ Мягкова Светлана Васильевна Камышин — 2009 г.

Задача I

Составить план перевозок зерна из районов А1, А2, А3, запасы которых составляют соответственно 250, 150 и 100 тыс. ц. в 5 пунктов В1, В2, В3, В4, В5, потребности которых 70, 110, 90, 130, 100 тыс. ц. Затраты на перевозку 1 тыс. ц. зерна приведены в таблице.

Минимизировать общие затраты на реализацию плана перевозок.

Решение:

а). Метод «северо-западного угла». Установим характер задачи:

итак

модель задачи закрытая.

Составим распределительную таблицу:

Итак, получили план 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 руб.

б). Метод «минимального элемента «. Составим распределительную таблицу:

В результате полного распределения зерна получаем план X2, для которого значение целевой функции:

Z (X2) =1010+1104+1308+505+1004+109+905=

=100+440+1040+250+400+90+450=2770 руб.

в). Построение нового улучшенного опорного плана по методу потенциалов.

Рассмотрим опорный план, найденный по методу «минимального элемента».

Проверяем условие 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, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

Для нового плана определяем новые потенциалы и находим новые оценки свободных клеток:

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, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

Таблица.

Для нового плана определяем новые потенциалы и находим новые оценки свободных клеток:

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

Решить ТЗ с открытой моделью, если дана матрица планирования перевозок:

Решение:

а). Установим характер задачи:

итак модель задачи открытая, значит, вводим фиктивный пункт отправления А5 с запасами груза a5= - = 120 — 115=5, а тарифы перевозки этого груза будут С51=С52=С53=С54= С55=0.

Составляем распределительную таблицу по методу «минимального элемента» :

Итак, получили план X1. Суммарные расходы на перевозку зерна составляют:

Z (X1) =246+1130+1429+2621+45+2028+11+1514+50 =

= 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) строим замкнутый цикл.

Найдем =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) строим замкнутый цикл. Найдем =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) строим замкнутый цикл. Найдем =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) строим замкнутый цикл. Найдем =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

Так как все Sij0, то план оптимальный и единственный. Затраты на перевозки по оптимальному плану составляют:

min Z=156+2030+95+204+1113+155+101+158+50=

=90+600+45+80+143+75+10+120+0=1163 руб.

Ответ: затраты на перевозки по оптимальному плану составляют 1163 рубля.