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

ТРАНСПОРТНАЯ ЗАДАЧА

ЭКОНОМИКО-МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ТРАНСПОРТНОЙ ЗАДАЧИ

Существуют поставщики и потребители некоторого однородного груза. У каждого поставщика имеется определенное количество единиц этого груза (мощность поставщика).

Каждому потребителю нужно некоторое количество единиц этого груза (спрос потребителя). Известны затраты на перевозку единицы груза от каждого из поставщиков к каждому из потребителей.

Нужно составить такой план перевозок от поставщиков к потребителям, при котором:

1) суммарные затраты на перевозку груза будут минимальны;

2) по возможности будут задействованы все мощности поставщиков;

3) по возможности будет удовлетворен весь спрос потребителей.

Закрытая модель транспортной задачи — это модель, в которой суммарная мощность поставщиков равна суммарному спросу потребителей. В противном случае модель называется открытой.

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

1) Составляем специальную таблицу.

2) Находим первоначальный план поставок (далее будут рассмотрены методы северо-западного угла и минимальной стоимости).

3) Оптимизируем его распределительным методом.

МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА

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

Пример. У поставщиков А1, А2, А3, А4, А5 сосредоточено соответственно 125, 130, 55, 95 и 435 единиц некоторого однородного груза, который необходимо доставить потребителям В1, В2, В3, В4 в количестве 135, 145, 250 и 310 единиц. Стоимость перевозок единицы груза от поставщиков к потребителям задается матрицей:

Таблица 1.

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

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

Суммарная мощность поставщиков равна: 125+130+55+95+435=840 единиц.

Суммарный спрос потребителей равен: 135+145+250+310=840 единиц.

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

Таблица 2.

					В1=135	Пот ре би те ли
					В2=145
					В3=250
					В4=310
А1=125	А2=130	А3=55	А4=95	А5=435	å=840
П о с т а в щ и к и

В последней строке указаны мощности поставщиков (А1-А5), в последнем столбце - спрос потребителей (В1-В4). Числа в левом верхнем углу клетки — это стоимость перевозок единицы груза от соответствующего поставщика к соответствующему потребителю, то есть значения из данной в условии матрицы.

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

Северо-западный угол таблицы — это ее левый верхний угол, то есть клетка в 1-й строке и 1-м столбце — клетка (1,1). Поэтому рассмотрим 1-го поставщика и 1-го потребителя. У поставщика А1есть 125 единиц груза, а потребителю В1 нужно 135 единиц. Находим минимум из этих двух чисел: min (125, 135) = 125. Клетка (1,1) перечеркивается по диагонали сплошной чертой (——), в правом нижнем углу пишется найденный минимум 125. Это означает, что поставщик А1должен поставить потребителю В1 125 единиц груза. Такие клетки в дальнейшем будем называть отмеченными.

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

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

Таблица 3.

					В1=135
3					В2=145
					В3=250
					В4=310
А1=125	А2=130	А3=55	А4=95	А5=435	å=840

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

Северо-западный угол этой таблицы — это клетка (1, 2). Поэтому рассмотрим поставщика А2 и потребителя В1. Мощность поставщика А2равна 130 единиц. Спрос потребителя В1 — 135 единиц груза. Но 125 единиц груза он получил от поставщика А1 (об этом говорит отмеченная клетка (1,1)). Поэтому непокрытый спрос потребителя В1 равен 135 - 125 = 10. Находим минимум min(130, 135 - 125) = 10. Клетка (1, 2) становится отмеченной. Мы запишем там этот минимум 10 (см ниже табл. 4).

Поставщики А1 (125 единиц) и А2(10 единиц) полностью покрывают спрос потребителя В1(135 единиц). Поэтому остальные клетки 1-й строки объявим пустыми и в дальнейшем исключим из рассмотрения.

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

Таблица 4.

	1	3		5
3

Северо-западный угол этой таблицы — это клетка (2,2). min (130 - 10, 145) = 120.

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

Таблица 5.

125	1	3		5
3
2	3

Северо-западный угол этой таблицы — это клетка (2,3). min (55, 145 - 120) = 25.

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

Таблица 6.

	1 10	3		5
3		5
2	3

Северо-западный угол этой таблицы — это клетка (3,3). min (55 - 25, 250) = 30.

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

Таблица 7.

	1 10	3		5
3		5 25
2	3	30

Северо-западный угол этой таблицы — это клетка (3,4). min (95, 250 - 30) = 95.

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

Таблица 8.

	1 10	3		5
3		5
2	3	4 30

Северо-западный угол этой таблицы — это клетка (3,5). min (435, 250 – 95–30) = 125.

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

Таблица 9.

	1 10	3		5
3		5
2	3	4 30		6

Северо-западный угол этой таблицы — это клетка (4,5). min (310, 435-125) = 310.

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

Таблица 10.

	1 10	3		5
3		5
2	3	4 30		6
			7

Получаем суммарные затраты:

5*125 + 1*10 + 4*120 + 5*25 + 4*30 + 5*95 + 6*125 + 1*310 = 2895.

Сделаем проверку.

Число отмеченных клеток = число строк + число столбцов – 1.

8 = 4 + 5 – 1.

8 = 8.