Правило «северо-западного угла»

Для составления исходного плана перевозок удобно пользо­ваться правилом «северо-западного угла», которое состоит в сле­дующем.

Будем заполнять, начиная с левого верхнего, услов­но называемого «северо-западным углом», двигаясь далее по строке вправо или по столбцу вниз. Занесем в клетку (1; 1) меньшее из чисел и , т. е. . Если , то и первый столбец «закрыт», т. е. спрос первого потребителя удовлетворен полностью. Это означает, что для всех остальных клеток первого столбца количество груза для .

Двигаясь дальше по первой строке таблицы, записываем в со­седнюю клетку (1, 2) меньшее из чисел и , т. е. .

Если , то аналогично «закрывается» пер­вая строка, т. е. , для . Переходим к заполнению соседней клетки (2; 1), в которую заносим .

Заполнив вторую клетку (1; 2) или (2; 1), переходим к за­полнению следующей третьей клетки по второй строке либо по второму столбцу. Будем продолжать этот процесс до тех пор, по­ка на каком-то этапе не исчерпаются ресурсы и потребности . Последняя заполненная клетка окажется лежащей в последнем -м столбце и в последней -й строке.