ИсследОпераций

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

Сравним значения целевой функции z на старом и новом планах перевозок

Для нового определенного соотношениями (4.2) плана, учитывая неравенство

(4.1), имеем

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

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

Из доказанной теоремы 4.1 следует, что при отыскании оптимального плана перевозок ТЗ можно рассматривать только ее ациклические планы.

104

§ 5. Построение исходного ациклического плана ТЗ

Решение закрытой ТЗ с m поставщиками и n потребителями начинают с нахождения ее ациклического плана, содержащего ровно m n 1 занятую

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

Метод северо-западного угла. Пусть дана закрытая ТЗ, условие которой записано в виде табл. 12. Ациклический план перевозок этой задачи будем строить, начиная с установления объема перевозки от 1 поставщика к 1 потребителю, т.е. с заполнения верхней левой («северо-западной») клетки таблицы. Примем этот объем перевозки x11 максимально возможным по условиям задачи, т.е. равным

наименьшему из чисел a1 и b1 :

x11 min a1,b1 .

Если a1 b1 , то запасы 1-го поставщика полностью израсходованы и поэто-

му все остальные клетки 1 строки заполняем прочерками. Запросы 1-го потребителя теперь равны b1 a1 .

Если a1 b1 , то запросы 1-го потребителя полностью удовлетворены и по-

этому все остальные клетки 1 столбца заполняем прочерками. 1 поставщик теперь располагает только a1 b1 единицами продукции.

Если a1 b1 , то из рассмотрения можно исключить и 1-го поставщика и

1-го потребителя, т.е. заполнить прочерками 1 строку и 1 столбец таблицы. Одна-

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

Теперь в левую верхнюю клетку незаполненной части исходной таблицы помещаем максимально возможны объем перевозок (он может оказаться и нулевым). Продолжая этот процесс, мы придем к ациклическому плану данной ТЗ, содержащему m n 1 занятую клетку.

Метод наименьшей стоимости. Отличие этого метода лишь в том, что на каждом шаге максимально возможным объемом перевозок заполняется не левая верхняя клетка, а та клетка незаполненной части таблицы, в которой содержится наименьшая стоимость перевозок cij (если таких клеток несколько, то произволь-

но может быть выбрана для заполнения любая одна из них).

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

З а м е ч а н и е 2. Планы, построенные описанными выше методами, всегда являются ациклическими и содержат m n 1 занятую клетку. Иногда не-

которые из клеток этих планов считаются занятыми, несмотря на то, что в них записан равный нулю объем перевозок.

105

Пример 1. Для транспортной задачи

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

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

Сначала заполняем левую верхнюю клетку табл. 16, помещая в нее объем перевозок x11 min a1,b1 30 . В результате из дальнейшего рассмотрения ис-

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

Оставшийся у 1-го поставщика запас a полагаем равным нулю.

1

(в дальнейшем эта клетка считается занятой). Так как у 1-го поставщика исчерпан весь запас продукции, заполняем клетки соответствующей ему 1-й строки прочерками.

Далее заполняем левую верхнюю клетку (2,2) незаполненной части таблицы, записывая в нее объем перевозок x22 min a2,b2 30 . Запросы 2-го потребителя

полностью удовлетворены, поэтому прочеркиваем остальные клетки 2-го столбца. Оставшиеся запасы 2-го поставщика полагаем равными a2 a2 x22 15.

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

106

z 5 30 3 0 4 30 6 15 3 15 5 30 555 .

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

Таблица 17

Записав условия ТЗ в виде табл. 17, выделяем в ней клетку с наименьшей стоимостью cij . Помещаем в эту клетку (3,2) максимально возможный объем перевозок

x32 min a3,b2 30 . В результате исключаем из рассмотрения 2-го потребителя, прочеркивая клетки соответствующего ему столбца, и изменяем запасы 3-го по-

ставщика на a a x 15 .

3 3 32

В незаполненной части табл. 17 наименьшая стоимость содержится в клетках (2,1) и (3,3). Выбрав одну из этих клеток, например, (2,1), помещаем в нее x21 min a2,b1 30 , прочеркиваем все клетки 1-го столбца и изменяем запасы

