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

 

Продажная цена акций 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. Сформулируйте двойственную задачу линейного программирования.

 

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

при условиях

                                                                  (20)

     (21)

Задача, состоящая в нахождении минимального значения функции

                                                                               (22)

при условиях

                                                                  (23)

   (24)

называется двойственной по отношению к задаче.

 

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

 

- Первая теорема двойственности.

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

- Вторая теорема двойственности.

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

                                                                                (25)

 

45. Дайте интерпретацию двойственных переменных в задаче линейного программирования.

 

Для двойственной задачи:

 

 

 (26) 

Интерпретация переменных следующая:

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

Для производства единицы продукции вида необходимо затратить непосредственно трудовые ресурсы в объеме .

вектор является вектором полных трудовых затрат на выпуск единицы продукции вида .

 

46. Расскажите об анализе чувствительности в задаче линейного программирования.

 

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

 

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

 

Решить графически

  . (27)

Для построения области допустимых решений строим граничные прямые, соответствующие данным ограничениям.

Областью решения есть многогранник:

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

Для нахождения максимума:

Прямая пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:

,

Максимальное значение целевой функции:

Для нахождения минимума:

Прямая пересекает область в точке С. Так как точка С получена в результате пересечения прямых (4) и (5), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:

,

Минимальное значение целевой функции:

Поскольку функция цели F(x) параллельна прямой (5), то на отрезке CA функция F(x) будет принимает одно и тоже минимальное значение.

 

48. В чем состоят методы решения задач линейного программирования, основанные на направленном переборе вершин (симплекс-метод и др.)?

 

Направленный перебор.

Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆ ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)