Методические указания (сборник задач) по курсу «системы принятия решений» (стр. 6 из 8)

67. Пусть множество

имеет вид , ( соответствует случаю ). Доказать, что тогда (13) эквивалентно условиям:

68. Решить задачу:

69. Решить задачу:

70. Пусть

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

71. Пусть

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

Напомним необходимое условие оптимальности (Принцип Лагранжа) в задаче математического программирования (1).

Теорема 12 (Принцип Лагранжа)

Пусть в задаче (1) множество

- выпукло, функции дифференцируемы в точке , функции непрерывно дифференцируемы в некоторой окрестности точки . Если - локальное решение задачи (1), то существует число и вектор не равные нулю одновременно и такие, что

(14)

. (15)

Используемые здесь обозначения пояснены после формулировки задачи (1) на странице 3, а числа

, также как в классической задаче на условный экстремум, называются множителями Лагранжа.

Теорема 13 (Достаточное условие оптимальности)

Пусть в задаче (1) множество

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

Теорема 14 (Условия регулярности)

Пусть в задаче (1) множество

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

1) ограничения-равенства отсутствуют (

) и существует точка такая, что при всех ;

2)

, функции линейны.

Тогда, если

- локальное решение задачи (1), то существует такой, что при будут выполнены условия (14), (15).

Условие 1) теоремы называется условием регулярности Слейтера.

Теорема 15 (Теорема Куна-Таккера в дифференциальной форме)

Пусть в дополнение к условиям теоремы 14 функция

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

Пример 3.

Рассмотрим задачу:

Решение:

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

2. Условия регулярности Слейтера выполнено, следовательно, функция Лагранжа регулярная:

.

1. Выпишем необходимые условия:

Пусть

, тогда , но данная точка не удовлетворяет ограничению задачи. Отсюда следует, что . Система перепишется в виде:

Разрешая систему, получим:

.

4. Для задачи выпуклого программирования необходимые условия оптимальности являются и достаточными (теорема 13), то есть

- глобальное решение задачи.

72. Опираясь на решение задач 65-67, конкретизировать условие (14) в случае, когда

и когда имеет вид, указанный в задачах 66, 67.

Проекцией точки

на множество D называется точка , ближайшая к среди всех точек из D. Иными словами, является решением задачи проектирования

.

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

Доказать следующие утверждения для произвольной точки

.

73. Если

- сфера, то .

74. Если

- координатный параллелепипед, то