Фиктивный потребитель

Закрытая транспортная задача.

Лекция 10

Тема: “ Примеры решения транспортной задачи”

Пример 1. Найти оптимальный план перевозок для транспортной задачи из примера 1.

Решение. В качестве начального плана выберем план, найденный по методу минимального элемента.

Пункты отправления	Пункты назначения
				Запасы
Потребности

Число заполненных клеток равно 4+3-1=6, т.е. данный план невырожденный. Определим потенциалы поставщиков и потребителей, составив уравнения для заполненных клеток.

Составим разности для свободных клеток:

Получена положительная разность . Заполним клетку первой строки и четвёртого столбца. Строим цикл, начинающийся и заканчивающийся в этой клетке.

Пункты отправления	Пункты назначения
				Запасы
			1 - 160	2 +
			+30	- 90
Потребности

Вершинами цикла являются клетки: (1,4), (3,4), (3,3), (1,3) (на первом месте стоит номер строки, на втором – столбца). В клетке (1,4) ставим «+», в клетке (3,4) «-», в клетке (3,3) «+», в клетке (1,3) «-». Перераспределяем продукцию по циклу. Минимальное значение для клеток со знаком «-» находится в клетке (3,4): Отнимаем 90 от значений стоящих в клетках со знаком «-», и прибавляем к значениям, стоящим в клетках со знаком «+». Получаем новый план перевозок, представленный в следующей транспортной таблице:

Пункты отправления	Пункты назначения
				Запасы
Потребности

Новый план невырожденный. Проверим его на оптимальность.

Составим разности для свободных клеток:

,

Положительная разность Заполним клетку (2,2). Цикл будет содержать клетки: (2,2), (3,2), (3,3), (1,3), (1,4), (2,4), (2,2).

Пункты отправления	Пункты назначения
				Запасы
			1 -	2 +
		5 +		8 -
		-50	+120
Потребности

Минимальное значение для клеток со знаком

«-». Перераспределив продукцию по циклу, получим новый план перевозок:

Пункты отправления	Пункты назначения
				Запасы
			1 -	2 +
		5 +		8 -
		-30	+140
Потребности

Новый план невырожденный. Проверим его на оптимальность.

Составим разности для свободных клеток:

,

,

Все разности отрицательные, следовательно, получен оптимальный план.

.

-

стоимость перевозок, соответствующая оптимальному плану.

Замечание. При пересчёте стоимости нового плана можно ограничиться пересчётом только тех поставок, которые участвовали в цикле. Экономия на цикле переносится на весь план.

Пример 2. Для строительства четырех дорог используется гравий из трёх карьеров. Запасы гравия в каждом из карьеров соответственно равны 120, 280 и 160 ед. Потребности в гравии для строительства каждой из дорог соответственно равны 130, 220, 60 и 70 ед. Известны также тарифы перевозок 1 ед. гравия из каждого из карьеров к каждой из строящихся дорог, которые задаются матрицей

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

Решение. Исходные данные задачи сведём в таблицу.

Пункты отправления	Пункты назначения	Запасы
Потребности

Запасы гравия в карьерах (120+280+160=560) больше, чем потребности в нём (130+220+60+70=480) на строящихся дорогах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введём дополнительный пункт назначения с потребностями, равными 560-480=80 ед. Тарифы перевозки единицы гравия из всех карьеров в пункт полагаем равными нулю. В результате получаем закрытую модель транспортной задачи, опорный план перевозок которой получаем по методу минимального элемента.

№						Предложение
Спрос						-

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

Составим разности для свободных клеток:

.

Все разности отрицательные, следовательно, получен оптимальный план.

.

- стоимость перевозок, соответствующая оптимальному плану; при этом остаётся неиспользованными 60 ед. гравия во втором карьере и 20 ед. гравия в первом карьере.

Дата добавления: 2014-01-11