Алгоритм решения транспортной задачи линейного программирования методом потенциалов

Алгоритм метода потенциалов, при меняемого при решении транспортной задачи линейного программирования (Т3ЛП), состоит из следующих действий:

1) построение матрицы (таблицы) транспортной задачи. Каждая клетка матрицы обозначает транспортную связь между поставщиком и потребителем. Строки матрицы соответствуют поставщикам, а столбцы - потребителям. В верхнем углу каждой клетки записывается стоимость перевозки (оценка транспортной связи). Справа от каждой строки матрицы записывается объем производства, а внизу каждого столбца -объем потребления груза. Объемы перевозок будут записываться в клетки матрицы;

2) построение начального (базисного) плана перевозок. Для построения базисного плана в ТЗЛП существует несколько методов, наиболее распространенными из которых являются метод «северо-западного угла» и метод наименьшей стоимости. По методу «северо-западного угла» распределение объемов перевозок начинается с верхней левой клетки матрицы. В нее помещается минимальное из двух значений: объем производства первого поставщика; объем спроса первого потребителя. Если объем предложения первого поставщика превышает спрос первого потребителя, то излишки продукции отправляются второму потребителю. И наоборот, если объем спроса первого потребителя превосходит возможности первого поставщика, то недостающий объем поставляется от второго поставщика. Объемы производства остальных поставщиков распределяются аналогичным образом. Метод наименьшей стоимости отличается от метода «северо-западного угла» тем, что перевозки в нем в первую очередь распределяются по клеткам с наименьшей оценкой. Количество заполненных перевозками клеток должно быть на единицу меньше суммы количества поставщиков и потребителей. В противном случае возникает случай вырождения, затрудняющий решение ТЗЛП, поэтому необходимо так перераспределить перевозки в базисном плане, чтобы их количество удовлетворяло указанному условию;

3) построение системы потенциалов по методике, описанной в предыдущем пункте;

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

5) перераспределение перевозок. Для определения клеток, из которых удаляются перевозки, и клеток, на которые переносятся перевозки, в матрице строится замкнутый прямоугольный контур. Первой вершиной контура должна быть незанятая клетка с максимальной положительной сдвижкой. Остальные вершины контура должны находиться в занятых клетках. Вершины контура нумеруются (1, 2, З,...), начиная с вершины, находящейся в незанятой клетке, либо поочередно помечаются знаками + и -, начиная со знака + в незанятой клетке. Нумерация или пометка может производиться в любом направлении движения по контуру. Определяется минимальный объем перевозок в четных клетках либо в клетках, помеченных знаком -.Этот объем перевозок переносится из четных клеток (со знаком -) в нечетные клетки (со знаком +);

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