Математические методы в принятии решений

Необходимым условием существования  экстремума непрерывной функции Q (u) является равенство нулю первой производной (dQ / du = 0) или ее отсутствие. Графически равенство нулю производной означает, что касательная к кривой Q (u) в этой точке параллельна оси абсцисс (рис. 2.1, а), на рис. 2.1, б изображен случай, когда производные в точках экстремума не существуют.

Рис. 2.1 Различные  типы экстремума функции одной переменной:

а – производная в точке экстремума существует; б – производная в точке экстремума не существует.

 

Рис. 2.2 Функции Q(u), удовлетворяющие необходимым условиям экстремума:

а – производная равна нулю; б – производная не существует; в – производная равна бесконечности.

 

Названные условия являются лишь необходимыми условиями. Их выполнение не означает еще, что в данных точках функция имеет экстремум (рис. 2.2).

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

1. Сравнение значений функций. Этот способ сводится к определению значений функции в точках, расположенных слева и справа в достаточной близости от исследуемой точки, т.е. в точках (u₁ – ε), (u₁ +ε), где ε – малая положительная величина. Если Q(u₁) > Q(u₁ – ε) и Q(u₁) > Q(u₁ + ε), то в точке u₁ существует максимум (рис. 2.3). Если Q(u₁) < Q(u₁ – ε) и Q(u₁) < Q(u₁ + ε), то в точке u₁ существует минимум (рис. 2.3, б). Если же Q(u₁) будет занимать промежуточное положение между Q(u₁ – ε) и Q(u₁ + ε), например, Q(u₁) > Q(u₁ – ε) и Q(u₁) < Q(u₁ – ε), то в точке u1 экстремума не будет (рис. 2.3, в).
2. Сравнение знаков производной. При этом способе определяется знак первой производной функции в точках (u₁ – ε) и (u₁ + ε). Если знаки производных различны, то в точке u₁ имеется экстремум функции Q(u), причем, если при переходе от точки (u₁ – ε) к точке (u₁ + ε) знак производной изменяется с "+" на "–", то в точке u₁ – максимум (рис. 2.3, а). Если же знак меняется с "–" на "+", то в точке u₁ – минимум (рис. 2.3, б).

Если же знаки производных  в точках (u₁ – ε) и (u₁ + ε) одинаковы, то в точке u₁ экстремума нет (рис. 2.3, в).

3. Исследование знаков высших производных. Этот способ применяется в тех случаях, когда исследуемая функция имеет производные высших порядков. Если в точке u₁ выполняется необходимое условие экстремума.

При решении практических задач, как правило, приходится исследовать  функции, имеющие несколько экстремумов. В этом случае говорят о нахождении наибольшего и наименьшего значения функции, которые называют глобальными  экстремумами. Остальные экстремумы называются локальными. Также в практических задачах диапазон изменения переменной u часто бывает ограничен заданным интервалом [a, b], поэтому в число "подозреваемых" точек должны быть включены и крайние точки этого интервала, так как в них может достигаться глобальный экстремум.

2.2 Метод неопределенных множителей Лагранжа

 

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

принятая оценка эффективности  процесса имела при этом максимальное или минимальное значение.

Для решения таких задач  в классическом анализе используется метод неопределенных множителей Лагранжа. Сами задачи получили название задач  на условный экстремум.

 

2.2.1 Основные положения

Пусть требуется найти  экстремум функции, например, минимум

Q (u₁, u₂, ..., u_n) → min    (2.3)

при условии

ϕι (u₁, u₂, ..., u_n) = 0, ι = 1, k .    (2.4)

Согласно методу Лагранжа для решения задач на условный экстремум функции составляется вспомогательная функция Лагранжа, которая определяется соотношением

где λι , ι = 1, k – неопределенные множители Лагранжа.

Таким образом, задача нахождения условного экстремума функции (2.3) сводится к задаче нахождения безусловного экстремума функции (2.5), но число неизвестных  в ней n + k (uι, ι = 1, n ; λj , j = 1, k ).

Как известно необходимым  условием безусловного экстремума функции  является равенство нулю частных  производных, которые для данного  конкретного случая записываются в  виде

и дает n уравнений для определения неизвестных. Эта система уравнений дополняется к уравнениям (2.4) и, следовательно, получается (n + k) неизвестных и (n + k) уравнений.

Метод множителей Лагранжа дает лишь необходимые условия существования  условного экстремума для непрерывных  функций, имеющих также непрерывные  производные, поэтому найденные  значения переменных могут и не давать экстремума функции Q (u₁, ..., u_n), их надо проверить с использованием достаточных условий экстремума функции многих переменных.

В окончательном решении  задачи фактически множители Лагранжа не известны, поэтому задача совместного  решения системы (2.4), (2.6) иногда ставится как задача исключения "k" неизвестных переменных uι с последующим решением остающейся системы n уравнений с n неизвестными.

Задача Лагранжа имеет "n – k" степеней свободы.

 

2.2.2 Геометрическая интерпретация метода множителей Лагранжа

Интерес представляют геометрический смысл множителей Лагранжа. Для такой  интерпретации лучше рассмотреть  задачу с двумя неизвестными и  одним ограничением.

Пусть требуется найти  минимум функции Q = Q(u₁, u₂) → min при условии ϕ (u₁, u₂) = 0. Если минимум существует, то в пространстве функция Q должна иметь вид воронки, а условие связи – это некоторая поверхность (рис. 2.4).

