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

Алгоритм нахождения начального плана перевозок методом северо-западного угла

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

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

Клетка с базисным нулем считается базисной (в ней пишется 0), а общее число базисных клеток остается равным .

Пример 6.1.

Дано. Транспортная задача, заданная матрицей перевозок:

Найти начальный план перевозок в транспортной задаче, заданной матрицей перевозок, методом северо-западного угла.

Решение:

Начнем с северо-западного угла, т.е. . Тогда в пункте  потребности удовлетворены и, следовательно,  (в таблице ставится точка). Первый столбец выбывает из рассмотрения.

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

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

Заполним последний элемент, находящийся в северо-западном углу: .

Таким образом, получен начальный план перевозок:      ,

с суммарной стоимостью .

Число базисных клеток, очевидно, составит  .