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

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

Метод минимальной стоимости

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

Алгоритм решения этим методом разберем на следующем примере. Пример 2. Найти первоначальный план поставок методом минимальной стоимости для данных представленных в примере 1.

Решение.В этом методе на каждом шаге решения поставка осуществляется в клетку с наименьшей стоимостью перевозки единицы груза среди всех незаполненных клеток.

Шаг 1. Из таблицы 1 видно, что поставка единицы груза от второго поставщика второму потребителю имеет наименьшую стоимость 1 у.е. Поэтому осуществляем поставку в эту клетку:

𝑥_!! = min 𝑀_!, 𝑁_! = min 190,120 = 120. Поскольку спрос второго

потребителя полностью удовлетворен, то остальные клетки второго столбца

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

Таблица 9

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

Шаг 2. Далее рассматриваем все незаполненные клетки. Среди них наименьшую стоимость перевозки единицы груза имеют клетки (1,3) и (2,3). Вычислим возможные объемы поставок соответствующим потребителям. Для

клетки (1,3): 𝑥_!" = min 𝑀_!, 𝑁_! = min 30,150 = 30. Для клетки (2,3):

𝑥_!" = min 𝑀_!, 𝑁_! = min 190 − 120,150 = 70. Выбираем вариант с наибольшим объемом поставки, поскольку 𝑥_!" > 𝑥_!", то выбираем клетку

(2,3). Вторая строка из дальнейшего решения исключается (второй поставщик

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

Таблица 10

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

Шаг 3. Теперь выбираем клетку (1,3): 𝑥_!" = min 𝑀_!, 𝑁_! = min 30,150 −

70 = 30. Первая строка из дальнейшего решения исключается (таблица 11).

Таблица 11

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

Шаг 4. Выбираем клетку (3,3): 𝑥_!! = min 𝑀_!, 𝑁_! = min 250,150 − 70−

30 = 50.

Шаг 5. Выбираем клетку (3,1): 𝑥_!" = min 𝑀_!, 𝑁_! = min 250 − 50,70 = 70. Шаг 6. Заполняем оставшуюся клетку (3,4): 𝑥_!" = min 𝑀_!, 𝑁_! = min 250 − 50 − 70,130 = 130 (таблица 12).

Таблица 12

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

Число отмеченных клеток равняется сумме чисел строк и столбцов минус

единица. В нашем примере: 6 = 3 + 4 − 1 правило соблюдается. Вычислим значение целевой функции для полученного первоначального

плана поставок транспортной задачи по формуле

nm

F_c_ijx_ij2 30 1120 2 70 5 70 3 50 7 130 1730.

j1 i1

Видим, что суммарные затраты на перевозку груза от поставщиков к потребителям по плану поставок, полученному методом минимальной стоимости равны 1730 у.е., что на 40 у.е. больше, чем в методе северо- западного угла (1690 у.е.). Это не означает, что суммарная стоимость поставок в методе минимальной стоимости всегда больше, чем в методе северо-западного угла. Здесь нет закономерности, бывает и наоборот.
Задача 2. Найти первоначальный план поставок методом минимальной стоимости для данных представленных в задаче 1. Вычислить значение целевой функции.