ТАБЛИЦА 3. Расчётные нормативы.

* Примечание. Допустимое отклонение ± 35 минут.

** Примечание. Используется автомобиль ЗИЛ-130 грузоподъёмностью 5 тонн.

§3. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

3.1. Математическая постановка задачи.

Рассмотрим и сформулируем в математической форме условие транспортной задачи. Потребителям Б1, Б2, , Бj, , Бn требуется груз в количествах b1, b2, ., bj, ., bn (т) единиц, который имеется или производится у поставщиков A1, A2, , Ai, , Am в количествах a1, a2, ., ai, , am (т) единиц соответственно. Обозначим через qij объём перевозок из i-ого пункта отправления в j-ый пункт назначения. Объём перевозок известен для всех пунктов ( задана заявка на перевозки грузов, см. таблицу 1.). Расстояние между поставщиками и потребителями известно (см. таблицу 2.) и составляет lij (км). В процессе выполнения перевозок в пунктах назначения Б1, Б2, , Бj, , Бn после разгрузки автомобилей будет образовываться порожняк в количествах b`1, b`2, ., b`j, ., b`n который надо направить в пункты A1, A2, , Ai, , Am в количествах a`1,a`2,…a`j,….a`m.

С методической точки для решения задачи удобней пользоваться понятием “ездка”. Поэтому за единицу измерения будет приниматься ездка автомобиля с грузом и без него.

В задаче будет выполняться условие:

m n

b`j = bj = S qij , где j=1,2, ,n и a`i = ai = S qij , где i=1,2, ,m ,

1 1

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

3.2. Математическая запись задачи.

Обозначим через Xij количество порожняка (в автомобиле - ездках) предназначенного к отправке из пункта разгрузки Бj в пункт погрузки Ai , тогда суммарный холостой пробег автомобиля из всех пунктов с наличием порожняка во все пункты его подачи будет иметь вид:

n m

S S Xij * lij à min. { 1 }

j=1 i=1

Условие полного удовлетворения спроса на порожняк каждого пункта отправления за счёт подачи его из разных пунктов с наличием порожняка выглядит так:

n

S Xij = a`i , где i= 1,2, .,m. { 2 }

j=1

Весь порожняк из каждого пункта назначения должен быть подан в пункт отправления под погрузку, т.е. :

m

S Xij = b`j , где j= 1,2, .,n. { 3 }

i=1

Очевидно, что количество автомобилей не может быть отрицательным числом, т.е. Xij > 0, при i= 1,2, .,m, j= 1,2, .,n. { 4 }

Таким образом, в математической форме транспортная задача формулируется так:

Определить значение переменных Xij минимизирующих линейную форму, выраженную {1}, при ограничениях, указанных в {2},{3},{4}. Необходимо равенство общей потребности получателей и наличия груза у поставщиков или отправителей:

m n

S b`j = S а`j { 5 }

i=1 j=1

Это равенство является необходимым и достаточным условием для совместимости уравнений {2},{3}.

Цель решения выражается уравнением {1}: найти минимальный суммарный холостой пробег автомобилей. Задачу, выраженную формулами {1—5} принято называть задачей минимизации холостых пробегов автомобилей.

3.3. Метод совмещённых планов.

Для решения задачи разработан метод совмещённых планов. С его помощью она решается в три этапа.

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

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

На третьем этапе найденные маршруты прикрепляют к АТП (автотранспортному предприятию), после чего разрабатывают сменно-суточные задания водителям по каждому маршруту.

Составление матрицы условий

Составление допустимого исходного плана

Подсчёт числа занятых клеток в матрице (N) и сравнение с (m+n-1)

N>m+n-1 N<m+n-1

Расчёт индексов

Проверка незанятых клеток на потенциальность