Транспортная задача

В пунктах Аь Аг, ..., А_т производится некоторый продукт, причем объем производства в пункте А; равен а_х единиц продукта. Этот продукт потребляется в пунктах В_ь В2,..., В_п и объем потребления в пункте Bj составляет bj единиц. Предположим, что суммарные объемы производства и потребления совпадают, то есть

Продукт может поставляться из любого пункта производства в любой пункт потребления, но транспортные издержки при этом различны. Считаем заданными все с у — издержки на поставку единицы продукта из i-ro пункта производства в j-й пункт потребления. Задача формулируется следующим образом: составить такой план перевозок, чтобы все потребности были удовлетворены, а суммарные транспортные издержки были минимальны.

Пусть Ху — количество продукта, поставляемого из пункта А} в пункт Bj. Тогда математическая модель задачи состоит в следующем:

Найтито есть план перевозок

при условиях:

Это условие означает, что все, что произведено в каждом пункте, из него вывозится.

В каждый пункт потребления ввозится столько, сколько требуется.

Всего m + п ограничений-равенств. Если эти условия выполнены, то обеспечено и равенство суммарного объема производства и потребления, то есть

Это означает, что при

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

Формально необходимы и условия неотрицательности всех переменных Ху > 0, которые очевидны по смыслу задачи, но автоматически могут и не выполняться.

Целевая функция представляет собой двойную сумму

Полученная задача линейного программирования обладает некоторыми особенностями. Так, если ограничения записать в матричном виде, то в каждом столбце матрицы только два элемента равны единице, а остальные нули. Именно эта особая структура матрицы позволила создать более эффективные алгоритмы решения задачи, чем алгоритм симплекс-метода [4, 8, 23].

Если выполнено условие

то одно (любое) из уравнений можно отбросить, так как оно является следствием остальных. Поэтому при числе неизвестных mn имеем m + п — 1 ограничение равенство и, следовательно, базисных переменных m + п — 1, а остальные переменные, число которых k = mn — (m + п — 1) = (m — l)(n — 1) равны нулю. Поскольку решением задачи является вершина допустимой области, то ровно к элементов плана перевозок Ху = 0.

В силу особенностей транспортной задачи существует простой способ нахождения допустимой вершины (начальное приближение) и вообще все операции поиска оптимального решения производятся непосредственно над таблицей, в которой в определенном порядке записаны условия задачи, а именно: перечень пунктов производства и назначения, заявки bj и запасы а,, а также стоимости перевозок Су. Покажем два способа построения начального приближения для следующей задачи: m = 3, п = 4, запасы ai = 2, аг = 5, аз = 7, заявки bi = 3, b2 = 4, Ьз = 5, b4 = 2. Суммы заявок и запасов равны 14. В первом способе стоимости перевозок не используются, и мы их пока задавать не будем. Метод построения начального приближения (вершины ОДР) носит название северо-западного угла и состоит в заполнении соответствующей таблицы (табл. 3.1).

Таблица 3.1

Заполнение начинается с клетки А] Вj. В нее записывается меньшее из чисел aj и fc>i, то есть хц = min(ai, bi). Дальнейшие действия зависят от соотношения а и Ъ.

• 1. Если aj > Ьь то Хц = Ьц и заявка первого потребителя полностью выполнена и она заменяется нулем, а вместо а осталось а-Ъ. Это означает, что все остальные клетки первого столбца должны оставаться нулями и нужно перейти к следующему (второму) потребителю, то есть сдвинуться по строке в клетку А]В₂. При этом Xi2 = min(ai — bj,b₂).
• 2. Если ai < Ьц то хц = aj и запасы первого поставщика исчерпаны (aj обнуляется), но заявка потребителя В удовлетворена не полностью (осталось b)-ai). Поэтому переходим по столбцу в клетку A₂Bj и записываем в нее

3. Если ai = Ьц то и первая строка и первый столбец «закрыты» и переходим в клетку А₂В₂.

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

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

Зададим матрицу

и занесем соответствующие числа в клетки транспортной таблицы в скобках запишем в последней строке соответствующие заявки (3, 4, 5, 2), а в последнем столбце запасы (2, 5, 7) (табл. 3.2).

Таблица 3.2

