Пример решения задачи - метод динамического программирования.

Ниже приведено условие  и решение задачи. Закачка решения в формате doc  начнется автоматически через 10 секунд.

Условие:

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

Все необходимые числовые данные приведены в таблице 4.1

Таблица 4.1

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)+jh — затраты, связанные с выпуском х единиц продукции на n-м отрезке и содержанием запасов, объем которых на конец n-го отрезка равен единицу j; fn(i)— значение функции, равное затратам на производство и хранение продук­ции за последние п месяцев при условии, что уровень запасов на начало no месяца составляет i единиц; xn(i) — производство про­дукции на n-м отрезке, если уровень запасов на начало отрезка равен i единиц. Изобразим плановый период на рисунке и для на­глядности нанесем на него числовые данные

 

               D1 = 3                D2 = 5                 D3 = 4                 

 

      i0 = 2      n =3                  n = 2                      n = 1          j4 = 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. Расчет всех значений выполним в виде таблицы 4.2.

 

 

Таблица 4.2

     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. Расчет всех значений выполним в виде таблицы. Таб. 4.3

        Таблица 4.3

     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 +xd3)),  где i уровень запаса сырья на начало предпоследнего месяца может принимать значение 2, а  x будет равняться  7, 6, 5, 4 , 3, 2, 1. Расчет всех значений выполним в виде таблицы. Таб. 4.4

      Таблица 4.4

     x

i    

1

2

3

4

5

6

7

x4(i)

f4(х)

i0 = 2     

5+0+17

6+1+16

7+2+15

8+3+14

9+4+13

10+5+8

11+6+8

1

22

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

       Минимальные затраты, связанные с производством и хранением продукции за три месяца, составят 22 единицы.

Имя файла: mathprog5.doc

Размер файла: 55.5 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке