Прямые методы решения нелинейных оптимизационных задач реферат

Обновлено: 02.07.2024

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

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

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

при ограничениях (2.1)

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

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

Пусть функция определена на . Задача одномерной оптимизации – задача, в которой требуется найти мах(min) , . Решение (точка максимума (минимума)) задачи одномерной оптимизации – точка , при условии для всех .

Функция называется унимодальной на множестве , если существует единственная точка её максимума на и для любых ,

Унимодальная функция монотонно возрастает слева от точки максимума и монотонно убывает справа от неё.

В процессе применения методов одномерной оптимизации выделяют два этапа:

· поиск отрезка, содержащего точку максимума;

· уточнение координаты точки максимума на данном отрезке.

Алгоритм Свенна

Исходные данные: – начальная точка, – шаг поиска ( ).

Этап 1. Определить , , , .

Этап 2. Если , то перейти на 4 этап.

Этап 3. Если , то , перейти на 4 этап, в противном случае ( ), , , конец.

Этап 4. . Определить .

Этап 5. Если , то , переход на 4 этап.

Этап 6. Если , то , , конец. В противном случае , , конец.

Случай (этап 3) не рассматривается, так как он противоречит предположению о модальности функции .

Метод золотого сечения

Золотое сечение отрезка – деление отрезка на две неравные части таким образом, что отношение длины всего отрезка к длине большей части равно отношению длины большей части к длине меньшей части отрезка. Золотое сечение отрезка производится двумя точками и , симметричными относительно середины отрезка (рисунок 2.1).

Рисунок 2.1 – Золотое сечение

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

Алгоритм золотого сечения включает этапы:

Исходные данные: – отрезок, содержащий точку максимума, – параметр окончания счёта.


Методы перебора применимы для отыскания экстремумов унимодальных целевых функций. Действие любого из методов поиска заключается в сужении области поиска экстремума (длины l 0):
а) до области заданной длины (e> 0), проводя минимальное число измерений значений функции (методы дихотомии, золотого сечения);
б) до наименьших возможных размеров ln при заданном числе измерений n (метод Фибоначчи).
Первая формулировка целесообразна в том случае, если с каждым измерением связаны значительные затраты средств или времени, однако на поиск отпускаются неограниченные средства, которые мы все же стремимся минимизировать; вторая – когда исследователь располагает ограниченными средствами и, зная расходы, связанные с каждым измерением, стремится получить наилучший результат.

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

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

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

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

Белорусский государственный университет

информатики и радиоэлектроники

Факультет информационных технологий и управления

Кафедра информационных технологий автоматизированных систем

на тему: «Решение оптимизационной задачи

Выполнил студент гр. 920603 Журавкин А.В.

Руководитель работы Батин Н.В.

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

Построение аналитической модели…………………………………….…9

Обоснование и описание вычислительной процедуры………………..11

Приведение задачи линейного программирования к стандартной форме………………..………………………………………………….11

Основная идея симлекс-метода……………………………………..12

4. Решение задачи оптимизации на основе симплекс-таблиц……………14

Приведение задачи к стандартной форме………..………………..14

Определение начального допустимого решения…………………14

Построение искусственного базиса………. ………………………15

Первый этап двухэтапного симплекс-метода…………………….16

Второй этап двухэтапного метода………………………………….19

5. Анализ модели на чувствительность……………………………………..22

Анализ на чувствительность к изменениям правых частей ограничений……………………………………………………….…..23

Анализ на чувствительность к изменениям коэффициентов целевой функции……………………………………………. ………25

6. Определение оптимального целочисленного решения…………………26

6.1. Метод Гомори для частично целочисленных задач……..……….26

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………….……..34

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

Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

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

 количество продукции - расход сырья

 количество продукции - качество продукции

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

При постановке задачи оптимизации необходимо:

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

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

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

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

а) получить максимальную производительность при заданной себестоимости;

б) получить минимальную себестоимость при заданной производительности;

В первом случае критерий оптимизации - производительность а во втором - себестоимость.

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

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

4. Учет ограничений.

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

Критерием оптимальности называется количественная оценка оптимизируемого качества объекта.

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

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

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

рационального использования сырья и материалов; задачи оптимизации раскроя;

оптимизации производственной программы предприятий;

оптимального размещения и концентрации производства;

составления оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

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

Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике.

Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода.

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

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

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

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

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

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


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

Определение подхода к разработке и формулировка основной задачи

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

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

Итак, в этой работе я расскажу:

  1. О задаче оптимизации и причинах ее выбора в качестве основополагающего объекта изучения,
  2. Об основных абстракциях и их реализациях, которые позволят использовать подход, основывающийся на решении прикладных задач путем сведения к задаче оптимизации,
  3. Об алгоритме K-Means, простейшем алгоритме Random Search и как заставить их дружить и работать на благо единой цели.

Оптимизация

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

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

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

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

    аналитические алгоритмы:

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

Используемые абстракции

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

Преобразования (Transformations)

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

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


Остановимся на элементах поподробнее:

  • Неоднородное преобразование (Inhomogeneous Transformation) — самый общий вид преобразования, когда классы входного и выходного объекта могут быть различными,
  • Однородное преобразование (Homogeneous Transformation) — частный вид неоднородного преобразования, когда классы входного и выходного объекта одинаковые,
  • Векторная функция (Vector Function) — преобразование, которой трансформирует вектор, состоящий из элементов множества A, в другой вектор, состоящий из элементов того же множества,
  • Функция (Function) — аналогична векторной функции (за исключением того, что выходной элемент теперь является скаляром),
  • Метрика (Metric) — некоторое оценивающее преобразование, ставящее в соответствие объекту числовое значение.


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


Налицо измененная параметризация обобщенного класса. Теперь данный параметр определяет то, из объектов какого класса будет состоять преобразуемый вектор. Следует отметить ограничение, накладываемое на класс, что определяется данным кодом "[A

Читайте также: