2.5. Задача о распределении ресурсов

Условие задачи. Производственное объединение, в которое вхо­дят два предприятия П\ и П2, планирует свою работу на двухлет­ний период. В ходе работы предприятия получают прибыль, расходуя при этом некоторые ресурсы. Для обеспечения работы предприятий в начале каждого года им выделяются необходимые объемы ресурсов, а в конце года оставшиеся неизрасходованными ресурсы изымаются и перераспределяются. -

Требуется найти оптимальную стратегию распределения ресур­сов, т. е. определить, сколько ресурсов необходимо выделять каждому предприятию в начале каждого года для получения максимальной сум­марной прибыли по всему производственному объединению за два года.

Будем считать, что общий начальный объем ресурсов в производ­ственном объединении равен V > 0 усл. ед. Все имеющиеся ресурсы объединения распределяются между двумя предприятиями полностью. При выделении предприятиям Г1] и П2 ресурсов в объеме V усл. ед. они получают прибыль, равную Р\(ь) и Р<2(«) усл. ден. ед., расходуя при этом ресурсы в объеме С}\{и) и С}2(г;) усл. ед. соответственно. Будем считать выполняющимися естественные условия

Рк(у) >0, 0 < Як{у) ^у для к = 1,2.

Решение. В данной задаче управляемой системой является рас­сматриваемое производственное объединение, многошаговым процес­сом— процесс распределения ресурсов между предприятиям. Эконо­мический эффект представляет суммарная величина прибыли, и при этом задача решается на поиск максимума. Проведем математическую формализацию поставленной задачи.

1.               Число шагов N в данной задаче следует принять равным 2 по числу лет в планируемом периоде.

2.               В качестве фазовых переменных х\ и примем суммарный объем ресурсов, остающихся в производственном объединении по про­шествии первого и второго годов его работы соответственно. Начальное состояние системы характеризуется значением хо = V.

3.               В качестве управляющей переменной и примем объем ресурсов, выделяемых предприятию П\ на каждом из шагов процесса. Именно, переменные и\ И «2 представляют объемы ресурсов, выделяемых пред­приятию П\ в начале первого и второго годов. Переменная иг, г = 1,2, может принимать бесконечное множество различных значений из от­резка [0,хг_\]. Соответственно предприятию 772 остается х^—щ усл. ед. ресурсов в начале первого года и х\ — и2 усл. ед. в начале второго года.

4.               Функция процесса хг = /Джг-ьщ), определяющая закон изме­нения состояния производственного объединения, для данной задачи представляется формулой

Хг = Хг-1 - {Я\{щ) + С?2(Жг-1 ~ Щ))

и имеет следующий смысл: за год с номером г суммарный началь­ный объем ресурсов хг _ 1 производственного объединения уменьшается на величину его расхода

+         - Щ)

на обоих предприятиях. В силу неотрицательности функций и (^2 имеет место соотношение Хг "С

5.               Функция 2г, определяющая частный экономический эффект на шаге с номером г, вычисляется по формуле

= Р\{Щ) + Р2(Жг_1 - щ).

На этом математическая формализация поставленной задачи за­вершена. Основные допущения метода ДП при этом выполняются: отсутствие последействия следует из явных формул для вычисления Xi и Zi, а аддитивность целевой функции

2 = 21 + 22

обусловлена самой постановкой задачи.

Тем самым можно непосредственно приступить к решению задачи методом ДП. В ходе решения мы будем постепенно конкретизировать исходные данные задачи; этот подход позволит разумно совместить рассмотрение общей постановки задачи с получением простых и нагляд­ных ответов, доведенных до определенных числовых значений. При этом будут выявляться наиболее сложные моменты в решении задачи.

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

Предварительный этап в данной задаче является малоинфор­мативным и сводится, по существу, к установлению соотношений

О ^ Х2 ^ XI ^ х0 = V,

О ^ Щ ^ Жг_1.

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

Этап условной оптимизации. На данном этапе для г = 2,1 про­водится вычисление функций Беллмана В^х^) и условно-оптимальных управлений щ(Хг-1). Расчеты начинаются с условия В2{х2) = 0.

г = 2. .

В начале данного шага общий объем ресурсов производственного объединения равен некоторому пока неизвестному значению х,\ ^ 0. Запишем основное функциональное уравнение Беллмана для этого последнего шага:

В1{х1) = тах{22(х1,и2) + В22) | х2 = /2ьи2)}, 112

причем 0 ^ и2 ^ х,\. Учитывая условие В22) = 0, явный вид функции 22(х1,«2) и область изменения переменной и2, получаем:

£1(^1)= пжх12) + Р2(х12)}.

Конкретизируем вид функций Р\ (у) и Р2(у), полагая

Р^у) = КхН(у), Р2(у) = К2Н(у),

где Н(у) = у/у, а К\ и К2 — некоторые положительные коэффициенты производительности, значения которых мы выберем позже. В этом случае

В11)= тах                         + К2у/XI - и2}.

Отметим, что функция Н(у) = у обладает следующими свой­ствами, имеющими естественную экономическую интерпретацию и ха­рактерными для так называемых производственных функций.

Свойство функции

Экономическая интерпретация

Функция у/и определена при у ^ 0

Объемы ресурсов не могут принимать отрицательных значений

Функция у/и положительна и обращается в 0 при у = 0

Предприятие получает прибыль при выделении ему некоторого объема ресурсов и не получает прибыли при отсутствии ресурсов

Функция у/у монотонно возрастает

Прибыль, получаемая предприятием, возрастает при увеличении объема выделяемых ему ресурсов

Производная (у/у)' = 1 /2у/у функции у/у монотонно убывает (иначе, функция у/и является выпуклой вверх)

Темпы роста прибыли, получаемой пред­приятием, снижаются при увеличении объема выделяемых ему ресурсов (иначе, чем больше объем выделяемых предприятию ресурсов, тем меньший абсолютный прирост прибыли дает выделение одной дополнительной единицы ресурса)

 

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

Найдем максимум на отрезке [0, жх] функции

С22) = К\у/щ. + К2у/х\ - и2,

применяя для этого известные методы дифференциального исчисления. Производная          ^                                            ^

С'2М = - 2

функции С22) является монотонно убывающей на интервале (0,Х\), причем ее односторонние пределы на концах интервала имеют следу­ющие бесконечные значения:

lim G'9(u2) = ^ lim jL= - -Д|= = +оо,

U2-^0+0             '      2 u2->0+0 y/Ü2

lim G'2(u2) = 7T1= ~ Iim 1 =

u2—Zy/Xi 2 u2>xx-0 y/X\ U2

к г  К2

Это означает, что функция G2(u2) принимает свое максимальное зна­чение в единственной точке, лежащей внутри отрезка [0, жх]. Для поиска точки максимума решим уравнение

G'2(u2) = 0, или

2ч/г^ 2у/хг - и2 '

Мхі) = 1РГТ172х 1-

Решение этого уравнения относительно переменной и2 и представляет собой условно-оптимальное значение «2(жх) управления на данном шаге:

К1 К1 + КГ

В соответствии со сказанным, функция Беллмана В\(х\) имеет вид: В1 (жх) = К1у/й21) + К2\/х1 - й2(жх) =

= К1\1кТ$к!Х1 + К2\1Х1 - кТТкё*1 =

где К = у/ЩТЩ-

Тем самым расчеты на данном шаге завершены. Обсудим полу­ченные промежуточные результаты.

1.               Функция Беллмана В\(х\) не зависит от функций <5х(^) и С22(у), определяющих затраты ресурсов на предприятиях; это представля­ется вполне логичным, поскольку по условию задачи после рассмат­риваемого последнего шага объемы оставшихся неизрасходованными ресурсов во внимание не принимаются и не подлежат дальнейшему перераспределению.

2.               Если выделить весь имеющийся объем Жх ресурсов только од­ному предприятию П\ ИЛИ П2, то полученная объединением прибыль составит Рх(жх) = К\у[х{ или Р2(х\) = К/ж7, что в любом случае меньше значения ^(жх) = К у/жх; это замечание еще раз на кон­кретном примере подтверждает оптимальность функций Беллмана. Переходим к следующему шагу.

г = 1.

В начале этого шага общий объем ресурсов производственного объ­единения равен значению ж0 = V, причем 0 ^ щ ^.жо. Запишем

основное функциональное уравнение Беллмана для данного шага: -Во(^о) = max{2i(x0,ui) + Bi(xi) \ xi = /1(^0,^61)}-

ui

Учитывая вид функций fi(x0,ui) и z\(xo,u\), получаем: В0о) = max {Pi(ui) + Р20 - щ) + В^х^}, xi = х0- Q\{ui) - Q2{xо - щ).

Конкретизируем вид функций Qi(v) и Q2(v), полагая

Qi(v) = aiv, Qi{v) = a2v,

где a\ и а2 — некоторые коэффициенты потребления ресурсов из интер­вала (0,1), значения которых мы выберем позже. В результате получим:

В0о) = max Gi(ui),

где

Gi(ui) = Kiy/щ + K2VX0 -Щ+ - a-2)xo + (ß2 - ai)«i. Найдем максимум на отрезке [0,хо] функции Gi(u\). Производная С(и)= Kl - К2 +___ K{a2-ai)______

1 1> 2у/Щ 2^х0 - иг 2у/(1 - a2)x0 + (а2 - ai)«i'

как и производная функции (^(«г), является монотонно убывающей на интервале (0,.то), причем ее односторонние пределы на концах интервала имеют бесконечные значения:

lim G'^ui) = +00, lim G'^ui) = —00. u\—»0+0    itj—>xq—0

Как и выше, это означает, что функция G\(u\) принимает свое максимальное значение в единственной точке, лежащей внутри от­резка [0,xq\. Для поиска точки максимума необходимо решить уравне­ние G\ (щ) = 0, однако это является уже непростой задачей. Решение этого уравнения можно свести к отысканию корней многочлена чет­вертой степени и воспользоваться методом JI. Феррари1', однако этот способ является весьма громоздким и недостаточно наглядным.

Мы поступим иным образом и подберем значения постоянных Ki,K2, аi,a,2 так, чтобы уравнение G\ (щ) = 0 имело корень щ — xq/2. Экономический смысл этого равенства заключается в том, что на пер­вом шаге все ресурсы производственного объединения В объеме Хо

JI. Феррари — итальянский математик XVI в.делятся поровну между обоими предприятиями. Полагая щ = х

/2 в выражении для С[ («1), получим условие

- К2 _                                      - а2

К ~ у/2 - (<ц + а2)'

Рассмотрим экономический смысл полученного условия. Пусть вы­полняется соотношение а\ < а2, т. е. предприятие 771 более экономно расходует ресурсы, чем 772. Тогда выражение в правой части по­следнего равенства является отрицательным; при этом и левая часть тоже должна быть отрицательной. Следовательно, для существования искомого корня должно выполняться соотношение К\ < К2, которое показывает, что предприятие 77] дает меньшую прибыль при одина­ковых объемах ресурсов, чем П2. Это представляется вполне зако­номерным, поскольку распределять ресурсы поровну в случае, когда предприятие 771 одновременно и более экономное, и более прибыльное, совершенно нецелесообразно — этому предприятию следует выделить большую часть ресурсов.

Легко проверить, что рассматриваемому условию удовлетворяют, например, следующие значения постоянных:

#1 = 3, #2 = 4, а1 = 0,4, а2 = 0,6. Тем самым расчеты на шаге г = 1 с функциями

= Р2(и) = 4^, (?!(«) = 0,4и, д2(^) = 0,6г;

можно считать законченными. При этом

Ы

х0 = у >

а функция Беллмана имеет вид

В00) =        + К2^х о +                    а20 + (а2 - <ц) Ц =

= {Кг +К2 + Ку/2 - а1 - «2) = бу/2^.

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

Этап безусловной оптимизации. Полагая = жо = V, опре­деляем максимальное значение целевой функции:


V

У 2

и\ = йх(4) = йх(у) = —,

4 = 4 ~ (діК) + }2Ъ - О)        (V - |

* у

г = 2:    = —,


59

4 = 4" (Єі(«2) + ^2(4 - «2)) = т-У.

На этом построение оптимального решения, этап условной опти­мизации и все решение задачи завершены.

Ответ: для достижения максимальной прибыли производственного объединения необходимо в первом году выделить предприятиям П\ и П2 по 50 % ресурсов, а во втором году — соответственно 9/25 = 36% и 64% от оставшегося после первого года объема ресурсов.

Замечание 1. Как видно из решения задачи, на каждом шаге этапа условной оптимизации расчет функций Беллмана становится все более сложным: если В22) равняется 0, Вхх) достаточно про­сто вычисляется в явном виде, то функцию Во(хо) в общем случае в явном виде нам вычислить так и не удалось. Такое усложнение яв­ляется закономерностью метода ДП, подчеркивая важность не только аналитических вычислений, но и численных расчетов с использова­нием ЭВМ.

Замечание 2. Выбранный вид производственной функции Н(у) = гарантировал нам наличие точек максимума исследу­емых функций внутри отрезка изменения аргумента. Иной выбор производственной функции может привести к тому, что максимум будет достигаться на концах отрезка. Соответствующие ситуации воз­никают при решении отдельных вариантов приведенных ниже задач для самостоятельного решения.

Задание. Провести сопоставление полученного оптимального ре­шения со следующими тремя допустимыми решениями, первое из ко­торых реализует стратегию выделения всех ресурсов на обоих шагах только предприятию П\, второе — только предприятию П2, третье —

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

Задачи для самостоятельного решения

2.1. Решить задачу о распределении инвестиций между предприяти­ями П\, П-2 и Яз. Инвестируется сумма 6 усл. ден. ед. Сопоставить полученные оптимальные решения с решениями, предписывающими выделение всего объема инвестиций только одному из предприятий либо распределение инвестиций поровну между всеми предприяти­ями, и вычислить, сколько процентов прибыли теряется в каждом из этих случаев. Варианты исходных данных задачи приведены ниже в табл. 2.1.

Таблица 2.1

№ вари­анта

Объем инвестиций

0

1

2

3

4

5

6

Ожидаемая прибыль предприятий, Пх / П2 / Дз

1

-3/3/-4

16/14/6

21/26/23

32/31/34

47/48/49

52/53/57

64/62/65

2

-1/2/2

9/12/7

24/27/18

35/30/33

46/43/45

60/58/59

63/61/69

3

1/-1/5

11/8/13

27/25/28

31/39/36

44/47/41

53/56/55

67/74/76

4

-2/1/3

18/6/10

26/24/22

29/38/35

43/46/45

54/52/56

73/76/68

5

-3/-5/-6

13/7/8

31/29/28

34/42/37

55/58/54

70/60/71

75/81/84

6

0/-1/6

9/18/19

27/26/31

40/36/43

57/49/56

65/68/66

79/75/83

7

1/1/4

18/8/11

32/23/25

44/35/48

63/62/52

76/73/75

77/82/85

8

3/1/1

17/15/12

24/27/30

38/41/43

54/61/56

71/75/74

86/80/81

9

7/4/5

11/14/15

33/28/36

44/45/46

51/59/64

72/81/69

91/89/84

10

0/-4/-1

10/17/13

29/37/35

51/49/47

60/55/61

77/79/74

83/88/93

 

2.2. Решить задачу о-распределении инвестиций между предприя­тиями Пх, П2 и Я3 по максимуму нормы прибыли. Инвестируется сумма от 3 до 6 усл. ден. ед. Сопоставить полученные оптимальные решения с решениями, предписывающими выделение всего объема инвестиций только одному из предприятий либо распределение 3 или 6 усл. ден. ед. поровну между всеми предприятиями. Вычислить, на сколько процен­тов снижается норма ирибыли в каждом из этих случаев. Варианты исходных данных —в табл. 2.1.

Решить задачи 2.1 и 2.2 при дополнительном условии, что каж­дому предприятию должно быть выделено не менее 1 усл. ден. ед. инвестиций.

2.3. Решить задачу о загрузке транспортного средства с вариантами исходных данных, представленными в табл. 2.2. Сопоставить получен­ные оптимальные решения с решениями, предписывающими погрузку предметов только одного типа, и вычислить, сколько процентов сто­имости перевозимого груза теряется в каждом из этих случаев.

Таблица 2.2

№ варианта

М

Ті

т2

Т3

771

г

771

г

771

г

1

76

11

19

16

28

25

45

2

77

12

20

17

29

26

46

3

79

12

21

16

30

26

47

4

83

12

22

17

31

27

48

5

84

13

23

18

32

28

49

6

85

13

25

19

33

29

51

7

87

14

25

19

34

30

53

8

89

15

26

20

35

31

55

9

92

15

28

19

36

32

57

10

93

16

29

21

36

33

60

 

2.4. Решить задачу о замене оборудования в следующей постановке. Руководство планирует деятельность предприятия на 5 лет. Установ­ленное на предприятии оборудование в начале каждого года может быть продано по остаточной стоимости и заменено новым, приобрета­емым по рыночной стоимости. Прогнозируемая рыночная стоимость оборудования М и стоимость С одной усл. ед. продукции предприятия (усл. ден. ед.) в зависимости от номера года (от 1 до 5) известна. Харак­теристики оборудования, к которым относятся производительность Р (усл. ед. продукции в год) и затраты на эксплуатацию <2 (усл. ден. ед. в год), зависят от его наработки (под наработкой оборудования будем понимать число полных лет его эксплуатации). Оборудование может эксплуатироваться только при наработке, не превышающей 3 года. Остаточная стоимость оборудования равна стоимости, по которой при­обреталось оборудование, уменьшаемой на 20 % от исходного значения за каждый год эксплуатации. Замена оборудования связана с наклад­ными расходами, составляющими 30 % от стоимости приобретаемого оборудования. В начале планируемого периода установленное на пред­приятии оборудование имеет наработку .то лет, а приобреталось оно по цене Мо-

