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

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

(1.8)

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

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

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

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

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

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

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

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

2.1 Построение начального опорного плана транспортной задачи

Для отыскания оптимального закрепления потребителей за поставщиками необходимо сделать в полученной таблице первоначальное закрепление, т. е. получить произвольный план закрепления (опорный), удовлетворяющий ограничениям (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. РАЗРАБОТКА МАРШРУТОВ МЕТОДОМ СОВМЕЩЕННЫХ ПЛАНОВ И РАСЧЁТ МАРШРУТОВ

3.1 Маршрутизация перевозок с помощью метода совмещённых планов

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

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

В тех клетках полученной таблицы совмещенных планов, где имеются две цифры (выделенная и невыделенная), получаются маятниковые маршруты, количество ездок на которых равно минимуму {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-м грузом между этими пунктами.