ТРАНСПОРТНЫЕ МОДЕЛИ

специальный класс задач линейного программирования. Эти модели часто описывают перемещение

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

транспортной задачи в виде сети с m пунктами отправления и

n пунктами назначения, которые показаны в виде узлов сети. Дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой (i, j), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: (1) стоимость сij перевозки единицы груза из пункта i в пункт j и (2) количество перевозимого груза хij. Объем грузов в пункте отправления i равен ai, a объем грузов в пункте назначения j — bj,-. Задача состоит в определении неизвестных величин xij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объемы грузов в пунктах отправления (предложения) и пунктах назначения (спрос).
Когда суммарный объем предложений (грузов, имеющихся в пунктах отправления) не равен общему объему спроса на товары (грузы), запрашиваемые пунктами назначения, транспортная модель называется несбалансированной. Далее мы последовательно будем применять прием, позволяющий любую несбалансированную транспортную задачу сделать сбалансированной. Для этого будем вводить фиктивные пункты назначения или отправления. Выполнение баланса транспортной задачи необходимо для того, чтобы иметь возможность применить алгоритм решения, построенный на использовании транспортных таблиц.

разделе будет описан алгоритм решения транспортной задачи. Этот алгоритм повторяет

основные шаги симплекс-метода (глава 3). Однако для представления данных, вместо обычных симплекс-таблиц, используются транспортные таблицы со специальной структурой.
Алгоритм решения транспортной задачи будет проиллюстрирован на следующем примере.
Пример 5.3-1
Транспортная компания занимается перевозкой зерна специальными зерновозами от трех элеваторов к четырем мельницам. В табл. 5.16 показаны возможности отгрузки зерна (предложения) элеваторами (в зерновозах) и потребности (спрос) мельниц (также в зерновозах), а также стоимость перевозки зерна одним зерновозом от элеваторов к мельницам. Стоимость перевозок сij приведена в сотнях долларов.

между элеваторами и мельницами с минимальной стоимостью. Для этого необходимо

найти объемы перевозок хij между i-м элеватором и j-й мельницей.
Последовательность шагов алгоритма решения транспортной задачи в точности повторяет аналогичную последовательность этапов симплексного алгоритма.
Шаг 1. Определяем начальное базисное допустимое решение, затем переходим к выполнению второго шага.
Шаг 2. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определяем вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности, вычисления заканчиваются; в противном случае переходим к третьему шагу.
Шаг 3. С помощью условия допустимости симплекс-метода среди текущих базисных переменных определяем исключаемую. Затем находим новое базисное решение. Возвращаемся ко второму шагу. Рассмотрим каждый описанный шаг в отдельности.
Определение начального решения
Общая транспортная модель с m пунктами отправления и n пунктами назначения имеет m + n ограничений в виде равенств, по одному на каждый пункт отправления и назначения. Поскольку транспортная модель всегда сбалансирована (сумма предложений = сумме спроса), одно из этих равенств должно быть избыточным. Таким образом, транспортная модель имеет m + n - 1 независимых ограничений, отсюда вытекает, что начальное базисное решение состоит из m + n - 1 базисных переменных. Например, начальное решение в примере 5.3-1 содержит 3 + 4 – 1 = 6 базисных переменных.
Специальная структура транспортной модели для построения начального решения позволяет применить следующие методы (вместо использования искусственных переменных, как это делается в симплекс-методе).
1. Метод северо-западного угла.
2. Метод наименьшей стоимости.
3. Метод Фогеля.
Различие этих методов заключается в "качестве" начального решения, т.е. насколько начальное решение ближе к оптимальному. В общем случае метод Фогеля дает наилучшее решение, а метод северо-западного угла - наихудшее. Однако метод северо-западного угла требует меньшего объема вычислений.

Выполнение начинается с верхней левой ячейки (северо-западного угла) транспортной

