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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

(1)

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

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

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

; , (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

Расчет кратчайших расстояний для пункта А2

Расчет кратчайших расстояний для пункта А3

Расчет кратчайших расстояний для пункта А4

Расчет кратчайших расстояний для пункта А5

Расчет кратчайших расстояний для пункта Б1

Расчет кратчайших расстояний для пункта Б2

Расчет кратчайших расстояний для пункта Б3

Расчет кратчайших расстояний для пункта Б4

Расчет кратчайших расстояний для пункта Б5

Кратчайшие расстояния между пунктами транспортной сети

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

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

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

(3)

(4)

(5)

(6)

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

(7)

Поставленная таким образом задача (ограничения (1.3), (1.4), (1.6), (1.7) и целевая функция (1.5)) является закрытой моделью классической транспортной задачи линейного программирования, в результате решения которой по известным значениям находятся неизвестные значения корреспонденций .

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

Грузы, перевозимые одним типом подвижного состава

транспортный поставщик подвижной

В клетках матрицы транспортной задачи указывается расстояние перевозки и объем перевозок по отправителям и получателям; затем строится в виде матрицы возможный план перевозок (таблица 1.14).

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

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

Распределение груза рекомендуется производить методом минимального элемента, как одним из наиболее простых и эффективных.

План перевозок грузов

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

Основан метод потенциалов на том, что если к расстояниям любой строки (столбца) таблицы прибавить или отнять произвольное одно и тоже число, то оценка оптимальности относительно не изменится. Если, например, от расстояний каждой i-ой строки отнимать число u_i и от расстояний каждого j-ого столбца - u_j, то тогда относительной оценкой любой клетки ij может служить параметр u_ij вместо l_ij, рассчитываемый по формуле:

(9)

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

Величина параметра u_ij характеризует общее увеличение пробега с грузом, достигаемое при включении в план единицы груза по корреспонденции ij по сравнению с рассматриваемым планом.

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

Отсутствие клеток со значением параметра u_ij <0, означает, что проверяемый план закрепления потребителей за постановщиками является оптимальным.

L_x1=100*1+50*3+125*25+25*23+100*19+125*11+25*20+125*14+25*13=10300 км

Суммарный холостой пробег автомобилей для данного плана перевозок составляет 10300 км, однако он не является оптимальным, так как есть отрицательные оценки. Для улучшения плана перевозок строится замкнутый контур для клетки (Б2,А3). Он содержит клетки (Б2,А3), (Б2,А1), (Б5,А1), (Б5,А3). Клетки (Б2,А3), (Б5,А1) помечаются знаком “+”, а клетки (Б2,А1) и (Б5,А3) - знаком “-”. Так как для клеток, помеченных “-”, минимальный объем перевозок равен 125 ездок, то отнимать и прибавлять необходимо 125 единиц. Получается матрица с новым планом перевозок.

L_x2=100*1+50*3+0*25+25*23+125*16+100*19+125*11+150*20+25*13=9425 км

Суммарный холостой пробег автомобилей для данного плана перевозок составляет 9425 км, однако и он не является оптимальным. Для улучшения плана перевозок строится цикл для клетки (Б5,А4).

Оптимальный план перевозок

L_x3=75*1+75*3+0*25+25*23+125*16+100*19+125*11+150*20+25*9=9375 км

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

Размещено на Allbest.ru