Анализ и принятие решений на основе задач транспортного типа

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ  УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ВЫСОКИХ  ТЕХНОЛОГИЙ

 

 

 

 

 

 

КУРСОВАЯ  РАБОТА

 

ПО ТЕМЕ:

АНАЛИЗ  И ПРИНЯТИЕ РЕШЕНИЙ НА ОСНОВЕ ЗАДАЧ  ТРАНСПОРТНОГО ТИПА

 

 

ДИСЦИПЛИНА: СИСТЕМНЫЙ АНАЛИЗ И ПРИНЯТИЕ РЕШЕНИЙ

 

 

 

 

 

 

 

 

 

 

Выполнил  ст-т гр 3-2

______________ Чекина  А.Н.

 

Принял преподаватель

______________ Золотарев  А. А

«___»________ 2013 г.

 

 

 

 

 

 

 

 

 

 

Ростов-на-Дону

2013

 

СОДЕРЖАНИЕ

 

Введение                                                                                                                   3

Глава 1. Транспортная задача: общая постановка, типы и виды моделей        4

1.1. Общая постановка, цели, задачи                                                                    4

1.2. Основные типы, виды моделей                                                                      6

Глава 2. Методы решения транспортной задачи                                                 9

2.1. Диагональный метод, или метод северо-западного угла                             9

2.2. Метод минимального элемента                                                                     10

2.3. Метод наименьшей стоимости                                                                      12

2.4. Метод потенциалов как метод решения транспортной задачи                  14

Заключение                                                                                                             18

Список литературы                                                                                                19

Приложения                                                                                                           20

 

Введение

 

Актуальность выбранной тематики курсовой работы заключается в том, что к задачам транспортного  типа сводятся многие другие задачи линейного  программирования - задачи о назначениях, сетевые, календарного планирования.

Целью данной работы является рассмотрение транспортной задачи и метода потенциалов  как метода ее решения.

Для реализации данной цели в работе необходимо решить следующие задачи:

- рассмотреть транспортную задачу, общую постановку, цели, задачи;

- изучить основные типы, виды  моделей;

- охарактеризовать методы решения  транспортной задачи;

- проанализировать метод потенциалов  как метод решения транспортной  задачи.

Новизна и практическая значимость работы обусловлена тем фактом, что  транспортная задача линейного программирования получила в настоящее время широкое  распространение в теоретических  обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.

Предметом исследования является транспортная задача. Объектом исследования выступает  метод потенциалов.

 

Глава 1. Транспортная задача: общая постановка, типы и  виды моделей

1.1 Общая постановка, цели, задачи

 

Под названием «транспортная задача»  объединяется широкий круг задач  с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом¹. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение².

Транспортная задача является частным  типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

 

,

 

т. е. общий объем производства равен  общему объему потребления. Требуется  составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос  всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу³.

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

 

 

Суммарное количество продукта, направляемого  из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что

 

, i 1, …, m

 

Суммарное количество груза, доставляемого  в каждый пункт назначения из всех пунктов отправления, должно быть равно  потребности. Это условие полного  удовлетворения спроса:

 

, j 1, …, n

 

Объемы перевозок - неотрицательные  числа, так как перевозки из пунктов  потребления в пункты производства исключены:

x_ij

0, i 1, ..., m; j 1, ..., n

1.2 Основные типы, виды моделей

 

Транспортная задача сводится, таким  образом, к минимизации суммарных  затрат при выполнении условий полного  удовлетворения спроса и равенства  вывозимого количества продукта запасам  его в пунктах отправления⁴.

Определение 1.

Всякое неотрицательное решение  системы линейных уравнений

 

, j 1, …, n и  , i 1, …, m,

 

определяемое матрицей X=(x_ij)(i 1, …, m; j 1, ..., n), называется планом транспортной задачи.

Определение 2.

План X*=(x*_ij)(i 1, …, m; j 1, ..., n), при котором функция

 

 

принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с баз потребителям .

Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени) ⁵.

Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имеющегося в наличии груза– :

 

;

 

заказы каждого из потребителей (потребности) обозначим соответственно , а общее количество потребностей – :

 

,

 

Тогда при условии

 

 

мы имеем закрытую модель, а при условии

 

 

– открытую модель транспортной задачи.

Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности  заказчиков полностью удовлетворены; в случае же открытой модели либо все  заказчики удовлетворены и при  этом на некоторых базах остаются излишки груза  , либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены .

Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный  пункт”, например – склад.

План перевозок с указанием  запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (приложение 1)

Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).

Таким образом, мы видим, что транспортная задача является задачей линейного  программирования. Для ее решения  применяют также симплекс-метод, но в силу специфики задачи здесь  можно обойтись без симплекс-таблиц. Решение можно получить путем  некоторых преобразований таблицы  перевозок. Эти преобразования соответствуют  переходу от одного плана перевозок  к другому. Но, как и в общем  случае, оптимальное решение ищется среди базисных решений⁶. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные · неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.

Для контроля надо проверять, равна  ли сумма чисел в заполненных  клетках каждой строки таблицы перевозок  запасу груза на соответствующей  базе, а в каждом столбце —  потребности заказчика.

 

Глава 2. Методы решения  транспортной задачи

2.1 Диагональный метод, или метод  северо-западного угла

 

При этом методе на каждом шаге построения первого опорного плана заполняется  левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При  таком методе заполнение таблицы  начинается с клетки неизвестного и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок (приложение 3).

Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным  . Первая база может полностью удовлетворить потребность первого заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения первый столбец. На базе остается измененный запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами ; северо-западным углом будет клетка для неизвестного . Первая база с запасом может полностью удовлетворить потребность второго заказчика . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается новый остаток (запас) . В оставшейся новой таблице с тремя строками и тремя столбцами северо-западным углом будет клетка для неизвестного . Теперь третий заказчик может принять весь запас с базы . Полагаем , вписываем это значение в клетку и исключаем из рассмотрения первую строку. У заказчика из осталась еще не удовлетворенной потребность .

Теперь переходим к заполнению клетки для неизвестного и т.д.

Через шесть шагов у нас останется  одна база с запасом груза (остатком от предыдущего шага) и один пункт с потребностью . Соответственно этому имеется одна свободная клетка, которую и заполняем, положив . План составлен. Базис образован неизвестными . Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам⁷.

Общий объем перевозок в тонно-километрах для этого плана составит

 

.

2.2 Метод минимального элемента

 

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая  ей соответствует, помещают меньшее  из чисел  и . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Пример 

Составить первоначальный опорный  план методом минимального элемента для транспортной задачи вида:

2	3	4	15
11	6	10	1
8	9	3	3
4	1	2	21
10	20	10

 

Решение:

Задача сбалансирована.

Строим первоначальный опорный  план методом минимального элемента.

1. Выясним минимальную стоимость перевозок. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2).
2. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта: , ;
4. Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки). .
5. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .
6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).

Опорный план имеет вид;

 

10	5	0
0	1	0
0	3	0
0	11	10

 

2.3 Метод наименьшей стоимости

 

При этом методе на каждом шаге построения опорного плана первою заполняется  та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них⁸.

Пример

Пункты отправления	Пункты назначения										Запасы
		70		50		15		80		70	300
	20				100				180
		80		90		40		60		85	150
	150
		50		10		90		11		25	250
			110				120		20
Потребности	170		110		100		120		200		700

 

В данном случае заполнение таблицы  начинается с клетки для неизвестного , для которого мы имеем значение , наименьше из всех значений . Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе и второму заказчику . Третья база может полностью удовлетворить потребность второго заказчика . Полагая , вписываем это значение в клетку и исключаем из рассмотрения второй столбец. На базе остается изменённый запас . В оставшейся новой таблице с тремя строками и четырьмя столбцами клеткой с наименьшим значением клетка, где . Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В результате оказываются заполненными (в приведенной последовательности) следующие клетки:

 

.

 

На пятом шаге клеток с наименьшими  значениями оказалось две . Мы заполнили клетку для , положив . Можно было выбрать для заполнения другую клетку, положив , что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит

 

.

 

Замечание. В диагональном методе не учитываются величины тарифов, в методе же наименьшей стоимости эти величины учитываются, и часто последний метод приводит к плану с меньшими общими затратами (что и имеет место в нашем примере), хотя это и не обязательно⁹.

2.5 Метод потенциалов как метод решения транспортной задачи

 

Метод потенциалов является модификацией симплекс-метода решения задачи линейного  программирования применительно к  транспортной задаче. Он позволяет, отправляясь  от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема  отдельной итерации такова. По допустимому  решению каждому пункту задачи сопоставляется число, называемое его предварительным  потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj.

Если разность предварительных  потенциалов для каждой пары пунктов  Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи¹⁰.

Этот первый точный метод решения  транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций) ¹¹.

Общий принцип определения оптимального плана транспортной задачи этим методом  аналогичен принципу решения задачи линейного программирования симплексным  методом, а именно: сначала находят  опорный план транспортной задачи, а затем его последовательно  улучшают до получения оптимального плана.

Составим двойственную задачу

1.

,  - любые

2.

3.

Пусть есть план

Теорема (критерий оптимальности): Для того чтобы допустимый план перевозок  в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа , , что

 

 если  , (6)

 если . (7)

 

числа  и называются потенциалами пунктов отправления  и назначения соответственно.

Сформулированная теорема позволяет  построить алгоритм нахождения решения  транспортной задачи. Он состоит в  следующем. Пусть одним из рассмотренных  выше методов найден опорный план. Для этого плана, в котором базисных клеток, можно определить потенциалы и так, чтобы выполнялось условие (6). Поскольку система (2)-(4) содержит уравнений и неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из уравнений (6) определяются остальные потенциалы и для каждой из свободных клеток вычисляются величины . Если оказалось, что , то план оптимален. Если же хотя бы в одной свободной клетке , то план не является оптимальным и может быть улучшен путем переноса по циклу, соответствующему данной свободной клетке.

Циклом в таблице условий транспортной задачи, называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. Если ломанная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами¹².

Процесс улучшения плана продолжается до тех пор, пока не будут выполнены  условия (7).

 

Заключение

 

В работе изложен анализ основных подходов и методов решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки¹³. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.

Алгоритм и методы решения транспортной задачи могут быть использованы при  решении некоторых экономических  задач, не имеющих ничего общего с  транспортировкой груза. В этом случае величины тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи¹⁴. К таким задачам относятся следующие:

- оптимальное закрепление за  станками операций по обработке  деталей. В них cij является таким экономическим показателем, как производительность.;

- оптимальные назначения, или проблема  выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

- задача о сокращении производства  с учетом суммарных расходов  на изготовление и транспортировку  продукции;

Таким образом, важность решения данной задачи для экономики несомненна.

 

Список литературы

 

1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.
2. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.
3. Боровков А.А. Математическая статистика. М.: Наука, 2004.
4. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 2004
5. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - СПБ: Издательство «Лань», 2003.
6. Коршунов Д.А., Чернова Н.И. Сборник задач и упражнений по математической статистике. Новосибирск: Изд-во Института математики им. С.Л.Соболева СО РАН, 2001.
7. Красс М. Математика для экономических специальностей. Учебник. 3-е изд., перераб и доп. М, Экономист, 2004.
8. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск, Высшая школа, 2005
9. Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. - Димитровград, 2002.

 

Приложения

 

Приложение 1

 

Таблица перевозок

Пункты Отправления	Пункты назначения				Запасы
			…
			…
			…
…	…	…	…	…	…
			…
Потребности			…		или