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

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

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

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

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

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

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

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

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

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

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

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

+         - Щ)

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

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

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

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

2 = 21 + 22

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

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

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

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

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

О ^ Щ ^ Жг_1.

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

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

г = 2. .

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

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

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

£1(^1)= пжх {Р₁(и₂) + Р2(х₁-и₂)}.

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

Р^у) = К_хН(у), Р₂(у) = К₂Н(у),

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

В₁(х₁)= тах                         + К₂у/XI - и₂}.

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

 

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

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

С₂(и₂) = К\у/щ. + К₂у/х\ - и₂,

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

^С'^{2М =} - 2

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

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

U2-^0+0             '      2 u₂->0+0 y/Ü2

lim G'₂(u₂) = 7T1= ~ ^{Iim 1} =

u₂—Zy/Xi 2 u₂—>x_x-0 y/X\ — U2

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

G'₂(u₂) = 0, или

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

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

К1 К1 + КГ

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

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

где К = у/ЩТЩ-

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

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

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

г = 1.

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

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

ui

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

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

Qi(v) = aiv, Qi{v) = a₂v,

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

В₀(хо) = max Gi(ui),

где

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

^{1 1>} 2у/Щ 2^х₀ - и_г 2у/(1 - a₂)x₀ + (а₂ - ai)«i'

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

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

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

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

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

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

- К2 _                                      - а₂

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

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

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

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

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

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

х₀ = у >

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

В₀(х₀) =        + К₂^х о +                    а₂)х₀ + (а₂ - <ц) Ц =

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

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

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

V

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

4 = 4 ~ (діК) + €}₂{хЪ - О)        (V - |

* ^у

г = 2:    = —,

59

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

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

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

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

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

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

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

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

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

 

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

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

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

ГМ(г -

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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