 |
Методологические основы оптимизации.
|
|
|
|
Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения
При решении конкретной задачи оптимизации исследователь прежде всего должен выбрать математический метод, который приводил бы к конечным результатам с наименьшими затратами на вычисления или же давал возможность получить наибольший объем информации об искомом решении. Выбор того или иного метода в значительной степени определяется постановкой оптимальной задачи, а также используемой математической моделью объекта оптимизации.
В настоящее время для решения оптимальных задач применяют в основном следующие методы:
методы исследования функций классического анализа;
методы, основанные на использовании неопределенных множителей Лагранжа;
вариационное исчисление;
динамическое программирование;
принцип максимума;
линейное программирование;
нелинейное программирование.
В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.
Как правило, нельзя рекомендовать какой-либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике. Одни методы в этом отношении являются более общими, другие - менее общими. Наконец, целую группу методов (методы исследования функций классического анализа, метод множителей Лагранжа, методы нелинейного программирования) на определенных этапах решения оптимальной задачи можно применять в сочетании с другими методами, например динамическим программированием или принципом максимума.
|
|
|
Отметим также, что некоторые методы специально разработаны или наилучшим образом подходят для решения оптимальных задач с математическими моделями определенного вида. Так, математический аппарат линейного программирования, специально создан для решения задач с линейными критериями оптимальности и линейными ограничениями на переменные и позволяет решать большинство задач, сформулированных в такой постановке. Так же и геометрическое программирование предназначено для решения оптимальных задач, в которых критерий оптимальности и ограничения представляются специального вида функциями позиномами.
Динамическое программирование хорошо приспособлено для решения задач оптимизации многостадийных процессов, особенно тех, в которых состояние каждой стадии характеризуется относительно небольшим числом переменных состояния. Однако при наличии значительного числа этих переменных, т. е. при высокой размерности каждой стадии, применение метода динамического программирования затруднительно вследствие ограниченных быстродействия и объема памяти вычислительных машин.
Пожалуй, наилучшим путем при выборе метода оптимизации, наиболее пригодного для решения соответствующей задачи, следует признать исследование возможностей и опыта применения различных методов оптимизации. Ниже приводится краткий обзор математических методов решения оптимальных задач и примеры их использования. Здесь же дана лишь краткая характеристика указанных методов и областей их применения, что до некоторой степени может облегчить выбор того или иного метода для решения конкретной оптимальной задачи
Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.
|
|
|
Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно.
Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например:
· количество продукции - расход сырья
· количество продукции - качество продукции
Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи.
При постановке задачи оптимизации необходимо:
1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры.
Типичный пример неправильной постановки задачи оптимизации:
«Получить максимальную производительность при минимальной себестоимости».
Ошибка заключается в том, что ставится задача поиска оптимальности 2-х величин, противоречащих друг другу по своей сути.
Правильная постановка задачи могла быть следующая:
а) получить максимальную производительность при заданной себестоимости;
б) получить минимальную себестоимость при заданной производительности;
В первом случае критерий оптимизации - производительность а во втором - себестоимость.
2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.
3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
4. Учет ограничений.
Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности.
|
|
|
Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.
На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации.
Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции.
В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них.
Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми.
Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».
Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр.
|
|
|
Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.
Оптимизационная модель.
ОПТИМАЛЬНАЯ (ИЛИ ОПТИМИЗАЦИОННАЯ) МОДЕЛЬ [optimization model] — экономико-математическая модель, которая охватывает некоторое число вариантов (технологических способов) производства, распределения или потребления и предназначена для выбора таких значений переменных, характеризующих эти варианты, чтобы был найден лучший из них.
В отличие от дескриптивной (описательной, балансовой) модели О. м. содержит наряду с уравнениями, описывающими взаимосвязи между переменными, также критерий для выбора — функционал (или, что то же, целевую функцию).
О. м. — основной инструмент экономико-математических методов. Обычно они очень сложны, насчитывают сотни и тысячи уравнений и переменных. Но общая структура таких моделей проста. Она состоит из целевой функции, способной принимать значения (на множестве значений переменных) в пределах области, ограниченной условиями задачи (области допустимых решений), и ограничений, характеризующих эти условия. Целевая функция в самом общем виде в свою очередь состоит из трех элементов: управляемых переменных, параметров (или также переменных), которые не поддаются управлению (напр., зависящих от внешней среды), и формы зависимости между ними (формы функции).
|
|
|
Для того чтобы использовать результаты и вычислительные процедуры теории оптимизации на практике, необходимо прежде всего построить математическую модель объекта оптимизации. Под математической моделью любой реальной системы принято понимать совокупность соотношений, определяющих характеристики состояний системы в зависимости от начальных условий и времени
В практике исследования объектов модели могут применяться для самых разных целей, что вызывает использование моделей различных классов. Построение одной модели для сложной системы практически не представляется возможным без разработки вспомогательных моделей. Поэтому при создании конечной математической модели исследуемого объекта строят частные вспомогательные модели, отражающие ту или иную информацию об объекте, имеющуюся у разработчика на данном этапе построения модели. Для построения модели необходима система правил (принципов), позволяющих корректно осуществлять процесс построения. Общие принципы системного экономико-математического моделирования вытекают из общих принципов системного анализа1. принцип достаточности используемой информации; 2. принцип инвариантности используемой информации; 3. принцип преемственности модели; 4. принцип эффективной реализуемости комплекса экономико-математических моделей.
При рассмотрении экономико-математических моделей оперируют следующими понятиями: критерий оптимальности, целевая функция, система ограничений, уравнения связи, решение модели. Критерием оптимальности называется некоторый показатель, имеющий экономическое содержание, служащий формализацией конкретной цели управления и выражаемый при помощи целевой функции через факторы модели. Критерий оптимальности определяет смысловое содержание целевой функции. Целевая функция математически связывает между собой факторы модели, и ее значение определяется значениями этих величин. Содержательный смысл целевой функции придает только критерий оптимальности. При наличии нескольких критериев оптимальности каждый из них будет описываться своей частной целевой функцией. Система ограничений определяет пределы, сужающие область осуществимых или допустимых решений и фиксирующие основные внешние и внутренние свойства объекта. Ограничения определяют область протекания процесса, пределы изменения параметров и характеристик объекта.
Уравнения связи являются математической формализацией системы ограничений. Различные по смыслу ограничения могут описываться одинаковыми уравнениями связи, а одно и то же ограничение в разных моделях может описываться разными уравнениями связи. Решением математической модели называется такой набор (совокупность) значений переменных, который удовлетворяет ее уравнениям связи. Общих способов построения математических моделей не существует, но можно условно разбить процесс на следующие основные этапы: 1. определение границ объекта оптимизации; 2. выбор управляемых переменных; 3. определение ограничений на управляемые переменные; 4. выбор критерия оптимизации; 5. формулировка математической задачи
|
|
|
