Постановка статической транспортной задачи линейного программирования. Сущность и алгоритм метода потенциалов решения транспортной задачи линейного программирования в матричной постановке

44. Постановка статической транспортной задачи линейного программирования. Сущность и алгоритм метода потенциалов решения транспортной задачи линейного программирования в матричной постановке

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

Оптимальный план перевозок в системе - это совокупность объемов перевозок между каждым поставщиком и потребителем по наиболее коротким или дешевым транспортным связям. План перевозок характеризуется затратами на перевозку всего объема. Затраты на перевозку определяются как сумма произведений стоимости перевозки единицы груза на перевозимый объем для всех транспортных связей. Тогда оптимальный план перевозок в транспортной системе имеет минимальные затраты на перевозку.

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

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

Идея метода потенциалов заключается в том, что отличия затрат на перевозку по разным транспортным связям можно представить как разность потенциалов, причем эта разность потенциалов будет тем больше, чем сильнее различаются величины затрат.

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

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

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

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

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

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

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