Оптимальное решение транспортной задачи.

Таблица 3

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

U1   U2   U3

	Потребители
Поставщики		-
	-		-	-
			-	-

V1 V2 V3 V4

 

Каждому поставщику и потребителю ставится в соответствии переменная, называемая потенциалом.(U_i - для поставщика, V_j - для потребителя).

Для каждой заполненной клетки составляем уравнение вида С_ij=U_i+V_j. Из полученной системы, методом подбора, определяются значения переменных U_i и V_j.

U₁+ V₂=13; U₁=0, V₂=13;

U₁+ V₃=6; U₁=0, V₃=6;

U₁+ V₄=11; U₁=0, V₄=11;

U₂+ V₂=2; U₂=-11, V₂=13;

U₃+ V₁=4; U₃=-6, V₁=10;

U₃+ V₂=7; U₃=-6, V₂=13.

Используя полученные значения переменных U_i и V_j для пустых клеток, определяется величина псевдостоимости Z_ij=U_i+V_j, а затем для этих пустых клеток вычисляем величина d, как разность между исходной стоимостью и найденной d_ij = C_ij – Z_ij.

Z₁₁=U₁+ V₁=10; δ₁₁=C₁₁-Z₁₁=-5;

Z₂₁=U₂+ V₁=-1; δ₂₁=C₂₁-Z₂₁ =10;

Z₂₃=U₂+ V₃=-5; δ₂₃=C₂₃-Z₂₃=8;

Z₃₃=U₃+ V₃=0; δ₃₃=C₃₃-Z₃₃=12;

Z₂₄=U₂+ V₄=0; δ₂₄=C₂₄-Z₂₄=10;

Z₃₄=U₃+ V₄=5; δ₃₄=C₃₄-Z₃₄=3;

Если среди полученных d_ij нет отрицательных, то получено оптимальное решение, при этом L®min.

Так как в таблице 3 имеется отрицательное значение δ₁₁=-5, то оптимальное решение не найдено, следовательно, строим цикл.

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

Вершины цикла маркируются последовательно чередующимися знаками "+" и "-", начиная с исходной величины. В исходной вершине ставим знак "+".

Находим минимальный объем перевозимого груза Х_ij среди отрицательных величин. Эта величина груза списывается со всех отрицательных вершин и добавляется к положительным вершинам, при этом состав клеток изменяется.

Таблица 4

	Потребители
Поставщики		+ 5 -	- 13
	-		-	-
	- 4	+ 7	-	-

 

Таблица 5

После преобразований получим:

 

	Потребители
			U1   U2   U3 10
Поставщики			-
	-		-	-
			-	-

V1 V2 V3 V4

 

Для таблицы 5 повторяем шаги решения.

Составим уравнения C_ij=U_i+V_j для каждой заполненной клетки и определим значения U_i и V_j:

U₁+ V₁=5; U₁=0, V₁=5;

U₁+ V₃=6; U₁=0, V₃=6;

U₁+ V₄=11; U₁=0, V₄=11;

U₂+ V₂=2; U₂=-6, V₂=8;

U₃+ V₁=4; U₃=-1, V₁=5;

U₃+ V₂=7; U₃=-1, V₂=8.

Используя полученные значения переменных, определим величины псевдо стоимости и значения δ для пустых клеток:

Z₂₁=U₂+ V₁=-1; δ₂₁=C₂₁-Z₂₁=10;

Z₁₂=U₁+ V₂=8; δ₁₂=C₁₂-Z₁₂ =5;

Z₂₃=U₂+ V₃=0; δ₂₃=C₂₃-Z₂₃=3;

Z₃₃=U₃+ V₃=5; δ₃₃=C₃₃-Z₃₃=7;

Z₂₄=U₂+ V₄=5; δ₂₄=C₂₄-Z₂₄=5;

Z₃₄=U₃+ V₄=10; δ₃₄=C₃₄-Z₃₄=-2;

Таблица 6

Так как в таблице 5 имеется отрицательное значение δ₃₄=-2, то оптимальное решение не найдено, следовательно, строим цикл:

 

	Потребители
Поставщики		+ 5	-		- 11
	-		-	-
	- 4		-	+ 8 -

 

Таблица 7

После преобразований получим:

 

	Потребители
			U1   U2   U3 10
Поставщики			-		-
	-		-	-
			-

V1 V2 V3 V4 V4

 

Для таблицы 7 повторяем шаги решения.

Составим уравнения C_ij=U_i+V_j для каждой заполненной клетки и определим значения U_i и V_j:

U₁+ V₁=5; U₁=0, V₁=5

U₁+ V₃=6; U₁=0, V₃=6

U₂+ V₂=2; U₂=-6, V₂=8

U₃+ V₂=7; U₃=-1, V₂=8

U₃+ V₄=8; U₃=-1, V₄=9

Используя полученные значения переменных, определим величины псевдо стоимости и значения δ для пустых клеток:

Z₂₁=U₂+ V₁=-1; δ₂₁=C₂₁-Z₂₁=10;

Z₁₂=U₁+ V₂=8; δ₁₂=C₁₂-Z₁₂ =5;

Z₂₃=U₂+ V₃=-7; δ₂₃=C₂₃-Z₂₃=10;

Z₃₃=U₃+ V₃=5; δ₃₃=C₃₃-Z₃₃=7;

Z₁₄=U₁+ V₄=9; δ₁₄=C₁₄-Z₁₄=2;

Z₂₄=U₂+ V₄=3; δ₂₄=C₂₄-Z₂₄=7;

В таблице 7 все δ > 0, следовательно, она является оптимальным решением транспортной задачи.

Определим стоимость всего плана перевозок.

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

 

---

Дата добавления: 2016-01-03; просмотров: 18; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!