korobov

151

Глава 4. ТРАНСПОРТНЫЕ АЛГОРИТМЫ. ИХ СУЩНОСТЬ В РЕШЕНИИ ЗАДАЧ

В 1.3 рассмотрена экономико-математическая постановка транспортной задачи, которая заключается в отыскании значений xij, минимизирующих целевую функцию

Напомним, что условие (4.2) означает, что из i-го пункта производства надо вывезти во все пункты потребления количество материалов ai, предназначенное к реализации, а условие (4.3) — что в каждый пункт потребления j должно быть завезено (поставлено) заданное количество материалов, равное спросу на них в этом пункте. При этом суммарные затраты на поставку всех материалов, выраженные в целевой функции (4.1), должны быть минимальными.

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

Самым простым (однако менее рациональным) методом в этой группе является распределительный метод. Между тем при решении транспортной задачи посредством этого метода наиболее показательно прослеживается экономическая сущность принципа последовательного улучшения плана и вообще отыскания оптимального решения.

Для практического применения наиболее приемлемыми следует считать: метод потенциалов, модифицированный распределительный и метод дифференциальных рент. Следует заметить, что метод потенциалов и модифицированный распределительный метод чрезвычайно похожи друг на друга.

В этой главе будут рассмотрены распределительный метод, метод потенциалов и метод дифференциальных рент.

153

Первая итерация заключается в определении исходного опорного плана и проверке его на оптимальность.

Определение исходного опорного плана. Первый опорный план может быть найден посредством различных способов: по правилу северо-западного угла, приоритету ближайших пунктов, способу минимального элемента С=(cij), способу Фогеля и, наконец, по способу Лебедева-Тихомирова. Рассмотрим некоторые из них.

Самый простой (и в то же время самый плохой) способ называется правилом северо-западного угла. Это формальный способ (порядок) распределения поставок между потребителями, приводящий обычно к плану поставок, весьма далекому от оптимального. Рассмотрим его на нашем примере. Для этого исходные условия задачи представим в рабочей табл.4.2.

Т а б л. 4.2

В соответствии c примером (табл.4.2) первый опорный план можно определить следующим образом.

Согласно правилу северо-западного угла сначала находим значение x11 (т.е. в первую очередь заполняем поставкой клетку А1В1, расположенную в северо-западном углу) из условия

x11=min(a1,b1).

Если a1≤ b1, то x11= a1 и все остальные x1j=0; если же a1≥ b1, то x11= b1 и остальные xi1=0. Для данного примера x11=min (150,200)=150, x12=0, x13=0, x14=0. Поставку x11=150

записываем в табл. 4.2 в клетку А1В1.

После этого определяем значение x21 по аналогичному правилу: x21=min (250,200150)=50. Тогда x31=0 и x41=0.

Иными словами, потребности потребителя В1 b1=200 удовлетворяются частично за счет поставщика А1-150 тыс.м3 и частично поставщика А2 – 50 тыс.м3, поскольку мощность первого поставщика ограничена и оказалась меньше спроса потребителя В1.

Далее определяется значение x22 для заполнения клетки А2В2. У поставщика А2 нераспределенными остались 200 тыс.м3, потребителю В2 необходимы также 200 тыс.м3, следовательно x22=200, x23=0 и x24=0, x32=0 и x42=0.

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

154

верхней клетки и далее уступами по диагонали к нижней правой, в нашем примере с А1В1

к А4В4.

В результате такого распределения получен опорный план (табл.4.2), удовлетворяющий условиям (4.2, 4.3, 4.4), однако очень далекий, как будет видно дальше, от оптимального.

Значение целевой функции (4.1) для этого опорного плана равно F=5 150+3 50+4 200+6 230+3 20+6 200=4340.

Таким образом, если бы осуществить поставки пиловочника по этому опорному плану, общие затраты на поставку составили бы 4340 тыс.руб.

Запомним значение целевой функции, характеризующее опорный план, найденный по правилу северо-западного угла. Сам же план оставим, и отыщем иное исходное решение задачи, но на этот раз посредством лучшего способа, называемого способом минимального элемента (или наименьшего элемента в матрице С(cij)).

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

Однако использование этого способа требует большого внимания. Поэтому рассмотрим его детально на том же примере. Сущность его заключается в следующем.

