3.2. Метод ПОТЕНЦИАЛОВ
Метод потенциалов позволяет, исходя из некоторого опорного плана, построить за конечное число итераций решение Т-задачи.
Метод потенциалов впервые предложили Л. В. Канторович и М. К. Гавурин в 1949 г. [18; 59]. Позже аналогичный метод разработал Г. Данциг, исходя из общих идей ЛП.
Общая схема метода такова. В данном начальном опорном плане перевозок каждому пункту ставят в соответствие некоторое число, называемое его предварительным потенциалом. Предварительные потенциалы выбирают так, чтобы их разность для любой пары пунктов Ai i Bj, связанных основной коммуникацией, была равна cij. Если окажется, что разность предварительных потенциалов для всех других коммуникаций не превосходит cij, то данный план перевозок - оптимальное решение задачи. В противном случае указывают способ улучшения текущего плана Т-задачи.
Описание алгоритма метода потенциалов. Алгоритм складывается из предварительного этапа и конечного числа однотипных итераций.
На предварительном этапе строят начальный опорный план и составляют матрицу 
где 
- предварительные потенциалы пунктов
.
Предварительный этап. С помощью известного метода (например северо-западного угла или минимального элемента) определяют начальный опорный план Х0 и вычисляют предварительные потенциалы 
.
Вычисление предварительных потенциалов производят так. По найденному опорному плану Х0 строят схему перевозок Т-задачи из основных коммуникаций плана. Напомним, что основные коммуникации 
плана Х0 = 
- это те, которым отвечают базисные компоненты плана, т.е. коммуникации для которых 
. Далее образуют следующие множества: J1 - множество индексов всех пунктов Bj, которые связаны с пунктом А1 основными коммуникациями; І1 - множество индексов тех пунктов Аі, которые связаны основными коммуникациями с множеством J1; J2 - множество пунктов Bj, которые связаны основными коммуникациями с множеством І1 и т.д. Образование таких множеств Ік продолжаем до тех пор, пока не получим пустое множество.
Поскольку на выполнение условий оптимальности оказывают влияние лишь разности 
(см. теорему 3.2), то за начало отсчета (нуль) можно принять потенциал любого из пунктов.
Полагаем для определенности 
и вычислим систему потенциалов относительно А1. Тогда 
где j 
J1. Затем по значениям 
определяем потенциалы пунктов 
. Аналогично вычисляем потенциалы 
(для и 
.) и т.д. После того как потенциалы всех пунктов найдены, строим матрицу
Очевидно, позиции матрицы С1, отвечающие базисным элементам плана Х0, будут заняты нулями. Если матрица С1 не содержит отрицательных элементов, то Х0 - оптимальный план. В противном случае Х0 - неоптимальный план, который может быть улучшен. Тогда переходим к выполнению однотипных итераций.
(k+1)-я итерация. Каждая итерация, кроме первой, где отсутствует первый этап, состоит из двух этапов. Предположим, что уже проведено k итераций (k=1,2,.),в результате которых получен план Хk и вспомогательная матрицу Сk. Цель (k+1)-й итерации - построение матрицы Сk+1, а также либо установление оптимальности плана Хk, либо нахождение более экономичного плана Xk+1.
Первый этап. Вычисляют матрицу Сk+1. Преобразвание матрицы Сk в матрицу Сk+1 состоит в следующем. Выбирают наибольший по модулю отрицательный элемент Сk. Пусть это элемент 
. Тогда вычеркивают (или выделяют) строку 
, в которой он содержится. Просматривают эту строку и отыскивают множество существенных его элементов. Хk -существенными элементами называют те элементы 
=0, которые отвечают базисным элементам плана Хk т.е. для которых 
. Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают вычеркнутые столбцы и ищут в них новые существенные элементы, которые лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы имеются, то вычеркивают строки, в которых они содержатся. Процесс выделения продолжают до тех пор, пока очередное множество новых существенных элементов не окажется пустым. Поскольку каждые строка и столбец не могут быть выделены дважды, то весь процесс заканчивается не более чем за l =m+ n - 1 шагов. Далее строят матрицу Сk+1. Для этого величину 
прибавляют ко всем элементам выделенных строк и вычитают из элементов всех выделенных столбцов матрицы Сk. При этом все существенные элементы матрицы Сk остаются равными нулю, а кроме того, в нуль превращается и элемент 
.
Если все элементы матрицы Сk+1 окажутся неотрицательными, то Xk - оптимальный план, и на этом процесс заканчивается. В противном случае переходят ко второму этапу.
Второй этап. Цель этого этапа - построить более экономичный план Хk+1. Выбирают наибольший по модулю отрицательный элемент матрицы Сk+1. Пусть это элемент 
. Строят цепочку из положительных элементов плана, которая замыкается на 
. После того, как цепочка построена, в ней находят минимальный нечетный по порядку следования элемент:
Прибавляют 
ко всем четным элементам (по порядку следования) цепочки и к элементу 
и вычитают из всех нечетных элементов. Остальные элементы Хk оставляют без изменения.
Новый план Хk+1 построен. Он является базисным, так как число его ненулевых элементов не изменилось.
Пусть Lk - транспортные издержки, отвечающие плану Хk. Тогда новое значение целевой функции, отвечающее плану Xk+1, находят по соотношению
. (3.2.1)
Так как 
и 
, то 
. Поэтому Хk+1 - улучшенный опорный план.
Затем производят аналогично (k+2)-ю итерацию.
Пример 3.2. Решить методом потенциалов Т-задачу, условия которой заданы в табл. 3.5
Проверим условие баланса:
,
поэтому задача разрешима.
В процессе решения этой задачи воспользуемся следующими обозначениями: Хk - существенные элементы матрицы Сk+1 обозначим черточкой сверху; при вычислении матрицы Сk+1 помещаем (-
) справа от выделенных строк матрицы Сk, а 
- под выделенными столбцами; минимальный элемент матрицы Сk обводим рамкой; элементы цепочки в плане Хk отмечаем знаком *.
Предварительный этап. С помощью метода северо-западного угла определяем исходный опорный план Х0.
Табл. 3.5
|
|
|
|
||||||||
|
Х0 |
5 |
6 |
0 |
0 |
11 |
6 |
0 |
0 |
0 |
|
|
0 |
3 |
8 |
0 |
11 |
11 |
8 |
0 |
0 |
||
|
0 |
0 |
1 |
7 |
8 |
8 |
8 |
8 |
7 |
||
|
|
5 |
9 |
9 |
7 |
||||||
|
|
0 |
9 |
9 |
7 |
||||||
|
|
0 |
3 |
9 |
7 |
||||||
|
|
0 |
1 |
7 |
|||||||
|
|
0 |
7 |
||||||||
|
|
0 |
|||||||||
Значение целевой функции 
.
Находим предварительные потенциалы задачи. Для этого строим схему перевозок по основным коммуникациям плана Х0 (рис 3.5).
 |