таблицы, т.е. с переменной х11.
Шаг 1. Переменной х11 присваивается максимальное значение, допускаемое ограничениями на спрос и предложение.
Шаг 2. Вычеркивается строка (или столбец) с полностью реализованным предложением (с удовлетворенным спросом). Это означает, что в вычеркнутой строке (столбце) мы не будем присваивать значения остальным переменным (кроме переменной, определенной на первом шаге). Если одновременно удовлетворяются спрос и предложение, вычеркивается только строка или только столбец.
Шаг 3. Если не вычеркнута только одна строка или только один столбец, процесс останавливается. В противном случае переходим к ячейке справа, если вычеркнут столбец, или к нижележащей ячейке, если вычеркнута строка. Затем возвращаемся к первому шагу.
МЕТОД НАИМЕНЬШЕЙ СТОИМОСТИ (Метод минимального элемента) Данный метод находит лучшее начальное решение, чем метод северо-западного угла, поскольку выбирает переменные, которым соответствуют наименьшие стоимости. Сначала по всей транспортной таблице ведется поиск ячейки с наименьшей стоимостью. Затем переменной в этой ячейке присваивается наибольшее значение, допускаемое ограничениями на спрос и предложение. (Если таких переменных несколько, выбор произволен.) Далее вычеркивается соответствующий столбец или строка и соответствующим образом корректируются значения спроса и предложений. Если одновременно выполняются ограничения и по спросу, и по предложению, вычеркивается или строка, или столбец (точно так же, как в методе северо-западного угла). Затем просматриваются невычеркнутые ячейки, и выбирается новая ячейка с минимальной стоимостью. Описанный процесс продолжается до тех пор, пока не останется лишь одна невычеркнутая строка или столбец.

наименьшей стоимости и в общем случае находит лучшее начальное решение.

Алгоритм этого метода состоит из следующих шагов.
Шаг 1. Для каждой строки (столбца), которой соответствует строго положительное предложение (спрос), вычисляется штраф путем вычитания наименьшей стоимости из следующей по величине в данной строке (столбце).
Шаг 2. Выделяется строка или столбец с наибольшим штрафом. Если таковых несколько, выбор произволен. Из выделенной строки или столбца выбирается переменная, которой соответствует минимальная стоимость, и ей присваивается наибольшее значение, позволяемое ограничениями. Затем в соответствии с присвоенным значением переменной корректируются величины оставшегося неудовлетворенным спроса и нереализованного предложения. Строка или столбец, соответствующие выполненному ограничению, вычеркиваются из таблицы. Если одновременно выполняются ограничения и по спросу, и по предложению, вычеркивается только строка или только столбец, причем оставшейся строке (столбцу) приписывается нулевое предложение (спрос).
Шаг 3. а) Если не вычеркнута только одна строка или только один столбец с нулевым спросом или предложением, вычисления заканчиваются.
b) Если не вычеркнута только одна строка (столбец) с положительным предложением (спросом), в этой строке (столбце) методом наименьшей стоимости находятся базисные переменные, и вычисления заканчиваются.
c) Если всем не вычеркнутым строкам и столбцам соответствуют нулевые объемы предложения и спроса, методом наименьшей стоимости находятся нулевые базисные переменные, и вычисления заканчиваются.
d) Во всех остальных случаях необходимо перейти к шагу 1.
Обычно метод Фогеля дает наилучшее начальное решение для транспортной задачи.

После определения начального решения (с помощью одного из трех

методов, описанных в предыдущем разделе) применяется алгоритм, позволяющий найти оптимальное решение транспортной задачи.
Шаг 1. На основе симплексного условия оптимальности среди текущего множества небазисных переменных определяется вводимая в базис переменная, которая может улучшить значение целевой функции. Если условие оптимальности выполняется для всех небазисных переменных, вычисления заканчиваются, в противном случае необходимо перейти ко второму шагу.
Шаг 2. С помощью симплексного условия допустимости определяется исключаемая из базиса переменная. Происходит изменение базиса и возврат к первому шагу.
При изменении базиса в данном случае не используются вычисления, выполняемые при реализации симплекс-метода, - специальная структура транспортной таблицы позволяет значительно упростить вычисления.
Определение вводимой переменной среди текущих небазисных (т.е. среди тех переменных, которые не входят в начальное базисное решение) основано на вычислении коэффициентов z-строки, соответствующих небазисным переменным, с использованием метода потенциалов.
В методе потенциалов каждой строке i и каждому столбцу j транспортной таблицы ставятся в соответствие числа (потенциалы) ui и vj. Для каждой базисной переменной хij потенциалы ui и vj удовлетворяют уравнению
ui + vj = cij.
В рассматриваемой задаче имеем 7 неизвестных переменных (потенциалов) и 6 уравнений, соответствующих шести базисным переменным. Чтобы найти значения потенциалов из этой системы уравнений, нужно присвоить одному из них произвольное значение (обычно полагают u1 = 0) и затем последовательно вычислять значения остальных потенциалов.
Далее используя вычисленные значения потенциалов, для каждой небазисной переменной вычисляются величины ui + vj – сij. Результаты вычисления этих величин приведены в следующей таблице.
Вычисленные значения совместно с нулевыми значениями для базисных переменных (поскольку ui + vj – сij = 0 для любой базисной переменной xij) фактически являются коэффициентами z-строки симплекс-таблицы.

стоимости перевозок, вводимой в базис будет переменная, имеющая наибольший положительный

коэффициент в z-строке.
Описанные вычисления обычно выполняются непосредственно в транспортной таблице. В этом случае нет необходимости в явном виде выписывать уравнения для потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу u1 нулевого значения: u1 = 0. Затем вычисляются v-потенциалы для всех столбцов, имеющих базисные переменные в первой строке. Далее на основании уравнения для потенциалов, вычисляется величина остальных потенциалов. После того, как все потенциалы определены, вычисляются величины ui + vj – сij для каждой небазисной переменной xij. Эти величины показаны в левом нижнем углу ячеек транспортной таблицы.
Определив вводимую в базис переменную, далее следует определить исключаемую из базиса переменную. Напомним, если какая-либо переменная вводится в базис, одна из текущих базисных переменных должна стать небазисной (и равной нулю), чтобы количество базисных переменных оставалось постоянным.
Исключаемая из базиса переменная определяется следующим образом. Выбрав в качестве вводимой переменную xij мы хотим, чтобы перевозки по маршруту, соответствующему этой переменной, уменьшили общую стоимость перевозок. Какой объем груза можно перевести по этому маршруту? Обозначим через  количество груза, перевозимого по маршруту (i, j) (т.е. xij = ). Максимально возможное значение в определяем из следующих условий.
1. Должны выполняться ограничения на спрос и предложение.
2. Ни по какому маршруту не должны выполняться перевозки с отрицательным объемом грузов.
Эти условия позволяют найти значение  и определить исключаемую переменную. Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной (в данном примере — это ячейка (i, j)). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. Для любой вводимой переменной можно построить только один замкнутый цикл.

удовлетворить ограничениям по спросу и предложению, надо поочередно отнимать и

прибавлять  к значениям базисных переменных, расположенных в угловых ячейках цикла (не имеет значения направление обхода цикла: по часовой стрелке или против).
Определив значение для вводимой переменной и выбрав исключаемую переменную, далее следует откорректировать значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла. Имея новое базисное решение, следует повторить вычисления потенциалов.

Интерпретация метода потенциалов как симплекс-метода
Связь метода потенциалов с симплекс-методом основывается на соотношениях двойственности задач ЛП (раздел 4.4.2). Исходя из специальной структуры транспортной задачи (обратитесь к примеру 5.5-1, где показано, как транспортную задачу представить в виде стандартной задачи ЛП), двойственная ей задача будет записана в следующем виде.
Максимизировать z =

при ограничениях
ui + vj ≤ cij для всех i и j,
ui и vj — свободные переменные,
где
аi — предложение (объем грузов) пункта отправления i,
bj — спрос (заявка на грузы) пункта назначения j,
сij — стоимость перевозки единицы груза из пункта отправления i в пункт назначения j,
ui — двойственная переменная, соответствующая ограничению на предложение пункта отправления i,
vj — двойственная переменная, соответствующая ограничению на спрос пункта назначения j.

коэффициент при переменной хij в выражении целевой функции должен быть

