Теория оптимизации. Оптимизация в центре теории экономики Перечень методов безусловной оптимизации

Федеральное агентство по образованию ГОУ ВПО «Уральский государственный технический университет - УПИ» ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ РАДИОЭЛЕКТРОННЫХ СХЕМ Методические указания к лабораторной работе по курсу “Компьютерный анализ электронных схем” для студентов всех форм обучения специальности 200700 - Радиотехника Екатеринбург 2005 УДК 681,3,06:621.396.6 Составители В.В. Кийков, В.Ф. Кочкина, К.А. Вдовкин Научный редактор доц., канд. техн. наук В.И. Гадзиковский ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ РАДИОЭЛЕКТРОННЫХ СХЕМ: методические указания к лабораторной работе по курсу «Компьютерный анализ электронных схем” /сост. В.В. Кийко, В.Ф. Кочкина, К.А. Вдовкин. Екатеринбуг: ГОУ ВПО УГТУ-УПИ, 2005. 21с. Методические указания содержат сведения о постановке задач оптимизации, критериях оптимальности, теории поиска минимума целевой функции. Приведен обзор методов параметрической оптимизации, подробно описан метод Хука - Дживса, даны вопросы для самоконтроля. Библиогр.: 7 назв. Рис. 6. Подготовлено кафедрой “Радиоэлектроника информационных систем”.  ГОУ ВПО «Уральский государственный технический университет-УПИ», 2005 2 ОГЛАВЛЕНИЕ ЦЕЛЬ РАБОТЫ........................................................................................................... 4 1.ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ.......................................................... 4 2. ТЕОРИЯ ОПТИМИЗАЦИИ.................................................................................. 4 2.1. Формальная (математическая) постановка задачи оптимизации............. 4 2.2. Постановка задачи параметрической оптимизации РЭС............................ 5 2.3. Критерии оптимальности................................................................................... 7 2.4. Стратегия решения задач оптимального проектирования РЭС................ 9 2.5. Алгоритмы глобального поиска .................................................................. 9 2.5.1. Алгоритм случайного поиска....................................................................... 10 2.5.2. Монотонный алгоритм глобального поиска............................................. 10 2.5.3. Алгоритм сканирования на сетке кода Грея............................................. 10 2.6. Методы и алгоритмы локального поиска..................................................... 11 2.6.1. Прямые методы............................................................................................... 11 2.6.2. Градиентные методы оптимизации первого порядка............................. 13 2.6.3. Градиентные методы оптимизации второго порядка............................. 13 3. ОПИСАНИЕ КОМПЬЮТЕРНОЙ ПРОГРАММЫ АНАЛИЗА.................. 15 3.1. Запуск программы............................................................................................. 15 3.2. Составление задания на оптимизацию.......................................................... 15 3.3. Результаты оптимизации................................................................................. 17 4. СОДЕРЖАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ............................................... 19 4.1. Порядок выполнения........................................................................................ 19 4.2. Задание к лабораторной работе....................................................................... 19 5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ ИСХОДНЫХ ДАННЫХ.................................................................................................................... 20 6. СОДЕРЖАНИЕ ОТЧЕТА................................................................................ 20 7. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ............................................................ 20 СПИСОК ЛИТЕРАТУРЫ........................................................................................... 21 3 ЦЕЛЬ РАБОТЫ Получить представление и практические навыки параметрической оптимизации РЭС при автоматизированном схемотехническом проектировании радиоэлектронной аппаратуры (РЭА). 1.ОБЩИЕ МЕТОДИЧЕСКИЕ УКАЗАНИЯ Данная работа является третей в комплексе лабораторных работ по методам расчета, анализа и оптимизации радиоэлектронных схем. В комплекс входят следующие работы: 1. Расчет радиоэлектронных схем методом узловых потенциалов. 2. Анализ электронных схем модифицированным методом узловых потенциалов. 3. Параметрическая оптимизация радиоэлектронных схем. 4. Анализ радиоэлектронных схем с помощью схемных функций. В первой и второй лабораторных работах выполнены частотный анализ, определены чувствительности коэффициента усиления по напряжению от вариаций внутренних параметров, рассчитаны переходная и импульсная характеристики при номинальных значениях параметров элементов РЭС, которые первоначально выбраны (заданы или рассчитаны) не лучшим образом. В этой работе выполняется параметрическая оптимизация проектируемой РЭС для обеспечения соответствия выходных параметров требованиям технического задания. 2. ТЕОРИЯ ОПТИМИЗАЦИИ 2.1. Формальная (математическая) постановка задачи оптимизации Оптимизацией параметров (параметрической оптимизацией) принято называть задачу расчета оптимальных номинальных значений внутренних параметров объекта проектирования. Задачи оптимизации параметров в САПР радиоэлектронной аппаратуры сводятся к задачи математического программирования extr F(X), XXД, (1) где XД = {XX0| k (X) ≥ 0, r (X) = 0, k  , r  }. Вектор X=(x1, x2, . . . . xn) называется вектором управляемых (варьируемых) параметров; F(X) - целая функция (функция качества); XД - допустимая область; X0 - пространство, в котором определена целевая функция; k(X) и r(X) функции - ограничения. 4 Словесная формулировка задачи (1): найти экстремум целевой функции F(X) в пределах области XД, ограниченной в пространстве X0 N неравенствами k(X) ≥ 0 и М равенствами r (X) = 0. Целевая функция должна быть сформулирована исходя из имеющихся представлений о качестве проектируемого объекта: её значение должно уменьшаться с улучшением качества, тогда в (1) требуется минимизация (extr есть min), или увеличиваться, тогда в (1) требуется максимизация (extr есть max). Ограничения - неравенства, имеющие вид xi > xi min или xi < xi max , называют прямыми ограничениями, где xi min и xi max - заданные константы, остальные ограничения называют функциональными. Задача поиска максимума, как правило, сводится к задаче поиска минимума путем замены F(Х) на -F(Х). Функция F(Х) имеет локальный минимум в точке Х0, если в малой окрестности этой точки F(Х) ≥ F(Х0). И функция F(Х) имеет глобальный минимум в точке Х*, если для всех Х справедливо неравенство F(Х) ≥ F(Х*). Классическая теория оптимизации подробно изложена в соответствующей литературе, например . Ниже основное внимание уделено применению теории оптимизации для поиска оптимальных решений при проектировании радиоэлектронной аппаратуры. 2.2. Постановка задачи параметрической оптимизации РЭС Решение задачи проектирования обычно связана с выбором оптимального, наилучшим образом удовлетворяющего требованиям технического задания варианта устройства из некоторого допустимого множества решений. Эффективное решение задач базируется на формальных поисковых методах оптимизации и неформальных способах принятия оптимальных проектных решений. Поэтому решение задач оптимального проектирования необходимо рассматривать не только в вычислительном аспекте, но скорее в творческом, учитывая опыт и знания инженера-схемотехника на всех этапах автоматизированного проектирования. Одной из наиболее cложных операций при решении задач оптимального проектирования является этап математической формулировки задачи, которая включает в себя выбор критерия оптимальности, определение варьируемых параметров и задание ограничений, накладываемых на варьируемые параметры . Среди задач схемотехнического проектирования, которые целесообразно решать с привлечением методов оптимизации, выделяют следующие задачи параметрического синтеза и оптимизации: - определение параметров компонентов схемы, обеспечивающих экстремальные характеристики при заданных ограничениях; - определение параметров функциональных узлов схем исходя из требований технического задания на характеристики устройства в целом; - адаптация существующих схемных решений с целью подбора параметров, удовлетворяющих новым требованиям к схеме; 5 - уточнение значений параметров компонентов схемы, полученных в результате ручного инженерного расчета. Для схем приемно-усилительной техники оптимизация ведется по отношению к таким выходным параметрам, как: - коэффициент усиления и полоса пропускания: - форма частотной характеристики; - устойчивость усилителя или активного фильтра; - время запаздывания, длительность фронта импульса. Примечание. Класс задач, связанный с определением значений параметров компонентов, при которых проектируемая схема удовлетворяет совокупности условий технического задания на разработку, принято называть параметрическим синтезом (по отношению к определяемым параметрам) или параметрической оптимизацией (по отношению к реализуемым характеристикам). В любой из перечисленных задач реализуемые характеристики проектируемого устройства являются функциями вектора варьируемых (настраиваемых) параметров, составляющих некоторое подмножество полного набора параметров компонентов схемы. Целью параметрического синтеза или оптимизации является определение вектора параметров X, обеспечивающего наилучшее соответствие характеристик устройства Y = Y(X) требованиям технического задания. Для решения этой задачи необходимо, прежде всего, выбрать формальный критерий оценки качества каждого из вариантов проектируемого устройства, который позволил бы различать их между собой и устанавливать между ними отношения предпочтения. Такая оценка может быть представлена функциональной зависимостью вида F(X) =F(Y(X)), называемой обычно критерием оптимальности, функцией качества или целевой функцией. Задача поиска параметров компонентов схемы сводится к классической задаче оптимизации - нахождения экстремума некоторой функции качества F(X) при наличии ограничений (равенств, неравенств или двухсторонних границ), накладываемых на варьируемые параметры и характеристики проектируемой схемы . Разнообразные задачи оптимизации аналоговых радиоэлектронных схем имеют общие черты, основные из которых: - многокритериальность оптимизационных задач; - отсутствие явных аналитических зависимостей выходных параметров от внутренних параметров, связь между внутренними и внешними параметрами выражается системами уравнений и оценивается количественно только через численное решение этих систем. Эти особенности обуславливают трудности постановки и решения задач оптимизации аналоговых радиоэлектронных схем. 6 2.3. Критерии оптимальности В процессе поиска оптимального решения для каждой конкретной задачи может оказаться предпочтительным определенный вид критерия оптимальности. Базовый набор критериев оптимальности, позволяющий удовлетворить разнообразные требования инженера-схемотехника к оптимизируемым характеристикам проектируемых устройств, изложен в . Так, для отыскания экстремума (минимума или максимума) показателя качества, например, как потребляемая схемой мощность, частота среза, используется само значение критерия оптимальности без преобразования: F1(X) = Y(X), (2) В задачах, требующих максимального соответствия оптимизируемой характеристики и некоторой желаемой, например, при оптимизации частотных характеристик, наиболее целесообразно использовать критерий среднего квадратического отклонения F2 ()  (Y() - Y )2 , (3) где Y* - желаемое или требуемое по техническому заданию значение характеристики, () - знак усреднения. Для характеристики, заданной дискретным набором точек, целевая функция 1 F2 (X)  N N  (Y(X , p i 1 i)  Yi)2 , * i (4) где N - число точек дискретизации независимой переменной р; Y(Х, рi) - значение оптимизируемой характеристики в i-ой точке интервала дискретизации; i - весовой коэффициент i-го значения оптимизируемой характеристики, отражающей важность i-ой точки по сравнению с другими (как правило, 0 < i > 1). Минимизация функции (3) и (4) обеспечивает близость характеристик по среднему квадратическому отклонению. Функция (4) используется при численных методах вычисления Y(Х). В некоторых задачах оптимизации необходимо обеспечить превышение или не превышение оптимизируемой характеристикой некоторого заданного уровня. Эти критерии оптимальности реализуются следующими функциями: - для обеспечения превышения заданного уровня F3 (X)  0 при Y (X)  YH* ; (Y  Y (X)) 2 приY (X)  YH* ; 7 (5) - для обеспечения непревышения заданного уровня F4 (X)  0 при Y (X)  YB* (Y (X)  YB*) 2 при Y (X)  YB* , (6) где YH*,YB* - нижняя и верхняя границы допустимой области для характеристики Y(X). Если необходимо, чтобы оптимизируемая характеристика проходила в некоторой допустимой зоне (коридоре), используют комбинацию двух предыдущих критериев оптимальности: 0приYH*  Y (X)  YB* ; F(X)  (Y (X)  YB*) 2 приY (X)  YB* , (YH*  Y (X)) 2 приY (X)  YH* . (7) В тех случаях, когда требуется реализовать лишь форму кривой, игнорируя при этом постоянное смещение по вертикали, используется критерий сдвига N F6 (X)    i (Yi *  Y (X , pi)  Yср) 2 , (8) i 1 где Yср  1 N *  (Yi  Y (X , pi)). N i 1 От вида целевой функции зависят важные характеристики вычислительного процесса и, в первую очередь, сходимость процесса оптимизации. Знаки производных целевой функции по управляемым параметрам не остаются постоянными во всей допустимой области. Для целевых функций вида (4) и (8) последнее обстоятельство ведет к их овражному характеру . Таким образом, особенностью целевых функций при решении задач схемотехнического проектирования является их овражный характер, что приводит к большим вычислительным затратам и требует особого внимания к выбору метода оптимизации. Другой особенностью целевых функций является то, что они обычно многоэкстремальные и наряду с глобальным минимумом имеются локальные минимумы. Особенность задач оптимизации электронных схем заключается и в том, что внутренние параметры не могут принимать произвольных значений. Так, величины резисторов и конденсаторов ограничены некоторыми максимальными и минимальными значениями. Кроме того, из нескольких внешних параметров обычно можно выделить один основной, по которому проводится оптимизация, а для других указать допустимые границы изменения. 8 Оптимизационная задача с ограничениями сводится к задаче оптимизации без ограничений с помощью введения штрафных функций. Целевая функция при этом приобретает вид M N r 1 k 1  (X)  Fi (X)   r ( Т (X)) 2    k ( k (X)) 2 , (9) где r , k - численные коэффициенты, учитывающие важность того или иного ограничения относительно других. Они равны нулю при удовлетворении соответствующему неравенству из (1) и принимают некоторые значения в противном случае; Fi(X) - одна из функций качеств, описанных соотношением (2) - (8). Тем самым выход за пределы допустимой области ХД приводит к увеличению минимизируемой функции цепи и промежуточные решения X j удерживаются «барьером» на границе области ХД. Высота «барьера» определяется значениями  и , которые на практике находятся в широких пределах (1-1010). Чем больше  и , тем меньше вероятность выхода за пределы допустимой области. Одновременно возрастает и крутизна склона оврага на границе, что замедляет или полностью нарушает сходимость процесса минимизации. В связи с невозможностью указать оптимальные значения  и  целесообразно начать оптимизацию с малых значений, увеличивая их затем при получении решения за пределами допустимой области. 2.4. Стратегия решения задач оптимального проектирования РЭС Задачи оптимального проектирования РЭС обладают специфическими особенностями, к которым относят многоэкстремальность и овражность функции качества, наличие ограничений на внутренние и выходные параметры проектируемого устройства, большую размерность вектора варьируемых параметров. Стратегия решения задач оптимального проектирования предусматривает применение глобальных процедур оптимизации на начальных этапах поиска и уточнение полученного глобального решения быстросходящимися в окрестности оптимальной точки локальными алгоритмами. Такая стратегия позволяет, вопервых, с достаточной надежностью и точностью определить значение глобального экстремума и, во-вторых, существенно снизить вычислительные затраты на поиск. При этом этапы глобального поиска могут выполняться с невысокой точностью, а этапы локального уточнения проводятся в области притяжения глобального экстремума, что требует значительно меньшего числа вычислений. 2.5. Алгоритмы глобального поиска Алгоритмы глобального поиска, как правило, дают достаточно грубую оценку глобального экстремума при небольших затратах вычислительных 9 ресурсов и требуют значительного увеличения числа вычислений для получения более точной оценки положения экстремума. 2.5.1. Алгоритм случайного поиска Наиболее простым, с точки зрения реализации вычислительного процесса, является алгоритм поиска глобального экстремума, основанный на зондировании допустимой области ХД последовательностью равномерно распределенных в ней точек с отбором наилучшего варианта из полученных. Качество работы алгоритма во многом определяется свойствами датчика равномерно распределенных случайных чисел, используемых для генерации векторов Х  ХД 2.5.2. Монотонный алгоритм глобального поиска Многомерная оптимизация этим алгоритмом основана на построении развертки (кривой Пеано), отображающей отрезок вещественной оси в гиперкуб допустимой области ХД. С помощью развертки осуществляется однозначное и непрерывное отображение Х(), которое для любой точки 0,1 позволяет получить точку Х  ХД. Тогда задача минимизации F(X) в области ХД эквивалентна поиску минимума * одномерной функции F(X) = F(X()). Для проведения глобальной одномерной минимизации функции F() на интервале 0,1 в подсистеме оптимизации системы схемотехнического проектирования ДИСП используется монотонная модификация алгоритма глобального поиска, реализующая для ускорения сходимости монотонное преобразование F() в виде  ()  { 1  [ 1  F ()] 2 }0 ,5 , (10) которое сохраняет расположение точки глобального экстремума, но делает функцию более гладкой. Алгоритм дает достаточно хорошую оценку глобального экстремума в пределах первых 50-100 итераций. Наилучшие результаты получаются, если число переменных не превышает 5-7. Для рассмотренного алгоритма в ряде случаев лучшие результаты удается получить при использовании преобразования пространства поиска по логарифмическому закону. Такое преобразование особенно эффективно, если границы поиска различаются на несколько порядков, что актуально в задачах оптимизации РЭА, и если экстремум находится вблизи границ области. 2.5.3. Алгоритм сканирования на сетке кода Грея Основная идея метода состоит в последовательном изменении специфической сферы поиска с характерными лучами, содержащими точки испытаний, при накоплении и обработке полученной информации. Направление сканирования осуществляется на особой сетке, задаваемой двоичным кодом 10 Грея. Сфера поиска на сетке кода Грея в рассматриваемом алгоритме отличается от традиционной (круг при числе переменных, равном 2) и имеет дополнительно к кругу характерные лучи. Лучи направлены от центра сферы к границам области ХД и тем самым как бы «просвечивают» всю область до ее границ. Рассматриваемый алгоритм имеет единственный настраиваемый параметр -чувствительность функции качества к вариациям параметров, которая используется для определения шага дискретности по каждой из переменных. 2.6. Методы и алгоритмы локального поиска Методы и алгоритмы локального поиска чаще всего отыскивают ближайший локальный экстремум, а траектория их движения сильно зависит от выбора начальной точки и характера целевой функции. 2.6.1. Прямые методы Методы нулевого порядка (прямые методы) в основе своей не имеют строгого математического обоснования и строятся на основании разумных предложений и эмпирических данных. Простейшим методом нулевого порядка является метод покоординатного спуска (Гаусса-Зейделя). На каждом шаге фиксируются все переменные, кроме одной, по которой определяется минимум целевой функции. Последовательным перебором переменных достигается оптимизация. Этот алгоритм оказывается неэффективным, если целевая функция содержит выражения типа x1x2. Для задач схемотехнического проектирования, в которых не удается получить аналитического выражения целевой функции, характерна ее сложная зависимость от компонентов схемы, и поэтому этот метод обычно неприменим. Из методов нулевого порядка в случае овражных целевых функций хорошие результаты дает метод Розенброка , в котором объединены идеи покоординатного спуска и идеи преобразования координат. Наилучшим направлением поиска экстремума является движение вдоль оврага. Поэтому после первого цикла покоординатного спуска производится поворот осей координат так, чтобы одна из них совпадала с направлением оврага Xk - Xk - n, k = n, 2n, 3n…. Метод Розенброка не дает информации о попадании в точку минимума. Поэтому счет прекращается либо после того, как уменьшение F(X) станет меньше некоторого малого числа , либо после определенного количества циклов. Метод Хука-Дживса был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным . Поиск минимума целевой функции состоит из последовательности шагов исследующего поиска вокруг базисной точки, за которой в случае успеха следует поиск по образцу. Эта процедура состоит из следующих шагов: 1. Выбрать начальную базисную точку b1 и шаг длиной hj для каждой переменной xj, j=1,2,…,n скалярной целевой функции F(X). 11 2. Вычислить F(X) в базисной точке b1 с целью получения сведений о локальном поведении функции F(X). Эти сведения будут использоваться для нахождения направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции F(X). Значение функции F(X) в базисной точке b1 находиться следующим образом: a) вычисляется значение функции F(b1) в базисной точке b1; б) каждая переменная по очереди изменяется изменением шага. Таким образом, вычисляется значение F(b1 + he1), где e1- единичный вектор в направлении оси x1. Если это приводит к уменьшению значений функции, то b1 заменяется на b1 + he1. В противном случае вычисляется значение функции F(b1 - he1), и если ее значение уменьшилось, то b1 заменяется на b1 - he1. Если не один из проделанных шагов не приводит к уменьшению значений функции, то точка b1 остается неизменной и рассматривают изменения в направлении оси x2, т. е. находится значение функции F(b1 + h2e2) и т. д. Когда будут рассмотрены все n переменные, определяется новая базисная точка b2; в) если b2 = b1 , т. е. уменьшение функции F(X) не было достигнуто, то исследование продолжается вокруг той же базисной точке b1 , но с уменьшенной длиной шага. Как правило, на практике шаг уменьшают в 10 раз от начальной длины; г) если b2  b1 , то производится поиск по образцу. 3. При поиске используется информация, полученная в процессе исследования, и минимизация целевой функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом: а) движение осуществляется из базисной точке b2 в направлении b2 - b1 , поскольку поиск в этом направлении уже привел к уменьшению значения функции F(X). Поэтому вычисляется значения функции в точке образца P1 = b2 + (b2 - b1). В общем случае Pi = 2bi+1 - bi; б) выполняется исследование вокруг точки P1(Pi); в) если наименьшее значение на шаге 3,б меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3(bi+2), после чего повторяется шаг 3,а. В противном случае не производится поиск по образцу из точки b2 (bi+1). 4. Завершается процесс поиска минимума, когда длина шага (длины шагов) будет уменьшена до заданного малого значения. 12 2.6.2. Градиентные методы оптимизации первого порядка Методы отыскания экстремума, использующие производные, имеют строгое математическое обоснование . Известно, что при отыскании экстремума не существует лучшего направления, чем движение по градиенту . Из градиентных методов одним из наиболее эффективных является метод Флетчера-Пауэлла (сопряженных градиентов), являющихся разновидность метода наискорейшего спуска. Метод наискорейшего спуска состоит из следующих этапов: 1) задается начальная точка (вектор Xk k=0); 2) вычисляются F(Xk) и F(Xk); 3) производится изменение X в направлении Sk = -F(Xk) до тех пор, пока F(X) перестанет убывать; 4) полагается k = k+1, вычисляется новое значение F(Xk) и процесс повторяется с 3-го этапа. Недостаток метода заключается в том, что при овражных функциях приближение к минимуму имеет зигзагообразный характер и требует большое число итераций. Суть метода Флетчера-Пауэлла состоит в том, что при всех итерациях, начиная со второй (на первой итерации этот метод совпадает с методом наискорейшего спуска), используются предыдущие значения F(X) и F(X) для определения нового вектора направления   S k  F X k  d k S k 1 , где (11) [F (X k)]T  F (X k) d . [F (X k 1)]T  F (X k 1) Тем самым исключается зигзагообразный характер спуска и ускоряется сходимость. Этот алгоритм прост для программирования, и при этом требуется умеренный объем машинной памяти (необходимо заполнить только предыдущее направление поиска и предыдущий градиент). 2.6.3. Градиентные методы оптимизации второго порядка Итерационный метод, основанный на знании вторых производных, в общем случае известен как метод Ньютона. Пусть функция F(X) разложена в ряд Тейлора и в нем удержано три члена. Результат запишем в следующем виде: 1 F (X k  X)  F (X k)  (X)T F k  (X)T G k X 2 (12) Требуется максимизировать разность, стоящую в левой части. Это можно сделать дифференцированием (12) по Х и приравниванием результата к нулю: 13  [ F (X k  X)  F (X k)]  F k  G k X  0, X G k X  F k . Это уравнение можно решить, например, методом LU-разложения, относительно Х. Формально можно записать X  (G k) 1 F k   H k F k где Н=G-1. Направление поиска полагаем теперь совпадающим с вектором S k  X k   H k F k . (13) При переходе к минимуму матрица Гессе1 будет положительно определенной и можно использовать полный размер шага dk=1 (т.е. не нужен поиск в направлении Sk). Однако вдали от минимума матрица Гессе может и не быть положительно определенной. Более того, вычисление этой матрицы требует больших затрат. Поэтому разработан целый класс других методов, называемых методами с переменной метрикой или квазиньютоновскими, которые лишены этих недостатков . Эти методы были разработаны довольно давно, но обобщены только в последнее время. Они базируются на оценке градиентов и на аппроксимации матрицы Гессе или обратной к ней. Аппроксимация достигается изменением исходной положительно определенной матрицы специальным образом так, чтобы сохранить положительную определенность. Только при достижении минимума полученная матрица аппроксимирует матрицу Гессе (или обратную к ней). Во всех методах этого класса направление поиска определяется, как и в методе Ньютона (13). На каждой итерации по матрице Hk согласно специальной формуле получают матрицу Hk+1. В качестве примера приведем формулу, полученную Дэвидоном, Флетчером и Пауэллом , и ее иногда называют ДФП-формулой:  2F 2F 2F  . . .   x1x n   x1x1 x1x 2  2F 2F 2F  . . .   1 Матрица Гессе - матрица вторых производных G (x)   x 2 x1 x 2 x 2 x 2 x n   .  . .    2F 2F 2F   x x x x . . . x x  n 2 n n   n 1 14 H k 1 X (X)T H k  T H k H   T k (X)T   H  k (14) Эта формула пригодна только в случае, если (X)Т   0,  ТHk  0. Здесь k=Fk+1-Fk. 3. ОПИСАНИЕ КОМПЬЮТЕРНОЙ ПРОГРАММЫ АНАЛИЗА Программа имеет удобный графический пользовательский интерфейс для работы в среде операционной системы Windows. Исходным описанием оптимизируемой электронной схемы является информация в файле, созданном при выполнении второй лабораторной работы. Загрузив этот файл и выбрав элементы для оптимизации, с помощью этой программы выполняется расчет новых значений элементов. Критерием правильности расчетов является значение минимума целевой функции, которая рассчитывается как взвешенное среднеквадратическое отклонение требуемой и реальной характеристики РЭС: амплитудно-частотной, переходной или импульсной характеристик. Программа имеет стандартный набор элементов управления - меню, панель инструментов … . Автоматически создается отчет о проведенной лабораторной работе в html - формате. Примечание. После всех заполнений диалоговых окон значениями, нажимается кнопка <Далее>. Если отображаемый в последующем окне результат не устраивает, то нажатием кнопки <Назад> можно вернуться к предыдущим шагам и изменить условия поиска. 3.1. Запуск программы При запуске программы открывается окно, в котором в строке меню Файл необходимо открыть файл, сохраненный после выполнения второй лабораторной работы (рис. 1). 3.2. Составление задания на оптимизацию В файле с описанием схемы содержатся параметры элементов, включая схему замещения транзистора. В левом окне необходимо выбрать варьируемые параметры для параметрической оптимизации. Требуемая характеристика, например АЧХ, задается значениями частоты (в Гц) и соответствующими значениями коэффициента усиления (в Дб). На следующем этапе задается начальный шаг измерения параметров при оптимизации (рис. 2). 15 Рис. 1. Окно открытия входного файла Рис. 2. Окно выбора значений оптимизации 16 3.3. Результаты оптимизации На следующем этапе программа представляет результаты расчетов:  минимум целевой функции;  параметры варьируемых элементов до и после оптимизации;  количество вычислений целевой функции;  количество уменьшений длины шага и поисков по образцу. Критерием правильности полученных результатов является значение минимума целевой функции. Для биполярного транзистора оно должно быть примерно 10-7 I10-8, а для полевого транзистора - 10-4 I 10-5 (рис. 3). Если результаты оптимизации устраивают, то переходим к следующему этапу - построению амплитудно-частотной или временных характеристик (рис. 4, 6,). Для точного определения (нахождения) полосы пропускания РЭС, т.е. верхней и нижней граничных частот, а так же для определения времени переходных процессов имеются таблицы расчетов (рис. 5). Рис. 3. Окно расчетов после оптимизации 17 Рис. 4. Окно построения АЧХ Рис. 5. Значения АЧХ в таблице 18 Рис. 6. Окно временных характеристик 4. СОДЕРЖАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ 4.1. Порядок выполнения 1. Подготовленный этап включает ознакомление с методическими указаниями к лабораторной работе, изучение теории оптимизации по конспекту лекций, литературным источникам и разделу 2 данных методических указаний. 2. Второй этап включает в себя выполнение теоретической работы: - формирование требований к оптимизируемой характеристике РЭС; - выбор элемента или элементов схемы, по параметрам которых предполагается осуществлять оптимизацию. 3. Загрузка программы-оптимизации с описанием оптимизируемой схемы и заданием на параметрическую оптимизацию. 4. Выполнение оптимизации. 5. Расчет характеристики схемы с оптимизированными параметрами. 6. Заключительный этап. На этом этапе сравниваются характеристики РЭС до и после оптимизации. По полученным материалам составляется отчет на листах формата А4 (297х210) с обязательным приложением распечаток результатов. 4.2. Задание к лабораторной работе 1. По результатам анализа АЧХ усилителя, полученной во второй лабораторной работе, сформировать требования к идеальной АЧХ. Выбрать способ задания идеальной АЧХ и координаты точек на графике АЧХ. 19 2. Определить группу элементов, по параметрам которых предполагается осуществить оптимизацию. 5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ ИСХОДНЫХ ДАННЫХ 5.1. По графику АЧХ, рассчитанной при выполнении второй лабораторной работы, определяются верхняя и нижняя граничные частоты и выясняется влияние высокочастотной индуктивной коррекции. 5.2. Пользуясь знаниями схемотехники усилительных устройств, определяются компоненты, параметры которых определяют верхнюю и нижнюю граничные частоты. 5.3. На графике АЧХ строится идеальная (требуемая по техническому заданию) характеристика. Выбираются точки оптимизации. Для того чтобы сохранить вид АЧХ в полосе пропускания, необходимо также выбрать точки и в этой части характеристики. 6. СОДЕРЖАНИЕ ОТЧЕТА 1. Цель работы. 2. Исходные данные в виде принципиальной электрической схемы усилительного каскада и параметров его элементов до оптимизации. 3. Листинг результатов машинного анализа. 4. Анализ результатов. Выводы. 7. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. Назовите необходимое и достаточное условие существования минимума функции. 2. Какая матрица называется положительно определенной? 3. Почему целевую функцию называют функцией качества? 4. Назовите основное свойство целевой функции. 5. Какие задачи называют параметрическим синтезом, а какие - параметрической оптимизацией? 6. В каких случаях задача численного поиска минимума целевой функции относятся к задачам нелинейного программирования? 7. В чем отличие градиентных методов поиска экстремума функции от прямых методов? 8. Поясните понятие глобальный и локальный минимум. 9. Чем обусловлены ограничения при параметрической оптимизации радиоэлектронных устройств? 10. Поясните метод покоординатного спуска. 11. Чем отличается метод сопряженных градиентов от метода наискорейшего спуска? 12. Что означает в методе Хука - Дживса «поиск по образцу»? 13. Каковы критерии окончания итерационного процесса оптимизации? 20 СПИСОК ЛИТЕРАТУРЫ 1. Системы автоматизированного проектирования в радиоэлектронике: Справочник/Е.В. Авдеев, А.Т. Еремин, И.П. Норенков, М.И. Песков; Под ред. И.П.Норенкова. М.: Радио и связь, 1986. 368с. 2. Банди Б. Метода оптимизации. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. 128с. 3. Влах И., Сингхал К. Машинные методы анализа и проектирования электронных схем. М.: Радио и связь. 1988. 560с. 4. Сборник задач по микросхемотехнике: Автоматизированное проектирование: Учебное пособие для вузов /В.И. Анисимов, П.П. Азбелев, А.Б. Исаков и др.; Под ред. В.И. Анисимова. Л.:Энергоатомиздат, Ленинградское отд-ие, 1991. 224с. 5. Диалоговые системы схемотехнического проектирования/ В.Н. Анисимов, Г.Д. Дмитриевич, К.Б. Скобельцын и др.; Под ред. В.Н. Анисимова. М.: Радио и связь, 1988. 288с. 6. Разевич В.Д., Раков В.К., Капустян В.И. Машинный анализи оптимизация электронных схем: Учебное пособие по курсам «Усилительные устройства» и «Радиоприемные устройства». М.:МЭИ, 1981. 88с. 7. Учебник по матанализу/ Табуева В.А. Математика, математический анализ: Учебное пособие. Екатеринбург: УГТУ-УПИ, 2001. 494с. 8. Кийко В.В. Кочкина В.Ф. Вдовкин К.А. Анализ электронных схем модифицированным методом узловых потенциалов. Екатеринбург: УГТУУПИ, 2004. 31с. 21

Отказ от доминирующего пока определения

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

В пользу краткого

ЭТ – наука об оптимизации экономики (хозяйствования) на всех уровнях вплоть до глобального.

Связан с возможностями понятия оптимизация

ОПТИМИЗАЦИЯ (одна из формулировок) - определение значений экономических показателей, при которых достигается оптимум, то есть наилучшее состояние системы. Чаще всего оптимуму соответствует достижение наивысшего результата при данных затратах ресурсов или достижение заданного результата при минимальных ресурсных затратах. http://slovari.yandex.ru/dict/economic

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

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

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

Экономическая теория как наука об оптимизации экономики требует

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

Цели экономического образования:
формирование основ экономического оптимизационного мышления;
выработка функциональной экономической грамотности и способностей к оптимизации саморазвития;
формирование практических навыков принятия оптимальных решений в различных экономических ситуациях;

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

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

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

Вместе с тем такая ЭТ допускает на всех уровнях и оптимальность коллективной выгоды, преимущественной выгоды большинства (тем более всех) участников любого уровня экономической жизни: семейного (где 2 и более членов семьи) , местного, регионального, государственного, межгосударственного, глобального…

Многообразная выгода (частная и общая) – как критерий оптимальности – характерна и живой природе (http://ddarwin.narod.ru/) , она включает и выгоды от самого выживания любой системы.

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

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

Различными аспектами оптимизации хозяйствования социальные группы занимались с первобытных времен. Процессы оптимизации усилились в последние тысячелетия при формировании государств, возникновении крупных полиэтносов в Китае и Индии, Египте и Шумере, на просторах Скифии и в других регионах. Без различных форм оптимизации (того или иного согласования интересов, нередко и насильственного) экономическая жизнь невозможна.

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

Потребности и экономические блага, полезность.
Экономические ресурсы, их виды, ограниченность ресурсов (и их оптимальное использование).
Экономический выбор. Альтернативные издержки. Принцип возрастания экономических издержек. Кривая производственных возможностей.
Понятие эффективности. Критерий эффективности и оптимальности по Парето. Эффективность использования ресурсов и эффективность распределения.
Позитивная и нормативная теория. Экономическая политика. Экономические системы.
Рыночная система. Рынок. Конкуренция.
Спрос и цена. Функция и кривая спроса. Факторы спроса. Закон спроса. Выигрыш потребителя. Индивидуальный и рыночный спрос.
Предложение и цена. Функция и кривая предложения. Факторы предложения. Закон предложения. Выигрыш производителя.
Рыночное равновесие спроса и предложения. Равновесная цена. Дефицит и излишки.
Влияние потоварных налогов и дотаций, распределение налогового бремени.
Эластичность спроса по цене и ее свойства. Дуговая эластичность.
Перекрестная эластичность. Эластичность спроса по доходу. Эластичность предложения по цене.
Предпосылки анализа выбора потребителя. Полезность. Предельная полезность.
Равновесие потребителя в кардиналистской теории.
Предпочтения потребителей. Кривые безразличия.
Бюджетное ограничение. Положение равновесия потребителя.
Изменение дохода потребителя и цен благ. Эффект замещения. Эффект дохода.
Блага низшего порядка. Взаимозаменяемость и взаимодополняемость благ.
Производство. Факторы производства. Доходы факторов.
Понятие производственной функции.
Совокупный, средний и предельный продукт.
Закон убывающей предельной производительности
Изокванта и ее свойства. Изокоста. Равновесие производителя
Фирма: понятие, типы.
Издержки фирмы. Постоянные и переменные издержки.
Общие издержки. Средние издержки.
Предельные издержки.
Бухгалтерская и экономическая прибыль
Общий, средний и предельный доход фирмы.
Различные типы рыночных структур.
Совершенная конкуренция
Равновесие конкурентной фирмы в краткосрочном периоде
Равновесие конкурентной фирмы в долгосрочном периоде
Чистая монополия. Определение цены и объема производства в условиях монополии. Показатели рыночной власти. Экономические последствия монополии.
Монополистическая конкуренция. Установление цены и объема производства в условиях монополистической конкуренции. Неценовая конкуренция. Диверсификация продукта.
Олигополоия. Определение цены и объема производства в условиях олигополии.
Рынки факторов производства: труда, капитала, земли. Формирование спроса на факторы производства, его производный характер.
Рынок труда. Спрос и предложение на рынке труда.
Монопсония и двусторонняя монополия на рынке труда. Роль профсоюзов. Эффективная заработная плата. Теория человеческого капитала. Инвестирования в образование.
Рынок капитала. Физический и денежный капитал. Капитал и ссудный процент. Спрос и предложение заемных средств.
Процентная ставка в условиях совершенной конкуренции. Реальная и номинальная процентная ставка. Равновесная ставка процента.
Инвестиционные решения фирм. Принцип дисконтирования. Оценка эффективности инвестиций.
Частичное и общее равновесие. Общее равновесие и эффективность распределения.
Критерии эффективности в рыночной экономике.
Критерий эффективности и оптимум по Парето (и здесь).
Эффективность и социальная справедливость, социальный и экономический оптимум. Принцип компенсации (принцип Калдора-Хикса).
«Провалы рынка». Система социального обеспечения.
Неравенство, бедность и дискриминация. Распределения дохода. Кривая Лоренца. Коэффициент Джини.
Общественные товары. Спрос и предложение общественных благ. Сравнительный анализ общественных и частных товаров.
Частные и социальные издержки. Частная (внутренняя) и социальная (внешняя) выгода. Проблема рынка общественных товаров и регулирующая роль государства.
Предложение общественных благ через политические институты. Общественный выбор в условиях прямой и представительной демократии. Решения, принимаемые при согласовании. Правила большинства. Лоббизм. Искатели политической ренты.
Внешние эффекты: положительные и отрицательные внешние эффекты.
Проблема интернализации внешних эффектов. Политика государства: корректирующие налоги и субсидии.
Теория прав собственности. Теорема Коуза. Трансакционные издержки. Рынок прав собственности.

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

Современная ЭТ должна просто обосновать эти усилия специалистов.

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

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

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

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

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

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

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

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

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

1) наличие системы взаимозависимых факторов;

