Опорный конспект лекции дисциплины «Методы оптимизации и исследование операции» (стр. 3 )

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

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

Алгоритм:

1) Задаём начальное приближение для и вычисляем два смежных аргумента :

, где

- полуинтервал интерполяции

2) вычисляем 3 значение :

, и

3)Находим коэффициенты

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

4) Проверяем условие , если оно не выполняется, то и идём к 1).

Если выполняется условие, то - найдено и вычисляем и завершаем счёт.

Многомерная оптимизация заключается в поиске экстремумов функции многих переменных .

Из всего разнообразия методов многомерной оптимизации ограничимся рассмотрением 3-х относительно простых методов поиска минимума .

Метод покоординатного спуска

Этот метод заключается в поочерёдном поиске минимума по координате ,

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

для каждой переменной.

1)Выбор нулевого приближения.

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

Затем из новой точки сделаем спуск по направлению, параллельному оси , т. е. рассмотрим, находим её минимум и обозначаем через .

Второй шаг приводит к точке .

Затем третий шаг - спуск параллельно оси и находим

Переход к точке завершает цикл спусков.

Циклы повторяются. На конечном спуске функция не возрастает, и значение функции снизу ограничены значения в

Метод парабол.

Если - дифференцируема, то корень уравнения =0 является точкой , если 0 и точка , если 0.

При нахождении нулей первой производной используем метод линеаризации, что приводит к итерационному процессу

(*)

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

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

этой параболы достигается в точке, определяемой формулой (*)

если =0, то сходимость медленная, то

Линейное программирование.

Стандартная задача линейного программирования.

max (c1x1+...+cnxn )

a11x1+...+ a1nxn ≤ b1

.............................

am1x1+...+ amnxn ≤ bm

(x1³0, ..., xn³0)

или матричная форма записи:

max (c,x)

Ах≤b, x≥0, где x=(x1,...,xn), c=(c1,...,cn), b=(b1,...,bn).

A=(aij) – матрица коэффициентов.

Вектор С называют вектором коэффициентов линейной формы, b – вектор ограничений.

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

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

max (c1x1+...+cnxn )

a11x1+...+ a1nxn = b1

.............................

am1x1+...+ amnxn = bm

(x1³0, ..., xn³0)

или матричная форма записи:

max (c,x)

Ах=b, x≥0

Основные вычислительные схемы (симплекс-метод и его модификации) решения задач ЛП разработаны именно для канонической задачи.

Общая задача ЛП

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

max (c1x1+...+cnxn )

a11x1+...+ a1nxn ≤ b1

.............................

aк1x1+...+ aкnxn ≤ bк

aк+1x1+...+ aк+1nxn = bк+1

.............................

am1x1+...+ amnxn= bm

(x1³0, ..., xr³0)

здесь k£ m, r£ n.

Ясно, что стандартная задача получается как частный случай общей при k=m, r=n, каноническая – при k=0, r=n.

Линейная форма ‹cx›=c1x1+...+cnxn – подлежащая максимизации (или минимизации) называется целевой функцией. Вектор x=(x1,...,xn), удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором или планом. Задачи ЛП, для которых существуют допустимые вектора, называются допустимой задачей. Допустимый вектор х*, доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором х, т. е. ‹с, х*›≥‹с, х› называется решением задачи или оптимальным планом. Максимальное значение d=‹с, х*› целевой функции называется значением задачи.

Квадратичное программирование.

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

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

или в матричной форме

(1)

где - симметричная положительно определенная nxn матрица

m*n матрица

d-вектор размерности n

b- вектор размерности m

Функция Лагранжа в нашем случае имеет вид:

(2)

при этом седловую точку нужно искать при =0 и свободном . Поэтому признак оптимальности

приводит к условию

или (3)

Левое же неравенство признака оптимальности сводится к допустимости и выполнению условия дополнительности, что означает, что (4)

(5)

Кроме этого множители Лагранжа должны быть неотрицательны.

(6)

Таким образом, если найдем пару (), удовлетворяет условию (3)-(6),то будет решением задачи (1), а - решением соответствующей двойственной задачи.

Метод: Многогранное множество, описываемое системой ограничении задачи (1), разбивается на грани различной размерности (включая внутренность - грань максимальной размерности). Конечная грань состоит из допустимых точек, удовлетворяет некоторой системе уравнений вида: (7)

где-матрица, составленная из строк матрицы А с номерами ,

т. е. .

Аналогично составлен столбец b. Уменьшив, если нужно, множество I, можно считать строки матрицы линейно независимыми. Наличие граней, которых описываются линейной системой (7) с зависимыми уравнениями, мы будем считать вырождением, и конечность метода в этом случае обосновываться не будет.

Так как искомая точка принадлежит (относительной) внутренности некоторой грани, то она должна доставлять минимум нашей квадратичной функции на всем множестве решения системы (7).

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

Намеченная схема корректна лишь для случая положительно-определенной матрицы , т. к. иначе для некоторых множеств I минимум может и не достигать.

Формальное описание метода: Пусть имеется допустимая точка и выделено множество , для которой строки матрицы линейно независимы, а удовлетворяет системе (7).

Возможны следующие случаи:

А) Точка доставляет минимум функций при ограничениях (7). Согласно классическому признаку Лагранжа существуют множители , для которых

или

(8)

В силу независимости строк матрицы равенством (8) вектор определяется однозначно.

Если найденные значения неотрицательны, то определив =0 при , найдём, что при и выполнены все соотношения (3)-(6), так что решение найдено.

Если же при некотором оказалось, что <0, то этот индекс из множества I удаляется и для той же точки мы получаем некоторое множество индексов , т. е. переходим к нашей грани, размерность которой на единицу больше исходной.

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

Алгоритмически это так, положим

(9)

(10)

определив по формуле (11)

положим

при =1, то сместились мы в точку и множество I в дальнейшем сохраним, если же , то номер , на котором реализован минимум (11), мы включим в множество I , т. е. перейдём к нашему множеству индексов .

В обоих случаях точка заменяется на точку

Для нахождения точки нужно решить систему

(12)

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