Правило минимального элемента
В приведенном способе построения плана не участвовали затраты на перевозку. Учет затрат позволит получить начальный план, более близкий к оптимальному. Первой заполняется клетка с минимальными затратами. Пусть min Cij = Ckp. Тогда Xkp =min(ak, bp). Если при этом закрывается строка
k,то в столбце p ищем клетку с минимальными затратами и определяем значение соответствующей переменной. При закрытии столбца p действуем аналогично в строке k. В общем случае клетка, лежащая в закрытом столбце и/или закрытой строке является закрытой, иначе – открытой. На каждом шаге движение идет либо по столбцу, либо по строке и при этом отыскивается среди открытых клетка с минимальным значением Cij.
Пример: Построим начальный план по правилу минимального элемента для задачи из примера 1. Результат в табл. При таком начальном плане L= 665, что меньше чем в примере 1. Однако нельзя утверждать, что для любых данных этот способ дает лучший план. Правило минимального элемента эффективнее в среднем (на множестве задач). В то же время алгоритм реализации этого правила сложнее, чем правила северо-западного угла. Применяется также вариант, в котором на каждом шаге ищется клетка с минимальными затратами среди всех открытых клеток. Такой способ еще сложнее, но в среднем дает планы, более близкие к оптимальным.
|
75 
