Критерии оптимизации

Классические основы оптимизации

Оптимизация в задачах управления и проектирования

ОСНОВНЫЕ ПОЛОЖЕНИЯ ОПТИМИЗАЦИИ

Оптимизация – это процесс нахождения наилучшего решения задачи, определяемого по некоторому заранее установленному критерию. Другими словами, это целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях.

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

– при проектировании сложных инженерных сооружений и систем;

– в управлении производственными, техническими и экономическими системами;

– в процессах разработки автоматизированных информационных систем и т.д.

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

Поиски оптимальных решений привели к созданию специальных математических методов, и уже в XVIII в. были заложены математические основы оптимизации (вариационное исчисление, численные методы и др.). Однако до второй половины ХХ в. методы оптимизации во многих областях науки и техники применялись редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев – невозможно. Например, большие трудности возникают при решении задач оптимизации процессов в химической технологии из-за большого числа параметров и их сложной взаимосвязи между собой. При наличии ЭВМ задача заметно упрощается.

Постановка задачи оптимизации предполагает существование следующих условий:

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

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

В первом случае критерий оптимизации – производительность, а во втором – себестоимость.

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

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

4. Учет ограничений.

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

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

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

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

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

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

– создание математической модели процесса, которым требуется управлять (объекта управления), и системы управления с обратными связями (контура управления);

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

– разработка (приобретение) системного программно-технического комплекса управляющей информационно-вычислительной системы и средств связи;

– разработка информационного и программного обеспечения.

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

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

– регистровая оптимизация программирования – привязка регистров ЭВМ к переменным и промежуточным результатам, чтобы минимизировать число случаев “холостого” резервирования регистров;

– локальная оптимизация программирования – адаптация программы к конкретным особенностям архитектуры ЭВМ.

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

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

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

Известно, что функция f(x) имеет локальный минимум в точке х₀, если существует некоторая положительная величина d, такая, что если Ѕ х - х₀ Ѕ < d, то f(x) ≥ f(x₀), т.е. если существует окрестность точки x₀, такая, что для всех значении х в этой окрестности f(x) больше f(x₀). Функция f(x) имеет глобальный минимум в точке х*, если для всех х справедливо неравенство f(x) ≥ f(x*).

На рис.1 а дано графическое представление функции f(x), которая имеет локальный минимум в точке x₀ и глобальный минимум в точке х^*.

Рис. 1 а. Локальный и глобальный минимумы

Классический подход к задаче нахождения значений x₀ и х^* состоит в поиске уравнений, которым они должны удовлетворять. Представленная на рис. 1 а функция и ее производные непрерывны, и видно, что в точках x₀ и х^* производная f’(x) (градиент функции) равна нулю. Следовательно, x₀ и х^* будут решениями уравнения

f’(x) = 0.

Точка x_m, в которой достигается локальный максимум, и точка x_с, в которой имеется точка горизонтального перегиба функции, также удовлетворяют этому уравнению. Следовательно, уравнение f’(x) = 0 является только необходимым условием минимума, но не является достаточным условием минимума.

Заметим, однако, что в точках x₀ и х* производная f’(x) меняет знак с отрицательного на положительный. В точке x_m знак меняется с положительного на отрицательный, в то время как в точке x_c он не меняется. Следовательно, производная в минимуме является возрастающей функцией, а поскольку степень возрастания f’(x) измеряется второй производной, можно ожидать, что f”(x₀) >0, f”(x^*) > 0, тогда как f”(x_m) < 0.

Если, однако, вторая производная равна нулю, ситуация остается неопределенной.

Полученные выше результаты могут найти надежное обоснование, если рассмотреть разложение функции f(x) в ряд Тейлора в окрестности точки x₀ (или х^*, или x_m), что требует непрерывности функции f(x) и ее производных:

f(x₀ + h) – f(x₀) = h f’(x₀) + (h² /2!) f”(x₀) +...

Если в точке x₀ достигается минимум, то левая часть уравнения будет неотрицательной для любого достаточно малого h. Следовательно, первая производная f’(x₀) должна быть равна нулю. Это является достаточным условием (см. уравнение f’(x) = 0). Если бы она была положительной, то достаточно малое отрицательное значение h делало бы правую часть

f(x₀ + h) – f(x₀) = h f’(x₀) + (h² /2!) f”(x₀) +...

отрицательной, а если бы она была отрицательной, то достаточно малое положительное значение h делало бы правую часть отрицательной.