равен разности между левой и правой частями соответствующего ограничения двойственной задачи, т.е. величине ui + vj – сij. Но как мы уже знаем, эта величина должна быть равной нулю для каждой базисной переменной. Другими словами, для этих переменных должно выполняться равенство ui + vj = сij. Имея m + n - 1 таких равенств и решая их как систему линейных уравнений (после присвоения какой-либо переменной произвольного значения, например u1 = 0), находим значения потенциалов м, и v/. Вычислив значения потенциалов, далее определяем вводимую в базис переменную среди всех небазисных как переменную, имеющую наибольшее положительное значение величины ui + vj – сij.
Присвоение одной из двойственных переменных произвольного значения (например, ui = 0) противоречит представлениям раздела 4.6, поскольку это присвоение показывает, что решение двойственной задачи (определяется вычисленными значениями двойственных переменных (потенциалов)) не единственно. В действительности, противоречия здесь нет, и решение упр. 5.3,с(2) объясняет, — почему.

работы" — вот подходящее краткое описание задачи о назначениях. В

этой задаче необходимо назначить работников на определенные работы; каждый работник может выполнять любую работу, хотя и с различной степенью мастерства. Если на некоторую работу назначается работник именно той квалификации, которая необходима для ее выполнения, тогда стоимость выполнения работы будет ниже, чем при назначении на данную работу работника неподходящей квалификации. Цель задачи — найти оптимальное (минимальной стоимости) распределение работников по всем заявленным работам.
Общая задача назначения n работников на n работ представлена в табл. 5.31.
Таблица 5.31












Коэффициент сij равен стоимости назначения работника i на работу j
(i, j = 1, 2, ..., n). То, что количество работников равно количеству работ, не является ограничением общности, поскольку всегда можно ввести в модель фиктивных работников или фиктивные работы.

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

пунктам назначения. В данном случае все величины спроса и предложения равны 1. Стоимость "транспортировки" рабочего i на работу j равна сij. Задачу о назначениях можно эффективно решить точно так же, как и транспортную задачу. Вместе с тем тот факт, что все величины спроса и предложения равны 1, привел к разработке упрощенного алгоритма решения, названного венгерским методом. Хотя этот метод не имеет никакого отношения к транспортной задаче, он, как и метод потенциалов, все равно основан на симплекс-методе.
Венгерский метод
Шаг 1. В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки.
Шаг 2. В матрице, полученной на первом шаге, найдем в каждом столбце минимальную стоимость и отнимем ее от других элементов столбца.
Шаг 3. Оптимальным назначениям будут соответствовать нулевые элементы, полученные на предыдущем шаге.
Обозначим через рi и qj минимальные стоимости соответственно в строке i и столбце j, определенные на первом и втором шагах описанного выше алгоритма. Минимальные стоимости по строкам находятся по исходной матрице стоимостей.
Теперь вычтем минимальные стоимости из элементов соответствующих строк, и в результате получим следующую матрицу.
На втором шаге алгоритма находим минимальные значения по столбцам и вычитаем их из элементов соответствующих столбцов.
В последней матрице подчеркнутые нулевые элементы определяют оптимальное решение.
Алгоритм венгерского метода в предыдущем примере завершен успешно, если нулевые элементы в конечной матрице соответствуют допустимому решению (в том смысле, что каждому ребенку назначена в точности одна работа). В некоторых случаях нулевые элементы, полученные на первом и втором шагах венгерского метода, не позволяют непосредственно получить допустимое решение. Тогда необходимы дополнительные действия для нахождения оптимального (допустимого) решения.

второго шагов описанного алгоритма не получено допустимое решение, выполните следующие

действия.
1) В последней матрице проведите минимальное число горизонтальных и вертикальных прямых по строкам и столбцам с тем, чтобы вычеркнуть в матрице все нулевые элементы.
2) Найдите наименьший невычеркнутый элемент и вычтите его из остальных невычеркнутых элементов и прибавьте к элементам, стоящим на пересечении проведенных на предыдущем шаге прямых.
3) Если новое распределение нулевых элементов не позволяет построить допустимое решение, повторите шаг 2,а. В противном случае перейдите к третьему шагу алгоритма.

Интерпретация венгерского метода как симплекс-метода
Задачу о назначении n работников на n видов работ можно представить в виде задачи линейного программирования следующим образом. Обозначим через cij стоимость назначения работника i на работу j и определим
Получаем следующую задачу ЛП.
Минимизировать z =

при выполнении условий

