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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

им. Н.И.ЛОБАЧЕВСКОГО

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

Факультет вычислительной математики и кибернетики

Кафедра информатики и автоматизации научных исследований

МЕТОДИЧЕСКИЕ УКАЗАНИЯ (СБОРНИК ЗАДАЧ) ПО КУРСУ «СИСТЕМЫ ПРИНЯТИЯ РЕШЕНИЙ»

Нижний Новгород, 2010

Методические указания (сборник задач) для самостоятельной работы студентов специальности «Прикладная информатика» факультета ВМК по курсу «Системы принятия решений» / Нижегородский государственный университет, 2010, с 20.

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

Методическая разработка подготовлена доцентом Коротченко А.Г., Сморяковой В.М., Кучиной О.М., Малаховской Д.А.

Рецензент: кандидат физ.-мат. наук, доцент В.А.Гришагин

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

Напомним основные обозначения, используемые при решении задач данного раздела:

- -мерные вектора;

- -мерное евклидово пространство со скалярным произведением ;

- норма вектора X;

- градиент функции в точке ;

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

Задача математического программирования

(1)

- допустимое множество задачи математического программирования,

.

- функция Лагранжа задачи (1), где .

- градиент функции Лагранжа по координатам вектора , то есть вектор, составленный из частных производных функции Лагранжа по координатам вектора :

.

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

Сформулируем известный из курса математического анализа результат о существовании решения задачи (1):

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

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

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

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

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

4. Пусть - точка строгого локального минимума функции на (). Можно ли утверждать, что убывает в некоторой левой полуокрестности точки и возрастает в некоторой правой полуокрестности ?

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

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

(2)

Теорема 2 (Необходимое условие локальной оптимальности первого порядка)

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

. (3)

Теорема 3 (Необходимое условие локальной оптимальности второго порядка)

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

при всех . (4)

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

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

при всех , . (5)

Тогда - строгое локальное решение задачи (2).

Теорема 5 (Критерий Сильвестра)

Симметрическая матрица является неотрицательно (положительно) определенной, тогда и только тогда, когда все её главные (угловые) миноры неотрицательны (положительны).

Пример 1.

Рассмотрим задачу безусловной оптимизации:

.

Решение:

1. Выпишем необходимое условие локальной оптимальности первого порядка:

Решениями этой системы являются точки = (0,0),

1. Рассмотрим гессиан функции в точках и :

, .

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

Матрица положительно определена. Следовательно, выполняется достаточное условие локальной оптима

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать