2.3 Модификации транспортной задачи
Если перевозка из некоторого пункта производства в некоторый пункт назначения по той или иной причине невозможна, то в алгоритме решения задачи данное ограничение можно учесть, присвоив соответствующей клетке достаточное большое значение стои-мости.
Точное значение в данном случае неважно, однако оно должно быть больше, чем остальные значения стоимости, указанные в таблице. Таким образом, алгоритм автоматически позволит избежать перевозок через данную клетку.З а д а ч а 2.4
Ниже показано применение алгоритма решения транспортной задачи в решении проблем, связанных с недопустимостью прямых перевозок товаров из пунктов производства в пункты назначения. Рассматривается движение продукта во времени. Пусть в нашем распоряжении имеется график перевозок сроком на 4 месяца, который необходимо выполнить. В таблице 2.27П приведены значения спроса на продукцию и значения производственных мощностей.
2.27П Значения спроса на продукцию и возможные объемы перевозок Месяц Производственные мощности, изделий Спрос, изделий 1 300 300 2 350 275 3 325 400 4 375 300 К началу первого месяца имеется начальный запас изделий объемом 50 шт. Если спрос на изделия в течение месяца не удовлетворяется полностью, то прибыль от услуг по перевозке теряется. Издержки на перевозку составляют 100 у. е. за единицу изделия. Стоимость хранения запасов - 2 у.е. за единицу изделия. Каков оптимальный план перевозок?
Решение.
Данную ситуацию можно формализовать, используя транспортную табл. 2.28П, в которой строками является начальный запас и пополнение запаса за месяц, а столбцы отражают ежемесячный спрос на продукцию. Маршруты (клетки), в которых подразумевается удовлетворение спроса за текущий месяц в следующих месяцах, считаются недопустимыми. В таблице этим клеткам соответствуют клетки с символом «х».
2.28П Данные плана перевозок для месяцев 1 - 4
Стоимость перевозки единицы изделия, у.е. Общее Месяцы предложе ние М1 М2 М3 М4 Запас М1 2 4 6 8 50 100 102 104 106 300 Произв одство М2 х 100 102 104 350 М3 х х 100 102 325 М4 х х х 100 375 Общая потребность 300 275 400 300 Решение этой транспортной задачи производится с помощью обычного алгоритма, позволяющего минимизировать стоимость.