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

Будем рассматривать задачу ( ) — ( ). Представим ее в виде таблицы:

Таблица 2.7.2

	A	B	C	D	Запас
		100
		700
		100	200	4
Потребность

Название данного метода свидетельствует о том, что мы стартуем с клетки, расположенной в верхнем левом углу и движемся по направлению "юго-восток". В клетки вносится количество перевозимого груза. При этом клетки, в которых имеется ненулевое количество груза, называются занятыми, а остальные — свободными. Вы, наверное, уже догадались, что количество, записанное в занятую клетку, есть не что иное, как значение соответствующего х_ij.

Рассмотрим клетку 1А и занесем туда максимально возможное количество груза. Это количество определяется величинами запаса на складе 1 и потребностями завода А. Очевидно, что это количество определяется наименьшим числом. Это количество будет равно 400. Тогда все потребности завода А удовлетворены, но на складе 1 осталось 500 — 400 = 100 т. Переходим к ближайшей незанятой клетке. Это не может быть клетка 2А, т. к. потребности потребителя А уже удовлетворены, в то время, как на складе 1 запасы еще есть. Т. е. мы попадаем в клетку 1В и загружаем ее опять максимально возможным количеством. Оно равно 100 (такой запас остался на складе 1). Таким образом, запасы на складе 1 исчерпаны, но заводу В еще необходимо 900 — 100 = 800 т. Снова от клетки 1В переходим к ближайшей клетке 2 В. Максимально возможно ее загрузить количеством 700, т. к это запас со склада2. Потребности завода В опять не удовлетворены, т. к. 800 — 700 = 100. Снова переходим к следующей клетке ЗВ. Туда заносится величина 100 для того, чтобы удовлетворить потребности завода В. На складе З осталось еще 800 — 100 = 700. Снова переходим на соседнюю клетку (ЗС) и заносим туда 200 (потребности завода С). Наконец, в клетку 3D заносим 500. В результате все потребности удовлетворены, а запа­сы исчерпаны.

Подсчитаем количество занятых клеток. Их шесть. Число линейно-независимых уравнений системы тоже шесть. Согласно нашей терми­нологии получается первоначальный опорный план, в котором шесть переменных являются базисными, остальные шесть равных нулю — небазисные. Согласно этому решению:

.

Остальные x = 0. Можно подсчитать общую стоимость перевозок при данном плане:

Конечно, очень проблематично считать, что найденный план яв­ляется оптимальным. Достоинством метода северо-западного угла,(по­жалуй, единственным) является его простота.