Approximation of the Slater set taking into account the relative importance of criteria

Full Text

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

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

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

1. Постановка задачи. Пусть в s – мерном евклидовом пространстве $ℝ$_s задана m – мерная непрерывная вектор-функция

$w\left(x\right)\in {ℝ}^m$ (1.1)

– вектор частных критериев эффективности, принимающий на непустом компактном множестве допустимых решений (допустимом множестве)

$X\subset {ℝ}^s$ (1.2)

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

$w\left(X\right)=\left\{u\in {ℝ}^m\left|u=w\left(x\right),x\in X\right.\right\}\subset \mathrm{int}{ℝ}_{+}^m$ (1.3)

принадлежит внутренности int ${ℝ}_{+}^m$ неотрицательного ортанта ${ℝ}_{+}^m$. Без потери общности полагаем, что каждую компоненту w_k(x), $к=\overline{1,m,}$ векторного критерия (1.1) желательно увеличивать на допустимом множестве (1.2).

Определение 1. Векторная оценка w ∈ w(X ) эффективна (слабо эффективна), если для всякой векторной оценки u ∈ w(X ) система неравенств u ≥ w несовместна при условии, что хотя бы одно неравенство строгое (все неравенства строгие).

Если u, w ∈ w(X ), то векторная оценка w доминируема .

Всякое допустимое решение x ∈ X, доставляющее эффективное (слабо эффективное, доминируемое) значение вектора w(x), называется эффективным (слабо эффективным, доминируемым) решением.

Согласно определению 1, эффективная векторная оценка слабо эффективна, достижимая векторная оценка w ∈ w(X ) либо слабо эффективна, либо доминируема, множества эффективных X_e, слабо эффективных X₀ и доминируемых X_д решений из множества допустимых решений X подчиняются соотношениям:

$X_e\subset X_0\subset X,X_0\cap X_{\partial }=\varnothing ,X=X_0\cup X_{\partial },$

где ∅ – пустое множество, ∪(∩) – символ объединения (пересечения) множеств. Соответственно w(X_e), w(X₀), w(X_д), w(X ) – множества эффективных, слабо эффективных, доминируемых и достижимых векторных оценок удовлетворяют соотношениям:

$w\left(X_e\right)\subset w\left(X_0\right)\subset w\left(X\right),w\left(X_0\right)\cap w\left(X_{\partial }\right)=\varnothing ,w\left(X\right)=w\left(X_0\right)\cup w\left(X_{\partial }\right)$ (1.4)

где w(X_e), w(X₀) – множества Парето и Слейтера соответственно.

Сформулируем также следующие определения.

Определение 2. Величина

$D\left(W,U\right)=\underset{w\in W}{\sup }\underset{u\in U}{\inf }||w-u||,\varnothing \ne W,U\subset {ℝ}^m,$

называется отклонением множества W от множества U, а величина

$\Delta \left(W,U\right)=\max \left\{D\left(W,U\right),D\left(U,W\right)\right\},\varnothing \ne W,U\subset {ℝ}^m,$

– расстоянием по Хаусдорфу между W и U, где ||·|| – норма вектора в ${ℝ}^m$.

Определение 3. Заданная на выпуклом множестве $A\subset {ℝ}^s$ функция f называется w – вогнутой на A, если для любых фиксированных x, y ∈ A при условии f (y) ≥ f (x) можно указать такую величину w = w(x, y) ∈ (0, 1], что для любого r ∈ (0, 1) выполняется неравенство:

Определение 4. Заданная на выпуклом множестве A ⊂ R^s функция f удовлетворяет на условию Липшица, если существует такая константа $\theta$ > 0, что для любых x, y ∈ A выполняется условие | f (y) – f (yx)| ≤ $\theta$|| y – x ||.

В условиях (1.1)–(1.3) множество Слейтера согласно работам [1, 2] можно представить в виде:

$w\left(X_0\right)=\underset{\lambda \in {\Lambda }_m}{\cup }\text{Arg}\underset{w\in w\left(X\right)}{\max }f\left(\lambda ,w\right),$

