Определение выгодного транспортного маршрута перевозки

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

Из трех пунктов производства А₁, А₂, А₃ необходимо перевезти груз четырем потребителям B 1 , В 2 , В 3 , В 4 .

Количество груза в пунктах производства и величина спроса потребителей на данный груз указаны в таблице 1.

Расстояния между грузоотправителями и грузополучателями приведены в таблице 2.

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

Таблица 1 – Количество груза в пунктах производства и величина спроса потребителей на данный груз

Объём предложения производителей, т			Объём спроса потребителей, т				Суммарный объем спроса (предложения)
А 1	А 2	А 3	B 1	B 2	B 3	B 4
266	434	700	182	308	560	350	1400

Таблица 2 – Расстояние между производителями и потребителями

Производители	Потребители
	B 1	B 2	B 3	B 4
	Расстояние, км
А 1	140	100	120	80
А 2	80	160	100	110
А 3	60	150	80	120

Методы линейного программирования применяются для решения задач, которые связаны с распределением грузопотоков: закрепление потребителей грузов за поставщиками, распределение парка и маршрутов работы ПС по АТП. Такая задача закрепления потребителей за поставщиками получила название классической транспортной задачи.

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

Математическая модель классической транспортной задачи в общем виде записывается в следующей форме: mn

XX V, -                       (1)

i = 1 j = 1

при ограничениях

Xx< S, (i = 1,2,...,m), j=1

n

X x ,^ D ( j = 1,2,..., n ) ,                            (2)

j = 1

xy > 0 для всех i и j, где m – число поставщиков; n – число потребителей; x – объем перевозок между i и j пунктами; S – ограничения по предложению; D – ограничения по спросу; a – расстояние от пункта i до пункта j .

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

n

S , = X X j .                              (3)

j = 1

Каждый потребитель должен получить столько, сколько ему требуется, т. е. m

D ,= X X j .                            (4)

i = 1

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

xX ^Xaa i-J x i-J = min.                           ⁽⁵⁾

i = 1 j = 1

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

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

Для нашей задачи нам даны исходные данные:

Количество груза в пунктах производства:

А1 = 266 т,

А2 = 434 т,

А3 = 700 т.

Спрос потребителей на данный груз составляет:

B1 = 182 т,

В2 = 308 т,

В3 = 560 т,

В4 = 350 т.

Расстояния между грузоотправителями и грузополучателями приведены в таблице 2.

Для решения задачи обозначим через x количество тонн груза, которое должно быть перевезено от i -поставщика j -потребителю. Тогда математическая модель задачи выразится системой уравнений (6), а целевая функция, представляющая собой сумму произведений расстояний на соответствующий объем перевозок груза в тоннах, уравнением (7).

Х 11 + х₁₂+х₁₃+х₁₄ = 266л Х 21 +Х 22 +Х 23 +Х 24 = 434 ^ 31 +^ 32 +^ 33 +^ 34 = 700 х 11 +х₂₁ + х₃₁ = 182 Х 12 +Х 22 +Х 32 = 308 ^Х 13 ^+х 23 ^+х 33 = ⁵⁶⁰ Х 14 +Х 24 +Х 34 ⁼ 350

>

Минимизировать

140x11 + 100х12+120х13+80х14+80х21+160х22 + 100х23 + 110х24+60х31 +150x32+80x33+120x34

Общее число уравнений в системе определяется суммой поставщиков и потребителей, то в базисе должно быть уравнений m + n -1                              (8)

где m – число поставщиков; n – число потребителей.

3+4-1=6

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

Метод северо-западного угла

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

Сущность этого способа заключается в следующем. Распределение груза по потребителям начинается с клетки А 1 В 1 (таблица 4). Если предложение больше спроса, то следующая цифра ставится в клетке А₁ В₂ и т. п.

Способ северо-западного угла является плохим способом составления базисного плана, так как в большинстве случаев базисный план, очень далекий от оптимального. Положительная сторона его заключается в том, что он очень прост и обеспечивает получение m + n — 1 загруженных клеток.

Таблица 4 – Базисный план, составленный методом северо-западного угла

Производители	Потребители								Итого
	B1		B2		B3		B4
А1	182	140	84	100		120		80	266
А2		80	224	160	210	100		110	434
А3		60		150	350	80	350	120	700
Итого	182		308		560		350		1400

При полученном допустимом плане закрепления поставщиков за потребителями (таблица 4), транспортная работа составит:

182*140+84*100+224*160+210*100+350*80+350*120=160720т км.

Метод наименьшего элемента по столбцу

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

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

Таблица 5 – Базисный план, составленный методом наименьшего элемента по столбцу

Производители	Потребители								Итого
	B 1		B 2		B 3		B 4
А 1		140		100		120		80	266
			266
А 2		80		160		100		110	434
					84		350
А 3		60		150		80		120	700
	182		42		476
Итого	182		308		560		350		1400

При базисном плане, полученном способом наименьшего элемента по столбцу (таблица 5), транспортная работа составит:

182*60+266*100+42*150+84*100+476*80+350*110=128800т км.

Базисный план получился лучше (транспортная работа сократилась на 31920 т км), однако нельзя сказать, является ли он оптимальным или нет. Для ответа на этот вопрос, необходимо составленный допустимый план проверить на оптимальность.

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

Для проверки базисного плана на оптимальность целей разработано несколько методов. Наиболее широкое применение находят методы потенциалов (метод МОДИ) Хичкока, Креко.

Идея метода потенциалов, или метода МОДИ, заключается в том, что для проверки допустимого базисного плана на оптимальность определяются особым образом числа, называемые потенциалами. Главное требование к потенциалам заключается в том, чтобы каждый показатель a в загруженной клетке был равен сумме потенциалов своих строки и столбца a..=U.+V., ij           i          j ,

• где U – значение потенциала строки;

• V – значение потенциала столбца;

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

Потенциалы незагруженных (свободных) клеток определяются по формуле

Ej = a„ - (Ui + Vj) ,                            (10)

где E – потенциал незагруженной (свободной) клетки.

Проверим на оптимальность допустимый план, составленный способом наименьшего элемента по столбцу. Для этого матрицу метода наименьшего элемента по столбцу дополним одним столбцом и строкой (таблица 6).

Таблица 6 – Проверка базисного плана на оптимальность

Производители	Потребители								Итого	Потенциалы строк
	B 1		B 2		B 3		B 4
А 1		140	266	100		120		80	266	0
А 2		80		160	84	100	350	110	434	70
А 3	182	60	42	150	476	80		120	700	50
Итого	182		308		560		350		1400	x
Потенциалы столбцов	10		100		30		40		х	х

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

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

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

Определяется наименее загруженная клетка, занятая отрицательным углом контура (в данном случае А 3 B 2 ). Количество груза, указанное в этой клетке (42 т), отнимается из всех клеток, занятых отрицательными углами контура (т.е. из клеток А 3 B 2 , A 2 B 3 ), и прибавляется во все клетки контура с положительными углами (клетки А 2 B 2 , A 3 B 3 ).

Ранее загруженные клетки, которые не оказались расположенными в углах контура, переносятся в матрицу нового варианта закрепления потребителей груза за поставщиками без изменения (таблица 7).

Потенциалы строк и столбцов в новой матрице изменяются в соответствии с главным требованием метода потенциалов (9).

Далее следует осуществить проверку базисного плана на оптимальность в соответствии с формулой (10).

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

Таблица 7 – Базисный план, составленный методом потенциалов после перераспределения грузопотоков

Производители	Потребители								Итого	Потенциалы строк
	B 1		B 2		B 3		B 4
А 1	+	140	266	100	+	120	+	80	266	0
А 2	+	80	42	160	42	100	350	110	434	60
А 3	182	60		150	434	80	+	120	700	40
Итого	182		308		560		350		1400	x
Потенциалы столбцов	20		100		40		50		x	x

Объем транспортной работы при оптимальном закреплении поставщиков за потребителями составляет:

182*60+266*100+42*160+42*100+434*80+350*110=121660т км.

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

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

По методу северо-западного угла получили транспортную работу 160720 т км.

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