Теоретические и практические вопросы оптимизации. Оптимизация в центре теории экономики. Классификация математических методов оптимизации

УДК 711.4 МАЗАЕВ А. Г

Методы и критерии оптимизации в современной теории расселения

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

Ключевые слова: оптимизация в градостроительстве, теория оптимизации, критерии и методы оптимизации, критерий Парето.

METHODS AND CRITERIA OPTIMIZATION IN THE MODERN THEORY OF SETTLEMENT

In clause the concept of town-planning optimization is considered. The origin of the term optimization, its communication with the basic concepts in the field of methodology of a science, economy is shown. Opportunities of development of concept of optimization in modern town-planning are considered. The set of criteria of optimization which is possible in modern town-planning activity is offered.

Keywords: optimization in town-planning, theory of optimization, oriteria and methods of optimization, сriterion Pareto.

Мазаев Антон

Григорьевич

кандидат архитектуры, советник РААСН, зав. лабораторией Филиала ФГБУ «ЦНИИП Минстроя России» УралНИИпроект

e-mail: [email protected]

Цель данной статьи состоит в том, чтобы представить теоретическое рассмотрение понятия «оптимизация» применительно к градостроительным объектам - городам и системам расселения. Оптимизация расселения крупного региона России на примере Уральского федерального округа является темой проводимого автором научного исследования. Актуальность этой темы связана с назревшим вопросом упорядочения развития региональных систем расселения Национальной системы России, развитие которой приняло неуправляемый и неравновесный характер. Методология разработки темы строится на формируемой в настоящее время теории геополитического развития расселения.

Понятие оптимизации в современной науке

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

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

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

Понятие оптимизации в экономической теории

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

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

Наиболее емкое и глубокое определение оптимизации дал в свое время В. Парето: «...Любое изменение, которое никому не причиняет убытков и которое приносит некоторым людям пользу (по их собственной оценке), является улучшением» . Этот критерий имеет весьма широкий смысл: он применяется при решении таких задач, когда оптимизация означает улучшение одних показателей при условии, чтобы другие не ухудшались, а также таких, когда реализуется композиционный подход к построению плана развития экономической системы, учитывающий интересы составляющих ее подсистем (групп экономических объектов). Приведенное выше определение можно формализовать следующим утверждением: состояние экономики S* считается лучшим, по В. Парето, чем другое состояние Б1, если хотя бы один экономический субъект предпочитает S*, а все остальные, по меньшей мере, не делают различий между этими состояниями, но в то же время нет таких, кто предпочитает 81; согласно В. Парето, состояние 8* безразлично состоянию Б1, если все экономические субъекты не делают между ними различий; наконец, оно оптимально, если не существует такого допустимого состояния экономики, которое было бы лучше, чем это. Критерий оптимальности В. Парето имеет большое методологическое значение, так как дает понимание, какое изменение в экономической системе можно назвать позитивным, т. е. направленным на общее ее улучшение, а какое нет. Рост экономического благосостояния одних субъектов за счет других не может быть признан позитивным по данному критерию. На Иллюстрации 1 показано действие критерия В. Парето в виде графика, показана область «приемлемых значений», которые обеспечивают улучшение хотя бы одного показателя, не приводя к ухудшению остальных.

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

Иллюстрация 1. Оптимальность по В. Парето

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

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

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

Реализация концепции ГСНМ была предпринята в рамках Генеральной схемы расселения СССР, разработанной в 1970-е гг. Создание ГСНМ предполагалось для оптимизации набравшего к тому времени процесса агломерирования больших и средних городов. Вместо произвольного «слипания» населенных пунктов должна была быть создана их иерархическая организация. Другим следствием оптимизации в градостроительстве

Иллюстрация 2. Основные методы решения задач оптимизации. Систематическое обобщение ее различных методик

