Методы оптимальных р ...

5.3 Поиск оптимального решения методом потенциалов

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

а) Цикл начинается и заканчивается в перспективной клетке

б) Цикл делает повороты в занятых клетках и только под прямым углом.

г) Число вершин цикла всегда четное.

В рассматриваемом примере перспективной является клетка 23 (строка под номером 2 и столбец под номером 3) Строим цикл в таблице1

Выносим его за пределы таблицы. Проставляем значения вершин цикла.

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

Затем делаем сдвиг по циклу.

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

Получаем следующий (в нашем случае прямоугольник)

Фермы Участки		В1	В2	В3	В4	Наличие сена на участках
		k1 =2	k2 =6	k3 =3	k4 =8
А1	р1= 0	2 200	8	6	4	200
А2	р2=-1	1 100	5 150	2 550	3	800
А3	р2=-2	7	4 700	10	6 300	1000
Потребность ферм в сене		300	850	550	300	2000

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

Повторяем все расчеты. Опять первый потенциал приравниваем к нулю и начинаем рассчитывать все остальные потенциалы по занятым клеткам.

После того как потенциалы по занятым клеткам рассчитаны, приступаем к расчету значения L_ij для свободных клеток:

L₁₂=8-(6+0)=2

L₁₃=6-(3+0)=3

L₁₄=4-(8+0)=-4

L₂₄=3-(8-1)=-4

L₃₁=7

L₃₃=9

С=200*2+100*1+150*5+700*4+550*2+300*6=6950

L₁₄ – перспективная клетка

Сдвиг получился следующий

Новая таблица

Фермы Участки		В1	В2	В3	В4	Наличие сена на участках
		k1 =2	k2 =2	k3 =3	k4 =4
А1	р1= 0	2 50	8	6	4 150	200
А2	р2=-1	1 250	5	2 550	3	800
А3	р2=2	7	4 850	10	6 150	1000
Потребность ферм в сене		300	850	550	300	2000

Повторяем все расчеты.

L12=8-2=6

L13=6-3=3

L22=5-1=4

L24=3-(4-1)=0

L31=7-4=3

L33=10-5=5

C=50*2+250*1+850*4+550*2+150*4+150*6=6350