Вматрице стоимостей поставки С=(cij) отыскивается клетка, содержащая наименьший элемент cij, затем в эту клетку записывается поставка xij=min(ai,bj). Если матрица содержит несколько одинаковых значений cij, тогда выбирают любое одно (безразлично какое) и заполняют эту клетку поставкой.

После занесения поставки xij в клетку с минимальным cij вычеркивают (мысленно) столбец или строку (или то и другое). Если ai>bj, вычеркивается столбец. При ai<bj, вычеркивают строку и при ai=bj вычеркивают и столбец и строку.

Далее процесс (шаги) повторяется до тех пор, пока не будут распределены все

поставки.

Если матрица большая, и в уме трудно держать разбитые в процессе

распределения на части значения ai и bj, в конце каждого шага вычисляют остаточные (нераспределенные) мощности поставщиков и неудовлетворенные емкости потребителей.

Втабл.4.3 запишем исходные данные рассматриваемого примера и определим исходный опорный план по способу минимального элемента матрицы С(cij).

Та б л. 4.3

155

В нашем примере в матрице стоимостей поставки С=(cij) наименьший элемент c41=1 находится в клетке А4В1. Следовательно, в эту клетку следует занести первую поставку х41=min(a4,b1)=min(220,200)=200. Спрос потребителя В1 оказался удовлетворенным полностью, поэтому столбец В1 "вычеркиваем" (исключаем из дальнейшего процесса распределения).

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

Дальше процесс повторяется в том же порядке. В оставшейся матрице стоимостей поставки два одинаковых наименьших значения c42=2 и c13=2 находятся соответственно в клетках А2В2 и А1В3. Выбираем любую из этих двух клеток, например А4В2, и заполняем ее поставкой х42=20, равной нераспределенной к этому шагу части мощности поставщика А4. Вычеркиваем строку А4, поскольку мощность этого поставщика теперь оказалась распределенной полностью.

На следующем, третьем, шаге заполняем клетку А1В3 поставкой х13= min(a1,b3)=min(150,250)=150 и т.д., на 4-м шаге – клетку А2В2 поставкой х22= min(a2,b2- 20)=min(250,200-20)=180, затем на 5-м шаге в клетку А2В4 записываем поставку х24= min(a2-180,b4)=min(250-180,200)=70. Наконец, остались незаполненными А3В3 и А3В4 – в них записываются поставки х33=100 и х34=130.

Последовательность заполнения клеток переменными xij мы указали цифрами помещенными в нижнем правом углу каждой клетки.

В результате такого распределения получен исходный опорный план, удовлетворяющий всем условиям модели транспортной задачи. Значение целевой функции (4.1) для этого опорного плана равно

F=2 150+4 180+4 70+6 100+5 130+1 200+2 20=2790. (4.7)

Таким образом, если бы осуществить поставки пиловочника по этому опорному плану, общие затраты на поставку составили бы 2790 тыс.руб.

Читателю нетрудно убедиться в том, что посредством способа минимального элемента С(cij) получен значительно лучший исходный опорный план, чем по правилу северо-западного угла. Разница в значениях целевых функций составила 1550 тыс.руб. (4340-2790).

Исходный опорный план, вычисленный посредством способа минимального элемента, представим в табл.4.4. Этот план является допустимым решением заданной транспортной задачи. В этом нетрудно убедиться, подставив значения переменных хij в ограничительные условия (4.2), (4.3) задачи. Так, например,

х21+ х22+ х23+ х24=а2, 0+180+0+70=250=250

х12+ х22+ х32+ х42=b2, 0+180+0+20=200=200 и т.д.

положительных поставок хij>0 равно рангу r=m+n-1 системы ограничительных уравнений (4.2), (4.3). В данном примере r=4+4-1=7 и число базисных клеток – клеток, заполненных числами хij>0, также равно 7.

Следующий этап решения транспортной задачи заключается в проверке

полученного исходного опорного плана на оптимальность.

Проверка опорного плана на оптимальность. Чтобы установить является ли опорный план оптимальным, надо проверить, как повлияет на величину целевой функции (4.7) любое возможное перераспределение поставок, удовлетворяющее ограничительным условиям (4.2), (4.3), (4.4).

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

Проверим возможность уменьшения суммарных затрат на поставку продукции. С этой целью для каждой свободной от поставки клетки определяется величина ij, характеризующая изменение суммарных затрат на поставку (в расчете на единицу перераспределяемой продукции), при условии включения в план единичной поставки хij=1 от поставщика Аi к потребителю Вj. При этом должно быть произведено такое изменение остальных поставок, чтобы получившаяся совокупность поставок не нарушала баланса спроса и поставок транспортной задачи, т.е. удовлетворяла ограничительным условиям (4.2), (4.3), (4.4).

Величину ij в дальнейшем будем называть оценкой свободной клетки (некоторые авторы называют характеристикой).

В нашем примере, в исходном решении задачи (см.табл.4.4) клетки А1В1, А1В2, А1В1, А2В1, А2В3, А3В1, А3В2, А4В3 и А4В4 оказались свободными от поставок.

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

контуром и т.д.).

Рассмотрим сначала наиболее простые формы циклов (цепей) приминительно к нашему примеру.

Вычислим оценку единичной поставки х21=1.

157

При включении в план поставки х21=1 для восстановления баланса спроса и предложений необходимо уменьшить поставки х22 и х41 на единицу и увеличить поставку х42 также на единицу. Представим фрагмент матрицы, относящейся только к этому перераспределению (рис.4.1).

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

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

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

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

Для каждой свободной клетки в плане с числом базисных клеток m+n-1 всегда может быть составлен замкнутый цикл пересчета, при этом только один.

-1 +2

Рис.4.3

158

Наконец, форма цикла может быть различной. На рис. 4.2 представленный цикл пересчета для клетки A2B1имеет форму четырехугольника. В других случиях цикл пересчета может быть в виде многоугольника различной конфигурации.

Вершины, в которых поставки при перераспределении увеличиваются (на рис. 4.1

– вершины A2B1 и A4B2), отмечаются плюсом и называются положительными вершинами И, наоборот, вершины, в которых поставки при перераспределении уменьшаются ( на рис. 4.1 - A2B2 и A4B1) отмечаются минусом и называются отрицательными вершинами. В цикле знаки по вершинам расставляют начиная с вершины, лежащей в свободной клетке, для которой определяется ij. В нее записывают знак плюс, затем знаки по вершинам чередуются: минус, плюс , минус, плюс и т. д., независимо от того, расставляют ли их по часовой стрелке или в обратном направлении. Таким образом, в цикле всегда насчитывается одинаковое число положительных и отрицательных вершин.

Поскольку конечная цель составления циклов пересчета заключается в определении оценок ij свободных клеток, условимся по вершинам цикла пересчета записывать соответствующие клеткам показатели критерия оптимальности сij с присвоенным вершине знаком. И еще одна условность. Вершины, лежащие в базисных клетках, будем отмечать квадратами, а вершину, лежащую в свободной клетке, без квадрата. Тогда для клетки A2B1 цикл пересчета можно представить в форме четырехугольника, показанного на рис.4.3.

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

Так, для свободной клетки A2B1 оценка 21 будет равна: 21=+3-4+2-1=0

Поясним, что записав поставку, равную 1м3, в клетку A2B1 (см.рис.4.1), мы увеличили значение целевой функции на 3 (с21=3). Уменьшив на 1 м3 поставку A2B2, мы тем самым уменьшили значение целевой функции на 4 (с22=4); увеличив поставку в клетке A4B2, мы увеличили целевую функцию на 2, и, наконец, уменьшив поставку в клетке A4B1, мы уменьшили целевую функцию на 1. Те же числа фигурируют в вершинах цикла на рис. 4.3.

Поскольку оценка свободной клетки A2B1 оказалась равной нулю, занятие ее поставкой не отразится на величине целевой функции (4.7). Далее построим циклы пересчета (рис.4.4) и по ним вычислим значение оценок ij для всех остальных свободных клеток табл.4.4.

Проведенные расчеты оценок свободных клеток показывают, что исходный опорный план, представленный в табл. 4.4, является неоптимальным решением задачи, так как оценка свободной клетки A3B1 оказалась равной – 2, что свидетельствует о возможности снижения значения целевой функции (4.7) на 2 руб. в расчете на каждый перераспределенный кубометр продукции.

Следующий этап решения транспортной задачи заключается в улучшении опорного

плана.

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

159

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

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

Для того, чтобы установить величину поставки, подлежащей записи в клетку A3B1, представим на рис. 4.5 цикл пересчета для этой клетки. В отличие от рис. 4.4 в данном случае в квадратах, являющихся вершинами цикла, будем записывать не показатели сij, а величины поставок хij из соответствующих базисных клеток. При этом знаки в вершинах сохраним без изменения.

160

Рис.4.4