Решение задач о планировании перевозок

аi(q+1)= аi(q) - xi,j, bj(q+1)= bj(q) - xi,j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: аi(q+1)= 0 или bj(q

+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj(q+1)= 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi(q)=bj(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.

Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далеко от оптимального. Это происходит потому, что при его построении никак не учитываются значения ci,j. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.

Несбалансированная задача

Если сумма единиц товара поставщиков не равна сумме единиц товара потребителей, то задача не сбалансированная (открытая), иначе задача сбалансированная (закрытая).

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

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

Алгоритм начинается с выбора некоторого допустимого базисного плана (первоначальный план перевозок, составленный, например, методом северо-западного угла). Если данный план не вырожденный, то он содержит m+n-1 ненулевых базисных клеток, и по нему можно так определить потенциалыui и vj, чтобы для каждой базисной клетки (т. е. для той, в которой xi,j> 0) выполнялось условие vj-ui=ci,j, если xi,j>0

Переменные ui называют потенциалами пунктов производства, a vj — потенциалами пунктов потребления.

Для этого составьте систему для заполненных клеток плана перевозок:vj-ui=ci,j; где ci,j - стоимость перевозки из пункта i в пункт j.

Поскольку система содержит m+n-1 уравнение и m+n неизвестных, то один из потенциалов можно задать произвольно. После этого остальные неизвестные vj и ui - определяются однозначно.

Критерий оптимальности

Для того чтобы допустимый план транспортной задачи xi,j был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы ui, vj, для которых

vj-ui=ci,j, если xi,j>0,

vj-ui≤ci,j, если xi,j=0

Вычислите коэффициенты изменения стоимости (dci,j) для незаполненных клеток плана: dci,j = vj- ui - ci,j;

Заметьте: если все dci,j оказались отрицательными, то полученный план оптимальный. Если есть хотя бы один положительный элемент dci,j, то далее ведущей (опорной) клеткой будет клетка [i,j] (при dci,j>0).

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

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

Решение задачи

1. Определим модель задачи

b1+b2+b3+b4+b5+b6=230+220+130+170+190+110=1050

a1+a2+a3+a4+a5=240+360+180+120+150=1050

Так как Σai=Σbj, то модель задачи является закрытой.

2. Построим распределительную таблицу по методу северо-западного угла.

V1=8 V2=0 V3=5 V4=2 V5=1 V6=6

230 220 130 170 190 110

U1=0 240 150 90

U2=5 360 80 170 110

U3=4 180 180

U4=6 120 40 80

U5=9 150 40 110

3.Определяем целевую функцию Z для первого этапа по формуле

Z= ΣCij*Xij

Z1=90*5+150*8+80*13+170*7+110*6+180*4+40*6+80*7+40*14+110*15=8270

4.Определим потенциалы для заданных клеток, где U1=0 по формуле

Ui+Vj=Cij

5.определим оценки свободных клеток, исходя из условия:

Δij=Cij-( Ui+Vj)

Δ12=7 Δ35=5

Δ14=8 Δ36=1

Δ15=11 Δ41=0

Δ16=2 Δ43=1

Δ22=3 Δ44=5

Δ23=0 Δ46=2

Δ26=2 Δ51=-8

Δ31=0 Δ52=3

Δ33=2 Δ54=4

Δ34=3 Δ55=-2

 Скачать реферат