Правило минимального элемента

В приведенном способе построения плана не участвовали затраты на перевозку. Следует ожидать, что учет затрат позволит получить начальный план, более близкий к оптимальному. Этим и отличается расматриваемое правило.

Первой заполняется клетка с минимальными затратами. Пусть min C_ij = C_kp. Тогда X_kp =min(a_k, b_p). Если при этом закрывается строка k, то в столбце p ищем клетку с минимальными затратами и определяем значение соответствующей переменной согласно (5.13). При закрытии столбца p действуем аналогично в строке k. В общем случае клетка, лежащая в закрытом столбце и/или закрытой строке является закрытой, иначе – открытой. На каждом шаге движение идет либо по столбцу, либо по строке и при этом отыскивается среди открытых клетка с минимальным значением C_ij.

Пример 2. Построим начальный план по правилу минимального элемента для задачи из примера 1. Результат представлен в табл. 3.

Таблица 3

Поставщик	Потребитель	Запасы груза
B1	B2	B3	B4
A1		5	60	35
A2	75	75
A3
Потребность в грузе

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

Применяется также вариант, в котором на каждом шаге ищется клетка с минимальными затратами среди всех открытых клеток. Такой способ еще сложнее, но в среднем дает планы, более близкие к оптимальным.

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