Некоторые определения и понятия

В математической формулировке транспортную задачу можно сформулировать так: требуется минимизировать общую стоимость перевозок

при условии, что на неизвестные наложены ограничения

Алгоритм решения транспортной задачи состоит из следующих шагов:

1. Составить исходный опорный план.

2. Найти оценки для каждой свободной клетки.

3. Проверить, будет ли найденный план оптимальным.

4. В случае, если найденный план не является оптимальным, то перейти к новому опорному плану, а затем к пункту 2.

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

Невырожденный опорный план транспортной задачи содержит положительных компонент или перевозок. Остальные перевозки равны нулю.

Определение 1. Клетки в таблице перевозок, в которых находятся отличные от нуля перевозки, называются занятыми или базисными, остальные (с ) – незанятыми или свободными.

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

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

Виды замкнутых циклов:

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

Определение 3. Означенным циклом называется цикл, каждой вершине которого приписан знак “+” или “-”, причем соседним вершинам приписаны разные знаки (соседние вершины – вершины, лежащие на одном звене цикла).

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

Определение 5. Оценкой свободной клетки называется алгебраическая сумма стоимостей перевозок, взятых вдоль означенного цикла, образованного клеткой и базисными клетками. Клетке приписывается знак “+”, тогда

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

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

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

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

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

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

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

Пример 1. Найти исходный опорный план транспортной задачи:

Таблица 1.6.1

Составим исходный опорный план по методу северо-западного угла.

Имеем:

Таблица 1.6.2

Опорному плану, полученному в табл. 1.6.2, соответствуют и значение функции цели .

Теперь составим исходный опорный план по методу минимального элемента.

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

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

Таблица 1.6.4

Так, в табл. 1.6.4, в клетку , имеющую наименьший тариф, нужно поместить ед. груза. Столбец исключаем из рассмотрения, так как потребности удовлетворены. Наличие груза у поставщика стали равными 230ед. (остаток записываем за косой чертой). Затем размещаем груз в клетку в количестве ед. Исключаем столбец , остатки груза на складе станут равными 450ед. Переходим к клетке и помещаем в нее ед. Запасы закончились, исключаем строку и так далее.

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

Имеем .

Как видно, план, составленный по методу минимального элемента, оказался лучше.

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