Транспортная задача. 
Экономико-математические методы и прикладные модели

Как показано выше, многие прикладные модели в экономике сводятся к задачам линейного программирования. Практически все задачи линейного программирования можно решить, используя ту или иную модификацию симплексного метода. Однако существуют более эффективные вычислительные процедуры решения некоторых типов задач линейного программирования, основанные на специфике ограничений этих задач. Рассмотрим так называемую транспортную задачу по критерию стоимости, которую можно сформулировать следующим образом.

В m пунктах отправления А₁, А₂, …, А_m, которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим a_i (i = 1, 2,…, m). Данный продукт потребляется в n пунктах В₁, В₂,…, В_n, которые будем называть потребителями; объем потребления обозначим b_j (j = 1,2,…, п). Известны расходы на перевозку единицы продукта из пункта А_i в пункт B_j, которые равны С_у и приведены в матрице транспортных расходов С = (с_ij).

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

Обозначим количество продукта, перевозимого из пункта A_i в пункт В_j через х_ij. Совокупность всех переменных Xj для краткости обозначим X, тогда целевая функция задачи будет иметь вид.

(3.15).

а ограничения выглядят следующим образом:

(3.16).

(3.17).

Условия (3.16) означают полное удовлетворение спроса во всех пунктах потребления; условия (3.17) определяют полный вывоз продукции от всех поставщиков.

Необходимым и достаточным условием разрешимости задачи (3.15)-(3.17) является условие баланса:

(3.18).

Транспортная задача, в которой имеет место равенство (3.18), называется закрытой и может быть решена как задача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым методом является метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал u_j, который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал Vj, который можно принять условно за цену продукта в пункте потребителя. В простейшем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т. е.

(3.19).

Алгоритм метода потенциалов для закрытой транспортной задачи детально описан в ряде учебных пособий (см., например, [6]). Первым этапом этого алгоритма является составление начального распределения (начального плана перевозок); для реализации этого начального этапа имеется в свою очередь ряд методов: северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля и др. Вторым этапом служат построение системы потенциалов на основе равенства (3.19) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу, содержание которого заключается в реализации так называемых циклов перераспределения (корректировка плана прикрепления потребителей к поставщикам), после чего переходят опять ко второму этапу. Совокупность процедур третьего и второго этапов образует одну итерацию; эти итерации повторяются, пока план перевозок не окажется оптимальным по критерию (3.15).

Если баланс (3.18) не выполняется, то ограничения (3.16) или (3.17) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче путем ввода или фиктивного потребителя, если в неравенства превращаются условия (3.17), или фиктивного поставщика — в случае превращения в неравенства ограничений (3.16) (см. ниже пример 3.5).

Рассмотрим этапы реализации метода потенциалов для закрытой транспортной задачи более подробно. Прежде всего следует отметить, что при условии баланса (3.18) ранг системы линейных уравнений (3.16), (3.17) равен т + п — 1; таким образом из общего числа m x n неизвестных базисных неизвестных будет т + п — 1. Вследствие этого при любом допустимом базисном распределении в матрице перевозок (таблице поставок), представленной в общем виде в табл. 3.5, будет занято ровно т + п — 1 клеток, которые будем называть базисными в отличие от остальных, свободных, клеток; занятые клетки будем отмечать диагональной чертой.

Таблица 3.5

Этап 1. Первоначальное закрепление потребителей за поставщиками. Рассмотрим два метода получения начального распределения (начального опорного плана): метод северо-западного угла и метод наименьших стоимостей. При каждом из этих методов при заполнении некоторой клетки, кроме последней, вычеркивается или только строка матрицы перевозок, или только столбец; лишь при заполнении последней клетки вычеркиваются и строка, и столбец. Такой подход будет гарантировать, что базисных клеток будет ровно т + п — 1. Если при заполнении некоторой (не последней) клетки одновременно удовлетворяются мощности и поставщика, и потребителя, то вычеркивается, например, только строка, а в соответствующем столбце заполняется незанятая клетка так называемой нулевой поставкой, после чего вычеркивается и столбец. Для идентификации клетки обычно в скобках указываются номера ее строки и столбца.

В методе северо-западного угла всегда в первую очередь заполняется клетка (из числа невычеркнутых), стоящая в верхнем левом (северо-западном) углу матрицы перевозок. Пример составления начального распределения данным методом показан в табл. 3.6: заполняется клетка (1; 1) и вычеркивается первый столбец, заполняется клетка (1; 2) и вычеркивается первая строка; заполняется клетка (2; 2) и вычеркивается второй столбец; заполняется клетка (2; 3) и вычеркивается вторая строка; заполняется клетка (3; 3) и вычеркивается третий столбец; наконец, заполняется клетка (3; 4) и вычеркиваются последние строка и столбец. Число запятых клеток равно m + n — 1 = 3 + 4 — 1 = 6. Суммарные затраты на реализацию данного плана перевозок составят

Таблица 3.6

Недостатком данного метода является то, что он не учитывает значения элементов с_# матрицы транспортных расходов, в результате чего полученное этим методом начальное распределение (начальный опорный план перевозок) может быть достаточно далеко от оптимального.

