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

Министерство образования и науки Российской Федерации

Волжский политехнический институт (филиал)

федерального государственного бюджетного образовательного учреждения

высшего профессионального образования

«Волгоградский государственный технический университет»

 

Инженерно-экономический факультет

Кафедра «Социально-гуманитарные дисциплины»

 

 

 

 

СЕМЕСТРОВАЯ РАБОТА

по анализу эффективности систем управления

на тему: «Исследование методов условной оптимизации»

 

 

 

 

 

 

 

 

                                                                                                                                      Выполнил:

студент гр. ВЭМ-313

Даудова А.И.

Проверила:

Гончарова Е.В.

 

 

 

Волжский,2014.

Содержание

 

Введение………………………………………………………………………3
1. Понятие оптимизации и её история возникновения…………………….4
1.2 Классификация методов оптимизации………………………………….7
2. Прямые методы условной  оптимизации………………………………..11
Заключение…………………………………………………………………..21
Список литературы………………………………………………………….22

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

 

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

 

 

 

 

 

 

 

 

 

 

 

 

1. Понятие оптимизации и её история возникновения

 

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

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

Задачи линейного программирования были первыми подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 году Фурье и затем в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

Присутствие в названии дисциплины термина «программирование» объясняется тем, что первые исследования и первые приложения линейных оптимизационных задач были в сфере экономики, так как в английском языке слово «programming» означает планирование, составление планов или программ. Вполне естественно, что терминология отражает тесную связь, существующую между математической постановкой задачи и её экономической интерпретацией (изучение оптимальной экономической программы). Термин «линейное программирование» был предложен Данцигом в 1949 году для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях.

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

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

В 1931 году венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода». Канторовичем совместно с М. К. Гавуриным в 1949 году разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Канторовича, Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем.

Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 году Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования — симплекс-метод — был опубликован в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна (англ.), А. Таккера (англ.), Гасса (Saul. I. Gass), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

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

Начиная с 1955 году опубликовано много работ, посвященных квадратическому программированию (работы Била,Баранкина и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования. В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.[4].

 

 

 

 

 

 

 

 

 

 

 

1.2 Классификация методов  оптимизации

 

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

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

• Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

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

Существующие в настоящее время методы поиска можно разбить на три большие группы:

1. детерминированные;

2. случайные (стохастические);

3. комбинированные.

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

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

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

• В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:

• если   и   — выпуклые функции, то такую задачу называют задачей выпуклого программирования;

• если  , то имеют дело с задачей целочисленного (дискретного) программирования.

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

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

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

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

Помимо того, оптимизационные методы делятся на следующие группы:

• аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера);

• численные методы;

• графические методы.

В зависимости от природы множества X задачи математического программирования классифицируются как:

• задачи дискретного программирования (или комбинаторной оптимизации) — если X конечно или счётно;

• задачи целочисленного программирования  если X является подмножеством множества целых чисел;

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

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

Кроме того, разделами математического программирования являются параметрическое программирование,динамическое программирование и стохастическое программирование.

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

Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования:

• Определение границ системы оптимизации

• Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается

• Выбор управляемых переменных

• «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные)

• Определение ограничений на управляемые переменные

• … (равенства и/или неравенства)

• Выбор числового критерия оптимизации (например, показателя эффективности)

• Создаём целевую функцию [ 5, 87 с.].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Прямые методы условной  оптимизации

 

Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах (в дальнейшем без ограничения общности будут рассматриваться задачи поиска минимального значения функции):

f(x) -> min

при ограничениях:

gi(x)   0, i   1, ..., k;

hj(x)   0, j   1, .., m;

a   x   b.

Здесь x, a, b — векторы-столбцы:

,  , 

Оптимизируемую функцию f(x) называют целевой функцией. Каждая точка x в n-мерном пространстве переменных x1, ..., х, в которой выполняются ограничения задачи, называется допустимой точкой задачи. Множество всех допустимых точек называется допустимой областью G . Будем считать, что это множество не пусто. Решением задачи считается допустимая точка х*, в которой целевая функция f(х) достигает своего минимального значения. Вектор х* называют оптимальным. Если целевая функция f(x) и ограничения задачи представляют собой линейные функции независимых переменных х1, ..., хn, то соответствующая задача является задачей линейного программировании, в противном случае - задачей нелинейного программирования. В дальнейшем будем полагать, что функции f(x), g(x), i   1, ..., k , hj(x), j   1, …, m, - непрерывные и дифференцируемые.

В общем случае численные методы решения задач нелинейного программирования можно разделить на прямые и непрямые. Прямые методы оперируют непосредственно с исходными задачами оптимизации и генерируют последовательности точек {x[k]}, таких, что f(х[k+1])   f(x[k]). В силу этого такие методы часто называют методами спуска. Математически переход на некотором k-м шаге (k.   0, 1, 2, ...) от точки х[k] к точке x[k+1] можно записать в следующем виде:

