1 Оптимизация грузопотоков

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

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

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

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

Задача оптимизации грузопотоков — это определение плана перевозок однородных (взаимозаменяемых) грузов от m поставщиков A_i к n потребителям В_j с учетом ограничений на ресурсы и потребности, обеспечивающие минимальную транспортную работу.

Если обозначить объем вывоза груза от поставщиков A_i через Q_i, требуемый объем завоза груза потребителю В_j через Q_j, перевозимое количество груза от i-го поставщика j-му потребителю - Q_ij, кратчайшее расстояние перевозки от i-го поставщика до j-го потребителя через l_ij, то задачу оптимизации грузопотоков можно выразить в следующей математической форме:

Во все j- е пункты получения груза из i- го пункта отправления может быть вывезено только Q_j единиц груза

(1.1)

из всех i-х пунктов отправления j-му пункту получения должно быть доставлено только Q_i единиц груза

(1.2)

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

(1.3)

а искомые переменные не могут быть отрицательными числами

т.е.

Q_ij≥0 (1.4)

Если общий объем вывоза грузов от поставщиков равен общему объему их завоза потребителям, то имеет место условие

(1.5)

Ограничения (]),(2),(3),(4),(5) и целевая функция (3) являются закрытой моделью классической задачи линейного программирования.

Для оценки первоначального базисного и отыскания оптимального плана

закрепления потребителей груза за поставщиками как задачи линейного программирования используются следующие методы: квадратов, опорных элементов, распределительные (Хичкока, Креко, модифицированный, распределительный метод - МОДИ), с разрешающими элементами [1,2].

Широкое применение получил метод МОДИ, который называют еще методом потенциалов.

Для решения поставленной транспортной задачи предлагается использовать данный метод.

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

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

Имеется несколько поставщиков и получателей однородной или взаимозаменяемой продукции. Известны наличие груза у каждого поставщика и потребность в нем у каждого получателя, а также расстояния между ними (таблица 1,2). Необходимо составить оптимальный план закрепления получателей за поставщиками, при котором общая стоимость доставки груза была бы минимальной.

В соответствии с «Прейскурантом № 13-01-02 единых тарифов на перевозку грузов автомобильным транспортом» стоимость перевозки зависит от класса груза и расстояния доставки. Согласно условию, груз является однотипным, т. е. имеет одинаковый класс, и поэтому стоимость перевозки будет зависеть только от расстояния.

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

Для получения оптимального плана закрепления получателей за поставщиками задачу решаем методом последовательного улучшения вариантов.

Расстояния должны быть приведены по фактическим замерам, произведенным контрольным автомобилем, или по карте при помощи курвиметра, причем расстояние до 0,5 округляется до 0,5 км, а свыше 0,5 - до целого километра.

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

Потребитель	Вспомога- тельные коэф.	Поставщик
	Строка Столбец	А1		А2		А3		Потребность в грузе, т
Б1			13		4		14	204
Б2			13		4		13	442
Б3			10		13		13	238
Б4			19		11		21	408
Наличие груза, т		442		646		204		1292

Рисунок 1 - Матрица №1-исходный план перевозок

Матрица с проставленными в ней исходными данными показана на рисунке 1 и называется исходным планом перевозок.

Математически транспортная задача линейного программирования формулируется следующим образом. Обозначим количество груза буквой x с двумя индексами: первый показывает, откуда везут, а второй - куда доставляют груз.

Первая группа уравнений - по поставщикам

х₁₁+x₂₁+х₃₁=204;

х₁₂+x₂₂+x₃₂=442;

х₁₃+x₂₃+x₃₃=238;

х₁₄+x₂₄+x₃₄=408. (1.6)

Она показывает ограничение груза по поставщикам. Вторая группа уравнений - по получателям

x₁₁+х₁₂+x₁₃+x₁₄=442;

x₂₁+x₂₂+x₂₃+x₂₄=646;

x₃₁+x₃₂+x₃₃+x₃₄=204. (1.7)

Вторая группа показывает ограничение количества груза по получателям.

Общее уравнение для отыскания минимального среднего расстояния перевозки

Cmin=8x₁₁+7x₂₁+6x₃₁+12x₁₂+14x₂₂+3x₃₂+7x₁₃+12x₂₃+4x₃₃+5x₁₄+5x₂₄+7x₃₄

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

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

Методика решения задачи следующая: рассматриваем матрицу № 1 (рисунок 1).

Вносим в матрицу значения единиц груза приведенные в задании.

Потребитель	Вспомога- тельные коэф.	Поставщик
	Строка Столбец	А1		А2		А3		Потребность в грузе, т
Б1			13		4		14	392
						204
Б2			13		4		13	392
		442
Б3			10		13		13	392
				238
Б4			19		11		21	192
				408
Наличие груза, т								1368

Рисунок 2 - Матрица №2-первичный план закрепления получателей за поставщиками.

Клетки, в которых поставлены цифры загрузки, называются загруженными (клетки А3Б1, А1Б2, А2Б3, А2Б4). Остальные клетки, не имеющие загрузки, называются незагруженными. Решение задачи возможно при соблюдении некоторых правил.

Правило 1 - Число загруженных клеток в матрице должно быть равно m+n-1

(m, n - число строк и столбцов)

В нашем случае m = 4, n = 3, следовательно, m + n- 1 = 4+3-1 = 6. На матрице число загруженных клеток равно 4.

Если число загруженных клеток больше m + n - 1, то план закрепления получателей за поставщиками составлен неверно, и задачу решить нельзя. Нужно составить новый план закрепления, соблюдая приведенное выше правило. Если число загруженных клеток меньше m + n - 1 , то задачу решить можно, загружая недостающее число клеток нулевой загрузкой (фиктивная загрузка). Для этого в одну или несколько клеток проставляют ноль.

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

В нашем случае нулевая загрузка проставляется в клетки А3Б2 и А1Б3. Матрица с нулевой загрузкой (№З) приведена на рисунке 3.

Потребитель	Вспомога- тельные коэф.	Поставщик						Потребность в грузе, т
	Строка Столбец	А1		А2		А3
Б1			13		4		14	204
						204
Б2			13		4		13	442
		442				0
Б3			10		13		13	238
		0		238
Б4			19		11		21	408
				408
Наличие груза, т		442		646		204		1292

Рисунок 3 - Матрица №3-введение фиктивной (нулевой) загрузки

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

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

Матрица №4 с поставленными на ней вспомогательными коэффициентами показана на рисунке 4.

Потребитель	Вспомога- тельные коэф.	Поставщик						Потребность в грузе, т
	Строка Столбец	А1		А2		А3
		4		7		4
Б1	10		13		4		14	204
						204
Б2	9		13		4		13	442
		442				0
Б3	6		10		13		13	238
		0		238
Б4	4		19		11		21	408
				408
Наличие груза, т		442		646		204		1292

Рисунок 4 - Матрица №4 со вспомогательными коэффициентами.

После отыскания вспомогательных коэффициентов проверяем матрицу на потенциальность.

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

Рассматриваем последовательно незагруженные клетки. Такой первой клеткой является А1Б1, расстояние которой равно 13 км. Эта клетка имеет вспомогательные коэффициенты строки и столбца 10 и 4.Так как (10+4)>13, то клетка является потенциальной.

В нашем случае есть три потенциальные клетки. Матрица №5 с проставленными потенциалами показана на рисунке 5

Потребитель	Вспомога- тельные коэф.	Поставщик						Потребность в грузе, т
	Строка Столбец	А1		А2		А3
		4		7		4
Б1	10		13		4		14	204
						204
Б2	9		13		4		13	442
		442				0
Б3	6		10		13		13	238
		0		238
Б4	4		19		11		21	408
				408
Наличие груза, т		442		646		204		1292

Рисунок 5-Матрица №5 с величинами потенциалов

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

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

Потребитель	Вспомога- тельные коэф.	Поставщик						Потребность в грузе, т
	Строка Столбец	А1		А2		А3
		4		7		4
Б1	10		13	-	4	+	14	204
						204
Б2	9	+	13		4	-	13	442
		442				0
Б3	6	-	10	+	13		13	238
		0		238
Б4	4		19		11		21	408
				408
Наличие груза, т		442		646		204		1292

Рисунок 6-Матрица №6 с нанесенным контуром

№ докум.

Подпись

Изм.

Лист

Дата

Лист