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

Это:

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