8.3. Метод потенциалов

Метод потенциалов линейного программирования применяется при решении задач, связанных с распределением на транспортной се­ти грузопотоков: закрепление потребителей грузов за поставщиками, распределение парка подвижного состава по автотранспортным пред­приятиям, закрепление маршрутов работы подвижного состава за ав­тотранспортными предприятиями и другие задачи. Задача закрепления потребителей за поставщиками получила название классической транс­портной задачи. Решение такой задачи сводится к выбору транспортных маршрутов, по которым продукция различных предприятий перевозится на несколько конечных пунктов назначения.

Математическая модель классической транс­портной задачи в общем виде записывается в следующей форме:

минимизировать

при ограничениях

где: m - число поставщиков;

n - число потребителей;

Xij - объем перевозок между i и j пунктами;

S_i- - ограничения по предложению;

Di - ограничения по спросу;

a_ij - расстояние от пункта i до пункта j.

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

Каждый потребитель должен получить столько, сколько ему требует­ся, т. е.

Необходимо найти такой вариант плана перевозок, чтобы транспорт­ная работа была минимальна, т.е.

Запись и решение транспортной задачи методом потенциалов вы­полняется в таблично-матричной форме. Совокупность всех элементов матрицы х_ij называется планом перевозок или распределением поставок. Элементы матрицы называются показателями критерия оптимальности.

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

Если допустимый план удовлетворяет условию (8.34), то он является оптимальным. В условии (8.34) сформулирована цель задачи или ее целе­вая функция. При решении транспортной задачи в качестве целевой функции могут приниматься следующие показатели: минимум тонно-километрового пробега, минимум провозных плат, минимум эксплуата­ционных расходов, минимум тонно-часов транспортирования и др.

Критерий «минимум тонно-километрового пробега» (показатель критерия - расстояние) наиболее прост для применения и оп­ределения. К его недостаткамследует отнести то, что при одинако­вом расстоянии транспортирования могут быть различные затраты (движение подвижного состава по различным дорожным покрытиям, пе­ревозки по дорогам с различной интенсивностью движения и т. д.).

Критерий «минимум провозныхплат» (показатель кри­терия - тарифы) применяется для получения схемы грузопотоков, обес­печивающей минимальные затраты грузоотправителей. К недостаткам этого критерия следует отнести то, что тарифы не обладают свойством аддитивности, т. е. суммы тарифных плат от пункта Адо пункта Би от пункта Бдо пункта Вне идентичны тарифу от пункта Адо пункта В.Это не дает возможности использовать тарифы в качестве критерия опти­мальности при сетевой постановке задачи, а также при использовании машинных методов составления матриц.

Критерий «минимум эксплуатационных расходов на транспортиро­вание грузов» (показатель критерия - себестоимость транспортирова­ния) отражает затраты автотранспортного предприятия, осуществляю­щего выполнение перевозок. Этот критерий может также использовать­ся при распределении перевозок между различными видами транспорта. Его недостатками являются:себестоимость транспорти­рования рассчитывается на обезличенный груз и не учитывает затрат, возникающих при перевозке отдельных видов специальных грузов; не учитывает изменение затрат на погрузочно-разгрузочные работы при использовании различных видов подвижного состава; сложность расче­та себестоимости транспортирования по отдельным участкам дорожной сети.

Критерий «минимум тонно-часов транспортирова­ниягруза» (показатель критерия - время транспортирования) может применяться при перевозке скоропортящихся грузов, овощей, живности и другой продукции. К его недостаткамотносится то, что он не учитывает затрат, связанных с транспортированием груза.

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

Чтобы задача имела допустимое решение, требуется, чтобы общие ресурсы поставщиков были не меньше общего спроса потребителей S_i≥ Dj,а также естественным представляется и требование неотрица­тельности объема поставок и спроса, т. е.Si ≥ 0, Dj≥ 0.

Рассмотрим применение метода потенциалов на следующем примере:

Задача 8.5.Из трех грузообразующих пунктовA₁, А₂, А₃необхо­димо перевезти однородный груз четырем потребителям B_l, В₂,B₃, B₄.Количество груза в пункте А₁= 300 т, в пункте А₂ =500 т,A₃= 800 т. Спрос потребителей на данный груз составляет: В₁= 200 т, В₂= 350 т,B₃= 650 т, В₄= 400 т. Расстояния между грузоотправите­лями и грузополучателями приведены в табл. 8.2. Необходимо так закре­пить потребителей груза за грузополучателями, чтобы общая транспорт­ная работа была минимальной (показатель критерия оптимальности - расстояние).

