Тема 3. Нелинейное программирование как инструмент принятия управленческих решений

1. Постановка и классификация задач математического программирования.

2. Задачи вогнутого и выпуклого программирования.

3. Функция Лагранжа. Матрица Гессе. Необходимые и достаточные условия экстремума целевой функции.

4. Производственные функции.

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

В зависимости от свойств целевой функции f(x) и функций ограничений среди задач математического программирования (МП) можно выделить следующие:

· задачи нелинейного программирования (НП), когда на свойства целевой функции и функций ограничений не накладываются никакие условия;

· задачи выпуклого программирования (ВП), когда целевая функция и функции ограничений в виде неравенств являются выпуклыми функциями;

· задачи линейного программирования (ЛП) если целевая функция и функции ограничений линейны;

· задачи квадратичного программирования (КП), когда целевая функция квадратична, а функции ограничения линейны;

· задачи дискретного программирования (ДП), если множество допустимых значений дискретно;

· задачи параметрического программирования (ПП), когда целевая функция или функции ограничений зависят от одного или нескольких параметров;

· задачи стохастического программирования (СП), содержащие какой-либо тип неопределенности (случайность отдельных параметров, отсутствие полных сведений о виде целевой функции).

Общая постановка задачи МП: найти

Max f(x), D ⊂ Rⁿ (9)

х ∈ D

Множество D называется допустимым множеством, а его элементы х – допустимыми решениями. В зависимости от вида множества D задачи оптимизации подразделяются на задачи безусловной оптимизации, в которых допустимым является любой n-мерный вектор, т.е. D в этом случае совпадает с Rⁿ, и задачами условий оптимизации, когда D – подмножество Rⁿ . В свою очередь, среди задач условной оптимизации различают задачи с ограничениями в виде равенств; задачи с ограничениями в виде неравенств; задачи со смешанными условиями.

2. Под множеством обычно понимается точечное множество – совокупность точек на плоскости или в пространстве.

Пример множества на плоскости – круг, в трехмерном пространстве – шар.

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

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

Функция f(x), х ∈ D называется выпуклой на множестве D, если для х, у ∈ D и α ∈ [0,1] справедливо неравенство

f (x (1- α) + αy) ≤ (1- α) f(x) + αf(y) (10)

Если в условии 10 изменить знак неравенства ≤ на ≥, то получим определение вогнутой функции. Если же в условии 10 неравенство выполняется как строгое, то функция называется строго выпуклой (или строго вогнутой).

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

3. Различают глобальный, локальный и условный экстремум.

Точка х*, в которой все частные производные функции z=f(x) = 0, называется стационарной точкой. Нулевые значения частных производных – необходимое условие экстремума. Для получения достаточных условий следует определить в стационарной точке знак дифференциала второго порядка. Дифференциал второго порядка обозначается d² f(x₁,x₂…x_n) и равен сумме произведений частных производных второго порядка на соответствующие приращения аргументов.

d² f(x) = , (11)

где - частная производная второго порядка по переменным , получаемая как частная производная по переменной , взятая от частной производной по переменной .

Достаточные условия экстремума

а) в стационарной точке х* функция z=f(x) имеет максимум, если d² f(x*) < 0, и минимум, если d² f(x*) > 0, при любых , не обращающихся в ноль одновременно;

б) если d² f( ) может принимать в зависимости от и положительные, и отрицательные значения, то в точке экстремума нет;

в) если d² f( ) может обращаться в нуль не только при нулевых приращениях , то вопрос об экстремуме остается открытым.

Матрица вторых частных производных целевой функции f(x), вычисленных в точке х, называется матрицей Гессе целевой функции (матрица Н). Для того чтобы дважды непрерывно дифференцированная целевая функция f(x) имела в стационарной точке х* безусловный локальный экстремум, достаточно, чтобы ее матрица Гессе в этой точке была отрицательно (положительно) определена.

Точка х* является точкой глобального максимума функции f(x) на множестве D, если x ∈ D

f(x*) ≥ f(x) (12)

Точка x* называется точкой локального максимума функции f(x), если существует достаточно малое E > 0 такое, что для всех x ∈ D, удовлетворяющих условию (х-х*) ≤ E, выполняется неравенство

f(x*) ≥ f(x)

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

Условный минимум (максимум) определяется при наличии системы ограничений (уравнений связи).

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

L(x) = f(x) + (13)

где L(х) – функция Лагранжа;

– постоянные множители (множители Лагранжа).

Множителям Лагранжа можно придать экономический смысл. Если f(x₁,x₂…x_n) – доход, соответствующий плану x=(x₁,x₂…x_n) , а функция ф_i(x₁,x₂…x_n) - издержки i-го ресурса, соответствующего этому плану, то – цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса (маргинальная оценка). L(х) – функция n+m переменных (х₁…х_n, ₁… _m). Определение стандартных стационарных точек этой функции приводит к решению системы уравнений.

