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

В приведенном способе построения плана не участвовали затраты на перевозку. Учет затрат позволит получить начальный план, более близкий к оптимальному. Первой заполняется клетка с минимальными затратами. Пусть min C_ij = C_kp. Тогда X_kp =min(a_k, b_p). Если при этом закрывается строка

ПО	Потребитель(ПН)	Запасы груза
B1	B2	B3	B4
A1		5	60	35
A2	75	75
A3
Потр-ть

k,то в столбце p ищем клетку с минимальными затратами и определяем значение соответствующей переменной. При закрытии столбца p действуем аналогично в строке k. В общем случае клетка, лежащая в закрытом столбце и/или закрытой строке является закрытой, иначе – открытой. На каждом шаге движение идет либо по столбцу, либо по строке и при этом отыскивается среди открытых клетка с минимальным значением C_ij.

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

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

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