Методы безусловной оптимизации

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

Рубрика Экономика и экономическая теория
Вид контрольная работа
Язык русский
Дата добавления 15.04.2013
Размер файла 77,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Методы безусловной оптимизации

безусловный оптимизация унимодальный

Оптимизация унимодальных функций

Унимодальная функция на заданном отрезке [a,b] имеет единственный локальный экстремум, который и является глобальным.

Задача (общая постановка)

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

T=f(x),

где x[a,b] - обобщенный числовой параметр, характеризующий процесс доставки пакета.

Найти f* а - оценку минимального времени прохождения пакета и x* - оценку точки минимума функции f(x).

Для функции f(x), которые можно задать простым семантическим выражением, минимум находится среди стационарных точек внутри отрезка (=0) и его границы (f(a) и f(b)). Однако в сетевых процессах f довольно сложна и не всегда имеет аналитический вид, поэтому необходимы приближающие методы.

Пример 1.

f(x)=x2-3x+3, a=1, b=4

Найти x*, f* различными методами.

1) Для данного примера f(x) задана аналитически, простым выражением, поэтому можно найти точные значения:

=2х - 3=0 => xmin=1.5, f(xmin)=0.75

f(a)=f(1)=1

f(b)=f(4)=7

x*=1.5, f*=0.75 - точные значения.

2) Метод дихотомии (половинного деления)

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

Пусть N=6, е=0.2. Число итераций N/2=3.

Рис. Первая итерация.

Рис. Вторая итерация

Рис. Третья итерация

Рис.

Таблица

№ итерации

x1(j)

x2(j)

f1(j)

? >

f2(j)

a(j)

b(j)

0

-

-

-

-

-

1

4

1

2.4

2.6

1.56

<

1.96

1

2.6

2

1.7

1.9

0.79

<

0.91

1

1.9

3

1.35

1.55

0.77

>

0.75

1.35

1.9

x*[1.35;1.9] на данном отрезке исследовались 4 последних точки, min при x=1.55, поэтому ответ x*?1.55, f*?0.75.

Недостатки:

1) много вычислений

2) надо задавать е

3) Метод «золотого сечения».

Отличие: не отступаем от выбранной точки на е; новую точку выбираем «золотым сечением» с сохранением пропорции:

Рис.

, (AC>CB)

Используем дроби Фибоначчи:

Ф1=0.382; Ф2=0.618;

Ф1+Ф2=1; Ф1=(Ф2)2;

Зададим N=4, число итераций N-1=3.

Ф1?0.38 Ф2?0.62

Рис.

Итерация 1

Рис.

Итерация 2

Таблица

№ итерации

x1(j)

x2(j)

f1(j)

? >

f2(j)

a(j)

b(j)

0

-

-

-

-

-

1

4

1

2.14

2.86

1.16

<

2.6

1

2.86

2

1.71

2.14

0.81

<

1.16

1

2.14

3

1.43

1.71

0.76

<

0.81

1

1.71

x*[1;1.71]

На этом интервале рассчитываем 2 точки, f(1.43)<f(1.71) => x*?1.43, f*?0.76.

Для уменьшения ошибки надо более точно считать Ф1 и Ф2.

Унимодальные функции, которые можно рассмотреть на занятии:

1) , x[1;3]. Локальный минимум x*=2, f*=2

2) , x[0;3]. Локальный минимум x*=2, f*=

3) , x[0;2]. Локальный минимум x*=3-?1.268, f*=2 - 2?1.464

4) Размещено на Allbest.ru

...

Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.