double arrow

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

Транспортная задача.

Алгоритм метода северо-западного угла.

Движение с северо-запада на юго-восток. Отдаем в эти клетки максимально-возможную поставку.

С

Потр. Пост. В1 В2 В3 В4 Запасы
А1     - -  
А2 -        
А3 - - -    
Потребности          

Ю

Fmax=1*20+2*40+6*70+5*40+2*10+4*100=1140(усл.ден.ед.)

Метод северо-западного угла имеет существенный недостаток. Он построен без учета знаний коэффициентов затрат задачи. Существует модификация этого метода, лишенная этого недостатка: на каждом шаге максимально-возможную поставку следует отдавать не в северо-западную клетку, а в клетку с наименьшим коэффициентом затрат. Этот метод называется методом наименьших затрат или методом минимального элемента.

Алгоритм метода наименьших затрат (минимального элемента)

Находим в таблице поставок клетки с наименьшим коэффициентом затрат. Если их несколько (равны коэффициенты затрат), то сравниваем максимально-возможные поставки и отдаем поставку в ту клетку, где максимально-возможная поставка больше. Если же и максимально-возможные поставки равны, то поставку отдаем в любую из них. Далее клетки заполняются в последовательности прямо зависящей от возрастания тарифа.

Потр. Пост. В1 В2 В3 В4 Запасы
А1 -   - -  
А2   - -    
А3 -        
Потребности          

Fmax=2*60+1*20+2*100+3*50+7*40+4*10=810 (усл.ден.ед.)

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

Перед распределением сырья между предприятиями и поставщиками нужно провести ряд расчетов.

В каждой строке и столбце таблицы нужно найти два наименьших тарифа, определить разность между ними и записать эту разность в специально отведенные для этого клетки справа и внизу от таблицы. После этого среди разностей двух минимальных тарифов по строкам и столбцам нужно найти наибольшую. Следовательно, нужно первоначально заполнить одну из клеток этого столбца или строки. Какую клетку заполнять первой?

Выбирают клетку с наименьшим тарифом, если тарифы одинаковые, выбирают клетку с максимально-возможной поставкой. Если потребность в сырье удовлетворена полностью, то в этом случае под разностью двух минимальных тарифов ставят знак «-».

Затем вновь повторяется поиск двух наименьших тарифов, находятся разности между ними и результат записывается в отведенные для этого клетки. Следует отметить, что тариф в клетке уже заполненной исключается из внимания и расчеты проводятся по оставшимся тарифам. Если в заполняемых клетках справа и внизу от таблицы появляются одинаковые разности, то предпочтение при заполнении отдают той клетке строки или столбца, где стоит наименьший тариф, а при их равенстве- максимально-возможной поставке. Расчеты производят до тех пор, пока в отведенных клетках не будут стоять «-».

Потр. Пост. В1 В2 В3 В4 Запасы Дополнительные клетки
А1       -             - -
А2 - -                   -
А3 -   - -         - - - -
Потр                        
Дополнит. клетки          
-      
-     -
-     -
- -   -
- -   -
- - - -

Fmax=1*20+2*10+5*30+5*10+2*110+3*100=760(усл.ден.ед.).


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: