Некрасова М.Г. Методы оптимизации - файл n1.doc

приобрести
Некрасова М.Г. Методы оптимизации
скачать (3013.5 kb.)
Доступные файлы (1):

n1.doc

3014kb.

22.08.2012 14:29

скачать

---

Смотрите также:
• Методы безусловной многомерной оптимизации. Рекомендации к выполнению лабораторных, практических и курсовых работ по дисциплине Методы оптимизации (Документ)
• Лекции - Методы оптимизации (Лекция)
• Доклад - Методы одномерной оптимизации (Реферат)
• Задача о рюкзаке ( о ранце ) (Документ)
• Харазов А.М., Цвид С.Ф. Методы оптимизации в технической диагностике машин (Документ)
• Васильев Ф.П. Методы оптимизации (Документ)
• Васильев О.В., Аргучинцев А.В. Методы оптимизации в задачах и упражнениях (Документ)
• Шпоры по МО (Шпаргалка)
• Васильев Ф.П. Методы оптимизации (Документ)
• Методы оптимизации (Документ)
• Лунева С.Ю. Теория оптимизации и численные методы (Документ)
• Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации (Документ)

n1.doc

Некрасова М.Г. - Методы оптимизации

Оглавление

ВВЕДЕНИЕ

1. ВВЕДЕНИЕ В МЕТОДЫ ОПТИМИЗАЦИИ

2. ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ
2.1 Параметры плана
2.2 Целевая функция (план)

3. ФУНКЦИЯ ОДНОЙ ПЕРЕМЕННОЙ
3.1 Определение функции одной переменной и ее свойства
3.2 Исследование функции в экономике. Нахождение максимума прибыли
3.3 Определение глобального экстремума
3.4 Выпуклость, вогнутость функции
3.5 Критерий оптимальности
3.6 Идентификация оптимумов

4. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ
4.1 Методы исключения интервалов
       4.1.1 Метод сканирования
       4.1.2 Метод деления отрезка пополам
       4.1.3 Метод золотого сечения
       4.1.4 Сравнительная характеристика методов исключения интервалов
4.2 Полиномиальная апроксимация и методы точечного оценивания
       4.2.1 Метод параболической апроксимации
       4.2.2 Метод Пуэлла
4.3 Сравнение методов одномерного поиска

5. ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ
5.1 Функции многих переменных, их обозначение и область определения
5.2 Некоторые многомерные функции, используемые в экономике
5.3 Частные производные функции многих переменных
5.4 Экономический смысл частных производных
5.5 Частные производные высших порядков
5.6 Свойства функции нескольких переменных
5.7 Производная по направлению. Градиент. Линии уровня функции
5.8 Экстремум функции многих переменных

6. МНОГОМЕРНАЯ БЕЗУСЛОВНАЯ ГРАДИЕНТНАЯ ОПТИМИЗАЦИЯ
6.1 Концепция методов
6.2 Метод градиентного спуска
6.3 Метод наискорейшего спуска

7. КРИТЕРИИ ОПТИМАЛЬНОСТИ В ЗАДАЧАХ С ОГРАНИЧЕНИЯМИ
7.1 Задачи с ограничениями в виде равенств
7.2 Множители Лагранжа
7.3 Экономическая интерпретация множителей Лагранжа
7.4 Условия Куна-Таккера
       7.4.1 Условия Куна-Таккера и задача Куна-Таккера
7.5 Теоремы Куна-Таккера
7.6 Условия существования седловой точки

8. МОДЕЛИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
8.1 Предмет динамического программирования
8.2 Постановка задачи динамического программирования
8.3 Принцып оптимальности и математическое описание динамического процесса управления
8.4 Общая схема применения метода динамического программирования
8.5 Двумерная модель распределения ресурсов
8.6 Дискретная динамическая модель оптимального распределения ресурсов
8.7 Выбор оптимальной стратегии обновления оборудования
8.8 выбор оптимального маршрута перевозки грузов
8.9 Построение оптимальной последовательности операций в коммерческой деятельности

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ РАСЧЕТНО-ГРАФИЧЕСКОГО ЗАДАНИЯ

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 1

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 2

