Методы нахождения первоначального распределения поставок

Все существующие методы нахождения опорных планов отличаются только способом выбора клеткидля заполнения. Само заполнение происходит одинаково независимо от используемого метода. Следует помнить, что перед нахождением опорного плана транспортная задача должна быть сбалансирована (приведена к закрытой модели).

Ø Метод северо-западного угла

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

Для того чтобы заполнить клетку , необходимо сравнить текущий запас товара в рассматриваемой i -й строке с текущей потребностью в рассматриваемом j -м столбце .

Если существующий запас позволяет перевезти всю потребность, то

· в клетку в качестве перевозки вписывается значение потребности ;

· j -й столбец вычеркивается, поскольку его потребность уже исчерпана;

· от существующего запаса в i -й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. .

Если существующий запас не позволяет перевезти всю потребность, то

· в клетку в качестве перевозки вписывается значение запаса ;

· i -я строка вычеркивается, поскольку ее запас уже исчерпан;

· от существующей потребности в j -й строке отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е. ).

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы. Если на некотором шаге вычеркиваются одновременно строка и столбец, то либо по строке, либо по столбцу рядом необходимо записать «0»-поставку и при дальнейших расчетах считать эту клетку условно заполненной.

Ø Метод минимальных затрат (минимального элемента)

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