Требуется определить оптимальную стратегию обновления обору­дования на 5 лет с целью достижения максимального суммарного экономического эффекта за весь планируемый период. Сопоставить полученное оптимальное решение с двумя допустимыми решениями, первое из которых реализует стратегию максимально частого обновле­ния оборудования, а второе — стратегию максимального откладывания обновления.

Провести решение задачи со следующими вариантами исходных данных:

               стоимость изначально установленного оборудования Мо = 400;

               изначальная наработка оборудования хц = 1; 2; .3;

               стоимость оборудования М, стоимость единицы продукции С и характеристики оборудования Р и С} имеют значения, пред­ставленные в табл. 2.3.

Таблица 2.3

№ вари­анта

Стоимость оборудования и единицы продукции в зависимости от номера года, М/С

Характеристики оборудования в зависимости от его наработки, Р/<5

1

2

3

4

5

0

1

2

3

1

495/10

545/11

585/12

630/13

680/15

75/100

75/110

70/130

60/150

2

505/11

560/12

615/13

655/14

705/16

76/105

75/110

72/135

64/160

3

520/11

565/12

620/13

670/15

710/16

78/105

77/115

73/140

65/165

4

535/12

580/13

630/14

675/15

730/17

80/110

78/120

75/140

68/170

5

550/12

595/14

640/15

700/16

750/18

82/115

80/120

76/145

70/175

 

Указание. В данной задаче частный экономический эффект г, опре­деляется по формуле

_ Г 5 - М{г) + С (г) • Р(0) - <2(0) - 0,30 • М(г), щ = 3;

* ~ I                  " С (г) • Р(а*_1) - Я{хг-Х), щ = С,

в которой остаточная стоимость

5 = Ж - (1 -0,20-Ж;_1),

где М представляет стоимость, по которой приобреталось оборудова­ние, и вычисляется по формуле

ГМ(г -

\                                    М0, Хг-1 > г - 1.

Доказать, что неравенство хг > г эквивалентно условию отсутствия обновления оборудования за период с 1-го по г-й год включительно.

2.5. Решить задачу о распределении ресурсов со следующими ва­риантами исходных данных:

               число шагов N = 2, производственная функция Н(у) — 1п(1 + (,'); число шагов N — 4, производственная функция Н(у) = у2 (по­следняя производственная функция не подчиняется закону убы­вающей эффективности, но является весьма простой и допускает построение явных решений для любого числа шагов 7\Г);

               начальный объем ресурсов V = 1; 10; 100 усл. ед.;

               коэффициенты производительности К\ = 20, К2 = 5; 10; 20; 40; 80;

               коэффициенты потребления ресурсов:

аі

а2

0,1

0,3; 0,5; 0,7; 0,9

0,3

0,5; 0,7; 0,9

0,5

0,7; 0,9

0,7

0,9

 

2.6. Решить задачу о распределении ресурсов с резервированием в следующей постановке. Руководство планирует работу предприя­тия на период в N лет. В ходе работы предприятие получает при­быль, расходуя при этом некоторые ресурсы. В начале каждого года часть имеющихся на предприятии ресурсов включается в производство, а остальная часть ресурсов резервируется. Начальный объем ресур­сов на предприятии равен V усл. ед. При включении в производство ресурсов в объеме у усл. ед. предприятие получает прибыль, равную Р(у) = КН(у) усл. ден. ед., и при этом расходует (}(у) = ау усл. ед. ресурсов (здесь Н{у) — производственная функция, К — коэффициент производительности, а — коэффициент потребления ресурсов).

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

(Заметим, что данная задача легко сводится к рассмотренной выше задаче о распределении ресурсов, если ввести второе «фиктивное» пред­приятие 77г, которое не дает прибыли и не потребляет ресурсов, т. е. характеризуется коэффициентами К2 = 0 и а2 = 0, а резервирование трактовать как направление ресурсов этому «фиктивному» предприя­тию. Тем самым данная задача проще рассмотренной выше и, в част­ности, допускает аналитические решения при большем числе шагов и в более широком классе производственных функций.)

Провести решение задачи со следующими вариантами исходных данных:

               число шагов N = 2; 3; 4;

                                                                                                                    производственная функция Н(у) — V2;     1п(1 + и); 1 —

               начальный объем ресурсов V = 1; 10; 100 усл. ед.;

               коэффициент производительности К = 5; 10; 20; 40; 80;

коэффициент потребления ресурсов а = 0,1; 0, 3; 0, 5; 0, 7; 0,9.Глава 3

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27  Наверх ↑