Постановка транспортной задачи

КИРОВСКИЙ ФИЛИАЛ

Кафедра естественнонаучных и математических дисциплин

ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ

ТРАНСПОРТНАЯ ЗАДАЧА

для студентов экономических специальностей

Киров

Транспортная задача(задача оптимального планирования перевозок груза)

Постановка транспортной задачи

Имеется m пунктов отправления (производства, поставщиков): в которых сосредоточены запасы некоего одно-родного груза в объемах соответственно. Величины аiопределяют максимально возможные размеры вывоза груза спунктов отправления. Суммарный запас груза поставщиков составляет Кроме того, имеются n пунктов назначения (потребления): , которые подали заявки на поставку груза в объемах соответственно. Величины bj определяю от максимально возможные размеры ввоза груза в пункты назначения. Суммарная величина заявок составляет , стоимость перевозки 1 ед. груза от поставщика к потребителю ден. ед. (транспортный тариф). Требуется разработать оптимальный план перевозок таким образом, чтобы общая стоимость всех перевозок груза была минимальной при условии, что весь груз от поставщиков будет вывезен и все заявки потребителей удовлетворены. В общем виде модель задачи оптимального планирования перевозок груза можно записать следующим образом:

– количество однородного груза, перевозимого от поставщика к потребителю , = .

. (1.37)

;

. (1.38)

Таким образом, необходимо составить такой план перевозки груза, при котором целевая функция (1.37) принимала бы наименьшее значение и выполнялись бы условия (1.38).Любое неотрицательное решение системы ограничений (1.38),определяемое матрицей X = , называется допустимым планом транспортной задачи. Допустимый план транспортной задачи,имеющий не более m+n–1 отличных от 0 величин , называется опорным. Если в опорном плане число отличных от 0 компонент равно в точности m+n–1, то план является невырожденным; если меньше этого числа, то план является вырожденным. Условия транспортной задачи можно записать в виде следующей таблицы перевозок – транспортной таблицы (табл. 1.73).В моделях оптимального планирования перевозок груза должно выполняться балансовое равенство:

, (1.39)

Таблица 1.73

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

Равенство (1.39) означает, что суммарный запас груза должен равняться суммарным потребностям. Модели, в которых выполняется балансовое равенство, называются закрытыми, в которых не выполняется – открытыми. Уравнение баланса (1.39)

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

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

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

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

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

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

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

Метод потенциалов

Наиболее распространенным графоаналитическим методом решения транспортных задач является метод потенциалов. Решение задач этим методом включает следующие этапы.

I. Проверка балансового равенства (1.39).

II. Разработка первоначального опорного плана (опорного решения). Существуют два метода построения первоначального опорного плана (см. табл. 1.73):

1) метод северо-западного угла. Заполнение таблицы начинается с левой верхней клетки, куда дается максимально возможная поставка. Объем поставки выбирается таким образом, чтобы полностью закрыть либо потребность по столбцу , либо запас по строке , т.е. в качестве выбирается минимум между запасами груза на первом складе и потребностями в грузе у первого потребителя: . Дальнейшее заполнение таблицы происходит слева направо, сверху вниз. На каждом шаге заполнения должна выпасть либо строка, либо столбец;

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

III. Проверка вырожденности плана. Если число занятых клеток в опорном плане меньше, чем m+n–1, т.е. план является вырожденным, то не будет хватать количества уравнений для определения потенциалов; поэтому необходимо внести 0* (0* –вводится фиктивная перевозка) в одну из свободных клеток транспортной таблицы так, чтобы общее число занятых клеток стало равным m + n – 1, т.е. опорный план стал невырожденным. При составлении первоначального опорного плана, заполняя клетку таблицы перевозок поставкой, из рассмотрения выводится либо строка, либо столбец таблицы. Если запас в строке и потребность в столбце совпадают, то после заполнения клетки ( ; ) пришлось бы выводить строку и столбец одновременно, чего делать нельзя, так как число занятых клеток будет меньше, чем m+n–1. Выведем из рассмотрения только строку , а в качестве потребности столбца запишем 0. Тогда на одном из следующих шагов заполнения таблицы появится фик-тивная перевозка, равная 0 (0*)

