18. Метод квадратичного программирования.

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

Основные сведения

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

при ограничениях

Лагранжиан задачи примет следующий вид:

где λ и σ — множители Лагранжа.

На итерации xk основного алгоритма определяются соответствующие направления поиска dk как решение следующей подзадачи квадратичного программирования:

при ограничениях

19. Сепарабельное программирование. Метод кусочно-линейной аппроксимации.

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

Определение.

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

Кусочно-линейная аппроксимация для сепарабельной непрерывной функции f(x) строится следующим образом. Интервал значений каждой переменной x_i разбивается при помощи сетки с K_i узлами. Таким образом, на интервале x_i^(L) Ј x_i Ј x_i^(R) рассматривается следующая последовательность точек:

x_i^(L) = x_i⁽¹⁾ < x_i⁽¹⁾ <...< x_i^(Ki) = x_i^(R)

Введём обозначение f_i(k) = f_i(x_i^(k) ). Тогда аппроксимирующая функция примет вид:

причём при всех i=1,...,N выполняется:

Последнее условие выражает тот факт, что не более двух переменных l⁽ⁱ⁾ должны быть положительными.

Таким образом, нелинейная функция f(x) заменяется кусочно-линейной . Для построения хорошего приближения число узлов сетки должно быть большим, то есть линейность достигается за счёт роста размерности задачи, то есть решение задачи НЛП сводится к решению задачи ЛП большой размерности с переменными l_i^(k) . Полученная задача ЛП может быть решена с помощью симплекс-метода, дополненного правилом ограниченного ввода в базис, учитывающего условие (*).

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

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

20. Задачи дробно-линейного программирования (гиперболическое программирование).

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

ДЛП является обобщением линейного программирования (ЛП) и, в то же время, частным случаем математического программирования. Как и в ЛП, принято разделение на общую задачу ДЛП и специальные задачи ДЛП (например, транспортная задача ДЛП, целочисленная задача ДЛП и т. д.).

Этапы для решение задачи:

1.В системе ограничений задачи заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые.

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

3 находят многоугольник решений задачи

4.Строят прямую , уравнение которой получается , если положить значение целевой функции равным некоторому постоянному числу.

5.Определяют точку максимума или устанавливают неразрешимость задачи

6.Находят значение целевой функции в точке .

21. Дискретное программирование. Общие характеристики дискретных задач. Математические модели дискретных задач и их классификации.

Дискретное программирование (дискретная оптимизация) — раздел математического программирования.

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

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

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

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

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

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

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

Примеры задач:

• Задача о назначениях

• Задача о ранце

• Задача коммивояжера

• Задачи теории расписаний

• Задача маршрутизации транспорта

• Задачи о покрытиях графов