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

1.1 Определение кратчайших расстояний между пунктами транспортной сети

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

Модель транспортной сети представляет собой чертеж-схему на плане местности с указанием вершин (пунктов) транспортной сети. Её построение производится по заданной схеме расположения пунктов, по наличию звеньев сети, соединяющих два соседних пункта, и длине этих звеньев. При выполнении курсового проекта использована готовая схема транспортной сети (вариант №21), которая приведена в Приложении А.

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

Шаг 1. Начальному пункту, от которого требуется определить кратчайшие расстояния, присваивается потенциал V_i = 0.

Шаг 2. Просматриваются все звенья, начальные пункты I которых имеют потенциал V_i, а для конечных j потенциалы не присвоены. Затем определяются значения потенциалов конечных пунктов j по следующей формуле:

V_j(i) = V_i + l_ij, (1.1)

где V_j(i) - потенциал конечного пункта j звена i-j;

l_ij - длина звена i-j, т. е. расстояние между пунктами i и j.

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

min {V_j(i)} = V_j'_(i'₎, V_j'_(i'₎ {V_j(i)}, (1.2)

где {V_j(i)}- множество значений потенциалов конечных пунктов j звеньев i-j, i-м начальным пунктом которых ранее присвоены потенциалы;

{V_j'_(i'₎} - потенциал конечного пункта j' звена i'-j', являвшийся наименьшим по значению элементом множества {V_j(i)}.

Потенциал {V_j'_(i'₎} присваивается соответствующему конечному пункту j', а звено i'-j' отмечается звездочкой (*).

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

В таблицах 1.1-1.10 приведён расчёт по методу потенциалов для пунктов А₁- Б₅ транспортной сети.

Результаты расчёта сведены в таблице 1.11.

Таблица 1.11 - Кратчайшие расстояния между пунктами транспортной сети (в километрах)

Таблица 1.1 - Расчёт кратчайших расстояний до пункта А₁

Таблица 1.2 - Расчёт кратчайших расстояний до пункта А₂

Таблица 1.3 - Расчёт кратчайших расстояний до пункта А₃

Таблица 1.4 - Расчёт кратчайших расстояний до пункта А₄

Таблица 1.5 - Расчёт кратчайших расстояний до пункта А₅

Таблица 1.6 - Расчёт кратчайших расстояний до пункта Б₁

Таблица 1.7 - Расчёт кратчайших расстояний до пункта Б₂

Таблица 1.8 - Расчёт кратчайших расстояний до пункта Б₃

Таблица 1.9 - Расчёт кратчайших расстояний до пункта Б₄

Таблица 1.10 - Расчёт кратчайших расстояний до пункта Б₅

1.2 Построение модели транспортной задачи для заданного варианта перевозок

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

(1.3)

(1.4)

(1.5)

(1.6)

В случае, если количество груза у поставщиков равно общему объему завоза груза всем потребителям, то имеет место условие:

(1.7)

Поставленная таким образом задача (целевая функция (1.3) и ограничения (1.4) - (1.7)) является закрытой моделью классической транспортной задачи линейного программирования, в результате решения которой по известным значениям Q_i, Q_j и l_ij находятся неизвестные значения объёмов перевозок между i-м поставщиком и j-м потребителей Q_ij.

Для составления транспортной задачи из исходных данных (вариант № 22) выбираются грузы, перевозимые одним типом подвижного состава.

Перечень этих грузов представлен в таблице 1.12.

Таковыми являются рельсы, овощи, метизы, шифер, шифер, проволока и фрукты.

Таблица 1.12 - Грузы, перевозимые одним типом подвижного состава

Для решения транспортной задачи объёмы перевозок приводятся к 1-му классу груза по следующей формуле:

(1.8)

где Q_ij - объём перевозок, указанный в плане;

q_n - грузоподъёмность автомобиля (для осуществления перевозок выбран автомобиль модели МАЗ-5336 грузоподъёмностью q_n = 10 т);

г_c - коэффициент статического использования грузоподъёмности (для грузов 1-го класса г_с = 1).

Подготовка исходных данных для их занесения в матрицу транспортной задачи приводится в табличной форме и представлена в таблице 1.13.

Таблица 1.13 - Подготовка исходных данных для маршрутизации перевозок грузов