если ко всем элементам какой-либо строки или столбца матрицы стоимостей

(сij) прибавить константу или вычесть ее из этих элементов. Для доказательства этого обозначим через pi, и qj константы, вычитаемые из элементов строки i и столбца j соответственно. Таким образом, стоимость сij изменится и будет равна
c’ij = cij – pi - qj
Теперь покажем, что при коэффициентах целевой функции c’ij получим те же оптимальные значения переменных xij, что и при коэффициентах сij.






Поскольку новая целевая функция отличается от исходной только на константу, оптимальные значения переменных хij должны быть одинаковы в обоих случаях. Таким образом показано, что шаги 1 и 2 венгерского метода, где pi вычитаются из элементов строки i, a qj — из элементов столбца j матрицы стоимостей, приводят к эквивалентной задаче о назначениях. Поэтому, если нулевые элементы в матрице стоимостей, созданные на шаге 1 и 2 венгерского метода, позволяют найти допустимое решение, то оно должно быть оптимальным, поскольку стоимости в измененной матрице стоимостей не могут быть меньше нуля.
Если созданные нулевые элементы не могут привести к допустимому решению (как в примере 5.4-2), необходимо выполнить описанный выше шаг 2,а. Эта процедура опять основывается на симплекс-методе, и ее корректность можно обосновать, исходя из теории двойственности (глава 4) и теоремы о дополняющей нежесткости (глава 7). Пока мы не будем углубляться в это.

То, что сумма равна оптимальному значению целевой функции, вытекает из того, что данная сумма представляет собой целевую функцию двойственной задачи. Это видно из представленного в разделе 5.3.3 выражения для целевой функции задачи, двойственной транспортной задаче. (Подробности см. в [1].)

модель с промежуточными пунктами соответствует реальной ситуации, когда между исходными

и конечными пунктами перевозок имеются промежуточные пункты для временного хранения грузов (транзитные пункты). Эта модель более общая, чем обычная транспортная, где перевозки осуществляются непосредственно между пунктами отправления и назначения.
В этом разделе показано, как транспортную модель с промежуточными пунктами можно преобразовать (и решить) в обычную транспортную с помощью введения буфера.
Пример 5.5-1
Два автомобильных завода Р1 и Р2 связаны с тремя дилерами D1, D2 и D3, имеющими два транзитных (перевалочных) центра Т1 и T2, как показано на рис. 5.5. Заводы Р1 и Р2 производят 1000 и 1200 автомобилей. Заказы дилеров составляют соответственно 800, 900 и 300 автомобилей. Стоимость перевозок одного автомобиля (в сотнях долларов) показана на рис. 5.5.






Рис. 5.5
В данной модели перевозки транзитом могут осуществляться через любые пункты (в соответствии с направлением дуг на схеме), даже через некоторые пункты назначения. Поэтому пункты, которым соответствуют как входящие, так и выходящие дуги на схеме рис. 5.5, назовем транзитными (пункты T1, T2, D1 и D2). Оставшиеся будут либо истинными пунктами отправления (пункты Р1 и Р2), либо истинными пунктами назначения (в данной схеме такой пункт только один - D3). Эту модель можно преобразовать в обычную транспортную модель с шестью пунктами отправления (P1, P2, T1, T2, D1 и D2) и пятью пунктами назначения (T1, T2, D1, D2 и D3). Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом.

исходного предложения.
Объем предложения транзитного пункта = объем

исходного предложения + объем буфера.
Объем спроса истинного пункта назначения = объем исходного спроса.
Объем спроса транзитного пункта = объем исходного спроса + объем буфера.
Объем буфера должен быть таким, чтобы вместить объем всего предложения (или спроса). Обозначим через B объем буфера. Тогда
В = Общий объем предложения (или спроса) = 1000 + 1200 = (или = 800 + 900 + 500) = 2200 автомобилей.
Построенная транспортная модель, эквивалентная исходной задаче, представлена в табл. 5.44. Решение этой транспортной модели показано на рис. 5.6. Отметим "транзитный" эффект решения: дилер D2 получает 1400 автомобилей, из них 900 оставляет себе (для удовлетворения сноего спроса), а 500 отправляет дилеру D3.
Таблица 5.44














Рис. 5.6