Сущность глобального и локального критериев оптимальности.

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

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

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

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

Сложность системы целей объясняется многообразием задач общественного развития и развития систем, а также тем, насколько обширны и интенсивны внешние связи данной системы.

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

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

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

Векторная оптимизация

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

Пусть X = {x1,…, x N} (j = 1,N) - вектор переменных, обычно предполагается неотрицательность вектора переменных X³0, функциональная взаимосвязь переменных устанавливается определенными соотношениями, на которые накладываются ограничения:

gi (X)£bi (i = 1,M).

Функционирование системы оценивается определенными критериями, записываемыми в виде целевых функций fr(X) (r = 1,K). Множество критериев можно представить в виде векторной целевой функции

F(X) = {f1(X),…>fr(X)}.

Чтобы минимизировать частный критерий fr(X), достаточно максимизировать -fr(X), так как min fr(X)=-max (-fr(X)). Поэтому в дальнейшем предполагается, что каждая компонента векторного критерия максимизируется. Задача многоцелевой оптимизации записывается как векторная задача математического программирования (ВЗМП)

F(X) = {f1(X),…>fr(X)} (max),

gi (X)£bi (i = 1,M),

X³0.

Будем рассматривать ВЗМП для случая, когда точки оптимума X*r(r=1,K), полученные при решении задачи по каждому критерию fr(r=1,K) не совпадают (случай их совпадения встречается крайне редко и такая задача не представляет интереса). Поэтому с математической точки зрения задача является некорректной, так как если один из критериев достигает своего оптимума, то улучшение по другим компонентам векторного критерия невозможно. Отсюда вытекает, что решением ВЗМП может быть только какое-то компромиссное решение.

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

Понятие предпочтительности плана. План X° не хуже плана X`, если

fr(X°)³ fr(X`) (r = 1,K). Если среди этих неравенств хотя бы одно строгое, то план X° предпочтительнее (лучше) X`,т.е. при переходе от X° к X`значение ни одного критерия не ухудшилось и хотя бы одного критерия улучшилось. План X° оптимален по Парето (эффективен), если он допустим и не существует другого плана X`, для которого fr(X°)³ fr(X`) (r = 1,K), и хотя бы для одного критерия выполняется строгое неравенство.

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

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

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

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

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

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

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

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

fr(X) = fr(X),

f*r

или относительными значениями отклонений от оптимальных значений критериев f*r

fr(X) = f*r - fr(X),

f*r

Проблема выбора принципа оптимальности связана с определением свойств оптимального решения и решением вопроса - в каком смысле оптимальное решение превосходит все остальные.

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

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

Решение перечисленных проблем идет в нескольких направлениях. Основные направления:

Методы, основанные на свертывании критериев в единый;

Методы, использующие ограничения на критерии;

Методы целевого программирования;

Методы, основанные на отыскании компромиссного решения;

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

В методах, основанных на свертывании критериев, из локальных критериев формируется один. Наиболее распространенным является метода линейной комбинации частных критериев. Пусть задан вектор весовых коэффициентов критериев a = {a1,…,ar}, характеризующих важность соответствующего критерия, åar = 1, ar ³ 0 (r = 1,K). Линейная скаляризованная функция представляет собой сумму частных критериев, умноженных на весовые коэффициенты. Задача математического программирования становится однокритериальной и имеет вид

F° = åarfr(X) (max),

qi(X) £ bi (I = 1,M),

X ³ 0.

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

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

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

1) метод ведущего критерия;

2) методы последовательного применения критериев (метод последовательных уступок, метод ограничений).

В методе ведущего критерия все целевые функции кроме одной переводятся в разряд ограничений. Пусть g = (g2, g3,…, gк-1) – вектор, компоненты которого представляют собой нижние границы соответствующих критериев. Задача будет иметь вид

F = f1 (max)

fr ³ gr (r = 2,K),

qi (X) £ bi (I = 1,M),

X ³ 0.

Полученное этим методом решение может не быть эффективным, поэтому необходимо проверить его принадлежность области компромиссов.

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

Алгоритм метода последовательных уступок:

1. Критерии нумеруются в порядке убывания важности.

2. Определяется значение f*1. Лицом, принимающим решение, устанавливается величина уступки D1 по этому критерию.

3. Решается задача по критерию f2 с дополнительным ограничением f1(X) ³ f*1 - D1.

Далее пункты 2 и 3 повторяются для критерия f2,…, fk.

Полученное решение не всегда принадлежит области компромиссов.

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

d(F(X), F) = (å w_R êf_R (X) - f _R ê^p) (min),

где F = {f₁,...., f_R} - вектор целевых значений,

W = {w₁,..., w_R} - вектор весов, обычно å w_R = 1_, w_R ³ 0

(r = 1, K), значения p находятся в пределах 1 £ p £ ¥,

d(.) – расстояние (мера отклонения) между F(X) и F.

Во многих случаях применения целевого программирования полагают p = 1. Например, в линейном целевом программировании функции f_R (X) (r=1, K) и q_i (X) (i = 1,M) линейны и нет целочисленных переменных.

В задачах лексикографического программирования критерии строго упорядочены по важности, так что при сравнении пары решений в первую очередь используется критерий f₁ и лучшим считается то решение, для которого значение этого критерия больше, если значения первого критерия для обоих решений оказываются равными, то применяется критерий f₂ и предпочтение отдается тому решению, для которого значение f₂ больше, ели и второй критерий не позволяет определить лучшее решение, то привлекается f₃ и т.д. Учет информации о важности критериев осуществляется путем поэтапного решения задачи минимизации отклонений критериев от целевых значений. Часто в лексикографическом программировании F = F, p = 1.

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