ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. РАСПРЕДЕЛЕНИЕ КАПИТАЛЬНЫХ ВЛОЖЕНИЙ

Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 50 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 50 тыс. руб.                                                                              Таблица I

 

Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1( - x2) = f1(- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.

Продолжая процесс, табулируем функции F3(), () и т.д. В табл. 6 заполняем только одну диагональ для значения = 700.

Таблица 2

 - x2 0 100 200 300 400 500 600 700

x2    F1( - x2)

F2(x2) 0 15 24 30 36 40 43 45

0

0      0 15 24 30 36 40 43 45

100  18   18* 33* 42* 48 54 58 61

200  26   26 41 50* 56 62 66

300  34   34 49 58* 64* 70*

400  39   39 54  63 69

500  42   42 57  66

600  44   44 59

700  46   46

                                                                                                                   

Таблица 3

     0 100 200 300 400 500 600 700

F2() 0  18  33  42    50  58  64  70

 ()

0    0 100 100 200 300 300 300

Таблица 4

 - x3 0 100 200 300 400 500 600 700

x3    F2( - x3)

F3(x3) 0 18  33 42 50 58 64 70

0

0      0 18* 33 42 50 58 64 70

100  16   16 34* 49* 58 66 74 80

200  27   27 45  60* 69 77 85

300  37   37 55      70* 79* 87*

400  44   44 62 77 86

500  48   48 66 81

600  50   50 68

700  56   56                                                             

 

Таблица 5

     0 100 200 300 400 500 600 700

F3() 0  18  34  49  60  70  79 87

 ()

0   0 100 100 200 300 300 300

Таблица 6

 - x4 0 100 200 300 400 500 600 700

x4    F3( - x4)

F4(x4) 0 18 34 49 60 70 79 87

0      0                                                                      87

100  10                                                            89*

200  17                                                  87

300  23                                          83

400  29                               78

500  34                     68

600  38           56

700  41   41                                                       .

Наибольшее число на этой диагонали: Zmax = 89 тыс. руб.,

причем четвертому предприятию должно быть выделено х*4 = 4 (700) = 100 тыс. руб.

На долю остальных трех предприятий остается 600 тыс. руб. Из табл. 5 видно, что третьему предприятию должно быть выделено x*3 = 3 (700-x*4) = 3 (600) = 300 тыс. руб.

Продолжая обратный процесс, находим        x*2 = 2 (700 - x*4 - x*3) = 2 (300) = 100 тыс. руб.

На долю первого предприятия остается x*1 = 700 - x*4 - x*3 - x*2 = 200 тыс. руб.

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

x*1 =200; x*2 =100; x*3 = 300; x*4 = 100.

Оно обеспечивает производственному объединению наибольший воможный прирост прибыли 89 тыс. руб.

выполнение равенства: f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max

                                                           24+18+37+10=89

ДИНАМИЧЕСКАЯ ЗАДАЧА УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ И ЗАПАСАМИ

Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.

Пусть спрос (заявки) потребителей на нашу продукцию составляют: на первый этап d1=3 единицы, на второй – d2=2, на третий - d3=3 единицы. К началу первого этапа на складе имеется 3 единицы продукции, т.е. начальный уровень запаса равен y1=3. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h1=4, h2=3, h3=2. Затраты на производство xj единиц продукции на j-м этапе определяются функцией j(xj) = xj2 + 2xj + 2                                                       

т.е. а=1; b=5; с=2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.

Исходные данные задачи можно кратко записать одной строкой:

d1   d2   d3              a     b     c                 h1   h2   h3               y1

3     2     3                 1     2     2                 4     3     2                 3

Воспользовавшись рекуррентными соотношениями, последовательно вычисляем F1 ( = y2), F2 ( = y3), ..., Fk ( = yk+1), ... и соответственно находим   1 (= y2), 2 ( = y3 ), ...,  k ( = yk+1), ...

Положим k = 1.

Параметр состояния  = у2 может принимать целые значения на отрезке

0 у2 d2 + d3    0 y2 2 + 3 т.е. у2 = 0, 1, 2, 3, 4, 5.

Каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием 0 х1 d1 + у2 или 0 х1 3 + у2

Из балансового уравнения х1 + у1 - d1 = у2 непосредственно следует, что объем производства связан со значением параметра состояния = у2 соотношением

        x1 = y2 + d1 - y1 = y2 + 3 - 3 = y2                                           

В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому F1( = y2) = 1 (x1, y2)

Придавая у2 различные целые значения от 0 до 6 и учитывая предыдущее соотношение, находим

y2 = 0, x1 = 0, 1 (0;0) = 02 + 20 + 2 + 40 = 2*

y2 = 1, x1 = 1, 1 (1;1) = 12 + 22 + 2 + 41 = 11

y2 = 2, x1 = 2, 1 (2;2) = 22 + 22 + 2 + 42 = 18

y2 = 3, x1 = 3, 1 (3;3) = 32 + 23 + 2 + 43 = 29

y2 = 4, x1 = 4, 1 (4;4) = 42 + 24 + 2 + 44 = 42

y2 = 5, x1 = 5, 1 (5;5) = 52 + 25 + 2 + 45 = 57

Значения функции состояния F1( ) представлены в табл. 1

                                                                            Таблица 1

 = y2 0     1     2     3     4     5

F1 ( = y2)

2      11   18   29   42   57

x1(=y2)    0     1     2     3     4     5

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F2( = y3)

Здесь минимум берется по единственной переменной х2, которая может изменяться в пределах

0  x2  d2 + y3 или 0  x2  2 + y3                                (1)

где верхняя граница зависит от параметра состояния  = у3, который принимает значения на отрезке

0  y3  d3 , т.е. 0  y3  3                                                            

а аргумент у2 связан с х2 и у3 балансовым уравнением       x2 + y2 - d2 = y3 откуда следует   y2 = y3 + d2 - x2 = =y3 + 2 - x2  (2)

Придавая параметру состояния различные значения от 0 до 3, будем последовательно вычислять 2 (x2, ), а затем определять F2( ) и 2( ).        

Положим  = у3 = 0. Тогда, согласно (1), 0  x2  2, т.е. переменная х2 может принимать значения: 0, 1, 2, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 2 - х2

Последовательно находим:

если x2 = 0, то у2 = 2 ,        2 (0,2) = 02 + 20 + 2 + F1(2) = 2 + 18 = 20,

x2 = 1,   y2 = 2 - 1 = 1, 2 (1,2) = 12 + 51 + 2 + F1(1) = 8 + 11 = 19,

x2 = 2,   y2 = 2 - 2 =0, 2 (2,2) = 22 + 52 + 2 + F1(0) = 16 + 2 = 18*,

Наименьшее из полученных значений 2 есть F2 (0), т.е.

F2 ( = y3 = 0) = 18,

причем минимум достигается при значении х2, равном  2 ( = y3 = 0) = 2

Положим  = у3 = 1. Тогда, согласно (1), 0  x2  3, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 3 - х2

Последовательно находим:

если x2 = 0, то y2 = 3-0 = 3,  2 (0,1) = 02 + 20 + 2 + 31 + F1(3) = 5 + 29 = 34,

x2 = 1,   y2 = 3-1 = 2, 2 (1,2) = 12 + 21 + 2 + 31 + F1(2) = 8 + 18 = 26,

x2 = 2,   y2 = 3-2 = 1,   2 (2,1) = 22 + 22 + 2 + 31 + F1(1) = 13 +11 = 24,

x2 = 3,   y2 = 3-3 = 0, 2 (3,1) = 32 + 23 + 2 + 31 + F1(0) = 20 + 2 = 22*,

Наименьшее из полученных значений 2 есть F2 (1), т.е.

F2 ( = y3 = 1) = min 2 (x2,1) = 22,

причем минимум достигается при значении х2, равном  2 ( = y3 = 1) = 3

Положим  = у3 = 2. Тогда, согласно (1), 0  x2  4, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 4 - х2

если x2 = 0, то y2 = 4-0 = 4,  2 (0,2) = 02 + 20 + 2 + 32 + F1(4) = 8 + 42 = 50,

x2 = 1,   y2 = 4-1 = 3, 2 (1,2) = 12 + 21 + 2 + 32 + F1(3) = 11 + 29 = 40,

x2 = 2,   y2 = 4-2 =2,    2 (2,2) = 22 + 22 + 2 + 32 + F1(2) = 16 + 18 = 34,

x2 = 3,   y2 = 4-3 = 1, 2 (3,2) = 32 + 23 + 2 + 32 + F1(1) = 23 + 11 = 34*,

x2 = 4,    y2 = 4-4 = 0, 2 (4,2) = 42 + 24 + 2 + 32 + F1(0) = 32 + 2 = 40.

Наименьшее из полученных значений 2 есть F2 (2), т.е.

F2 ( = y3 = 2) = min 2 (x2,2) = min (64, 55, 50, 49, 52) = 49,

                               x2

причем минимум достигается при значении х2, равном  2 ( = y3 = 2) = 3

Положим  = у3 = 3. Тогда, согласно (1), 0  x2  5, т.е. переменная х2 может принимать значения: 0, 1, 2, 3, 4, 5, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (2): у2 = 5 - х2

если x2 = 0, то y2 = 5-0 = 5,  2 (0,3) = 02 + 20 + 2 + 33 + F1(5) = 11 + 57 = 68,

x2 = 1,   y2 = 5-1 = 4, 2 (1,3) = 12 + 21 + 2 + 33 + F1(4) = 14 + 42 = 56,

x2 = 2,   y2 = 5-2 = 3,   2 (2,3) = 22 + 22 + 2 + 33 + F1(3) = 19 + 29 = 48,

x2 = 3,   y2 = 5-3 = 2, 2 (3,3) = 32 + 23 + 2 + 33 + F1(2) = 26 + 18 = 44*,

x2 = 4,   y2 = 5-4 = 1,   2 (4,3) = 42 + 24 + 2 + 33 + F1(1) = 35 + 11 = 46.

x2 = 5,   y2 = 5-4 = 0,   2 (5,3) = 52 + 25 + 2 + 33 + F1(0) = 46 + 2 = 48.

Наименьшее из полученных значений 2 есть F2 (3), т.е.

F2 ( = y3 = 3) = min 2 (x2,3) = 44,

причем минимум достигается при значении х2, равном  2 ( = y3 = 3) = 3

Результаты табулирования функции F2 ( = y3)сведены в табл. 2.    

                                                                                                    Таблица 2

= у3 0     1     2     3

F2 (= y3) 18   22   34   44

 (= y3)

Или 3      3

 

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 ( = y4):

 

Вычисляем значение функции состояния только для одного значения аргумента  = у4 = 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода.

0y40; =y4; 0  x3  d3 + y4 → 0  x3  3; y3 = y4 + d3-x3= y4+3- x3;

3(x3, y4) = a + bx3 + c + h3y4 + F2(y3)= +2 x3+2 + 2 y4 + F2(y3)

x3=0       y3=3          3(0;0)=02 + 20 +2 +20 +F2(3)=2 +44=46

x3=1       y3=2          3(1;0)=12 + 21 +2+20 + F2(2)=5 +34=39

x3=2       y3=1          3(2;0)=22 + 22 +2+20 + F2(1)=10+22=32*

x3=3       y3=0          3(3;0)=32 + 23 +2+20 +F2(0)=17 +18=35

Получаем F3 ( = y4) = min 3 (x3,0) = 32, причем минимум достигается при  3 ( = y4 = 0) = 2.

Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения. Она равна = 2.

Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования. Чтобы найти предпоследнюю компоненту, учтем, что х3 + у3 - -d3 = y4 или 2 + у3 - 3 = 0, oткуда у3 = 1. Из таблицы (2) значений находим 

Аналогично, продолжая двигаться в обратном направлении и учтя, что х2 + у2 - d2 = y3 или 3 + у2 - 2 = 1, получаем у2 = 0; из таблицы (1) значений х1() находим .

Итак, оптимальный план производства имеет вид х1 = 0, х2 = 3, х3 = 2, а минимальные общие