Практическое задание. Занятие Методы составления первоначального плана поставок

• Название: Занятие Методы составления первоначального плана поставок
• Дата: 04.04.2023
• Размер: 0.81 Mb.
• Имя файла: Практическое задание.docx
• Тип: Занятие; #1037593
• страница: 1 из 4

Практическое занятие 1.

Методы составления первоначального плана поставок

Транспортная задача является одной из наиболее распространенных задач линейного программирования и находит широкое практическое приложение. Рассмотрим некоторые методы построения первоначального плана поставок для транспортной задачи.

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

Этот метод используется для нахождения первоначального плана поставок в транспортной задаче. Рассмотрим алгоритм метода на следующем примере.

Пример1. У поставщиков 𝐴_!, 𝐴_!, 𝐴_! сосредоточено соответственно 30, 190,

250 единиц некоторого однородного груза. Этот груз необходимо доставить

потребителям 𝐵_!, 𝐵_!, 𝐵_!, 𝐵_! в количестве 70, 120, 150 и 130 единиц

соответственно. Стоимость перевозок единицы груза от поставщиков к

потребителям задается матрицей коэффициентов затрат

	4	7	2	3
𝐶 =	3	1	2	4	.
	5	6	3	7

В этой матрице элемент 𝑐_!! = 4, т.е. стоимость перевозки единицы груза от

первого поставщика первому потребителю равна 4 у.е. и т.д.

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

Решение.Определим суммарную мощность поставщиков 𝑀 = 30 + 190 +

250 = 470 единиц .

Определим суммарный спрос потребителей 𝑁 = 70+ 120 + 150 + 130 =

470 единиц .

Поскольку 𝑀 = 𝑁, то экономико-математическая модель транспортной

задачи является закрытой.

Запишем исходные данные в виде таблицы поставок (таблица 1).

План поставок будет задан, если будет найдены величины x_ij-­‐ искомые объемы перевозок от iпоставщика jпотребителю.

Отметим, что северо-западный угол таблицы поставок это ее левый верхний

угол, клетка в которой, в нашем примере, стоит число 4. Клетка, стоящая на пересечении первого поставщика и первого потребителя клетка (1,1).

Именно с этой клетки и начинается решение задачи о нахождении первоначального плана поставок методом северо-западного угла.

Таблица 1

	70	120	150	130
30	4	7	2	3
190	3	1	2	4
250	5	6	3	7

Алгоритм решения.

Шаг 1. Выбираем клетку (1,1). Рассматриваем первого поставщика и первого

потребителя. Поставщик 𝐴_! имеет мощность 𝑀_! = 30. У потребителя 𝐵_!

имеется спрос 𝑁_! = 70. Находится минимум из этих двух чисел:

min 𝑀_!, 𝑁_! = 30. Полагаем, что объем перевозок от первого поставщика первому потребителю: 𝑥_!! = 30 единиц груза. В таблице поставок клетка

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

пишется значение 𝑥_!!. Такие клетки в дальнейшем будем называть

отмеченными (таблица 2).

Таблица 2

	70	120	150	130
30	4 30	7	2	3
190	3	1	2	4
250	5	6	3	7

Поскольку поставщик 𝐴_! израсходовал все свои мощности, то исключаем его

из дальнейшего рассмотрения. Поэтому все клетки первой строки

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

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

Таблица 3

	70	120	150	130
30	4 30	7	2	3
190	3	1	2	4
250	5	6	3	7

Шаг 2. Снова выбираем северо-западный угол таблицы поставок. Теперь это клетка (2,1). Рассматриваем второго поставщика и первого потребителя.

Поставщик 𝐴_! имеет мощность 𝑀_! = 190. У потребителя 𝐵_! имеется спрос

𝑁_! = 70. Однако он уже получил 30 единиц груза от поставщика 𝐴_! (об этом говорит отмеченная клетка (1,1)). Следовательно у потребителя 𝐵_! имеется неудовлетворенный спрос 𝑁_! = 70 − 30 = 40. Далее находится минимум из двух чисел: min 𝑀_!, 𝑁_! = 40. Полагаем, что объем перевозок от второго поставщика первому потребителю: 𝑥_!" = 40 единиц груза. В таблице

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