РАСЧЕТНО-ГРАФИЧЕСКОЕ ЗАДАНИЕ 3

ЛИТЕРАТУРА

ВВЕДЕНИЕ

Математизация различных областей знаний в настоящее время не является чем-то новым. Широкое внедрение математических методов в самые разнообразные сферы деятельности сегодня уже никого не удивляет. Это не только технические и экономические науки, где эти методы давно приносят свои плоды, но и развивающиеся сейчас разнообразные прикладные науки управления: менеджмент, принятие управляющих решений, социально-экономическое прогнозирование и т.д.

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

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

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

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

Учебно-практическое пособие для системы дистанционного образования по дисциплине «Методы оптимизации и теория управления» предназначено для самостоятельной работы студента при нестационарной форме контроля знаний.

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

После изучения курса студенты сдают зачет. Вопросы к зачету составляются на основе контрольных вопросов, указанных в конце каждого раздела пособия.

Глава 1. ВВЕДЕНИЕ В МЕТОДЫ ОПТИМИЗАЦИИ

Термин «оптимизация» имеет очень широкое употребление, а потому может зависеть от контекста. Оптимум (от лат. optimum – наилучшее) - совокупность наиболее благоприятствующих условий; наилучший вариант решения задачи или путь достижения цели при данных условиях и ресурсах. Экономический оптимум в широком смысле – наиболее эффективное функционирование производства, в узком – наилучшее использование материальных ресурсов, при котором достигается возможный максимальный эффект производства или возможный минимум затрат.

Оптимизация – это процесс выбора наилучшего варианта или процесс приведения системы в наилучшее (оптимальное) состояние, который состоит в нахождении всех максимизирующих или минимизирующих элементов или седловых точек. Оптимизация  лежит в основе экономического анализа. В пассивных экономических моделях (таких, как изучающие общее равновесие) нас интересует оптимальное поведение лица, принимающего решение. В активных моделях (таких, как модели эффективного роста) мы сами заинтересованы в получении оптимума. В последние годы появилась тенденция к переходу от моделей типа «затраты – выпуск» к моделям анализа производственных процессов, от простейших моделей роста к моделям, изучающим траектории оптимального и эффективного роста.

Методы оптимизации – методы поиска экстремума функции (в практических задачах – критериев оптимальности) при наличии ограничений или без ограничений очень широко используются на практике. Это, прежде всего оптимальное проектирование (выбор наилучших номинальных технологических режимов, элементов конструкций, структуры технологических цепочек, условий экономической деятельности, повышение доходности и т.д.), оптимальное управление построением нематематических моделей объектов управления (минимизации невязок различной структуры модели и реального объекта) и многие другие аспекты решения экономических и социальных проблем (например, управление запасами, трудовыми ресурсами, транспортными потоками и т.д.).

Методы оптимизации являются разделом математического моделирования.

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

Модель – это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное  изучение дает новые знания об объекте–оригинале.

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

        установить границы подлежащей оптимизации системы;

        определить количественный критерий, на основе которого можно произвести анализ вариантов с целью выявления «наилучшего»;

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

        построить модель, отражающую взаимосвязи между переменными.

Эта последовательность действий составляет содержание процесса постановки задачи оптимизации.

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

Задачи оптимального распределения ресурсов. В общем ви­де эти задачи могут быть описаны следующим образом. Имеется некоторое количество ресурсов, под которыми можно понимать денежные средства, материальные ресурсы (например, сырье, по­луфабрикаты, трудовые ресурсы, различные виды оборудования и т.д.). Эти ресурсы необходимо распределить между различны­ми объектами их использования по отдельным промежуткам вре­мени или по различным объектам так, чтобы получить макси­мальную суммарную эффективность от выбранного способа распределения. Показателем эффективности может служить, на­пример, прибыль, товарная продукция, фондоотдача (задачи мак­симизации критерия оптимальности) или суммарные затраты, се­бестоимость, время выполнения данного объема работ и т.п. (задачи минимизации критерия оптимальности).