В различных модификациях метода наименьших стоимостей заполнение клеток матрицы перевозок проводится с учетом значений величин с_ij. Так, в модификации «двойного предпочтения» отмечают клетки с наименьшими стоимостями перевозок сначала по каждой строке, а затем по каждому столбцу. Клетки, имеющие две отметки, заполняют в первую очередь, затем заполняют клетки с одной отметкой, а данные о нераспределенном грузе записывают в неотмеченные клетки с наименьшими стоимостями. При этом из двух клеток с одинаковой стоимостью перевозок предпочтение отдается клетке, через которую осуществляется больший объем перевозок. Вычеркивание строк и столбцов при заполнении клеток проводится по описанным выше правилам. Пример начального распределения методом наименьших стоимостей дня тех же исходных данных, что и ранее, представлен в табл. 3.7.

Порядок заполнения клеток: (2; 1), (3; 2), (1; 3), (2; 4), (1; 4), (3; 4). Суммарные затраты на перевозки, представленные в табл. 3.7, составляют.

Таблица 3.7

Следовательно, данный план перевозок значительно ближе к оптимальному, чем план, составленный по методу северо-западного угла.

Этап 2. Проверка оптимальности полученного плана перевозок. Введем специальные показатели и, для каждой строки матрицы перевозок (каждого поставщика), где , и показатели Vj для каждого столбца (каждого потребителя), где . Эти показатели называются потенциалами поставщиков и потребителей, их удобно интерпретировать как цены продукта в соответствующих пунктах поставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i; j) выполнялось равенство (3.19). Совокупность уравнений вида (3.19), составленных для всех заполненных клеток (всех базисных неизвестных), образует систему т + п — 1 линейных уравнений с т + п неизвестными u_i, и v_y. Эта система всегда совместна, причем значение одного из неизвестных можно задавать произвольно (например, и_; = 0), тогда значения остальных неизвестных находятся из системы однозначно.

Рассмотрим процесс нахождения потенциалов для базисного начального распределения по методу северо-западного угла, представленного в табл. 3.6. Задав и, = 0 и используя формулу (3.19) для заполненных клеток (1; 1) и (1; 2), находим V = 4 и v₂ = 5. Зная v₂, по заполненной клетке (2; 2) находим и_Л = 2, а зная v₂, по заполненной клетке (2;

2) находим ?'₃ = 8. Зная у₃, по заполненной клетке (3; 3) находим щ = 1, а затем по заполненной клетке (3; 4) находим.

= 5. Результаты представлены в табл. 3.8, где потенциалы поставщиков приведены в последнем столбце, а потенциалы потребителей — в последней строке.

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

Таблица 3.8

Аналогичные результаты для начального распределения по методу наименьших стоимостей, приведенного в табл. 3.7, представлены в табл. 3.9.

Таблица 3.9

Чтобы оценить оптимальность распределения, для всех клеток (i, j) матрицы перевозок определяются их оценки, которые обозначим через ?_ij, по формуле.

(3.20).

Используя ранее принятую интерпретацию, выражение (Uj+Cjj) можно трактовать как сумму цены продукта у поставщика и стоимости перевозки; эта сумма путем вычитания сравнивается с ценой продукта у соответствующего потребителя V:. Очевидно, оценки заполненных клеток равны нулю (цена потребителя покрывает цену поставщика и стоимость перевозок). Таким образом, об оптимальности распределения можно судить, но величинам оценок свободных клеток. Если оценка некоторой свободной клетки отрицательна, это можно интерпретировать так: цена, предлагаемая соответствующим потребителем, больше суммы цены поставщика и стоимости перевозки, т. е. если бы эта клетка была занята, то можно было бы получить дополнительный экономический эффект. Следовательно, условием оптимальности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок.

Оценки клеток по формуле (3.20) удобно представить в виде матрицы оценок. Для ранее рассматриваемого распределения, полученного методом северо-западного угла (см. табл. 3.8), матрица оценок клеток имеет вид.

(3.21).

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

Для распределения, полученного методом наименьших стоимостей (см. табл. 3.9), матрица оценок клеток имеет вид.

Так как все оценки неотрицательны, то не имеется возможности улучшить данный план перевозок, т. е. он оптимален (суммарные затраты на перевозку по этому плану равны 590). Кроме того, следует отметить, что в данном случае оценки всех свободных клеток строго больше нуля, т. е. любой другой план, предусматривающий занятие хотя бы одной из этих клеток, будет менее оптимален. Это говорит о том, что найденный оптимальный план является единственным. Наличие нулевых оценок свободных клеток в оптимальном плане перевозок, наоборот, свидетельствует о неединственности оптимального плана.

Этап 3. Улучшение неоптимального плана перевозок (циклы перераспределения). Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с отрицательной оценкой; если таких клеток несколько, то обычно (но необязательно) выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой. Например, для распределения, представленного в табл. 3.8, такой клеткой может служить клетка (1; 3) (см. матрицу оценок (3.21)).