x[k+l]   x[k] + akp[k],

где р[k] — вектор, определяющий направление спуска; аk — длина шага вдоль данного направления. При этом в одних алгоритмах прямых методов точки х[k] выбираются так, чтобы для них выполнялись все ограничения задачи, в других эти ограничения могут нарушаться на некоторых или всех итерациях. Таким образом, в прямых методах при выборе направления спуска ограничения, определяющие допустимую область G, учитываются в явном виде.

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

Рассмотрим некоторые алгоритмы прямых методов.

Метод проекции градиента

Рассмотрим данный метод применительно к задаче оптимизации с ограничениями-неравенствами. В качестве начальной выбирается некоторая точка допустимой области G. Если х[0] - внутренняя точка множества G (Рис. 3.1), то рассматриваемый метод является обычным градиентным методом:

x[k+l]   x[k] –akf’(x[k]), k   0, 1, 2, ...,

где 

градиент целевой функции f(х) в точке x[k].

После выхода на границу области G в некоторой граничной точке х[k] , k   0, 1, 2,..., движение в направлении антиградиента -f’(х[k]) может вывести за пределы допустимого множества (см. Рис. 3.1). Поэтому антиградиент проецируется на линейное многообразие М, аппроксимирующее участок границы в окрестности точки х[k]. Двигаясь в направлении проекции вектора -f'(x[k]) на многообразие М, отыскивают новую точку х[k+1], в которой f(х[k+1])   f(x[k]), принимают х[k+1] за исходное приближение и продолжают процесс. Проведем более подробный анализ данной процедуры.

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

В точке х[k] часть ограничений-неравенств удовлетворяется как равенство:

hi(x)   0, j   1, ..., l; l   m.

Такие ограничения называют активными.

Обозначим через J набор индексов j(1   j   l) этих ограничений. Их уравнения соответствуют гиперповерхностям, образующим границу области G в окрестности точки х[k] . В общем случае эта граница является нелинейной (см. рис. 3.1). Ограничения hj(x), j   J, аппроксимируются гиперплоскостями, касательными к ним в точке х[k]:

Полученные гиперплоскости ограничивают некоторый многогранник М, аппроксимирующий допустимую область G в окрестности точки х[k] (см. Рис. 3.1).

Проекция р[k] антиградиента -f'(x[k]) на многогранник вычисляется по формуле

p[k]   P[-f’(x[k])].

Здесь Р - оператор ортогонального проектирования, определяемый выражением

Р   E – AT(AAT)-1A,

где Е - единичная матрица размеров п; А - матрица размеров lхn . Она образуется транспонированными векторами-градиентами аj, j   1, ..., l, активных ограничений. Далее осуществляется спуск в выбранном направлении:

x[k+1]   x[k] + akp[k].

Можно показать, что точка х[k+1] является решением задачи минимизации функции f(х) в области G тогда и только тогда, когда Р[-f’(x[k])]   0,

т. е , и u   (u1, ..., ul)   (ATA)-1AT(-f’(х[k]))   0.

Эти условия означают, что антиградиент (-f’(х[k])) целевой функции является линейной комбинацией с неотрицательными коэффициентами градиентов ограничений hj(x)   0.

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

1. В точке х[k] определяется направление спуска р[k].

2. Находится величина шага аk.

3. Определяется новое  приближение х[k+1].

Рассмотрим детально каждую из этих операций.

1. Определение направления  спуска состоит в следующем. Пусть  найдена некоторая точка х[k]   G и известен набор активных ограничений hi(х[k])   0, j   J. На основании данной информации вычисляют (-f’(х[k])) и определяют проекцию Р[-f’(х[k])]. При этом возможны два случая:

а) Р[-f’(х[k])] не равна 0. В качестве направления спуска р[k] принимают полученную проекцию;

б) Р[-f’(х[k])]   0, т. е.  .

Данное выражение представляет собой систему из п уравнений для определения коэффициентов иj. Если все иj   0, j   J, то в соответствии с вышеизложенным точка х[k] является решением задачи. Если же некоторый компонент иq   0, то соответствующий ему градиент выводится из матрицы А и порождается новая проецирующая матрица Р. Она определит новое направление спуска.

2. Для определения величины  шага аk целевая функция минимизируется по направлению р[k] при условии соблюдения ограничений задачи с установленной точностью. Последняя задается введением некоторого положительного числа e. Считают, что точка х удовлетворяет условиям задачи с заданной точностью, если hi(х)   e, j   1, ..., m. Величина шага аk определяется решением задачи вида:

f(x[k] + ар[k]) > min;

hj(x[k] + ар[k])   e, j   1, ..., m.

3. Определение нового приближения состоит в следующем. Очередная точка вычисляется по формуле

x[k+1]   x[k] + аkр[k].

Признаком сходимости является стремление к нулю векторов р[k]. Рассмотренный метод является в некотором смысле аналогом градиентных методов для решения задач на безусловный экстремум, и ему свойствен их недостаток - медленная сходимость.