Имеется начальное количество средств Р₀, которое необходи­мо распределить в течение п лет между S предприятиями. Сред­ства и_ki (k = 1,..., n; i = 1,..., S), выделенные в k-м году i-му пред­приятию, приносят доход в размере f_ki(u_ki) и к концу года возвращаются в количестве _ki(u_ki). В последующем распределе­нии доход может либо участвовать (частично или полностью), ли­бо не участвовать.

Требуется определить такой способ распределения ресурсов (количество средств, выделяемых каждому предприятию в каж­дом плановом году), чтобы суммарный доход от S предприятий за п лет был максимальным. Следовательно, в качестве показателя эффективности процесса распределения ресурсов за п лет прини­мается суммарный доход, полученный от S предприятий:

                                                         (1)

Количество ресурсов в начале k-го года будем характеризовать величиной P_n1 (параметр состояния). Управление на k-том шаге состоит в выборе переменных u_k1, u_k2, …, u_ks, обозначающих ресурсы, выделяемые в k-том году i-му предприятию.

Если предположить, что доход в дальнейшем распределении не участвует, то уравнение состояния процесса имеет вид

                                      (2)

Если же некоторая часть дохода участвует в дальнейшем рас­пределении в каком-нибудь году, то к правой части последнего равенства прибавляется соответствующая величина.

Требуется определить п_s неотрицательных переменных и_ki, удовлетворяющих условиям (2) и максимизирующих функ­цию (1).

Оптимальное управление запасами. Класс задач, в которых рассматривается оптимальное управление запасами, является од­ним из наиболее сложных. Это обусловлено тем, что в задачах управления запасами процесс, естественно, разворачивается во времени, причем управление заключается в том, что решение на данном промежутке времени принимается с учетом того состоя­ния, к которому пришла система за предшествующие периоды. Кроме того, эти задачи связаны, как правило, с дискретным харак­тером переменных и, следовательно, решаются довольно сложно.

Проблема управления запасами является одной из важнейших областей практического приложения экономико-математических методов, в том числе методов математического программирова­ния.

При формулировке задач управления запасами используют следующие понятия.

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

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

В такой общей постановке подобные задачи могут иметь са­мое разнообразное практическое применение. Например, под за­пасами можно понимать продукцию предприятия, которая произ­водится непрерывно (пополнение) и отгружается потребителям определенными дискретными партиями (расход). При этом спрос на продукцию предполагается наперед заданным (детерминиро­ванный спрос) или подверженным случайным колебаниям (сто­хастическая задача). Управление запасами состоит в определении размеров необходимого выпуска продукции для удовлетворения заданного спроса. Цель — минимизация суммарных затрат на хранение и пополнение запасов.

Под запасами можно понимать запасы сырья или других мате­риалов, поставляемых дискретными партиями (пополнение), ко­торые должны обеспечить непрерывное потребление в процессе производства (расход). Критерием оптимальности могут служить суммарные затраты на хранение запасов, замораживание оборот­ных средств и поставки запасов.

Запасами могут быть товары, поставляемые в магазин опреде­ленными партиями и предназначенные для удовлетворения непрерывного, но подверженного случайным колебаниям поку­пательского спроса. Критерий оптимальности — суммарные за­траты на поставки, хранение запасов и изменение производствен­ного ритма; связи с вариациями спроса.

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

Задачи о замене. Одной из важных экономических проблем, с которыми приходится встречаться на практике, является опреде­ление оптимальной стратегии в замене старых станков, произ­водственных зданий, агрегатов, машин и т.д., другими словами, старого оборудования на новое.

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

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

Оптимальная стратегия замены оборудования состоит в опре­делении оптимальных сроков замены. Критерием оптимальности при определении сроков замены может служить либо прибыль от эксплуатации оборудования, которую следует максимизировать, либо суммарные затраты на эксплуатацию в течение рассматри­ваемого промежутка времени, подлежащие минимизации.

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

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

Существует достаточно большое количество численных методов оптимизации. Основные из них можно классифицировать следующим образом:

        по размерности решаемой задачи: одномерные и многомерные;

        по способу формирования шага многомерные методы делятся на следующие виды:

         градиентные:

o     по способу вычислений градиента: с парной пробой и с центральной пробой;

