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

Будем строить допустимое решение задачи, начиная с заполнения левой верхней клетки («северо-западный угол») исходной таблицы. Примем соответствующий объем перевозок x ₁₁ = min (a ₁, b ₁), т. е. максимальному значению, допускаемому ограничениями на спрос и объем предложений. Если a ₁> b ₁, то потребности первого потребителя полностью удовлетворены, и он может быть исключен из дальнейшего рассмотрения, а ресурсы первого поставщика равны a ₁ – b ₁. Если a ₁< b ₁, то первый поставщик полностью использовал свои ресурсы и в дальнейшем его можно не учитывать, а потребности первого потребителя считать равными b ₁ – a ₁. Если a ₁ = b ₁, то можно исключить и потребителя, и поставщика, но договоримся в этом случае исключать поставщика, а потребности первого потребителя считать равными нулю.

После установления объема перевозок по маршруту (1, 1) мы получаем задачу, в которой суммарное число поставщиков и потребителей на единицу меньше, чем в исходной задаче. Соответствующая таблица для нее получается вычеркиванием первого столбца или первой строки, фиксируя этим, что остальные переменные вычеркнутого столбца (строки) полагаются равными нулю. Продолжая этот процесс, мы придем к допустимому решению, т. к. .

Пример 2.12. Рассмотрим закрытую транспортную задачу с тремя поставщиками и четырьмя потребителями. Количество груза, имеющееся у каждого поставщика и требующееся каждому потребителю, а также соответствующие стоимости перевозки единицы груза (тариф) приведены в таблице 2.8.

Таблица 2.8

Потребители	1-й	2-й	3-й	4-й
Поставщики
1-й
2-й
3-й

По плану X₀, представленному на рис. 2.10, спрос первого потребителя полностью удовлетворен за счет первого поставщика, т. е. x ₁₁ = 200, и, следовательно, x ₂₁ = 0, x ₃₁ = 0. Оставшиеся у первого поставщика 50 ед. груза направляются второму потребителю, т. е. x ₁₂ = 50, и у этого поставщика оказывается вывезенным весь груз, следовательно, x ₁₃ = 0, x ₁₄ = 0. Недостающие второму потребителю 250 ед. груза вывозятся от второго поставщика, т. е. x ₂₂ = 250, и, следовательно, x ₃₂ = 0. Оставшиеся у второго поставщика 100 ед. направляются третьему потребителю, т. е. x ₂₃ = 100, и, следовательно, x ₂₄ = 0. Недостающие 250 ед. третий потребитель получает от третьего поставщика, т. е. x ₃₃ = 250. И, наконец, остаток в 200 ед. третий поставщик направляет четвертому потребителю, т. е. x ₃₄ = 200. Таким образом, весь груз оказался вывезенным у поставщиков и доставлен в нужных количествах потребителям.

Рис. 2.10

Стоимость перевозок по плану X₀ составляет

f(X₀) = 2× 200+4× 50 + 3× 250 + 6× 100+ 4× 250 + 5× 200 = 3950.