стало выяснение вопроса относительно так называемой «оптимальной величины» городов. Подразумевалось, что раз существует чрезмерное перенаселение некоторых городов, то есть и оптимальная его величина, которая может быть вычислена градостроительной наукой. «...Понятие "оптимального"города оставалось одним из наиболее существенных элементов советской градостроительной политики. .Не было сомнения в том, что такой оптимум существует. Разногласия начинались при попытке определить, какую именно людность следует считать оптимальной. В 1920-е гг. оптимальным казалось 50-тысячное население. Оно было достаточным для того, чтобы проявились выгоды от экономии на масштабе производства и городской инфраструктуре, и в то же время не столь большим, чтобы разрушить чувство общности и социалистическую коммунальную этику. В середине 1950-х гг. оценки оптимума колебались между 150 тысячами и 200 тысячами, а к 1960 г. они подскочили уже к 250-300 тысячам человек, и сама правомерность этой концепции. была поставлена под сомнение» . Спор оказался схоластичен, потому что оптимальность размера города зависит не от абсолютной ве-

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

Вопрос об этой оптимальной величине города по-новому остро встал в 1960-1970-е гг., когда в СССР наметился рост числа крупных и крупнейших городов, стали заметны их недостатки. В статье с характерным названием «Максимальные размеры города» (1970) утверждалось: «С точки зрения городского хозяйства, наиболее экономичны города, в которых меньше сумма капиталовложений и эксплуатационных расходов в пересчете на одного жителя. Неэкономичными оказываются как слишком маленькие города, так и города-гиганты. В городском строительстве проявляется общий для всех областей экономики принцип, в соответствии с которым крупная хозяйственная единица эффективнее малой. В маленьких городках с числом жителей до 20 тысяч приходится создавать мелкие, малопроизводительные коммунальные и бытовые предприятия. С ростом городов, они становятся экономичнее. <.> С дальнейшим ростом численности населения положение ухудшается, <.> невозможно

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

Авторы статьи считают, что им удалось найти ответ на оптимизационную задачу: «Взвешивая все "за" и "против", во многих странах, в том числе и в СССР, градостроители и экономисты пришли к выводу, что в настоящее время следует ограничить рост городов с миллионным населением, стимулируя развитие городов средней величины (курсив наш. - А. М.)» .

Видим, что оптимальным признается город средней величины, с численностью населения от 50 тыс. до 100 тыс. жителей. С этим выводом не согласен В. И. Переведенцев, который видит решение вопроса опять-таки в сфере экономики, но более глубоко. Он показывает нелинейный характер зависимостей экономической эффективности от величины города: «Город - это не только дома, где живут люди, но и заводы, где они работают. Оказывает ли размер города влияние на производительность труда? Да, оказывает. Большой город выгоден с точки зрения производства. Это выгоды совместного использования

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

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

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

В качестве завершения этой дискуссии стоит привести симптоматичную жалобу самого В. И. Пере-веденцева о том, что города в своем развитии уходят от состояния оптимальности, а не приходят к нему: «... Наиболее высокие темпы прироста населения имели города, в которых в 1959 г. было от 400 до 600 тысяч человек - свыше 35 процентов. По господствующим в нашем градостроительстве воззрениям, оптимальными считаются города с населением 50-200 тысяч человек, допустимыми - до 400 тысяч. Значит, быстрее всего росли города, вышедшие за пределы "допустимых". "Оптимальные" города росли тоже быстро, становясь неоптимальными (курсив наш. - А. М.)» .

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

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

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

3 Возникло новое понимание понятия оптимальной величины города, своего рода не абсолютная, а относительная оптимальная величина, которая связана не с абсолютными, а относительными показателями. Причем наиболее четким таким показателем предлагается считать соответствие размеров города его параметрам, заданным в генеральном плане.

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

Виды оптимизационных задач в градостроительстве

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

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

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

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

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

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

1) Природно-экологическая подсистема.

2) Социально-демографическая подсистема.

3) Экономическая подсистема.

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

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

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

в качестве идеального конечного результата.

Список использованной литературы

1 Шупер В. А. Самоорганизация городского расселения/Рос. открытый ун-т. М., 1995.

2 Покшишевский В. В. Заселение Сибири. Историко-географиче-ские очерки. М., 1951.

3 Бразовская Н. В. Методы оптимизации: учеб. пособие / Алтайский гос. техн. ун-т им. И. И. Ползунова [Центр дистанц. обучения]. Барнаул, 2000.

4 Большая Советская Энциклопедия. 3-е изд. М., 1975. Т. 19.

5 Райзберг Б. А., Лозовский Л. Ш., Стародубцева Е. Б. Современный экономический словарь. 2-е изд., испр. М., 1999.

6 Экономика: толковый словарь. М., 2000.

