2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 методы оптимизации. помогите пожалуйста ответить на вопросы
Сообщение04.02.2011, 21:23 
Аватара пользователя
у меня есть несколько вопросов по теме методы оптимизации пожалуйста помогите ответить, с кратким обоснованием. Я буду вам очень признательна. Пытаюсь разобраться в этой теме и множестве других, скоро экзамены, мозги работают, сильно скрипя. Помогите-е-е!!! :cry: :cry: :cry:

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


13. Верно ли следующее утверждение: рекуррентный механизм динамического программирования применяется для решения задач временнóго планирования?

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

"Метод прямого поиска для решения задач оптимизации это такой метод, в котором не используется ни какая информация о градиенте целевой функции. В противоположность обычным традиционным методам поиска точки минимума, в которых для поиска самой точки минимум используется информация о градиенте целевой функции или о производных различного порядка, в алгоритме метода прямого поиска анализируется определенный набор точек вокруг текущей точки. Причем ищется такая точка, в которой значение целевой функции меньше, чем значение в текущей точке. Методы прямого поиска для решения задач оптимизации можно использовать тогда, когда отсутствует какая-либо информация о дифференцируемости целевой функции или для случая прерывистой функции." и даже если она оказывается минимумом, то только на рассматриваемой нами области, а не на всей области определения ф-ии.... ну кроме очевидных случаев типа x^2

20. Является ли требование выпуклости области допустимых значений необходимым и достаточным условием оптимальности?

Спасибо за внимание.

 
 
 
 Re: методы оптимизации. помогите пожалуйста ответить на вопросы
Сообщение05.02.2011, 07:52 
12. Нет. Можно даже придумать пример, когда задача имеет решение, а целочисленная задача имеет пустое множество допустимых решений. Нарисуйте просто допустимую область так, чтобы она не включала в себя ни одну целую точку.

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

13. Вопрос некорректен. Надо знать, какой именно метод имеется в виду и к какой именно задаче он применяется. А названия можно дать какие угодно.

18. Можно. Если функция является выпуклой. Занимаясь поиском локального экстремума, вы найдет глобальный, так как для выпуклых функций они совпадают. А ещё можно его случайно угадать, даже если экстремумов несколько. Поэтому ответ на этот вопрос "да, в некоторых случаях".

20. Вопрос некорректный. Оптимальности чего?

 
 
 
 Re: методы оптимизации. помогите пожалуйста ответить на вопросы
Сообщение05.02.2011, 17:07 
Некоторые вопросы несколько вырваны из контекста, поэтому неясны. Насчет
18 - так. Если нам заранее известно, что локальный минимум и есть глобальный (например, функция выпукла) - тогда данный метод даст глобальный минимум. В общем же случае он может найти только лишь локальный минимум. Но насколько я понимаю методологию, здесь имеется ввиду вопрос "всегда ли можно определить глобальный". Ответ: нет. Этот метод лишь может оценить локальный минимум в общем случае.

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

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

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group