Транспортная задача.
Алгоритм метода северо-западного угла.
Движение с северо-запада на юго-восток. Отдаем в эти клетки максимально-возможную поставку.
С
| Потр. Пост. | В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(усл.ден.ед.).
Задача для самостоятельного решения.
С трех складов, расположенных в Химках, на Сходне и в Ховрино, необходимо доставить в пять магазинов сахарный песок в соответствии с заявкой каждого магазина. Объемы запасов песка, имеющегося на складах, объемы заявок магазинов и тарифы на поставку одной тонны груза со складов в магазины даны даны в транспортных таблицах по вариантам:
Решить задачу тремя методами (методом северо-западного угла, методом наименьших затрат, методом аппроксимации Фогеля).
Задачи для самостоятельного решения:
Задача 1
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 2
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 3
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 4
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 5
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
|
|
Задача 6
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 7
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 8
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 9
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 10
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 11
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 12
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 13
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 14
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 15
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 16
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 17
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 18
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 19
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 20
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 21
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 22
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 23
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 24
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |
Задача 25
| Магазины Склады | №1 | №2 | №3 | №4 | Объем запаса |
| Химки | |||||
| Сходня | |||||
| Ховрино | |||||
| Заявки |