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

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

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

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

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

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

Широкое применение получил метод МОДИ, который называется методом потенциалов. Для решения поставленной транспортной задачи предлагается использовать данный метод.

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

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

Таблица 1 – Суточный объем перевозки грузов между грузообразующими и грузопоглащающими пунктами

Шифр вершины грузообразующих пунктов	Шифр вершины грузоопоглащающих пунктов	Количество, тонн
А1	Б3
А1	Б4
А2	Б2
А3	Б1

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

Грузопоглащающие пункты	Грузообразующие пункты
А1	А2	А3	АТП
Б1
Б2
Б3
Б4
АТП

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

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

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

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

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

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

Потреб.	Коэф	Поставщик	Потреб. в грузе, т
А1	А2	А3
Б1
Б2
Б3
Б4
Наличие груза, т

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

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

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

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

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

Вторая группа уравнений – по получателям

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

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

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

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

Потреб.	Коэф	Поставщик	Потреб. в грузе, т
А1	А2	А3
Б1
Б2
Б3
Б4
Наличие груза, т

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

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

Решение задачи возможно при соблюдении некоторых правил.

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

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

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