Векторная оптимизация с равнозначными критериями и с заданным приоритетом критерия в моделировании технических систем

Размещено на http://www.allbest.ru/

Векторная оптимизация с равнозначными критериями и с заданным приоритетом критерия в моделировании технических систем



Введение

Представлена новая технология (методология) моделирования технической системы (ТС), базирующаяся на решении задач векторной оптимизации с равнозначными критериями и с заданным приоритетом критерия в условиях определенности и неопределенности. Выполнено построение модели ТС в виде векторной задачей математического программирования (ВЗМП). Представлена теория и методы решения ВЗМП с равнозначными критериями и с заданным приоритетом критерия, как математический аппарат моделирования ТС в условиях определенности и неопределенности. Исследовалась проблема размерности модели ТС, при ее решении и геометрической интерпретации используются методы решения ВЗМП с приоритетом критерия. Методология построения, методы решения ВЗМП и принятие оптимального решения демонстрируются на тестовом примере моделирования ТС в системе Matlab.

При исследовании и моделировании новых технических объектов, систем (ТС), модель которых представлена векторной задачей математического программирования (ВЗМП) [10], возникает проблема оценки результатов моделирования и принятия оптимального решения на их основе [7 - 8,10,11,12]. Проблеме - оптимального принятия решений при моделировании ТС, как в условиях определенности, так и неопределенности уделяется достаточно большое внимание в отечественной науке, начиная с работ Ю.Б. Гермейера [1] в МГУ им. М.В. Ломоносова и ведущих научных школ АН СССР - РАН [4-7, 13, 14], внесших большой вклад в решение важных научно-технических задач, и в зарубежной научной деятельности в теоретических [15-17] и прикладных аспектах [3, 17-19].

Математическая модель технической системы, как правило, учитывает некоторый набор параметров и характеристик ТС, которые функционально зависят от этих параметров [10, 11, 12]. При построении модели ТС возникает ряд проблем, связанных, во-первых, условиями определенности и неопределенности, и, во-вторых, проблемой размерности параметров и ее геометрической интерпретацией. Если известна функциональная зависимость характеристик ТС от этих параметров, то построение такой модели осуществляется в условиях определенности, при этом используются методы [7, 9]. Когда не известна функциональная зависимость характеристик ТС от её параметров, построение модели ТС осуществляются в условиях неопределенности. При этом используются экспериментальные данные по принципу «вход-выход», на основе которых строятся регрессионные модели. Построение моделей в условиях неопределенности в виде задачи векторной оптимизации показано в [10, 11]. В [12] выполнено построение математической модель технической системы модели условиях определенности и неопределенности в совокупности.

Проблема размерности возникает при практической реализации решения задачи векторной оптимизации, когда количество параметров ТС больше двух и геометрической интерпретацией результатов решения. В работах [10, 11, 12] эта проблема достаточно успешно решалась при равнозначных критериях в двухмерной системе координат, где на соответствующих рисунках представлены оптимальные параметры и характеристики в относительных единицах. При количестве параметров больше двух при геометрической интерпретации необходим переход из N-мерного в двухмерное пространство. Такой переход в настоящее время достаточно хорошо отработан - графически это можно представить в системе Matlab, с некоторой ошибкой аппроксимации.

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

Цель данной работы - представление методологии математического моделирования ТС, построенной в виде векторной задачи математического программирования (ВЗМП) в условиях определенности и неопределенности в совокупности. Представления конструктивных методов векторной оптимизации при равнозначных критериях, и заданном приоритете критерия. Геометрической интерпретации и расчет оптимальных параметров ТС путем решения ВЗМП с приоритетом критерия, т. е. принятие оптимального решения. Демонстрация методологии на численном примере модели ТС.

Для реализации поставленной цели в работе показано построение модели технической системы в виде ВЗМП в условиях определенности и неопределенности в совокупности [10, 11, 12]. Теория и конструктивные методы решения ВЗМП, основанные на нормализации критериев, принципе гарантированного результата, позволяющие решать ВЗМП при равнозначных критериях и приоритете критерия, [7, 9] при равнозначных критериях и заданном приоритете критерия. Геометрическая интерпретация и анализ результатов решения ВЗМП в N-мерной системе координат, т. е. решение с количеством параметров ТС три и больше. Методология в совокупности с регрессионным анализом и методами решения ВЗМП представляет новую информационную технологию оптимального выбора и принятия решения в условиях определенности и неопределенности с количеством параметров больше двух. Методология проиллюстрирована на численном модельном примере ТС в условиях неопределенности и реализована в системе Matlab [2].



1. Постановка проблемы. Построение математической модели технической системы в условиях определенности и неопределенности в совокупности

математический программирование технический

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

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

