Основные виды задач математического программирования. Линейное, квадратичное, выпуклое программирование

// Чёрным-основное. Синим-то, что может понадобиться.

Задачи оптимизации(ЗО)

Постановка ЗО:

Пусть требуется найти точки min или max функции f(x) на некотором множестве D.

Условимся записывать задачу на min в виде:

(1) //задача минимизации

и будем называть
f(x)-целевой функцией,

D-допустимое множество,
а любой элемент - допустимой точкой задачи (1).

Задача (1) представляет собой общую постановку ЗО.

Задача на max функции:
(2) //задача максимизации

/*Опр

Точка называется:
1)точкой глобального минимума[максимума] f(x) на D или глобальным решением задачи (1), если
(*)

2)точкой локального минимума[максимума] f(x) на D или локальным решением задачи (1), если

, (**)

где // шар радиуса с центром в точке

Если неравенство в (*) или (**) строгое, то -точка строгого минимума[максимума] в глобальном или локальном смысле.

Тот факт, что -точка глобального минимума [максимума] f(x) на D, будем записывать в виде:

[ ]

или [ ]

Решение задач (1) и (2), т.е. точки min и max функции f(x) на D также называют точками экстремума, а задачи (1) и (2) –экстремальные задачи.

Задача (2)~задаче(1), если её представить как . Это позволяет переписать решения, полученные для задачи минимизации на задачи максимизации и наоборот.*/
Существуют задачи безусловной и условной оптимизации.

Опр Задача вида наз. задачей безусловной оптимизации, т.к. в ней отсутствует ограничение на аргумент x.

Опр Задача вида з. задачей условной оптимизации. //

/*Геометрическое решение задачи условной оптимизации строится на понятии линии уровня.

Опр Множество вида наз. линией(поверхностью) уровня*/

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

Опр Важнейший класс задач условной оптимизации вида:

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

Условие наз. ограничениями-неравенствами, а ограничениями-равенствами.

Условие означает прямое ограничение на координаты вектора x.

Обычно в качестве множества X берется множество простой структуры .

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

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

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

задачи динамического программирования. //это видимо писать ненадо, но оно как бы есть J

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

· Задача линейного программирования(ЛП)

Опр Задачей ЛП наз. задача оптимизации(минимизации) линейной функции при линейных ограничениях.

Существуют различные формы записи задач ЛП.(Р/м наиболее часто применимые)

Опр Задача ЛП вида

наз. общей.

Опр Задача ЛП вида

наз. основной.

Опр Задача ЛП вида

наз. стандартной.

Опр Задача ЛП вида

наз. канонической.

/*Достаточно часто используется векторно-матричная форма записи этих задач. Например, задачу ЛП в основной форме можно представить в виде:

,

*/

Р/м геометрическую интерпретацию задач ЛП. В качестве примера выберем задачи ЛП в основной форме.

В этой задаче допустимое множество представляет собой полиэдр:

,

образованный пересечением полупространств:

,

где -нормаль, а является гиперплоскостью с нормалью .

Линии уровня образуют семейство параллельных гиперплоскостей

//формула м.б. не та! (и опять же )

Р/м рис.:

		Не будет решения

с

с

с

с

с

рис1 рис2 рис3

Градиент целевой функции задачи ЛП равен , а значит постоянен и является нормалью каждой из гиперплоскостей. Поиск решений задачи минимизации сводится к нахождению min числа , причем такого, что гиперплоскость имеет непустое пересечение с D.

- Тогда множество является множеством решений задачи ЛП.

Решения задачи ЛП м.б. одно(рис1), их м.б.. множество(рис2) или не быть ни одного(рис3).

Характерная особенность: если решение задачи ЛП , то оно достигается обязательно на границе.

· Задача квадратичного программирования

Задача квадратичного программирования(КП) представляет собой задачу с линейными ограничениями и квадратичной целевой функцией.

Опр Задачей КП наз. задача минимизации квадратичной целевой функции

,

где ,

,

C-симметричная матрица ,

A-матрица .

· Задача выпуклого программирования

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

Опр(яновский) Задачей ВП наз. задача вида , где

множество и функции - линейны,

а функции -выпуклы.

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

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

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

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

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

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

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////на всякий случай
Функция f(X), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек

X₁, X₂ ∈ X и любого λ, 0≤λ≤1, справедливо неравенство

f(X) ≤ λf(X₁)+(1-λ)f(X₂), (4.2)

где X= λX₁+(1-λ)X₂.

ВОПРОС 22 (2)