2) строго определенный критерий оценки оптимальности;

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

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

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

Найти max (min) f(x) при условии, что переменная х (точка х) пробегает некоторое заданное множество Х:

f(x) ® max (min), х I Х (4.1)

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

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

Очень многое зависит от того, в каком виде задается допустимое множество Х. Во многих случаях это делается с помощью системы неравенств (равенств):

q1 (х1, х2, … , хn) {? , = , ?} 0,

q2 (х1, х2, … , хn) {? , = , ?} 0, (4.2)

……………………………..

qm (х1, х2, … , хn) {? , = , ?} 0,

где q1, q2, … ,qm – некоторые функции, (х1, х2, … , хn) = х – способ, которым точка х задается набором из нескольких чисел (координат), являясь точкой n-мерного арифметического пространства Rn. Соответственно множество Х есть подмножество в Rn и составляет множество точек (х1, х2, … , хn) I Rn и удовлетворяющих системе неравенств (2.2.2).

Функция f(х) становится функцией n переменных f(х1, х2, … , хn), оптимум (max или min), который требуется найти.

Понятно, что следует найти не только само значение max (min) (х1, х2, … , хn), но и точку или точки, если их больше одной, в которых это значение достигается. Такие точки называются оптимальными решениями. Множество всех оптимальных решений называют оптимальным множеством.

