Теоретическая часть

Краткое содержание лекции

Математическое программирование

К математическому программированию относится следующие типы задач:

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

2. Нелинейное программирование целевая функция и ограничения могут быть нелинейными функциями.

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

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

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

6. Стохастическое линейное программирование. Бывает много практических ситуаций, когда коэффициенты c_i целевой функции, коэффициенты a_ij в матрице коэффициентов, коэффициенты ограничений b_i - являются случайными величинами. В этом случае сама целевая функция становится случайной величиной, и ограничения типа неравенств могут выполняться лишь с некоторой вероятностью.

7. Геометрическое программирование. Под задачами геометрического программирования понимают задачи наиболее плотного расположения некоторых объектов в заданной двумерной или трехмерной области.

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

9. Теория игр изучает явления, возникающие в конфликтных ситуациях, в условиях столкновения сторон.

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

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

- аналитические методы;

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

Группа аналитических методов оптимизации объединяет аналитический поиск экстремума функции, метод множителей Лагранжа, вариационные методы и принцип максимума. Аналитический поиск экстремума функции, заданной без ограничений на независимые переменные, применяется к задачам, у которых оптимизируемая функция имеет аналитическое выражение, дифференцируемое во всем диапазоне исследования, а число переменных невелико. Это один из наиболее простых методов.

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

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

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

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

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

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

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

1. Допустимое множество – множество ;

2. Целевую функцию – отображение f: X ® R;

3. Критерий поиска (max или min).

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

1. Показать, что X = Æ.

2. Показать, что целевая функция не ограничена снизу.

3. Найти .

4. Если , то найти .

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов. Если допустимое множество X = Rⁿ, то такая задача называется задачей безусловной оптимизации, в противном случае – задачей условной оптимизации.

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

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

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

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

1. детерминированные;

2. случайные (стохастические);

3. комбинированные.

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

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

• Задачи оптимизации, в которых целевая функция и ограничения являются линейными функциями, разрешаются так называемыми методами линейного программирования.
• В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:
• если и – выпуклые функции, то такую задачу называют задачей выпуклого программирования;
• если X Ì Z, то имеют дело с задачей целочисленного (дискретного) программирования.

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

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

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

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

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

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

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

Параметрическое программирование (Макропрограммирование) – это язык программирования ЧПУ. Производители систем управления используют параметрическое программирование в качестве расширения G-кода. Его можно сравнить с компьютерными языками программирования, такими как Basic, но он может быть доступен на уровне G-функций (кодов). В отличие от ЧПУ программирования, в параметрическом программировании расширяются возможности, сравнимые с объектно-ориентированными. Используя его системах управления ЧПУ становится возможным вариантность вычисления, применение логических операторов, работа с проходами инструмента, движениями манипуляторов. Возможность организации циклов, выбор по условию, переход, работа с подпрограммами. Добавляются элементы, осуществляющих полный контроль над ЧПУ - доступ к системным переменным и ячейкам программы электроавтоматики, возможность создавать свои собственные G-коды и функции, которые наиболее полно реализуют управление всех компонентов станка. Возможен доступ к параметрам ЧПУ, хранящим информацию об инструменте, положении рабочих органов, манипуляторов, системы координат, значений G-кода управляющей программы и ошибок. С помощью параметрического программирования можно разрабатывать диалоговые управляющие программы. Подобно компьютерным языкам программирования, в параметрическом программировании их существует несколько версий: Custom Macro, User Task (Okuma), Q Routine (Sodick), Advanced Programming Language (APL G& L). Например, язык макропрограммирования FMS-3000 из подмножества языка Basic дает возможность организовать дополнительные информационные окна, систему слежения за параметрами, режимы контроля и протоколирования процессов обработки. Такие программы выполняются в фоновом режиме и в свободное от всех других задач время, при большой загрузке могут временно приостанавливать свою работу. Используя такие возможностями, имеешь один из эффективных способов управления станком, роботом, системой ЧПУ.

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

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

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

Процессы нахождения экстремума

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

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

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

Термин «линейное программирование» предложен Дж. Данцигом в 1949 г. для изучения теоретических и алгоритмических задач, связанных с оптимизацией линейных функций при линейных ограничениях. Название «Математическое программирование» связано с тем, что целью решения задач является выбор оптимальной программы действий. Выделение класса экстремальных задач, определяемых линейным функционалом на множестве, задаваемом линейными ограничениями, следует отнести к 30-м годам ХХ столетия. Джон фон Нейман – доказал основную теорему о матричных играх и изучивший экономическую модель, носящую его имя. Л.В. Канторович – сформулировал ряд задач линейного программирования и предложил метод разрешающих множителей, незначительно отличающийся от симплекс-метода. Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода». Основной метод решения задач линейного программирования – симплекс-метод – был опубликован в 1949 г Дж. Данцигом.

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

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

AMPL («A Modeling Language for Mathematical Programming» – «Язык моделирования для математического программирования») – язык программирования высокого уровня, разработанный в Bell Laboratories, для того, чтобы описывать и решать сложные задачи оптимизации и теории расписаний. AMPL не решает задачи непосредственно, а вызывает соответствующие внешние решатели (типа CPLEX, MINOS, IPOPT, SNOPT и т. д.), для получения решения. AMPL работает с линейными и нелинейными задачами оптимизации с дискретными или непрерывными переменными. Одно из преимуществ AMPL – подобие его синтаксиса математической записи задач оптимизации. Многие современные решатели, доступные на сервере NEOS, принимают ввод моделей на AMPL. AMPL был создан Robert Fourer, David Gay и Брайаном Керниганом.

Таблица. Области применения методов оптимизации.