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

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

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

4×300 + 0×300 + 3×200 + 2×100+2×400 = 28 00 евро

Для того, чтобы решение являлось базисным, оно должно включать (3 + 4—1) = 6 переменных, тогда как в нашей задаче число перевозок равно лишь 5. Найденное решение является вырожденным. Поступая в соответствии с алгоритмом метода МОДИ, мы должны ввести нулевую перевозку, чтобы использовать в качестве заполненной одну из пустых клеток. Этот прием позволяет получить требуемое число перевозок, равное 6. Затем можно будет рассчитать значения всех компонент u и v, a следовательно, и теневые цены.

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

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

Заполненные клетки используются для расчета соответствующих компонент по строкам и по столбцам из соотношения: с_ij = u_i + v_j. при условии, что u_i = 0. Значения v₂, v₄, u₂ и v_з можно найти, не испытывая никаких затруднений, однако, значения u₃ и v₁ рассчитать нельзя. Для этого необходимо иметь дополнительную заполненную клетку.

Нулевую перевозку можно поместить в пустую клетку столбца v₁ или строки u₃. Какая из этих клеток будет выбрана, значения не имеет. Пусть выбрана клетка (Z, N). Теперь молено завершить алгоритм и найти значения теневых цен для пустых клеток из соотношения s_ij = с_ij — (u_i + v_j ). Соответствующие величины приведены в табл 4.26. Как видно из таблицы, в двух клетках теневые цены принимают отрицательные значения. Следовательно, полученное распределение перевозок является неоптимальным, и необходимо осуществить их перераспределение, используя при этом клетки (Z,M) или (Z, фиктивный). Начнем с клетки (Z,M), поскольку ей соответствует большее по абсолютной величине значение теневой цены. Ступенчатый цикл для клетки (Z,M) и движение объемов перевозок по входящим в него клеткам можно представить в виде табл. 4.27.

Чтобы определить число единиц, которые следует перемещать вдоль построенного цикла, обратимся к клеткам (Y,M) и (Z,N), помеченным знаком "—", количество перевозок в которых равно 2 и 0 единицам.

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

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

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

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