Для выбранной клетки строится замкнутая линия (контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть только горизонтальными и вертикальными. Вершиной контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой угол (нельзя рассматривать как вершины клетки, где горизонтальные и вертикальные отрезки контура пересекаются). Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура расставляются поочередно знаки «+» и «-», начиная со знака «+» в выбранной свободной клетке. Пример простого контура показан пунктиром в табл. 3.8, хотя вид контура может быть самым разнообразным (см., например, контур в табл. 3.11).

Величина перераспределяемой поставки определяется как наименьшая из величин поставок в вершинах контура со знаком «-», и на эту величину увеличиваются поставки в вершинах со знаком «+» и уменьшаются поставки в вершинах со знаком «-». Это правило гарантирует, что в вершинах контура не появится отрицательных поставок, начальная выбранная клетка окажется занятой, в то время как одна из занятых клеток при этом обязательно освободится. Если величина перераспределяемой поставки равна поставкам не в одной, а в нескольких вершинах контура со знаком «-» (это как раз имеет место в контуре перераспределения в табл. 3.8), то освобождается только одна клетка, обычно с наибольшей стоимостью перевозки, а все другие такие клетки остаются занятыми с нулевой поставкой.

Результат указанных операций для представленного в табл. 3.8 распределения поставок показан в табл. 3.10. Суммарные затраты на перевозки по этому плану составляют:

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

Таблица 3.10

Транспортные задачи, в базисном плане перевозок которых имеют место занятые клетки с нулевой поставкой (или в первоначальном распределении, или в процессе итераций), называются вырожденными; пример такой задачи представлен в табл. 3.10. В случае вырожденной транспортной задачи существует опасность зацикливания, т. е. бесконечного повторения итераций (бесконечного перебора одних и тех же базисных комбинаций занятых клеток). Как правило, в практических задачах транспортного типа зацикливание не встречается, тем не менее следует знать, что существуют специальные правила, позволяющие выйти из цикла, если зацикливание все же произойдет. При отсутствии вырождения метод потенциалов конечен и приводит к оптимальному плану перевозок за конечное число шагов.

Пример 3.4. Решим методом потенциалов закрытую транспортную задачу, заданную в табл. 3.11, в которую уже внесено некоторое допустимое базисное распределение. Суммарные транспортные расходы составляют при этом плане перевозок.

Потенциалы по формуле (3.19) находим следующим образом: задавая u_{ = 0, находим по клетке (1; 1) = 3, по клетке (1; 2) = 2, а по клетке (1; 4) = 1; затем по клетке (2; 1) находим и₂ = 1 и по клетке (2; 3) v₃ = 2; наконец, по клетке (3; 3) находим u₃ = -2.

Таблица 3.11

Матрица оценок клеток для этого плана рассчитывается по формуле (3.21):

Наличие отрицательных оценок свидетельствует о том, что план неоптимален. Построим контур перераспределения, например, для клетки (3; 2) в табл. 3.11 он показан пунктиром и его вершинам присвоены соответствующие знаки.

Наименьшая поставка в вершине контура со знаком «-» равна 20, поэтому проведем перераспределение поставок, уменьшив поставки в клетках со знаком «-» на 20 и увеличив поставки в клетках со знаком «+» также на 20; при этом клетка (3; 2) заполняется, а клетка (3; 3) освобождается. Новый план представлен в табл. 3.12, соответствующие значения потенциалов показаны в последних столбце и строке.

Таблица 3.12

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

Наличие нулевой оценки незанятой клетки (3;1) говорит о том, что оптимальный план не является единственным. Можно отметить также, что, применяя для начального распределения в этой транспортной задаче модификацию двойного предпочтения метода наименьших стоимостей, мы сразу же получили бы оптимальное распределение, представленное в табл. 3.12.

Пример 3.5. Рассмотрим пример решения открытой транспортной задачи, исходные данные которой представлены в табл. 3.13.

Таблица 3.13

Проверим выполнение условия баланса (3.18):

Условие баланса не выполняется, следовательно, задача действительно является открытой. Сформулируем экономико-математическую модель этой задачи.

Пусть Х_y - объемы перевозок от г-го поставщика j-му потребителю. Целевая функция задачи будет иметь вид.

а ограничения выглядят следующим образом: по поставщикам:

по потребителям:

прямые ограничения:

Сведем эту задачу к закрытой, введя фиктивного потребителя с мощностью 280 — 270 = 10; стоимости перевозок единицы груза в соответствующих (фиктивных) клетках принимаются равными нулю, и эти клетки при составлении начального распределения перевозок заполняются в самую последнюю очередь. Начальный план перевозок, но методу наименьших стоимостей представлен в табл. 3.14.

Матрица оценок клеток этого плана в соответствии с методом потенциалов имеет вид.

Таблица 3.14

Анализ элементов матрицы оценок клеток свидетельствует о том, что план перевозок в табл. 3.14 является оптимальным и единственным. Стоимость перевозок по этому плану составит 550, при этом мощности потребителей будут удовлетворены полностью, а у третьего поставщика останутся невывезенными 10 единиц груза.