Решение транспортной задачи

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

1. Понятие транспортной задачи

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

Задачи транспортного типа широко распространены в практике. Кроме того, к ним сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

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

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

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

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

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

Для существования допустимого плана перевозок должен выполнятся общий баланс между спросом и потреблением:

При этом транспортную задачу называют сбалансированной.

Можно убедиться, например, что в сбалансированной транспортной задаче

являются допустимым вариантом перевозок, то есть удовлетворяющим ограничениям (6).

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

и задача заключается в минимизации (8) при выполнении ограничений (6) и условия неотрицательности переменных .

Переменные можно представить в виде матрицы (см. табл. 1).

Таблица: Матрица объемов перевозок.
Потребители Поставщики	1	2	…
1			…
2			…
…	…	…	…	…
M			…

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

Матрица ограничений транспортной задачи

1	1	…	1
				1	1	…	1
								…
									1	1	…	1
1				1				…	1
	1				1			…		1
								…
			1				1	…				1

Видно, что матрица ограничений транспортной задачи обладает рядом характерных особенностей, из которых отметим следующие:

- большая часть ее элементов равна нулю.

- среди ненулевых элементов много одинаковых.

Первое свойство матрицы называют разреженностью, а последнее свойство называют сверхразреженностью.

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

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

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

Список транспортных связей

Ў	Поставщик	Потребитель	Стоимость перевозки
1	Владивосток	Москва	134
2	Хабаровск	Владивосток	27
…	…	…	…
127	Якутск	Магадан	98

С -ой связью можно ассоциировать соответствующую переменную , которая имеет смысл объема перевозок по этому направлению.

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

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

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

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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 (xij[0]) m, n, элементы которой неотрицательны и удовлетворяют неравенствам.

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

vj[k] - ui[k] Cij, i 1,…, m; j 1, …, п.

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

Особенности математической модели транспортной задачи:

- система ограничений есть система уравнений, то есть задача ЛП в каноническом виде;

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

- каждая переменная входит в систему ограничений два раза: один раз в систему ограничений поставок, второй раз - в систему ограничений спроса.

Пусть хij - количество груза, перевозимого с i-го в j-й пункт.

Целевая функция:

Система ограничений:

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

Сбалансированная ТЗ:

Несбалансированная ТЗ:

Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке должна быть равна запасам ai, а сумма перевозок в каждом столбце равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.

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

потенциал транспортный матрица

3. Решение транспортной задачи методом потенциалов

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

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

U1 = V1 - C1,2 = 0-14 = -14, U2 = V1 - C2,2 = 0-10 = -10.

Имея U2 и учитывая, что во второй строке таблицы существуют еще ненулевые компоненты x2,2 и x2,3, можно определить V2 = U2 + C2,2 = -10+17 = 7 и V3 = U2 + C2,3 = -10 + 15 = 5, после чего появляется возможность рассчитать U3 = V3 - C3,3 = 5 - 25 = -20 и, наконец, V4 = U3 + C3,4 = -20 + 21= 1. В результате получаем полную систему потенциалов, показанную в табл.

V1 = 0 V2 = 7 V3 = 5 V4 = 1

14 27	28	21	28	27
10 6	17 13	15 1	24	20
14	30	25 26	21 17	43
33	13	27	17

U1 = -14

U2 = -10

U3 = -20

Для свободных клеток транспортной таблицы вычисляются величины аij = V1 - U1, называемые разностями потенциалов. В табл. 2 они выписаны для всех небазисных клеток под ценами.

V1 = 0 V2 = 7 V3 = 5 V4 = 1

14 27	28 21	21 19	28 15	27
10 6	17 13	15 1	24 11	20
14 20	30 27	25 26	21 17	43
33	13	27	17

U1 = -14

U2 = -10

U3 = -20

Разность потенциалов аij можно трактовать как увеличение цены продукта при его перевозке из пункта j в пункт i. Согласно критерию оптимальности, если все аij < или = сij, то план оптимален, в противном случае, если существует хотя бы одна разность потенциалов аij > сij, то он может быть улучшен. Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

Кандидатом на ввод, очевидно, может быть любая клетка, в которой аij > сij, поскольку после ввода в базис будет обеспечено равенство аij = сij. Для определенности обычно рекомендуется брать ту клетку, в которой оценка аij - сij максимальна. В рассматриваемом нами примере это будет клетка (3, 1).

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

Логика алгоритма построения цепочки достаточно проста: «выйдя» из клетки (3,1) в горизонтальном направлении, мы должны «остановиться» в той занятой клетке плана, из которой сможем двигаться дальше по вертикали. В данном примере этому требованию удовлетворяют как клетка (3,3), так и клетка (3,4). Однако цепочка от (3,4) ни может быть продолжена дальше, в то время как двигаясь от (3,3) по вертикали к (2,3) и далее к (2.1), мы возвращаемся к исходной клетке (3,1) и образуем замкнутый цикл.

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные - знаком «+», а четные знаком «-». Знаком «+» - отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «-» - те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «-», выбирается клетка с наименьшим значением хij (обозначим его q). Она и становится кандидатом на вывод, т.к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям хij в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем q, а из объемов клеток, помеченных знаком «-». он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.

В нашем примере знаком «-» отмечены клетки (2,1) и (3,3), причем х1,2 = 6, х3,3 = 26. Вычислив значение q = min {х1,2, х3,3}=6, осуществляем преобразование и переходим к следующему базисному плану/

Для вновь полученного плана повторяются действия стандартной итерации: рассчитываются потенциалы и оценки для небазисных клеток транспортной таблицы. Как можно видеть, план не является оптимальным (в клетке (1,3) аij =25>сij =21), поэтому вновь строим цепочку преобразования плана и переходим к следующему базисному плану.

V1 = 0 V2 = 7 V3 = 5 V4 = 1

14 7	28 23	21 20	28 21	27
10 8	17 13	15 7	24 15 11	20
14 26	30 23	25 21	21 17	43
33	13	27	17

U1 = -14

U2 = -10

U3 = -20

Из транспортной таблицы 3. видно, что полученный план оптимален, так как все разности потенциалов для небазисных клеток аij = V1 - U1, не превышают соответствующих цен сij. По данному плану вычисляется оптимальное (наименьшее) значение суммарных издержек на перевозку;

f (x*) = 14x7+21x20 + 17x13 + 15x7 + 14x26 + 21x17 = 1565.

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

1. Абчук В.А. Экономико-математические методы. СПб.: Союз, 2014. - 320 с.

2. Боборыкин В.А. Математические методы решения транспортных задач. СПб.: СЗПИ, 2014. - 170 с.

3. Горчаков А.А., Орлова А.А. Компьютерные экономико-математические модели. М.: ЮНИТИ, 2015. - 242 с.

4. Дадаян В.С. Макроэкономические модели. М.: МГУ, 2014. - 184 с.

5. Конюховский П.В. Математические методы исследования операций в экономике. СПб.: Питер, 2014. - 208 с.

6. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа, 2011. - 220 с.

7. Фомин Г.П. Математические методы и модели в коммерческой деятельности. М.: Финансы и статистика, 2015. - 616c.

Размещено на Allbest.ru