|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Общие задачи оптимизацииКлассификация методов оптимизации Общая запись задач оптимизации задаёт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность её решения). Классификацию задач определяют: целевая функция и допустимая область (задаётся системой неравенств и равенств или более сложным алгоритмом)[1]. Методы оптимизации классифицируют в соответствии с задачами оптимизации: § Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом. § Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции. Существующие в настоящее время методы поиска можно разбить на три большие группы: 1. детерминированные; 2. случайные (стохастические); 3. комбинированные. По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной оптимизации и методымногомерной оптимизации. По виду целевой функции и допустимого множества, задачи оптимизации и методы их решения можно разделить на следующие классы: § Задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования. § В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи: § если и — выпуклые функции, то такую задачу называют задачей выпуклого программирования; § если , то имеют дело с задачей целочисленного (дискретного) программирования. По требованиям к гладкости и наличию у целевой функции частных производных, их также можно разделить на: § прямые методы, требующие только вычислений целевой функции в точках приближений; § методы первого порядка: требуют вычисления первых частных производных функции; § методы второго порядка: требуют вычисления вторых частных производных, то есть гессиана целевой функции. Помимо того, оптимизационные методы делятся на следующие группы: § аналитические методы (например, метод множителей Лагранжа и условия Каруша-Куна-Таккера); § численные методы; § графические методы. В зависимости от природы множества X задачи математического программирования классифицируются как: § задачи дискретного программирования (или комбинаторной оптимизации) — если X конечно или счётно; § задачи целочисленного программирования — если X является подмножеством множества целых чисел; § задачей нелинейного программирования, если ограничения или целевая функция содержат нелинейные функции и X являетсяподмножеством конечномерного векторного пространства. § Если же все ограничения и целевая функция содержат лишь линейные функции, то это — задача линейного программирования. Кроме того, разделами математического программирования являются параметрическое программирование, динамическое программирование и стохастическое программирование. Математическое программирование используется при решении оптимизационных задач исследования операций. Способ нахождения экстремума полностью определяется классом задачи. Но перед тем, как получить математическую модель, нужно выполнить 4 этапа моделирования: § Определение границ системы оптимизации § Отбрасываем те связи объекта оптимизации с внешним миром, которые не могут сильно повлиять на результат оптимизации, а, точнее, те, без которых решение упрощается § Выбор управляемых переменных § «Замораживаем» значения некоторых переменных (неуправляемые переменные). Другие оставляем принимать любые значения из области допустимых решений (управляемые переменные) § Определение ограничений на управляемые переменные § … (равенства и/или неравенства) § Выбор числового критерия оптимизации (например, показателя эффективности) § Создаём целевую функцию
· · ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ [linear programming] — область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостьюмежду переменными. В самом общем виде задачу Л. п. можно записать так. Даны ограничения типа или в т. н. канонической форме, к которой можно привести все три указанных случая: Требуется найти неотрицательные числа xj (j = 1, 2,..., n), которые минимизируют (или максимизируют) линейную форму Неотрицательность искомых чисел записывается так: xj ≥ 0. Таким образом, здесь представлена общая задача математического программирования с оговорками: как ограничения, так и целевая функция линейные, а искомые переменные неотрицательные. Обозначения можно трактовать следующим образом: bi — количество ресурса вида i; m — количество видов этих ресурсов; aij — норма расхода ресурса вида i на единицу продукции вида j; xj — количество продукциивида j, причем количество таких видов — n; cj — доход (или другой выигрыш) от единицы этой продукции, а в случае задачи на минимум — затраты на единицу продукции; нумерация ресурсов разделена на три части: от 1 до m1, от m1 + 1 до m2 и от m2 + 1 до m в зависимости от того, какие ставятся ограничения на расходование этих ресурсов; в первом случае — “не больше”, во втором — “столько же”, в третьем — “не меньше”; Z — в случае максимизации, напр., объем продукции или дохода, в случае же минимизации — себестоимость, расход сырья и т. п. Добавим еще одно обозначение, оно появится несколько ниже: vi — оптимальная оценка i-го ресурса. Слово “программирование” объясняется здесь тем, что неизвестные переменные, которые отыскиваются в процессе решения задачи, обычно в совокупности определяют программу (план) работы некоторого экономического объекта. Слово “линейное” отражает факт линейной зависимости между переменными. При этом, как указано, задача обязательно имеет экстремальный характер, т. е. состоит в отысканииэкстремума (максимума или минимума) целевой функции. Следует с самого начала предупредить: предпосылка линейности, когда в реальной экономике подавляющее большинство зависимостей носит более сложный нелинейный характер, есть огрубление, упрощение действительности. В некоторых случаях оно достаточно реалистично, в других же выводы, получаемые с помощью решения задач Л. п., оказываются весьма несовершенными.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |