Компьютерные технологии решения оптимизационных задач управления

Пусть функция определена в некоторой  области S ( ), в случае одномерной оптимизации S – интервал :

1. точка называется глобальным минимумом, если для
2. точка называется строгим глобальным минимумом, если для
3. точка называется локальным минимумом, если для
4. точка называется строгим локальным минимумом, если для

 

Следствие: любая точка глобального минимума является локальным минимумом, обратное не верно. 

Аналитический способ нахождения локального минимума. 

- дифференцируема

- необходимое условие точки  локального минимума.

                             
 
 
 
 

 

Численные методы 

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

 
 
 
 
 
 

                                       а                                                           b 

     Если  из того что  следует, что , то функция называется монотонно возрастающей. Если из того что следует, что , то функция называется монотонно убывающей. 

Методы  одномерного поиска 

Разобьем 

и вычислим значение функции в каждой точке.

 

                                                                   

                                            искомый минимум 

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

     Интервал  неопределенности – интервал, в  котором заведомо находится точка минимума. Наиболее эффективное разбиение – двумя точками на 3 равных отрезка. 

 
 

                                                                  

1)

2)

 

- после выполнения n шагов сокращение исходного интервала

- точность с которой надо  найти решение задачи. 

                 

N=2n, где n – число шагов, N – число вычислений (мера эффективности данного решения). 
 

Метод золотого сечения 

Точки должны быть расположены на равном расстоянии. 

                                                                   

                                                           

                             а                                                     b

                                                        

; ; ;

; - золотое сечение. 

                                                           а

                                                                 

 - величина сокращения на каждом  шаге

число итераций растет как логарифм функции. 

Одномерная  оптимизация с использованием производных 

. Пусть целевая функция дифференцируема  . 

 
 

     Методы  для нахождения корня уравнения  функции 1-ой производной от исходной 

     Нахождение  локального минимума или максимума  сводится к нахождению корней первой производной от данной

      f’(x)=0 

     Если  f’(x) представляет собой многочлен, то уравнение называется алгебраическим (полиномиальным), если f’(x) представлена тригонометрическими, логарифмическими, показательными и т.п. функциями, то уравнение называется трансцендентным.( вдальнйшем вместо f’(x) будем употреблять f(x) )

    Решение уравнения вида разбивается на два этапа:

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

На первом этапе может помочь построение приближенного графика функции f(x) или, если функция достаточно сложная, то можно попытаться представить уравнение  в виде и построить два графика   и , тогда корнями уравнения будут абсциссы точек пересечения этих кривых. 
 
 
 
 

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

• Если на концах некоторого  интервала функция непрерывна и принимает значения разных знаков, т.е. , то на этом интервале уравнение имеет хотя бы один корень (один  или нечетное количество корней).
• Если на концах интервала функция принимает значения одинаковых знаков, т.е. , то на этом интервале уравнение не имеет корней или имеет четное количество корней.
• Если на интервале первая и вторая производные функции сохраняют определенный знак, т.е. и или и , и не обращаются в нуль на всем участке, то функция монотонна, и корень будет единственным.

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

• половинного деления;

 

Метод половинного деления 

     Суть  метода половинного деления (дихотомии) заключается в следующем.

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

    Метод половинного деления реализуется  в виде следующего алгоритма:

Найти точку c = (a + b)/2.

Если  f(a)×f(c) <0, то корень лежит на интервале [a, c], если нет, то корень лежит на интервале [c, b].

Если  величина интервала не превышает  некоторое достаточно малое число е, то найден корень с точностью е, иначе возврат к п.1.

      Несмотря  на простоту, этот метод требует  слишком большого количества вычислений и не всегда позволяет найти решение с заданной точностью.

      

 
 

Блок-схема  алгоритм решения уравнения методом  деления пополам. 
 
 
 
 
 
 
 
 
 
 
 

Список  использованной литературы 

       

1. Автоматизация вычислений и компьютерное моделирование. MS Excel и MathCad : учебное пособие / Н.В. Вознесенская. – Саранск : Изд-во Мордовского университета, 2004. – 91 с.
2. Дьяконов, В. MathCad 2001: специальный справочник / В. Дьяконов. – СПб. : Питер, 2002. – 832 с.
3. Информатика : учебник / Макарова Н. В. [и др.].  – М. : Финансы и статистика, 1997. —768с.
4. Исследование операций в экономике: Учебное пособие для вузов / Кремер Н.Ш. [и др.]. – М.: ЮНИТИ, 2002. – 407 с.
5. Кудрявцев, Е. Н. Исследования операций в задачах, алгоритмах и программах / Е.Н. Кудрявцев. М., Наука, 1982. – 150 с.
6. Кузнецов, Ю. Н. Математическое программирование / Ю.Н. Кузнецов, В.И. Кузубов, А.В. Волощеноко. - М.: Высшая школа, 1980. – 320 с.
7. Леонтьев, Ю. Microsoft Office 2000. Краткий курс / Ю. Леонтьев. – СПб.: Питер, 2001. – 760 с.
8. Сидоров, М. Е. Решение задач оптимального планирования в таблицах Excel // Информатика  и образование. – М., 2001. – № 1. – с. 36 – 51.
9. Стандарт предприятия. Общие требования и правила оформления курсовых и дипломных работ и пояснительных записок к курсовым и дипломным проектам.
10. Ширяев, В.Д. Экономико-математические методы: учебное пособие / В.Д. Ширяев, Н.М. Куляшова.  – Саранск : Изд-во Мордовского университета, 2002. – 112 с.
11. Экономическая информатика: Учебник / Косарев В.П.. – М.: Финансы и статистика, 2004. – 592 с.