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

Будем строить допустимое решение задачи, начиная с заполнения левой верхней клетки («северо-западный угол») исходной таблицы. Примем соответствующий объем перевозок 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.