Пример. Предположим, что фирма разработала новый проект. В первый год после выхода на рынок фирма продала 500 единиц продукции по цене 300 руб. за каждую. Переменные затраты – 100 руб. на единицу, постоянные накладные расходы, отнесенные на продукт – 40000 руб. Изменение этих затрат в следующем году не ожидается.

Фирма заключила договор с рекламным агентством на рекламу этого продукта. Агентство предлагает рекламную кампанию, включающую публикацию объявлений на полную полосу в двух распространенных по всей стране журналах «Медиум 1» и «Медиум 2». Полная полоса в «Медиум 1» стоит 6000 руб., а в «Медиум 2» - 4000 руб. После проведения соответствующего исследования рынка рекламное агентство сообщило фирме, что эффективность рекламной компании зависит от количества данных объявлений, и функция спроса будет иметь вид:

Ɵ = 500 + 66М₁-3 +34M₂-2 , (14)

Ɵ – функция проданных изделий (спроса) в натуральном выражении

М₁ – число поданных объявлений в «Медиум 1»

М₂ – число поданных объявлений в «Медиум 2».

TR = 300Ɵ = 150000 + 19800M₁ - 900 + 10200M₂ - 600 , (15)

Где TR – функция продаж

TVC=100Ɵ+6000M₁+4000M₂=50000+12600M₁-300 +7400M₂-200 (16)

Где TVC – функция переменных затрат.

Введем ограничение 6000M₁+4000M₂=40000 (17)

Функция спроса будет максимизирована, когда мы приравняем к нулю как уравнение ограничения (17), так и частные производные М₁ и М₂ в уравнении (14). Мы можем приравнять к нулю как уравнение ограничения (17), так и частные производные по М₁ и М₂ в уравнении (14).

6000M₁+4000M₂-40000 =0 (18)

Когда мы возьмем частные производные от уравнения (14), то в результате получим систему из трех уравнений, имеющую всего две переменных, которая не имеет решения.

Разрешить эту дилемму можно, умножив уравнение (18) на искусственную переменную и прибавив полученное значение к уравнению (14).

Теперь мы имеем функцию из трех переменных

Ɵ = f(M₁, М₂, λ) = 500+66М₁-3 +34M₂-2 +6000λM₁+4000λM₂-40000λ'

Когда мы возьмем частные производные по всем переменным (M₁, М₂, λ), то получим три уравнения для тех переменных, которые доступны решению

= 66-6M₁+6000λ=0

= 34-4M₂+4000λ=0

= 6000M₁+4000M₂-40000=0

Решив эту системы, мы получим

М₁ =5,0; М₂ = 2,5; λ=-0,006.

Знак «минус» говорит о том, что значение функции будет увеличиваться при расширении ограничения. В данном случае оно составит 0,006 единиц на каждый рубль, добавляемый к расходам на рекламу. Поскольку каждая проданная единица продукции дает 200 руб. прибыли (300-100), предельная прибыль при данном уровне расходов на рекламу составит 200×0,006=1,20 руб. Предельная прибыль – разность между предельным доходом (приростом дохода) и предельными затратами (приростом переменных затрат) при изменении аргумента на единицу (в нашем случае единица аргумента – одно рекламное объявление). Поскольку данная функция прибыли нелинейна TCR=TR-TVC=100000+7200М₁-600 +2800М₂-400 (TCR в западной экономической литературе получила название предельный вклад – contribution margin или вложенная прибыль – contribution profit), а предельная прибыль уменьшается с увеличением расходов на объявления и становится отрицательной, расходы на рекламу могут быть увеличены до 52 тыс. руб. При расходах на рекламу в 56 тыс. руб. (6 объявлений в «Медиум 1» и 5 объявлений в «Медиум 2») вложенная прибыль начинает снижаться, а предельная прибыль – отрицательна.

4. Примером типичной и простой нелинейной задачи является следующая: данное предприятие для производства какого-то продукта расходует два средства в количестве х₁ и х₂ соответственно. Это факторы производства, например, машины и труд, два различных сырья и т.п. а величины х₁ и х₂ – затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это «труд» и «машины», то можно применить такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда сказывается больше или меньше (производство более или менее трудоемкое). В сельском хозяйстве взаимозаменяемыми факторами могут быть посевные площади или минеральные удобрения (экстенсивный или интенсивный метод производства). Объем производства (выраженный в натуральных или стоимостных единиц) является функцией затрат производства z=f(x₁,x₂). Эта зависимость называется производственной функцией.