Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
EMMM_Lektsii.doc
Скачиваний:
4
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

Контрольные вопросы

  1. Предмет теории игр на основе понятия матричных игр.

  2. Решение игр с седловой точкой. Принцип минимакса.

  3. Решение игр размером 2х2 в смешанных стратегиях.

  4. Геометрическая интерпретация игры 2х2.

  5. Графический метод решения игры 2xn.

  6. Графический метод решения игры mx2. Рекомендованная литература: [ 1, 2, 4, 9, 12] раздел 2. Модели нелинейного программирования

Тема 9. Нелинейное программирование

Розглянуті питання з теми:

9.1. Общая задача нелинейного программирования

9.2. Метод множителей Лагранжа

9.3. Обобщёние метода множителей Лагранжа

9.4. Теорема Куна-Таккера

9.5. Модели выпуклого программирования

9.6. Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации

9.1. Общая задача нелинейного программирования

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

Общая оптимизационная задача формулируется следующим образом: найти вектор X=(x1,x2, ... , xn), удовлетворяющий системе ограничений, представляемых в виде совокупности равенств и/или неравенств вида

i(x1, x2, ... , xn)  bi , i=1,2,...,k, (1)

i(x1, x2, ... , xn) = bi , i=k+1,k+2,...,m

и доставляющий экстремальное значение целевой функции

Z=f(x1, x2, ... , xn); (2)

При этом на некоторые переменные x1, x2, ... , xn могут накладываться условия неотрицательности и целочисленности.

В случае если одна из функций i и/или f будет нелинейной, то полученную модель считают задачей нелинейного программирования (ЗНП). Класс ЗНП шире класса ЗЛП. Основные результаты получены при рассмотрении задач, в которых ограничения имеют линейный вид, а целевая функция нелинейная. Рассмотрим частные случаи, когда целевая функция сепарабельная (ее можно представить в виде суммы функций, каждая из которых зависит от одной переменной) или квадратичная.

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

Можно выделить класс нелинейных задач, которые относятся к классическим методам оптимизации. Рассмотрение ЗНП начинают с классической задачи оптимизации. Задачи такого рода имеют место, если система (1) содержит только уравнения, отсутствуют условия неотрицательности и целочисленности переменных, а функции i(x1, x2, ... , xn) и f(x1, x2, ... , xn) непрерывны и имеют частные производные не ниже второго порядка. Т.е. задачу оптимизации можно сформулировать так: найти переменные x1, x2, ... , xn, удовлетворяющие системе уравнений

i(x1, x2, ... , xn) = bi , i=1,2,...,m, (3)

и обращающие в максимум (минимум) целевую функцию

Z=f(x1, x2, ... , xn). (4)

Примером типичной и простой ЗНП является следующая: данное предприятие для производства какого-то продукта расходует два средства в количестве х1 и х2 . Это факторы производства, например, машины и труд, а величины х1 и х2 – затраты факторов производства. Объем производства (выраженный в натуральных или стоимостных единицах) является функцией затрат производства Z=f(x1, x2). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (x1 и x2) и от цен этих факторов (с1 и с2). Совокупные издержки выражаются формулой b=c1x1+c2x2. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z.

Математическая модель этой задачи: найти переменные x1, x2, удовлетворяющие условиям b=c1x1+c2x2, х10, х20, при которых функция Z=f(x1, x2) достигает максимума. Как правило, функция Z может иметь произвольный нелинейный вид.

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

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

Будем полагать, что функция Z=f(x1, x2, ... , xn)= f(Х) дважды дифференцируема в точке Х*=(x*1, x*2, ... , x*n) и в некоторой ее окрестности. Если для всех точек Х этой окрестности f(Х*) f(Х) или f(Х*) f(Х), то говорят, что функция f(Х) имеет локальный экстремум в Х* (соответственно максимум или минимум).

Точка Х*, в которой все частные производные функции f(Х) равны 0, называется стационарной точкой.

Необходимое условие экстремума: если в точке Х* функция f(Х) имеет экстремум, то частные производные функции в этой точке равны нулю:

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

Функция Z=f(Х) имеет в точке Х* заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f(Х*) f(Х) или f(Х*) f(Х) соответственно выполняется для любой точки

Х D.

Если область D замкнута и ограничена, то дифференцируемая функция Z=f(Х) достигает в этой области своих наибольшего и наименьшего значений в стационарной точке или в граничной точке области (теорема Вейерштрасса).

Следовательно, чтобы найти наибольшее (наименьшее) значение функции Z=f(Х) в области D, нужно:

  1. найти все стационарные точки внутри области D и вычислить значения функции в них;

  2. исследовать функцию на экстремум на границе области D;

  3. сравнить значения функции, полученные в п.1 и 2: наибольшее (наименьшее) из этих чисел и будет наибольшим (наименьшим) значением функции в этой области.

Граница области D аналитически может быть задана системой уравнений (условий) относительно переменных x1, x2, ... , xn. Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума.

Пусть необходимо найти экстремум функции Z=f(x1, x2, ... , xn) при условии, что переменных x1, x2, ... , xn удовлетворяют уравнениям

i(x1, x2, ... , xn) = 0 , i=1,2,...,m, m<n. (*)

Предполагается, что функции f и i имеют непрерывные частные производные по всем переменным. Уравнения (*) называют уравнениями связи.

Функция Z=f(Х) имеет в точке , удовлетворяющей уравнениям связи (*), условный максимум (минимум), если неравенство f( ) f(Х) (f( ) f(Х)) имеет место для всех точек Х, координаты которых удовлетворяют уравнениям связи.

Легко заметить, что задача определения условного экстремума совпадает с ЗНП (3), (4).

Один из способов определения условного экстремума применяется в том случае, если из уравнений связи m переменных можно явно выразить через оставшиеся n-m переменных:

xi=I(xm+1, …,xn), i=1,2,…,m.

Подставив полученные выражения для xi в функцию Z, получим

Z= f(1(xm+1, …,xn),…, m(xm+1, …,xn), xm+1, …,xn), или Z=F(xm+1, …,xn).

Задача сведена к нахождению локального (глобального) экстремума для функции

n-m переменных. Если в точке функция Z=F(xm+1, …,xn) имеет экстремум, то в точке =(1 ,…,m , функция Z=f(x1, x2, ... , xn) имеет условный экстремум ( сформулированный ранее).

Если число переменных n=2, нелинейные задачи можно решить графически. Ограничения должны быть записаны в виде неравенств i(x1, x2, ... , xn)  bi , i=1,2,...,m, а целевая функция иметь вид Z=f(x1, x2).

Как и в случае геометрического решения ЗЛП, сначала необходимо построить область допустимых решение (ОДР) – множество точек плоскости, удовлетворяющих неравенствам i(x1, x2, ... , xn)  bi. Но в отличии от ЗЛП здесь ОДР не обязательно будет выпуклой и может быть разрывной. Экстремум функции может достигаться и внутри области, и на границе.

После построения ОДР следует записать уравнения линий уровня целевой функции- множество точек плоскости, в которых целевая функция постоянна: f(x1, x2)=C, и определить направление возрастания (убывания) целевой функции, построив, например, линии уровня для разных значений С. Затем, перемещая линию уровня в нужном направлении в ОДР, найти точки области, в которых целевая функция принимает оптимальное значение.

Пример1. Найти минимальное и максимальное значения сепарабельной функции Z=(x1-4)2+(x2-6)2 при ограничениях:

x10, x20.

Решение. ОДР представляет собой многоугольник ABCE (рис. 1). Если положить Z=Q (Q>0),то линии уровня целевой функции - это уравнение окружности (x1-4)2+(x2-6)2=Q. С уменьшением (увеличением) Q (квадрата радиуса) значения функции Z соответственно уменьшаются (увеличиваются).

Центром окружностей будет точка М с координатами (4, 6). Проведем из точки M окружности различных радиусов при разных Q и получим: минимальное значение функция Z(D)=196/13 принимает в точке D (24/13,36/13), в которой окружность касается области решений. Точка D не является угловой, ее координаты находят в результате решения системы уравнений, соответствующих прямым MD и CE.

Функция Z имеет два локальных максимума: в вершине A(1;0) функция

Рис.1 Z(A)=45, в вершине E(6;0) функция Z(e)=40.

Так как Z(А)>Z(E), то вершина A является точкой глобального максимума.

Пример 2. Пусть область допустимых решений остается прежней, а Z=(x1-4)2+(x2-1)2. Найти минимальное и максимальное значения этой функции.

Решение. Минимальное значение функция принимает в точке M(4;1) (рис.2): Z(M)=0. Функция Z имеет два локальных максимума: в вершине E(6;0) функция Z(E)=5, в вершине С(0;4) функция Z(C)=25, причем глобальный максимум достигается в вершине С.

Рис. 2

Пример 3. Найти минимальное и максимальное значения функции Z=x12+x22 при ограничениях

x10, x20.

Решение. В этом случае (рис.3) область допустимых решений не является выпуклой и состоит из двух отдельных частей. Минимальное значение функции Z=17 достигается в точках A(1;4) и L(4;1). Функция Z

Рис.3. имеет два локальных максимума: в точке D(2/3; 6) функция Z(D)=328/9 и в точке M(7; 4/7) функция Z(M)=2417/49. Точка M является точкой глобального максимума.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]