7 Переведенцев В. И. Методы изучения миграции населения, М., 1975.

8 Дубровский П. Н. Максимальные размеры города // Наука и техника. 1970. № 6.

9 Мазаев А. Г. Национальная территориальная система расселения как фактор контроля: геополитический подход // Академический вестник УралНИИпроект РААСН. 2008. № 1. С. 32-37.

10 Мазаев А. Г. Формирование и развитие системы расселения Урала (XVII-XIX вв.): этапы и геополитические особенности // Академический вестник УралНИИпроект РААСН. 2014. № 1. С. 10.

11 Мазаев А. Г. Анализ развития структуры системы расселения Урала (конец XIV - XX век) методом скользящих средних // Академический вестник УралНИИпроект РААСН. 2014. № 3. С. 34.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Федеральное агентство по образованию ГОУ ВПО «Уральский государственный технический университет - УПИ» ПАРАМЕТРИЧЕСКАЯ ОПТИМИЗАЦИЯ РАДИОЭЛЕКТРОННЫХ СХЕМ Методические указания к лабораторной работе по курсу “Компьютерный анализ электронных схем” для студентов всех форм обучения специальности 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

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) является точкой локального минимума, а так как это единственная стационарная точка, то она же является и точкой глобального минимума.

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

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

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

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

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

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

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

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

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

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

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

1. детерминированные;
2. случайные (стохастические);
3. комбинированные.

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

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

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

См. также

Примечания

Литература

• Абакаров А. Ш., Сушков Ю. А. Статистическое исследование одного алгоритма глобальной оптимизации . - Труды ФОРА, 2004.
• Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. - М .: Высшая школа, 1986.
• Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. - М .: Мир, 1985.
• Гирсанов И. В. Лекции по математической теории экстремальных задач. - М .; Ижевск : НИЦ «Регулярная и хаотическая динамика», 2003. - 118 с. - ISBN 5-93972-272-5
• Жиглявский А. А., Жилинкас А. Г. Методы поиска глобального экстремума. - М .: Наука, Физматлит, 1991.
• Карманов В. Г. Математическое программирование. - Изд-во физ.-мат. литературы, 2004.
• Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М .: Наука, 1970. - С. 575-576.
• Коршунов Ю. М., Коршунов Ю. М. Математические основы кибернетики. - М .: Энергоатомиздат, 1972.
• Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. - М .: МИФИ, 1982.
• Максимов Ю. А. Алгоритмы линейного и дискретного программирования. - М .: МИФИ, 1980.
• Плотников А. Д. Математическое программирование = экспресс-курс. - 2006. - С. 171. - ISBN 985-475-186-4
• Растригин Л. А. Статистические методы поиска. - М ., 1968.
• Хемди А. Таха. Введение в исследование операций = Operations Research: An Introduction. - 8 изд. - М .: Вильямс, 2007. - С. 912. - ISBN 0-13-032374-8
• Кини Р. Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. - М .: Радио и связь, 1981. - 560 с.
• С.И.Зуховицкий , Л.И.Авдеева. Линейное и выпуклое программирование. - 2-е изд., перераб. и доп.. - М .: Издательство «Наука», 1967.

Ссылки

• Б.П. Поляк . История математического программирования в СССР: анализ феномена // Труды 14-й Байкальской школы-семинара «Методы оптимизации и их приложения» . - 2008. - Т. 1. - С. 2-20.

Методы оптимизации
Одномерные	Метод золотого сечения Дихотомия Метод парабол Перебор по сетке Метод Фибоначчи Троичный поиск
Прямые методы	Метод Гаусса Метод Нелдера - Мида Метод Хука - Дживса Метод конфигураций Метод Розенброка
Первого порядка	Градиентный спуск Метод Зойтендейка Покоординатный спуск Метод сопряжённых градиентов Квазиньютоновские методы Алгоритм Левенберга - Марквардта
Второго порядка	Метод Ньютона Метод Ньютона - Рафсона
Стохастические	Метод Монте-Карло Имитация отжига Эволюционные алгоритмы Дифференциальная эволюция Муравьиный алгоритм Метод роя частиц
Методы линейного программирования	Симплекс-метод Алгоритм Гомори Метод эллипсоидов Метод потенциалов
Методы нелинейного программирования	Последовательное квадратичное программирование

Wikimedia Foundation . 2010 .