Задача, описанная выше, есть общая задача оптимального (математического) программирования, в основе построения которой лежат принципы оптимальности и системности. Функция f называется целевой функцией, неравенства (равенства) qi (х1, х2, … , хn) {? , = , ?} 0, i = 1, 2, … , m – ограничениями. В большинстве случаев в число ограничений входят условия неотрицательности переменных:

х1 ? 0, х2 ? 0, … , хn ? 0,

или части переменных. Впрочем, это может быть и необязательным.

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

1. линейное программирование – функции линейны;

2. нелинейного программирования – хотя бы одна из этих функций нелинейна;

3. квадратичного программирования – f(х) является квадратичной функцией, ограничения линейны;

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

5. целочисленное (линейное или нелинейное) программирование – координаты искомой точки х являются только целыми числами;

6. выпуклое программирование – целевая функция – выпуклая, функции – ограничения – выпуклые, то есть рассматриваются выпуклые функции на выпуклых множествах и т. п.

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

а1х1 + а2х2 + … аnхn + b ,

то есть имеет место задача линейного программирования. Подсчитано, что в настоящее время примерно 80-85% всех решаемых на практике задач оптимизации относятся к задачам линейного программирования.

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

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

В 30-е гг., в период интенсивного эко­номического и индустриального разви­тия Советского Союза, Канторович был в авангар­де математических исследований и стре­мился применить свои теоретические разработки в практике растущей совет­ской экономики. Такая возможность представилась в 1938 г., когда он был на­значен консультантом в лабораторию фанерной фабрики. Перед ним была по­ставлена задача разработать такой ме­тод распределения ресурсов, который; мог бы максимизировать производительность оборудования, и Канторович, сформули­ровав проблему с помощью математиче­ских терминов, произвел максимизацию линейной функции, подверженной боль­шому количеству ограничителей. Не имея чистого экономического образо­вания, он тем не менее знал, что максими­зация при многочисленных ограниче­ниях-это одна из основных экономиче­ских проблем и что метод, облегчающий планирование на фанерных фабриках, может быть использован во многих дру­гих производствах, будь то определение оптимального использования посевных площадей или наиболее эффективное распределение потоков транспорта.