построение математической модели технической системы в условиях определенности и неопределенности в совокупности;

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

1.1 Построение общей математической модели технической системы

Рассматривается техническая система, функционирование которой определяется набором (вектором) К технических характеристик:

F(X) = (f₁(X) f₂(X) … (X) )^T,



каждая компонента которого функционально зависят от N конструктивных параметров Х=(х₁ х₂ … х_N)^T. Каждый параметр лежит в заданных пределах:

х x_j x, j = , или X^minXX^max,

где х, x,jN - нижний и верхний пределы изменения вектора параметров ТС, N - множество индексов параметров. Множество характеристик (критериев) К подразделяется на два подмножества K₁ и K₂: К=K₁K₂. K₁ - это подмножество технических характеристик, числовые величины которых желательно получить, как можно выше: f_k(X) max, k=. K₂ - это подмножества технических характеристик, числовые величины которых желательно получить, как можно ниже: f_k(X) min, k=, K₂?, [10, 11, 12]. Демонстрируемый ниже метод инвариантен к такому разбиению. Математическую модель технической системы, решающую в целом проблему выбора оптимального проектного решения (оптимальных параметров ТС), представим в виде векторной задачи математического программирования.

Opt F(X) = {max F₁(X) = {max f_k(X), k =}

min F₂(X) = {min f_k(X), k =}},

G(X)0, X^minXX^max,

где G(X)=(g₁(X) g₂(X) … g_M (X))^T - вектор-функция ограничений, накладываемых на функционирование ТС. Они определяются протекающими в ней технологическими, физическими и тому подобными процессами и могут быть представлены функциональными ограничениями, например



f f_k(X) f, k=.

Предполагается, что функции f_k(X), k= дифференцируемы и выпуклы, g_i(X), i=непрерывны, а заданное ограничениями (1.5) множество допустимых точек S не пусто и представляет собой компакт:

S={XR^N | G(X)0, X^minXX^max}?.

Соотношения (1.2)-(1.4) образуют математическую модель ТС. Требуется найти такой вектор параметров Х^oS, при котором каждая компонента вектор - функции F(X) принимает минимальное значение. Для решения такого класса ВЗМП в данной статье используются методы, основанные на нормализации критериев и принципе гарантированного результата [7, 9].

1.2 Построение математической модели технической системы в условиях определенности и неопределенности

В [10, 11, 12] показано, что при построении модели ТС (1.3)-(1.5) возможны два варианта:

· первый, когда известна функциональная зависимость каждой характеристики вектор - функции F(X) (1.1)-(1.2) и ограничений, накладываемых на функционирование ТС, (1.3) от всех параметров ТС, которая связана, как правило, с физическими, технологическими процессами, протекающими в ТС, - такую модель принято называть моделью ТС, в условиях определенности;



Opt F(X)={max F1(X)={max fk(X), k =}, min F2(X)={min fk(X), k =}} (1.6)

при ограничениях f f_k(X) f, k=, x x_j x, j =. (1.7)

Задача (1.6)-(1.7) адекватна задачи (1.3)-(1.5)

· второй вариант, когда нет достаточной информации о функциональной зависимости каждой характеристики и ограничений от параметров ТС, - отсюда моделирование ТС в условиях неопределенности. В этом случае проводятся экспериментальные исследования по принципу «вход-выход» и формируется задача принятия решений в условиях неопределенности [3] и возникает проблема выбора оптимальной оценки на основе полученных данных:

I ==, или I = (1.8)

где каждая альтернатива {a_i, i=}, представлена: конструктивными параметрами системы: X={X_i ={x_ij, j=}, i=} - (они также называются «параметрами, характеризующими состояние ТС»), N - множество параметров системы; множеством K показателей: {f(X_i), … , f(X_i)}, i=, k=, M -множество альтернатив.

Задача лица, принимающего решение (ЛПР), состоит: из множества данных I выбрать такую альтернативу iМ, с соответствующим набором конструктивных параметров системы: X_i={x_j, j=}, которая позволила бы получить «в наибольшей мере устраивающий его результат»: f_k(X_i), k=, [3].

Множество характеристик (критериев) К также подразделяется на два подмножества технических характеристик K₁ и K₂, числовые величины которых желательно получить, как можно выше и ниже: К=K₁K₂. [10,12]. Такую целенаправленность представим векторной задачей в условиях неопределенности в следующем виде:

