Методы оптимизации


Методы оптимизации

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

Формально, задача математического программирования формулируется так:

Найти \operatorname{argmin}_{x\in X}\; f(x)

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

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

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

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

История

Задачи линейного программирования были первыми, подробно изученными задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 г. Ж. Фурье и затем в 1947 г. Дж. Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции — симплекс-метод, ставший основным при решении задач линейного программирования.

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

Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Одними из первых, исследовавшими в общей форме задачи линейного программирования, были: Джон фон Нейман, знаменитый математик и физик, доказавший основную теорему о матричных играх и изучивший экономическую модель, носящую его имя; советский академик, лауреат Нобелевской премии (1975 г.) Л. В. Канторович, сформулировавший ряд задач линейного программирования и предложивший (1939 г.) метод их решения (метод разрешающих множителей), незначительно отличающийся от симплекс-метода.

В 1931 г. венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

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

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

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

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

Литература

  • Хемди А. Таха Введение в исследование операций = Operations Research: An Introduction. — 8 изд.. — М.: «Вильямс», 2007. — С. 912. — ISBN 0-13-032374-8
  • А.Д. Плотников Математическое программирование = экспресс-курс. — 2006. — С. 171. — ISBN 985-475-186-4

Wikimedia Foundation. 2010.

Смотреть что такое "Методы оптимизации" в других словарях:

  • методы оптимизации — — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN optimization strategyoptimization techniques …   Справочник технического переводчика

  • РД 50-216-80: Методические указания. Количественные методы оптимизации параметров объектов стандартизации. Основные положения по обеспечению широкого внедрения. Направления работ и унификация методов и документов — Терминология РД 50 216 80: Методические указания. Количественные методы оптимизации параметров объектов стандартизации. Основные положения по обеспечению широкого внедрения. Направления работ и унификация методов и документов: Базовая… …   Словарь-справочник терминов нормативно-технической документации

  • Численные методы оптимизации — [numerical optimization technique] методы приближенного или точного решения математических задач оптимизации, сводящиеся к выполнению конечного числа элементарных операций над числами. (См. например, Градиентные методы). Численные методы предмет… …   Экономико-математический словарь

  • численные методы оптимизации — Методы приближенного или точного решения математических задач оптимизации, сводящиеся к выполнению конечного числа элементарных операций над числами. (См. например, Градиентные методы). Численные методы предмет изучения вычислительной математики …   Справочник технического переводчика

  • оптимизации мышления методы —         ОПТИМИЗАЦИИ МЫШЛЕНИЯ МЕТОДЫ (от лат. optimus наилучший) специальные практические психолого педагогические приемы, направленные на повышение эффективности протекания мыслительного процесса, его продуктивности. Разработка конкретного метода …   Энциклопедия эпистемологии и философии науки

  • Методы изобретательного творчества — Методы технического творчества  это совокупность последовательности операций прогнозирования оптимальных параметров, в наибольшей степени отвечающих общественным или техническим потребностям. Содержание 1 Развитие методики изобретательного… …   Википедия

  • МЕТОДЫ ПРОЕКТИРОВАНИЯ СУДОВ — методы, используемые для определения основных элементов проектируемых судов, а также для решения ряда других задач, предусматриваемых теорией проектирования судов: разработки задания на проектирование судна; построения теоретического чертежа;… …   Морской энциклопедический справочник

  • Методы активного обучения — (МАО) совокупность педагогических действий и приёмов, направленных на организацию учебного процесса и создающего специальными средствами условия, мотивирующие обучающихся к самостоятельному, инициативному и творческому освоению учебного материала …   Википедия

  • методы сетевого планирования и управления — Комплекс методов построения, расчёта, анализа и оптимизации сетевых моделей [Терминологический словарь по строительству на 12 языках (ВНИИИС Госстроя СССР)] Тематики сетевое планирование, моделирование EN methods of network planning and control… …   Справочник технического переводчика

  • МЕТОДЫ КЛАССИФИКАЦИИ — совокупность методов статистич. многомерного анализа. В зависимости от того, в какой области научн. знаний М.к. возникли и получили свое развитие, они наз. методами многомерной классификации, таксономии, кластерного анализа, группировки,… …   Российская социологическая энциклопедия

Книги

  • Методы оптимизации, А. В. Аттетков, В. С. Зарубин, А. Н. Канатников. Освещается одно из важнейших направлений математики - теория оптимизации. Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной оптимизации. Описаны алгоритмы… Подробнее  Купить за 1370 грн (только Украина)
  • Методы оптимизации, А. П. Смирнов. Особое внимание уделено построению алгоритмов поиска экстремума, что даст возможность студентам самостоятельно разрабатывать соответствующие программные средства в случаях, когда… Подробнее  Купить за 512 руб электронная книга
  • Методы оптимизации, А. В. Аттетков, В. С. Зарубин, А. Н. Канатников. Освещается одно из важнейших направлений математики - теория оптимизации. Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной оптимизации. Описаны алгоритмы… Подробнее  Купить за 402 руб
Другие книги по запросу «Методы оптимизации» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.