double arrow

Построения начального опорного плана


Рассмотрим способы построения начального опорного плана. Составить опорный план можно различными способами. Однако для всех способов непременным является требование, чтобы в процессе заполнения распределительной таблицы в каждую загружаемую клетку вписывалась максимально возможная по величине поставка. В таком случае каждый раз будет либо исчерпываться весь запас груза у поставщика (мы будем говорить: "закрывается строка"), либо полностью удовлетворяться спрос потребителя ("закрывается столбец"). Соблюдение этого требования обеспечит заполнение именно m + n – 1 клеток.

Способ "северо-западного угла".Первой загружается клетка (1; 1). Если закрывается строка, то следующей загружается клетка (2; 1); если же закрывается столбец, то следующей загружается клетка (1; 2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу (в зависимости от конкретных данных задачи). Последней будет загружена клетка (т; п). В результате загруженные клетки расположатся вдоль диагонали (1; 1) — (т; п), поэтому способ "северо-западного угла" называют еще диагональным способом.

Существенным недостатком способа "северо-западного угла" является игнорирование при загрузке клеток тарифов , поэтому построенный опорный план обычно оказывается весьма далеким от оптимального.

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

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


Сейчас читают про: