13.2.7. Модификации транспортной задачи

НЕДОПУСТИМЫЕ ПЕРЕВОЗКИ

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

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

Таблица 13.22. Значения спроса и производственных мощностей

К началу первого месяца имеется начальный запас изделий объемом 50 шт. Изделия можно производить как для удовлетворения текущего спроса, так и создания запаса для удовлетворения спроса в последующие месяцы. Если спрос на изделия в течение месяца не удовлетворяется полностью, то прибыль от продажи теряется. Издержки производства составляют 100 ф. ст. за единицу изделия. Стоимость хранения запасов равна 2 ф. ст. за единицу изделия. Каков оптимальный план производства?

Решение.

Данную ситуацию можно формализовать, используя транспортную таблицу, в которой строками являются начальный запас и объемы производства изделий в

месяц, а столбцы отражают ежемесячный спрос на продукцию. Маршруты (клетки), в которых подразумевается удовлетворение спроса за текущий месяц в следующих месяцах, считаются недопустимыми. В табл. 13.23 этим клеткам соответствуют бесконечные значения стоимости.

Таблица 13.23. Данные производственного плана для месяцев 1—4 (см. скан)

Решение этой транспортной задачи производится с помощью обычного алгоритма, позволяющего минимизировать стоимость выполнения производственного графика (см. пример 13.8).

ВЫРОЖДЕННОСТЬ

Решение называется вырожденным, если число перевозок в транспортной таблице меньше, чем Данную проблему можно разрешить, проставив в независимые клетки очень маленькие, по сути равные нулю объемы перевозок. Число перевозок увеличивается таким образом до Выявить клетки, которые следует использовать для этой цели, поможет алгоритм метода МОДИ проверки решения на оптимальность.

Пример 13.6. Три торговых склада (X, Y и Z) могут осуществлять поставки 6, 3 и 4 единиц продукта в три магазина и спрос которых равен 4, 5 и

1 единицам соответственно. Значения единичной стоимости транспортировки указаны в приведенной ниже таблице.

Таблица 13.24. Исходная информация (см. скан)

Как следует распределить перевозки, чтобы общая стоимость транспортировки была минимальной?

Решение.

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

Таблица 13.25. Начальное распределение перевозок, полученное методом Вогеля (см. скан)

Значение стоимости транспортировки составит:

Для того, чтобы решение являлось базисным, оно должно включать переменных, тогда как в нашей задаче число перевозок равно лишь 5. Найденное решение является вырожденным. Поступая в соответствии с алгоритмом метода МОДИ, мы должны ввести нулевую перевозку, чтобы использовать в качестве заполненной одну из пустых клеток. Этот прием позволяет получить требуемое число перевозок, равное 6. Затем можно будет рассчитать значения всех компонент и и а следовательно, и теневые цены.

Реализацию алгоритма метода МОДИ мы начнем, используя 5 заполненных клеток, соответствующих начальному распределению перевозок. Дополнительная

нулевая перевозка будет введена только тогда, когда без нее продолжение алгоритма будет невозможно. Обратимся к данным табл. 13.26.

Таблица 13.26. Проверка вырожденного решения на оптимальность — метод МОДИ (см. скан)

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

Нулевую перевозку можно поместить в пустую клеггку столбца или строки и. Какая из этих клеток будет выбрана, значения не имеет. Пусть выбрана клетка Теперь можно завершить алгоритм и найти значения теневых цен для пустых клеток из соотношения Соответствующие величины приведены в табл 13.26. Как видно из таблицы, в двух клетках теневые цены принимают отрицательные значения. Следовательно, полученное распределение перевозок является неоптимальным, и необходимо осуществить их перераспределение, используя при этом клетки или фиктивный). Начнем с клетки поскольку ей соответствует большее по абсолютной величине значение теневой цены. Ступенчатый цикл для клетки и движение объемов перевозок по входящим в него клеткам можно представить в виде табл. 13.27.

Чтобы определить число единиц, которые следует перемещать вдоль построенного цикла, обратимся к клеткам помеченным знаком количество перевозок в которых равно 2 и 0 единицам.

Таблица 13.27. Ступенчатый цикл для клетки (Z.M)

Это означает, что по циклу следует осуществлять перемещение нулевой перевозки таким образом, чтобы клетка (Z, N) снова стала пустой, а клетку (Z, М) предполагается использовать при распределении перевозок, поскольку в нее помещается нулевая перевозка. Остальные перевозки остаются без изменений. При дальнейшей проверке данного распределения на оптимальность выясняется, что значения всех теневых цен положительны. Данное распределение перевозок оптимальное. Это предполагает, что начальное решение, включающее 5 переменных, также оптимально. Обратимся к данным табл. 13.28.

Таблица 13.28. Проверка оптимального решения — метод МОДИ (см. скан)

Такие результаты далеко не всегда имеют место в случае вырожденности решения. В некоторых ситуациях при перераспределении перевозок определенное

количество единиц продукции помещается в клетку с нулевой перевозкой, и тем самым данная клетка вводится в новое распределение перевозок. Это приводит к исчезновению вырожденности решения. Затем, для получения улучшенного распределения перевозок, применяются обычные алгоритмы.

МАКСИМИЗАЦИЯ

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