o     по алгоритму коррекции шага;

o     по алгоритму вычисления новой точки: одношаговые и многошаговые;

         безградиентные: с поочередным изменением переменных и с одновременным изменением переменных;

         случайного поиска: с чисто случайной стратегией и со смешанной стратегией;

          по наличию активных ограничений;

          без ограничений (безусловные);

          с ограничениями (условные);

          с ограничениями типа равенств;

          с ограничениями типа неравенств;

          смешанные.

Методы одномерной оптимизации являются базой для некоторых «многомерных» методов. В многомерной градиентной оптимизации строится улучшающая последовательность в зависимости от скорости изменения критерия по различным направлениям. При этом под улучшающей последовательностью понимается такая последовательность х₀, х₁, …, х_i, …, в каждой точке которой значение критерия оптимальности лучше, чем в предыдущей. В безградиентных методах величина и направление шага к оптимуму при построении улучшающей последовательности формируется однозначно по определенным детерминированным функциям в зависимости от свойств критерия оптимальности в окрестности текущей точки без использования производных (т.е. градиента). Случайные методы используются в задачах высокой размерности. Многомерная условная оптимизация учитывает активные ограничения, выраженные в виде равенств и неравенств. В каждом из рассмотренных направлений имеется большое число методов, обладающих своими достоинствами и недостатками, которые зависят, прежде всего, от свойств функций, экстремум которых ищется. Одним из сравнительных показателей качества метода является количество значений функции, которое нужно вычислить для решения задачи с заданной погрешностью. Чем это число меньше, тем при прочих равных условиях эффективнее метод.

В теоретических и математических задачах принято рассматривать задачи оптимизации как задачи поиска минимума функции. Даже методы имеют общее название – методы спуска. Однако при решении реальных практических задач очень часто встречаются задачи и на максимум (например, максимизация дохода, объема выпуска и т.д.). Конечно, легко перейти от одного вида экстремума к другому путем смены знака у критерия оптимальности, но это делают в прикладных нематематических задачах не всегда, чтобы не терять содержательную нить задачи.

Вопросы к главе 1

1.    Почему необходимо использование математики в экономике?

2.    Что такое математическая модель?

3.    Как строится математическая модель экономического явления и объекта? Приведите пример построения модели.

4.    Что такое оптимизация?

5.    Какие существуют методы оптимизации?

6.    Какие экономические задачи решаются методами оптимизации?

 

Глава 2. ОСНОВЫ ТЕОРИИ ОПТИМИЗАЦИИ

 

Термином «оптимизация» обозначают процесс, позволяющий получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего, или «оптимального», решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

Рассматривая некоторую произвольную систему, описываемую m уравнениями с n неизвестными, можно выделить три основных типа задач:

      если m = n, то задачу называют алгебраической. Такая задача обычно имеет  единственное решение;

      если m > n, то задача переопределена, как правило, не имеет решений;

      если m < n, то задача недоопределена, имеет бесконечно много решений.

В практике чаще всего приходится иметь дело с задачами третьего типа.

Введем ряд определений.

2.1. Параметры плана

Определение. Параметры плана – это независимые переменные параметры, которые полностью и однозначно определяют решаемую задачу.

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

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

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

Обозначения. Обычно число проектных параметров обозначают через n, х – сами проектные параметры с соответствующими индексами

х₁, х₂, …, х_n – n проектных параметров задачи.

2.2. Целевая функция (план)

Определение. Целевая функция – выражение, значение которого стремимся  сделать максимальным или минимальным.

Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (n+1)-мерную поверхность.

1)      Если имеется только один проектный параметр, то целевую функцию можно представить кривой на плоскости (рис. 1).

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



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

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

      кусочно-гладкой функцией;

      таблицей;

      только целыми значениями;

      двумя значениями – да или нет (дискретная функция).

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

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

Вопросы к главе 2

1.        Что такое параметры плана?

2.        Приведите пример параметров плана.

3.        Дайте определение целевой функции.

4.        Как изображается целевая функция?

 

Глава 3. ФУНКЦИЯ ОДНОЙ ПЕРЕМЕННОЙ

 

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

