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

Основные данные о работе

Версия шаблона	2.1
Название дисциплины	Математические методы исследования экономики
Тема	Транспортная задача. Постановка. Область применения. Примеры.
Фамилия
Имя
Отчество
№ контракта

  

Основная часть

Транспортная задача, постановка, область применения, примеры

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

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

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

Наиболее часто встречаются  следующие задачи, относящиеся к  транспортным:

прикрепление потребителей ресурса к производителям;

привязка пунктов отправления  к пунктам назначения;

взаимная привязка грузопотоков прямого и обратного направлений;

отдельные задачи оптимальной  загрузки промышленного оборудования;

оптимальное распределение  объемов выпуска промышленной продукции  между заводами-изготовителями и  др.

Транспортная модель

 

где n – количество пунктов отправления,

m – количество пунктов  назначения,

аi – запас продукции  в пункте отправления Ai( ) [ед. прод.],

bj – спрос на продукцию  в пункте назначения Bj( ) [ед. прод.],

cij – тариф (стоимость)  перевозки единицы продукции из пункта отправления Ai в пункт назначения Bj [руб. / ед. прод.],

xij - количество продукции,  перевозимой из пункта отправления  Ai в пункт назначения Bj [ед. прод.],

L(Х) – транспортные  расходы на перевозку всей  продукции [руб.].

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

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

(1)

Если такого равенства  нет (потребности выше запасов или  наоборот), запасу называют открытой, т.е.:

(2)

Для написания модели необходимо все условия (ограничения) и целевую функцию представить  в виде математических уравнении.

Все грузы из i-х пунктов  должны быть отправлены, т.е.:

, (3)

Все j-е пункты (потребители) должны быть обеспечены грузами в  плановом объеме:

, (4)

Суммарные объемы отправления  должны равняться суммарным объемам  назначения (1). Должно выполняться условие неотрицательности переменных: , , . Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(5)

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

потребности по пунктам  назначения превышают запасы пунктов  отправления, то вводится фиктивный  поставщик с недостающим объемом  отправления;

запасы поставщиков  превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.

Варианты, связывающие  фиктивные пункты с реальными, имеют  нулевые оценки. После введения фиктивных  пунктов задача решается как закрытая.

Транспортным задачам  присущи следующие особенности:

распределению подлежат однородные ресурсы;

условия задачи описываются  только уравнениями;

все переменные выражаются в одинаковых единицах измерения;

во всех уравнениях коэффициенты при неизвестных равны единице;

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

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

Опорный план является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. «Качество» опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

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

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

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

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

ПН: 41, 50, 27, 19, 43 = 180

ПО: 47, 53, 29, 51       = 180

Сij=

Решение

Пункт назначения Пункт отправления	В1	В2	В3	В4	В5	Запасы
А1	36	2	27	4	18	47
А2	11	7	17	1	17	53
А3	13	1	29	19	14	29
А4	3	5	8	5	11	51
Потребности	41	50	27	19	43	180

 

Транспортная задача относится к двухиндексным задачам  линейного программирования, так  как в результате её решения необходимо найти матрицу X c компонентами Xij.

Обозначим через Xij –  объем груза, перевозимый из пункта отправления i (i=1, 2, 3, 4) в пункт назначения j (j=1, 2, 3, 4, 5).

Стоимость всего плана (целевая функция) выразится двойной  суммой:

Zmin= , где

Сij -  тарифы на перевозку  продукции из пункта отправления i в  пункт назначения j.

Систему ограничений  получаем из следующего условия задачи:

а) все грузы должны быть перевезены, т.е. ;

б) все потребности  должны быть удовлетворены, т.е.

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

Ограничения по строкам:

Х11+Х12+Х13+Х14+Х15=47

Х21+Х22+Х23+Х24+Х25=53

Х31+Х32+Х33+Х34+Х35=29

Х41+Х42+Х43+Х44+Х45=51

Ограничения по столбцам:

Х11+Х21+Х31+Х41=41

Х12+Х22+Х32+Х42=50

Х13+Х23+Х33+Х43=27

Х14+Х24+Х34+Х44=19 
Х15+Х25+Х35+Х45=43

Прямые ограничения: Хij³0, Хij – целые

Решим задачу методом  потенциалов: vj= ui+cij

Оценки свободных клеток: dij=(ui+cij)-vj

Первоначальный план найдем методом минимального элемента, начиная с клетки (2;4).

 

Z=27·4+18·43+7·34+1·19+13·13+1·16+3·28+8·23=1592

Оценки свободных клеток:

dij=

План не является оптимальным, так как среди оценок свободных клеток есть отрицательные. Осуществим пересчет по выделенному контуру.

 

Z=27·4+18·43+11·13+7·21+1·19+1·29+3·28+8·23=1488

Оценки свободных клеток:

dij=

Вновь осуществим пересчет по выделенному контуру.

 

Z=2·4+18·43+11·17+7·17+1·19+1·29+3·24+8·27=1424

Оценки свободных клеток:

dij=

План не является оптимальным, так как среди оценок свободных  клеток есть отрицательные. Вновь осуществим пересчет по выделенному контуру.

 

Z=2·21+18·26+11·17+1·19+17·17+1·29+3·24+8·27=1322

Оценки свободных клеток:

dij=

Так как d35<0, план не является оптимальным. Вновь осуществляем пересчет.

 

Z=2·47+11·17+1·19+17·17+1·3+14·26+3·24+8·27=1244

Оценки свободных клеток:

dij=

Так как все оценки свободных клеток положительны, имеем единственное оптимальное решение.

Минимальная стоимость  перевозок составит 1244 ден. ед. при  следующей матрице перевозок:

Решим задачу в MS Excel.

Заполним рабочий лист Excel следующим образом:

 

Используем Поиск решения:

 

 

Результат расчетов:

 

Таким образом, наименьшая стоимость перевозок составит 1244 ден. ед., что совпадает с результатом, полученным при решении задачи методом  потенциалов.

Список использованных интернет-ресурсов

№ п/п	Наименование интернет-ресурса		Ссылка на конкретную используемую страницу интернет-ресурса
1	Учебные материалы		http://works.doklad.ru
2	К.Л. Самаров – Учебное  пособие «Транспортная задача»		http://www.resolventa.ru/metod/student/transproblem.htm
3	Пример и оформление транспортной задачи		http://www.ikasteko.ru/page/primer-i-oformlenie-transportnoj-zadachi
4	Транспортная задача. Опорное решение	http://www.grandars.ru/student/vysshaya-matematika/opornoe-reshenie-transportnoy-zadachi.html
5	Транспортная задача. Метод минимального элемента. (с введением фиктивного потребителя)	http://www.reshmat.ru/example_transport_2.html
6	Транспортная задача. Метод Фогеля.	http://www.reshmat.ru/example_transport_2.html

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