korobov

161

-130 +130

180 70

+130

130

-130

200 20

-130 +130

Рис. 4.5 В данном цикле пересчета (рис.4.5) три поставки х22=180, х34=130 и х41=200

отмечены знаком минус.

Для получения нового, лучшего, опорного плана, в клетку A3B1 следует записать наименьшую из поставок, отмеченных знаком минус в цикле пересчета (в данном случае поставку х34, равную 130). Далее по вершинам цикла эту поставку (130) следует прибавить или вычесть, в зависимости от знака в вершине (так, как это показано на рис.4.5). Поставки, не вошедшие в цикл пересчета (в данном случае х13=150 и х33=100), переносятся в новый план без изменения.

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

Целевая функция (4.1), соответствующая этому новому опорному плану, равна F2=2 150+4 50+4 200+2 130+6 100+1 70+2 150=2530 (4.9)

Таким образом, в связи с переходом к новому плану произошло уменьшение целевой функции (4.7) на 260 тыс. руб. (2790— 2530).

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

занятия свободной клетки поставкой хij' =1. И действительно, эти 260 тыс. руб. равны произведению оценки клетки A3B1 (-2) на величину записанной в эту клетку поставки

F2= 2790+(—2) 130 =2530.

Итак, план поставок в табл. 4.5 является допустимым решением задачи; причем он лучше предыдущего.

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

Доведение опорного плана до оптимального. На следующей итерации вновь надо составить циклы пересчета (цепи) и вычислить оценки ij, каждой свободной клетки в плане поставок табл. 4.5.

Опорный план в табл. 4.5 является неоптимальным, поскольку оценки клеток А2В3 и А4В3 (рис. 4.6) оказались отрицательными, при этом одинаковыми по величине (-2).

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

С этой целью вновь построим циклы пересчета для этих двух свободных клеток, с записью поставок xij по вершинам (рис.4.7).

Это необходимо еще и потому, что один из них потребуется для перестроения

плана.

Из рис.4.7 видно, что при занятии поставкой свободной клетки А2В3 в нее следует записать поставку х23, равную 50 тыс. м3, и это приведет к общему снижению целевой

функции ( ij xij' ) в 100 тыс. руб. Если же за очередной переход к лучшему плану занять

поставкой клетку А4В3, а не А2В3, то ее следует заполнить поставкой x43 ==70 тыс. м3. Тогда общее снижение целевой функции (4.9) будет равно —140 тыс. руб. (-2 70).

Таким образом, мы установили, что в данном случае при переходе к лучшему плану следует занять поставкой x43=70 клетку А4В3.. При этом поставки x41 и x33 должны быть уменьшены на 70, a x31—увеличена на 70, в соответствии со знаками по вершинам цикла (рис. 4.7).

163

Поставки, не вошедшие в цикл пересчета клетки А4В3 (x13 = 150, x22. = 50, x24 = 200

иx42 =150), перейдут в новый план табл. 4.6 без изменения.

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

164

Рис.4.6

165

Целевая функция (4.1), соответствующая этому плану, равна

F3==2 150+4 50+4 200+2 200+6 30+2 150+3 70==2390 (4.11)

или, по формуле (4 .10),

F3= 2530 +(-2) 70 =2390.

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

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

Оценки свободных клеток по плану поставок табл. 4.6 будут равны:

166

23=5-3+2-4=0;

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

F= 2390= min.

Таким образом, последний опорный план табл. 4.6 является оптимальным.

Решение задачи практически закончено. Однако следует обратить внимание читателя еще на один

существенный момент.

В оптимальном решении задачи свободные клетки А2В3, А3В2 и А3В4 имеют оценку равную нулю ( 23=0, 32=0 и 34=0). Это является свидетельством того, что среди бесчисленного множества решений этой задачи существуют еще решения, являющиеся также оптимальными, поскольку значение целевой функции остается одинаковым— минимальным. Их принято называть альтернативными.

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

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

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

Т а б л .4.7

Значение целевой функции (4.1), соответствующей этому плану, равно

Значения целевых функций (4.11) и (4.12) равны между собой. Иначе и не могло быть, если решение правильно в том и другом случае.

Другие альтернативные планы рекомендуется читателю найти самостоятельно. Это послужит

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

167

4.2. Метод потенциалов

Основной алгоритм распределительного метода, рассмотренный нами в 4.1 является далеко не лучшим методом решения транспортных задач, так как на каждой итерации для проверки опорного плана на оптимальность приходилось строить [тп— (т+п—1)] циклов пересчета, что при больших размерах матрицы оказывается очень громоздким и трудоемким делом. Так, для расчетов по матрице 10х10 на каждой итерации надо строить 81 цикл, а по матрице 20x20—361 цикл.

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

В 1940 г. советским ученым Л. В. Канторовичем был разработан метод решения транспортной задачи, и в первой публикации (1942 г.) содержались основные идеи метода. Впоследствии (в 1949 г.) в совместной статье Л. В. Канторовичем и.М. К. Гаву-риным был изложен сам метод (в сетевой постановке), названный методом потенциалов.

Позднее (в 1951 г.) американским ученым Дж. Б. Данцигом был разработан аналогичный метод, получивший название модифицированного распределительного метода, который в иностранной и некоторой советской литературе сокращенно именуют методом МОДИ.

Поскольку разница между этими способами чрезвычайно незначительна, в дальнейшем не будем их разграничивать и станем именовать общим названием—

методом потенциалов.

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

потенциалами.

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

Для этого составим условие двойственной задачи по отношению прямой транспортной задачи (4.1)—(4.4), в которой требовалось отыскать не отрицательные значения переменных xij, минимизирующие целевую функцию

j=1

168

i=1

Сцелью составления двойственной задачи переменные xij в условии (4.14) заменим

на u1, u2,…, ui,…,um, а переменные условия (4.15) на v1, v2,…, vj,…,v n.

Поскольку каждая переменная xij входит в условия (4.14, 4.15) и целевую функцию (4.13) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа vi (при i= 1, 2, ..., m) и vj (при j=1, 2, ..., п), обращающие в максимум целевую функцию

В системе условий (4.17) будет тxп неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть

Эти условия (4.18) являются необходимыми и достаточными признаками

оптимальности плана транспортной задачи.

Числа ui и vj, удовлетворяющие условиям (4.18), называются потенциалами. Причем число ui, называется потенциалом поставщика Ai, а число vj — потенциалом потребителя

Вj.

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

Поскольку как ui так и vj неизвестны, произвольно принимают один из потенциалов равным какой-то величине (например, потенциал поставщика с максимальной мощностью

— равным нулю). Затем вычисляются все остальные потенциалы из уравнений (4.20), (4.21).

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

ui+ vj≤cij (4.22)

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

Если обозначить через ij, характеристику свободной клетки AiBj то ее можно вычислить из формулы (4.22):

(4.23) В оптимальном решении ij≥0. (4.24)

Кроме того, по первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственной задач совпадают: F=G.

169

Здесь следует заметить, что значение целевой функции G следует рассчитывать лишь по потенциалам задачи, которые вытекают из последнего, т. е. оптимального плана.

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

Решение задачи следует начать с отыскания исходного опорного плана задачи. Для этого, как и в предыдущем случае (4.1), воспользуемся способом минимального элемента матрицы С=(сij), так как он позволяет найти план более близкий к оптимальному.