В клетках матрицы транспортной задачи указывается расстояние перевозки и приведенный к первому классу объём грузов в тоннах по отправителям и получателям. Таким образом, завершается построение так называемой «специальной таблицы» транспортной задачи, представленной в виде таблицы 1.14.

Таблица 1.14 - Специальная таблица транспортной задачи

2. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

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

Существует несколько методов получения опорного плана - метод северо-западного угла (диагональный) и ряд более эффективных, ускоряющих в дальнейшем отыскание оптимального решения, - метод абсолютного двойного предпочтения, метод минимального элемента, метод минимальных разностей и другие. Распределение груза рекомендуется производить методом минимального элемента, как одним из наиболее простых и эффективных. В соответствии с этим методом опорный план составляется по следующему правилу: выбирается минимальное расстояние, клетки загружаются объемами перевозок Q_ij, пока не будут удовлетворены ограничения по вывозу и завозу груза. Объем груза Q_ij, заносимый в клетку ij, определяется как минимум от объёма вывоза по строке и объёма завоза по столбцу с учётом ранее назначенных других перевозок. Выбор загрузки именно таким образом обусловлен тем, что, во-первых, необходимо переправить как можно больше груза по маршруту с наименьшим расстоянием, во-вторых, невозможно переправить груза больше, чем имеется у данного грузоотправителя, в-третьих, не должно пересылаться грузополучателю больше груза, чем ему требуется. Выбранное значение и будет представлять собой загрузку данной клетки. Оставшиеся загрузки проставляются по возможности в клетки с наименьшими расстояниями. При проставлении загрузок необходимо соблюдать условия, оговоренные выше.

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

Таблица 2.1 - Начальный опорный план перевозок грузов

2.2 Нахождение оптимального плана транспортной задачи методом потенциалов

Далее полученный план перевозок проверяется на оптимальность с помощью метода потенциалов. В таблицу транспортной задачи вводятся вспомогательные строка и столбец, в которые заносятся специальные показатели, называемые потенциалами. Метод потенциалов основан на том, что если к расстояниям любой строки (столбца) таблицы прибавить или отнять произвольное одно и то же число, то оценка оптимальности относительно не изменится. Если например, от расстояний каждой i-ой строки отнимать число u_i и от расстояний каждого j-ого столбца - v_j, то тогда относительной оценкой любой клетки ij может служить параметр ?_ij вместо l_ij, рассчитываемый по формуле:

(2.1)

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

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

Если значение оценочного параметра свободной клетки будет меньше нуля (?_ij<0), то это значит, что перераспределение корреспонденций по клеткам таблицы с занесением объема перевозок в такую свободную клетку, называемую потенциальной, уменьшит значение целевой функции.

Отсутствие клеток со значением параметра ?_ij<0, означает, что проверяемый план закрепления потребителей за постановщиками является оптимальным. Проверка исходного опорного плана перевозок на оптимальность представлена в таблице 2.2. Суммарный холостой пробег автомобилей составляет 6750 км. План не оптимален, т. К. имеются отрицательные оценки. В связи с этим для клетки минимальным отрицательным потенциалом (А₁,Б₁) составлен цикл для перехода к следующему (улучшенному) опорному плану. Соответствующие клетки цикла помечаются попеременно «+» и «-», а их значения соответственно увеличиваются или уменьшаются.

Таблица 2.2 - Проверка начального опорного плана на оптимальность и переход к следующему плану перевозок

Полученный опорный план является оптимальным и представлен в таблице 2.3. Суммарный холостой пробег автомобилей составляет 24500 км.

Таблица 2.3 - Оптимальный план перевозок

3. РАЗРАБОТКА МАРШРУТОВ МЕТОДОМ СОВМЕЩЕННЫХ ПЛАНОВ И РАСЧЁТ МАРШРУТОВ

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

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

В тех клетках полученной таблицы совмещенных планов, где имеются две цифры (выделенная и невыделенная), получаются маятниковые маршруты, количество ездок на которых равно минимуму {X_ij, X_ji}, где X_ij- количество ездок с грузом и X_ji - количество ездок без груза. Включенное в маршрут количество ездок с грузом или без груза из дальнейшего рассмотрения исключается.

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

Применим метод совмещённых планов для данных, представленных в таблице 3.1.

Таблица 3.1 - Совмещённый план гружёных и порожних ездок