Так как всегда h² > 0, то, если f”(x₀) > 0, в точке x₀ достигается минимум. Если f’(x_m) = 0 и f”(x_m) < 0, то из аналогичных соображений в точке x_m достигается максимум. Для определения различия между локальным и глобальным минимумами необходимо сравнить значения функций f(x₀) и f(x^*).

Например, исследуем характер точек перегиба функции

f(x) = х ³ – 2 х ² + х + 1,

так как f’(x) = 3 х ² – 4 х + 1 = 0 и ( 3 х – 1)(х – 1 ) = 0, то х = 1/3 или х = 1.

При х = 1/3 производная f ′ (x) меняет знак с положительного на отрицательный, а при х = 1 – с отрицательного на положительный. Следовательно, в точке х = 1/3 достигается максимум, а в точке х = 1 – минимум.

Этот пример может быть решен более простым способом, если вычислить вторую производную f”(x) = 6 х – 4:

f” (1/3) = – 2, т.е. отрицательна, и при х = 1/3 достигается максимум;

f” (1) = 2, т.е. положительна, и при х = 1 достигается минимум. Неоднозначность, возникающую при f”(x) = 0, можно разрешить, увеличив количество членов в формуле разложения в ряд Тейлора:

f(x ₀ + h) -f(x) = hf’(x ₀ ) + (h ²/2!) f”(x₀) + (h ³/3!) f”’ (x₀) + (h ⁴/4!) f”’’ (x₀) +...

При этом можно сформулировать следующее правило:

“Если функция f(x) и ее производные непрерывны, то точка x ₀ является точкой экстремума (максимума или минимума) тогда и только тогда, когда n четное, где n – порядок первой необращающейся в нуль в точке x ₀ производной. Если f”(x ₀ ) < 0, то в точке x ₀ достигается максимум, если f”(x ₀ ) > 0, то в точке x ₀ достигается минимум”.

Например, найдем точку перегиба функции f(x) = (х – 1)⁶.

f’(x) = 6(х – 1)⁵ = 0 при х = 1.

Первой необращающейся в нуль в точке х = 1 производной будет f ⁶(1) = 6!. Следовательно, функция f(x) имеет минимум в точке х = 1.

Функцию n действительных переменных можно представить как

F(x ₁, x ₂, x ₃ ,..., x _n ).

Точка в n -мерном евклидовом пространстве с координатами x ₁, x ₂, x ₃ ,..., x _n обозначается вектором-столбцом х. Градиент функции, т.е. вектор с компонентами ¶f/¶x₁, ¶f/¶x₂,…, ¶f/¶x_n, обозначается С f (x)или, иногда, g(x). Наиболее распространенные задачи оптимизации заключаются в нахождении минимума (или максимума) функции или функционала. В первом случае находят значение n переменных х₁, х₂,. .., х _n, при которых функция F (х ₁, х ₂,..., х _n) принимает экстремальное значение F = min(max).

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

(1-1)

dF/dx_i = 0, i = 1, 2,..., n.

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

Если функция F(x), где x = (x₁, x₂,..., x_n), помимо переменных x₁, x₂,..., x_n зависит еще (параметрически) от другой переменной λ, то решение для каждого значения λ соотношения (1-1) дает оптимальный закон управления

x (l) = { x₁ (l), x₂ (l) ,…, x_n (l)}.

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

Если одному множеству М значений величины х (х ÎМ) соответствует другое множество N значений величины y, то говорят, что y является функцией х, т.е. y = f(x).

Например, пусть М {1, 4, 9, 8} и N {20, 70,90, 110} и пусть каждому значению x из множества М соответствует одно значение y из множества N. Это – метод задания функции в виде таблиц. Он часто встречается в кибернетике. Аналитически функция может быть задана в виде y = x ², y = sin x.

Если М – множество функций и каждой функции f(x), принадлежащей М{ f(x) Î M}, ставится в соответствие определенное значение величины y из множества N, то говорят, что на множестве М задан функционал.

Например

М {sin x, cos x, tg x, ctg x }

и

N {3, 4, 5, 18}.

Другим примером функционала может служить определенный интеграл

I = I { y(x) } =

Каждой функции y (x) будет соответствовать числовое значение I. Так, при y = x I = 1/2, при y = x ² I = 1/3.

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

I { y }→min(max).

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

(1-2)

I {y} = (x, y, y’)dx.

Нетрудно показать, что запись (1-2) включает в себя функцию. Так, если положить

F (x, y, y’) = f(x) g (t-x),

то

I = f (x) g (t-x)dx = f(x),

при a < t < b.

Аналогично, если положить

F (x, y, y’) = c_i f _i (x) g (t_i-x),

