Оптимизация и безопасность перевозочного процесса

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

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

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

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

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

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

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

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

                              =Q_i, i = 1,2…,m ;   (1.1)

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

                        =Q_j, j = 1,2…,n.     (1.2)

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

                         min ,   (1.3)

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

     Q_ij ≥ 0.     (1.4)

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

                            = .     (1.5)

   Ограничения (1.1),(1.2),(1.4),(1.5) и целевая функция (1.3) являются закрытой моделью классической задачи линейного программирования.

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

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

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

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

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

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

Таблица 1.1 - Наличие  груза у поставщиков

 

Таблица 1.2 - Потребность  в грузе у получателей

 

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

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

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

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

Таблица 1.3 - Расстояние от поставщиков до получателей, км

 

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

 

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

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

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

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

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

x₂₁+ x₂₂+ x₂₃+ x₂₄ = 504;    (1.6)

x₃₁+ x₃₂+ x₃₃+ x₃₄ = 504.

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

x₁₁+ x₂₁+ x₃₁ = 714;

x₁₂+ x₂₂+ x₃₂ = 504;    (1.7)

     x₁₃+ x₂₃+ x₃₃ =504;

     x₁₄+ x₂₄+ x₃₄ =392.

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

C_min =16x₁₁+8x₂₁+26x₃₁+24x₁₂+30x₂₂+6x₃₂ +12x₁₃+26x₂₃+16x₃₃+ +20x₁₄+36x₂₄+26x₃₄.        (1.8)

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

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

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

 
 
 
 
 

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

   Клетки  матрицы, в которых поставлены цифры  загрузки, называются загруженными (клетки А1Б4, А1Б1,АЗБ3, А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, то задачу решить можно, загружая недостающее число клеток нулевой загрузкой (фиктивная загрузка). Для этого в одну или несколько клеток проставляют ноль.

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

   Матрица с нулевой загрузкой (№3) приведена  на рисунке 1.3.