Методы безусловной и условной оптимизации
Задача 1. Найти
где
Задача 1 сводится к решению системы уравнений:
и исследованию значения второго дифференциала:
в точках решения уравнений (8.3).
Если квадратичная форма (8.4) отрицательно определена в точке, то она достигает в ней максимальное значение, а если положительно определена, то минимальное значение.
Пример:
Система уравнений имеет решения:
Точка (– 1/3,0) является точкой максимума, а точка (1/3,2) –точкой минимума.
Задача 2. Найти
при условиях:
Задача 2 решается методом множителей Лагранжа. Для этого находится решение системы (т + п) уравнений:
Пример. Найти стороны прямоугольника максимальной площади, вписанного в круг: . Площадь А прямоугольника можно записать в виде: А = 4ху, тогда
откуда
Задача 3. Найти:
при условиях:
Эта задача охватывает широкий круг задач, определяемых функциями f и ?.
Если они линейны, то задача является задачей линейного программирования.
Задача 3а.
Найти
при условиях
Она решается симплекс-методом [3,7], который с помощью аппарата линейной алгебры производит целенаправленный перебор вершин многогранника, определяемого (8.13).
Симплекс-метод (состоит из двух этапов):
Этап 1. Нахождение опорного решения х(0).
Опорное решение – одна из точек многогранника (8.13).
Этап 2. Нахождение оптимального решения.
Оптимальное решение находится последовательным перебором вершин многогранника (8.13), при котором значение целевой функции z на каждом шаге не уменьшается, то есть:
Частный случай задачи линейного программирования – так называемая транспортная задача [3].
Транспортная задача. Пусть в пунктах находятся склады, в которых хранятся товары в количестве соответственно. В пунктах находятся потребители, которым необходимо поставить эти товары в количествах соответственно. Обозначим cij стоимость перевозки единицы груза между пунктами
Исследуем операцию перевозки потребителями товаров в количествах, достаточных, чтобы удовлетворить потребности потребителей. Обозначим через количество товара, перевозимого из пункта аi в пункт bj.
Для того, чтобы удовлетворять запросы потребителя, необходимо, чтобы величины хij удовлетворяли условиям:
В то же время со склада а; нельзя вывезти продуктов в большем количестве, чем там имеется. Это означает, что искомые величины должны удовлетворять системе неравенств:
Удовлетворять условиям (8.14), (8.15), то есть составить план перевозок, обеспечивающий запросы потребителей, можно бесчисленным числом способов. Для того, чтобы исследователь операций мог выбрать определенное решение, то есть назначить определенные хij, должно быть сформулировано некоторое правило отбора, определяемое с помощью критерия, который отражает наше субъективное представление о цели.
Проблема критерия решается независимо от исследования операции – критерий должен быть задан оперирующей стороной. В данной задаче одним из возможных критериев будет стоимость перевозки. Она определяется следующим образом:
Тогда задача о перевозках формулируется как задача линейного программирования: определить величины , удовлетворяющие ограничениям (8.14), (8.15) и доставляющие функции (8.16) минимальное значение. Ограничение (8.15) – это условие баланса; условие (8.14) можно назвать целью операции, ибо смысл операции в том и состоит, чтобы обеспечить запросы потребителей.
Эти два условия составляют, по существу, модель операции. Реализация операции будет зависеть от критерия, при помощи которого будет обеспечено достижение цели операции. Критерий может фигурировать в различных ролях. Он может выступать и как способ формализации цели и как принцип выбора действий из числа допустимых, то есть удовлетворяющих ограничениям.
Одним из известных методов решения транспортной задачи является метод потенциалов [3].
На первом этапе решения задачи составляется первоначальный план перевозок, удовлетворяющий
ограничениям (8.14), (8.15). Если (то есть суммарные потребности не совпадают с суммарными запасами продуктов на складах), то вводится в рассмотрение фиктивный пункт потребления или фиктивный склад со стоимостью перевозок, равными нулю. Для новой задачи суммарное количество товаров на складах совпадает с суммарной их потребностью. Затем каким-нибудь методом (например, наименьшего элемента или северо-западного угла) находится первоначальный план. На следующем шаге процедуры полученного плана строится система специальных характеристик – потенциалов. Необходимым и достаточным условием оптимального плана является его потенциальность. Процедура уточнения плана производится до тех пор, пока он не станет потенциальным (оптимальным).
Задача 3б. В общем случае задача (8.10 – 8.11) называется задачей нелинейного программирования. Рассмотрим ее в более принятом виде:
при условиях
Для решения этой задачи используются так называемые релаксационные методы. Процесс построения последовательности точек называется релаксационным, если:
Методы спуска (общая схема) [3]. Все методы спуска решения задачи безусловной оптимизации (8.17) различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Методы спуска состоят в следующей процедуре построения последовательности {xk}.
В качестве начального приближения выбирается произвольная точка x0. Последовательные приближения строятся по следующей схеме:
• точке xk выбирается направление спуска – sk;
• находят (к + 1) – е приближение по формуле:
где в качестве величины выбирают любое число, удовлетворяющее неравенству
где число – любое такое число, когда
В большинстве методов спуска величина ?к выбирается равной единице. Таким образом, для определения ?к приходится решать задачу одномерной минимизации.
Метод градиентного спуска. Поскольку антиградиент – указывает направление наискорейшего убывания функции f(x), то естественным является перемещение из точки хk по этому направлению. Метод спуска, в котором называется методом градиентного спуска. Если , то релаксационный процесс называется методом скорейшего спуска.
Метод сопряженных направлений. В линейной алгебре этот метод известен как метод сопряженных градиентов решения систем линейных алгебраических уравнений АХ=b, а следовательно, как метод минимизации квадратичной функции
Схема метода:
Если = 0, то эта схема превращается в схему метода скорейшего спуска. Соответствующий выбор величины tk гарантирует сходимость метода сопряженных направлений со скоростью того же порядка, что и в методах градиентного спуска и обеспечивает конечность числа итераций в квадратичном спуске [3] (например ).
Покоординатный спуск. На каждой итерации в качестве направления спуска – sk выбирается направление вдоль одной из координатных осей. Метод имеет скорость сходимости процесса минимизации порядка 0(1/m). Причем она существенно зависит от размерности пространства.
Схема метода:
где координатный вектор
Если в точке xk имеется информация о поведении градиента функции f(x), например:
то в качестве направления спуска sk можно взять координатный вектор еj. В этом случае скорость сходимости метода в n раз меньше, чем при градиентном спуске.
На начальном этапе процесса минимизации можно использовать метод циклического покоординатного спуска, когда сначала спуск осуществляется по направлению е1, затем по е2 и т. д. вплоть до еп, после чего весь цикл повторяется снова. Более перспективным по сравнению с предыдущим является покоординатный спуск, в котором направления спуска выбираются случайным образом. При таком подходе к выбору направления существуют априорные оценки, гарантирующие для функции f(x) с вероятностью, стремящейся к единице при , сходимость процесса со скоростью порядка 0(1/m).
Схема метода:
На каждом шаге процесса из n чисел {1, 2, ..., n} случайным образом выбирается номер j(k) и в качестве sk выбирается единичный координатный вектор еj(k), после чего осуществляется спуск:
Метод случайного спуска. На n-мерной единичной сфере с центром в начале координат выбирается случайная точка sk, подчиняющаяся на этой сфере равномерному распределению, и затем по вычисленному на k-м шаге процесса элементу хк определяется :
Скорость сходимости метода случайного спуска в n раз ниже, чем у метода градиентного спуска, но в n раз выше, чем у метода случайного покоординатного спуска. Рассмотренные методы спуска применимы и к необязательно выпуклым функциям и гарантируют их сходимость при очень малых на них ограничениях (типа отсутствия локальных минимумов).
Релаксационные методы математического программирования. Вернемся к задаче 36 ((8.17) – (8.18)):
при условиях
В оптимизационных задачах с ограничениями выбор направления спуска сопряжен с необходимостью постоянной проверки того, что новое значение хk+1 должно также, как и предыдущее xk удовлетворять системе ограничений X.
Метод условного градиента. В этом методе идея выбора направления спуска состоит в следующем: в точке хк линеаризуют функцию f(x), строя линейную функцию и затем, минимизируя f(x) на множестве х, находят точку yk. После этого полагают и далее вдоль этого направления осуществляют спуск , так, чтобы
Таким образом, для отыскания направления – sk следует решить задачу минимизации линейной функции на множестве X. Если X в свою очередь задается линейными ограничениями, то она становится задачей линейного программирования.
Метод возможных направлений. Идея метода: среди всех возможных направлений в точке хк выбирают то, вдоль которого функция f(x) убывает быстрее всего, и затем осуществляют спуск вдоль этого направления.
Направление – s в точке х ? X называется возможным, если существует такое число , что для всех . Для нахождения возможного направления необходимо решить задачу линейного программирования, либо простейшую задачу квадратичного программирования:
При условиях:
Пусть – решение этой задачи. Условие (8.25) гарантирует, что направление – – возможное. Условие (8.26) обеспечивает максимальность величины ( , то есть среди всех возможных направлений – s, направление – обеспечивает самое быстрое убывание функции f(x). Условие (8.27) избавляет от неограниченности решения задачи. Метод возможных направлений устойчив к возможным вычислительным ошибкам. Однако скорость его сходимости оценить в общем случае сложно и эта задача пока остается нерешенной.
Метод случайного поиска. Реализация изложенных выше методов минимизации в общем случае очень трудоемка, кроме простейших случаев, когда множество ограничений обладает простой геометрической структурой (например, является многомерным параллелепипедом). В общем случае весьма перспективным может быть метод случайного поиска, когда направление спуска выбирается случайным образом. При этом мы будем существенно проигрывать в скорости сходимости, однако простота выбора направления может компенсировать эти потери с точки зрения общих затрат труда на решение задачи минимизации.
Схема метода:
На n-мерной единичной сфере с центром в начале координат выбирается случайная точка rk, подчиняющаяся на этой сфере равномерному распределению, и затем направление спуска – sk из условий ,
В качестве начального приближения выбирается . По вычисленной на каждой итерации точке xk строится (k + 1)-я точка xk+1:
В качестве выбирается любое число из = , удовлетворяющее неравенству:
Доказана сходимость этого метода при весьма нежестких ограничениях на функцию f (выпуклость) и множество ограничений X (выпуклость и замкнутость).
8.3. Корреляционный и регрессионный анализ
Для оценки степени связи двух характеристик в корреляционном анализе используется коэффициент корреляции. Оценка коэффициента корреляции по наблюдениям рассчитывается по формуле:
где
Значимость оценки определяется с помощью критерия Стьюдента: если
то оценка значима, и не значима в противном случае.
Величина выбирается из таблицы распределения Стьюдента [6] и отвечает уровню значимости а. (Для ).
Для оценки характера связи в регрессионном анализе используется понятие функции регрессии. Оценка функции регрессии в нормальном случае производится по n наблюдениям по формуле
где
Доверительная область для линии регрессии r(х) определяется как:
где
К? определяется по уровню значимости ? (для ).
В многомерном случае степень связи случайных величин , Y определяется с помощью множественного коэффициента корреляции
Его оценка по n наблюдениям определяется как:
где – оценка функции множественной регрессии Y пo
Оценка множественной регрессии в виде линейной функции находится методом наименьших квадратов:
Значимость оценок коэффициентов определяется из условий:
• имеет распределение Стьюдента
• имеет распределение Стьюдента
• имеет распределение
Оценка коэффициента является значимой, если значение соответствующей статистики превосходит табличное значение, отвечающее заданному уровню значимости.
8.4. Робастные методы и процедуры
Многие «наилучшие» оценки в статистике (например, наиболее распространенная на практике оценка среднего значения случайной величины ) обладают тем дефектом, что они являются наилучшими лишь в случае, если выборка наблюдений получена из нормально распределенной совокупности данных и быстро теряют свои оптимальные свойства по мере отклонения распределения от нормального, то есть являются неустойчивыми к отклонениям от нормального распределения. В качестве характеристики устойчивости оценки можно предложить понятие робастности.
Определение робастности оценки. Пусть случайная величина X имеет плотность распределения вероятностей , где вид функции f известен, а ? – неизвестный параметр (может быть величиной векторной). Оценка параметра производится по n наблюдениям . В классической статистике качество оценки определяется ее дисперсией Df вычисленной в предположении, что выборка получена из генеральной совокупности с плотностью распределения вероятностей
Определим понятие ?-окрестности распределения f:
где – произвольная плотность распределения вероятностей.
Назовем оценку робастной, если для нее имеет место
То есть робастная оценка – это такая оценка, которая в наихудшем случае (когда достигается max ) имеет наименьшую дисперсию. Нахождение робастной оценки отвечает решению, как говорят в математике, минимаксной задачи. Минимаксное значение есть гарантированный верхний порог дисперсии оценки для любого распределения f из ?-окрестности.
Минимаксная стратегия широко распространена в таком разделе теории операций как теория игр. В определенном смысле робастная процедура – это «игра» исследователя с природой.
Робастная оценка среднего значения. Если параметр ? играет роль центра распределения (среднего значения), то . Робастная оценка параметра ? в этом случае находится по п наблюдениям решением следующей задачи:
Если – плотность вероятностей нормального распределения, то:
Робастная оценка в этом случае представляет собой некий гибрид оценки средней арифметической и выборочной медианы . Она совмещает в себе эффективность первой оценки и устойчивость второй. Их соотношение определяется величиной степени засорения е через величину . Если , то оценка близка к среднему арифметическому. Если , то оценка близка к выборочной медиане.
Робастная оценка имеет вид:
где – вариационный ряд выборочных значений; . Значения можно найти в таблице 2 [6].
Таблица 2
Значения уровня урезания ? = ?(?)
Робастная регрессия. Уравнение регрессии, получаемое методом наименьших квадратов, имеет существенный дефект, заключающийся в том, что при наличии грубых ошибок в данных оценки его коэффициентов сильно искажаются, то есть являются неустойчивыми к отклонениям от обычного предположения в регрессионном анализе, что ошибки в модели регрессии имеют нормальное распределение.
Коэффициенты робастной регрессии вычисляются решением задачи:
где ?(t) имеет вид (8.29).
8.5. Выводы по анализу применяемых методов
Мы рассмотрели несколько типичных задач, с которыми сталкивается исследователь операции. С точки зрения математика – это обычные задачи математического программирования и статистики. Каждая из этих задач относится к той или иной главе математики и для ее решения существуют разнообразные, хорошо изученные алгоритмы. Теория математического программирования, то есть теория решения экстремальных задач при наличии ограничений, возникла и развилась, прежде всего, благодаря потребностям исследования операций. Поэтому многие авторы, занимающиеся приложениями математики к решению инженерных или экономических проблем, рассматривают задачи линейного, нелинейного и целочисленного программирования не как разделы математики, используемые в исследовании операций, а как составную часть этой дисциплины [1,5]. Математическое программирование и другие методы решения экстремальных задач составляют основу аппарата исследования операций. Но сама теория исследования операций никак не может быть сведена к решению экстремальных задач. Более того, исследование операций не является чисто математической дисциплиной и главные сложности анализа конкретных операций, как правило, состоят не в преодолении математических трудностей.
Решение реальных задач показывает, что первый шаг это формализация операций, их описание с помощью языка математики. От того, как будет формализована задача, зависит вся судьба исследования. Простое описание делает анализ довольно простым, но если оно не будет в достаточной степени адекватно реальности, то может привести к результатам сомнительной достоверности. Наоборот, переусложненная задача, учитывающая разнообразные детали процесса и с большими подробностями описывающая реальность, может привести к такой затрате машинного времени, которая окажется не оправданной высокой точностью результата. Одним словом, уже при составлении модели исследователь операции, который, как правило, является математиком, должен руководствоваться как своим опытом, так и способностями, умением проникать в содержание задачи и ясностью понимания цели всего исследования. Мы видим, что этот первый этап очень далек от традиционной математики, и, тем не менее, преодолеть его трудности может лишь человек, представляющий себе возможности аппарата, то есть он должен быть не де-юре, а де-факто математиком.
В последнее время делаются попытки разделить обязанности программиста-исследователя и «постановщика» задач. Такое разделение должно делаться с большой осторожностью. Конечно, на определенной стадии разделение обязанностей оказывается необходимым и часть программистской работы может быть поручена специалистам в области машинного программирования. В особенности если это касается вопросов организации системы программ, управляющих программ, работ с массивами и т. д. Но что абсолютно необходимо для успеха исследования – это объединение в лице исследователя операции математика и специалиста, в тонкостях понимающего специфику предмета.
NB
¦ Исследование операций является одним из основных источников системного анализа.
¦ Сам термин «исследование операций» родился в послевоенные годы, когда стало очевидно, что задачи широкого класса, возникшие в самых различных сферах человеческой деятельности, имеют, несмотря на их качественное различие, одно общее – они сводятся к выбору способа действия, варианта плана, параметров конструкций, то есть к принятию решений.
¦ Таким образом, задача исследования операций на этом этапе нами трактуется как некоторая оптимизационная проблема. В действительности задача исследователя операции несколько шире. Анализируя требования к операции, то есть те цели, которых предполагает достигнуть оперирующая сторона, и те неопределенности, которые при этом неизбежно присутствуют. Исследователь должен сформулировать цель операции на языке математики. Язык оптимизации здесь оказывается естественным и удобным, но вовсе не единственно возможным. Но он удобен, поскольку методы оптимизации достаточно развиты, а язык оптимизации обладает достаточно большой степенью общности.
¦ В исследовании операций возникли определенная терминология и принципы анализа. Поскольку под операцией мы будем понимать любое целенаправленное действие, то в качестве «модели операции» мы должны себе представлять некоторую совокупность, состоящую из субъекта (оперирующей стороны), формулирующего цель операции, запаса активных средств (ресурсов) для проведения операции, набора стратегий, т. е. способов использования этих ресурсов, и критерия-способа сравнения различных стратегий, преследующих достижение цели операции. Сам критерий, точнее – стремление к максимизации или минимизации его значений часто и объявляется целью операции.
¦ Многие «наилучшие» оценки в статистике (например, наиболее распространенная на практике оценка среднего значения случайной величины ) обладают тем дефектом, что они являются наилучшими лишь в случае, если выборка наблюдений получена из нормально распределенной совокупности данных и быстро теряют свои оптимальные свойства по мере отклонения распределения от нормального, то есть являются неустойчивыми к отклонениям от нормального распределения. В качестве характеристики устойчивости оценки можно предложить понятие робастности.
¦ Решение реальных задач показывает, что первый шаг это формализация операций, их описание с помощью языка математики. От того, как будет формализована задача, зависит вся судьба исследования. Простое описание делает анализ довольно простым, но если оно не будет в достаточной степени адекватно реальности, то может привести к результатам сомнительной достоверности. Наоборот, переусложненная задача, учитывающая разнообразные детали процесса и с большими подробностями описывающая реальность, может привести к такой затрате машинного времени, которая окажется не оправданной высокой точностью результата.
Литература
1. Вентцель Е.С. Введение в исследование операций. – М.: Советское радио, 1984.
2. Гермейер Ю.Б. Введение в теорию исследования операций. – М.: Наука, 1981.
3. Карманов В.Г. Математическое программирование. – М.: Наука, 1985.
4. Моисеев Н.Н. и др. Методы оптимизации. – М.: Наука, 1978.
5. Моисеев Н.Н. Математические задачи системного анализа, – М.: Наука, 1981.
6. Смоляк С.А., Титаренко Б.П. Робастные методы в статистике. – М.: Финансы и статистика, 1980.
7. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование, – М.: Наука, 1979.
Похожие рефераты:
