Транспортная задача и методы ее решения

из "Математические исследования операций в экономике "

Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. [c.110]
Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц, структура которых представлена на рис.3.1. [c.110]
Очевидно, что на каждом шаге выполняется хотя бы одно из равенств а +1)=0 или +1)=0. Если справедливо первое, то это означает, что весь запас f-ro пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i + 1, т. е. переместиться к следующей клетке вниз по столбцу. Если же Ь = 0, то значит, полностью удовлетворена потребность для /-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции. [c.112]
Основываясь на условии баланса запасов и потребностей (3.5), нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m + n-1, поэтому всегда останутся свободными (нулевыми) wn-(m + n-l) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (а( = j q) ). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает потерю одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана. [c.112]
Рассмотрим применение метода северо-западного угла на конкретном примере. Транспортная таблица 3.1 содержит условия некоторой задачи, а в табл. 3.2 показан процесс поиска допустимого плана, включая последовательное изменение объема нераспределенных запасов и неудовлетворенных потребностей. Стрелки отражают траекторию перехода по клеткам транспортной таблицы, а цифры, находящиеся за ее пределами, — текущие нераспределенные остатки после назначения объема для очередной клетки. [c.113]
Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения сц. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами. [c.113]
Данные условия имеют содержательную экономическую интерпретацию. Потенциалы щ и vf можно рассматривать как цены на перевозимый груз в пунктах производства и потребления (это, кстати, объясняет то, зачем понадобилось обозначать соответствующую двойственную переменную через (-и.)). Тогда, согласно условию (3.8), для оптимальности плана перевозок требуется, чтобы на тех маршрутах, по которым действительно перевозится груз, его цена в пункте потребления возрастала ровно на цену его перевозки, а в соответствии с условием (3.9) в оптимальном плане цена груза в пункте потребления не может быть меньше его цены в пункте производства с учетом затрат на транспортировку. [c.115]
Точно так же как транспортная задача является частным случаем задачи ЛП, так и метод потенциалов, вообще говоря, может трактоваться как разновидность симплексных процедур. Он представляет собой итеративный процесс, на каждом шаге которого рассматривается некоторый текущий базисный план, проверяется его оптимальность, и при необходимости определяется переход к лучшему базисному плану. [c.115]
Поскольку система (ЗЛО) содержит т + /г-1 уравнение и неизвестных, то один из потенциалов можно задать произвольно (например, приравнять vl или щ к нулю). После этого остальные неизвестные щ и vj определяются однозначно. [c.116]
Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В табл. 3.3 переписаны условия задачи из табл. 3.1 и ее допустимый базисный план, построенный методом северо-западного угла (см. табл. 3.2). [c.116]
Кандидатом на ввод, очевидно, может быть любая клетка, в которой ai / Сц, поскольку после ввода в базис будет обеспечено равенство af/. =с . Для определенности обычно рекомендуется брать ту клетку, в которой оценка a -с,.. максимальна. В рассматриваемом нами примере это будет клетка (3, 1). [c.117]
Выводимая клетка определяется с помощью так называемой цепочки преобразования плана, описывающей характер перераспределения грузовых потоков. В соответствии со свойствами транспортной задачи для невырожденного базисного плана в текущей таблице можно образовать замкнутую цепочку, состоящую только их вертикальных и горизонтальных звеньев, одной из вершин которой является выбранная свободная клетка, а остальные — занятые клетки. В табл. 3.5 показана цепочка преобразования текущего плана относительно вводимой в него клетки (3, 1). [c.117]
Логика алгоритма построения цепочки достаточно проста выйдя из клетки (3,1) в горизонтальном направлении, мы должны остановиться в той занятой клетке плана, из которой сможем двигаться дальше по вертикали. В данном примере этому требованию удовлетворяют как клетка (3,3), так и клетка (3,4). Однако цепочка от (3,4) не может быть продолжена дальше, в то время как двигаясь от (3,3) по вертикали к (2,3) и далее к (2.1), мы возвращаемся к исходной клетке (3,1) и образуем замкнутый цикл. [c.118]
В нашем примере знаком — отмечены клетки (2,1) и (3,3), причем 2,i =6, я33 =26. Вычислив значение 6 = тт л 21, я33 = 6, осуществляем преобразование и переходим к следующему базисному плану, показанному в табл. 3.6. [c.119]
Для вновь полученного плана повторяются действия стандартной итерации рассчитываются потенциалы и оценки для небазисных клеток транспортной таблицы. Как можно видеть, план в табл. 3.6 также не является оптимальным (в клетке (1,3) ос/ - =25 с/у- =21), поэтому вновь строим цепочку преобразования плана и переходим к следующему базисному плану (табл. 3.7). [c.119]

Вернуться к основной статье