Лабораторная работа № 7 Решение задач оптимизации

Цель работы: изучить численные методы поиска минимума функции одной переменной. Ознакомиться с методами решения задач условной оптимизации средствами Excel.

Содержание работы

1. Изучение методов поиска минимума функции одной переменной;

2. Реализация вычислительного процесса поиска минимума функции одной переменной;

3. Изучение средств Excel для решения задач оптимизации;

4. Изучение алгоритма решения задач условной оптимизации этими средствами;

5. Рассмотрение примеров решения экономических задач на условную оптимизацию;

6. Реализация вычислительного процесса в Excel.

Основные понятия Унимодальные функции

Определение. Непрерывная функция y=f(x) называется унимодальной на отрезке [а,b], если:

1) точка х* локального минимума функции принадлежит отрезку [a,b];

2 ) для любых двух точек отрезка x₁ и х₂, взятых по одну сторону от точки минимума, точке х₁, более близкой к точке минимума, соответствует меньшее значение функции, т.е. как при х*<х₁<х₂ (рис. 1,а), так и при х₂<х₁<х* (рис. 2,б) справедливо неравенство f(x₁) < f(x₂).

Достаточное условие унимодальности функции f(x) на отрезке [а,b] содержится в следующей теореме.

Теорема 8. Если функция f(x) дважды дифференцируема на отрезке [а,b] и f’’(x) > 0 в любой точке этого отрезка, то f(x) - унимодальная функция на [а,b].

Заметим, что условие f’’(х) > 0 определяет множество точек, на котором функция является выпуклой вниз.

Пример 1. Для функции f(x) = 2х² – ln x найти:

1) промежуток X, на котором функция является унимодальной;

2) решение задачи f(x) → min, x  X (X  R).

Решение. Функция f(x) определена при х>0; найдем ее производные

.

Следовательно, функция f(x) унимодальна на интервале (0, ). Первая производная f’(х)=0 при х=0,5.Заключаем, что х*=0,5 - точка локального минимума функции f(x).

Схема сужения промежутка унимодальности функции

Пусть требуется решить задачу

f(x) → min, x  X (X  R) (1)

Применение численных методов для отыскания точек х* локального минимума функции f(x) предполагает:

1) определение промежутков унимодальности функции, т.е. нахождение отрезков, которым принадлежит одна точка локального минимума;

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

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

При вычислении точки минимума точность достигается последовательным уменьшением отрезка [a, b], содержащего точку х*, до размеров, не превышающих заданную точность  (b - а ≤ ).

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

Рассмотрим один из приемов, позволяющих сузить отрезок унимодальности функции.

Пусть функция f(x) унимодальна на отрезке [а,b]. Возьмем две произвольные точки х₁ и х₂, принадлежащие отрезку [а,b] такие, что х₁ < х₂. В каждом из следующих трех очевидных возможных случаев можно указать отрезок меньших размеров [a₁, b₁], содержаний точку минимума х* и принадлежащий первоначальному отрезку (рис.2):

I. Если y₁ = f(х₁) < у₂ = f(x₂), то положим a₁ = а и получим меньший отрезок унимодальности [a₁, b₁].

II. Если у₁ = f(х₁) > у₂ = f(х₂), то естественно принять a₁ = x₁ и b₁ = b.

III. Если у₁ = f(х₁) = у2 = f(х₂), то a₁ = x₁ и b₁ = x₂.

Пример 2. Для функции f(x) = 2x² – ln x, выбрав отрезок унимодальности [а,b] = [0,25; 1] и две произвольные точки х₁, х₂ с [a, b], найти меньший отрезок унимодальности [a₁, b₁].

Решение. В примере 1 было установлено, что функция f(x) имеет точку минимума х*=0,5 и является унимодальной на любом отрезке, содержащем точку х* и лежащем в области ее определения (0, ). Возьмем х₁ = 0,375, х₂ = 0,625; тогда y₁ = f(x₁) = 1,2620793, y₂ = f(х₂) = 1,2512536. Здесь естественно положить a₁ = x₁ = 0,375 и b₁ = b = 1 (случай II).

Методы вычисления значения точки минимума функции одной переменной отличаются алгоритмами выбора точек х₁ и х₂ для локализации точки х* с заданной точностью.