Метод аппроксимации Фогеля

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

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

3) Из всех различий Метод аппроксимации Фогеля, приобретенных по строчкам и столбцам избираем самую большую. Клеточка с минимальным расстоянием (при решении задач на минимум) расположенная в строке либо столбце, имеющем самую большую разницу, загружается наибольшим количеством груза. Если окажется несколько схожих различий, имеющих наибольшее значение, то в соответственных им строчках и столбцах загружают седловую Метод аппроксимации Фогеля точку. Седловой точкой именуют клеточку, расстояние которой имеет меньшее значение (при решении задач на минимум) из всех расстояний ее строчки и столбца при наличии независящих седловых точек, т. е. расположенных в различных строчках и столбцах таблицы их загружают сразу.

В согласовании с выше обозначенным методом производится загрузка клеток с учетом имеющихся ограничений Метод аппроксимации Фогеля по спросу и предложению. Оставшиеся различия столбцов либо строк перечеркиваются и ставиться символ «К», т. е. окончание проверки, значащей, что перераспределение груза закончено. Определяются новые различия для всех строк и столбцов таблицы, при всем этом загруженные и свободные клеточки, расположенные в строчках либо столбцах, в каких Метод аппроксимации Фогеля исчерпаны ограничения по спросу либо предложению во внимание не принимаются. Если вновь приобретенная разница отличается от приобретенной ранее, то последняя зачеркивается и пишутся новые. Действие повторяется до того времени, пока весь груз не будет распределен. Последнюю одну либо две клеточки загружают без определения разностей, приобретенный по способу аппроксимации Фогеля план перевозки проверяется Метод аппроксимации Фогеля на оптимальность по способу Моди, если приобретенное рассредотачивание груза окажется не хорошим, то предстоящее решение делается по методу способа Моди.

Таблица № 6

ГО ГП вывоз столбец разности
Б1 Б2 Б3 Б4 Б5 Б6 Б7
А1 8-4=4 4-4=0 16-4=12 12-4=18 7-4=3 5-4=1 К
X X X X X
А2 4-4=0 8-4=4 12-4=8 11-4=7 5-4=1 7-4=3 К
X X X X
А3 14-4=10 5-4=1 4-4=0 12-4=8 16-4=12 К
X Метод аппроксимации Фогеля X X X
А4 5-4=1 8-4=4 9-4=5 11-4=7 12-4=8 4-4=0 К
X X X X
ввоз
строчка разности 5-4=1 8-4=4 14-4=10 4-4=0 К 5-4=1 8-4=4 4-4=0 К 16-4=12 12-4=8 9-4=5 4-4=0 К 11-8=3 12-8=4 8-8=0 К 9-5=4 11-5=6 14-5=9 5-5=0 К 7-5=2 12-5=7 5-5=0 К 5-4=1 7-4=3 16-4=12 4-4=0 К

Транспортная работа согласно приобретенному допустимому решению –

L(x) =50*4+10*5+80*4+0*5+4*100+8*30+5*40+5*200+4*20+5*20=1690 т*км


Способ Моди

Для оценки оптимальности решения потенциалы подбираются последующим образом: потенциал первой строчки берется равным 0, по расстоянию загруженных клеток подбирается потенциал для Метод аппроксимации Фогеля других строчек и столбцов таблицы. Расстояние каждой загруженной клеточки должно быть равно сумме потенциалов строчки и столбца, в какой находится данная клеточка.

Находим потенциалы для всех строчек и столбцов таблицы. Если число загруженных клеток будет меньше, чем условие m+n-1, то потенциал для неких строк и столбцов Метод аппроксимации Фогеля будет нереально отыскать, недостающее количество клеток загружаем нулями. Загружать нулями, следует клеточки, которые лежат на скрещении строк и столбцов, не имеющих потенциалов, со строчками и столбцами для которых потенциалы уже определены. При всем этом более целенаправлено выбирать из этих клеток такие, в каких имеются меньшие расстояния. После того как потенциалы Метод аппроксимации Фогеля всех строк и столбцов определены, определяется их сумма для каждой свободной клеточки, сумма потенциалов указывается в верхнем левом углу свободной клеточки. При решении задач на минимум сбалансированный вариант получится в этом случае, когда в каждой свободной клеточке сумма потенциалов для этой клеточке не превосходит обозначенного в ней расстояния.

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


Таблица № 7

ГО ГП вывоз,т потенциал
Б1 Б2 Б3 Б4 Б5 Б6 Б7
А1 7 5
А2 5 3 -2
А3 -2
А4 -1
ввоз, т
потенциал

Условие m+n-1 соблюдается- 7+4-1=10

L(x)= 50*4+10*5+100*4+80*4+30*8+40*5+20*5+0*5+20*5+20*4=1690 т*км

Найдено другое наилучшее решение, потому что в каждой свободной клеточке сумма потенциалов не превосходит Метод аппроксимации Фогеля обозначенного в ней расстояния.


metafora.html
metafori-v-rechi-predstavitelej-sekt.html
metaforicheskih-associativnih-kart-mak.html