Этап 3. Улучшение неоптимального плана перевозок (циклы перераспределения).

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

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

Результат указанных операций для представленного в табл.

4-30 + 5-0 + 2-30 + 3-100 + 7-10 + 4-110 = 990, что значительно меньше предыдущей суммы затрат 1170, хотя план перевозок в табл. 3.10 еще не является оптимальным. Об этом свидетельствует наличие отрицательных значений в матрице оценок клеток этого плана (соответствующие потенциалы Ui и Vj найдены способом, изложенным при описании этапа 2): ' 0 0 0 4) (dij) = -1 0 6 5 ,-3 -8 0 0, Таблица 3.10

Мощности поставщиков Мощности потребителей щ 30 100 40 110 0 30 5

0 2

^^ 30 3 0 100 1 ^^100 6 2 2 120 6 2 7 ^^ 10 4

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

L. Пример 4. Решим методом потенциалов закрытую транспортную задачу, заданную в табл. 3.11, в которую уже внесено некоторое допустимое базисное распределение. Суммарные транспортные расходы составляют при этом плане перевозок f(X) = 3- 5 + 2-25 + 1-20 + 2-25 + 1-15 + 4-20 = 230. Потенциалы по формуле (3.20) находим следующим образом: задавая щ = 0, находим по клетке (1;1) Uj = 3, по клетке (1;2) u2 = а по клетке (1;4) и4 = 1; затем по клетке (2;1) находим и2 = 1 и по клетке (2;3) = 2; наконец, по клетке (3;3) находим и3 = -2.

Таблица 3.11 Мощности поставщиков Мощности потребителей Щ 30 25 35 20 50 3

5 1

^ \ 25 4 1

^^ 20 0 40 2

25 JL

| 5 1 20 3 2 <1- 4 -2 "і 3 2 2 1 Матрица оценок клеток для этого плана рассчитывается по формуле (3.21): ш

2 0 0

0

2 -2

о о

1-2

Наличие отрицательных оценок свидетельствует о том, что план неоптимален.

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

Таблица 3.12 Мощности поставщиков Мощности потребителей Щ 30 25 35 20 50 3

25^ 2 ^^ 4 1

^^ 20 0 40 2 ^^ 5 3 1

35 5 1 20 3 2

20 4 4 0 "і 3 2 2 1

Матрица оценок клеток этого распределения не содержит отрицательных значений: Л

(dU) =

0 0 2 0 0 2 0 5

v0 0 2 3, следовательно, данный план перевозок является оптимальным. Стоимость перевозок по этому плану равна

f(X) = 3-25 + 2- 5 + 1-20 + 2- 5 + 1-35 + 2-20 = 180.

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