Процесс начинаем с клетки А3В2 и удовлетворяем полностью заявку второго потребителя за счет третьего поставщика Х32 = 4 (у третьего поставщика остается 3). Переходим в клетку А)В], запас aj = 2 будет исчерпан, и для полного удовлетворения заявки не хватит 1. Переходим в клетку A3В3, используем остаток запаса третьего поставщика, и нужно еще 2. Следующая минимальная стоимость (3) соответствует клеткам А1В2 и А3В4. Однако ее использовать нельзя, так как уже не осталось запасов у соответствующих поставщиков (первого и третьего). Можно использовать стоимость (5), то есть перейти в клетку А2В1. Первому потребителю нужно только 1, его потребность удовлетворяется полностью, и у второго поставщика остается 4. Затем третий потребитель получает 2 от второго поставщика (стоимость 7), и, наконец, четвертый потребитель получает 2 от второго же поставщика (ровно столько у него осталось).

Сравнивая по целевой функции два полученных начальных приближения, убеждаемся, что для каждого из них целевая функция равна 47, хотя обычно второй метод дает лучшее начальное приближение, так как приоритет отдается поставкам с минимальными стоимостями. Однако если вместо С24 = 8 задать большее число и ничего более не меняя повторить построение начального приближения, то в нашем примере по методу минимальных стоимостей получим начальное приближение, для которого целевая функция больше, чем для начального приближения, полученного по методу северо-западного угла (табл. 3.1).