На рис. 2.4, б изображены на плоскости переменных u₁, u₂ линии уровня функции Q (u₁, u₂) и ограничение ϕ (u₁, u₂) = 0, представляющее собой линию. Составляется вспомогательная функция Q (u₁, u₂) = Q (u₁, u₂) + λϕ (u₁, u₂). Необходимое условие экстремума дает:

Рис. 2.4 Геометрический смысл множителей Лагранжа:

а – пространственное изображение; б – изображение проекции на плоскость u₂ – u₁.

 

В точке А (рис. 2.4) – точке касания линии ϕ (u₁, u₂) = 0 с линией равного уровня функции ϕ (u₁, u₂) и Q (u₁, u₂) имеют общую касательную и необходимое условие (2.7) минимума представляет собой условие пропорциональности двух векторов: вектора – градиента функции Q (u₁, u₂) и вектора .

Два вектора пропорциональны  друг другу лишь в том случае, если они коллинеарные. Так как  градиент функции перпендикулярен  касательной к линии уровня, то в точке А выполняется условие (2.7), и множитель λ является коэффициентом пропорциональности между векторами ∇Q и ∇ϕ.

 

2.2.3 Экономическая трактовка метода множителей

В некоторых задачах множители  Лагранжа допускают и экономическое  толкование. Если толковать целевую  функцию Q (u₁, ..., u_n) как прибыль, получаемую некоторым предприятием при использовании ресурсов, а условия ϕι (u₁, ..., u_n) = 0, ι = 1, k ограничения на дефицит ресурсов, то при ϕι (u₁, ..., u_n) < 0 прибыль, то максимум целевой функции будет расти.

Экономист такую задачу будет  решать следующим образом. Он назначит некоторые цены λι на единицы ресурсов ϕι и предложит потребителю купить их по этой цене. Последний, максимизируя чистую прибыль  ,

найдет (u₁, ..., u_n) и скажет, сколько ресурсов он хотел бы купить. В экономике почти всегда бывает так, что чем больше λι, тем меньше ϕι (u₁, ..., u_n), и чем меньше λι, тем больше ϕι (u₁, ..., u_n). Если окажется, что ϕι (u₁, ..., u_n) > 0, то экономист повысит цену, если ϕι (u₁, ..., u_n) < 0 – понизит. Так будет происходить до тех пор, пока при некоторой цене, называемой равновесной, потребителю будет выгодно, чтобы дефицит ресурсов ϕι (u₁, ..., u_n) был равен нулю, при этом чистая прибыль будет максимальна, т.е. будут выполняться условия

 

Таким образом, равновесная  цена с точностью до знака равна  множителю Лагранжа.

 

2.2.4 Особые случаи

В заключение следует отметить особые случаи, когда градиент функции Q (u₁, ..., u_n) равен нулю (∇Q = 0) и когда градиент ϕι (u₁, ..., u_n) равен нулю (∇ϕι = 0).

В первом случае решение  может достигаться в точке  экстремума функции Q (u₁, ..., u_n), множители λι равны нулю, и задача сводится к задаче безусловного экстремума и условия ϕι (u₁, ..., u_n) = 0 роли не играют. Во втором случае подозрительные на экстремум точки находятся из уравнений ∇ϕι (u₁, ..., u_n) = 0, в которых затем вычисляется значение критерия Q (u₁, ..., u_n).

Для того, чтобы условия  экстремума были справедливы и в  особых случаях, функцию Лагранжа записывают в виде

ϕι (u₁, ..., u_n) = 0.

Если λ0 ≠ 0, то его можно  выбрать положительным числом, обычно полагают λ0 = 1, это никак не отражается на решении.

2.3 Особенности реальных задач

 

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

1. Целевая функция не является гладкой, она может быть "колючей" (рис. 2.5), и тогда применять необходимые условия экстремума не представляется возможным.
2. При наличии ограничений на независимые переменные минимум целевой функции может быть на границе (рис. 2.6). Необходимое условие оптимальности позволяет найти минимум только внутри допустимой области, и в этом случае механизм нахождения экстремума (определение первых производных и приравнивание их нулю) теряет смысл, так как минимум таким образом определен не будет.
3. Критерий оптимальности задается алгоритмически, производные тогда можно рассчитывать только численными методами. Примером такого критерия является прибыль, которую нельзя аналитически связать с капиталовложениями.
4. Метод множителей Лагранжа предполагает наличие связей в виде равенств. В реальных задачах существуют ограничения и в виде неравенств.

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

3.НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

 

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

В большинстве практических задач критерий оптимальности Q (u), где u – вектор управляющих переменных, не может быть записан в явном виде, его значение обычно находится в результате решения системы уравнений математического описания оптимизируемого объекта. На независимые переменные u_i , i = 1, n могут быть наложены связи и ограничения как в виде равенств ϕι (u) = 0, ι = 1, m , так и в виде неравенств ψ_i (u) ≤ 0, i = 1, l , которые, как правило, являются нелинейными и трудно вычислимыми соотношениями. Задачи такого типа являются предметом рассмотрения специального раздела математики, называемого нелинейным программированием. Обычно, решения задач нелинейного программирования могут быть найдены только численными методами.

3.1 Области применения нелинейного программирования

 

Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в сфере  деловых отношений и в науке  управления государством.

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

Метод "затраты – эффективность" также укладывается в схему нелинейного  программирования.

Данный метод был разработан для использования при принятии решений в управлении государством.

Общей функцией эффективности  является благосостояние. Здесь возникают  две задачи нелинейного программирования: первая – максимизация эффекта при  ограниченных затратах, вторая – минимизация  затрат при условии, чтобы эффект был выше некоторого минимального уровня. Обычно эта задача хорошо моделируется с помощью нелинейного программирования.

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