Методы построения начального опорного решения

Построение первоначального плана по способу северо-западного угла

В этом случае не обращают внимания на показатели затрат. Начав заполнение с клетки (1.1) - "северо-западного угла" таблицы, ступенями спускаются вниз до клетки (k, l), вычеркивая либо одну строку, либо один столбец. На последнем шаге вычеркиваются последняя (k -я) строка и последний (l -й) столбец. При практическом заполнении таблицы, вычеркивание строк и столбцов производится лишь мысленно.

Когда осуществляется первоначальное распределение поставок, то не ставится цель получить оптимальное распределение. Достижению этой цели служат последующие этапы решения задачи. Они заключаются в переходах к новым распределениям поставок, пока не будет найдено оптимальное распределение поставок.

Построение первоначального плана по способу минимального элемента

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

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

Этот способ заключается в следующем.

1. Располагаем все клетки таблицы в очередь по мере возрастания тарифов, начиная с минимального.

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

Полученный план будет ациклическим и будет состоять не более чем из k + l -1 компонент. Этот план и принимаем за исходный. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений.