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

Метод потенциалов является комбинаторным методом, т.е предполагающий решение поставленной задачи при этом на каждом последующем этапе полученное решение является более лучшим относительно сформированного условия оптимальности. Данный метод используется для решения таких математических моделей, в которых перед всеми заданными переменными находится коэффициент +1. Такие модели возникают при описании транспортных процессов, в которых идет речь о распределении каких-либо ресурсов при этом рассматривается один ресурс, имеющий определенный запас с одинаковым расходом на изменение значения переменных на один пункт.

Примером таких процессов является распределение подвижного состава по объектам, распределение объемов производства на объектах, распределение какого-либо груза по объектам.

Классическим процессом данного типа является задача распределения некой продукции от некоторого количества объектов ее производящих к некому количеству объектов ее потребляющих.

При этом ставится задача об оптимальности распределения при ограниченности объемов производства данной продукции i-ым производителем и ограниченность объектов потребления j-ыми потребителями. (выбирается в качестве условия оптимальности)

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

Как правило, суммарный объем производства продукции не равняется суммарному объему потребления продукции, наблюдается недостаток производства, т.е. дефицит или наблюдается перепроизводство.

В обоих этих случаях считается, что данная задача является открытого типа, т.е. в каких-то случаях потребителям не хватит или у производителей останется. Для решения задачи приводим ее к закрытому типу, т.е приравнивать данное равенство = путем добавления фиктивного участника процесса.

В качестве условия оптимальности выбирается некоторый показатель транспортного процесса, который в общем случае называется транспортные затраты, на перевозку одной единицы продукции от i-го поставщика к j-му потребителю.

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

Транспортные затраты принято указывать в матричном виде

Оптимизация распределения продукции от поставщиков к потребителям, также показывается в матричной форме.

В строчках указывается поставщики, в столбцах потребители.

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

Поскольку необходимо минимизировать суммарные транспортные расходы, то это можно достичь только меняя значение объемов перевозок от поставщиков к потребителям.

Соответственно для минимизации z, необходимо сконцентрировать большие объемы перевозок в ячейках с малыми транспортными затратами и меньшие объемы перевозок в ячейках с большими транспортными затратами. Данная процедура выполняется многократно, спонтанно, с расчетом текущих планов перевозок, транспортные затраты в которых будут постоянно снижаться пока не достигнут минимума – это и будет оптимальный план перевозок. Составление начального плана перевозок можно осуществлять методом потенциальных затрат, т.е. пытаться разместить больший объем в месте с минимальными затратами.

Достоинства метода – сокращение последующих планов.

Недостаток – сложность в расстановке объемов.

Метод северо-западного плана, т.е. расстановка объемов перевозок начиная с верхней левой ячейки и далее вниз по диагонали. Достоинство – простота составления начального плана. Недостаток – большое количеств расчетных планов. Последующие изменения объемов перевозок в ячейках определяется на основании оценки целесообразности перемещения некоторого объема перевозки из одной ячейки, в которой Q>0 (занятые ячейки) в другую ячейку,в которой Q=0 (незанятые или пустые ячейки).

Для оценки целесообразности выполняются следующие действия:

1) для всех поставщиков и потребителей задается условное число, которое называется потенциал и характеризующиедля поставщиков и их конкурентов преимущество, а для потребителей потенциал характеризует их выгоду от поставки к ним продукции от i-го поставщика. Принято начинать с нуля потенциал поставщиков, у которых наибольшие затраты в занятых ячейках. Для поставщиков U=V-C, а для потребителей V=U+C

2) Зная потенциалы поставщиков и потребителей определяется оценки ячеек с нулевыми объемами, данные оценки принято называть сдвижками. Сдвижки определяются только для незанятых ячеек путем вычитания из потенциала потребителя транспортных затрат в этой ячейке и вычитание потенциала поставщика. Значение данных сдвижек может быть >0, =0, <0. G=V-U-C

Если текущий план будет оптимальным, если величина всех сдвижек будет меньше либо равна 0.

При если величина всех сдвижек будет больше либо равна 0.

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