Реализация алгоритма метода потенциалов

 

Алгоритм метода потенциалов может быть представлен в виде последовательности ИТЕРАЦИЙ и ШАГОВ, обеспечивающих переход от одного плана перевозок к другому (т.е. от одного базисного решения к другому), до получения оптимального решения. Схема расчетов на каждой ИТЕРАЦИЙ остается одной и той же. Меняются лишь входные данные. Каждая из ИТЕРАЦИЙ состоит из четырех ШАГОВ, имеющих определенный вычислительный смысл.

ИТЕРАЦИЯ 1

ШАГ 1. Выписываем исходное допустимое базисное решение (первый план перевозок) и вычисляем соответствующее ему значение целевой функции.

150 50 0 0

Х₃ = 0 140 10 0

0 0 90 120

Z₃=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) произвольных чисел U₁, U₂,…… U_m и V₁, V₂,..., V_n; такую, что для всех занятых клеток выполняется соотношение:

С _{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.

Аналогично рассчитаем все остальные потенциалы:
потенциал второго столбца U₁+V₂=С_12, т.е. О+V₂=7, откуда V₂=7;
потенциал второй строки U₂+V₂=С_22, т.е. V₂+7=5, откуда V₂= -2;

Потенциал третьего столбца U₂+V₃=С_23, т.е. –2+V₃=7, откуда V₃=9;
потенциал третьей строки U₃+V₃=С_33, т.е.V₃+9=11, откуда V₃=2;
потенциал четвертого столбца U₃+V₄ = С₃₄, т.е. 2 + V₄ = 4, откуда V₄ =2.

Таблица 4 -Транспортная схема 1

Пасеки	Точки	(запасы)	Ui
I	150 3	-50 -7	+Х2	9
II	8	+140 5	10 - 7	50 -7		-2
III	5	6	90 11	120 4
(потребности)
Vj					=3040

 

После расчета потенциалов проверим выполнение признака опти­мальности плана. Для этого будем просматривать по очереди все пустые клетки слева направо, начиная с первой пустой клетки (1, 3). По тем клет­кам, где не выполняется соотношение (3), результат перечеркнем:

С₁₃ = 2 (0+9) - С₂₄ = 8 (-2+3) +

С₁₄ = 9 (0+2) + С₃₁ = 5 (-2+3) +

С₂₁ = 8 (-2+3) + С₃₂ = 6 (2+7) -

Вывод: Так как не для всех пустых клеток выполняется соотношение (3), план, представленный в транспортной таблице 1, не оптимальный. Его можно улучшить.

Шаг 3. Выполняем процесс улучшения плана.

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

Клетки, в которых не выполняется условие (3), назовем «плохими». Из всех «плохих» клеток выбираем только одну по такому принципу: при решении задачи на min-клетку с наименьшим тарифом, при решении задачи на max-клетку с наибольшим тарифом. Все рассуждения о «плохой» клетке будут относиться к этой клетке В нашей задаче две «плохие»клетки (1,3) и (3,2). Меньший тариф у клетки (1,3) (он равен С₁₃=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
I	150 - 3	40 7	+ 10 2	9
II	8	150 5	7	8		-2
III	Х+ 5	6	-90 11	120 4
(потребности)
Vj				-5	=2970

ИТЕРАЦИЯ 2

ШАГ 1. Выписываем очередное допустимое базисное решение (второй план перевозок) и вычисляем соответствующее ему значение целевой функции.

150 40 10 0

Х₂ = 0 150 0 0

0 0 90 120

Z₂= 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) для всех пустых клеток:

С₁₄ = 9 (0 + (-5)) + С₂₄ = 8 (-2 +(-5)) +

С₂₁ = 8 (-2 + 3) + С₃₁ = 5 (9 + 3) -

С₂₃ = 7 (-2 + 2) + C₃₂ = 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
I	60 + 3	40 7	100 2	9
II	8	150 5	7	8		-2
III	90 - 5	Х+ 6	11	120 4
(потребности)
Vj					=2340

 

ИТЕРАЦИЯ 3

Шаг 1. Выписываем очередное допустимое базисное решение (новый план перевозок) и вычисляем соответствующее ему значение целевой функции.

60 40 100 0

Х₃ = 0 150 0 0

90 0 90 120

Z₃= 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) для всех пустых клеток:

С₁₄ = 9 (0 + 2) + С₂₄ = 8 (-2 +2) +

С₂₁ = 8 (-2 + 3) + С₃₂ = 6 (2+ 7) -

С₁₃ = 7 (-2 + 2) + C₃₃ = 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					=2220

 

ИТЕРАЦИЯ 4

Шаг 1. Выписываем очередное допустимое базисное решение (новый план перевозок) и вычисляем соответствующее ему значение целевой функции.

100 0 100 0

Х₄ = 0 150 0 0

50 40 0 120

Z₄= 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) для всех пустых клеток:

С₁₂ = 7 (0 + 4) + С₂₃ = 7 (1 +2) +

С₁₄ = 9 (0 + 2) + С₂₄ = 8 (1+ 2) +

С₂₁ = 7 (1 + 3) + C₃₃= 11 (2 + 2) +

Вывод: Так как для всех пустых клеток выполняется соотношение
(3), план, представленный в транспортной схеме 4, оптимальный.