Opt F(X) = {max I₁(X) {max{f_k(X_i, i=)}^T, k=},

min I₂(X) {min{f_k(X_i, i=)}^T, k

при ограничениях f f_k(X) f, k=,

x x_j x, j =,

где Х - вектор управляемых переменных (конструктивных параметров) эквивалентный (1.2); F(X)={I₁(X), I₂(X)} - векторный критерий, каждая компонента которого представляет характеристику технической системы (1.1), функционально зависящую от величины дискретного значения вектора переменных X; M - множество дискретных значений вектора переменных X; (1.11) f f_k(X) f, k= - вектор-функция ограничений, накладываемая на функционирование ТС; (1.12) x x_j x, j = - параметрические ограничения.

Дискуссия. Используя обозначения (1.9), (1.10), можно дать некоторую оценку размерности неопределенности. Если N - множество компонент вектора переменных Х равно M - множеству дискретных значений вектора переменных X, то неопределенность линейная (например, N = M =2, или N = M =3 и т. д.). (Так как в двух мерном R^N=2 пространстве можно провести линию, в трех мерном R³ - плоскость и т.д.). Если N < M , то неопределенность является нелинейной. Если N > M , то неопределенность является полной. (Например, в трехмерном пространстве R³ через две точки можно провести бесконечное множество плоскостей). В общем случае, чем больше измерений M , тем определенность больше. Полная определенность наступает, когда известна функциональная зависимость f(X). В этом случае множество точек X бесконечно.

Точность измерений представляет вторую сторону неопределенности. В этой работе точность не исследуется.

1.3 Построение математической модели технической системы в условиях определенности и неопределенности в совокупности

В реальной жизни условия определенности и неопределенности совмещаются. Модель технической системы так же должна отражать эти условия. Объединим модели (1.6)-(1.7) и (1.9)-(1.11). В итоге получим модель технической системы в условиях определенности и неопределенности в совокупности:

Opt F(X) = {max F₁(X) = {max f_k(X), k =},

max I₁(X) {max{f_k(X_i, i=)}^T, k=},

min F₂(X) = {min f_k(X), k =},

min I₂(X) {min{f_k(X_i, i=)}^T, k=}},

при ограничениях f f_k(X) f, k=

x x_j x, j =,

где Х - вектор управляемых переменных (параметров) эквивалентный (1.2);

F(X)={F₁(X) F₂(X) I₁(X), I₂(X)} - векторный критерий, каждая компонента которого представляет вектор критериев (характеристик) технической системы (1.1), которые функционально зависят от дискретных значений вектора переменных X, где K, K (definiteness), K, K (uncertainty) множество критериев max и min сформированные в условиях определенности и определенности;

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

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

Техническая система, в которой экспериментальные данные представлены в виде матрицы (1.8), рассматривается в следующих обозначениях:

I= , или I=|X Y|, (1.17)

где: X={X_i ={x_ij, j=}, i=} - конструктивные параметры технической системы, N - множество параметров системы, M -множество альтернатив (экспериментов); Y={y_ik, k=, i=}, K - множество критериев (характеристик), по которым оценивается каждая альтернатива.

Построение вектор - функции (критериев) осуществляется по методу наименьших квадратов, где y_i, i= - реально наблюдаемые величины, и , i= их оценки, полученные для однофакторной модели с помощью функции = f(X_i,А), X_i ={x _i}.

В качестве функции = f(x_i, А) используем полином N-1 степени, который для i-го наблюдения (x_i, y_i) примет вид

= f(А, x_i)= a₀+a₁x+a₂x²+…+ a_N-1x ^N-1 , (1.18)

x - точки (узлы) интерполяции, А={a₀, a₁ , a₂ ,…, a_N-1} - коэффициенты.

В прикладной части работы используется уравнение, определяющее зависимость = f(X_i,А) от пяти факторов X_i ={х_1i , х_2i , х_3i, х_4i, х_5i, i=}. В этом случае функция по методу наименьших квадратов примет вид:

, (1.19)

где A={a₀, a₁, a₂, a₃, a₄, a₅} - вектор переменных, который следует определить. Минимум функционала f(А,X) достигается в той точке A={a₀, …, a₅}, в которой частные производные равны нулю:

, … , . (1.20)

Получим систему из шести линейных уравнений:

, (1.21)

,

,

,



,

. (1.22)

В результате решения этой системы линейных уравнений получим величины неизвестных: a₀, a₁, a₂, a₃, a₄, a₅, которые:

во-первых, определяют уравнение регрессии:

_i=a₀+a₁x_1i+a₂x_2i+a₃x_3i+a₄x_4i+a₅x_5i, i= (1.23)

и, во-вторых, уравнение (1.23) можно использовать в однофакторной нелинейной модели, формируя полином пятой степени:

_i=a₀+a₁x_1i+a₂x_1i^2+a₃x_1i^3+a₄x_1i^4+a₅x_1i^5, i=, (1.24)

а также промежуточные состояния: например х₁ и х₂ представлены полиномом второй степени и т. п.:

_i=a₀+a₁x_1i+a₂x_1i^2+a₃x_2i+a₄x_2i^2+a₅x_3i, i=, (1.25)

Результат: Исходные данные {{f_k(X_i, i=}^T, k=}, {f_k(X_i, i=}^T, k=}} в задачах принятия решения в условиях неопределенности (1.9), (1.11) и (1.13), (1.14) преобразованы функции f_k(X) , k=, f_k(X), k=, с соответствующей ошибкой аппроксимации. В итоге векторная задача (1.13)-(1.16) преобразуется в векторную задачу в условиях определенности:



Opt F(X) = {max F₁(X) = {max f_k(X), k =}, (1.26)

min F₂(X) = {min f_k(X), k =}}, (1.27)

при ограничениях f f_k(X) f, k=, x x_j x, j =, (1.28)

где F(X)={f_k(X), k=} - векторный критерий, каждая компонента которого представляет характеристику технической системы, функционально зависящую от вектора переменных X; подмножество критериев

K₁= KUK, K₂= KUK.

Для решения векторной задачи (1.26)-(1.28) используется метод, основанный на нормализации критериев и принципе гарантированного результата.

Реализация обоих вариантов в условиях определенности и неопределенности при равнозначных критериях показана в [10, 11,12], но в реальной жизни не всегда критерии равнозначны, и некоторые из них могут быть более важными, чем другие. Отсюда возникает векторная задача математического программирования с приоритетом критерия. Теоретическое (аксиоматика) и практическое (алгоритмы) обоснование решения векторных задач оптимизация с равнозначными критериями и с заданным приоритетом критериев ниже представлено.



2. Векторная оптимизация с равнозначными критериями, с заданным приоритетом критериев в задачах моделирования технических систем

2.1 Аксиоматика векторной оптимизации с равнозначными критериями

В настоящее время теоретические исследования и методы решения задач векторной оптимизации проводились по следующим направлениям: методы решения векторных задач, основанные на свертывании критериев; использующие ограничения на критерии; методы целевого программирования; методы, основанные на отыскании компромиссного решения и на человеко-машинных процедурах принятия решения. Анализ перечисленных методов показан путем сравнения результатов решения тестового примера, полученного по этим методам, с методом, основанным на нормализации критериев и принципе гарантированного результата еще в [7]. Концептуальная трудность решения векторных задач состоит в определении «Что значит решить векторную задачу?». Это означает необходимо сформулировать аксиоматику, определяющую, в чем одно решение векторной задачи лучше другого. И из этой аксиоматики выводим принцип оптимальности и последующие конструктивные алгоритмы решения.

Определение 1. Критерии в ВЗМП (1.26)-(1.28) являются нормализованными, если выполняется следующее равенство:

_k(X) =, k K, (2.1)

где _k(X), kK - относительная оценка точки XS по k-му критерию; f_k(X) - величина k-го критерия в точке X S; f - величина k-го критерия в точке оптимума X, полученной при решении ВЗМП (1.26)-(1.28) отдельно по k-му критерию; f- наихудшая величина k-го критерия (антиоптимум) в точке X (верхний индекс 0 - ноль) на допустимом множестве S в ВЗМП (1.26)-(1.28); в задаче на max (1.26),(1.28) величина f является наименьшим значением k-го критерия: f=f_k(X) kK₁, а в задаче (1.27),(1.28) на min f является наибольшим: f=f_k(X) kK₂.

Аксиома 1. (О равенстве и равнозначности критериев в допустимой точке векторной задачи математического программирования)

В векторной задаче два критерия с индексами kK, qK будем считать равными в точке ХS, если относительные оценки по k-му и q-му критерию равны между собой в этой точке, т. е. _k(X) = _q(X), k, q K.

Критерии будем считать равнозначными в векторной задаче, если в точке XS при сравнении по числовой величине относительных оценок _k(X), k=, между собой, на каждый критерий f_k(X), k=, и, соответственно, относительные оценки _k(X), не накладывается условий о приоритетах критериев.

Определение 2 Относительный уровень в векторной задаче представляет нижнюю оценку точки XS среди всех относительных оценок _k(X), k =:

XS _k(X), k =, (2.2)

нижний уровень для выполнения условия (2.2) в допустимой точке XS определяется формулой

XS = _k(X). (2.3)



Соотношения (2.2) и (2.3) являются взаимосвязанными. Они служат переходом от операции (2.3) определения min к ограничениям (2.2) и наоборот.

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

Определение 3. (Принцип оптимальности при равнозначных критериях).

Векторная задача математического программирования при равнозначных критериях решена, если найдена точка X^oS и максимальный уровень ^o (верхний индекс o - оптимум) среди всех относительных оценок такой, что

^o= _k(X). (2.4)

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

^o = , (2.5)

_k(X), k=. (2.6)

Полученную задачу (2.5)-(2.6) назовем -задачей. -задача (2.5)-(2.6) имеет (N+1) размерность, как следствие результат решения -задачи (2.5)-(2.6) представляет собой оптимальный вектор X^оR^N+1, (N+1)-я компонента которого суть величина ^o, т. е. X^o={x, x, ..., x, x}, при этом x= ^o, и (N+1)-я компонента вектора X^o выделена в виду ее специфики.

Полученная пара {^o, X^o}=X^о характеризует оптимальное решение -задачи (2.5)-(2.6) и векторную задачу математического программирования (1.26)-(1.28) с равнозначными критериями, решенную на основе нормализации критериев и принципе гарантированного результата, т.е. точка X^о оптимальна по Парето. Назовем в оптимальном решении X^о={X^o, ^o}, X^o - оптимальной точкой, а ^o - максимальным уровнем.

Важным результатом алгоритма решения векторной задачи (1.26)-(1.28) при равнозначных критериях является представленная ниже теорема.

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

В выпуклой векторной задачи математического программирования при эквивалентных критериях, которая решена на основе нормализации критериев и принципа гарантированного результата, в оптимальной точке X^o={^o, X^o} всегда имеется два критерия - обозначим их индексами qK, pK (которые в каком-то смысле являются самыми противоречивыми из множества критериев k = ), для которой выполняется равенство:

^o = _q(X^o) = _p(X^o), q, p K, X S, (2.7)

а другие критерии определяются неравенством:

^o _k(X^o) k K, q p k. (2.8)



2.2 Алгоритм решения векторной задачи при равнозначных критериях (Алгоритм Хоменюка В.В., Машунина Ю.К. [7]).

Конструктивный алгоритм решения векторной задачи (1.26)-(1.28) при равнозначных критериях вытекает из аксиомы 1 и принципа оптимальности 1. Мы представим его в виде ряда шагов:

Шаг 1. Решается задача (1.26)-(1.28) по каждому критерию отдельно, т.е. для k K₁ решается на максимум, а для k K₂ решается на минимум. В результате решения получим: X- точка оптимума по соответствующему критерию, k=; f=f_k(X) - величина k-го критерия в этой точке, k=.

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

Шаг 2. Определяем наихудшую величину каждого критерия (антиоптимум): f, k=. Для чего решается задача (1.26), (1.28) для каждого критерия k = ₁ на минимум: f= min f_k(X), G(X) B, X 0, k = ₁.

Решается задача (1.27), (1.28) для каждого критерия на максимум:

В результате решения получим: X={x_j, j=} - точка оптимума по соответствующему критерию, k=; f=f_k(X) - величина k-го критерия в точке, X, k=.

Шаг 3. Выполняется системный анализ множества точек, оптимальных по Парето, для этого в оптимальных точках X ^*={X, k=} определяются величины целевых функций F(X)= и относительных оценок



(X)=, _q(X) =, q,k K,:

F(X^*)=, (X^*)=. (2.9)

В целом по задаче относительная оценка _k(X), k= kК лежит в пределах 0 _k(X) 1kК.

Шаг 4. Построение -задачи осуществляется в два этапа. На первом, для построения максиминной задача оптимизации мы используем определение 1. Относительный уровень определяется по формуле: XS =_k(X). Мы получили нижний уровень , который максимизировали по XS. В итоге построили максиминную задачу оптимизации с нормализованными критериями:

^o= _k(X). (2.10)

На втором этапе задача (2.10) преобразуется в стандартную задачу математического программирования, названную -задача:

^o = max , (2.11)

- 0, k = , (2.12)

G(X) B, X 0, (2.13)

где вектор неизвестных X имеет размерность N+1: X={, x₁, … , x_N}.

Шаг 5. Решение -задачи.

-задача (2.11)-(2.13) - это стандартная задача выпуклого программирования и для ее решения используются стандартные методы.

В результате решения -задачи получаем: X^o={^o, X^o} - точку оптимума; f_k(X^o), k= - величины критериев в этой точке;

_k(X^o) =, k= - величины относительных оценок;

^o - максимальную относительную оценку, которая является максимальным нижним уровнем для всех относительных оценок _k(X^o), или гарантированным результатом в относительных единицах, ^o гарантирует, что в точке X^o все относительные оценки _k(X^o) больше или равны ^o, _k(X^o)^o, k= или

^o - _k(X^o) 0, k=. (2.14)

Из теоремы 3 [9] вытекает, что точка X^o={^o, x₁,…, x_N} оптимальна по Парето

2.3 Аксиоматика векторной оптимизации с приоритетом критерия

Для разработки методов решения задач векторной оптимизации с приоритетом критерия введем определения: приоритет одного критерия ВЗМП над другими; числовое выражение приоритета; заданный приоритет критерия; нижний (минимальный) уровень от всех критериев с приоритетом одного из них; о подмножестве точек, приоритетных по критерию (Аксиома 2); принцип оптимальности решения задач векторной оптимизации с заданным приоритетом одного из критериев и связанные с ними теоремы. Подробнее см. [7, 9].

Определение 4. Критерий qK в ВЗМП в точке XS имеет приоритет над другими критериями k = , если относительная оценка _q(X) по этому критерию больше или равна относительных оценок других критериев_k(X):

_q(X) _k(X), k = ,

и строгий приоритет, если хотя бы для одного критерия tK,

_q(X) > _t(X), tq,

а для остальных критериев _q(X) _k(X), k=, ktq.

Введением определения приоритета критерия в ВЗМП выполнено переопределение раннего понятия приоритета. Если раньше в него вкладывалось интуитивное понятие о важности этого критерия, то сейчас эта “важность” определяется математическим понятием: чем больше относительная оценка q-го критерия над другими, тем он важнее (приоритетнее), и наиболее высокий приоритет в точке оптимума X, q K .

Из определения приоритета критерия qK в ВЗМП вытекает, что можно выявить множество точек S_qS, которое характеризуется тем, что _q(X)_k(X) kq XS_q. Но ответ на вопрос о том, насколько критерий qK в этой или иной точке множества S_q приоритетнее остальных, остается открытым.

Для выяснения этого вопроса введем коэффициент связи между парой относительных оценок q и k, которые в совокупности представляют вектор:

P^q(X) = {p(X) k=} qK XS_q.

Определение 5. В ВЗМП с приоритетом критерия q-го над другими критериями k = , для XS_q, вектор P^q(X), каждая компонента которого показывает во сколько раз относительная оценка _q(X), qK, больше остальных относительных оценок _k(X), k=, назовем числовым выражением приоритета q-го критерия над остальными критериями k = , т. е.

P^q(X) = , (2.15)

p(X) 1, X S_q S, k=, q K .

Определение 6. В ВЗМП с приоритетом критерия qK для XS вектор P^q={p, k=}, считается заданным лицом, принимающим решения, (ЛПР), если задана каждая компонента этого вектора. Заданная ЛПР компонента p, с точки зрения ЛПР, показывает во сколько раз относительная оценка _q(X), qK больше остальных относительных оценок _k(X), k = . Вектор p, k = является заданным числовым выражением приоритета q-го критерия над остальными критериями k=:

p, k = , q K , (2.16)

p 1, X S_q S, k=, q K.

ВЗМП, в которых задан приоритет какого-либо из критериев, называют ВЗМП с заданным приоритетом критерия.

Проблема задания вектора приоритетов возникает тогда, когда следует определить точку X^o S по заданному вектору приоритетов.

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

Определение 7. Уровень является нижним среди всех относительных оценок с приоритетом критерия q K , таким, что

p_k(X), k=, q K , X S_q S; (2.17)

нижний уровень для выполнения условия (2.17) определяется

= p_k(X), q K , X S_q S. (2.18)

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

Выше показано, что точка X^oS оптимальна по Парето. Развивая это направление, построим ряд аксиом, разделяющих допустимое множество S, во-первых, на подмножество точек S^о, оптимальных по Парето, и, во-вторых, на подмножества точек S_qS, qK, приоритетных по q-му критерию.

Аксиома 2. (О подмножестве точек, приоритетных по критерию).

В векторной задаче математического программирования (1.26)-(1.28) подмножество точек S_q S называется областью приоритета критерия qK над другими критериями, если X S_q kK _q(X) _k(X), q k.

Это определение распространяется и на множество точек S^о, оптимальных по Парето, что дается следующим определением.

Аксиома 2а. (О подмножестве точек, приоритетных по критерию, на множестве Парето в ВЗМП).

В векторной задаче математического программирования подмножество точек SS^oS называется областью приоритета критерия qK над другими критериями, если XS kK _q(X) _k(X), q k.

Дискуссия. Аксиома 2 и 2а позволили в ВЗМП (1.26)-(1.28) разбить допустимое множество точек S, в том числе подмножество точек, оптимальных по Парето, S^о S, на подмножества:

одно подмножество точек S'S, где критерии равнозначны, причем подмножество точек S', пересекаясь с подмножеством точек S^o, выделяет подмножество точек, оптимальных по Парето, при равнозначных критериях S^oo =S'S^o, которое, как будет показано далее, состоит из одной точки X^oS, т.е. X^o=S^oo=S'S^o, S'S, S^oS;

“K” подмножеств точек, где каждый критерий q= имеет приоритет над остальными критериями k=, q k, при этом разбивается, во-первых, множества всех допустимых точек S, на подмножества S_qS, q= и, во-вторых, множество точек, оптимальных по Парето, S^о, на подмножества

SS^oS, q=,

Отсюда верны следующие соотношения: S'U() = S^o, SS^oS, q=.

Заметим, что подмножество точек S с одной стороны включено в область (подмножество точек) приоритета критерия qK над другими критериями:

S S_q S, (2.19)

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

S S^o S. (2.20)

На тестовых примерах рис. 1 [10, 11, 12] в двухмерной системе координат эти области достаточно хорошо видны.

Аксиома 2 и числовое выражение приоритета критерия (7) позволяют идентифицировать каждую допустимую точку XS (с помощью вектора P^q(X)={p(X)=_q(X)/_k(X), k=}), формировать и выбирать:

· подмножество точек по приоритетному критерию S_q, которое включено в множество точек S, qK XS_qS, (такое подмножество точек может быть использовано в задачах кластеризации, но это выходит за рамки статьи);

· подмножество точек по приоритетному критерию S, которое включено в множество точек S^o, оптимальных по Парето, qK, XSS^o.

Таким образом, выполнена полная идентификация всех точек в векторной задаче (1.26)-(1.28) в последовательности:

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

Определение 8. Принцип оптимальности 2 (Решение ВЗМП с заданным приоритетом одного из критериев).

ВЗМП с заданным приоритетом q-го критерия p, k = считается решенной, если найдена точка X^o и максимальный уровень ^o среди всех относительных оценок такой, что

^o = p_k(X), q K. (2.21)

Используя взаимосвязь (2.17) и (2.18), преобразуем максиминную задачу (2.21) в экстремальную задачу вида



^o = , (2.21)

p_k(X), k=. (2.22)

Задачу (2.21)-(2.22) назовем -задачей с приоритетом q-го критерия.

Результатом решения -задачи будет точка X^o={X^o, ^o} - она же является и результатом решения ВЗМП (1.26)-( 1.28) с заданным приоритетом критерия, решенной на основе нормализации критериев и принципа гарантированного результата. В оптимальном решении X^o={X^o, ^o}, X^o - оптимальной точкой, а ^o - максимальный нижний уровень. Точка X^o и уровень ^o соответствуют ограничениям (15), которые могут быть записаны как:

^o p_k(X^o), k . (2.23)

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

Из определения «Принципов оптимальности» 1 и 2 вытекает возможность сформулировать понятие операции opt.

Определение 9. Математическая операция «opt».

В ВЗМП (1.26)-(1.28), в состав которой входят критерии “max” и “min”, математическая операция «opt» состоит в определении точки X^o и максимального нижнего уровня ^o, до которого подняты все критерии, измеренные в относительных единицах:

^o _k(X^o)= , k=, (2.24)

т. е. все критерии _k(X^o), k= равны или больше максимального уровня ^o (поэтому ^o также называется гарантированным результатом).

Теорема 2. (Теорема о наиболее противоречивых критериях в ВЗМП с заданным приоритетом).

Если в выпуклой векторной задаче математического программирования максимизации (1.26)-(1.28) задан приоритет q-го критерия p, k = , q K над остальными критериями, то в точке оптимума X^oS, полученной на основе нормализации критериев и принципа гарантированного результата, всегда найдется два критерия с индексами rK, tK, для которых выполняется строгое равенство:

^o = p_r(X^o) = p_t(X^o), r, t, K, (2.25)

а остальные критерии определяются неравенствами:

^o p(X^o), k = , q K, qrt. (2.26)

Критерии с индексами rK, tK, для которых выполняется равенство (2.25) называются наиболее противоречивыми.

Доказательство. Аналогично теореме 1 [9].

Заметим, что в (2.25) и (2.26) индексы критериев r, t K могут совпадать с индексом q K.

Следствие теоремы 1. О равенстве оптимального уровня и относительных оценок в ВЗМП с двумя критериями с приоритетом одного из них.

В выпуклой векторной задаче математического программирования с двумя равнозначными критериями, решенной на основе нормализации критериев и принципа гарантированного результата, в оптимальной точке X^o всегда выполняется равенство:

при приоритете первого критерия над вторым:



^o = ₁(X^o) = p(X^o)₂(X^o), X^oS, где p(X^o) = ₁(X^o)/₂(X^o), (2.27)

при приоритете второго критерия над первым:

^o = p(X^o)₁(X^o) = ₂(X^o), X^oS, где p(X^o) = ₁(X^o)/₂(X^o).

2.4 Алгоритм решения в задачи векторной оптимизации с приоритетом критерия (Алгоритм Машунина Ю.К. [7]).

Рассмотрим векторную задачу (1.26)-(1.28). Предполагаем, что в этой задаче имеется приоритет qК критерия. Под решением ВЗМП с приоритетом критерия понимаем получение оптимальной точки из области приоритета критерия в соответствии с аксиомой 2а и заданным вектором приоритетов в соответствии с определением 6.

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

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

Выбор точки X^oS осуществляется по двум алгоритмам, которые отличаются друг от друга заданием исходных данных:

· задается вектор приоритетов P={p, k=}, qK и находится соответствующая точка оптимума X^o, у которой величина f_q(X^o) приближается к заданной f, см. определения 5, 6;

· задается величина целевой функции f задается в натуральных единицах и для нее определяется вектор приоритетов p, k=, qK, вычисляется точка X^oS - этот алгоритм ниже представлен.

Алгоритм решения ВЗМП с приоритетом критерия представим в виде последовательности шагов.

Шаг 1. Решается ВЗМП с равнозначными критериями - алгоритм выше представлен. В результате решения получим:

· точки оптимума по каждому критерию отдельно X, k= и величины целевых функций в этих точках f=f_k(X), k=, которые представляют собой границу множества точек, оптимальных по Парето;

· точки антиоптимума по каждому критерию X={x_j, j=} и наихудшую неизменяемую часть критерия f=f_k(X), k=;

· X^o={^o, X^o} - точку оптимума, как результат решения ВЗМП при равнозначных критериях, т. е. результат решения максиминной задачи и построенной на ее основе -задачи;

· ^o - максимальную относительную оценку, которая является максимальным нижним уровнем для всех относительных оценок _k(X^o), или гарантированным результатом в относительных единицах, ^o гарантирует, что в точке X^o все относительные оценки _k(X^o) больше или равны ^o:

^o _k(X^o), k=, X^o S. (2.28)

Лицо, принимающее решение, проводит анализ результатов решения ВЗМП при равнозначных критериях. Если полученные результаты удовлетворяют ЛПР, то конец , иначе последующие вычисления.

Дополнительно вычислим:

· в каждой точке X, k= определим величины всех критериев F(X) и относительных оценок (X):

F(X)=, (X)=, _q(X)=, q,kK.

Матрицы критериев F(X^*) и относительных оценок (X^*) показывают величины каждого критерия k= при переходе от одной оптимальной точки X, kK к другой X, qK, т. е. на границе множества Парето.

· в точке оптимума при равнозначных критериях X^o вычислим величины критериев и относительных оценок:

f_k(X^o) , k=; _k(X^o), k=, (2.30)

которые удовлетворяют неравенству (2.28). В других точках XS^o меньший из критериев в относительных единицах = _k(X) всегда меньше ^o.

Запоминаются данные -задачи (2.11)-(2.13).

^o = max , (2.31)

- 0, k = , (2.32)

G(X) B, X 0, (2.33)

где вектор неизвестных X имеет размерность N+1: X={, x₁, … , x_N}.

Эта информация и является основой для дальнейшего изучения структуры множества Парето.

Шаг 2. Выбор приоритетного критерия qK.

Из теоремы 1 вытекает, что в оптимальной точке X^o всегда имеется два наиболее противоречивых критерия, qK и vK, для которых в относительных единицах выполняется точное равенство:

^o = _q(X^o) = _p(X^o), q, v K, XS, (2.34)

а для остальных выполняется неравенства: ^o _k(X^o) k K, q v k.

Эти два критерия сдерживают дальнейший рост всех критериев. Поэтому из этой пары выбирается критерий, который ЛПР хотел бы улучшить, такой критерий называется «приоритетным критерием», обозначим его qK.

Шаг 3. Определяются числовые пределы изменения величины приоритета критерия qK. Для приоритетного критерия qK из матрицы (2.29) определим числовые пределы изменения величины критерия в точках X^o, X:

· в натуральных единицах f_q(X^o)f_q(X)f_q(X), kK, (2.35)

где f_q(X) берется из матрицы (2.29) F(X^*), показывающих величины всех критериев, измеренных в натуральных единицах; f_q(X^o) из (2.30);

· в относительных единицах _q(X^o) _q(X) _q(X), kK, (2.36)

где _q(X) берется из матрицы (2.29) (X^*), показывающих величины всех критериев, измеренных в относительных единицах (заметим, что _q(X)=1); _q(X^o) из (2.30).

Как правило, результаты (2.35)-(2.36) выдаются на дисплей для анализа.

Шаг 4. Определяются пределы изменения вектора приоритета критерия P^q, qK. Величина приоритета критерия qK по отношению к другим критериям определяется в точках X^o и X по формулам: