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

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

Пример. Найти опорный план транспортной задачи из предыдущего примера методом минимального элемента.

Решение. Исходные данные задачи запишем в виде табл. 2.16. В каждой строке и каждом столбце отмечаем галочкой клетки с наименьшей стоимостью перевозки. После чего проставляем перевозки: вначале заполняя клетки с двумя галками, потом — с одной, а потом — оставшиеся, при этом не должно нарушаться условие допустимости плана.

Таблица 2.16

Пункты отправления	Пункты назначения	Запасы
В1	B2	В3	В4	В5
А1
A2
Аз
Потребности

Минимальный тариф, равный 1, находится в клетке для переменной х₂₃. Положим х₂₃= 120, запишем это значение в соответствующую клетку табл. 4.6 и исключим временно из рассмотрения столбец B₃. А для пункта A₂ запас будем считать равным 180 - 120=60 ед.

Кроме того, минимальный тариф, равный 1, находится в клетке для переменной х₂₅. Положим х₂₅⁼ 60, запишем это значение в соответствующую клетку табл. 2.17 и исключим временно из рассмотрения столбец B₃.

Таблица 2.17

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

В оставшейся части таблицы с двумя строками А₁ и А₃ и четырьмя столбцами В₁, В₂ В₄ и В₅ клетка с наименьшим значением тарифа С_ij =2 находится на пересечении строки А₃ и столбца В₅, строки А₁ и столбцов В₁ и В₄. Не нарушая допустимости плана, положим x₃₅ = 40, x₁₁ = 60, х₁₄ = 80 и внесем эти значения в соответствующие клетки табл. 2.18.

Таблица 2.18

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

Теперь исключим из рассмотрения строки A₁ и A₂ и столбцы B₁, B₃, B₅, т. к. по ним выполнены условия допустимости. После этого аналогично заполняем оставшуюся часть таблицы (табл. 2.19).

Таблица 2.19

Пункты отправления	Пункты назначения	Запасы
В1	В2	В3	В4	В5
А1
А2
А3
Потребности

В результате получим опорный план

При данном плане перевозок общая стоимость перевозок составляет

F= 2·60 + 2·80 + 1·120 + 1·60 + 7·70 + 7·50+2·40= 1380.

Дата добавления: 2014-01-07