Таблица 8.2

Расстояние между грузообразующими и грузопоглощающими пунктами

Для решения задачи обозначим через х_ijколичество тонн груза, ко­торое должно быть перевезено отi-поставщикаj-потребителю. Тогда ма­тематическая модель задачи выразится системой уравнений (8.35), а це­левая функция, представляющая собой сумму произведений расстояний на соответствующий объем перевозок груза в тоннах, уравнением (8.36).

Минимизировать

Полученная система уравнений (8.35) является линейно зависимой, так как любое ее уравнение можно представить в виде линейной комби­нации остальных уравнений. Действительно, если из суммы уравнений 1, 2, 3вычесть сумму уравнений 4, 5,6, то получим уравнение 7 и т. д. Чис­ло линейно независимых уравнений должно быть меньше на одно общего числа уравнений в системе, т. е. базис системы должен быть равен коли­честву уравнений в системе ограничений за вычетом единицы. Так как общее число уравнений в системе определяется суммой поставщиков и потребителей, то в базисе должно быть уравнений

т + п-1, (8.37)

где: m- число поставщиков;

n- число потребителей.

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

Матрица- прямоугольная таблица чисел, состоящая изmстрок иnстолбцов, в которой на пересечении строк и столбцов, обычно в пра­вых верхних углах, указывается расстояние между данным поставщи­ком и потребителем (в общем случае указывается показатель целевой функции).

К базисному плану предъявляются следующие требования:

он должен быть допустимым, содержать m + n — 1 загруженных клеток, чтобы загруженные клетки были расположены в порядке вычеркивае­мой комбинации. Для сокращения числа итераций при последующем ре­шении желательно, чтобы базисный план был, возможно, ближе к оп­тимальному.

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

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

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

Самый простой способ составления базисного плана - это так назы­ваемый способ северо-западного угла. Сущность этого спо­собазаключается в следующем. Распределение груза по потребителям начинается с клетки А₁В₁(табл. 8.3). Если предложение больше спроса, то следующая цифра ставится в клетке А₁ В₂и т. п.

Таблица 8.3

Базисный план, составленный способом северо-западного угла

Клетки таблицы, в которых отмечено количество груза, перевозимого от грузоотправителя к данному грузополучателю, называются загружен­ными. Остальные клетки - незагруженными. Способ северо-западного угла является плохим способом составления базисного плана, так как в большинстве случаев дает базисный план, очень далекий от оптималь­ного.Положительная сторона его заключается в том, что он очень прост и обеспечивает получение т + п-1 загруженных клеток.

При полученном базисном плане закрепления поставщиков за потребителями (табл. 8.3), транспортная работа составит

200 • 11 +100 • 7 + 250 • 13 + 250 • 7 + 400 • 5 + 400 -9 = 13500 т-км.

Несколько лучшими способами составления базисного плана являют­ся способы наименьшего элемента по столбцу или наименьшего элемента по строке.При составлении базис­ного плана способом наименьшего элемента по столбцу поочередно в столбцах матрицы отмечаются клетки с минимальным значением ау и в

них заносятся поставки. Если при записи поставок спрос по столбцу удовлетворен не полностью, ищется следующий по величине показа­тель a_ij, и так до полного удовлетворения спроса. Только после этого переходят на следующий столбец. Когда в столбце два или несколько одинаковых по величине минимальных показателейa_ij, то поставки мо­гут быть размещены в любом из них. Результаты составления базисного плана этим способом приведены в табл. 8.4.

Таблица 8.4

Базисный план, составленный способом наименьшего элемента по столбцу

При базисном плане, полученном способом наименьшего элемента по столбцу (табл. 8.4), транспортная работа составит

200-3 + 300-7 + 50-12 +100-7 +550-5 + 400-8 = 9950т-км.

Базисный план получился лучше (транспортная работа сократилась на 3550 т-км), однако нельзя сказать, является ли он оптимальным или нет. Для ответа на этот вопрос необходимо составленный базисный план проверить на оптимальность. Для этих целей разработано несколько ме­тодов. Наиболее широкое применение находят методы потенциалов (ме­тода МОДИ), Хичкока, Креко.

Идея метода потенциаловбыла высказана Л. В. Канторовичем в 1940 г. В 1951 г. американский ученый Дж. Д. Данциг предложил ту же идею, назвав ее модифицированным распределительным методом (МО­ДИ). Идея метода потенциалов, или метода МОДИ, заключается в том, что для проверки допустимого базисного плана на оптимальность опре­деляются особым образом числа, называемые потенциалами.Главное требование к потенциаламзаключается в том, чтобы каждый показатель a_ijв загруженной клетке был равен сумме потенциалов своих строки и столбца

a_ij=V_i+Vj, (8.38)

где: Ui- значение потенциала строки;

Vj- значение потенциала столбца.

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

Потенциалы незагруженных (свободных) клеток определяются по формуле

где: Е_ij- потенциал свободной клетки.

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

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

Проверим на оптимальность базисный план, составленный способом наименьшего элемента по столбцу. Для этого матрицу распределительно­го метода дополним одним столбцом и строкой (табл. 8.5). Поставим в строке A₁величину потенциала, равную нулю. Тогда, согласно форму­ле (8.38), потенциал столбца В₂будет равен 7. Потенциал строкиA₃ будет равен 5, а столбцаB₃- 0 и т. д. Потенциалы незагруженных кле­ток находим по формуле (8.39).

В результате проверки допустимого плана на оптимальность получе­на клетка А₂В₂, имеющая отрицательный потенциал. Это указывает на то, что план не оптимален и необходимо выполнить перераспределение закрепления поставщиков за потребителями. Это выполняется сле­дующим образом. Строится контур. Контуром называется замкнутая ломаная линия, образованная прямыми отрезками, углы со­единений между которыми равны 90°. Строится контур так, чтобы все углы, кроме одного, располагались в загруженных клетках, а один угол в свободной, наиболее потенциальной клетке. При соблюдении этих правил для каждой свободной (незагруженной) клетки можно построить только один контур. Определяют положительные (+) и отрицательные (-)углы контура. Первый положительный угол лежит в незагруженной клетке, для которой строится контур, рядом с ним находятся отрица­тельные углы и т. д.

Таблица 8.5

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

Ранее загруженные клетки, которые не оказались расположенными в углах контура, переносятся в матрицу нового варианта закрепления по­требителей груза за поставщиками без изменения (табл. 8.6).

Таблица 8.6

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

200-3 + 300-7 + 50-13 + 50-7 + 600-5 + 400-8 = 9900 т-км.

Последовательность решения транспортной задачи методом по­тенциалов схематически показана на рис. 8.7.

Ранее отмечалось, что способ северо-западного угла является самым неудачным способом со­ставления базисного плана. Распределение поставок способом наимень­шего элемента по столбцу или по строке значительно улучшает базисный план поставок. Помимо этих приемов, улучшающих базисный план, рас­смотрим еще три способа: способ аппроксимации У. Фогеля, способ по­следующего анализа (способ стрелок) и способ двойного предпочтения.

Способ аппроксимации У. Фогеля.По мнению У. Фо­геля, его способ может заменить во многих случаях методы линейного программирования. На самом деле его можно применять только для со­ставления базисного плана, а затем для решения задачи использовать обычную процедуру линейного программирования.

При составлении базисного плана поставок способом аппроксимации У. Фогеля исходные данные заносятся в таблицу, которая отличается от матрицы метода потенциалов тем, что имеет дополнительную строку и столбец разностей (табл. 8.7).

Таблица 8.7

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

Так, в столбце минимальный элемент равен 3 в клетке А₃В₁. Сле­дующий за ним по величине элемент, равный 5, находится в клеткеА₂В₁.Разность между ними равна 2. Эта и другие разности по строкам и столбцам записаны в табл. 8.7.

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

Смысл способа У. Фогеля заключается в следующем.Найденные разности показывают, насколько больше будут расстояния, если в со­ответствующем столбце или строке поставка будет записана не в клетку, где находится минимальный в этом столбце или строке элемент, а в клетку, где находится элемент, следующий за ним по величине. Там, где разность оказывается наивысшей, будут наибольшие потери на единицу продук­ции, если поставка не попадет в клетку с наименьшим оптимизирую­щим элементом.