то

I = c_i f _i (t _i).

Иногда считают, что функционал является функцией бесконечного числа переменных. Соответственно, вариационное исчисление можно рассматривать как обобщение методов отыскивания экстремума функции на случай большого или бесконечного числа переменных. Действительно, функцию у(х) в формуле (1-2) можно заменить приближенно ломаной линией (рис. 1) с вершинами y ₀ = y(x₀) = y (a), y ₁ = y(x₀ +Δx), yn = y(x₀ +Δ_nx) = y (b), а интеграл – суммой:

I = F (x_i, y_i(y_i – y_i–1)/ Δ x) Δ x.

Рис. 1. Замена интеграла на сумму

После этого вариационная задача приближенно решается как обычная задача на отыскивание экстремума функции n переменных

I = (y₁, y₂,..., y_n).

Такой вывод использовал для своего основного уравнения вариационного исчисления Эйлер.

Однако большинство задач оптимизации содержит ограничения на исходную функцию. Пусть требуется минимизировать функционал

I = (x, y, y’)dx ® min

при наличии ограничений

j_k (x, y, y’)≤0;

k = 1, 2, 3,..., m,

где φ_k - некоторые функции.

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

(1-3)

F (x₁, x₂,..., x_n) ® min;

j_k (x₁, x₂,..., x_n)≤0,

k = 1, 2, 3,..., m.

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

Следует заметить, что во всех приведенных формулах переменные х и у могут быть векторами:

х = (x₁, x₂,..., x_n);

y = (y₁, y₂,... y_n;

F = (F ₁, F ₂ ,..., F _p).

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

Задачи оптимизации при наличии ограничений, по существу, привели к пересмотру классических методов и созданию новых методов, известных под названием методов программирования. Если в формулах (1-3) все функции линейные, налицо задача линейного программирования. В общем случае эти соотношения определяют задачу нелинейного программирования.

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

Вопрос о выборе критерия оптимизации - один из самых важных в процессах оптимизации, в то же время он один из наиболее сложных, и процесс выбора критерия содержит существенную творческую составляющую. Рассмотрим более подробно требования, которые должны предъявляться к критерию оптимизации.

Критерий оптимизации должен:

- выражаться количественно;

- быть единственным;

- отражать наиболее существенные стороны процесса;

- иметь ясный физический смысл и легко рассчитываться.

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

K_опт. = K(Х₁, Х₂, …, Х_n, Y₁, Y₂,… Y_n, U₁, U₂,… U_n),

где К – критерий оптимизации; Y – выходные параметры; Х – контролируемые входные параметры; U – регулируемые, управляющие параметры.

Так как Y=f (U), то при фиксированных Х можно записать К = К (U_{i ср}.)

При этом всякое изменение значений управляющих параметров двояко сказывается на величине К:

– прямо, т.к. управляющие параметры непосредственно входят в выражение критерия оптимизации;

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

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

Y = φ (X_i,U_i),

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

К = К(X_ср.,U_ср.).

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

– необходим реальный объект;

– необходимо изменять технологический режим в значительных пределах, что не всегда возможно;

– длительность испытаний и сложность обработки данных.

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

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

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

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

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

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

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

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

Критерий среднего квадрата ошибки – требование минимума дисперсии или квадрата ошибки между заданным h(t) и выходным x(t) сигналами системы.

Этот критерий применяется при оценке качества работы автоматизированных систем регулирования и удобен при решении математических задач оптимизации. Требование минимума дисперсии или квадрата ошибки (рис. 2) между заданным (или желаемым) h(t) и выходным х(t) сигналами системы записывается как

e²_ср = [ h(t) - x(t) ]²_ср ® min

и означает большую нежелательность (по сравнению с линейным законом) больших (чем малых) по значению ошибок (рис. 3). Причем, в соответствии с рис.2 h(t) получается из полезного входного сигнала m(t) с помощью заданного оператора x(t), в то время как реальный сигнал x(t) получается из входного сигнала системы s (t) с помощью оператора k(t), который следует найти. При использовании критерия

|e_ср| =|h(t) - x(t)|_ср =min,

где “ср“ означает усреднение по ансамблю, считается, что вред, наносимый ошибкой, пропорционален ее величине.

Рис. 2. Схема определения ошибки автоматической системы регулирования

Рис. 3. Оценка качества управления по величине дисперсии

Средний квадрат ошибки e²_ср - это функционал от ее импульсной переходной функции и для стационарных сигналов и линейной системы имеет вид

e²_ср = R_h(0) - 2(τ)R_hs(τ)dτ+(τ)dτ(τ₁)R_s(τ-τ₁)dτ₁,

где R_h(τ) и R_s(τ) - функции корреляции желаемого h(t) и входного s(t) сигналов, а R_hs(τ) - их взаимная функция корреляции.

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

(τ)(-τ)^zdτ = μ_z, z = 1, 2,..., m,

где μ_z - заданные числа, и задача становится вариационной задачей на условный экстремум.

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

I₁ = [ e ² + T² (de/dt)² ] dt,

где e - ошибка рассогласования в системе (рис. 4).

Рис. 4. Интегральный критерий качества

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

Требованием минимума функционала

I₁ ® min

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

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

(de/dt)² dt,

который по существу включает управление по производной. Дело в том, что при переходе нулевого значения ошибки e производная e^/ принимает большие значения и из-за этого возникают большие переколебания. Наличие второго члена в функционале уменьшает значение производной, способствуя меньшим колебаниям.

Интегральный критерий требует минимума суммарной площади, ограниченной кривыми ошибки, ее производной и осью абсцисс, причем последняя площадь берется с весом Т. Из рис. 4 видно, что эти две кривые “работают” со сдвигом примерно в 90 градусов, и коэффициент Т осуществляет оптимальный баланс между управлением по ошибке и по производной.

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

Этот критерий возник при зарождении вариационного исчисления (первая задача которого – задача о “брахистохроне”, кривой наискорейшего спуска, и была задачей быстродействия) и основное развитие получил при решении военных задач в 60-е гг. XX в., в которых быстродействие является принципиальным фактором.

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

I = (x, y, y’) dx ® min

необходимо положить

F(x, x’, t) =1

и, изменив x ® t, y ® x, y’ ® x’, получить

I ₂ = (x, x’, t) dt = t_k - t₀ → min,

причем t ₀ соответствует начальным координатам процесса, а t _k - конечным.

Наиболее распространено получение оптимального переходного процесса с включением максимального ускорения в начале с последующим переходом на максимальное торможение. В этом случае необходимо только определить момент переключения t_n. Задача максимального быстродействия может возникнуть не обязательно в связи с переходным процессом следящих систем. Если, например, требуется за наименьшее время доставить летательный аппарат с Земли на Луну, то эта задача также сведется к задаче о максимальном быстродействии.

Критерий минимума стоимости в единицу времени – стоимость функционирования совокупности систем массового обслуживания в единицу времени.

Рис. 5. Система, оптимальная по быстродействию

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

C = c ₁ p _ср + c ₂ w _ср,

где p _ср — среднее число свободных приборов; w _ср — среднее число заявок, ожидающих своей очереди; c ₁ и с ₂ — стоимости простоев одного прибора и заявки, соответственно, в единицу времени.

Из-за случайности потока заявок и времени их обслуживания всегда имеется какое-то среднее число простаивающих приборов или ожидающих заявок. Требуется так распределить число приборов по разным системам, чтобы С = min. Такая кибернетическая модель и критерии широко используются при создании оптимальных систем управления в сфере обслуживания, например управления системой гостиниц. В качестве заявок здесь выступают клиенты, в качестве приборов - администраторы. Поток клиентов и время их обслуживания — случайные величины. Плохо, и когда простаивают администраторы, и когда ожидают клиенты. Минимум функционала

C = c ₁ p _ср + c ₂ w _ср

означает оптимальный выбор числа администраторов, основанный на определенной статистике потока клиентов. Для решения задачи должны быть известны значения стоимости простоя клиентов и администраторов. Величины p _ср и w _ср являются функциями числа приборов на отдельных участках.

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

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

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

Рис. 6. Сетевой граф комплекса работ

Узел графа обозначает конец одной работы и начало другой. Дуга, или ребро, графа - работа, а длина ребра пропорциональна времени выполнения работы. Пусть длительность выполнения отдельной работы

t _ij = t _j - t _i,

где t _i и t _j — моменты времени, соответствующие началу и концу работы.

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

t_кр = ® max.

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

I = t _кр ® min

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

min max =?,

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

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

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

|| a _ij||,

где i= 1, 2,..., m; j = 1, 2,..., n.

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

min max a_ij =?

i j

Нетрудно убедиться, что если поменять знаки а_ij на обратные, а это физически означает замену проигрыша нашей стороны на выигрыш, то будет решаться максиминная задача

max min (-а_ij) =?

i j

В некоторых задачах, имеющих так называемую седловую точку,

min max a_ij = max min a_ij.

i j i j

Дата добавления: 2014-01-04