А) Метод северо-западного угла (диагональный метод)

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

Заполнение таблицы начинают с клетки (1; 1), при этом . Далее смещаются или по строке вправо или по столбцу вниз и заканчивается заполнение в клетке неизвестного x_mn (a_m; b_n), т.е. заполнение идет как бы по диагонали таблицы.

 

Пример 2. Рассмотрим пример составления начального опорного плана методом северо-западного угла.

Запасы груза у поставщиков а = (90; 100; 90); потребности потребителей b = (70; 60; 80; 70); тарифы перевозок . Построить методом северо-западного угла начальный опорный план для ТЗ и найти стоимость перевозок.

Решение. Задача закрытая, так как .

Строим распределительную таблицу и находим в клетке (1; 1) количество груза х₁₁ = min(90; 70) = 70. Спрос 1-го потребителя удовлетворен полностью.

По 1-му столбцу не перемещаемся, так как спрос 1-го потребителя удовлетворен. Перемещаемся по 1-й строке в клетку (1; 2):

х₁₂ = min(а₁-х₁₁; b₂) = min(90-70; 60) = min(20; 60) = 20.

Груз от 1-го поставщика вывезен полностью (70+20=90).По 1-й строке не перемещаемся, переходим по 2-му столбцу в клетку (2; 2):

х₂₂ = min(100; b₂-х₁₂) = min(100; 60-20) = min (100; 40) = 40.

Спрос 2-го потребителя удовлетворен (20+40=60). Переходим в клетку (2; 3):

х₂₃ = min(а₂-х₂₂; b₃) = min(100-40; 80) = min(60; 80) = 60.

У 2-го поставщика груз выбран полностью (40+60=100). Переходим в клетку (3; 3):

х₃₃ = min(а₃; b₃-х₂₃) = min(90; 80-60) = min(90; 20) = 20.

Спрос 3-го потребителя удовлетворен (60+20=80). Переходим в клетку (3; 4):

х₃₄ = min(а₃-х₃₄; b₄) = min(90-20; 70) = min(70; 70) = 70.

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

Ранг матрицы системы и число заполненных клеток 6 (= r). Следовательно, полученный план – невырожденный.

Для подсчета стоимости перевозок количество груза в каждой заполненной клетке умножим на соответствующий тариф и результаты сложим:

.

Как правило, исходный опорный план, полученный данным методом, оказывается весьма далеким от оптимального, так как при его определении игнорируются величины затрат c_ij. Поэтому в дальнейших расчетах для определения оптимального плана требуется много итераций (шагов). Число итераций можно сократить, если исходный план строить по более рациональному методу «минимального элемента».