3.1. Определение функции одной переменной и её свойства

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

Определение. Функция f(x) представляет собой правило, которое позволяет каждому значению хХ поставить в соответствие единственное значение y = f(x)У, где х – независимая переменная (аргумент), y – зависимая переменная (значение функции). Говорят, что функция f имеет область определения D(f)=X и область значений R(f)Y.

Определение. Множество пар {(x, f(x)): xD(f)} называется графиком функции f.

Существует три основных способа задания функции:

      при аналитическом способе задания функции зависимость между переменными определяется формулой;

      при табличном способе задания функции выписываются в определенном порядке значения аргумента и соответствующие значения функции;

      при графическом способе задания функции зависимость между переменными отражается с помощью графика.

Рассмотрим некоторые функциональные зависимости, используемые в экономике:

      функция спроса – зависимость спроса D на некоторый товар от его цены p;

      функция предложения – зависимость предложения S некоторого товара от его цены p;

      функция полезности – субъективная числовая оценка данным индивидом полезности и и количества х товара для него;

      функция издержек – зависимость издержек I на производство х единиц продукции;

      налоговая ставка – зависимость налоговой ставки N в процентах от величины годового дохода Q.

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

Определение. Функция f(x) имеет предел b, когда х стремится к а, если значения f(x) сколь угодно близко приближаются к числу b, когда значения переменной х сколь угодно близко приближаются к числу а.

Обозначение. .

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

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

Определение. Функция, непрерывная в каждой точке своей области определения, называется непрерывной функцией. В противном случае функцию называют разрывной.

График непрерывной функции можно начертить без отрыва руки.

Непрерывные функции обладают следующими свойствами:

      сумма или произведение непрерывных функций является непрерывной функцией;

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

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

Определение. Функция f(x) называется возрастающей (убывающей) на множестве X, если из того, что x₁2 вытекает, что f(x₁)2) (f(x₁)>f(x₂)). Функция f(x) называется неубывающей (невозрастающей) на множестве X, если из того, что x₁ x₂, x₁, x₂ X вытекает, что f(x₁) f(x₂) ( f(x₁) f(x₂)).

Теорема. Пусть функция f(x) дифференцируема на интервале (a, b). Тогда:

      если первая производная функции всюду на этом интервале, то функция возрастает на нем;

      если первая производная  всюду на этом интервале, то функция убывает;

      первая производная всюду на этом интервале, то функция постоянна на этом интервале.

Определение. Возрастающие, убывающие, неубывающие, невозрастающие функции называются монотонными.

Замечание. Монотонная функция не обязательно должна быть непрерывной.



Пример 1. Найти интервалы монотонности функции  f(x)=(1-x²)³.

Решение. Находим производную:  Решим уравнение . Получим х₁=0, х₂=1, х₃=-1. Функция f(x) определена и непрерывна на всей числовой оси. Поэтому точки х₁, х₂, х₃ являются критическими точками. Других критических точек нет, так как  существует всюду.

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

   Таблица 1

х	-2	-1	-1/2	0	1/2	1	2
	+	0	+	0	-	0	-
f(x)	возр.		возр.		убыв.		убыв.

 

В первой строке помещены все критические точки в порядке расположения их на числовой оси; между ними вставлены промежуточные точки, расположенные слева и справа от критических точек. Во второй строке помещены знаки производной в указанных промежуточных точках. В третьей строке – заключение о поведении функции на исследуемых интервалах. На интервале (-; 0) функция возрастает, на интервале           (0; +) функция убывает.

Определение. Функция f(x) является унимодальной на отрезке [a, b] в том и только в том случае, если она монотонна по обе стороны от единственной на рассматриваемом интервале оптимальной точки х*.

Пример 2. Приведем примеры графиков унимодальных функций:

      на рис. 6 непрерывная функция;

      на рис. 7 – разрывная функция;

      на рис. 8 – дискретная функция.


Множество функций, унимодальных на отрезке [a; b], будем обозначать Q[a; b].

Для проверки унимодальности функции f(x) на практике обычно используют следующие критерии:

1)        если функция f(x) дифференцируема на отрезке [a; b]  и производная не убывает на этом отрезке, то f(x)Q[a; b];