Говоря о развитии этого метода на Западе, следует сказать о Тьяллинге Купмансе, американском экономисте-математике голландского происхождения.

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

Купманс разработал аналитическую методи­ку, названную анализом деятельности, которая решительно изменила подход экономистов и руководителей к распре­делению маршрутов. Впервые он описал эту методику в 1942 г., назвав ее «Соот­ношение между грузами на различных маршрутах» ("Exchange Ratios Between Cargoes on Various Routes"), где показал возможность подхода к проблеме рас­пределения как к математической про­блеме максимизации в пределах ограни­чений. Величина, подлежащая макси­мальному увеличению, - это стоимость доставленного груза, равная сумме стои­мостей грузов, доставленных в каждый из портов. Ограничения были представ­лены уравнениями, выражающими отно­шение количества расходуемых факто­ров производства (например, судов, вре­мени, труда) к количеству груза, достав­ленному в различные места назначения, где величина любой из затрат не должна превышать имеющуюся в распоряжении сумму.

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

В 1975 году Л.В. Канторовичу и Тьяллингу Ч. Купмансу была присуждена Нобелевская премия «за вклад в теорию оптимального распределения ресурсов».

Говоря о первых исследованиях в области линейного программирования, нельзя также не упомянуть еще об одном американском ученом – Джордже Д. Данциге. Конкретная формулировка метода линейного программирования восходит к его работе, выполненной им по заказу ВВС США во время Второй Мировой войны, когда возникла проблема координации действий одной большой организации в таких вопросах, как накопление запасов, производство и содержание оборудования и материально-технического снаряжения, причем имелись альтернативы и ограничения. Кроме того, в свое время Дж. Данцинг работал совместно с В.В. Леонтьевым, и симплекс-метод решения линейных оптимизационных задач (наиболее часто применяемый для их решения) появился в связи с одним из первых практических применений метода межотраслевого баланса.

ВВЕДЕНИЕ

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

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 – наилучшее) - совокупность наиболее благоприятствующих условий; наилучший вариант решения задачи или путь достижения цели при данных условиях и ресурсах. Экономический оптимум в широком смысле – наиболее эффективное функционирование производства, в узком – наилучшее использование материальных ресурсов, при котором достигается возможный максимальный эффект производства или возможный минимум затрат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Количество ресурсов в начале k-го года будем характеризовать величиной P n 1 (параметр состояния). Управление на k-том шаге состоит в выборе переменных u k 1 , u k 2 , …, u ks , обозначающих ресурсы, выделяемые в k-том году i-му предприятию.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· смешанные.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· таблицей;

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

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

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

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

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

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

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

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

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

1. Задачи математического программирования

где - скалярная функция на конечномерном множестве:

• - задачи линейного программирования (ЛП): - линейная, допустимое множество Х - выпукло, задается линейными уравнениями и неравенствами. (Ядро ЛП - сиплекс-метод; теория двойственности, функция Лагранжа, существование седловой точки)
• - задачи целочисленного ЛП (оптимальные решения Z);
• - задачи квадратичного программирования;
• - задачи дискретного программирования (допустимое множество - конечно);
• - задачи выпуклого программирования (Х - выпукло, - выпуклая; теорема Куна-Таккера - аналог теории двойственности в ЛП);
• - задачи невыпуклого программирования.
• 2. Задачи многокритериальной оптимизации (критерий оптимальности состоит из нескольких скалярных функций, которые нужно максимизировать или минимизировать).
• 3. Задачи вариационного исчисления.