$\text{Arg}\underset{w\in w\left(X\right)}{\max }f\left(\lambda ,w\right)=\left\{w\in W\left|f\left(\lambda ,w\right)=\underset{u\in w\left(X\right)}{\max }\right.f_{\lambda }\left(u\right)\right\},$ (1.5)

где скалярная функция (обобщенная логическая свертка)

$f\left(\lambda ,w\right)=\underset{k=\overline{\mathrm{1,}m},{\lambda }_k>0}{\min }{\lambda }_k^{-1}{w}_k,\lambda \in {\Lambda }_m=\left\{\lambda \in {ℝ}^m\left|{\sum }_{k=1}^m{\lambda }_k=\mathrm{1,}\lambda \ge 0\right.\right\}$ (1.6)

зависит от векторного параметра $\lambda \in {\Lambda }_m\subset {ℝ}^m$, принадлежащего (m – 1)-мерному стандартному симплексу ${\Lambda }_m$ = conv{e^k}^m_{k = 1} – выпуклой оболочке векторов ортонормированного базиса {e^k}^m_{k = 1} в евклидовом пространстве ${ℝ}^m$. Компоненты {$\lambda$^k}^m_{k = 1} вектора $\lambda$ имеют в скалярной свертке (1.6) смысл коэффициентов важности (весовых коэффициентов) соответствующих частных критериев {w^k}^m_{k = 1}.

Пусть о коэффициентах важности $\lambda$ получена (например, в результате экспертизы) достоверная информация, позволяющая сузить априорное множество ${\Lambda }_m$ = conv{e^k}^m_{k = 1}, заменив его более точным непустым подмножеством $\Lambda$_инф, так что можно утверждать:

$\lambda ={\Lambda }_{\text{инф}}=\text{conv}{\left\{{\lambda }^q\right\}}_{q=1}^n,\varnothing \ne {\Lambda }_{\text{инф}}\subset {\Lambda }_m\ne {\Lambda }_{\text{инф}}.$ (1.7)

В этих условиях нет необходимости строить множество Слейтера w(X₀) из (1.5) целиком. Достаточно, в согласии с дополнительной информацией (1.7), найти его более “узкое” подмножество:

$w_{\text{инф}}=\underset{\lambda \in {\Lambda }_{\text{инф}}}{\cup }\text{Arg}\underset{w\in w\left(X\right)}{\max }\underset{k=\mathrm{1,}m,{\lambda }_k>0}{\min }{\lambda }_k^{-1}{w}_k\subset w\left(X_0\right),$ (1.8)

где включение в (1.8) с учетом (1.5) вытекает из последнего включения в (1.7).

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

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

$w_k\succcurlyeq w_{k+1}, k=\overline{\mathrm{1,}m-1} .$ (2.1)

С формальной точки зрения это означает, что на множестве пар объектов (пар частных критериев эффективности {W_k}^m_k=1 в нашем случае) установлен линейный квазипорядок (рефлексивное, транзитивное и линейное бинарное отношение нестрогого предпочтения), а коэффициенты важности критериев соответствуют порядковой мере важности:

${\lambda }_k\ge {\lambda }_{k+1},k=\overline{\mathrm{1,}m-1}.$.

Эта дополнительная информация позволяет уточнить коэффициенты важности по сравнению с априорным утверждением $\lambda \in {\Lambda }_m$ из (1.6):

$\begin{array}{c}\lambda \in {\Lambda }_{инф}=\left\{\lambda \in {ℝ}^m\left|\sum _{}_{k=1}^m{\lambda }_k=\mathrm{1,} {\lambda }_k\ge {\lambda }_{k+1}\ge \mathrm{0,} k=\overline{\mathrm{1,}m-1}\right.\right\}=conv{\left\{{\lambda }^q\right\}}_{q=1}^m,\\ {\lambda }^q=q^{-1}\sum _{}_{k=1}^q{e}^k, q=\overline{\mathrm{1,}m} ,\end{array}$ (2.2)

так что уточняющее множество $\lambda \in \Lambda$_инф может быть приведено в виде (1.7).

Среди других используемых мер важности частных критериев [3] представляет интерес следующая частичная порядковая мера важности.

Пример 2. Пусть для частных критериев эффективности {W_k}^m_k=1 не удается определить линейный квазипорядок, подобный (2.1), но можно указать непустое подмножество ${\left\{w_k\right\}}_{k\in K} , \varnothing \ne K\subset I=\left\{k| k=\overline{\mathrm{1,}m}\right\},$ каждый критерий которого превосходит по важности любой критерий дополнения – подмножества {w_k}_{k ∈ I \K}, так что на множестве пар частных критериев эффективности {W_k}^m_k=1 определен следующий частичный квазипорядок:

$w_k\succcurlyeq w_i,k\in K,i\in I\text{}K,$ (2.3)

а на множестве коэффициентов важности критериев устанавливается соответствующая частичная порядковая мера важности:

$\lambda \in {\Lambda }_{\text{инф}}=\left\{\lambda \in {ℝ}^m\left|\sum _{}_{k=1}^m{\lambda }_k=\mathrm{1,} {\lambda }_k\ge {\lambda }_i, k\in J , j\in I\text{}J .\right.\right\}$

3. Построение информационного множества. Согласно соотношениям (1.5), (1.6), (1.8), обе задачи: исходная задача построения множества Слейтера w(X₀) и задача построения информационного множества W_инф, могут быть решены одним и тем же методом. В основу метода положена [4] логическая свертка (1.6) векторного критерия (1.1) в скалярный критерий. Разница заключается лишь в том, что для аппроксимации множества Слейтера на основе представления (1.5) некоторая e – сеть L_e, в узлах которой предстоит решать задачу скалярной условной оптимизации:

$\begin{array}{c}f\left(\lambda ,w\right)\underset{w\in w\left(X\right)}{\to }\text{max}, \lambda \in {\Lambda }_{\epsilon },\\ f\left(\lambda ,w\right)=\underset{1\le k\le m , {\lambda }_k>0}{\text{min}}{\lambda }_k^{-1}{w}_k, {\Lambda }_{\epsilon }={\left\{{\lambda }^i\right\}}_{i=1}^N=\left\{{\lambda }^i\in \Omega \left|\underset{\lambda \in \Omega }{\text{max}}\underset{i=\overline{\mathrm{1,}N}}{\text{min}}\lambda -{\lambda }^i\le \epsilon \right.\right\} ,\end{array}$ (3.1)

накладывается на весь стандартный симплекс $\Omega \in {\Lambda }_m$, а при аппроксимации информационного множества $\epsilon$ – сеть накладывается в согласии с (1.8) только на часть стандартного симплекса $\Omega ={\Lambda }_{инф}\subset {\Lambda }_m$. Если множество ${\Lambda }_{инф}$ определяет порядковая мера важности, то в согласии с (2.2) его (m–1) – мерный объем меньше в m! раз объема стандартного симплекса ${\Lambda }_m$, так что для достижения одинаковой точности аппроксимации $\epsilon$ – сеть ${\Lambda }_{\epsilon }$ = {$\lambda$ⁱ}^N_{i = 1}, покрывающая ${\Lambda }_{инф}$, может содержать в m! раз меньше точек, чем при покрытии всего стандартного симплекса. Это обеспечивает существенную экономию вычислительных средств, если число критериев m велико.

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

В самом деле, пусть на множестве w(X ) в (1.3) задан набор оценок:

$w^q\le \sum _{k=1}^m{w}_k^{\ast }{e}^k,q=\mathrm{1,2,}\dots ,$

где $w_k^{*}= \underset{x\in X}{\text{max}} w_k\left(x\right) , k=\overline{\mathrm{1,}m} ,$ – рекордные значения критериев эффективности. Тогда экспертное мнение может измениться кардинально в зависимости от того, какая из векторных оценок w ^q предъявлена эксперту.

Пример 3. Пусть m = 2, векторные оценки w¹, w² ∈ ${ℝ}^2$ таковы, что

$w^1=0.1w_1^{\ast }{e}^1+0.9w_2^{\ast }{e}^2,w^2=0.1w_1^{\ast }{e}^1+0.9w_2^{\ast }{e}^2,$

так что оценка w¹ по первому критерию далека от рекордной, а по второму критерию близка, тогда как с оценкой w² ситуация противоположная. При предъявлении эксперту оценки w¹ он может заключить, что первый критерий следует “подтянуть”, так что он важнее второго, w¹ $\ge$ w²; при предъявлении оценки w² результат может оказаться противоположным, w² $\ge$ w¹.

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

Затруднения подобного рода отсутствуют, если применяются методы отыскания слабо эффективных векторных оценок, не использующие прием скаляризации векторного критерия [2, 5]. Дадим, согласно [2], формальное описание универсальной процедуры аппроксимации множества Слейтера.

4. Универсальная процедура аппроксимации множества Слейтера. На непустом компактном множестве допустимых решений X ⊂ ${ℝ}^s$ строится последовательность множеств {X_t}^∞_{t = 1} ⊂ X. Если {x¹} ⊂ X₁ ⊂ X – произвольное начальное приближение, и известно множество X_t, t ≥ 1, то следующее за ним множество X_{t + 1} подчиняется соотношениям:

$X_{t+1}=\underset{x\in X_t}{\cup }{X}_{t+1}\left(x\right) , X_{t+1}\left(x\right)=\left\{x\right\}+\underset{J\in M_t\left(x\right)}{\cup }\left\{h\left(x,J\right)\right\}\subset X.$ (4.1)

Согласно (4.1), всякое опорное решение порождает на t + 1-м этапе непустую векторную сумму множеств X_{t + 1}(x), причем направление h(x, J ) перехода от опорного решения x ∈ X_t к любому последующему решению $y^J=x+h(x,J)\in X_{t+1}\left(x\right),J\in M_t\left(x\right)$ определяется единственным образом и удовлетворяет условиям:

$h\left(x,\varnothing \right)=\mathrm{0,}h\left(x,J\right)\ne \mathrm{0,}\varnothing \ne J\subset I=\left\{k\left|k=\overline{\mathrm{1,}m}\right.\right\}$ (4.2)

тогда как ненулевые направления $h\left(x,J\right)\ne 0$ подчиняются соотношениям:

$\begin{array}{c}{y}^J=x+h\left(x,J\right)\in X\cap Y_J\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right), \varnothing \ne J\subset I=\left\{\text{k|} \text{k}=\overline{\mathrm{1,}\text{m}}\right\},\\ Y_J\left(x,\epsilon \right)=\left\{y\in {ℝ}^s\left|\frac{w_k\left(y\right)}{w_k\left(x\right)}\ge 1+\sigma {\epsilon }^2,k\in J\right., \frac{w_k\left(y\right)}{w_k\left(x\right)}\ge 1-\sigma \epsilon ,k\in I\text{}J\right\},\\ Y\left(x,\epsilon \right)=\left\{y\in {ℝ}^s\left|\frac{w_k\left(y\right)}{w_k\left(x\right)}\le 1+\sigma \epsilon ,k\in I\right.\right\},\\ \epsilon ={\epsilon }_t\left(x\right)\in \left(\mathrm{0,1}\right), \sigma ={\left[2\underset{z\in X}{\text{max}}\sum _{}_{k\in I}{w}_k\left(z\right)\right]}^{-1}\underset{z\in X}{\text{min} }\underset{k\in I}{\text{min}} w_k\left(z\right)\in \left(0,\frac{1}{2}\right].\end{array}$ (4.3)

Последовательность множеств (4.1) ветвится в каждой опорной точке x ∈ X_t, причем степень ее ветвления |M_t(x)| определяет множество не вложенных друг в друга подмножеств |M_t(x)| ⊂ 2^I, заданное следующими соотношениями:

$\begin{array}{c}\left|M_t\left(x\right)\right|=\left\{\begin{array}{c}{N}_t\left(x\right),еслиN_t\left(x\right)\ne \mathrm{0,}\\ \left\{\varnothing \right\},еслиN_t\left(x\right)\ne \mathrm{0,}\end{array}\right.\\ N_t\left(x\right)=\left\{J\subset I\left|\begin{array}{c}X\cap Y_J\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)\ne 0\\ X\cap Y_M\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)=\varnothing ,M\ne J\subset M\subset I\end{array}\right.\right\}.\end{array}$ (4.4)

