Контрольная работа по "Методам оптимальных решений"

где и - некоторые известные функции n переменных, а - заданные числа.

 

16. Сформулируйте необходимое условие локального максимума в общей задаче нелинейного программирования.

 

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

 

17. Что такое функция Лагранжа?

Лагранжиан (функция Лагранжа) [Lagrangian] — вспомогательная функция, применяемая при решении задач математического программирования, в частности — линейного программирования. Образуется путем прибавления к целевой функции скалярного произведения двух векторов: вектора разностей между константами ограничений и функциями ограничений и вектора (неизвестных) множителей, называемых множителями Лагранжа:

 

 

 

где L(x, l) — лагранжиан, j(l) — целевая функция, li (1, 2, …, k)    — множители Лагранжа, k — число ограничений gi(x).

 

Часто величину bi полагают равной нулю; иногда знак (+) перед  ∑  заменяют на (-), но при этом множители λ  получаются тоже с обратным знаком. Все эти варианты эквивалентны.

 

Существует ряд вычислительных алгоритмов решения задач математического программирования методом  Лагранжа (см. также Куна — Таккера условия).

А вообще это один из способов нахождения экстремума функции (минимума или максимума) на неком данном отрезке.

 

18. Дайте определение седловой точки функции Лагранжа.

 

Седловая точка — точка, где функция Лагранжа достигает максимума по исходным переменным (прямой задачи) и минимума по множителям Лагранжа.

 

19. Сформулируйте и докажите достаточное условие оптимальности с помощью функции Лагранжа.

 

Достаточное условие оптимальности:

 Если - седловая точка функции Лагранжа, то вектор x* - решение задачи нелинейного программирования.

Доказательство:

Из и из условия дополняющей нежесткости (Если - седловая точка функции Лагранжа, то в ней выполняется условие дополняющей нежесткости.) следует неравенство

.

(7)

Пусть . Тогда и, так как . Отсюда и из . Что и требовалось доказать.

 

20. Сформулируйте условие дополняющей нежесткости и дайте его экономическую интерпретацию.

 

Равенство , где , , называется условием дополняющей нежесткости.

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

Ресурсов, что имеют нулевую двойственную оценку, – не является дефицитным.

Если xi=0, то, что затраты на сырье №i превосходят возможные затраты в случае закупки отдельных ресурсов, поэтому эти виды сырья использоваться не будут.

 

21. Дайте определение выпуклого множества.

 

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

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

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

 

22. Какие свойства имеют выпуклые множества?

 

Свойства выпуклых множеств:

- Пересечение выпуклых множеств является выпуклым.

- Линейная комбинация точек выпуклой множества выпуклая.

- Выпуклая множество содержит любую выпуклую комбинацию своих точек.

- Любую точку n -мерного евклидова пространства с выпуклой оболочки множества можно представить как выпуклую комбинацию не более n +1 точек этого множества.

 

23. Дайте определение опорной гиперплоскости.

 

Опорная гиперплоскость — гиперплоскость, имеющая общую точку или ряд общих точек с границей рассматриваемого множества (области), причем такая, что вся эта область лежит по одну сторону от нее.

 

24. Дайте определение разделяющей гиперплоскости.

РАЗДЕЛЯЮЩАЯ ГИПЕРПЛОСКОСТЬ [dividing, separating hyperplane] — гиперплоскость, разделяющая два выпуклых множества, каждое из которых лежит в одном из двух полупространств, образуемых этой гиперплоскостью в многомерном пространстве. Два замкнутых ограниченных выпуклых множества, не имеющих общих точек, всегда могут быть разделены гиперплоскостью. Причем если эти множества пересекаются в единственной точке, единственственная разделяющая их гиперплоскость является также опорной гиперплоскостью для обоих множеств

25. Сформулируйте и проиллюстрируйте теорему об отделимости выпуклых множеств.

 

Пусть X и Y выпуклые множества из и   Тогда множества X и Y отделимы.

Пример 1:

Пример2:

 

Пример 3:

 

26. Сформулируйте понятие выпуклой и вогнутой функций.

 

 Функция f(x) называется выпуклой  на отрезке [a, b], если выполнено условие

.                    (8)

Пример:

Функция f(x) называется вогнутой  на отрезке [a, b], если выполнено условие

. (9)

Пример:

 

27. Что такое строгая выпуклость функции?

 

Если неравенство является строгим, то функция f называется строго выпуклой.

   Выпуклые функции 

     Функция u = f(x), заданная  на выпуклом D, называется выпуклой, если

и строго выпуклой, если

     Признак строгой выпуклости 

     Если в каждой точке X области D второй дифференциал d2f(X) есть положительно-определенная  квадратичная форма от дифференциалов  независимых переменных, то f строго  выпукла в D.

     Свойства строго выпуклых функций

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

 

28. Что такое надграфик функции? Какими свойствами обладает надграфик выпуклой функции?

 

Надгра́фик — это множество точек, лежащих над графиком данной функции.

Свойства

- Надграфик функции является выпуклым множеством тогда и только тогда, когда она сама является выпуклой.

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

 

29. Сформулируйте достаточное условие выпуклости функции.

 

Пусть функция f ( x ) дважды дифференцируема (имеет вторую производную) на интервале ( a, b ), тогда:

если  f '' ( x ) < 0 для любого x ( a, b ), то функция  f ( x ) является выпуклой на интервале ( a, b ).

 

30. Какие свойства имеют выпуклые функции?

 

- Функция , выпуклая на интервале , непрерывна на всём , дифференцируема на всём за исключением не более чем счётного множества точек и дважды дифференцируема почти везде.

- Непрерывная функция выпукла на тогда и только тогда, когда для всех точек выполняется неравенство

                                                                  (10)

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

- Дважды дифференцируемая функция одной переменной выпукла на интервале тогда и только тогда, когда её вторая производная неотрицательна на этом интервале. Если вторая производная дважды дифференцируемой функции строго положительна, такая функция является строго выпуклой, однако обратное неверно (например, функция строго выпукла на , но её вторая производная в точке равна нулю).

- Если функции , выпуклы, то любая их линейная комбинация с положительными коэффициентами , также выпукла.

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

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

- Для выпуклых функций выполняется неравенство Йенсена:

                       (11) 
где — случайная величина со значениями в области определения функции , — математическое ожидание.

 

31. Сформулируйте выпуклую задачу нелинейного программирования.

 

Выпуклая Задача нелинейного программирования ставится как задача нахождения оптимума определенной выпуклой целевой функции при выполнении условий

  (выпуклое множество ограничений)

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

 

32. Сформулируйте теорему о глобальном максимуме в выпуклом случае.

 

Теорема (теорема Вейерштрасса).

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

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

 

33. Приведите содержательный пример выпуклой задачи нелинейного программирования.

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

Примером выпуклой задачи нелинейного программирования может служить следующая задача:

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

Или задача о выборе портфеля с минимальным риском:

Инвестор располагает информацией, отражающей динамику курсов и выплачиваемых дивидендов по акциям трех ведущих эмитентов A, B, C за десять прошедших месяцев перед предстоящим месяцем. Усредненный (по ценам покупки и продажи) курс акций на начало каждого месяца и размер выплаченных в каждом месяце дивидендов приведены в нижеследующей таблице в рублях.

Таблица 1.

Месяц	Курс А	Диви- денды А	Курс В	Диви- денды В	Курс С	Диви- денды С
1	…	…	…	…	…	…
2	…	…	…	…	…	…
3	…	…	…	…	…	…
4	…	…	…	…	…	…
5	…	…	…	…	…	…
6	…	…	…	…	…	…
7	…	…	…	…	…	…
8	…	…	…	…	…	…
9	…	…	…	…	…	…
10	…	…	…	…	…	…