2)        если функция f(x) дважды дифференцируема на отрезке [a; b] и при х[a; b], то f(x)Q[a; b].

Пример 3. Показать, что функция унимодальна на отрезке [3; 5].

Решение. Найдем последовательно первую и вторую производные функции:



Решим уравнение . Корни полученного квадратного трехчлена х₁=2 и х₂=3. Следовательно, и, в частности, при х [3; 5]. Используя второй критерий унимодальности, получаем, что f(x)Q[3; 5].

Пример 4. Выяснить, является ли функция f(x)=x²-3x+xlnx на отрезке [1;2] унимодальной.

Решение. Найдем первую и вторую производные функции:



Решим уравнение . Полученное уравнение имеет единственный корень х=-0,5. Следовательно, если х-0,5 и, в частности, при х[1; 2]. Используя второй критерий унимодальности, получаем, что f(x)Q[1; 2].

Определение. Рассмотрим множество SR. Мы можем определить соответствие, с помощью которого каждой точке xS приписывается единственное числовой значение. Такое соответствие называется скалярной функцией f, определенной на множестве S.

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

3.2. Исследование функций в экономике. Нахождение максимума прибыли

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

.

1)      Находим производную этой функции



2)      Приравниваем производную нулю



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

3)      Анализируем характер изменения знака производной

При   и прибыль убывает.

При   и прибыль возрастает.

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

4)      Принятие решения

Каким же будет оптимальный объем выпуска для фирмы? Ответ на вопрос зависит от дополнительного исследования производственных мощностей фирмы. Если фирма не может производить за рассматриваемый период больше 8 единиц продукции (p(q=8)=p(q=0)=10), то оптимальным решением для фирмы будет вообще ничего не производить, а получать доход от сдачи в аренду помещений и/или оборудования. Если же фирма способна производить за рассматриваемый период больше 8 единиц продукции, то оптимальным решением для фирмы будет выпуск на пределе своих производственных мощностей.

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

3.3.         Определение глобального экстремума

Необходимо максимизировать f(x) при ограничениях , где a и b – установленные границы изменения значений переменной х. Проверку наличия локального оптимума

необходимо проводить не только в стационарных точках, но и в граничных точках интервала.

Алгоритм определения глобального максимума (минимума):

Шаг 1. Приравнять  и найти все стационарные точки.

Шаг 2. Выбрать все стационарные точки, которые расположены в интервале [a, b]. Обозначим эти точки через  х₁, х₂, …, х_n. Проверку наличия локального оптимума следует проводить только на множестве указанных точек, дополненном точками a и b.

Шаг 3. Найти наибольшее (наименьшее) значение f(x)  из множества f(a), f(b), f(x₁), …, f(x_n). Это значение соответствует глобальному максимуму (минимуму).

Пример 5. Найти наибольшее и наименьшее значение функции на отрезке [-4; 4].

Решение. Найдем критические точки функции u, лежащие внутри отрезка [-4; 4], и вычислим ее значения в этих точках:  в точках х = -1, х = 3. Эти точки лежат внутри рассматриваемого отрезка и являются критическими.

Вычислим значения функции на концах отрезка и в критических точках:

u(-1) =40, u(3) = 8, u(-4) = -41, u(4) = 15.

Сравнивая все вычисленные значения функции во внутренних критических точках и на концах отрезка, заключаем: наибольшее значение функции u на отрезке [-4; 4] равно 40 и достигается ею во внутренней критической точке х = -1, а ее наименьшее значение равно –41 и достигается на левой границе отрезка х = -4.

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

Замечание. Для унимодальной функции локальный оптимум является глобальным.

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

3.4.         Выпуклость, вогнутость функции

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

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

Определение. Точкой перегиба графика функции называется точка этого графика, которая отделяет выпуклую его часть от вогнутой (рис. 11).


Теорема 2. Пусть функция f(x) определена в некоторой окрестности точки b и дважды дифференцируема в ней всюду, кроме, быть может самой точки b. Тогда, если при переходе через точку b вторая производная меняет знак, то точка b есть точка перегиба графика функции.

Теорема 3. Если вторая производная функции  в точке b равна нулю,то точка b – точка перегиба графика функции.

Алгоритм определения точек перегиба:

Шаг 1. Найти и точки х, в которых  или не существует, а  график функции f(x) непрерывен и которые лежат внутри области его расположения.

Шаг 2. Определить знак слева и справа от каждой из этих точек. Исследуемая точка х будет абсциссой точки перегиба, если по разные стороны от неё имеет разные знаки.

Пример 6. Определить направление выпуклости и точки перегиба кривой

Решение. Ищем точки х, в которых  или не существует, а кривая непрерывна и которые лежат внутри области расположения кривой:



в точках х = 0, х = 1. Эти точки являются искомыми, так как область расположения и область непрерывности данной кривой есть вся ось абсцисс. Других точек х, которые могли бы быть абсциссами точек перегиба, нет, так как  существует всюду.

Исследуем найденные точки, определяя знак второй производной слева и справа от каждой из них. Запишем это исследование в табл. 2:

                                                                                                 Таблица 2

х	-1	0	1/2	1	10
	-	0	-	0	+
у	выпукла	нет перегиба	выпукла	перегиб	вогнута

Из табл. 2 следует, что х = 1 есть абсцисса точки перегиба кривой: у(1) = 2. Поскольку эта кривая непрерывная, то во всем интервале (-, 1) она выпукла, а во всем интервале (1, +) – вогнута.

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

1)        если унимодальная функция выпукла, то она имеет глобальный максимум;

2)        если унимодальная функция вогнута, то она имеет глобальный минимум.

3.4.         Критерий оптимальности

При анализе задач возникают два общих вопроса:

1)      Вопрос анализа в «статике». Как определить, представляет ли данная точка х* оптимальное решение задачи?

2)      Вопрос анализа в «динамике». Если х* не является точкой оптимума, то какая последовательность действий приводит к получению оптимального решения?

В этом разделе основное внимание уделяется решению вопроса анализа «в статике», а именно построению множества критериев оптимальности, позволяющих определить, является ли данное решение оптимальным.

Определение. Функция f(x), определенная на множестве S, достигает своего глобального минимума в точке х**S в том и только в том случае, если

f(x**)  f(x) для всех х  S.

Определение. Функция f(x), определенная на множестве S, имеет локальный минимум в точке х*  S в том и только в том случае, если f(x*)  f(x) для всех х, удаленных от х*

на расстояние, меньшее , то есть если существует >0 такое, что для любых х, удовлетворяющих условию /х-х*/<, выполняется неравенство f(x*)  f(x).

Пример 7. Рассмотрим график некоторой функции y = f(x) (рис. 12). Тогда имеем:

х₁ – точка локального максимума;

х₂ – точка локального минимума;

х₃ – точка глобального максимума;

х₄ – точка глобального минимума.

Замечание.

1)      Всякая точка глобального минимума является и точкой локального минимума этой функции. Обратное, вообще говоря, неверно.

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

3)      Если функция обладает свойством унимодальности, то локальный минимум автоматически является глобальным минимумом.

4)      Если функция не является унимодальной, то возможно наличие нескольких локальных оптимумов, при этом глобальный минимум можно определить путем нахождения всех локальных оптимумов и выбора наименьшего из них.
3.6. Идентификация оптимумов

Теорема 1. Необходимые условия того, что х* является точкой локального минимума (максимума) дважды дифференцируемой функции f на открытом интервале (a,b), выражаются следующими соотношениями:



Эти условия необходимы, но не достаточны для того, чтобы точка х* была точкой локального минимума (максимума).

Определение. Стационарной точкой называется точка х*, в которой

 ,

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

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

1)        если n – нечетное, то х* - точка перегиба;

2)        если n – четное, то х* - точка локального оптимума.

Кроме того,

a)    если эта производная положительная, то х* - точка локального минимума;

б)  если эта производная отрицательная, то х* - точка локального максимума.

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

Пример 8.

Рассмотрим функцию

 