Наибольшая степень ветвления последовательности (4.1) совпадает с наибольшим числом не вложенных друг в друга подмножеств множества номеров частных критериев эффективности I = {k | $\text{k}=\overline{\mathrm{1,}\text{m}}$}, так что

$\left|M_t\left(x\right)\right|\le \raisebox{1ex}{$m!$}\!\left/ \!\raisebox{-1ex}{$⌊\raisebox{1ex}{$m$}\!\left/ \!\raisebox{-1ex}{$2$}\right.⌋!\left(m-⌊\raisebox{1ex}{$m$}\!\left/ \!\raisebox{-1ex}{$2$}\right.⌋\right)$}\right.,$ (4.5)

где | A | – число элементов в конечном множестве A, $\left|Z\right|$ – целая часть числа Z.

Соотношения (4.3), (4.4) включают величину $\epsilon$ = $\epsilon$_t(x) ∈ (0, 1) – параметр возмущения, который в начальной точке x¹ и в любых последующих точках x^t ∈ X_t, x^{t +1} ∈ X_{t +1}(x^t)последовательности (4.1), таких, что

$x^{t+1}=x^t+h\left(x^t,J_t\right),J_t\in M_t\left(x\right),$ (4.6)

удовлетворяет условиям:

${\epsilon }_1\left(x^1\right)=\kappa \in \left(\mathrm{0,1}\right), {\epsilon }_{t+1}\left(x^{t+1}\right)=\left\{\begin{array}{c}\kappa {\epsilon }_t\left(x^t\right),\text{\hspace{1em}если} Q_t=\varnothing ,\\ {\epsilon }_t\left(x^t\right),\text{\hspace{1em}если} Q_t\ne \varnothing ,\end{array}\right.$ (4.7)

$Q_t=\underset{q\le t,{\epsilon }_q\left(x^q\right)={\epsilon }_t\left(x^t\right)}{\cap }{J}_q,$

где величина k определяет степень дробления параметра возмущения. Эта величина может быть выбрана любой в интервале (0, 1), но является фиксированной на протяжении всей вычислительной процедуры.

В согласии с доказательством из работы [2] заданная соотношениями (4.1)–(4.7) последовательность множеств {w(X_t)}^∞_{t =1} аппроксимирует множество Слейтера в следующем смысле.

Теорема. Пусть в соотношении (1.1) компоненты вектор–функции w ∈ ${ℝ}^m$ положительно определены, удовлетворяют условию Липшица и w – вогнуты в открытой окрестности непустого выпуклого компакта X. Тогда отклонение множества Парето w(X_e) от аппроксимирующего множества w(X_t ) и отклонение множества w(X_t ) от множества Слейтера w(X₀) стремятся к нулю с ростом номера аппроксимации t:

$\underset{t\to \infty }{\lim }D\left(w\left(X_e\right),w\left(X_t\right)\right)=\underset{t\to \infty }{\lim }D\left(w\left(X_t\right),w\left(X_0\right)\right)=0.$

Следствие. Если множества Парето и Слейтера совпадают, w(X_e) = w(X₀), то последовательность аппроксимирующих множеств стремится к множеству Слейтера в метрике Хаусдорфа, $\underset{t\to \infty }{\lim }\Delta \left(w\left(X_t\right),w\left(X_0\right)\right)=0.$

5. Учет информации об упорядоченности критериев. Итеративная структура универсальной процедуры (4.1)–(4.7) позволяет осуществлять переход от текущего опорного решения x ∈ X_t к последующим:

$y^J=x+h\left(x,J\right)\in X_{t+1}\left(x\right),J{\in }_t\left(x\right),$

в интерактивном режиме с учетом принятого для данного опорного решения x ∈ X_t упорядочения частных критериев по важности. Для этого требуется скорректировать правило (4.4) формирования множеств M_t(x).

Линейный квазипроядок. Пусть на каждом шаге t для соответствующей опорному решению x ∈ X_t векторной оценки

$w\left(x\right)=\sum _{k=1}^m{w}_k\left(x\right)e^k$

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

$w_{k\left(x,i\right)}\succcurlyeq w_{k\left(x,i+1\right)},i=\overline{\mathrm{1,}m-1},$ (5.1)

где {k(x, i)}^m_{i =1} – перестановка исходной нумерации критериев {k}^m_{i =1}, так что всякий критерий w_{k(x, i)} не уступает по важности критериям {w_{k(x, i+c)}}_c^m₌₁^{– i}.

Тогда множество M_t(x), определяющее, согласно соотношениям (4.1)–(4.4), новые опорные решения X_{t +1}(x), следует задать в виде:

${}_{\mathrm{t}}\left(\mathrm{x}\right)=\left\{\begin{array}{c}\left\{{\left\{\mathrm{k}\left(\mathrm{x},\mathrm{i}\right)\right\}}_{\mathrm{i}=1}^{\mathrm{r}}\right\}, \text{\hspace{0.33em}если} \mathrm{r}=\text{arg }\underset{\mathrm{J}={\left\{\mathrm{k}\left(\mathrm{x},\mathrm{i}\right)\right\}}_{\mathrm{i}=1}^{\mathrm{q}}\subset \mathrm{I} , \mathrm{X}\cap {\mathrm{Y}}_{\mathrm{J}}\left(\mathrm{x},\mathrm{\epsilon }\right)\cap \mathrm{Y}\left(\mathrm{x},\mathrm{\epsilon }\right)\ne \varnothing }{\text{max}} \mathrm{q},\\ \left\{\varnothing \right\}, \text{если} \mathrm{X}\cap {\mathrm{Y}}_{\left\{\mathrm{k}\right\}}\left(\mathrm{x},\mathrm{\epsilon }\right)\cap \mathrm{Y}\left(\mathrm{x},\mathrm{\epsilon }\right)=\varnothing , \mathrm{k}=\overline{1,\mathrm{m}} . \end{array}\right.$ (5.2)

Из соотношений (5.2) следует, что множество M_t(x) содержит единственный элемент: либо пустое множество ∅, либо множество {k(x, i)}^r_{i =1} первых r номеров в перестановке, что позволяют выстроить множество M_t(x) конструктивно. В самом деле, для вычисления величины r достаточно проверить последовательно выполнение условий

$X\cap Y_{{\left\{k\left(x,i\right)\right\}}_{i=1 }^q}\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)\ne \varnothing , q=\overline{\mathrm{1,}m}$, (5.3)

и остановиться, как только возникнет ситуация

$X\cap Y_{{\left\{k\left(x,i\right)\right\}}_{i=1}^r}\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)\ne \varnothing ,X\cap Y_{{\left\{k\left(x,i\right)\right\}}_{i=1}^{r+1}}\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)\ne \varnothing$,