Фиктивная перевозка может появиться также при перераспределении поставок, если окажется, что существует несколько наименьших объемов перевозок, стоящих в «минусовых» клетках цикла. Тогда любую одну клетку считаем свободной, а остальные – занятыми фиктивными объемами перевозок.

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

V. Проверка опорного плана на оптимальность:

1) расчет потенциалов. Для каждой занятой объемами перевозок клетки транспортной таблицы записываем уравнение

. (1.40)

Получим систему уравнений относительно чисел , , называемых потенциалами. Эта система имеет m+n–1 уравнений с m+n переменными. Так как число уравнений меньше числа переменных, то система является неопределенной и имеет бесконечное число решений. Поэтому полагаем ;

2) расчет оценок свободных клеток. Для клеток, не занятых объемами перевозок (свободные клетки), считаем оценки:

. (1.41)

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

VI. Перераспределение груза. Из клетки, которой соответствует наибольшая положительная оценка, начинаем строить цикл, поставив в этой клетке знак «+». Цикл – это замкнутая ломаная линия, звенья которой параллельны строкам и столбцам таблицы, а вершины лежат в занятых клетках. Вершинам цикла поочередно присваиваем знаки «+» и «–». Из объемов груза, стоящих в минусовых клетках, выбирают наименьший и обозначают d. В новой таблице прибавляют d к объемам груза в «плюсовых» клетках и вычитают d из объемов «минусовых» клеток.

VII. Получение нового опорного плана. Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решение.

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

Таблица 1.74

Решение. Обозначим через количество груза, перевозимого из пункта в пункт j, где ; . Балансовое равенство выполняется (суммарная потребность в грузе равняется суммарным запасам: 3 + 6 + 7 + 5 = 7 + 8 + 6), значит, транспортная задача – закрытая. Тогда экономико-математическая модель задачи выглядит следующим образом:

;

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

Таблица 1.75

Или

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

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

Далее заполнение таблицы происходит следующим образом:

;

Первоначальный опорный план, построенный методом наименьшего тарифа, следующий (табл. 1.76):

Таблица 1.76

или

Проверим найденный опорный план на вырожденность. Вычислим m + n–1: m + n–1 = 3 + 4–1 = 6, т.е. число занятых клеток равно 6. Так как эти значения совпадают, то найденный опорный план является невырожденным. Стоимость перевозки: = 92 ден. ед. Практически всегда метод наименьшего тарифа дает более приближенный к оптимальному опорный план, чем метод северо-западного угла. Проверим план, построенный методом наименьшего тарифа, на оптимальность. Для этого по занятым объемами перевозок клеткам составим систему уравнений по формуле (1.40):

;

Неизвестные потенциалы , находим из этой системы уравнений, полагая . Тогда из первого и второго уравнений: ; далее из предпоследнего: ; затем из третьего и четвертого уравнений: ; и, нако-нец, из последнего: . Перепишем матрицу перевозок, добавивсправа столбец с потенциалами , а внизу – строку с потенциалами (табл. 1.77).

Таблица 1.77


-9		-3