Эта функция непрерывна во всех точках действительной оси, но недифференцируема при х=2. Функция достигает максимума в точке х=2, которая не является стационарной в соответствии с данным выше определением. Это подтверждает тот факт, что теорема 1 является необходимым, но не достаточным условием оптимума.

Пример 9. Найти и идентифицировать оптимумы функции

Решение. Найдем первую производную функции:

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

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

х	f(x)
0	-8	2

 

Значит, х=0 – точка  минимума.

Пример 10. Найти и идентифицировать оптимумы функции



Решение. Сначала найдем первую производную функции:

.

Найдем стационарные точки. Для этого решим уравнение:

Следовательно, стационарные точки:  

Найдем вторую производную

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

 

x	f(x)
0	36	0
1	27.5	60
2	44	-120
3	5.5	540

 

Значит, х=1 х=3 – точки локальных минимумов, х=2 – точка локального максимума.



Чтобы идентифицировать точку х=0, найдем и вычислим третью производную:

Так как  и n=3 – нечетное, то (по теореме 2) х*=0 – точка перегиба.

Вопросы к главе 3

1.        Приведите определение функции.

2.        Что такое область определения и область допустимых значений функции?

3.        Какие существуют способы задания функции? Приведите конкретные примеры каждого способа.

4.        Дайте определения возрастания и убывания функции. Приведите примеры возрастающей и убывающей функций.

5.        Как проверить, является ли функция возрастающей или убывающей?

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

2.        Что такое точка перегиба и как её идентифицировать?

3.        Как проверить, является ли функция выпуклой или вогнутой?

4.        В чем состоит свойство унимодальности функций?

5.        Пусть данная точка удовлетворяет достаточным условиям существования локального минимума. Как установить, является ли этот минимум глобальным?

6.        Приведите алгоритм определения глобального оптимума.

Глава 4. ОДНОМЕРНАЯ ОПТИМИЗАЦИЯ

4.1. Методы исключения интервалов

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

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


Теорема. Пусть функция f унимодальна на замкнутом интервале , а её минимум достигается в точке х*. Рассмотрим точки х₁ и х₂, расположенные в интервале таким образом, что a < x₁ < x₂ < b. Сравнивая значения функции в точках х₁ и х₂, можно сделать следующие выводы:

1)      Если f(x₁) > f(x₂), то точка минимума f(x) не лежит в интервале (а, х₁), т.е.  (см. рис. 14).

2)      Если f(x₁) < f(x₂), то точка минимума не лежит в интервале (х₂, b), т.е.  (см. рис. 15).

Замечание. Если f(x₁) = f(x₂), то можно исключить оба крайних интервала      (а, х₁) и (х₂, b); при этом точка минимума должна находится в интервале (х₁, х₂).

Согласно приведенной выше теореме, которую иногда называют правилом исключения интервалов, можно реализовать процедуру поиска, позволяющую найти точку оптимума путем последовательного исключения частей исходного ограниченного интервала. Поиск завершается, когда оставшийся подынтервал уменьшается до достаточно малых размеров. Заметим, что правило исключения интервалов, устраняет необходимость полного перебора всех допустимых точек. Несомненным достоинством поисковых методов такого рода является то, что они основаны лишь на вычислении значений функций. При этом не требуется, чтобы исследуемые функции были дифференцируемы; более того, допустимы случаи, когда функцию нельзя даже записать в аналитическом виде. Единственным требованием является возможность определения значений функции f(x) в заданных точках x с помощью прямых расчетов или имитационных экспериментов.

Вообще в процессе применения рассматриваемых методов поиска можно выделить два этапа:

        этап установления границ интервала, на котором реализуется процедура поиска границ достаточно широкого интервала, содержащего точку оптимума;

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

В данном разделе рассматриваются методы решения одномерных задач оптимизации вида



где х – скаляр, a и b – соответственно концы интервала, из которого берутся значения переменной х.

В основном рассматриваются алгоритмы, связанные с построением улучшающей последовательности. Решением задачи называется х*, при котором f(x*)  f(x) для любого значения . При практическом решении задач не будем различать два значения x_i и x_i+1, если |x_i-x_i+1|, где  - задаваемая погрешность решения.

 

---

Некрасова М.Г. - Методы оптимизации