Минимакс и многокритериальная оптимизация

МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)

КАФЕДРА СИСТЕМНОГО АНАЛИЗА

Реферат

на тему: Минимакс и многокритериальная оптимизация

Работу выполнил:

Студент 137-й группы

Баранов А.В.

Работу проверил:

Кандидат физ-мат наук

Бритков в. Б.

Долгопрудный 2013

Оглавление

Введение

1. Теория оптимизации

1.1 Задача оптимизации. Типы оптимизации

1.2 Математический аппарат

1.3 Функция одной переменной

1.4 Функции многих переменных

1.5 Оптимизация линейных функций (линейное программирование)

1.6 Оптимизация нелинейных функций (нелинейное программирование)

2. Задача на ранжирование

Заключение

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

Введение

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

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

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

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

1. Теория оптимизации

1.1 Задача оптимизации. Типы оптимизации

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

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

В жизни часто встречаются ситуации, где нужно сделать наилучший выбор, исходя из доступных ресурсов и имеющихся параметров. Для таких случаев используются возможности оптимизации. Задача оптимизации состоит в поиске оптимального набора параметров при некоторых ограничениях и соотношениях, накладываемых на функцию, зависящую от этих параметров. Стоит указать, что оптимальных набором параметров называется такой набор, при котором функция от этих параметров при данных значениях будет иметь минимум или максимум. Ограничения играют роль задания множества значений, которые могут принимать параметры. Математически все вышесказанное можно описать так. Имеется некоторая функция f(x) при x ϵ X, х = (х₁, ... , х_n); нужно найти набор х⁰ =  при max(f(x)) или min(f(x)) и условиях g_k(x) (=,<,>,≥,≤ ) 0 при . Математический аппарат для решения этой задачи будет рассмотрен далее.

Оптимизацию можно разделить по следующим категориям:

·        По количеству критериев (многокритериальный, один критерий);

·        По виду функциональной зависимости (линейная и нелинейная).

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

1.2 Математический аппарат

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

1.3 Функция одной переменной

Это самый тривиальный случай, заключающийся в исследовании поведения функции на некотором промежутке. Рассмотрим функцию y=f(x) с ограничением x ϵ [a,b]. Функция является непрерывной на данном промежутке.

Пусть перед нами стоит задача отыскания максимума f(x). По определению, точка х⁰ будет точкой минимума (максимума) для f(x), если для любого x такого, что |x - x⁰|<ε следует f(x)≥f(x⁰) (f(x)≤f(x⁰)). Для нахождения максимума рассмотрим производную f '(x) на промежутке [a,b]. Возникают следующие случаи:

·        Производная всюду неотрицательная (f '(x)≥0 на [a,b]). Тогда:

f(x) _{x ϵ [a,b]} = f(b);

·        Производная всюду неположительная (f '(x)≤0 на [a,b]). Тогда:

f(x) _{x ϵ [a,b]} = f(a);

·        Производная меняет знак в точке с ϵ [a,b]. Тогда рассматриваем эту функцию на промежутках [a,c] и [c,b]. Соответственно, у нас получатся точки c₁ ϵ [a,c] и c₂ ϵ [c,b] такие, что:

Max f(x) _{x ϵ [a,с]} = f(c₁) и max f(x) _{x ϵ [c,b]} = f(c₂).

Пусть теперь функция имеет особую точку с ϵ [a,b]. Рассмотрим левый полуинтервал [a,с). Если lim f(x)_x→c = +∞, тогда решения максимизации нет, иначе lim f(x)_x→c = -∞, то решение ищется как написано ранее. Аналогично нужно поступить с правым промежутком.

1.4 Функции многих переменных

Пусть имеется функция f(x) при x ϵ x, х = (х₁, ... , х_n). Рассмотрим все ее первые и вторые производные в точке :

 = 0, ;

||  || , - положительно (отрицательно) определенная матрица.

Тогда в таких точках будет наблюдаться соответственно минимум (максимум).

Соответственно, все точки xⁱ такие, что выполняются условия выше, обращают функцию в локальный минимум.

Теперь пусть добавим определенные ограничения, представимые функциями g_k(x) = 0 при k=1,m. Такие условия называют уравнениями связи.

В данном случае будем говорить об условном экстремуме функции: точка  будет точкой минимума (максимума) для f(x), если для любого x такого, что |x - x⁰|<ε следует f(x)≥f(x⁰) (или f(x)≤f(x⁰)).

Для нахождения решений воспользуемся методом множителей Лагранжа:

.

Данная функция называется функцией Лагранжа. Отыскание точек условного экстремума функции f(x) сводится к поиску обычного локального экстремума функции Лагранжа.

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

1.5 Оптимизация линейных функций (линейное программирование)

Начало линейному программированию заложил в 30-х годах прошлого века советский математик и экономист Л.В. Канторович.

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

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

Линейной функции:

.(1)

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

, (2)

Так и равенствами:

.(2*)

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

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

.(3)

Можно показать, что каноническая задача имеет решения, если определитель матрицы коэффициентов будет ненулевым. При том будет единственное решение, если m = n. Этот факт очевидно следует из теоремы крамера. Если же m < n, то останется n - m независимых переменных, остальные выражаются через них ввиду линейной зависимости. Таким образом, при преобразовании целевой функции f(x), получается новая функция f₁(k), где  - независимые переменные. Притом задача оптимизации сводится к поиску оптимального набора , при котором функция f₁(k⁰) будет максимальной или минимальной без каких-либо ограничений. Таким образом, при m < n, основную каноническую задачу линейного программирования с n переменными можно привести к общей задаче с n - m независимыми переменными и ограничениями (3).

Если же условия g_j(x) являются неравенствами, то можно при помощи введения дополнительных переменных (2) преобразовать в (2*):

Данное преобразование "канонизирует" задачу, однако увеличивается ее размерность.

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

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

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

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

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

Для начала заметим, что уравнение (1) порождает гиперплоскость L(F(x)). Для удобной записи обозначим F(x)=S. Зависимость от S порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку - требуется найти такое наибольшее S, что гиперплоскость L(S) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения целевой функции. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением целевой функции невозможен, считается, что оптимальное значение S найдено.

Последовательность вычислений симплекс-методом можно разделить на два этапа:

1.      нахождение нулевого решения (первая итерация),

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

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

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

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

.        Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче, заключающейся в следующем. Имеется некий однородный груз, который нужно перевести с n складов на m заводов. Для каждого склада i известно, сколько в нём находится груза a_i, а для каждого завода известна его потребность b_j в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния c_ij от i-го склада до j-го завода известны). В этой задаче требуется составить наиболее дешёвый план перевозки.

1.6 Оптимизация нелинейных функций (нелинейное программирование)

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

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

,

являющейся функцией Лагранжа.

Притом:

.

Как было уже указано ранее, нахождение условного экстремума функции F(x) сводится к нахождению безусловного экстремума функции Лагранжа.

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

.

Пусть теперь известно положение х_k , тогда х_k+1, можно определить так:

,  - к-ый шаг итерации.

Важно брать такие значения  такие, чтобы:

, если требуется функцию максимизировать;

, если нужно минимизировать.

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

.        Метод наискорейшего спуска. Заключается в поиске  таких, что выполняется наименьшее число шагов. (рис. 2)

.        Покоординатный метод. Ищется производная F(x) по каждой компоненте (рис. 3).

2. Задача на ранжирование

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

Действительно, рассмотрим множество из n объектов A_i и m параметров Q_j. Для каждого объекта будет определена точка A_i, в m-мерном пространстве (рис. 4). Дело в том, что сами по себе эти точки сравнить невозможно - неизвестно, нельзя сказать, какая точка большая, а какая меньше. Однако можно сравнить их радиус-векторы. А для этого необходимо указать взаимные отношения базисных векторов, что равносильно степени предпочтения одного параметра другому. Ввиду того, что трудно объективно описать подобные предпочтения, введем эмпирическую таблицу, показывающую степень подобных предпочтений:

Таблица 1: шкала относительной важности.

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

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

многокритериальный оптимизация программирование ранжирование

,

притом , то есть матрица является кососимметрической. Далее каждый параметр оценивается:

, где .

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

.

Заключение

Было рассказано про многокритериальную оптимизацию - линейное и нелинейное программирование, ранжирование.

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

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

Все это ни что иное, как полезный инструмент в руках человека, способствующий наилучшему управлению процессами.

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

1.      Н.Н. Моисеев, Ю.П. Иванилов, Е.М. Столярова. Методы оптимизации. 1978 г.

2.      http://ru.wikipedia.org/wiki/%CB%E8%ED%E5%E9%ED%EE%E5_%EF%F0%EE%E3%F0%E0%EC%EC%E8%F0%EE%E2%E0%ED%E8%E5#.D0.A2.D1.80.D0.B0.D0.BD.D1.81.D0.BF.D0.BE.D1.80.D1.82.D0.BD.D0.B0.D1.8F_.D0.B7.D0.B0.D0.B4.D0.B0.D1.87.D0.B0

.        http://ru.wikipedia.org/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)