|
 |
|||||||||||||||||||
|
|
|
||||||||||||||||||||
 |
|
|
|||||||||||||||||||
|
|
|
||||||||||||||||||||
Рис. 3.5
Наносим на основные коммуникации соответствующие велечины транспортных издержек.
Предварительные потенциалы вычисляем в таком порядке. Пусть 
. Рассмотрев коммуникацию А1В1, находим 
. Используя коммуникацию А1В2 ,определяем 
.
Аналогично 
Теперь вычисляем элементы матрицы С1=
, например 
и т.д.
Заметим, что существенные элементы С1 (т.е. те, которые отвечают элементам 
) равны нулю, поэтому их можно заполнить без вычислений.
Первая итерация. Здесь первый этап отсутствует, так как матрица С1 уже определена.
На втором этапе в матрице С1 находим наибольший по модулю отрицательный элемент:
С14 = -7 = 
. Переходим к плану Х0 и строим цепочку из его базисных элементов, которая замыкается на x14.
Элементы цепочки будем отмечать знаком *. Нечетные по порядку следования элементы цепочки х*12 = 6, х*23 = 8, х*34 = 7. Определив минимальный среди них элемент 
, прибавим q1 ко всем четным элементам (по порядку следования) цепочки, а также к х14 и вычтем из всех нечетных элементов цепочки.
Таким образом получаем план Х1, который также является базисным, так как число ненулевых элементов в нем не изменилось и из них нельзя построить цикл. Получим
|
|
|
|
|
|
|
|||||||||
|
|
6* |
0 |
0* |
5 |
0 |
0 |
6 |
|||||||
|
X0 = |
|
|
3* |
8* |
0 |
|
X1 = |
0 |
9 |
2 |
0 |
|||
|
0 |
0 |
1* |
7* |
q1 = 6 |
0 |
0 |
7 |
1 |
||||||
|
|
Целевая функция L1 = L0 + 
= 150 - 7*6 = 108.
Вторая итерация. Первый этап заключается в построении матрицы С2 по С1. В матрице С1 чертой сверху отметим Х1 = существенные элементы (нули). Вычеркиваем в С1 первую строку, содержащую наибольший по модулю отрицательный элемент С14 = 
. Просматриваем эту строку и находим в ней существенный нуль (то есть 0), принадлежащий первому столбцу. Поэтому вычеркиваем также первый столбец и просматриваем, нет ли в нем еще существенных нулей. Поскольку таковых нет, процесс вычеркивания заканчивается. Далее, из вычеркнутой строки вычтем (т.е. прибавим 7), а к вычеркнутому столбцу прибавим 
(т.е. вычтем 7).
Получим матрицу С2. Так как С2 содержит отрицательные элементы, то план Х2 необходимо улучшить.
|
|
|
|
|
|
||||||||||
|
|
|
0 |
-1 |
-7 |
+7 |
0 |
7 |
3 |
0 |
|||||
|
С1 = |
-1 |
|
|
3 |
|
С2 = |
-8 |
0 |
0 |
3 |
||||
|
7 |
3 |
|
|
0 |
3 |
0 |
0 |
|||||||
|
-7 |
На втором этапе находим в матрице С2 наибольший по модулю отрицательный элемент С21 = 
, отыскиваем в плане Х1 соответствующий ему элемент x21 и строим цепочку из базисных элементов этого плана, которая замыкается на x21. Его нечетные элементы по порядку следования: 
Выбрав 
прибавим 
ко всем четным элементам цепочки, а также к x21 и вычтем из всех нечетных элементов цепочки.
Получим новый улучшенный план:
|
|
|
|
|
q2 = 1 |
|
|
||||||||
|
|
0 |
0 |
6+ |
4 |
0 |
0 |
7 |
|||||||
|
X1 = |
|
|
9 |
2- |
0 |
|
X2 = |
1 |
9 |
1 |
0 |
|||
|
0 |
0 |
7+ |
1- |
0 |
0 |
8 |
0 |
|||||||
|
|
Целевая функция 
= 108 - 8 =100.
Последующие итерации проводим аналогично.
Третья итерация. Первый этап.
|
|
|
|
|
|
||||||||||
|
|
7 |
3 |
|
0 |
-1 |
-5 |
0 |
|||||||
|
|
-8 |
|
|
3 |
|
С3 = |
0 |
0 |
0 |
11 |
||||
|
|
0 |
3 |
|
0 |
+8 |
8 |
3 |
0 |
8 |
|||||
|
-8 |
-8 |
Второй этап.
|
|
|
|
|
q3 = 1 |
|
|
||||||||
|
|
0 |
0+ |
7 |
3 |
0 |
1 |
7 |
|||||||
|
X2 = |
|
1* |
9 |
1* |
0 |
|
X3 = |
2 |
9 |
0 |
0 |
|||
|
0 |
0 |
8* |
0 |
0 |
0 |
8 |
0 |
|||||||
Четвертая итерация. Первый этап.
|
|
|
|
|
|||||||||||
|
|
|
-1 |
-5 |
|
+5 |
0 |
-1 |
0 |
0 |
|||||
|
|
|
|
0 |
11 |
|
С4 = |
0 |
0 |
5 |
11 |
||||
|
8 |
3 |
|
8 |
3 |
-2 |
0 |
3 |
|||||||
|
-5 |
-5 |
-5 |
Второй этап.
|
|
|
|
|
|
|
|||||||||
|
|
0 |
1+ |
7 |
0 |
0 |
4 |
7 |
|||||||
|
X3 = |
|
|
9- |
0 |
0 |
|
X4 = |
5 |
6 |
0 |
0 |
|||
|
0 |
0+ |
8- |
0 |
q4 = 3 |
0 |
3 |
5 |
0 |
||||||
|
|
Пятая итерация. Первый этап.
|
|
|
|
|
|
||||||||||
|
|
0 |
-1 |
|
|
+2 |
2 |
1 |
0 |
0 |
|||||
|
С4 = |
|
|
5 |
11 |
|
С5 = |
0 |
0 |
3 |
9 |
||||
|
|
3 |
-2 |
0 |
8 |
+2 |
5 |
0 |
0 |
3 |
|||||
|
-2 |
-2 |
Все элементы матрицы С5 
. Следовательно, х1 - оптимальный план перевозок. Ему соответствует значение L4 = 89.
Связь метода потенциалов с симплекс - методом.
Пусть 
- некоторый базисный план Т-задачи. Множество, состоящее из базисных векторов Pij этого плана, которые отвечают его основным коммуникациям, обозначим через 
. Напомним, что состоит из (m + n - 1) векторов.
На первом этапе метода потенциалов вычисляют предварительные потенциалы 
и 
, которые удовлетворяют условиям 
. Величина 
имеет смысл симплекс - разности. Предположим, что
для всех Pij 
. Это означает, что при введении в базис любого из векторов Pij уменьшить значения L(Xk) нельзя, а поэтому план Xk - оптимальный. Если же для некоторого вектора 
величина 
, то при введении этого вектора в базис можно уменьшить значение целевой функции L(Х).
Переход к новому базису, который включает вектор , связан с построением цепочки, которая замыкается на элементе 
. Чтобы определить, какой вектор выводится из базиса, разлагают по векторам старого базиса. Далее отыскивают
(3.2.2)
где 
- базисный элемент плана Хk при векторе 
, выводимом из базиса; 
- коэффициент разложения вектора 
при векторе .
Для Т-задачи всегда 
. При этом 
, если элемент 
занимает нечетную позицию в цепочке, которая замыкается на элементе , и 
, если он занимает четную позицию. Новые базисные значения переменных в общем случае симплекс-метода определяется по формуле
(3.2.3)
Поскольку 
, формулы (3.2.2) и (3.2.3) применительно к Т-задаче можно представить следующим правилом: перевозки, запланированные по нечетным (четным) позициям цепочки, уменьшаются (увеличиваются) на величину 
, перевозка между 
и 
, а остальные перевозки сохраняют свои значения (где - минимальный нечетный по порядку следования элемент цепочки, которая соединяет пункты и ).
Таким образом, метод потенциалов является частным случаем симплекс-метода, учитывающим специфику Т-задачи.
Решение транспортной задачи
при вырожденном опорном плане
Опорный план называется вырожденным, если число его ненулевых перевозок k меньше ранга матрицы ограничений. В процессе построения начального плана или при его улучшении очередной план может оказаться вырожденным.
Рассмотрим два случая.
1. Вырожденный план является начальным Х0 . Тогда выбирают некоторые нулевые элементы матрицы Х0 в качестве базисных так, чтобы при этом не нарушалось условие базисного плана. Число этих элементов равняется 
. Далее данные элементы заменяют на 
(где 
- произвольное, бесконечно малое число) и рассматривают их как обычные базисные элементы плана. Задачу решают как невырожденную, а в последнем оптимальном плане Хk вместо пишут нули.
2. Вырожденный план получается при построении плана Хk+1 на базе Хk, если цепочка в плане Хk содержит не менее двух минимальных нечетных элементов. В таком случае в матрице Хk+1 полагают равным нулю только один из этих элементов, а остальные заменяют на , и далее решают задачу как невырожденную. Если на k-м шаге 
, то при переходе от Хk к Хk+1 значение целевой функции не изменяется, а в базис вводится элемент , для которого перевозка станет равной .
Пример 3.3. Решим Т-задачу со следующими условиями (см. Табл. 3.6)
Проверим условие баланса 
Предварительный этап. Методом минимального элемента строим начальный базисный план Х0 (Табл. 3.7)
Таблица 3.6
|
C = |
ai bj |
4 |
6 |
8 |
6 |
|
6 |
2(5) |
2(4) |
3(6) |
4(11) |
|
|
8 |
6(12) |
4(10) |
3(9) |
1(3) |
|
|
10 |
1(1) |
2(6) |
2(7) |
1(2) |
Так как m + n - 1 = 6; k = 4, то план х0 - вырожденный; l = m+ n -1 -k = 2.
Два нулевых элемента Х0 делаем базисными так, чтобы не нарушить условие опорности. Выберем в качестве базисных элементов 
, 
и положим их равными e.
|
|
|
|||||||||
|
|
|
|
|||||||
Рис 3.6.
Для вычисления предварительных потенциалов выберем начальный пункт А1 и допустим, что 
. Потенциалы всех остальных пунктов вычисляем по формулам
, 
Для проверки оптимальности плана х0 строим матрицу С1, элементы которой вычисляем по соотношению
Так как в матрице С1 элемент С23 = - 3 < 0, то план Х0 - неоптимальный.
Первая итерация. Второй этап.
|
|
|
|
|
|
|
|||||||||
|
e* |
6* |
0 |
0 |
e |
6 |
0 |
0 |
|||||||
|
X0 = |
|
|
e* |
8 |
0+ |
|
X1 = |
0 |
0 |
6 |
e |
|||
|
4 |
0 |
0 |
6* |
q1 = e |
4 |
0 |
0 |
6 |
||||||
|
|
В результате построения Х1 в базис вводим
. План Х1 является вырожденным (в цепочке есть два минимальных элемента). Поэтому один из этих элементов, например 
, в плане Х1 заменяем на e.
Вторая итерация. Первый этап.
|
|
|
|
|
|||||||||||
|
|
|
0 |
2 |
2 |
0 |
0 |
-1 |
2 |
||||||
|
|
2 |
0 |
|
-3 |
|
С2 = |
5 |
3 |
0 |
0 |
||||
|
0 |
1 |
2 |
0 |
0 |
1 |
-1 |
0 |
|||||||
|
-3 |
Второй этап.
|
|
|
|
|
|
||||||||||
|
e |
6 |
0 |
0 |
e |
6 |
0 |
0 |
|||||||
|
X1 = |
|
0 |
0 |
8* |
e* |
X2 = |
0 |
0 |
2 |
6 |
||||
|
4 |
0 |
0+ |
6* |
q3 =min{8, 6}= 6 |
4 |
0 |
6 |
0 |
||||||
|
|
Третья итерация. Первый этап.
|
|
|
|
|
|
||||||||||
|
|
|
|
-1 |
2 |
+1 |
0 |
0 |
0 |
3 |
|||||
|
С2 = |
5 |
3 |
|
|
|
С2 = |
4 |
2 |
0 |
0 |
||||
|
|
|
1 |
-1 |
0 |
+1 |
0 |
1 |
0 |
1 |
|||||
|
-1 |
-1 |
Так как в матрице С3 нет отрицательных элементов, план Х2 - оптимальный.
