Алгоритм метода потенциалов может быть представлен в виде последовательности ИТЕРАЦИЙ и ШАГОВ, обеспечивающих переход от одного плана перевозок к другому (т.е. от одного базисного решения к другому), до получения оптимального решения. Схема расчетов на каждой ИТЕРАЦИЙ остается одной и той же. Меняются лишь входные данные. Каждая из ИТЕРАЦИЙ состоит из четырех ШАГОВ, имеющих определенный вычислительный смысл.
ИТЕРАЦИЯ 1
ШАГ 1. Выписываем исходное допустимое базисное решение (первый план перевозок) и вычисляем соответствующее ему значение целевой функции.
150 50 0 0
Х3 = 0 140 10 0
0 0 90 120
Z3=150* 3+50* 7+0* 2+0* 9+0* 8+140*5+10*7+0* 8+0* 5+0* 6+90* 11+120* 4=3040
Проверим план на вырожденность, т.е. проверим выполнение условия: количество занятых клеток должно быть равно величине (m+n-1).
Выполним расчеты: 3+4-1= 6
В построенном нами плане также шесть занятых клеток, т.е. план невырожденный. На любой ИТЕРАЦИИ при решении данной задачи количество занятых клеток должно быть равно шести.
Примечание 2. Если план окажется вырожденным, нужно в одну из пустых клеток поместить нулевую постановку и считать эту клетку занятой. При этом данная клетка не должна приводить к образованию замкнутого контура из занятых клеток.
ШАГ 2. Проверяем полученный план на оптимальность.
Для доказательства оптимальности полученного плана разработан ряд специальных методов. Одним из наиболее широко распространенных точных методов доказательства является гак называемый метод потенциалов. В его основе лежит следующая теорема, доказываемая в теории I линейного программирования: "Если для некоторого план X = (Хi,j) перевозок траспортной задачи можно подобрать систему из (m+ n) произвольных чисел U1, U2,…… Um и V1, V2,..., Vn; такую, что для всех занятых клеток выполняется соотношение:
|
С i j = U i + V j,
а для всех пустых клеток – соотношение:
G i j U i + V j,
при решении задачи на минимум (или соотношение С ij U i + V j при решении задачи на максимум), то план X будет оптимальным".
Числа Ui, Vj называются, соответственно, потенциалами строк (поставщиков) и столбцов (потребителей).
Таким образом, ШАГ 2 сводится к тому, чтобы, во-первых, рассчитать потенциалы строк Ui (i=1, 2,3) и потенциалы столбцов Vj (j = 1,2,3,4) по следующему правилу: "для всех занятых клеток сумма потенциалов соответствующее строки и столбца должна равняться тарифу клетки", т.е.
Ui + Vj = С i j (2)
И, во-вторых, проверить выполнение признака оптимальности плана, т.е. проверить, будет ли тариф каждой пустой клетки больше или равен сумме потенциалов соответствующей строки и столбца, т.е.
С i j Ui+Vj (3)
при решении задачи на минимум (или С i j Ui+Vj при решении задачи максимум).
Проверим оптимальность исходного плана перевозок.
Для этого сначала рассчитаем потенциалы строк и столбцов. Поскольку количество занятых клеток равно величине.
(m+n-1)=3+4-1=6
а сумма строк и столбцов составляет (m+ п) = 3 + 4 = 7, т.е. на единицу больше количества занятых клеток, то можно построить лишь шесть потенциалов. В связи с этим некоторому потенциалу (строки или столбца) придается любое произвольное значение. Для простоты расчетов обычно потенциалу первой строки придают нулевое значение. Значения вычислительных потенциалов строк и столбцов будем заносить, соответственно, в клетки столбца и в клетки строки Vj транспортной схемы I (табл. 4).
|
Итак, потенциал первой строки равен нулю, т.е. Ui = 0. Тариф клетки (1.1) (занятая клетка первой строки) равен 3. На основании формулы (2) определим потенциал первого столбца:
Ui+Vi=Сij, т.е. 0+Vi=3, откуда Vi=3.
Аналогично рассчитаем все остальные потенциалы:
потенциал второго столбца U1+V2=С12, т.е. О+V2=7, откуда V2=7;
потенциал второй строки U2+V2=С22, т.е. V2+7=5, откуда V2= -2;
Потенциал третьего столбца U2+V3=С23, т.е. –2+V3=7, откуда V3=9;
потенциал третьей строки U3+V3=С33, т.е.V3+9=11, откуда V3=2;
потенциал четвертого столбца U3+V4 = С34, т.е. 2 + V4 = 4, откуда V4 =2.
Таблица 4 -Транспортная схема 1
Пасеки | Точки | ![]() | Ui | |||
![]() ![]() ![]() | 150 3 | -50 -7 | +Х2 | 9 | ||
![]() | 8 | +140 5 | 10 - 7 | 50 -7 | -2 | |
III | 5 | 6 | 90 11 | 120 4 | ||
![]() | ||||||
Vj | ![]() |
После расчета потенциалов проверим выполнение признака оптимальности плана. Для этого будем просматривать по очереди все пустые клетки слева направо, начиная с первой пустой клетки (1, 3). По тем клеткам, где не выполняется соотношение (3), результат перечеркнем:
С13 = 2
(0+9) - С24 = 8
(-2+3) +
С14 = 9 (0+2) + С31 = 5
(-2+3) +
С21 = 8
(-2+3) + С32 = 6
(2+7) -
Вывод: Так как не для всех пустых клеток выполняется соотношение (3), план, представленный в транспортной таблице 1, не оптимальный. Его можно улучшить.
Шаг 3. Выполняем процесс улучшения плана.
Определим, из какой точки на какую пасеку должна быть произведена перепоставка и ее величину (т.е. какая из прежних базисных неизвестных должна быть выведена из базиса).
Клетки, в которых не выполняется условие (3), назовем «плохими». Из всех «плохих» клеток выбираем только одну по такому принципу: при решении задачи на min-клетку с наименьшим тарифом, при решении задачи на max-клетку с наибольшим тарифом. Все рассуждения о «плохой» клетке будут относиться к этой клетке В нашей задаче две «плохие»клетки (1,3) и (3,2). Меньший тариф у клетки (1,3) (он равен С13=2). Это и будет окончательно «плохая» клетка, в которую поставим знак «Х» (см. транспортную схему 1).
|
Процесс улучшения плана осуществляется в соответствии с так называемым правилом «замкнутого маршрута». По которому происходит перераспределение постановок и улучшение ранее построенного плана.
Сформулируем три правила построения «замкнутого маршрута»:
- маршрут замкнут, т.е. начинается с «плохой» клетки и в ней же заканчивается;
- переход от одной клетки маршрута к другой осуществляется только по горизонтали и вертикали;
- в углах поворота маршрута должны находиться занятые клетки, причем их знаки («+»или «-») чередуются по контуру маршрута, начиная с «плохой» клетки, которой придается знак «+».
Для каждой пустой клетки существует только один «замкнутый маршрут», удовлетворяющий выше сформулированным правилам
Примечание 3. Возможные конфигурации "замкнутых маршрутов" представлены на рисунке 1.
В нашей задаче будет построен следующий "замкнутый маршрут":
(1,3) (1,2)
(2,2)
(2,3)
(1,3)
Среди всех клеток со знаком «-» выбираем ту, в которой величина поставки минимальная (как при решении задачи на max, так и при решении задачи на min). В нашей задаче две клетки со знаком «-»: клетка (1,2) с поставкой 50 и клетка (2,3) с поставкой 10. Выбираем клетку (2, 3) с меньшей постановкой, равной 10. Эту величину (10) перераспределим по контуру маршрута таким образом; в клетках, имеющих знак «+» число 10 прибавим к имеющейся величине поставки, а в клетках со знаком "-" вычтем из имеющейся величины поставки. Число 10 запишем в «плохую» клетку, а клетка (2,3) станет пустой. В клетках, не затронутых «замкнутым маршрутом», величины поставок останутся прежними.
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() | Х+ | - | Х+ | +Х | - | |||||
![]() | ||||||||||
![]() ![]() ![]() ![]() | - | + | - | + | ||||||
![]() ![]() ![]() ![]() | - | + | - | + | - |
Рисунок 1- Конфигураций "замкнутых маршрутов"
ШАГ 4. Строим новый план перевозок.
С намеченными на ШАГЕ 3 изменениями новый план перевозок занесем в транспортную схему 2 (табл. 5).
Таблица 5 -Транспортная схема 2
Пасеки | Точки | ![]() | Ui | |||
![]() ![]() ![]() ![]() ![]() | 150 - 3 | 40 7 | + 10 2 | 9 | ||
II | 8 | 150 5 | 7 | 8 | -2 | |
![]() ![]() | Х+ 5 | 6 | -90 11 | 120 4 | ||
![]() | ||||||
Vj | -5 | ![]() |
ИТЕРАЦИЯ 2
ШАГ 1. Выписываем очередное допустимое базисное решение (второй план перевозок) и вычисляем соответствующее ему значение целевой функции.
150 40 10 0
Х2 = 0 150 0 0
0 0 90 120
Z2= 150 3+40
7+10
2+0
9+0
8+150
5+0
7+0
8+0
5+0
6+90
11+120
4 = 2970
Количество заполненных клеток 6. План невырожденный.
ШАГ 2. Проверяем полученный план перевозок на оптимальность.
Для этого во-повых, рассчитаем потенциалы строк и столбцов, учитывая соотношение (2); и запишем их значения в транспортную схему 2. Во-вторых, проверим выполнение признака оптимальности полученного плана перевозок, т.е. проверим выполнение соотношения (3) для всех пустых клеток:
С14 = 9 (0 + (-5)) + С24 = 8
(-2 +(-5)) +
С21 = 8
(-2 + 3) + С31 = 5
(9 + 3) -
С23 = 7
(-2 + 2) + C32 = 6
(9 + 7) -
Вывод: т.к. не для всех пустых клеток выполняется соотношение (3), план, представленный в транспортной схеме 2 не оптимальный. Его можно улучшить.
Шаг 3. Выполняем процесс улучшения плана.
«Плохая» клетка (3.1). Строим «замкнутый маршрут»:
(3,1) (1,1)
(1,3)
(3,3)
(3,1).
Из двух клеток со знаком «-» (1,1)и(3,3) клетка (3,3) имеет меньшую постановку, равную 90. Эту величину перераспределим по контуру маршрута.
Шаг 4. Строим новый план перевозок.
С намеченными на ШАГЕ 3 изменениями новый план перевозок занесем в транспортную схему 3 (табл. 6).
Таблица 6 -Транспортная схема 3
Пасеки | Точки | ![]() | Ui | |||
![]() ![]() ![]() ![]() | 60 + 3 | 40 7 | 100 2 | 9 | ||
II | 8 | 150 5 | 7 | 8 | -2 | |
![]() | 90 - 5 | Х+ 6 | 11 | 120 4 | ||
![]() | ||||||
Vj | ![]() |
ИТЕРАЦИЯ 3
Шаг 1. Выписываем очередное допустимое базисное решение (новый план перевозок) и вычисляем соответствующее ему значение целевой функции.
60 40 100 0
Х3 = 0 150 0 0
90 0 90 120
Z3= 60*3 +40*7 +100*2 +0*9 +0*8 +150*5 +0*7 +0*8 +90*5 +0*6 +0*11 +120*4 = 2340
Количество заполненных клеток 6. План невырожденный.
ШАГ 2. Проверяем полученный план перевозок на оптимальность.
Снова рассчитаем потенциалы строк и столбцов. Их значения запишем в транспортную схему3. Проверим выполнение соотношения (3) для всех пустых клеток:
С14 = 9 (0 + 2) + С24 = 8
(-2 +2) +
С21 = 8
(-2 + 3) + С32 = 6
(2+ 7) -
С13 = 7 (-2 + 2) + C33 = 11
(2 + 2) +
Вывод: Так как не для всех пустых клеток выполняется соотношение
(3), план, представленный в транспортной схеме 3, не оптимальный.
Его можно улучшить.
ШАГ 3. Выполняем процесс улучшения плана.
"Плохая" клетка (3,2).Строим «замкнутый маршрут":
(3,2) (3,1)
(1,1)
(1,2)
(3,2). '.
Перераспределим по контуру маршрута число 40.
ШАГ 4. Строим новый план перевозок.
С намеченными на ШАГЕ 3 изменениями новый план перевозок за
несем а транспортную схему 4 (табл.7).
Таблица 7 - Транспортная схема 4
Пасеки | Точки | ![]() | Ui | |||
I | 100 3 | 7 | 100 2 | 9 | ||
II | 8 | 150 5 | 7 | 8 | ||
III | 50 5 | 40 6 | 11 | 120 4 | ||
![]() | ||||||
Vj | ![]() |
ИТЕРАЦИЯ 4
Шаг 1. Выписываем очередное допустимое базисное решение (новый план перевозок) и вычисляем соответствующее ему значение целевой функции.
100 0 100 0
Х4 = 0 150 0 0
50 40 0 120
Z4= 100*3 +0*7 +100*2+ 0*9+ 0*8+ 150*5+ 0*7+ 0*8+ 50*5+ 40*6+ 0*11+ 120*4= 2220
Количество заполненных клеток 6. План невырожденный.
ШАГ 2. Проверяем полученный план перевозок на оптимальность.
Снова рассчитаем потенциалы строк и столбцов. Их значения запишем в транспортную схему4. Проверим выполнение соотношения (3) для всех пустых клеток:
С12 = 7 (0 + 4) + С23 = 7
(1 +2) +
С14 = 9 (0 + 2) + С24 = 8
(1+ 2) +
С21 = 7 (1 + 3) + C33= 11
(2 + 2) +
Вывод: Так как для всех пустых клеток выполняется соотношение
(3), план, представленный в транспортной схеме 4, оптимальный.