Исходная информация

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

Решение.

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

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

ф. ст.

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

Реализацию алгоритма метода МОДИ мы начнем, используя 5 заполненных клеток, соответствующих начальному распределению перевозок. Дополнительная нулевая перевозка будет введена только, когда без нее продолжение алгоритма будет невозможно. Обратимся к таблице 2.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_i). Соответствующие величины приведены в табл. 13.26. Как видно из таблицы, в двух клетках теневые цены принимают отрицательные значения. Следовательно, полученное распределение перевозок является неоптимальным, и необходимо осуществить их перераспределение, используя при этом клетки (Z,M) или (Z, фиктивный). Начнем с клетки (Z,M), поскольку ей соответствует большее по абсолютной величине значение теневой цены. Ступенчатый цикл для клетки (Z,M) и движение объемов перевозок по входящим в него клеткам можно представить в виде табл. 2.27.

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

Таблица 2.27.