2-го поставщика на a a x 15 .

2 2 21

Продолжая те же действия, приходим к содержащемуся в табл. 17 ациклическому плану, для которого

z 4 15 5 15 3 30 6 15 2 30 3 15 420 .

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

а) для каждой занятой клетки таблицы сумма соответствующих потенциалов должна быть равна записанной в этой клетке стоимости:

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

§ 7. Проверка плана ТЗ на оптимальность

Пусть дана закрытая ТЗ с m поставщиками и n потребителями, для которой известен записанный в транспортной таблице ациклический план перевозок, содержащий m n 1 занятую клетку.

Проверка этого плана на оптимальность состоит из следующих этапов.

1. Построение системы уравнений для потенциалов. Вводим потенциалы поставщиков ui i 1, m и потребителей v j j 1, m , записывая для каждой за-

нятой клетки i, j уравнение

ui v j cij ,

получаем систему из m n 1 линейных уравнений с m n неизвестными.

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

3.Проверка плана на оптимальность. Для каждой свободной клетки i, j

транспортной таблицы вычисляем величину

Если для всех свободных клеток ij 0 , то рассматриваемый план перевозок яв-

ляется оптимальным планом данной ТЗ. Если же хотя бы для одной свободной клетки ij 0 , то данный план оптимальным не является.

109

Пример 1. Для транспортной задачи

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

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

u3 v1 4, u3 v3 5 .

содержащую пять уравнений с шестью неизвестными. Полагая u1 0 , находим v2 6, v3 4, u2 1, u3 1, v1 5 .

Записываем найденные значения потенциалов в первую строку и первый столбец табл. 18.

Для каждой свободной клетки i, j табл. 18 вычисляем по формуле (7.1) число ij . Получаем

110

Поскольку все величины ij неположительны, построенный план является оптимальным планом перевозок данной ТЗ.

§ 8. Алгоритм решения ТЗ методом потенциалов

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

I. Начальный шаг

1. Используя метод северо-западного угла или метод наименьшей стоимости, находим для данной ТЗ ациклический план перевозок, содержащийm n 1 занятую клетку.

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

П. Общий шаг

1. Построение нового ациклического плана:

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

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

них), помечаем ее знаком + и добавляем к числу занятых клеток.

б) Теперь в таблице m n занятых клеток и из них можно образовать по крайней мере один цикл. Отыскиваем любой такой цикл и, начиная с отмеченной знаком + клетки, последовательно обходим его клетки, проставляя в них поочередно знаки и + .

в) Из всех объемов перевозок xij , записанных в отмеченных знаком клет-

ках, выбираем наименьший и обозначаем его через . Вычитаем величину из объемов перевозок, которые расположены в клетках, отмеченных знаком , и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком + . Получаем новый ациклический план перевозок данной ТЗ, содержащийm n 1 занятую клетку.

2. Проверяем построенный план на оптимальность. Если этот план не оптимален, то снова повторяем общий шаг данного алгоритма.

Пример 1. Методом потенциалов решить ТЗ

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

111

Для нахождения потенциалов составляем систему уравнений:

Полагая u1 0 , находим содержащиеся в табл. 19 значения потенциалов. Вычисляя для каждой свободной клетки табл. 19 величину ij , получаем

11 2, 22 6, 23 4, 31 2, 33 5, 34 1.

Так как среди найденных значений ij имеются положительные, то постро-

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

11 2 , поэтому помечаем клетку (1,1) табл. 19 знаком + и включаем ее в число

занятых клеток. Из занятых клеток строим цикл, который показан в табл. 19. Отмечаем клетки выбранного цикла знаками и + и находим величинуmin 7,10 7 . Вычитая величину из объемов перевозок, расположенных в

отмеченных знаком клетках, и прибавляя к объемам перевозок в клетках со знаком +, получаем новый ациклический план перевозок, записанный в табл. 20.

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

zmin 3 7 4 2 3 12 2 3 3 10 2 16 133.

112