В нашем примере, записав максимальную поставку в клетку А₁ В₂в количестве 300 т, исключаем показатели критерия оптимальности по этой строке, поскольку мощность поставщика А₁полностью исчерпа­на, и вновь определяем разности между наименьшими элементами по строкам и столбцам матрицы (табл. 8.8.)

Таблица 8.8

Если оказывается несколько одинаковых разностей, имеющих мак­симальное значение (в нашем примере столбцы В₁В₃и строки А₂и A₃), то в соответствующих им столбцах или строчках находят и загружают седловую точку.Седловой точкойназывают клетку таблицы, рас­стояние которой имеет наименьшее значение (при решении задачи на минимум) из всех расстояний ее строки и столбца или наибольшее значе­ние при решении задачи на максимум.

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

В нашем примере седловой точкой будет клетка А₃В₁в которую за­писывается максимально возможная поставка, и т. д.

Способ последующего анализа (способ стрелок). Первоначальное закрепление потребителей за поставщиками, начиная с первого столбца с учетом наименее возможного расстояния транспор­тирования, потребности грузопотребителя и возможности поставщика (см. табл. 8.4). Полученный базисный план анализируется с целью выяв­ления возможностей его улучшения. В строке А₃можно передвинуть из клетки А₃В₂ вклетку A₃В₁50 т, а из клетки А₂В₃в клетку А₂В₂вместо это­го - 50 т. В результате этого в первом случае расстояние перевозки уве­личится на 7 км, а во втором случае сократится на 6 км. Суммарное со­кращение расстояния перевозки составит 1 км.

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

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

Если при составлении базисного плана число загруженных клеток получается больше, чем m + n-1, то при проверке на оптимальность для какой-либо строки или столбца будут найдены два потенциала. Чтобы устранить такую ситуацию, нужно произвести следующие действия:

построить для загруженной клетки, по которой определены два по­тенциала, контур так, чтобы все его углы лежали в загруженных клетках;

углы контура обозначить попеременно знаками «плюс» и «минус». Углу, лежащему в загруженной клетке, для которой построен контур, присваивается знак «плюс»;

выявить наименьшую загрузку в клетках, занятых углами со знаком «плюс», вычесть ее из всех клеток и прибавить во все клетки, занятые углами со знаком «минус».

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

Если число загруженных клеток при составлении базисного плана окажется меньше, чем т + п - 1, то недостающее число клеток загру­жают нулями. Загружать следует те клетки, которые лежат на пересече­нии строк и столбцов, не имеющих потенциалы, со строками или столб­цами, для которых потенциалы уже определены и имеют наименьшие значения показателя критерия оптимальности.

Дополнительные условия при решении транспортных задач ме­тодом потенциалов. Предложение больше спроса.Условия задачи записываются в таблицу, в которую вводится фиктивный столбец Р с ограничением по спросу, равный разности между предложением и спросом. Так как груз никуда не вывозится, то в углах клеток столбца Р ставятся нули. Задачу решают по алгоритму метода потенциалов, рас­сматривая столбец Р как потребитель груза.

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

Запрещение корреспонденции. Если необходимо по каким-либо при­чинам наложить запрет на перевозку груза из пункта A₁в пунктВ₁,то для этого достаточно вместо реального элемента целевой матрицы, стоящего в клетке А₁В₁, поставить очень большую величину М, которая больше лю­бого наперед заданного числа, имеющегося в данной задаче.

Обязательная поставка. Если из пункта А_i- в обязательном порядке не­обходимо перевезти в пунктBjкакой-то объем груза, то в этом случае ве­личина обязательной поставки вычитается из суммы спроса и суммы пред­ложений и при решении задачи не учитывается. При определении оконча­тельного результата затраты, связанные с обязательным объемом перевозок, прибавляются к полученному оптимальному варианту.

Открытая модельвозникает в случаях, когда отсутствует ка­кая-либо из групп ограничений - спрос или предложение. Это означает, что любой потребитель может взять всю сумму имеющихся у поставщи­ков материалов или любой из поставщиков может удовлетворить спрос всех потребителей данного материала.

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

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