Поиск допустимого ациклического плана методом северо-западного угла

Работаем на макете (табл. 8). Невзирая на тарифы, начинаем составление плана с заполнения левой верхней клетки (1,1) (с северо-западного угла).

Смотрим на запасы a₁ и потребности b₁. Если a₁ < b₁, то в клетку (1,1) вписываем a₁ (т. е. отдаем пункту назначения весь запас груза из первого пункта отправления — случай в таб­лице). Если b₁ < a₁, то в клетку (1,1) записываем b₁ т. е. покрываем всю потребность первого пункта назначения за счет первого пункта отправления.

Перепишем баланс после первой операции (изменятся и по­требности, и запасы). В первой строке остальные клетки можно прочеркнуть, так как весь груз пошел в первый пункт.

Начинаем опять с северо-западного угла. Удов­летворяем оставшуюся потребность первого пункта назначения, доставив туда (b₁ — a₁) единиц груза из второго пункта отправления. Если потребность первого пункта удовлетворена пол­ностью, остальные клетки в первом столбце прочеркиваем. Переписываем баланс после второй операции.

Таблица 8

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

Пункты назначения Пункты отправления	B1	B2	B3	B4	Запасы груза
A1	а1	–	–	–	a1
А2	b1-a1				a2	a2	a2-b1+a1
А3	–				a3	a3	a3
А4	–				a4	a4	a4
Потребности в грузе	b1	b2	b3	b4
	b1- a1	b2	b3	b4
	b2	b3	b4

Снова начинаем с северо-западного угла, удовлетворяем по­требность второго пункта назначения и т. д., пока справа и сни­зу не будут стоять нули, т. е. весь груз распределен и потреб­ности удовлетворены. Полученный внутри таблицы план будет допустимым. Его и берем в качестве исходного.

Пример. Пусть условие задачи приведено в табл. 9.

Таблица 9

Условие задачи

Пункты назначения Пункты отправления	B1	B2	B3	B4	Запасы груза
A1
А2
A3
Потребности в грузе

Для составления первоначального плана обращаемся к клет­ке (1, 1). Запасы для нее равны 90, потребности—110. Мень­шее из этих чисел считаем перевозкой по маршруту (1, 1):

.

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

Таблица 10

Первый шаг метода северо-западного угла

Пункты назначения Пункты отправления	B1	B2	B3	B4	Запасы груза
A1		–	–	–
А2
A3
Потребности в грузе

Затем берем клетку (2, 1)— северо-западный угол оставшей­ся части таблицы. Для нее запасы равны 100, а потребности — только 20. Меньшее число будет перевозкой по маршруту (2, 1):

.

Вносим это число в клетку, прочеркиваем последнюю клетку первого столбца (потребности первого пункта удовлетворены), пересчитываем оставшиеся запасы и потребности и записываем их в новые столбец и строку (табл. 11).

Таблица 11

Второй шаг метода северо-западного угла

Пункты назначения Пункты отправления	B1	B2	B3	B4	Запасы груза
A1		–	–	–
А2
A3	–
Потребности в грузе

Снова находим северо-западный угол незаполненной части таблицы. Им будет клетка (2, 2). Запасы для нее равны 80, потребности — 100. Принимаем

,

вносим это число в таблицу, производим пересчет запасов и по­требностей и, так как во втором пункте запасы исчерпаны, две клетки второй строки прочеркиваем (табл. 12).

Таблица 12

Третий шаг метода северо-западного угла

Пункты назн. Пункты отправ.	B1	B2	B3	B4	Запасы груза
A1		–	–	–
А2			–	–
A3	–
Потребности в грузе

Продолжая те же рассуждения для клеток (3, 2), (3, 3), (3, 4), придем в итоге к табл. 13, в дополнительной части кото­рой будут стоять одни нули (с записью последнего числа 40 нуль ставим и в третьей строке, и в четвертом столбце). Это свидетельствует о том, что все запасы исчерпаны, потребности удовлетворены, исходный план составлен.

Таблица 13

Заключительный шаг метода северо-западного угла

Пункты назн. Пункты отправ.	B1	B2	B3	B4	Запасы груза
A1		–	–	–
А2			–	–
A3	–
Потребности в грузе

Практически после получения табл. 12 следовало сравнить за­пасы, сосредоточенные в оставшемся третьем пункте (они рав­ны 140), с потребностями пунктов назначения (20, 80 и 40) и просто вписать последние числа в соответствующие клетки.

При некотором навыке можно вообще обходиться без дополни­тельной части таблицы, фиксируя нужные изменения в уме.

План, построенный способом северо­-западного угла обладает двумя свойствами:

1. Число положительных компонент полученного плана не превосходит (m + n – 1).

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