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) + В2{х2) | х2 = /2(хьи2)}, 112
причем 0 ^ и2 ^ х,\. Учитывая условие В2(х2) = 0, явный вид функции 22(х1,«2) и область изменения переменной и2, получаем:
£1(^1)= пжх {Р1(и2) + Р2(х1-и2)}.
Конкретизируем вид функций Р\ (у) и Р2(у), полагая
Р^у) = КхН(у), Р2(у) = К2Н(у),
где Н(у) = у/у, а К\ и К2 — некоторые положительные коэффициенты производительности, значения которых мы выберем позже. В этом случае
В1(х1)= тах + К2у/XI - и2}.
Отметим, что функция Н(у) = у/у обладает следующими свойствами, имеющими естественную экономическую интерпретацию и характерными для так называемых производственных функций.
Свойство функции |
Экономическая интерпретация |
Функция у/и определена при у ^ 0 |
Объемы ресурсов не могут принимать отрицательных значений |
Функция у/и положительна и обращается в 0 при у = 0 |
Предприятие получает прибыль при выделении ему некоторого объема ресурсов и не получает прибыли при отсутствии ресурсов |
Функция у/у монотонно возрастает |
Прибыль, получаемая предприятием, возрастает при увеличении объема выделяемых ему ресурсов |
Производная (у/у)' = 1 /2у/у функции у/у монотонно убывает (иначе, функция у/и является выпуклой вверх) |
Темпы роста прибыли, получаемой предприятием, снижаются при увеличении объема выделяемых ему ресурсов (иначе, чем больше объем выделяемых предприятию ресурсов, тем меньший абсолютный прирост прибыли дает выделение одной дополнительной единицы ресурса) |
Последнее свойство представляет собой важное положение экономической теории, хорошо подтверждается практикой и называется законом убывающей эффективности.
Найдем максимум на отрезке [0, жх] функции
С2(и2) = К\у/щ. + К2у/х\ - и2,
применяя для этого известные методы дифференциального исчисления. Производная ^ ^
С'2М = - 2
функции С2(и2) является монотонно убывающей на интервале (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у/й2(х1) + К2\/х1 - й2(жх) =
= К1\1кТ$к!Х1 + К2\1Х1 - кТТкё*1 =
где К = у/ЩТЩ-
Тем самым расчеты на данном шаге завершены. Обсудим полученные промежуточные результаты.
1. Функция Беллмана В\(х\) не зависит от функций <5х(^) и С22(у), определяющих затраты ресурсов на предприятиях; это представляется вполне логичным, поскольку по условию задачи после рассматриваемого последнего шага объемы оставшихся неизрасходованными ресурсов во внимание не принимаются и не подлежат дальнейшему перераспределению.
2. Если выделить весь имеющийся объем Жх ресурсов только одному предприятию П\ ИЛИ П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) + Р2(х0 - щ) + В^х^}, 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 = у >
а функция Беллмана имеет вид
В0(х0) = + К2^х о + а2)х0 + (а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. Как видно из решения задачи, на каждом шаге этапа условной оптимизации расчет функций Беллмана становится все более сложным: если В2(х2) равняется 0, Вх (хх) достаточно просто вычисляется в явном виде, то функцию Во(хо) в общем случае в явном виде нам вычислить так и не удалось. Такое усложнение является закономерностью метода ДП, подчеркивая важность не только аналитических вычислений, но и численных расчетов с использованием ЭВМ.
Замечание 2. Выбранный вид производственной функции Н(у) = гарантировал нам наличие точек максимума исследуемых функций внутри отрезка изменения аргумента. Иной выбор производственной функции может привести к тому, что максимум будет достигаться на концах отрезка. Соответствующие ситуации возникают при решении отдельных вариантов приведенных ниже задач для самостоятельного решения.
Задание. Провести сопоставление полученного оптимального решения со следующими тремя допустимыми решениями, первое из которых реализует стратегию выделения всех ресурсов на обоих шагах только предприятию П\, второе — только предприятию П2, третье —
стратегию равного выделения ресурсов обоим предприятиям. Вычислить, сколько процентов прибыли теряется в каждом из этих случаев.
Задачи для самостоятельного решения
2.1. Решить задачу о распределении инвестиций между предприятиями П\, П-2 и Яз. Инвестируется сумма 6 усл. ден. ед. Сопоставить полученные оптимальные решения с решениями, предписывающими выделение всего объема инвестиций только одному из предприятий либо распределение инвестиций поровну между всеми предприятиями, и вычислить, сколько процентов прибыли теряется в каждом из этих случаев. Варианты исходных данных задачи приведены ниже в табл. 2.1.
Таблица 2.1
|
2.2. Решить задачу о-распределении инвестиций между предприятиями Пх, П2 и Я3 по максимуму нормы прибыли. Инвестируется сумма от 3 до 6 усл. ден. ед. Сопоставить полученные оптимальные решения с решениями, предписывающими выделение всего объема инвестиций только одному из предприятий либо распределение 3 или 6 усл. ден. ед. поровну между всеми предприятиями. Вычислить, на сколько процентов снижается норма ирибыли в каждом из этих случаев. Варианты исходных данных —в табл. 2.1.
Решить задачи 2.1 и 2.2 при дополнительном условии, что каждому предприятию должно быть выделено не менее 1 усл. ден. ед. инвестиций.
2.3. Решить задачу о загрузке транспортного средства с вариантами исходных данных, представленными в табл. 2.2. Сопоставить полученные оптимальные решения с решениями, предписывающими погрузку предметов только одного типа, и вычислить, сколько процентов стоимости перевозимого груза теряется в каждом из этих случаев.
Таблица 2.2
|
2.4. Решить задачу о замене оборудования в следующей постановке. Руководство планирует деятельность предприятия на 5 лет. Установленное на предприятии оборудование в начале каждого года может быть продано по остаточной стоимости и заменено новым, приобретаемым по рыночной стоимости. Прогнозируемая рыночная стоимость оборудования М и стоимость С одной усл. ед. продукции предприятия (усл. ден. ед.) в зависимости от номера года (от 1 до 5) известна. Характеристики оборудования, к которым относятся производительность Р (усл. ед. продукции в год) и затраты на эксплуатацию <2 (усл. ден. ед. в год), зависят от его наработки (под наработкой оборудования будем понимать число полных лет его эксплуатации). Оборудование может эксплуатироваться только при наработке, не превышающей 3 года. Остаточная стоимость оборудования равна стоимости, по которой приобреталось оборудование, уменьшаемой на 20 % от исходного значения за каждый год эксплуатации. Замена оборудования связана с накладными расходами, составляющими 30 % от стоимости приобретаемого оборудования. В начале планируемого периода установленное на предприятии оборудование имеет наработку .то лет, а приобреталось оно по цене Мо-
Требуется определить оптимальную стратегию обновления оборудования на 5 лет с целью достижения максимального суммарного экономического эффекта за весь планируемый период. Сопоставить полученное оптимальное решение с двумя допустимыми решениями, первое из которых реализует стратегию максимально частого обновления оборудования, а второе — стратегию максимального откладывания обновления.
Провести решение задачи со следующими вариантами исходных данных:
— стоимость изначально установленного оборудования Мо = 400;
— изначальная наработка оборудования хц = 1; 2; .3;
— стоимость оборудования М, стоимость единицы продукции С и характеристики оборудования Р и С} имеют значения, представленные в табл. 2.3.
Таблица 2.3
|
Указание. В данной задаче частный экономический эффект г, определяется по формуле
_ Г 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
25 26 27 Наверх ↑