Контрольное задание по «Методы оптимальных решений»

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

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

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

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

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

 

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

 

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

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

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

 

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

 

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

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

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

 

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

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

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

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

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

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

Таблица 1.

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

 

Продажная цена акций A,B,C на начало предстоящего месяца составляет соответственно РА, РВ, РС руб.

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

 

34. Сформулируйте теорему Куна-Таккера.

 

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

                          (12)

       (13)

Или:

Если (х, и) — седловая точка функции Лагранжа, то x является оптимальным планом задачи, причем справедливо правило дополняющей нежесткости:

             (14)

 

35. Дайте экономическую интерпретацию множителей Лагранжа.

 

Экономическая интерпретация множителей Лагранжа, соответствующих оптимальному решению, аналогична интерпретации двойственных оценок ограничений ЗЛП

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

- В отличие от случая ЗЛП, множители Лагранжа (кроме частных случаев) не обладают свойством устойчивости

 

36. Как решения выпуклой задачи оптимизации зависят от параметров?

 

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

найти

при условии, что

Для того чтобы преобразовать ограничения-неравенства в ограничения в форме равенств, вводим вектор, состоящий из m вспомогательных («свободных») переменных

Теперь задача состоит в отыскании

при условии, что

причем неотрицательность вспомогательных переменных обеспечивает выполнение ограничений-неравенств.

Функция Лагранжа для данной задачи имеет вид:

где - вектор множителей Лагранжа (параметры)

Т.к. x и s –неотрицательны, то получаем следующие условия первого порядка для существования локального максимума задачи:

Заменяя вектор вспомогательных переменных на , получаем условия Куна-Таккера:

Либо другая форма записи:

, но  , если

, но  , если

 

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

 

Общей (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида:

                                    (15)

задача в которой фигурируют ограничения в форме неравенств, называется — основной задачей линейного программирования (ОЗЛП)

, (16)

.

 

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

 

Пример:

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

Тип оборудования	Затраты времени (станко-часы)  на обработку одного изделия  каждого вида			Общий фонд рабочего времени оборудования (часы)
	А	В	С
Фрезерное	2	4	5	120
Токарное	1	8	6	280
Сварочное	7	4	5	240
Шлифовальное	4	6	7	360
Прибыль (руб.)	10	14	12

 

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

 

39. Что такое нормальная (стандартная) и каноническая формы задачи линейного программирования?

 

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

 (17)

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

 

40. Какие свойства имеет допустимое множество задачи линейного программирования?

 

1. Допустимое множество задачи ЛП либо пусто, либо является выпуклым многогранником в Rn (как пересечение полупространств, описываемых неравенствами. Оно может быть как ограниченным, так и неограниченным; в любом случае это замкнутый многогранник.

2. Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.

3. Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением (т.е. существует бесконечное множество точек максимума или минимума).

 

41. Какие свойства имеет оптимальное решение в задаче линейного программирования?

 

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

 

42. Как выглядят функция Лагранжа и условия Куна-Таккера в задаче линейного программирования?

 

Для задачи:

                                                                                   

Функция Лагранжа:

                                                                   (18)

Условия Куна-Таккера:

      (19)

 

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