,

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

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

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

При решении практических задач находят эффективное применение различные классы оптимизационных задач (линейные, нелинейные, динамические, целочисленные, игровые).

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

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

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

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

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

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

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

Понимая, что объять необъятное невозможно, в данном курсе мы попытаемся отразить наиболее значимые и перспективные направления в теории оптимизации, а именно:

- классические методы нахождения экстремумов функции;

- нахождение оптимальных решений в условиях определенности (линейное, нелинейное, целочисленное и динамическое программирование);

- принятие решений в условиях риска - стохастическое программирование;

- принятие решений в условиях неопределенности (метод анализа иерархий).

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

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

Изучение теоретических разделов курса сочетается с выполнением соответствующих лабораторных работ на ЭВМ.

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

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

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

1.1 Экстремумы функции одной переменной

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

Минимум функции на множестве обозначается как или просто .

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

Максимум функции на множестве обозначается как или просто .

Различают локальные минимумы и максимумы и глобальные минимумы и максимумы. На рис . 1 точки - точки локального минимума, точки - точки локального максимума функции на отрезке . Причем точки являются одновременно и точками глобального минимума и максимума, соответственно.

Рис. 1. Глобальные и локальные оптимумы

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

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

Рис. 2. Различные типы экстремумов функции

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

Рис. 3. Функции, удовлетворяющие необходимым условиях экстремума

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

Сравнение знаков производных. При этом способе исследования точки , «подозреваемой» на экстремум, в точках и определяется знак производной . Если знаки производной в этих точках различны, в точке имеется экстремум функции. Тип экстремума может быть определен по изменению знака производной при переходе от точки к точке . Если знак производной меняется с (+) на (-), то в точке - максимум, если наоборот - с (-) на (+), то - минимум. Если же знаки производной в точках и совпадают, то в точке нет ни максимума, ни минимума, т.е. она не является экстремальной.

Рис.4. Проверки точки, на наличие экстремума

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

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

Пример 1. Найти экстремум функции и определить характер экстремума.

Решение: Стационарная точка определяется из решения уравнения :

.

Отсюда . В точке с координатой может быть экстремум. Вычисление второй производной дает:

.

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

1.2 Экстремумы функций многих переменных

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

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

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

.

Критерий Сильвестра. Матрица А положительно определена тогда и только тогда, когда все ее главные угловые миноры положительны. Напомним, что главными минорами матрицы А называются определители, соответствующие главным подматрицам матрицы А.

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

Пример 2. Найти экстремум функции и определить характер экстремума.

Решение: Стационарная точка определяется из решения системы уравнений первых производных по переменным , и приравненных к нулю:

Отсюда , , . Матрица вторых производных

положительно определена

,

,

Следовательно, в точке , , функция достигает минимума. Значение функции в точке минимума .

1.3 Метод множителей Лагранжа

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

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

Пусть требуется найти экстремум функции

,(1)

которая зависит от n переменных , , связанных в свою очередь соотношениями:

, .(2)

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

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

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

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

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

Нарисуем на плоскости линии уровня функции (то есть кривые и кривую ограничений (рис.5).

Рис.5. Геометрическая интерпретация

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

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

,(3)

где - некоторое число, отличное от нуля, и являющееся множителем Лагранжа.

Введем функцию, которая называется функцией Лагранжа:

. (4)

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

(5)

Мы получили систему, первые два уравнения которой эквивалентны необходимому условию локального экстремума (1), а третье - уравнению . Из (5) можно найти . При этом , поскольку в противном случае градиент функции обращается в нуль в точке , что противоречит нашим предположениям. Следует заметить, что найденные таким образом точки могут и не являться искомыми точками условного экстремума -- рассмотренное условие носит необходимый, но не достаточный характер. Нахождение условного экстремума с помощью вспомогательной функции и составляет основу метода множителей Лагранжа, примененного здесь для простейшего случая двух переменных. Оказывается, вышеприведенные рассуждения обобщаются на случай произвольного числа переменных и уравнений, задающих условия.

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

Пусть V - заданный объем цилиндрической емкости. Необходимо найти диаметр d и высоту h емкости, при которых площадь поверхности емкости S была бы минимальной (экономия материала на ее изготовление).

Критерием оптимальности рассматриваемой задачи в данном случае является поверхность цилиндрической емкости

.(3)

Объем емкости описывается выражением

(4)

или в общем виде

.(5)

С помощью метода множителей Лагранжа составим вспомогательную функцию L для этой задачи:

.(6)

Дифференцируя выражение (6) по переменным d и h находим систему уравнений, соответствующих системе (5):

.(7)

,(8)

.(9)

Из уравнения (8) получим:

, .(10)

Первое из найденных значений , как нетрудно видеть, отвечает нулевому значению критерия оптимальности (3), что хотя и соответствует экстремальной точке функции S, т.е. точке минимума, но не удовлетворяет требованию получения заданного объема V, т.е. требованию (9). Поэтому для дальнейших рассуждений в соотношениях (10) имеет смысл только второе значение

.

Подставляя это значение в уравнение (7) , найдем выражение h через :

.(11)

Теперь можно определить величину , если подставить в уравнение (9) значения d и h, выраженные через . В результате получим:

.(12)

Отсюда

. (13)

Подставляя найденное значение в форумы (10) и (11) найдем:

,(13)

.(14)

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

Это так называемые задачи оптимизации безусловных экстремумов.

2.Материал к практическим занятиям по классическим методам анализа функций

Упражнения

1. Исследовать на экстремум следующие функции

2. Решить задачи помощью метода неопределенных множителей Лагранжа

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