Решение задач о планировании перевозок — страница 7

  • Просмотров 235
  • Скачиваний 7
  • Размер файла 58
    Кб

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

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