Транспортная задача.
Алгоритм метода северо-западного угла.
Движение с северо-запада на юго-восток. Отдаем в эти клетки максимально-возможную поставку.
С
Потр. Пост. | В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(усл.ден.ед.).