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

Пример 

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

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

 

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

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