Методология математического моделирования ассортиментной задачи

 

Дальнейшее решение  было проведено на компьютере и получены следующие ответы: всего подлежит раскрою 200 плит, причем все раскраиваются вторым способом, тогда мы получим 600 заготовок первого вида, 200 – второго, 400 – третьего, 400 – четвёртого, при минимальных отходах, равных 56 м².

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

 

Известны: пункты производства (А₁, А₂ … A_i … А_m); m – пунктов, производящих конкретную продукцию;

а_i – мощность i-поставщика (сколько необходимо реализовать продукции, т. е. перевести из А_i)

– суммарная мощность поставщиков  в плановом периоде;

пункты потребления (В₁, В₂ … B_j … В_n); n – пунктов потребления конкретной продукции;

b_j – потребность (спрос, ёмкость) j-поставщика в конкретной продукции;

  – суммарный спрос n-потребителей.

1)   – сбалансированные спрос и предложение, такие задачи называются закрытыми транспортными задачами;

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

2) возможна поставка  продукции из любого пункта  производства в любой пункт  потребления.

3) с_ij – затраты на поставку продукции, т. е. критерий оптимальности (может быть и на производство, и на транспортировку).

 

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

 

x_ij – объём поставки от i-поставщика к j-потребителю (искомая величина)

 

Поставщики и их мощности		Потребители и их спрос
		B1 ………………………….. Bj ………………………………….. Bn
		b1 …………………………… bj ………………………………….. bn
		С=[ сij] mxn / Х=[ xij]mxn
A1	a1	c11	……………………. x11…………………	c1j	…………………. ………x1j………	c1n	……………… ………….. x1n
. . .	. . .	. . .	.            .                 . .            .                 . .            .                 .	. . .	.             .             . .             .             . .             .             .	. . .	.          .         . .          .         . .          .          .
Ai	ai	ci1	……………………. xi1…………………	cij	…………………. ………xij………	cin	……………… ………….. xin
. . .	. . .	. . .		. . .		. . .
Am	am	cm1	……………………. xm1…………………	c11	…………………. ………xmj………	c11	……………… …………..xmn

 

 

Целевая функция:

  (1)

Условие реализации продукции  у каждого из поставщиков:

  (2)

Условие обеспечения  всех потребителей продукцией по их потребности:

   (3)

Условие не отрицательности переменных:

     

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

 

m+n-1 – линейно независимых уравнений, ранг системы, r= m+n-1.

В каждом опорном плане  должно быть m+n-1 базисных элементов (x_ij>0), если таких переменных равно или больше, чем m+n-1, план называется невырожденный; если одна или несколько базисных переменных равна нулю, то такой план считается вырожденным.

Открытые транспортные задачи.

 

a)

  (1)

  (2)

   (3)

B_n+1: – потребность какого-то потребителя, находящегося за пределами района (фиктивный потребитель).

  (1)

  (2)

   (3)

с_{i, n+1}=0 (i=1,2…m)

 

б)

  (1)

  (2)

   (3)

     

А_n+1: – фиктивный поставщик.

  (1)

  (2)

   (3)

     

Ограничение транспортных возможностей.

 

а) x_ij=0 => c_ij=М, где М»0;

б) 0 ≤ х_ij ≤ d_ij

d_ij – характеризует транспортные возможности между i-поставщиком и j-потребителем.

Тогда поставщик А_i условно делится на А_i` и А<sub>i</sub>``, при этом a<sub>i</sub>`=d_ij и a_i``= a<sub>i</sub>`-d<sub>ij</sub>, c<sub>ij</sub>`=c<sub>ij</sub> и c<sub>ij</sub>``=М, где М»0.

 

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

 

	В1 200		В2 250		В3 275		В4 255		В5 120		Ui
A1 300	7	-	10	-	M	-	6	255	0	45	0
A2 125	9	-	5	125	6	0	8	-	0	-	-5
A3 125	9	-	5	125	M	-	8	-	0	-	-5
A4 270	8	-	6	-	11	195	10	-	0	75	0
A5 280	6	200	11	-	9	80	7	-	0	-	-2
Vj	-8		10		11		6		0

 

Δ₁₁=-1

Δ₁₂=0

Δ₁₃=M-11

Δ₂₁=6

Δ₂₄=7

Δ₂₅=5

Δ₃₁=6

Δ₃₃=M-6

Δ₃₄=7

Δ₃₅=5

Δ₄₁=0

Δ₄₂=-4

Δ₄₄=4

Δ₅₂=13

Δ₅₄=0

Δ₅₅=2

 

 

	В1 200		В2 250		В3 275		В4 255		В5 120		Ui
A1 300	7	-	10	-	M	-	6	255	0	45	0
A2 125	9	-	5	-	6	125	8	-	0	-	-5
A3 125	9	-	5	125	M	-	8	-	0	-	-1
A4 270	8	-	6	125	11	70	10	-	0	75	0
A5 280	6	200	11	-	9	80	7	-	0	-	-2
Vj	8		6		11		6		0

 

Δ₁₁=-1

Δ₁₂=4

Δ₁₃=M-11

Δ₂₁=6

Δ₂₂=4

Δ₂₄=7

Δ₂₅=5

Δ₃₁=2

Δ₃₃=M-10

Δ₃₄=3

Δ₃₅=1

Δ₄₁=0

Δ₄₄=4

Δ₅₂=7

Δ₅₄=3

Δ₅₅=2

 

	В1 200		В2 250		В3 275		В4 255		В5 120		Ui
A1 300	7	45	10	-	M	-	6	255	0	-	0
A2 125	9	-	5	-	6	125	8	-	0	-	-4
A3 125	9	-	5	125	M	-	8	-	0	-	0
A4 270	8	-	6	125	11	25	10	-	0	120	1
A5 280	6	155	11	-	9	125	7	-	0	-	-1
Vj	7		5		10		6		-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-го года, составляется пара функциональных уравнений в предположении, что пришло старое оборудование без замены: