Рассмотрим пример решения транспортной задачи методом потенциалов.

 

	В1	В2	В3	В4	В5	Ui
A1		-		-	M	-
A2		-						-		-	-5
A3		-			M	-		-		-	-5
A4		-		-				-
A5				-				-		-	-2
Vj	-8

 

Δ₁₁=-1

Δ₁₂=0

Δ₁₃=M-11

Δ₂₁=6

Δ₂₄=7

Δ₂₅=5

Δ₃₁=6

Δ₃₃=M-6

Δ₃₄=7

Δ₃₅=5

Δ₄₁=0

Δ₄₂=-4

Δ₄₄=4

Δ₅₂=13

Δ₅₄=0

Δ₅₅=2

 

 

	В1	В2	В3	В4	В5	Ui
A1		-		-	M	-
A2		-		-				-		-	-5
A3		-			M	-		-		-	-1
A4		-						-
A5				-				-		-	-2
Vj

 

Δ₁₁=-1

Δ₁₂=4

Δ₁₃=M-11

Δ₂₁=6

Δ₂₂=4

Δ₂₄=7

Δ₂₅=5

Δ₃₁=2

Δ₃₃=M-10

Δ₃₄=3

Δ₃₅=1

Δ₄₁=0

Δ₄₄=4

Δ₅₂=7

Δ₅₄=3

Δ₅₅=2

 

	В1	В2	В3	В4	В5	Ui
A1				-	M	-				-
A2		-		-				-		-	-4
A3		-			M	-		-		-
A4		-						-
A5				-				-		-	-1
Vj					-1

 

Δ₁₂=5

Δ₁₃=M-10

Δ₁₅=1

Δ₂₁=6

Δ₂₂=4

Δ₂₄=6

Δ₂₅=5

Δ₃₁=2

Δ₃₃=M-10

Δ₃₄=2

Δ₃₅=1

Δ₄₁=0

Δ₄₄=3

Δ₅₂=7

Δ₅₄=2

Δ₅₅=2

 

 

F=7x₁+10x₂+Mx₃+6x₄+7x₁+10x₂+Mx₃+6x₄+9x₅+5x₆+6x₇+8x₈+8x₉+6x₁₀+11x₁₁+

+10x₁₂+6x₁₃+11x₁₄+9x₁₅+7x₁₆=min

при ограничениях:

F=7*45+6*155+5*125+6*125+6*125+11*25+9*125+6*255=6300

 

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

1-ое лесозаготовительное предприятие поставляет 45 т. м³ 1-ому деревообрабатывающему предприятию;

1-ое – 4-ому: 255 т. м³;

2-ое – 2-ому: 125 т. м³;

2-ое – 3-ему: 125 т. м³;

3-е – 2-ому: 125 т. м³;

3-е – 3-ему: 25 т. м³;

у 3-го предприятия остаётся запас в 120 т. м³;

4-е – 1-ому: 155 т. м³;

4-е – 3-ему: 125 т. м³;

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

1-ое – 4-ому: 255 т. м³;

2-ое – 2-ому: 125 т. м³;

2-ое – 3-ему: 125 т. м³;

3-е – 1-ому: 25 т. м³;

3-е – 2-ому: 125 т. м³;

у 3-го предприятия остаётся запас в 120 т. м³;

4-е – 1-ому: 130 т. м³;

4-е – 3-ему: 150 т. м³.

 

Оптимизация замены оборудования. Динамическое программирование в планировании производством и управлении им.

 

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

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

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

Под функциональными уравнениями понимаются такие уравнения, в которых выражается функциональная зависимость между множеством функций – это сущность и отличие динамического программирования от линейного.

 

Содержание проблемы и сущность алгоритма решения.

 

Процесс решения задачи осуществляется следующим способом. Берётся период в N лет. К этому времени оборудование отработало некое количество лет и пришло t₀ возраста.

Решение задачи начинается с последнего N-го года, составляется пара функциональных уравнений в предположении, что пришло старое оборудование без замены:

1) рассчитывается доход от эксплуатации оборудования при замене;

2) рассчитывается доход от эксплуатации оборудования в течение года при условии его старения.

Вторая гипотеза: к N-ому году оборудование могло прийти замененным в каком-то году, тогда составляется пара уравнений, в которых определяется доход за год от эксплуатации единицы оборудования при условии замены или сохранения оборудования.

Шаг второй: рассматриваем (N-1) год.

Рассматриваются две гипотезы:

· пришло старое оборудование без замены;

· пришло оборудование, которое было заменено.

Шаг третий: рассматривается (N-2) год при двух гипотезах, составляются уравнения, рассчитывается доход.

Решение продолжается по всем шагам. На первом году будет одна гипотеза, что пришло старое оборудование, используемое t₀ лет.