когда первые r критериев по порядку (5.1) согласно (4.3), (5.2) еще можно улучшить относительно текущего значения на величину ~e², а первые r + 1 – уже нет; если все пересечения (5.2) не пусты, то $r=m, M_t\left(x\right)=\left\{I\right\}$.

В организованной таким образом процедуре ветвление отсутствует (поскольку вектор h(x, J) в соотношениях (4.3) определяется единственным образом). Таким образом, последовательность (4.1) есть последовательность точек {x ^t}^∞_{t =1}, если для каждой опорной точки x = x ^t может быть получен тот или иной линейный квазипорядок (5.1). В условиях теоремы справедливо следующее утверждение.

Утверждение 1. Множество предельных точек X_инф последовательности {x ^t}^∞_{t =1}, заданной соотношениями (4.1)–(4.3), (4.5)–(4.7), (5.1), (5.2), составлено из слабо эффективных решений, X_инф ⊂ X₀, а соответствующее информационное множество вложено во множество Слейтера, W_инф = w(X_инф) ⊂ w(X₀).

Утверждение 1 следует из доказательства теоремы сходимости [5].

Пусть на некотором шаге t процедуры для соответствующей векторной оценки

$w\left(x\right)=\sum _{k=1}^m{w}_k\left(x\right)e^k$

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

