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

Жанр: Экономика

Рейтинг:

Просмотров: 1030

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

3.1.1. Транспортная задача в матричной постановке и ее свойства. Вернемся к транспортной задаче в матричной, постановке, о которой мы уже упоминали при рассмотрении вопросов построения математических моделей. Напомним, что данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (║xi,j║mxn), который минимизирует целевую функцию

на множестве допустимых планов

при соблюдении условия баланса

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

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n) х mn. Матрицы систем уравнений в ограничениях (3.2) и (3.3) имеют ранги, равные соответственно m и n. Однако, если, с одной стороны, просуммироватьуравнения (3.2) по m, а с другой — уравнения (3.3) по n, то в силу (3.5) получим одно и то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n-1, и ее невырожденный базисный план должен содержать m+n-1 ненулевых компонент.

Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц, структура которых представлена на рис.3.1.

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта аi), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится

цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (хi,j = 0), называют свободными, а ненулевые — занятыми (xi,j >0).

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

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

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

Рассмотрим применение метода северо-западного угла на конкретном примере. Транспортная таблица 3.1 содержит условия некоторой задачи, а в табл. 3.2 показан процесс поиска допустимого плана, включая последовательное изменение объема нераспределенных запасов и неудовлетворенных потребностей. Стрелки отражают траекторию перехода по клеткам транспортной таблицы, а цифры, находящиеся за ее пределами, — текущие нераспределенные остатки после назначения объема для очередной клетки.

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

3.1.3. Критерий оптимальности. Рассмотрим более подробно структуру матрицы транспортной задачи. Схематично она показана на рис. 3.2.

Из него видно, что матрица имеет размерность (m+n) х mn, состоит из нулей и единиц и распадается на две группы однотипных блоков. Первая (верхняя) соответствует ограничениям на

объемы вывоза из пунктов производства, а вторая — ограничениям на удовлетворение потребностей в пунктах производства.

Построим двойственную задачу. С учетом специфической структуры матрицы транспортной задачи вектор двойственных переменных будет иметь размерность m+n, причем его компоненты, соответствующие первой группе ограничений, обозначим через (-ui), i∊1: m, а второй — через vj , j∊1:n (рис. 3.2). Тогда двойственная задача будет иметь вид:

Переменные ui называют потенциалами пунктов производства, а vj — потенциалами пунктов потребления. Применяя доказанные в главе 1 теоремы двойственности (см. теорему 1.7), можно получить критерий оптимальности для плана транспортной задачи:

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

Данные условия имеют содержательную экономическую интерпретацию. Потенциалы ui, и vj можно рассматривать как цены на перевозимый груз в пунктах производства и потребления (это, кстати, объясняет то, зачем понадобилось обозначать соответствующую двойственную переменную через (-ui)). Тогда, согласно условию (3.8), для оптимальности плана перевозок требуется, чтобы на тех маршрутах, по которым действительно перевозится груз, его цена в пункте потребления возрастала ровно на цену его перевозки, а в соответствии с условием (3.9) в оптимальном плане цена груза в пункте потребления не может быть меньше его цены в пункте производства с учетом затрат на транспортировку.

3.1.4. Алгоритм метода потенциалов для транспортной задачи. Критерий (3.8)-(3.9) положен в основу одного из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом.

Точно так же как транспортная задача является частным случаем задачи ЛП, так и метод потенциалов, вообще говоря, может трактоваться как разновидность симплексных процедур. Он представляет собой итеративный процесс, на каждом шаге которого рассматривается некоторый текущий базисный план, проверяется его оптимальность, и при необходимости определяется переход к «лучшему» базисному плану.

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

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

Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В табл. 3.3 переписаны условия задачи из табл. 3.1 и ее допустимый базисный план, построенный методом северо-западного угла (см. табл. 3.2).

Потенциал первого пункта потребления принимаем равным нулю (v1=0). Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками. В данном случае их два (это первый и второй пункты), получаем:

Имея u2 и учитывая, что во второй строке таблицы существуют еще ненулевые компоненты х2,2 и х2,3, можно определить v2 = u2 + c2,2 = -10+17=7 и v3 = u2 +c2,3 = -10+15=5, после чего появляется возможность рассчитать u3 = v3 – c3,3 =5 - 25 = - 20 и, наконец, v4 = u3+ c3,4 = -20 +21=1. В результате получаем полную систему потенциалов, показанную в табл. 3.3.

Для свободных клеток транспортной таблицы вычисляются величины αi,j = vj - ui, называемые разностями потенциалов. В табл. 3.4 они выписаны для всех небазисных клеток под ценами.

Разность потенциалов αi,j можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j. Согласно критерию оптимальности (3.8)-(3.9), если все αi,j ≤ сi,j, то план оптимален, в противном случае, если существует хотя бы одна разность потенциалов αi,j > сi,j, то он может быть улучшен. Процесс «улучшения» плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

Кандидатом на ввод, очевидно, может быть любая клетка, в которой αi,j > сi,j, поскольку после ввода в базис будет обеспечено равенство αi,j = сi,j. Для определенности обычно рекомендуется брать ту клетку, в которой оценка αi,j - сi,j  максимальна. В рассматриваемом нами примере это будет клетка (3, 1).

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

Логика алгоритма построения цепочки достаточно проста: «выйдя» из клетки (3,1) в горизонтальном направлении, мы должны «остановиться» в той занятой клетке плана, из которой сможем двигаться дальше по вертикали. В данном примере этому требованию удовлетворяют как клетка (3,3), так и клетка (3,4). Однако цепочка от (3,4) не может быть продолжена дальше, в то время как двигаясь от (3,3) по вертикали к (2,3) и далее к (2,1), мы возвращаемся к исходной клетке (3,1) и образуем замкнутый цикл.

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины: нечетные — знаком «+», а четные знаком «—». Знаком «+» отмечаются те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком «—» — те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком «—», выбирается клетка с наименьшим значением хi,j (обозначим его θ). Она и становится кандидатом на вывод, т. к. уменьшение объема перевозок на большую величину может привести к отрицательным значениям хi,j в других «минусовых» клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком «+», добавляется объем θ, а из объемов клеток, помеченных знаком «—», он вычитается. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описанные выше действия повторяются.

В нашем примере знаком «—» отмечены клетки (2,1) и (3,3), причем x2,1 = 6, x3,3 = 26. Вычислив значение θ = min{x2,1, x3,3} = 6, осуществляем преобразование и переходим к следующему базисному плану, показанному в табл. 3.6.

Для вновь полученного плана повторяются действия стандартной итерации: рассчитываются потенциалы и оценки для небазисных клеток транспортной таблицы. Как можно видеть, план в табл. 3.6 также не является оптимальным (в клетке (1,3) αi,j = 25 > сi,j = 21), поэтому вновь строим цепочку преобразования плана и переходим к следующему базисному плану (табл. 3.7).

Из транспортной таблицы 3.7 видно, что полученный план оптимален, так как все разности потенциалов для небазисных клеток αi,j  = vj – ui не превышают соответствующих цен сi,j. По данному плану вычисляется оптимальное (наименьшее) значение суммарных издержек на перевозку

Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке: если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком «—», то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем m+n-1 ненулевых компонент. Способ преодоления вырожденности в транспортной задаче весьма прост, а именно: предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К такому выводу легко прийти, если положить, что добавляемые фиктивные клетки содержат некоторый малый объем ε.