Комплексный метод Бокса

Этот метод представляет модификацию метода деформируемого многогранника и предназначен для решения задачи нелинейного программирования с ограничениями-неравенствами. Для минимизации функции n переменных f(x) в n-мерном пространстве строят многогранники, содержащие q  п+1 вершин. Эти многогранники называют комплексами, что и определило наименование метода.

Введем следующие обозначения:

х[j, k]   (х1[j, k], …, хi[j, k], …, хn[j, k])T,

где j   1, ..., q; k   0, 1, 2, ... - j-я вершина комплекса на k-м этапе поиска;

х[h, k] - вершина, в которой значение целевой функции максимально, т. е. f(x[h, k])   max{f(x[l, k]), ..., f(x[q, k])}; x[h, k]- центр тяжести всех вершин, за исключением х[h, k] . Координаты центра тяжести вычисляются по формуле

, i   l, ..., n.

Алгоритм комплексного поиска состоит в следующем. В качестве первой вершины начального комплекса выбирается некоторая допустимая точка х[1, 0]. Координаты остальных q-1 вершин комплекса определяются соотношением

хj[j, 0]   аi + ri(bi - ai), i   1, ..., п; j   2, ..., q.

Здесь аi, bi - соответственно нижнее и верхнее ограничения на переменную хi', ri - псевдослучайные числа, равномерно распределенные на интервале [0, 1]. Полученные таким образом точки удовлетворяют ограничениям а   х   b , однако ограничения hj(x)   0 могут быть нарушены. В этом случае недопустимая точка заменяется новой, лежащей в середине отрезка, соединяющего недопустимую точку с центром тяжести выбранных допустимых вершин. Данная операция повторяется до тех пор, пока не будут выполнены все ограничения задачи. Далее, как и в методе деформируемого многогранника, на каждой итерации заменяется вершина х[h, k], в которой значение целевой функции имеет наибольшую величину. Для этого х[h, k] отражается относительно центра тяжести х[l, k] остальных вершин комплекса. Точка х[р, k], заменяющая вершину х[h, k], определяется по формуле

x[p, k]   (a+1)х[l, k] + ax[h, k],

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

Если f(x[р, k])   f(x[h, k]), то новая вершина оказывается худшей вершиной комплекса, В этом случае коэффициент ауменьшается в два раза. Если в результате отражения нарушается какое-либо из ограничений, то соответствующая переменная просто возвращается внутрь нарушенного ограничения. Если при отражении нарушаются ограничения hj(x)   0. то коэффициент а каждый раз уменьшается вдвое до тех пор, пока точка х[р, k] не станет допустимой. Вычисления заканчиваются, если значения целевой функции мало меняются в течение пяти последовательных итераций: |f(х[l, k+1]) – f(х [l, k])|   e, k   1, ..., 5, где e   - заданная константа. В этом случае центр тяжести комплекса считают решением задачи нелинейного программирования.

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

Выбор начальной точки допустимой области

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

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

J1   {j|hj( )  0, j   1, …, m};

J2   {j|hj( )  0, j   1, …, m};

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

hj(х)   0, j   J1;

hj(х) - z   0, j   J2;

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

,

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

h(x)   0, j   1, …, m.

Следовательно, минимальное значение z меньше нуля. В силу этого после конечного числа шагов некоторого прямого алгоритма будут получены x[0], z, такие, что z   0, и условия задачи удовлетворяются. Точка х[0] и принимается в качестве начальной для исходной задачи нелинейного программирования.[ 5, 210].

 

Заключение

 

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

Оптимизация  в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств. Теорию и методы решения задачи оптимизации изучает математическое программирование. Задача условной оптимизации заключается в поиске минимального или максимального значения скалярной функции f(x) n-мерного векторного аргументах (в дальнейшем без ограничения общности будут рассматриваться задачи поиска минимального значения функции).

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

 

 

 

 

 

 

 

 

Список литературы. 

 

1.Юдин Д.Б. Вычислительные  методы теории принятия решений. - М.: Наука. Гл. ред. физ.-мат. лит., 2009. - 320 с. (Теория и методы системного анализа.)

2.МЕТОДЫ ОПТИМИЗАЦИИ  ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ: методические  указания к лабораторным работам / сост. С.Д. Чернина. Екатеринбург: УГТУ-УПИ, 2007.36 с.

3. Габасов Р. Методы оптимизации / Р. Габасов, Ф.М. Кириллова. Минск: БГУ, 2010 .350 с.

4. http://ru.wikipedia.org/- [ Электронный ресурс ].

5. А.Г.Трифонов. "Постановка задачи оптимизации и численные методы ее решения", 2010.325 с.

6. Пантелеев А.В., Т.А.Летова. Методы оптимизации в примерах и задачах: Учебное пособие.- М.: Высш. Шк., 2009.

7. Сухарев А.Г., Тимохов А.В Курс методов оптимизации – М.: Наука, 2009.