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

ВВЕДЕНИЕ В ОПТИМИЗАЦИЮ

ВВЕДЕНИЕ

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

Методы оптимизации = математическое программирование.

Пример: планирование производства.

Пусть имеется предприятие, выпускающее некоторый продукт, где используется n-ресурсов.

где X – вектор ресурсов,

y – количество выпускаемой продукции,

f – производственная функция.

где p – вектор цен ресурсов,

– сумма затрат на ресурсы.

Если предприятие имеет денежные ресурсы в размере β, то возможны 2 постановки задачи:

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

2. Минимизируются затраты, при условии, что объем выпуска не менее заданной величины.

f₀ – заданный объем выпуска.

Задача оптимизации формулируется следующим образом: задано множество Х (допустимое множество задачи) и функция f(x) (целевая функция), определенная на Х; требуется найти точки минимума или максимумам функции f на X.

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

(1.1)

где f(x) – целевая функция,

X – допустимое множество,

х – допустимая точка (вектор).

(R ⁿ – n –мерное Евклидово пространство).

Задачи оптимизации называются задачами безусловной оптимизации, если

Задачи оптимизации называются задачами условной оптимизации, если .

Наиболее общий способ задания допустимого множества Х:

При таком способе задача (1.1) записывается следующим образом:

(1.2)

функциональные – ограничение неравенства ограничения – ограничение равенства

– прямое ограничение

При необходимости можно заменить на и

Определение решения задачи оптимизации (1.1).

Точканазывается точкой глобального минимума f(x) на множестве Х, или глобальным решением задачи (1.1), если выполняется:

(1.3)

Точка называется точкой локального минимума f(x) на множестве Х, или локальным решением задачи (1.1), если при некотором достаточно малом выполняется

(1.4)

где

Если выполняется (1.3), то выполняется (1.4), но не наоборот.

По аналогии с (1.1) можно записать:

(1.5)

Для этого необходимо в (1.3) и (1.4) поменять знаки их решений.

(1.1) и (1.5) – экстремальные задачи, а их точки называются экстремальными точками.

Чтобы от задачи максимизации (1.5) перейти к задаче минимизации (1.4):

При условии, что локальные и глобальные решения совпадают.

Если нашли точки, то решением является – значение функции в точке.

Это говорит о том, что функция достигает локального или глобального минимума.

Существование решения оптимизационных задач.

Если X допустимое ограниченное множество, то можно найти решения методом перебора.

Рассмотрим случаи, когда решений нет:

1)

Допустимое множество Х неограничено.

2)

Допустимое множество Х ограничено, но не замкнуто.

3)

Допустимое множество Х ограничено, замкнуто, но прерывается асимптотой (имеет разрыв в точке с).