Полезные материалы:

Примеры - Математическое программирование

Mетод динамического программирования

Задача1. Для двух предприятий выделено 1400 единиц денежных средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от х единиц, вложенных в первое предприятие равен , а доход от у единиц, вложенных в первое предприятие равен . Остаток средств к концу года составляет  - для первого предприятия,  - для второго предприятия. Решить задачу методом динамического программирования.

Решение

Процесс распределения средств разобъем на 4 этапа – по соответствующим годам.
Обозначим  - средства, которые распределяются на к–ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на к–ом шаге:

Остаток средств от обоих предприятий на к–ом шаге:

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

Проведем оптимизацию, начиная с четвертого шага:

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

3-й шаг.

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

2-й шаг.

 т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .

1-й шаг.

 т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при .

Результаты оптимизации:



         Определим количественное распределение средств по годам:

Т.к. , получаем


         Представим распределение средств в виде таблицы:

предприятие

год

1

2

3

4

1

1400

700

0

0

2

0

0

350

105

 

При таком распределении средств за 4 года будет получен доход, равный

 

Задача 2. Предприятие изготавливает продукцию, спрос на которую в каждом из месяцев планируемого периода Dt  (t =) тыс. ед. Запас продукции на складе на начало планируемого периода i0 тыс.ед. Затраты на производство продукции складываются из условно постоянных затрат, равных kден.ед., и пропорциональных затрат, равных Lxt. Затраты на хранение 1 тыс. ед. продукции составляют h ден.ед. Складские площади позволяют хранить не более М тыс.ед. продукции. Производственные мощности ограничены, и в каждом месяце предприятие может произвести не более В тыс.ед. продукции. Требуется разработать производственную программу изготовления продукции xt  удовлетворяющую спрос в каждом из месяцев планируемого периода и обеспечивающую минимальные затраты на производство продукции и содержание запасов. Запас продукции на складе в конце планируемого периода должен быть равен нулю.
Все необходимые числовые данные приведены в таблице.

T

D1

D2

D3

D4

i0

k

L

h

M

B

3

3

5

4

-

2

4

1

1

6

7

Решение
Для решения задачи методом динамического программирования и записи рекуррентного соотношения будем использовать следующие обозначения: n — номер планового отрезка времени периода; j — уровень запаса на конец отрезка; dn— спрос на продук­цию на n-м отрезке;

cn(x,j)= c(x)+j h — затраты, связанные с выпуском х единиц продукции на n-м отрезке и содержанием запасов, объем которых на конец n-го отрезка равен единицу j;  fn(i)— значение функции, равное затратам на производство и хранение продук­ции за последние n месяцев при условии, что уровень запасов на начало n-гo месяца составляет i единиц; xn(i)— производство про­дукции на n-м отрезке, если уровень запасов на начало отрезка равен i единиц. Изобразим плановый период на рисунке и для на­глядности нанесем на него числовые данные

          D1 = 3             D2 = 5            D3 = 4                 
 

  i 0 = 2   n =3           n = 2                n = 1     j 4 = 0
d3 = 3              d2 = 5                      d1 = 4
x3                      x2                            x1

Т.к. c(x)=k+Lxто c(0)=0; c(l)=5; c(2)=6; c(3)=7; c (4)=8; c(5)=9; c(6)=10; c(7)=11; Уровень запасов на конец планового периода должен быть равен нулю, то для n=0 имеем f0(0)=0. Перейдем к рассмотрению первого отрезка, т.е. n=1.
Тогда функциональные уравнения Беллмана для рассматриваемой задачи имеют следующий вид: для n =1
f1(i)=c1(d1-i, 0) = c1(d1-i, 0)  , где  i может принимать значения 0, 1, 2, 3, 4.
Расчет всех значений выполним в виде таблицы.

x
i    

X1* (i)

f1 (i)

0

4

8

1

3

7

2

2

6

3

1

5

4

0

0

Переходим к анализу периода, состоящего из двух последних месяцев, т.е. n= 2. Тогда уравнение Беллмана примет вид:
(с2(x) + h(i +x- d2 ) + f1(i +x - d2)) ,  где i - уровень запаса сырья на начало предпоследнего месяца может принимать значения 0, 1, 2, 3, 4, 5, 6,

x будет равняться   7, 6, 5, 4 ,3, 2, 1, 0.
Расчет всех значений выполним в виде таблицы.

x
i    

0

1

2

3

4

5

6

7

X2(i)

f2(i)

0

-

-

-

-

-

9+0+8=17

10+1+7=18

11+2+6=19

5

17

1

-

-

-

-

8+0+8=16

9+1+7=17

10+2+6=18

11+3+5=19

4

16

2

-

-

-

7+0+8=15

8+1+7=16

9+2+6=17

10+3+5=18

11+4+0=15

3

15

3

-

-

6+0+8=14

7+1+7=15

8+2+6=16

9+3+5=17

10+4+0=14

-

2

14

4

-

5+0+8=13

6+1+7=14

7+2+6=15

8+3+5=16

9+4+0=13

-

-

1

13

5

0+0+8=8

5+1+7=13

6+2+6=14

7+3+5=15

8+4+0=12

-

-

-

0

8

6

0+1+7=8

5+2+6=13

6+3+5=14

7+4+0=14

-

-

-

-

0

8

      Последнему шагу (n=3) будет соответствовать функциональное уравнение,  
(с3(x) + h(2 +x- d3 ) + f2(2 +x – d3)),  где i - уровень запаса сырья на начало предпоследнего месяца может принимать значение 2, а  x будет равняться  7, 6, 5, 4 , 3, 2, 1.

Расчет всех значений выполним в виде таблицы. Таб. 4.4

     x
i    

1

2

3

4

5

6

7

x4(i)

f4(х)

i 0 = 2     

5+0+17

6+1+16

7+2+15

8+3+14

9+4+13

10+5+8

11+6+8

1

22

Из таблицы видно, что в первом месяце оптимальной будет поставка x3(2)=1 единицам. С учетом запаса 2 единиц, общее коли­чество составит 3. За этот месяц будет израсходовано 3 единицы, так что к началу второго месяца запас составит i=0 единиц. По таб. 4.3 находим x2(0)=5, за этот месяц будет израсходовано 5 единиц. Останется 0 единица. В третьем   месяце с учетом остатка 0 единиц будет поставка x1(0)=4 единицы, что достаточно для удовлетворения потребностей в третьем   месяце. При этом к концу третьего   месяца уровень запаса будет равен  0 ед. 
Минимальные затраты, связанные с производством и хранением продукции за три месяца, составят 22 единицы.