Задача ВИ: найти, Х - произвольное множество, например, - функционал, аргументом которого чаще всего являются функции (т.е. - подмножество функционального пространства). Для ВИ характерно то, что множество Х - чаще всего является пространством непрерывно дифференцируемых функций.

4. Задачи оптимального управления.

Классический пример задачи ОУ - задача о полете ракеты.

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

Для задачи ОУ характерны разные типы переменных: фазовые (положение в пространстве) и параметры управления (- множество допустимых управлений, которое обычно является множеством кусочно-непрерывных функций).

Кроме того, обычно, .

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

Постановка классической задачи оптимизации

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

Х - множество допустимых решений, среди элементов которого осуществляется поиск; - n-мерное евклидово пространство.

Определение 1. Точка называется точкой локального минимума [максимума] функции на множестве Х, если существует окрестность точки такая, что справедливо.

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

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

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

Замечания.

• 1) Задача сводится к задаче поиска минимума следующим образом: .
• 2) Если, то задача (1) называется задача безусловной оптимизации. Если Х задается условиями (ограничениями), накладываемыми на x, то задача (1) называется задачей условной оптимизации.
• 3) Обозначим - множество точек глобального минимума функции на множестве Х.

Тогда решить задачу (1) означает:

Найти множество и значение целевой функции в точках этого множества;

• - если, то найти;
• - убедиться, что функция не ограничена снизу на Х;
• - убедиться в том, что.

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

Определение 2. Матрицей Гессе дважды непрерывно дифференцируемой в точке x функции называется матрица частных производных второго порядка, вычисленных в данной точке:

Матрица Гессе является симметрической матрицей размера.

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

Вектор антиградиента - вектор, равный по модулю вектору градиента, но противоположный по направлению.

Вектор антиградиента указывает направление наибольшего убывания функции в данной точке.

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

Евклидова норма вектора

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

Выражение называется квадратичной формой от переменных.

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

Определение 3. Квадратичная форма (а также соответствующая матрица Гессе) называется:

положительно определенной (>0), если для любого ненулевого выполняется неравенство;

отрицательно определенной (), если для любого ненулевого выполняется неравенство;

положительно полуопределенной (), если для любого выполняется неравенство 0 и имеется отличный от нуля вектор, для которого =0;

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

неопределенной (), если существуют такие векторы, что выполняются неравенства, ;

тождественно равной нулю (), если для любого выполняется.

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

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

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

Пример:

положительно определена при любом Х, поэтому точка (2, 4, 6) является точкой локального минимума, а так как это единственная стационарная точка, то она же является и точкой глобального минимума.

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