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

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

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

Шаг 1. Каждому поставщику A_i; (т. е. каждой строке) поста­вим в соответствие некоторое число u_i (i=l, m), называемое по­тенциалом А_i, а каждому потребителю B_j (т. е. каждому столбцу) поставим в соответствие некоторое число v_j (j=1, n), называемое потенциалом B_j.

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

u_i+v_j=c_ij

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

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

c’_ij=u_i+v_j

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

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

с'_ij-c_ij ≤ 0,

то план является оптимальным.

В противном случае полученный план не оптимальный, и необходимо переходить к новому базисно­му плану путем перемещения перевозки в клетку, отвечающей условию max [с'_ij—с_ij> 0]. Если таких клеток более одной, то до­говоримся перемещать перевозку в первую по порядку. Выбран­ная клетка помечается в таблице. Переменная, стоящая в этой клетке, вводится в базис.

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

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

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

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

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