Математические модели операций

В математических моделях задаются следующие компоненты:

- х и у- это векторные переменные, соответствующие управляемым и неуправляемым параметрам;

- множество Х допустимых значений векторной переменной х;

- множество У допустимых значений векторной переменной у;

- целевая функция F(x, y), устанавливающая значение критерия эффективности.

(у – характеристики погодных условий, настроение).

Если известно значение y, то математическая модель – детерминированная, иначе – недетерминированная.

Детерминированная модель:

Пусть y принимает значение , нам известное. Введем в этом случае обозначение:

.

Тогда модель может быть записана в виде:

f(x)®min (1)

xÎ X

(Запись означает, что необходимо найти значение векторной переменной xÎ X такое, при котором функция f(x) достигает минимума).

Модель (1) называется задачей оптимизации.

Недетерминированная модель:

Если y является векторной случайной величиной с известной вероятностной мерой, то недетерминированная модель называется стохастическоймоделью. (Под термином “случайное явление” в теории вероятностей принято понимать явление, относящееся к классу повторяемых и, главное, обладающее свойством статистической устойчивости (при повторении средние характеристики стабилизируются).)

Если операция проводится неоднократно и имеет смысл средний результат, то математическая модель имеет следующий вид:

Если операция проводится однократно, либо не имеет смысла средний результат, то модель может принимать вид:

Эти задачи называются задачами стохастической оптимизации.

Если y не является случайной величиной, либо это случайная величина с неизвестной вероятностной мерой, то имеем модель в условияхнеопределенности.

Такая модель может принимать вид:

5. Задачи оптимизации – определения

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

def. Точка называется точкой глобального минимума функции f(x) на множестве X или глобальным решением задачи (1), если

(2)

def. Точка называется точкой локального минимума функции f(x) на множестве X или локальным решением задачи (1), если существует такое , что:

, (3)

где - шар радиуса e с центром в .

def. Если неравенство в (2) или (3) выполняется как строгое при , то говорят, что - точка строго минимума (строгое решение) в глобальном или локальном смысле соответственно.

Задачу максимизации функции f на X будем записывать в виде

f(x)®max (4)

xÎ X

Ясно, что задача (4) эквивалентна задаче

-f(x)®min

xÎ X

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

def. Точная нижняя грань функции f на X, то есть величина

называется значением задачи (1).

Возможны три случая:

a) f*> и f(x*)=f* при некотором x*Î X, то есть значение задачи конечно и достигается, при этом ;

b) и при всех , то есть значение задачи конечно, но не достигается;

c) , то есть значение задачи бесконечно.

В случае a) задача (1) имеет глобальное решение, в случаях b) и c) – не имеет.

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

def. Если X= , то задача (1) называется задачей безусловной оптимизации.

def. Если X - собственное подмножество , то (1) – задача условной оптимизации.

def. Если X определяется соотношением а функции и , являются дифференцируемыми, то (1) – задача классической оптимизации и записывается в виде:

def. Под множеством простой структуры в будем понимать множества типа:

а) неотрицательного октанта:

б) n -мерного параллелепипеда:

в) n -мерного шара.

def. Если X определяется из условия:

где P - множество простой структуры , то (1) – общая задача математического программирования и записывается в виде:

(5)

(6)

(7)

(8)

Рассмотрим также ряд важных определений из теории выпуклых множеств.

def Пусть даны две точки , тогда их выпуклой линейной комбинацией будет любая точка x вида

def Множество выпукло, если оно содержит все выпуклые линейные комбинации любых пар точек .

def Пусть - выпуклое множество.Функция выпукла на , если для любых двух точек

(*)

если , просто говорят, что выпукла.

Грубо говоря, выпуклая функция прогибается вниз.

Так, на рисунке функция f(x) выпукла на отрезке [0, 1] (хорды всегда выше этой функции).

def. Функция вида называется афинной. Если b= 0, то функция f(x) называется линейной.

Любая афинная функция выпукла на любом выпуклом множестве X.

def. Задача (1) называется задачей выпуклой оптимизации, если f(x) – выпуклая функция, а множество X – выпуклое множество.

def. Если в задаче (5)–(8) f(x) – выпуклая функция, - выпуклые функции, – афинные функции, P - выпуклое множество, то задача (5)-(8) – общая задача выпуклого программирования.

def. Если в задаче (5)-(8) f(x) – линейная функция, - афинные функции, P - неотрицательный октант, то (5)-(8) – задача линейного программирования.

def. Если в (5)-(8) f(x) - квадратичная функция, функции - афинные функции, P - неотрицательный октант, то (5)-(8)- задача квадратичного программирования.

def. Если в задаче (5)-(8) множество P - дискретное, то задача (5)- (8) – общая задача дискретного программирования (комбинаторная задача).

def. Если в (5)-(8) являются аддитивными или мультипликативными, то задача (5)-(8) - задача сепарабельногопрограммирования.

аддитивная

мультипликативная