Транспортная задача

7) Перейти к п.2.

Пример. Провести одно улучшение опорного плана методом потенциалов:

	ПН
ПО		10		65		25
	30	-l	6	+l	3		2
		10		20
	20		2		1		5
				20
	50	l	3	-l	4		1
				25		25

 

Решение:

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

 или 

Пусть , найдем потенциалы всех поставщиков и потребителей :

 

Определить  косвенные стоимости свободных  ячеек:

 

 

 

 

Поскольку есть отрицательные косвенные стоимости, то решение не оптимальное. Поместим перевозку l в ячейку , которой соответствует наименьшая отрицательная косвенная стоимость . Построим цикл пересчета:

lllll

Найдем максимальное значение l, сохраняющее неотрицательность всех перевозок: l (если взять значение l больше, то в ячейке будет отрицательная перевозка).

Пересчитаем новый план перевозок:

	ПН
ПО		10		65		25
	30		6		3		2
				30
	20		2		1		5
				20
	50		3		4		1
		10		15		25

 

Стоимость перевозок:  

 

 

 

 

 

 

 

 

 

Пример решения транспортной задачи

Имеется три поставщика хлебобулочной продукции: ОАО «Заря», ОАО «Хлебный дом» и ОAО «Каравай» у каждого из них имеются запасы однородных грузов:

ОАО «Заря» − 150 единиц хлебобулочной продукции,

ОАО «Хлебный дом» − 300 единиц хлебобулочной продукции,

ОAО «Каравай» − 250 единиц хлебобулочной продукции, которая должна быть доставлена потребителям: OOO «Пятерочка», OOO «Семья» и ООО «Полушка» в количестве:

OOO «Пятерочка» − 200 единиц,

OOO «Семья» − 250 единиц,

ООО «Полушка» − 250 единиц.

Стоимость доставки единицы продукции от поставщика ОАО «Заря» к указанным потребителям равна:

10 руб. – для OOO «Пятерочка»,

13 руб. – для OOO «Семья»,

11 руб. – для ООО «Полушка».

Стоимость доставки единицы продукции от поставщика ОАО «Хлебный дом» к указанным потребителям равна:

10 руб. − для OOO «Пятерочка»,

12 руб. − для OOO «Семья»,

10 руб. − для ООО «Полушка».

Стоимость доставки единицы продукции от поставщика ОAО «Каравай» к указанным потребителям равна:

11 руб. − для OOO «Пятерочка»,

12 руб. − для OOO «Семья»,

12 руб. − для ООО «Полушка».

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

Решение:  

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

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

В нашем случае, потребность всех потребителей - 700 единиц хлебобулочной продукции равна запасам всех поставщиков.

Согласно  условию задачи составим таблицу (тарифы располагаются в верхнем правом углу ячейки)

 

	Потребители	ООО «Пятерочка»		ООО «Семья»		ООО «Полушка»
Поставщики		200		250		250
ОАО «Заря»	150		10		13		11
		150	х11	−	х12	−	х13
ОАО «Хлебный дом»	300		10		12		10
		50	х21	−	х22	250	х23
ОАО «Каравай»	250		11		12		12
		0	х31	250	х32	−	х33

 

Последовательность  заполнения таблицы:

(х₁₁ = 150) → (х₂₁ = 50) → (х₂₃ = 250) → (х₃₂ = 250) → (х₃₁ = 0)

Распишем последовательность заполнения таблицы:  

1) Минимальный элемент матрицы тарифов находится в ячейке х₁₁  и равен 10, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика ОАО «Заря» к потребителю OOO «Пятерочка» наиболее рентабельный.

Запасы  ОАО «Заря» составляют 150 единиц продукции. Потребность OOO «Пятерочка» составляет 200 единиц продукции. Следовательно, от ОАО «Заря» к OOO «Пятерочка» будем доставлять 150 единиц хлебобулочной продукции.

Разместим в ячейку х₁₁ значение равное 150.

Мы полностью израсходoвали запасы ОАО «Заря». Вычеркиваем строку 1 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.

2) Следующий минимальный элемент матрицы тарифов находится в ячейке х₂₁ и равен 10, т.е. из незадействованных маршрутов, маршрут доставки продукции от ОАО «Хлебный дом» к OOO «Пятерочка» наиболее рентабельный.

Запасы  ОАО «Хлебный дом» составляют 300 единиц продукции. Потребность OOO «Пятерочка» составляет 50 единиц продукции. Следовательно, от ОАО «Хлебный дом» к OOO «Пятерочка» будем доставлять 50 единиц хлебобулочной продукции.