Следующий этап расчетов состоит в проверке построенного начального приближения на оптимальность. Это можно сделать с помощью метода потенциалов. Следуя этому методу, введем так называемые псевдостоимости dij = а; + (3j. Если Ху # 0 (базисные клетки), то dy = Су, то есть псевдостоимость равна фактической. Если же Ху = 0 (свободные клетки), то соответствующая псевдостоимость может быть меньше фактической и даже стать отрицательной dy < су. Если ни одна псевдостоимость не превышает фактическую, то решение оптимально. Входящие в псевдостоимости величины oq и (3j называются потенциалами. Найдем потенциалы для начального приближения, полученного по методу северо-западного угла. Только пять величин отличны от нуля: хц, Х21, Х22, Х33, Х34. Им соответствуют заданные стоимости Си = 1, С21 = 5, С22 ⁼ 6, С33 = 2, С34 = 3. Получаем систему из пяти уравнений a + Р] = 1, «2 + Pi⁼5, 0С2 + р2⁼6, аз + Рз=2, аз + Р4 = 3 с семью неизвестными. Эта система имеет бесконечное число решений. Примем ai = 0 и аз = 0. Тогда последовательно получим Pi = 1, a2 =4, Р2 = 2, (З3 = 2, Р4 = 3. Через найденные потенциалы вычислим псевдостоимости, соответствующие свободным клеткам.

Сравнивая полученные псевдостоимости с фактическими, видим, что все они, кроме 632 ⁼ аз + Р2 = 2, не превосходят фактических, но бз2 > С32, так как С32 = 1. Отсюда следует, что рассматриваемое решение (план перевозок Ху) можно попытаться улучшить.

Для этого составим таблицу по аналогии с таблицей 3.2, но вместо Aj и Bj будут соответственно aj и Pj и в каждую клетку запишем объемы перевозок Ху и псевдостоимости в сравнении со стоимостями.

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

Таблица 3.3

Эта задача решается с помощью метода циклических перестановок. По этому методу сначала определяется маршрут циклической

перестановки, то есть цикл пересчета. Клетка, с которой начинается цикл пересчета, выбирается из тех, которым соответствует недопустимая псевдостоимость. Для каждой из таких клеток нужно определить превышение псевдостоимости над стоимостью (невязку) и взять ту клетку, в которой невязка максимальна. В нашем примере только одна «плохая» клетка, это А3В2, с нее и может начаться цикл пересчета, который строится по следующим правилам: цикл пересчета — это замкнутая ломаная линия, начинающаяся в свободной клетке, остальные вершины совпадают с базисными клетками, звенья располагаются вдоль строк и столбцов таблицы. В каждой вершине встречаются только два звена (одно по строке, другое по столбцу), никакие три вершины, встречающиеся подряд при обходе, не лежат на одной прямой. Циклом может быть самопересекающаяся линия, но точки самопересечения могут быть только в свободных клетках. Свободной клетке присваивается знак «+», другим вершинам чередующиеся по ходу цикла знаки «—», «+», «—» и т. д. Поскольку число вершин со знаком «+» равно числу вершин со знаком «—», то баланс не нарушится, если в вершинах со знаком «—» уменьшить объем перевозок на некоторое число, а в вершинах со знаком «+» увеличить на то же число. Так как объем перевозок не может быть отрицательным, то это число определяется как наименьшее из чисел в «отрицательных» клетках. В нашей задаче при полученных потенциалах мы определили начало возможного цикла, но построить его с соблюдением изложенных правил из клетки А3В2 невозможно.

Возьмем другие потенциалы, соответствующие тому же начальному приближению. Примем oq = 1 и аз = 0 и последовательно получим Pi = О, СС2 = 5, Р2 = 1, Рз = 2, Р4 = 3. Через найденные потенциалы вычислим псевдостоимости, соответствующие свободным клеткам.

Сравнивая полученные псевдостоимости с фактическими, видим, что все они не превосходят фактических (табл. 3.4.), следовательно, план, полученный по методу северо-западного угла (таб. 3.1), оптимален.

Таблица 3.4

Поскольку при первоначально выбранных потенциалах мы получали недопустимую псевдостоимость и надеялись улучшить план перевозок, что оказалось невозможно, остается сделать вывод: получение недопустимых (т. е. превышающих фактические) псевдостоимостей не означает, что план можно улучшить. Этот пример и сделанный вывод опровергают распространенное умозаключение: если набор потенциалов, полученный из условия равенства псевдостоимостей и фактических стоимостей для базисных клеток (djj = Су для Ху # 0) не удовлетворяет системе неравенств (dy < Су для Ху = 0), то проверяемый план не оптимален. Вместо «не оптимален» здесь должны быть слова «возможно не оптимален».

Если проанализировать план, полученный по методу минимальных стоимостей (табл. 3.2), то при потенциалах cq = 0, 0С2 = 4, аз = —2, Pi = 1, Р2 = 2, Рз = 3, Р4 = 4 убеждаемся в том, что он оптимален (табл. 3.5).

Таблица 3.5

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

В табл. 3.3 можно построить только один цикл (из клетки А]В₂), а в табл. 3.5 уже три (из клеток АВ3 А₂В₂ и А3В4), но ни один из них не приводит к уменьшению целевой функции. Смысл метода потенциалов в том, что если удается построить цикл начиная с любой свободной клетки, которой соответствует недопустимая псевдостоимость, то такой цикл пересчета дает уменьшение целевой функции, что избавляет от «слепого» поиска «хорошего» цикла.

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

Наибольшая невязка соответствует клетке AjB₂, отмеченной знаком «+», цикл пересчета отмечен пунктиром.

Таблица 3.6

Число пересчета (наименьшее из отмеченных знаком «—») равно 2. Пересчет состоит в том, что перевозки в клетках, отмеченных знаком «—», уменьшаются на 2, а в клетках, отмеченных знаком «+», увеличиваются на 2. Сокращая перевозки, выигрываем 2x9 + 2x2 = 22, а увеличивая перевозки, проигрываем 2x1 + + 2 х 1 = 4. В целом выигрываем 18. После пересчета в клетке А]В] будет нуль. Это означает, что она (точнее, переменная хц) будет свободной, а в бывшей свободной клетке А)В₂ будет 2, то есть она станет базисной. Это означает, что для нового плана перевозок при поиске потенциалов вместо уравнения ai + (3₂ = 1 будет неравенство ai + р₂ < 1, а вместо неравенства a] + Pi < 1 будет уравнение оц + Pi = 1.

Для новой таблицы можно получить потенциалы oci = О, 0С2 = 1, аз = 0, (3i = О, (З2 = 1, Рз = 7, Р4 = 8, дающие недопустимые псевдостоимости, но построить цикл пересчета не удается. Для этой же таблицы можно взять другие потенциалы aj = 0, а2 = 1, аз = 5, Pi ⁼ О, Р2 = 1, Рз = 2, Р4 = 3 и убедиться, что недопустимых псевдостоимостей нет и, следовательно, получено оптимальное решение, показанное в таблице 3.7.

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

Таблица 3.7

Характерно, что в транспортной задаче при целочисленности всех щ и bj автоматически получаются целые значения Ху.

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

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