Метод минимального элемента

В методе северо-западного угла при построении исходного плана совершенно не учитываются транспортные расходы. Это, как правило, приводит к увеличению количества шагов (приближений).

В методе же минимального элемента при построении базисного решения такой недостаток устранен. Поэтому полученный в этом методе план перевозок является более приближенным к оптимальному решению. Суть метода заключается в следующем.

Определение объема перевозок х_ij. начинается с клетки, которая имеет минимальную стоимость перевозок с_ij.; если таких клеточек больше одной, то избирается первая по порядку. Как и в методе северо-западного угла x_ij = min(a_i,b_j.), соответствующая строка или столбец исключаются из последующего рассмотрения, а потребность потребителя или наличие груза у поставщика уменьшается на выбранную величину. Если для выбранной клетки с минимальной стоимостью a_i, = b_j., то исключается строка и столбец. Затем в оставленной таблице выполняют аналогичные операции, начиная с клетки с минимальной стоимостью перевозок. На последнем шаге остаются одна строка иодин столбец. После заполнения клетки, которая стоит на их пересечении, процесс завершается.

Проверка полученного плана на вырожденность проводится так же, как и в методе юго-западного угла.

Пример 3.9. Для той же задачи найти исходный план и сделать его в таблице:

Таблица

Шаг 1. Переменной х₂₁ отвечает клетка с минимальной стоимостью перевозок с₂₁= 4д.е. Поэтому x₂₁=min(14,10)=10. Столбец 1 вычеркивается, а наличие груза у второго поставщика уменьшается на 10 ед.

Шаг 2. В оставшейся части таблицы минимальные стоимости перевозок с₁₃ =с₂₃= 5д.е. отвечают клеточке с объемом поставок x₁₃ и х₂₃. Выбираем первую по порядку клетку: x_l3=min (11,7)=7. Столбец 3 ис­ключается из таблицы, а наличие груза у первого поставщика (строка 1) уменьшается на 7 д.е.

Шаг 3. В уменьшенной части таблицы х₂₂ имеет минимальную стоимость перевозок с₂₂= 5д.е.; x₂₂= min(4,8)=4. Строка 2 исключается из таблицы, а потребность второго потребителя (столбец 2) уменьшается на 4 ед.

Шаг 4. Поскольку в таблице осталась одна строка (строка 1) и один столбец (столбец 1) — это последний шаг процесса, х₂₂= 4ед.

Количество заполненных клеток таблицы— 4 :т+п- 1=2+3-1=4. Таким образом, получен план невырожденный. Значение базисных переменных: x_I2= 4; х₂₃= 7; x₂₁=10; х₂₂= 4. Другие переменные — небазисные, и их значения равняются нулю (в клетках нулине проставляются). Транспортные расходы: Z=6*4+5*7+4*10+5*4=119 д.е.

Получен лучший с точки зрения критерия оптимальностей план (Z=119 д.е.). Однако из этого не следует, чтометод минимального элемента всегда имеет лучший опорный план. Существуют задачи, где метод северо-западного угла может дать лучший план. Поэтому рациональность приведенных методов построения опорного плана можно оценить только в среднем.