Частичный квазипорядок. Согласно (2.3), в опорной точке x ∈ X_t выполняются соотношения $w_k\succcurlyeq w_i,k\in K_t,i\in I\text{}{K}_t$: каждый критерий множества {w_k}_{k ∈ Kt} не уступает по важности любому из критериев дополнения {w_k}_{k ∈ I \Kt}.

Множество M_t(x), определяющее согласно соотношениям (4.1)–(4.4) новые опорные решения X_{t +1}(x), в данных условиях следует задать в виде:

$\begin{array}{c}{M}_t\left(x\right)=\left\{\begin{array}{c}{N}_t\left(x\right),еслиN_t\left(x\right)\ne \varnothing \\ \left\{\varnothing \right\},еслиN_t\left(x\right)\ne \varnothing \\ \left\{I\right\},еслиX\cap Y_I\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)\ne \varnothing ,\end{array}\right.\\ N_t\left(x\right)=\left\{J\subset I\left|\begin{array}{c}X\cap Y_J\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)\ne \varnothing \\ X\cap Y_M\left(x,\epsilon \right)\cap Y\left(x,\epsilon \right)=\varnothing ,M\ne J\subset M\subset K_t\end{array}\right.\right\}.\end{array}$ (5.4)

В процедуре, заданной соотношениями (4.1)–(4.3), (4.5)–(4.7), (5.1), (5.4), ветвление на этапе t имеет место, как и в исходной, однако в условиях частичного квазипорядка степень ветвления существенно меньше в сравнении с (4.5),

$\left|{}_t\left(x\right)\right|\le \raisebox{1ex}{$\left|K_t\right|!$}\!\left/ \!\raisebox{-1ex}{$⌊\left|K_t\right|/2⌋\left(\left|K_t\right|!-⌊\left|K_t\right|/2⌋\right)!$}\right.,$ (5.5)

поскольку зависит лишь от количества |K_t | более важных критериев: при |K_t | = 3 степень ветвления |M_t (x)| ≤ 3 в согласии с (5.5). Тем самым разработчики могут от этапа к этапу варьировать как состав, так и число |K_t | более важных критериев в зависимости от доступности вычислительных мощностей.

Для частичных квазипорядков выполняется подобное утверждению 1 следующее утверждение.

Утверждение 2. Множество предельных точек X_инф последовательности множеств {X_t}^∞_{t =1} ⊂ X, заданной соотношениями (4.1)–(4.3), (4.5)–(4.7), (5.1), (5.4), составлено из слабо эффективных решений, X_инф ⊂ X₀, а соответствующее информационное множество W_инф = w(X_инф) вложено во множество Слейтера.

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

Заключение. Задача построения информационного множества исследовалась на основе предложенной в работе [2] универсальной вычислительной процедуры при следующих предположениях: компонентами вектора частных критериев эффективности являются функции, которые положительно определены, удовлетворяют условию Липшица и w – вогнуты в открытой окрестности непустого выпуклого компакта – множества допустимых решений X. Показано, что основанные на скаляризации векторного критерия методы продуктивны, если для частных критериев может быть принят неизменный порядок важности, никак не связанный с меняющимися в ходе вычислительного процесса векторными оценками эффективности.

При необходимости соотносить ранжирование критериев с достигнутым значением оценки эффективности могут применяться методы, основанные на универсальной вычислительной процедуре [2]. Если на каждом шаге процедуры критерии удается ранжировать согласно линейному квазипорядку, процедура не ветвится; она задает последовательность векторных оценок, множество предельных точек которой принадлежит множеству Слейтера, W_инф ⊂ w(X₀). Если определяются лишь частичные квазипорядки, ветвление вычислительной процедуры оказывается подавленным, а множество предельных точек также принадлежит множеству Слейтера, W_инф ⊂ w(X₀).

About the authors

YA. I. Rabinovich

Author for correspondence.
Email: jacrabin@rambler.ru
Russian Federation, Moscow

References

Supplementary files