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

Сущность этого метода становится понятной при рассмотрении следующеего примера. Пусть условия транспортной задачи заданы табл. 8.4

Таблица 8.4

Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя B1 за счет запаса поставщика А1 (северо-западный угол). В левый нижний угол клетки А₁B₁ записываем меньший из располагаемых[ объемов min (a₁, b₁)= min (100, 200)=100 ед. После данной операции запасы первого поставщика полностью израсходованы, поэтому остальные клетки первой строки прочеркиваем. Потребности B ₁ остались неудовлетворенными на 200-100 = 100 ед. Сравниваем этот остаток с запасами поставщика А ₂: так как 100 < 250, то 100 ед. записываем в клетку А ₂ B ₁, чем полностью удовлетворяем потребности потребителя B ₁, а оставшиеся клетки в первом столбце прочеркиваем.

У поставщика А ₂ осталось 150 ед.груза. Частично удовлетворяем потребителя B ₂ за счет оставшегося у поставщика А ₂ груза. Для этого сравниваем этот остаток с потребностями потребителя В ₂: 150 < 200, записываем 150 ед. в клетку А ₂ В ₂, так как запасы А ₂ полностью израсходованы, прочеркиваем остальные клетки второй строки. Читателю рекомендуется довести данный процесс до конца и получить табл. 8.4.

На этом построение первоначального опорного плана заканчивается.

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

Проверим, является ли план, построенный в табл. 8.4, опорным. Видим, что, начиная движение от занятой клетки A₁B₁, двигаясь только по занятым клеткам, вернуться в нее, невозможно. Аналогичная ситуация с другими начальными клетками. Следовательно, план является опорным, и в то же время он является невырожденным, поскольку содержит точно m+n -1= 4 + 5-1=8 занятых клеток.

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

Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же клетках:

Z = 100·10+100·2+150·7+50·5+100·3+50·2+50·16+250·13=6950 (ед. стоимости).

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