Решение закрытой транспортной задачи

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

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

При распределении грузов может оказаться, что количество запятых клеток меньше, чем т + п - 1. В этом случае недостающее их число заполняется клетками с пудеашги пыггнктачи, такие клетки называют условно занятыми. Такая 1р«нспортная задач« называется вы рангов инои.

Рассмотрим нахождение i [сходно го опори о го решения невырожденной транспортной задачи и а конкретном примере.

Пример 1.

На складах A,, At. А, имеются запасы продукции в количествах 90. 400, ПО I соответственно Потребители В,, В3, В, должны получить эту продукцию в ко тчествах 140. 300, 160 т соответственно. Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальном. Расходы но перевозке 1 т продукции ыданы матрицей (у. е.)

Решение.

А, Проверим, является ли данная транспортная задача закрытой:

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

Число занятых клеток в таблице радии 5, т + п - 1 = 3 +■ 3 - 1 = 5. т. е. условие невырожденности выполнено. Получим исходное опорное решение, которое запишем в виде матрицы:

Б. Проверка решения на оптимальность

Найденное исходное опорное решение проверяется па отлшалыюсть методом потенциалов по следующему критерию: если опорное решети транспортной задачи является оптимальным, то ему соответствует система тО: действительных чисел нг и V., удовлетворяющих условиям и, + с, = с,( для запятых клеток н и, + V, г„ < 0 — для свободных юте гик.

Числа и, и с\'; называют потенциалами. В распределительную таблицу добавляют строку и, и столбец щ. Потенциалы и, и п; находя: из равенства и, + >) = с„, справедливого для занятых клеток. Одному из потенциалов дается пронзвотыюе значение, нанрнмер, = 0. тогда остальные потенциалы определяются однозначно. Так, если известен і мнении »л щ то г;; = сч - и„ если нзиестен потенциал Ц, т и, = сч -

Об; ишачим Д,, = и, + П/ - Ср которую называют оценкой евг™, од пых клеток. Если нее оценки свободных клеток Л,, < 0, то опорное решение 19-1322

является оптимальным. Если хотя бы одна на оценок А1; > 0. то опорное решение не являє гея оптимальным и его можно улучшить, перейдя от одного опорного решгиия к другому.

Проверим найденное опорное решение на оптимальность, доба пив в распределительную таблицу столбец и строку V. Теперь цшолпенная таблица имеет следующий вид:

Полагаем и, = 0. запишем ото значение в последнем столбце первой строки таблицы.

В. Переход от одного решения к другому.

Наличие положительной оценки свободной клетки (Д > 0} при проверке опор пито решения на оптимальность свидетельствует о том, что полученное решение не оптимально II для уменьшения значения целевой функции надо перейти к другому опорному решению. При этом надо перераспредели гъ грузы перемещая их из занятых клеток в свободные. Свободная клетка становится занятой, а одна из ранее занятых клеток — свободной.

Для свободном клетки С Д„ > 0 строится цикл (цепь, многоугольник), все вершины которого, кроме одной, находятся в занятых клетках: углы прямые, число вершин четное. Около свободной клетки цикла ставится знак {+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком ( +), и отнимают о г грузов у вершин со знаком (-) В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т. д. до тех пор, пока не получим оптимальное решение.

Рассмотрим переход ш одного опорного решения к другому па ладанном примере.

Струим цикл для клетки (1,3), имеющей положительную оценку У вершин цикла ставим знаки ( + ) к ( )м запнеываем іру.ш.

У вершин со знаком (-) выбираем минимальный груз, он равен 60. Его прибавляем к грузам, стоящим у положительных вершин, и отнимаем от величин фузии, с с j ответе г в у юп u 14 отрицательным вершинам Получаем новый цикл:

Произведем перераспределение грузов по указанному ранее правилу:

Получим новое решение, которому cool петствуст и овал таблица.

Стоимость транспортных расходов составляет:

По сравнению с исходным опорным решением транспортные расходы уменьшились па 1610 1280 = 330 ден. ед.