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

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

Пример 1. У поставщиков А₁, А₂, А₃ сосредоточено соответственно 20, 200 и 240 единиц некоторого однородного груза, который необходимо доставить потребителям В₁, В₂, В₃, В₄ в количестве 60, 130, 120 и 150 единиц. Стоимость перевозок единицы груза от поставщиков к потребителям задается матрицей: .

Элемент в 1 - й строке и 3-м столбце равен 8, то есть стоимость перевозки единицы груза от поставщика А₁ к потребителю В₃ равна 8, и т.д.

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

Суммарная мощность поставщиков равна: .

Суммарный спрос потребителей равен:

Это – закрытая модель. Запишем данные в виде таблицы 2.1.

Таблица 2.1 – Данные для расчета

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

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

Северо-западный угол таблицы – это ее левый верхний угол, то есть клетка в 1-й строке и 1-м столбце – клетка (1,1). Поэтому рассмотрим 1-го поставщика и 1-го потребителя. У поставщика А₁ есть 20 единиц груза, а потребителю В₁ нужно 60 единиц. Находим минимум из этих дух чисел:

Клетка (1,1) перечеркивается по диагонали сплошной чертой (______),

в правом нижнем углу пишется найденный минимум 20. Это означает, что А₁ должен поставить потребителю В₁ 20 единиц груза. Такие клетки в дальнейшем будем называть отмеченными.

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

После первого шага таблица 2.1. примет следующий вид:

Таблица 2.2 – Таблица после первого шага

		130	120	150
	5

Первая строка в дальнейшем не рассматривается.

Северо-западный угол этой таблицы – это клетка (2,1). Поэтому рассмотрим 2-го поставщика и 1-го потребителя. Мощность поставщика А₂ равна 200 единиц. Спрос потребителя В₁ – 60 единиц груза. Но 20 единиц груза он получил от поставщика А₁ (отмеченная клетка (1,1)). Поэтому непокрытый спрос потребителя В₁ равен . Находим минимум Клетка (2,1) становится отмеченной. Мы запишем там этот минимум - 40.

Поставщики А₁ (20 единиц) и А₂ (40 единиц) полностью покрывают спрос потребителя В₁ (60 единиц). Поэтому остальные клетки 1-го столбца объявим пустыми и в дальнейшем исключим из рассмотрения.

После второго шага таблица 2.1. примет следующий вид.

Таблица 2.3 – Таблица после второго шага

		130	120	150
	5
	4
240

Северо-западный угол таблицы 2.3. – это клетка (2,2). .

Получаем следующую таблицу 2.4:

Таблица 2.4 - Таблица после третьего шага

	60	130	120
	5
	4	1
240	2

Северо-западный угол таблицы 2.4. – это клетка (2,3).

. Получаем следующую таблицу 2.5:

Таблица 2.5 - Таблица после четвертого шага

	60	130	120
	5
	4	1	3
240	2

Северо-западный угол этой таблицы – это клетка (3,3).

. Получаем следующую таблицу 2.6:

Таблица 2.6 - Таблица после пятого шага

	60	130	120
	5
	4	1	3
	2		4

Осталась одна незаполненная клетка – это клетка (3,4).

. Получаем следующую таблицу 2.7:

Таблица 2.7 - Таблица после шестого шага

	60	130	120
	5
	4	1	3
240	2		4	7

После выполнения очередного шага мы исключали из рассмотрения либо строку, либо столбец. Только на последнем шаге отпали и строка, и столбец. Поэтому для полностью заполненной таблицы должно соблюдаться следующее соотношение: число отмеченных клеток = число строк + число столбцов −1. В нашем случае это так: .

Если это соотношение не выполняется, то возникает так называемый особый случай. Как в этом случае поступать, будет рассказано дальше.

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