Построенный одним из описанных выше методов исходный план можно довести до оптимального с помощью симплекс-метода. В силу особенностей модели транспортной задачи (ограничения имеют вид равенств, каждая неизвестная, входит только в два уравнения, коэффициенты при неизвестных единицы) процесс ее решения симплекс-методом является громоздким. Поэтому для нахождения оптимального плана транспортной задачи созданы специальные методы, самым распространенным из которых считается метод потенциалов.
Рассмотрим алгоритм, реализующий этот метод.
Шаг 1. Каждому поставщику Ai; (т. е. каждой строке) поставим в соответствие некоторое число ui (i=l, m), называемое потенциалом Аi, а каждому потребителю Bj (т. е. каждому столбцу) поставим в соответствие некоторое число vj (j=1,n), называемое потенциалом Bj.
Для каждой заполненной клетки, т. е. для каждой базисной переменной, строится соотношение
ui+vj=cij
Полученная система должна содержать m+n—1 уравнений (так как количество базисных переменных равно т + п —1) с m + п неизвестными. Как известно, такая система имеет множество решений, и любое из них будет содержать искомые потенциалы. Чтобы найти одно из решений, значение одного потенциала в системе задается произвольно. Обычно считают, что ui = 0, и находят значения остальных потенциалов. Значения потенциалов записывают справа и снизу таблицы против соответствующих строк и столбцов.
|
|
Шаг 2. Для каждой незаполненной клетки, т. е. для каждой небазисной переменной, рассчитываются так называемые косвенные тарифы (с'ij) по формуле
c’ij=ui+vj
Расчет косвенных тарифов проводится непосредственно по таблице, результат заносится в левый нижний угол соответствующей незаполненной клетки.
Шаг 3. Проверяем полученный план на оптимальность по критерию оптимальности плана транспортной задачи. Если для каждой незаполненной клетки выполняется условие
с'ij-cij ≤0,
то план является оптимальным.
В противном случае полученный план не оптимальный, и необходимо переходить к новому базисному плану путем перемещения перевозки в клетку, отвечающей условию max [с'ij—сij>0]. Если таких клеток более одной, то договоримся перемещать перевозку в первую по порядку. Выбранная клетка помечается в таблице. Переменная, стоящая в этой клетке, вводится в базис.
Шаг 4. Для правильного перемещения перевозок, чтобы не нарушить ограничений, строится цикл, т. е. замкнутый путь, соединяющий выбранную незаполненную клетку с ней же самой и проходящий через заполненные клетки. Цикл строится следующим образом. Вычеркиваются все строки и столбцы, содержащие ровно одну заполненную клетку (выбранная клетка при этом считается заполненной). Все остальные заполненные клетки составляют цикл и лежат в его углах.
|
|
Замечание. После перевода незаполненной клетки в число заполненных количество заполненных клеток становится равным m+n. Для такого количества клеток всегда можно построить цикл, и он будет единственным. Направление построения цикла (по часовой стрелке или против) несущественно.
Шаг 5. В каждой клетке цикла, начиная с незаполненной, проставляются поочередно знаки «+» и «—» (обычно они ставятся в правом нижнем углу клетки). В клетках со знаком «—» выбирается минимальная величина. Новый базисный план получается путем сложения выбранной величины с величинами, стоящими в клетках цикла со знаком «+», и вычитания этой величины из величин, стоящих в клетках со знаком «—».
Выбранная минимальная величина будет соответствовать переменной, выводимой из базиса. Если таких величин более одной, то из базиса выводится любая из соответствующих им переменных. Значения переменных,
включенных в цикл, после описанной корректировки переносятся в новую таблицу. Все остальные переменные записываются в новую таблицу без изменений. Осуществляется переход к шагу 1.
Замечание. Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти ее минимум.