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

Разберем метод на примере.

Пусть есть 3 пункта отправления

и 4 пункта назначения

Запасы в пунктах отправления:

Потребности:

Занесем данные в таблицу.

Таблица 6.2.
					Запасы


Потребности

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

Таблица 6.3.
				(так как переслали в )

Отметим, что и в таблице 6.3 сумма всех потребностей по-прежнему равна сумме всех запасов. К Таблице 6.3 применим тот же прием и попытаемся удовлетворить потребности пункта .(в таблице 6.3 пункт играет роль первого) запасами пункта . Очевидно, что потребности эти удается удовлетворить лишь частично, так как . При этом потребности сократятся до , а запасы окажутся исчерпаны полностью. В силу этого строку, отвечающую , из таблицы 6.3 можно временно удалить. Получим новую таблицу – таблицу 6.4, в которой имеются уже два пункта отправления и и три пункта назначения .

Таблица 6.4.

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

Вписав их в таблицу 6.2, получим таблицу 6.5.

Таблица 6.5.

Условимся называть те клетки таблицы 6.5, в которые вписаны значения неизвестных, — базисными, а остальные клетки — свободными. Если считать, что значения неизвестных , которые отвечают свободным клеткам, равны нулю, то получившийся набор значений всех неизвестных дает допустимое решение рассматриваемой задачи.

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

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