правом нижнем углу пишется значение 𝑥_!". Клетка (2,1) становится

отмеченной. Поскольку спрос первого потребителя полностью удовлетворен,

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

исключаются и считаются пустыми.

После второго шага таблица поставок примет вид (таблица 4).

Таблица 4

	70		120	150	130
30	4	30	7	2	3
190	3	40	1	2	4
250	5		6	3	7

Шаг 3. Теперь северо-западный угол таблицы поставок это клетка (2,2).
Рассматриваем второго поставщика и второго потребителя. У Поставщик 𝐴_! теперь имеет мощность 𝑀_! = 190 − 40 = 150. У потребителя 𝐵_! имеется спрос 𝑁_! = 120. Находим минимум из двух чисел: min 𝑀_!, 𝑁_! = 120.

Полагаем, что объем перевозок от второго поставщика второму потребителю:

𝑥_!! = 120 единиц груза. В таблице поставок клетка (2,2) перечеркивается по диагонали сплошной чертой и в правом нижнем углу пишется значение 𝑥_!!.

Клетка(2,2) становится отмеченной. Поскольку спрос второго потребителя

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

После третьего шага таблица поставок примет вид (таблица 5).

Таблица 5

	70		120		150	130
30	4	30	7		2	3
190	3		1		2	4
		40		120
250	5		6		3	7

Шаг 4. Северо-западный угол таблицы поставок это клетка (2,3). Объем перевозок от второго поставщика третьему потребителю:

𝑥_!" = min 𝑀_!, 𝑁_! = min 190 − 40 − 120, 150 = 30 единиц груза. После

четвертого шага получим следующую таблицу поставок (таблица 6).

Таблица 6

	70		120		150		130
30	4	30	7		2		3
190	3		1		2		4
		40		120		30
250	5		6		3		7

Шаг 5. Северо-западный угол таблицы поставок это клетка (3,3). Объем перевозок от третьего поставщика третьему потребителю:

𝑥_!! = min 𝑀_!, 𝑁_! = min 250,150 − 30 = 120 единиц груза. После пятого

шага получим следующую таблицу поставок (таблица 7).

Таблица 7

	70		120		150		130
30	4	30	7		2		3
190	3		1		2		4
		40		120		30
250	5		6		3	120	7

Шаг 6. Северо-западный угол таблицы поставок это клетка (3,4). Это единственная незаполненная клетка. Объем перевозок от третьего

поставщика четвертому потребителю: 𝑥_!" = min 𝑀_!, 𝑁_! = min 250 −

120,130 = 130 единиц груза. После шестого шага получим окончательную

таблицу поставок (таблица 8).

Таблица 8

	70		120			150				130
30	4	30		7			2				3
190	3			1			2					4
		40			120				30
250	5		6			3					7
								120					130

Таким образом, получен первоначальный план поставок методом северо- западного угла. Этот план поставок можно представить в виде матрицы


X = .

Отметим, что в методе северо-западного угла после каждого шага из рассмотрения исключается либо строка, либо столбец. Только на последнем шаге исключаются и строка, и столбец. Следовательно для таблицы поставок после последнего шага должно соблюдаться следующее правило: число отмеченных клеток равняется сумме чисел строк и столбцов минус единица.

В нашем примере: 6 = 3 + 4 − 1 правило соблюдается. Ниже рассмотрим

пример для которого это правило не соблюдается. Это, так называемый,

особый случай.

Вычислим значение целевой функции для полученного первоначального плана поставок транспортной задачи по формуле
nm

F_c_ijx_ij4 30 3 40 1120 2 30 3 120 7 130 1690 .

j1 i1
Другими словами, суммарные затраты на перевозку груза от поставщиков к потребителям по плану поставок, полученному методом северо-западного угла, равняются 1690 у.е.

Задача 1. Найти первоначальный план поставок методом северо-западного угла для данных представленных в таблице. Вычислить значение целевой функции.

Поставщики	Запасы поставщиков	Потребители и их потребности
		1		2			3			4
		20		110			40			110
1	60	1	x11		2	x12		5	x13		3	x14
2	120	1	x21		6	x22		5	x23		2	x24
3	100	6	x31		3	x32		7	x33		4	x34