Как видно из таблицы 3.1, для данных планов перевозок имеются два маятниковых маршрута с обратным порожним пробегом: А₂Б₂ - Б₂А₂ (1000 ездок), А₃Б₂ - Б₂А₃ (250 ездок). С помощью построения контуров образуется три рациональных кольцевых маршрута, представленные в таблицах 3.2-3.4 соответственно: А₁Б₁?Б₁Б₁?Б₁А₁?А₁А₁ (250 ездок), А₂Б₂?Б₂Б₂?Б₄А₂?А₂А₂ (200 ездок), А₁Б₁?Б₁А₂?А₂Б₃?Б₃А₁ (250 ездок).

Таблица 3.2 - Рациональный кольцевой маршрут №1

Таблица 3.3 - Рациональный кольцевой маршрут №2

Таблица 3.4 - Рациональный кольцевой маршрут №3

После того, как получены маршруты движения при перевозке груза условными однотонными автомобилями, разрабатываются схемы маршрутов перевозки грузов с указанием конкретных видов грузов и объемом их перевозки, порожних пробегов от пунктов разгрузки в пункты погрузки. При этом фактическое количество k-го груза Q_ijk, перевозимого между двумя пунктами, определяется по формуле:

(3.1)

гдеx_ijk- количество ездок автомобилей с k-м грузом между этими пунктами.

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

(3.2)

Составленные маршруты приведены в таблице 3.5.

Таблица 3.5 - Мощности грузопотока на маршруте

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

3.2 Оптимальное закрепление маршрутов за АТП

Закрепление маршрутов за автотранспортными предприятиями (АТП) требует решения двух взаимосвязанных вопросов: определения начального и соответствующего ему конечного пунктов маршрута и непосредственно закрепления маршрута за АТП.

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

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

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

Поэтому критерием выбора начального пункта маршрута и прикрепления его к АТП является оценочный параметр (скорректированный нулевой пробег), рассчитываемый по формуле:

(3.3)

где ?l_kij - скорректированный нулевой пробег, км; l_ki- расстояние от k-го АТП до i-го первого пункта погрузки (первый нулевой пробег), км; l_jk- расстояние от j-го последнего пункта выгрузки до k-го АТП (второй нулевой пробег), км; l_ij - расстояние между j-м последним пунктом выгрузки и i-м первым пунктом погрузки, км.

При закреплении маршрутов за АТП рассчитываются значения оценочного параметра для всех возможных вариантов начала выполнения маршрута и по каждому АТП. Расчёты выполняются в табличной форме и представлены в таблице3.6.

Таблица 3.6 - Расчёт скорректированных нулевых пробегов

Из возможных вариантов принимается тот, для которого значение скорректированного нулевого пробега ?l_kij- является минимальным. Выбирается наилучший вариант начала и соответственно окончания выполнения маршрута относительно каждого АТП.

По результатам расчётов получен следующий вариант оптимального закрепления маршрутов за АТП:

М1: А₂Б_2? Б₂А₂АТП №1 (Б₂)

М2: А₃Б_2? Б₂А₃АТП №1 (Б₂)

Р1: А₁Б₁?Б₁Б₁?Б₁А₁?А₁А₁АТП №1 (Б₂)

Р2: А₂Б₂?Б₂Б₂?Б₂А₂?А₂А₂АТП №2 (Б₄)

Р3: А₁Б₁?Б₁А₂?А₂Б₃?Б₃А₁АТП №1 (Б₂)

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

3.3 Расчёт маршрутов

А₃Б₂ - Б₂А₃= 250т

Исходные данные:

T_н= 9 ч;

q_n = 10 т;

t_п-р= 0,91 ч;

V_m = 27,9 км/ч;

l_x= 4 км;

l₀₁= 4 км;

l₀₂= 0 км;

lм= 8 км;

Q_сут= 250 т;

l_ег= 4 км

Т_м = 9-(4+0)/27,9=8,86 ч;

t_о=8/27,9+0,91*1=1,20 ч;

z₀=8,86/1,20=7,25 =8 об.;

P_Q=10*1*8*1=80 т;

=4/8=0,5;

=(4*8)/(4*8+4*7+4+4) = 0,031;

L_гр=4*8=32 км;

А=250/80 = 3,125 ? 4 авт.;

T_н'=(4*8+4*7+4+0)/27,9+0,91*8*1=9,574ч;

Маршрут №3

С целью сравнительной характеристики эффективности рассчитанных маршрутов на основании имеющихся данных рассчитаем следующие нерациональные маятниковые маршруты: