Методы решения транспортных задач

Для начала решения транспортной задачи необходимо иметь какой-то исходный опорный план, то есть оказаться в какой-то вершине допустимой области. Приведем конструктивный прием построения такого опорного плана, получивший название «метод северо-западного угла». Итак, пусть имеется m складов с запасами и n пунктов потребления с потребностями. Пусть запасы и потребности сбалансированы, то есть. Представим это.

где в столбце справа указаны запасы, в строке снизу потребности, а пустые клетки оставлены для будущего плана перевозок. Начнем заполнение с клетки, расположенной вверху слева, то есть с «северо-западного угла». Вместо впишем число. Возможны два варианта.

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

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

.

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

1. Ну, а в первом складе еще останется запасов продукта. Наша таблица примет вид:

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

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

У нас всего в таблице m строк и n столбцов. Каждый раз исчезает, как минимум, либо строка, либо столбец (могут исчезнуть сразу и строка, и столбец, если запасы какого-то подмножества складов полностью удовлетворят потребности какого-то подмножества пунктов потребления). Однако при последней перевозке исчезает сразу и последняя строка, и последний столбец. Поэтому получающийся план перевозок содержит не более m+n-1 компонент.

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

Рассмотрим два примера. С целью экономии места, вся таблица не переписывается, а лишь приписываются последние строки и столбцы.

Пример 1.

Пусть.

Пример 2.

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

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

произошло потому, что запасы складов и полностью удовлетворили потребности пунктов потребления и и поэтому в тот момент, когда эти сбалансированные потребности удовлетворились (a1+a2=10=b1+b2), обнулились сразу и строка, и столбец. 2].

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

Пример № 2.

Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

Решение:

Задача сбалансирована.

Строим первоначальный опорный план методом минимального элемента.

• 1. Выясним минимальную стоимость перевозок.. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки. Выясним минимальную стоимость перевозок (без учета столбца № 2).
• 2. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта: , ;
• 3. Четвертая перевозка осуществляется с пункта в пункт потребления, т.к. (без учета первого, второго столбца и четвертой строки).
• 4. Пятая перевозка осуществляется с пункта в пункт потребления, т.к. (без учета первого, второго столбца, третьей и четвертой строки). .
• 5. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).

Опорный план имеет вид;

Метод Фогеля При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.

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

Пример Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:

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

Опорный план имеет вид:

Метод двойного предпочтения то план не оптимален.

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

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

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

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

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

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

Пример

Заполняем клетки с двойным предпочтением :

Заполняем клетки с простым предпочтением, начиная с наименьшей стоимости.

Заполняем оставшиеся пустыми клетки.

Это опорный план составленный методом двойного предпочтения. 5].

Потенциалы. Критерий оптимальности плана Итак, наша транспортная задача имеет вид:

Распишем нашу задачу в векторной форме. Для этого введем векторы Как уже говорилось выше, одно из этих ограничений является лишним, и оно может быть вычеркнуто. Рассмотрим теперь двойственную задачу. Так как ограничений всего m + n, то и соответствующие переменные двойственной задачи обозначим так: (переменные, соответствующие первым m ограничениям) и (переменные, соответствующие последним n ограничениям). Тогда, учитывая вид векторов и вид вектора, запишем двойственную задачу в следующем виде:

Величины называются потенциалами складов, а величиныпотенциалами пунктов потребления. Так как одно из ограничений является лишним, то на самом деле одного из потенциалов нет. Для сохранения симметрии всех формул и обозначений можно просто полагать скажем u1=0.

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

Это и позволяет проверить оптимальность любого опорного плана.

Сам алгоритм выглядит следующим образом:

• 1. Один из потенциалов задается произвольно, скажем, полагается .
• 2. Рассматривается система линейных уравнений вида для тех наборов индексов i, j, для которых, и находятся потенциалы и всех складов и всех пунктов потребления.
• 3. Для всех остальных наборов индексов i, j (для которых) проверяется условие .

Если это условие выполняется для всех наборов индексов i, j, для которых, то рассматриваемый план является оптимальным. Если же, хотя бы для одной пары, то план не оптимален.

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

• 1. Одна из величин или задается произвольно, например, полагается .
• 2. Затем рассматриваются уравнения вида для тех j, для которых. Так как известно, то находятся для некоторого множества

индексов .

3. Для этих индексов рассматриваются уравнения вида:

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

4. Далее повторяются пункты 2 (движение по строкам) и 3 (движение по столбцам), пока не определятся все потенциалы.

Проиллюстрируем этот процесс примером, а заодно покажем форму записи результатов при ручном счете.

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

Таблица стоимостей перевозок.

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

План имеет 6=3+4−1 компонент, поэтому он является невырожденным. Заметим, что для него транспортные расходы равны .

Заготовим матрицу размером (в нашем случае размером 3ґ 4), в которую впишем те коэффициенты, которые соответствуют ненулевым перевозкам нашего плана (смотрите следующую страницу).

Далее действуем следующим образом. Полагаем.

1. Идем по строке.

следовательно ;

следовательно .

следовательно .

2. Идем по строке.

следовательно 5. Идем по столбцу.

следовательно .

6. Идем по строке.

следовательно .

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

• 4
• 0

— 3.

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

Сравнивая с матрицей величин мы видим, что условие оптимальности плана нарушено в двух местах — для и. Следовательно, построенный нами план перевозок не является оптимальным. 6].

Дельта-метод Рассмотрим алгоритм дельта-метода в общем виде:

• 1. Рассмотрим таблицы приращений, полученных соответственно в результате выбора каждого столбца наименьшей стоимости и вычитания ее из всех стоимостей столбца, а также таблицу, получающихся в результате выбора в каждой строке приращений и вычитании его из всех приращений строки при условии, что строки с нулевым приращением не рассматриваются.
• 2. Заполнение проводится по столбцам, содержащим одно нулевое приращение, в клетки, содержащие его, записываются потребности, без учета величины запасов на складах. Затем уже с учетом произведенных постановок просматриваем столбцы, содержащие два нулевых и более приращений, и заполняем их, до тех пор, пока все объемы потребностей не будут закреплены за поставщиками.
• 3. Подсчитываются для строк разницы между фактическими запасами и полученными для опорного «фиктивного» плана. Критерием оптимальности плана является нулевая разница по всем запасам и «фиктивным» планом. В случае положительной разницы строки называют недостаточными, в случае отрицательной разницы — избыточными, нулевыми строки называют в случае 0-разницы.
• 4. Отмечаются столбцы, с занятыми клетками в избыточных строках. Для каждой недостаточной и нулевой строки просматриваются приращения, стоящие в отмеченных столбцах, выбирается наименьшее в строке. Эти значения показывают, какое приращение стоимости будет получено на данном шаге, если единицу потребности перезакрепить от одного поставщика к другим (избыточные и недостаточные строки). Сравнивая со значениями нулевой строки, получим два случая:
  • а) для каждой нулевой строки минимальное значение меньше либо равно по отношению к приращениям нулевой строки.
  • б) минимальное приращение больше приращений нулевой строки;

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

В случае б) составляются цепочки.

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

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

5. Исключаем из рассмотрения отмеченные столбцы. Если занятая клетка избыточной строка стала незанятой или избыточной, то начинаем п. 4. В противном случае продолжаем процесс до тех пор, пока все строки не превратятся в нулевые. 7].