Файл: Экономикоматематические методы и модели.pdf

93
f '
x1
(X
*
) = 0, i = 1, 2, ..., n.
Следовательно, точки экстремума функции Z = f(Х) удовлетворяют си- стеме уравнений:
{
(
)
(
)
(
)
(5.6)
Для получения достаточных условий следует определить в стационар- ной точке знак дифференциала второго порядка. Дифференциал второго по- рядка обозначается d
2
f (х
1
, х
2
, …, х
n
) f '
x1
(X) найти частную производную по переменной х
j
, то получим частную производную второго порядка по пере- менным х
i
, х
j
, которая обозначается f ''
xi, xj
(X). В этом случае
( ) ∑
∑
( )
. (5.7)
Достаточные условия экстремума.
Для двух переменных: еслиΔ > 0 и а
11
< 0 (а
22
< 0), то в точке Х
0
функция имеет максимум: если Δ
> 0 и а
11
> 0 (а
22
> 0),то в точке Х
0
– минимум (в этих случаях Х
0
= Х*); если Δ < 0, то экстремума нет; если Δ = 0, то вопрос об экстремуме остается открытым.
В общем виде задача НЛП описывается с помощью следующей модели
нелинейного программирования:
( )
( )
, (5.8) где х = (x
1
, х
2
, ..., х
n
) — вектор переменных задачи.
Задача (5.8) называется задачей НЛП в стандартной форме на макси-
мум. Можно так же сформулировать и задачу НЛП на минимум. Вектор х =
(x
1
, х
2
, ..., х
n
), компоненты х
j
которого удовлетворяют ограничениям
( )
, называется допустимым решением или допустимым планом задачиНЛП.
Совокупность всех допустимых планов называется множеством допусти-
мых планов. Допустимое решение задачи НЛП, на котором целевая функция
f(x) достигает максимального значения, называется оптимальным решением
ЗНЛП.
С точки зрения экономической интерпретации f(x) может рассматри- ваться как доход, который получает фирма (предприятие) при плане выпуска
х, а g
i
(х) ≤ 0 как технологические ограничения на возможности выпуска про- дукции. В данном случае они являются обобщением ресурсных ограничений в ЗЛП (а
i
х – b
i
≤ 0).
Электронный архив УГЛТУ

94
Эффективность алгоритма решения ЗНЛП может существенно зависеть от постановки задачи, от изменения масштабов измерения тех или иных пе- ременных. Поэтому алгоритмы ориентируются на решение определенного класса задач, и как правило, они не гарантируют правильность решения за- дач.
Перечислим основные свойства ЗНЛП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования:
1. Множество допустимых планов
x
может иметь очень сложную струк- туру (например, быть невыпуклым или несвязным).
2. Оптимум задачи может находиться как внутри области допустимых решений, так и на её границах (где он, вообще говоря, не будет совпадать ни с одним из локальных экстремумов).
3. Целевая функция может быть недифференцируемой, что затрудняет применение классических методов математического анализа.
В силу названных факторов задачи нелинейного программирования настолько разнообразны, что для них не существует общего метода решения.
5.2. Динамическое программирование.
Принципы построения динамических моделей
В отличие от статических, независимых от времени моделей динамиче- ские модели описывают экономические или управленческие процессы или системы в движении, то есть, в зависимости от временных периодов.
Динамическое программирование (ДП) - это метод оптимизации мно- гошаговых или многоэтапных процессов, критерий эффективности которых обладает аддитивным свойством (т.е. общий доход процесса равен сумме ло- кальных доходов на отдельных этапах). В задачах динамического програм- мирования критерий эффективности называется доходом.
Динамическое моделирование – многошаговый процесс, каждый шаг которого, соответствует поведению экономической системы в определенный временный период. Каждый текущий шаг получает результаты предыдущего шага, который по определенным правилам определяет текущий результат и формирует данные для следующего шага [10, 11].
Таким образом, динамическая модель позволяет исследовать развитие сложной экономической системы, например, предприятия, на протяжении определенного периода планирования в условиях изменения ресурсного обеспечения (сырья, кадров, финансов, техники), и полученные результаты представить в плане развития предприятия на заданный период.
Для решения динамических задач в математическом программировании сформировался соответствующий класс моделей под названием «Динамиче-
Электронный архив УГЛТУ

95 ское программирование», его основателем стал известный американский ма- тематик Р. Беллман. Им предложен специальный метод решения задач этого класса на основе «принципа оптимальности», согласно которому оптималь- ное решение задачи находится путем ее разбиения на n этапов, каждый из ко- торых представляет подзадачу относительно одной переменной. Расчет вы- полняется таким образом, чтобы оптимальный результат одной подзадачи являлся исходным для следующей подзадачи с учетом уравнений и ограни- чений связи между ними, а результат последней из них является результатом всей задачи. Данный метод по существу определяет порядок поэтапного решения задачи допускающей её декомпозицию (это более приемлемый путь, чем непосредственное решение задачи, в исходной постановке) с по- мощью рекуррентных вычислительных процедур [11].
Общим для всех моделей этой категории является то, что текущие управляющие решения «проявляются» как в период, относящийся непосред- ственно к моменту принятия решения, так и в последующие периоды. Следо- вательно, наиболее важные экономические последствия проявляются в раз- ные периоды, а не только в течение одного периода. Такого рода экономиче- ские последствия, как правило, оказываются существенными в тех случаях, когда речь идет об управляющих решениях, связанных с возможностью но- вых капиталовложений, увеличением производственных мощностей или обу- чением персонала с целью создания предпосылок для увеличения прибыль- ности или сокращения издержек в последующие периоды.
Принцип оптимальности Беллмана. Еще раз подчеркнем, что смысл подхода, реализуемого в динамическом программировании, заключен в за- мене решения исходной многомерной задачи последовательностью задач меньшей размерности.
Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход [11]:
1) объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями;
2) задача должна позволять интерпретацию как многошаговый процесс, каждый шаг которого состоит из принятия решения о выборе одного из до- пустимых управлений, приводящих к изменению состояния системы;
3) задача не должна зависеть от количества шагов и быть определенной на каждом из них;
4) состояние системы на каждом шаге должно описываться одинако- вым (по составу) набором параметров;
5) последующее состояние, в котором оказывается система после вы- бора решения на k-м шаге, зависит только от данного решения и исход- ного состояния к началу k-го шага; это свойство является основным с точки зрения идеологии динамического программирования и называется отсутствием последействия.
Электронный архив УГЛТУ

96
Типичными областями применения моделей динамического программи- рования при принятии решений являются:
● разработка правил управления запасами, устанавливающих момент по- полнения запасов и размер пополняющего заказа;
● разработка принципов календарного планирования производства и вы- равнивания занятости в условиях колеблющегося спроса на продукцию;
● определение необходимого объема запасных частей, гарантирующего эффективное использование дорогостоящего оборудования;
● распределение дефицитных капитальных вложений между возможными новыми направлениями их использованием;
● выбор методов проведения рекламной кампании, знакомящей покупа- теля с продукцией фирмы.
В задачах, решаемых методом динамического программирования, значе- ние целевой функции (оптимизируемого критерия) для всего процесса полу- чают простым суммированием частных значений f
i
(x) того же критерия на от- дельных шагах. То есть в задачах, решаемых методом динамического про- граммирования, значение целевой функции (оптимизируемого критерия) для всего процесса получают простым суммированием частных значений f
i
(x) того же критерия на отдельных шагах:
( ) ∑
( )
. (5.9)
Во многих практических задачах критерий F(x) аддитивен. Если в перво- начальной постановке задачи критерий не аддитивен, то постановку задачи надо изменить так, чтобы он стал аддитивным. К примеру, если рассматрива- ется критерий F (x), представленный в виде произведения выигрышей, дости- гаемых на отдельных этапах F(x) = f
1
(x) f
2
(x) ,..., f
m
(x) (такой критерий назы- вают мультиплексным), то можно просто преобразовать его к аддитивному, прологарифмировав выражение для F(x)
( ) ∑
( ). (5.10)
Обозначим V = lgF(x), V
j
= lgf
i
(x). Получим новый критерий
∑
, (5.11) обладающий свойством аддитивности и имеющий тот же оптимум, что и F(x).
Рассмотрим общую схему решения задач с аддитивным критерием.
Процесс управления состоит из m шагов. На каждом i-том шаге управление x
i
переводит систему из состояния S
i-1
, достигнутого в результате (i-1)-го шага,
Электронный архив УГЛТУ

97 в новое состояние S
i
, которое зависит от состояния S
i-1 и выбранного управ- ления х
i
,:
(
) (5.12)
Здесь существенно, чтобы новое состояние S
i
, зависело только от состо- яния S
i-1 и управления x
i
и не зависело от того, каким образом система при- шла в состояние S
i-1
. В крайнем случае, это достигается увеличением числа состояний системы (в понятие «состояние системы» входят те параметры, от которых зависит будущий результат).
Принцип оптимальности. Оптимальная стратегия обладает тем свой- ством, что, каковы бы ни были первоначальное состояние и решение, после- дующее решение должно определять оптимальную стратегию относительно состояния, полученного в результате предыдущего решения.
Рассмотрим задачу о максимизации целевой функции F(x) на m-шаговом процессе. Под влиянием управлений x
1
, х
2
,…,х
m
система переходит из началь- ного состояния S
0
в конечное S
кон
. За m шагов получают выигрыш (значение целевой функции)
( ) ∑
(
), (5.13) где
(S
i-1
, х
i
) - выигрыш на i-том шаге.
Принцип оптимальности позволяет заключить, что при любом началь- ном управлении х
i
имеет место соотношение
( )
(
) [
(
)
(
)]
(
)
[
(
) ] (5.14)
Поскольку это соотношение справедливо для всех начальных решений
x
1
, то, чтобы найти максимальный выигрыш, надо найти максимум по x
1
зна- чения F(x). Это приводит к основному функциональному уравнению - к ре- куррентной формуле динамического программирования (РДП):
(
) ( ) [
(
)
[
(
)]] (5.15)
Представленное выше выражение означает, что, зная f
0
(S), можно вы- числить f
1
(S), зная f
1
(S),вычислить f
2
(S) и т.д. Такая вычислительная проце- дура именуется рекуррентным алгоритмом, а выражение - рекуррентной формулой или рекуррентным соотношением.
Согласно этому алгоритм получения решения можно определить как по- следовательность функций выигрыша, или же, как последовательность стра- тегий {x
n
(S
0
)}. Эти последовательности определяют друг друга - в этом и со-
Электронный архив УГЛТУ

98 стоит смысл рекуррентных соотношений. Причем имеется только одна по- следовательность оптимальных значений целевой функции, хотя могут быть различные стратегии, которые приводят к тому же максимальному выигры- шу.
В динамическом программировании, планируя многоэтапную операцию, управление на каждом шаге выбирают с учетом будущего. И только на одном шаге - последнем - такой необходимости нет. Этот последний шаг можно спланировать так, чтобы он приносил наибольшую выгоду.
Планируя оптимальным образом последний шаг, к нему присоединяют предпоследний и находят согласно основной рекуррентной формуле наибольший выигрыш на этих двух шагах и т.д. Поэтому в динамическом программировании процесс разворачивается от конца к началу.
А как спланировать последний шаг, если мы не знаем, каков результат предпоследнего шага? Для этого делают различные предположения о том, чем закончится предпоследний шаг, и для каждого предположения выбирают управление на последнем, которое запоминают до конца решения задачи. Та- кое оптимальное управление, выбранное при определенном условии о том, каков результат предыдущего шага, называют условным оптимальным управлением.

99 3. При данном в задаче исходном условии для каждого возможного зна- чения первой переменной вычисляем значение целевой функции. Выбираем оптимальное значение целевой функции, соответствующее оптимально- му/оптимальным значению/значениям первой переменной.
4. При известном оптимальном значении первой переменной определяем исходные данные для следующего (второго) шага и по последней таблице - оптимальное(ые) значение(ия) следующей (второй) переменной.
5. Если следующая переменная не характеризует последний шаг, то пе- реходим к п. 4. Иначе – переходим к п. 6.
6. Формируем (выписываем) оптимальное решение.
5.4. Метод динамического программирования
в задаче оптимального управления запасами
Постановка задачи. Предприятие разрабатывает календарный план вы- пуска изделий на плановый период, состоящий из нескольких этапов. Теку- щая деятельность предприятия характеризуется следующими параметрами:
1) длительностью одного этапа планового периода;
2) выпуском продукции в течение этапа;
3) спросом на продукцию в конце этапа;
4) уровнем запасов изделий на конец этапа;
5) максимально возможным выпуском изделий на одном этапе;
6) максимально возможным уровнем запасов на одном этапе.
Известны затраты на каждом этапе планового периода, связанные с вы- пуском изделий и хранением запасов изделий. Также известны затраты на формирование начального запаса.
Необходимо определить план производства изделий для заданного спро- са продукции при минимальных затратах.
Математическая постановка задачи.
Введем следующие обозначения: N – число календарных этапов из кото- рых состоит плановый период; при этом каждый n-й этап (n = 1, N) характе- ризуется следующими параметрами:
i
n-1
– запас, оставшийся после окончания (n-1)-го этапа;
х
n
– объем производства предприятия на n-м этапе;
d
n
– величина спроса на продукцию предприятия на n-м этапе;
x
max
– максимальный объем производства на одном этапе;
i
max
– максимальный объем запасов на одном этапе;
С
n
(x
n
, i
n-1
) – затраты на n-м этапе функционирования, связанные с вы- пуском х
n деталей и хранением i
n-1
запасов деталей.
Тогда критерий оптимизации имеет вид:
Электронный архив УГЛТУ