Курсовая работа: Решение задач о планировании перевозок

C_m,1 C_m,2 …… C_m,n

X_m,1 X_m,2 …… X_m,n A_m

B₁ B₂ …. B_n

Построение исходного допустимого плана в транспортной задаче

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге qвеличины текущих нераспределенных запасов обозначаются а _i ^{( q )} , а текущих неудовлетворенных потребностей — b_j ^{( q )} . Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем а _i ⁽⁰⁾ = а _i , b_j ⁽⁰⁾ = b_j . Для очередной клетки, расположенной в строке i и столбце j , рассматриваются значения нераспределенного запаса в i -ом пункте производства и неудовлетворенной потребности j -ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х _{i , j} = min {а _i ^{( q )} , b_j ^{( q )} }. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:

а _i ^{( q +1)} = а _i ^{( q )} - x_{i , j} , b_j ^{( q +1)} = b_j ^{( q )} - x_{i , j}

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

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

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

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

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

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

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

Алгоритм начинается с выбора некоторого допустимого базисного плана (первоначальный план перевозок, составленный, например, методом северо-западного угла). Если данный план не вырожденный, то он содержит m + n -1 ненулевых базисных клеток, и по нему можно так определить потенциалыu_i и v_j , чтобы для каждой базисной клетки (т. е. для той, в которой x_{i , j} > 0 ) выполнялось условие v_j - u_i = c_{i , j} , если x_{i , j} >0

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

Для этого составьте систему для заполненных клеток плана перевозок:v_j - u_i = c_{i , j} ; где c_{i , j} - стоимость перевозки из пункта i в пункт j .

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

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

Для того чтобы допустимый план транспортной задачи x_{i , j} был оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы u_i , v_j , для которых

v_j - u_i = c_{i , j} , если x_{i , j} >0,

v_j - u_i ≤ c_{i , j} , если x_{i , j} =0

Вычислите коэффициенты изменения стоимости ( dc_{i , j} ) для незаполненных клеток плана: d c_{i , j} = v_j - u_i - c_{i , j} ;

Заметьте: если все d c_{i , j} оказались отрицательными, то полученный план оптимальный. Если есть хотя бы один положительный элемент d c_{i , j} , то далее ведущей (опорной) клеткой будет клетка [i,j] (при d c_{i , 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

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

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

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

230 220 130 170 190 110

U1=0 240 150 90