Задача оптимизации грузопотоков в общем виде формулируется следующим образом: имеется множество поставщиков (пункты погрузки) и множество потребителей однородных грузов (пункты разгрузки). Известно количество грузов, имеющихся у поставщиков и объемы поставок потребителям. Определены кратчайшие расстояния между пунктами транспортной сети.

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

Рисунок 1 - Схема железнодорожного направления

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

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

(1.1)

m - количество поставщиков продукции;

n - количество потребителей продукции;

хij - объем перевозок от i-поставщика к j-потребителю;

lij - расстояние перевозки от i-поставщика к j-потребителю.

При этом действуют следующие ограничения:

; .

аi - объем вывоза груза от поставщика, т;

bj - объем завоза груза потребителю, т.

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

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

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

Опорный план должен отвечать следующим условиям:

1) он должен содержать m + n - 1 клеток, где

m - количество строк;

n - количество столбцов.

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

3) должно соблюдаться условие проверки плана на оптимальность методом потенциалов.

Доказано, что, если план является оптимальным, то ему соответствует система из m + n чисел, удовлетворяющих следующим условиям:

1) при хij > 0

2) при xij = 0.

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

Таблица 1.1 - Распределительная таблица оптимального закрепления потребителей за поставщиками каменного угля

Должно выполняться следующее условие: m + n - 1

5 + 3 - 1 = 7 (заполненных клеток)

Данный опорный план является оптимальным, т.к. соответствует первому условию и нельзя построить замкнутый контур.

Чтобы проверить план на оптимальность методом потенциалов, необходимо построить распределительную таблицу, в которую будут сведены все расчеты.

Таблица 1.2 - Проверка оптимальности плана перевозки каменного угля методом потенциалов

(1.2)

Далее производится проверка оптимальности по заполненным клеткам.

Далее проводится проверка по незаполненным клеткам.

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

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

Первоначальная клетка отмечается знаком «+», а затем в каждой последующей вершине происходит чередование знака. Из вершин контура, отмеченных знаком «-» выбирается клетка с наименьшим значением объема перевозки. Это число прибавляется к имеющимся значениям во всех клетках, отмеченных знаком «+» и вычитается из значений вершин, отмеченных знаком «-».

Таблица 1.3 - Улучшенный план перевозки

Производится проверка оптимальности по заполненным клеткам.

Далее проводится проверка по незаполненным клеткам.

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

Таблица 1.4 - Распределительная таблица оптимального закрепления потребителей за поставщиками нефтепродуктов

Должно выполняться следующее условие: m + n - 1

3 + 3 - 1 = 5 (заполненных клеток)

Данный опорный план является оптимальным, т.к. соответствует первому условию и нельзя построить замкнутый контур.

Чтобы проверить план на оптимальность методом потенциалов, необходимо построить распределительную таблицу, в которую будут сведены все расчеты.

Таблица 1.5 - Проверка оптимальности плана перевозки каменного угля методом потенциалов

Далее производится проверка оптимальности по заполненным клеткам.

Далее проводится проверка по незаполненным клеткам.

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

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

Рисунок 1.2 - Схема вагонопотоков на участке сети железных дорог

Полученная схема вагонопотоков является оптимальной при существующих запасах и потребностях станций в каменном угле и нефтепродуктах. Из схемы видно, что наибольшее количество вагонов следует в направлении станций В (для каменного угля) и Л и Б (для нефтепродуктов). Наиболее напряженным является участок Б-А за сутки по ним проходит 360 вагонов.

2 ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ЗАМКНУТОГО МАРШРУТА

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

Рисунок 2.2 - Схема возможных маршрутов коммивояжера

Постановка задачи. Имеется п пунктов, соединенных между собой дорогами так, что из любого транспортного узла можно проехать в любой другой пункт. Задана матрица lij транспортных расстояний между этими пунктами (время перевозки или поездки из пункта i в пункт j). Выезжая из одного пункта, коммивояжер должен побывать в других пунктах по одному разу и вернуться в исходный пункт. Поэтому маршрут коммивояжера образует замкнутый цикл без петель. Требуется найти такой маршрут, проходящий через все пункты и заканчивающийся в пункте выезда, чтобы пройденное расстояние (время поездки) было минимальным.

Решение. Дня решения этой задачи необходимо составить математическую модель. Введем обозначения: i и j - номера пунктов выезда и въезда, lij - расстояние от пункта i до пункта j. Из таблицы 2.1 видно, что lij в общем случае может быть не равно расстоянию в обратном направлении lij ? lji.

Таблица 2.1 - Расстояния между пунктами

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

xij={

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

0, если не поедет,

где i,j - 1, 2, ..., n. Требуется минимизировать выражение:

(2.1)

при следующих ограничениях:

,

где Ui и Uj - произвольные вещественные значения.

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

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

вычисление нижней границы (оценки);

разбиение на подмножества, т. е. ветвление;

пересчет оценок;

нахождение решений;

определение признака оптимальности;

оценка точности приближенного решения.

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

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

1. Обозначим через G0 множество всех циклов, среди которых отыскивается кратчайший цикл t*: l(t*)=min l(t). При этом под циклом будем понимать набор из n упорядоченных пар городов, образующих замкнутый маршрут, который проходит через каждый город только один раз:

t=[(i1,i2),(i2,i3),…,(in-1,in),(in,i1)].

Длина цикла равна (2.2)

2. Вычислим оценку для множества G0.Для этого введем понятие приведенной матрицы и процесса приведения.

Пусть hi=minj Сij,

тогда Cij'=Сij-hi0 и l(t)=.

Пусть Hj=mini Cij',

тогда Cij''=Cij'-Hj0 и l(t)=.

Полученная матрица С" называется приведенной. Она обладает тем свойством, что в каждой ее строке и столбце имеется по крайней мере один нуль. Процесс, позволяющий из неотрицательной матрицы С получить приведенную неотрицательную матрицу С", называется приведением. Сумма вычитаемых в процессе приведения элементов называется приводящими константами и обозначается hУ. Оптимальный план задачи о коммивояжере с матрицей С" является оптимальным и для задачи о коммивояжере с матрицей С. Длина цикла l(t) на приведенной матрице будет меньше длины цикла l(t) на исходной матрице на сумму приводящих констант: l(t)=l(t)+hУ.

Так как приведенная матрица содержит только неотрицательные элементы, то сумма приводящих констант может служить нижней границей длины цикла при исходной матрице С, т. е. является оценкой исходного множества G0: о(G0)=hУ.

3. Произведем ветвление множества G0 на два непересекающихся подмножества G1 и G2:

· подмножество G1 получается из множества G0 при добавлении следующего условия: из пункта r следует непосредственно идти в пункт s;

· подмножество G2 получается из множества G0 при добавлении условия: из пункта r запрещается непосредственный переход в пункт s.

При этом пару городов (r, s) выбирают так, чтобы множество G1 с наибольшей вероятностью содержало оптимальный цикл, а множество G2 - не содержало. Следовательно, пара (r, s) выбирается из множества пар претендентов (i, j), которым соответствуют нулевые элементы матрицы С, то есть Сij=0, таким образом, чтобы циклам, входящим в подмножество G2, соответствовали как можно более длинные пути. Так как по определению подмножества G2 путь по любому из этих циклов переходит из города r в некоторый промежуточный пункт j (js), а в город s коммивояжер приезжает из некоторого пункта i (ir), длина этого пути будет не меньше чем

И(r, s)=

Поэтому необходимо выбрать пару (r, s) так, чтобы И(r, s) было максимально, т. е.

И(r,s)= (2.3)

при условии, что Сij=0.

4. Выполним преобразование матрицы расстояний при ветвлении и пересчитаем оценки. Каждому подмножеству, полученному в результате ветвление, будет соответствовать своя приведенная матрица и своя оценка. Матрица С2, соответствующая подмножеству G2, получается из матрицы С в результате следующих преобразований:

· запрещается переезд из города r в город s: Сrs>;

· проводится процедура приведения матрицы. Оценка подмножества G2 равна оценке исходного множества G0 и И(r, s):

о(G2)=о(G0)+И(r, s).

Для построения матрицы С1 соответствующей подмножеству G1 выполняются следующие преобразования матрицы С:

· вычеркивается строка r и столбец s из матрицы С, так как из каждого города можно выезжать только один раз и в каждый город можно въезжать только один раз;

· запрещается переезд из города s в город r (Сsr>), а также все другие переезды, которые приводят к образованию замкнутых подциклов;

· выполняется процесс приведения матрицы С.

Оценка подмножества G1 равна оценке исходного множества G0 и сумме приводящих констант:

о( G1)=о( G0) +.

грузопоток транспортный сеть маршрут

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

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

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

2.2 РАСЧЕТ ОПТИМАЛЬНОГО ЗАМКНУТОГО МАРШРУТА