t RptYGnsUL+o16r6B5pm0QxiHlj4ZGR3gD84GGtia++87gYoz88mS/vNiOo0Tnpzp7LIkB88jm/OI sJKgah44G81VGH/FzqHedvRSkcq1cEM9a3USM/ZzZHUkS0OZND5+oDj1537K+vXNlz8BAAD//wMA UEsDBBQABgAIAAAAIQAnQ2FG3QAAAAcBAAAPAAAAZHJzL2Rvd25yZXYueG1sTI7BTsMwEETvSPyD tUjcWieYtFXIpqqokODAgQB3N94mUWM7it00/D3LiZ5GoxnNvGI7215MNIbOO4R0mYAgV3vTuQbh 6/NlsQERonZG994Rwg8F2Ja3N4XOjb+4D5qq2AgecSHXCG2MQy5lqFuyOiz9QI6zox+tjmzHRppR X3jc9vIhSVbS6s7xQ6sHem6pPlVni7BvdtVqkipm6rh/jdnp+/1NpYj3d/PuCUSkOf6X4Q+f0aFk poM/OxNEj5Ct19xEWKQZCM43j6wHBJUokGUhr/nLXwAAAP//AwBQSwECLQAUAAYACAAAACEAtoM4 kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAI AAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVsc1BLAQItABQABgAI AAAAIQDQzBt4GgIAAC4EAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9jLnhtbFBLAQItABQA BgAIAAAAIQAnQ2FG3QAAAAcBAAAPAAAAAAAAAAAAAAAAAHQEAABkcnMvZG93bnJldi54bWxQSwUG AAAAAAQABADzAAAAfgUAAAAA "/>-6	-2		-2
-2

Посчитаем оценки свободных клеток по формуле (1.41):

;

Запишем оценки свободных клеток в транспортной таблице, обводя их в круг. План не оптимальный, так как оценка ∆32 положительна, поэтому ставим в этой клетке знак «+» и строим цикл (табл. 1.78).

Таблица 1.78


	uL 7YmQZxuKSxXwoDGgc7HOIvmxSBfr+Xqej/LJbD3K07oePW2qfDTbZA/T+lNdVXX2M1DL8qITjHEV 2F0Fm+V/J4jL0zlL7SbZ2xiS9+hxXkD2+h9Jx82GZZ5lsdPstLXXjYNGY/DlPYVHcH8H+/7Vr34B AAD//wMAUEsDBBQABgAIAAAAIQBYFxF62wAAAAYBAAAPAAAAZHJzL2Rvd25yZXYueG1sTM4xb8Iw EAXgvRL/wToklqo4UBLREAchpA4dC0hdTXwkaeNzFDsk5df32oWOT+/07su2o23EFTtfO1KwmEcg kApnaioVnI6vT2sQPmgyunGECr7RwzafPGQ6NW6gd7weQil4hHyqFVQhtKmUvqjQaj93LRJ3F9dZ HTh2pTSdHnjcNnIZRYm0uib+UOkW9xUWX4feKkDfx4to92LL09ttePxY3j6H9qjUbDruNiACjuF+ DL98pkPOprPryXjRKFgnLA8KVisQXD/HSQzi/Jdlnsn//PwHAAD//wMAUEsBAi0AFAAGAAgAAAAh ALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAU AAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJlbHNQSwECLQAU AAYACAAAACEApWK/gSACAAA9BAAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0RvYy54bWxQSwEC LQAUAAYACAAAACEAWBcRetsAAAAGAQAADwAAAAAAAAAAAAAAAAB6BAAAZHJzL2Rvd25yZXYueG1s UEsFBgAAAAAEAAQA8wAAAIIFAAAAAA== "/>5 GGxILqTHg7qAzmgNM/Jjlay2y+0ym2SzxXaSJVU1edqV2WSxSx/m1aeqLKv0p6eWZnnLKWXSs7vO a5r93TyML2eYtNvE3toQ36OHfgHZ6z+QDsJ6LYepOCh62Zur4DCiwXl8Tv4NvN+D/f7Rb34BAAD/ /wMAUEsDBBQABgAIAAAAIQAUGotV2wAAAAcBAAAPAAAAZHJzL2Rvd25yZXYueG1sTI7BTsMwEETv lfoP1iJxqaidqlQhxKmqShw40lbi6sZLEojXUew0oV/PwoUeRzN68/Lt5FpxwT40njQkSwUCqfS2 oUrD6fjykIII0ZA1rSfU8I0BtsV8lpvM+pHe8HKIlWAIhcxoqGPsMilDWaMzYek7JO4+fO9M5NhX 0vZmZLhr5UqpjXSmIX6oTYf7Gsuvw+A0YBgeE7V7ctXp9Tou3lfXz7E7an1/N+2eQUSc4v8YfvVZ HQp2OvuBbBCthnTD5lHDeg2C67945plKE5BFLm/9ix8AAAD//wMAUEsBAi0AFAAGAAgAAAAhALaD OJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54bWxQSwECLQAUAAYA CAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJlbHNQSwECLQAUAAYA CAAAACEAsJBVrB0CAAA8BAAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0RvYy54bWxQSwECLQAU AAYACAAAACEAFBqLVdsAAAAHAQAADwAAAAAAAAAAAAAAAAB3BAAAZHJzL2Rvd25yZXYueG1sUEsF BgAAAAAEAAQA8wAAAH8FAAAAAA== "/> -6		+1
		8 +	-4
	+	-6
-2

Заметим, что такой цикл всегда существует и он единственный. Наименьший объем груза в «минусовых» клетках d = 4.Новую таблицу перевозок составляем с учетом следующих изменений: в клетках со знаком «+» объем перевозок увеличится на 4 ед., в клетках со знаком «–» уменьшится на 4, а в остальных останется без изменений (табл. 1.79).

Таблица 1.79


-7		-1
	R piqNPYkX9Rp130BzJO0QxpmlP0ZGB/iDs4Hmteb++06g4sx8tKT/vJhGtUJyprN3JTl4GdlcRoSV BFXzwNlorsL4KXYO9bajl4pE18It9azVSczYz7GqU7E0k0nj0/+JQ3/pp6xfv3z5EwAA//8DAFBL AwQUAAYACAAAACEArkVzU9wAAAAHAQAADwAAAGRycy9kb3ducmV2LnhtbEyPQU+DQBCF7yb+h82Y eLNLQQhFlqaxMdGDB9Het+wUSNlZwm4p/nvHkx7fvJf3vim3ix3EjJPvHSlYryIQSI0zPbUKvj5f HnIQPmgyenCECr7Rw7a6vSl1YdyVPnCuQyu4hHyhFXQhjIWUvunQar9yIxJ7JzdZHVhOrTSTvnK5 HWQcRZm0uide6PSIzx025/piFezbXZ3NMglpctq/hvR8eH9L1krd3y27JxABl/AXhl98RoeKmY7u QsaLQUGaP3JSQRynINjPM/7kyPd0A7Iq5X/+6gcAAP//AwBQSwECLQAUAAYACAAAACEAtoM4kv4A AADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNdLnhtbFBLAQItABQABgAIAAAA IQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8ucmVsc1BLAQItABQABgAIAAAA IQCSz/7ZGAIAAC0EAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJvRG9jLnhtbFBLAQItABQABgAI AAAAIQCuRXNT3AAAAAcBAAAPAAAAAAAAAAAAAAAAAHIEAABkcnMvZG93bnJldi54bWxQSwUGAAAA AAQABADzAAAAewUAAAAA "/>5 -2		-2
-5			-4

Или

Для проверки полученного плана на оптимальность по формуле (1.40) составляем систему уравнений:

;

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

Cтоимость перевозки

Замечание. Если среди оценок свободных клеток нет нулевых оценок, то найденный оптимальный план является единственным. Если же среди оценок свободных клеток есть нулевая оценка:∆24=0, то задача имеет множество оптимальных планов (множество решений). Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь то же значение целевой функции. Пример 1.21. Составить методом северо-западного угла первоначальный опорный план для заданной таблицы перевозок транспортной задачи (табл. 1.80).

Таблица 1.80

Решение. Заполнение таблицы начинаем с левого верхнего угла:

Тогда запас в первой строке: = 11–10=1 ед. груза, а пер-вый столбец выводим из рассмотрения. Далее:

;

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

Затем:

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

Таблица 1.81