Разместим в ячейку х₂₁ значение равное 50.

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

3) Следующий минимальный элемент матрицы тарифов находится в ячейке х₂₃ и равен 10, т.е. из незадействованных маршрутов, маршрут доставки продукции от ОАО «Хлебный дом» к ООО «Полушка» наиболее рентабельный.

Запасы  ОАО «Хлебный дом» составляют 250 единиц продукции. Потребность ООО «Полушка» составляет 250 единиц продукции.

Следовательно, от ОАО «Хлебный дом» к ООО «Полушка» будем доставлять 250 единиц хлебобулочной продукции.

Разместим в ячейку х₂₃ значение равное 250.

Таким образом, мы полностью израсходoвали запасы ОАО «Хлебный дом», а также мы полностью удовлетворили потребность ООО «Полушка». Вычеркиваем строку 2 и столбец 3 таблицы, т.е исключаем их из дальнейшего рассмотрения.

4) Следующий минимальный элемент матрицы тарифов находится в ячейке х₃₂ и равен 12, т.е. из незадействованных маршрутов, маршрут доставки продукции от ОAО «Каравай» к OOO «Семья» наиболее рентабельный.

Запасы  ОAО «Каравай» составляют 250 единиц продукции. Потребность OOO «Семья» составляет 250 единиц продукции. Следовательно от ОAО «Каравай» к OOO «Семья» будем доставлять 250 единиц хлебобулочной продукции.

Разместим в ячейку х₃₂ значение равное 250.

Мы  полностью израсходoвали запасы ОAО «Каравай». Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

5) Заполненные нами ячейки будем называть базисными, остальные - свободными.

Для решения задачи методом потенциалов, количество базисных ячеек (задействованных  маршрутов) должно равняться:

m + n - 1, где

m - количество строк в таблице,

n - количество столбцов в таблице.

У нас количество базисных ячеек равно 4. Требуется, чтобы было 5. Следовательно, в свободную ячейку х₃₁ запишем ноль, как в ячейку не образующую цикл (понятие цикл см. ниже) с базисными ячейками и имеющую наименьший тариф.

Будем считать, что от ОAО «Каравай» к OOO «Пятерочка» доставляем 0 единиц хлебобулочной продукции.

Теперь  количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.

Мы  нашли начальное решение, т.е израсходовали  все запасы поставщиков и удовлетворили  все потребности потребителей.

 F = 10 * 150 + 10 * 50 + 10 * 250 + 12 * 250 = 7500 руб., где

 F – стоимость перевозок.

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

Дальнейшие  наши действия состоят в следующем:

• Находим потенциалы поставщиков и потребителей для имеющегося решения.
• Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена.

	Потребители	ООО «Пятерочка»		ООО «Семья»		ООО «Полушка»		Ui
Поставщики		200		250		250
ОАО «Заря»	150		10		13		11	u1 =10
		150	х11	2	х12	1	х13
ОАО «Хлебный дом»	300		10		12		10	u2 =10
		50	х21	1	х22	250	х23
ОАО «Каравай»	250		11		12		12	u3 =11
		0	х31	250	х32	1	х33
Vj		v1 = 0		v2 = 1		v3 = 0

 

Каждому поставщику ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

Для базисной ячейки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута

(ui + vj = тариф  клетки).

 

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

 

Примем v1 = 0.

v1 + u1 = x11

v1 + u1 = 10

u1 = 10 - 0 = 10

v1 + u2 = x21

v1 + u2 = 10

u2 = 10 - 0 = 10

v3 + u2 = x23

v3 + u2 = 10

v3 = 10 - 10 = 0

v1 + u3 = x31

v1 + u3 = 11

u3 = 11 - 0 = 11

v2 + u3 = x32

v2 + u3 = 12

v2 = 12 - 11 = 1

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

∆₁₂ = x₁₂ - ( u₁ + v₂ ) = 13 - ( 10 + 1 ) = 2

∆₁₃ = x₁₃ - ( u₁ + v₃ ) = 11 - ( 10 + 0 ) = 1

∆₂₂ = x₂₂ - ( u₂ + v₂ ) = 12 - ( 10 + 1 ) = 1

∆₃₃ = x₃₃ - ( u₃ + v₃ ) = 12 - ( 11 + 0 ) = 1

Составим матрицу оценок:

	0	2	1
	0	1	0
	0	0	1

 

Все оценки свободных ячеек положительные, следовательно, найдено оптимальное  решение.