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

3.3.1. Метод потенциалов

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

Рассмотрим алгоритм, реализующий этот метод.

Шаг 1. Каждому поставщику (т.е. каждой строке) поставим в соответствие некоторое число, называемоепотенциалом , а каждому потребителю(т.е. каждому столбцу) поставим в соответствие неизвестное число, называемоепотенциалом .

Для каждой заполненной клетки, т.е. для каждой базисной переменной, строится соотношение

(3.17)

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

Шаг 2. Для каждой незаполненной клетки, т.е. для каждой небазисной переменной, рассчитываются так называемые косвенные тарифы () по формуле:

(3.18)

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

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

(3.19)

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

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

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

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

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

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

Осуществляется переход к шагу 1.

Замечание. Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти её минимум.

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

Таблица 3.5

Первой строке табл. 3.5 поставим в соответствие потенциал , второй – потенциал, а столбцам соответственно потенциалы. Для каждой заполненной клетки на основании формулы (3.17) построим соотношения, определим значения потенциалов и запишем их в табл. 3.5 справа и снизу против соответствующих строк и столбцов:

Для каждой незаполненной клетки по формуле (3.18) рассчитаем косвенные тарифы и занесем их в левый нижний угол соответствующий незаполненной клетки табл. 3.5:

Проверяем полученный план на оптимальность по формуле (3.19):

8 – 5 = 3  0, 7 – 4 = 3  0.

Критерий оптимальности плана транспортной задачи нарушается в обеих незаполненных клетках. В общем случае необходимо переходить к новому базисному плану путем перемещения перевозки в клетку, отвечающую максимальной положительной разности (). На данной итерации таких клеток две (клетки, отвечающие переменным и). Поэтому будем перемещать перевозку в первую по порядку клетку, то есть клетку, отвечающую переменной. Отметим эту клетку в табл. 3.3.1.

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

В каждой клетке цикла, начиная с клетки, отвечающей переменной , проставим поочередно знаки «+» и «-». В клетках со знаком «-» выберем минимальную величину. В данном случае эта величина равна 1. Новый базисный план отражен в табл. 3.6. Значение переменной, не включенной в цикл, переносится без изменений. Переменные, включенные в цикл, корректируются на выбранную величину, которая равна 1, в зависимости от знаков «+», и «-», стоящих в клетках цикла.

Таблица 3.6

Полученный в табл. 3.6 новый базисный план прежде всего необходимо проверить на вырожденность.

План невырожденный. Значение базисных переменных:

Транспортные расходы:

Переходим к шагу 1. Дальнейшее решение задачи приведено в табл. 3.6-3.8. На каждой итерации необходимо осуществить проверку плана на вырожденность и шаги 1-5 алгоритма. На последней итерации, когда получен оптимальный план, последним является шаг 3 алгоритма.

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

5 – 8 = -3  0,

4 – 7 = -3  0.

Значение базисных переменных в оптимальном плане: . Транспортные расходы:

.

Исходный план, полученный методом минимального элемента (табл. 3.4), будет оптимальным.

Таблица 3.7

Таблица 3.8

Пример 3.4.Решить заданную транспортную задачу методом потенциалов. Для построения исходного плана использовать следующие методы:

• Метод северо-западного угла;

• Метод минимального элемента.

Таблица 3.9

Всего	99	97	95	95	95
96	16	15	14	15	6	А1
97	8	11	6	8	8	А2
99	12	7	9	13	8	А3
189	10	8	4	3	8	А4
	В1	В2	В3	В4	В4

1. Метод северо-западного угла.

Таблица 3.10

Транспортные расходы:

2. Метод минимального элемента

Таблица 3.11

Транспортные расходы:

3. Метод потенциалов(для оптимизации исходного плана, полученного методом северо-западного угла)

Таблица 3.12

Косвенные тарифы для незаполненных клеток:

Значение целевой функции на данном этапе:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»: 1. Перейдем к следующей таблице.

Таблица 3.13

Косвенные тарифы для незаполненных клеток:

Значение целевой функции на данном этапе:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»: 93. Перейдем к следующей таблице.

Таблица 3.14

Косвенные тарифы для незаполненных клеток:

Значение целевой функции на данном этапе:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»:1. Перейдем к следующей таблице.

Таблица 3.15

Косвенные тарифы для незаполненных клеток:

Проверка на оптимальность:

Полученный план является оптимальным.

Транспортные расходы:

4. Метод потенциалов(для оптимизации исходного плана, полученного методом минимального элемента).

Таблица 3.16

Косвенные тарифы для незаполненных клеток:

Проверка на оптимальность:

Полученный план не является оптимальным. Минимальное количество единиц груза из клеток, отмеченных знаком «-»:1. Перейдем к следующей таблице.

Таблица 3.17

Косвенные тарифы для незаполненных клеток:

Проверка на оптимальность:

Полученный план является оптимальным.

Транспортные расходы: