5.3 Поиск оптимального решения методом потенциалов
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 |
После того как построили новую таблицу, необходимо проверить ее, что бы наличие ресурсов совпадала с потребностью (проконтролировать себя, правильно ли осуществлен сдвиг).
Повторяем все расчеты. Опять первый потенциал приравниваем к нулю и начинаем рассчитывать все остальные потенциалы по занятым клеткам.
После того как потенциалы по занятым клеткам рассчитаны, приступаем к расчету значения Lij для свободных клеток:
L12=8-(6+0)=2
L13=6-(3+0)=3
L14=4-(8+0)=-4
L24=3-(8-1)=-4
L31=7
L33=9
С=200*2+100*1+150*5+700*4+550*2+300*6=6950
L14 – перспективная клетка
Сдвиг получился следующий
Новая таблица
Фермы Участки |
В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