Методы оптимизации организационно-технических систем

Федеральное агентство по образованию

 

Московский авиационный институт
(государственный технический университет)

 

 

В.Е. Усачов

 

 

Методы оптимизации организационно-технических систем

 

Учебное пособие

 

 

УТВЕРЖДЕНО

на заседании Редсовета Аэрокосмического факультета

14.10.2008г.

ТЕМА 1

 

1. Общая постановка задач оптимизации организационно-технических систем

Любая организационно-техническая система (ОТС) характеризуется рядом количественных показателей, которые определяют качество того или иного варианта ОТС.

Некоторые показатели качества космических комплексов научного назначения:

- а) стоимость космического комплекса (КК), решающего ряд определенных научных задач;

- б) надежность КК (вероятность выполнения заданных космических операций);

- в) продолжительность реализации космической миссии, включая разработку КК, испытания КК, производство КК и собственно выполнение миссии;

- г) научная эффективность того или иного варианта КК.

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

(возможные аргументы критериев качества КК):

В частности, аргументами критериев качества КК являются:

· параметры баллистических схем выведения КА;

· параметры баллистических схем межпланетного полета КА;

· характеристики ракетно-космического комплекса, осуществляющего выведение КА (ракетоносителя, разгонного блока и др…);

· основные характеристики КА и его служебных систем.

В общем случае критерии качества КК моделируются математически в виде целевых функционалов (объект исследования последующих курсов оптимизации). В данном учебном пособии будут рассматриваться только целевые функции - f (x).

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

Где  - параметры (аргументы) целевой функции   f.

И пусть, эта связь полностью определена, т.е. имеет место детерминированная аксиоматика, согласно которой применимы все положения математического анализа [1].

Постановка задачи:

Определить минимум или максимум (экстремум) целевой функции f(x) по ее аргументам - x, допускающим вариации в определенных пределах.

Формально это записывается следующим образом.

,

где X - множество допустимых вариаций вектора x,  определена на множестве X.

Результатом решения этой задачи являются: экстремальные значения целевой функции f* и соответствующие значения вектора аргументов:

.

2. Теоретические основы математического «программирования»

2.1 Основные понятия и определения

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

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

 (),                                                                     (2.1)

где ,

и пусть для любого выполняются условия:

,                                                  (2.2)

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

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

Если неравенство (2.2) выполняется только для точек, принадлежащих -окрестности , , тогда говорят, что в точке  достигается локальным минимумом.

Напоминание

.        (2.3)

Замечание

Если функция  достигает в точке  своего минимума, то функция  в этой же точке достигает своего максимума, т.е.

.

Исходя из этого, в дальнейшем без ограничения общности будут рассматриваться задачи минимизации.

 

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

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

(2.4)

где  - единичный вектор вида , в котором 1 находится на -м месте.

.    (2.5)

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

x 1

Рис.2.1, а)

 

 

 

Рис.2.1, б)

 

Из рис. 2.1, б) видно, что градиент функции grad(f (x)) ортогонален касательной к линиям уровня функции, в частности, к линии f (x) = C ₂.

 

 

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

Гессианом (матрицей Гессе) функции  в точке  называется матрица вторых частных производных:

 .                       (2.6)

Замечание

 

Матрица Гессе является симметрической, т.е:

.

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

Производная функции  в точке  по направлению  называют предел:

 .                                          (2.7)

 

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

Разложение в ряд Тейлора функции  в точке  будет иметь следующий вид:

+… (2.8)

2.2 Необходимое условие минимума целевой функции

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

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

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

Пусть  - локальный минимум , тогда согласно данному определению имеем:

;

и пусть построена некоторая точка  из точки  путем перемещения в направлении

.

Тогда, исходя из определения 2 для  можно записать:

,                                                        (2.9)

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

                                       (2.10)

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

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

2.3 Достаточные условия минимума целевой функции

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

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

Рис 2.2

На рис 2.2, а) изображено выпуклое множество : все точки  произвольного отрезка [ x ⁽¹⁾, x ⁽²⁾] принадлежат множеству , поскольку ,, т.е.  - выпукло. На рис 2.2, б) изображено невыпуклое множество. Поскольку существуют точки , не принадлежащие множеству .

Формально это можно записать следующим образом. Если  - выпукло, то любая точка , принадлежащая отрезку прямой, соединяющей точки  и  является одновременно точкой множества :

                                    (2.11)

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

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

(2.12)

 

 

На рис. 2.3 представлена графическая интерпретация этого неравенства.

 

Рис. 2.3

Определение достаточных условий минимума функции

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

Доказательство (от противного)

Пусть в точке выполняются достаточные условия минимума функции  на множестве .

И пусть существует точка  такая, что , тогда в силу условия выпуклости функции можно записать (см. достаточные условия):

где r – вектор, направленный из точки  в точку .

Исходя из выпуклости , такое направление должно существовать. Условие выпуклости можно записать иначе:

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