Системный анализ в информационных технологиях - 71 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Отношение R называют транзитивным, если из aRb и bRc следует aRc.
Отношение R называется полным, если для любых a, b ∈ R справедливо aRb или bRa. Отношение,
не являющееся полным, называется частичным.
Например, отношение ≥ («не меньше») на множестве действительных чисел рефлексивно, анти-
симметрично, транзитивно и полно.
Определим на множестве E
n
отношения
>
, ≥, > следующим образом:
a > b ⇔ a
i
≥ b
i
, i = 1, 2, …, n, a > b ⇔ a ≥ b и a ≠ b
(т.е. хотя бы одно из n неравенств a
i
≥ b
i
строгое);
a > b ⇔ a
i
> b
i
, i = 1, 2, …, n,
где a = (a
1
, a
2
, …, a
n
), b = (b
1
, b
2
, …, b
n
).
Обозначим через (µ, а) скалярное произведение векторов. Справедливо следующее утверждение.
Лемма 1. Для любых a, b ∈ E
n
из неравенства a > b следует, что существует такой вектор
)}...,,,{(
21 n
M λλλ=∈λ .
Доказательство. Предположим, что a ≥ b. Если a = b, то, очевидно, (λ, a) = (λ, b) для любого λ ∈ М.
Пусть для некоторого номера j ≤ n имеет место строгое неравенство a
j
≥ b
j
. Обозначим p = max{A, B},
где A =
∑
≠ ji
i
a , B =
∑
≠ ji
i
b . Если p = 0, то (λ, a)= λ
i
a
i
> λ
i
b
i
= (λ, b) для любых λ
i
> 0.
Если p > 0, положим r = (a
j
– b
j
) / 2p > 0.
Поскольку p ≥ (A + B) / 2, то (a
j
– b
j
) = 2pr ≥ r (A + B), откуда
a
j
– rA ≥ b
j
– rB.
Учитывая
∑
∑
≠≠
−≥
jiji
ii
aa = – AB =
∑
∑
≠≠
≥
jiji
ii
bb
получим a
j
+
∑
i
ar ≥ b
j
+
∑
i
b .
Выберем λ
j
= 1/(1 + r (n – 1)), λ
i
= r / (1 + r (n – 1)) при i ≠ j, тогда окончательно получим (λ, a) ≥ (λ,
b).
Для произвольного бинарного отношения R часто возникает задача: среди элементов множества E
n
найти недоминируемые по бинарному отношению R. Элемент a называется недоминируемым по бинар-
ному отношению R, если не существует
n
Eb ∈ , такого, что bRa. Для решения задачи могут быть исполь-
зованы свойства этих отношений. Одним из основных свойств такого рода является отделимость.
Пусть
n
E∈λ . Отношение R на E
n
называется λ-отделимым, если aRb ⇒ (λ, a)> (λ, b).
Если неравенство заменить на нестрогое, то получим понятие нестрогой λ-отделимости.
Пусть отношение λ
1
-отделимо и λ
2
-отделимо, т.е.
aRb ⇒ (λ
1
, a) > (λ
1
, b), (λ
2
, a) > (λ
2
, b).
Тогда, очевидно, отношение R будет (λ
1
+ λ
2
)-отделимым. Если R λ-отделимо и k – положительная
константа, то R является
kλ-отделимым. Таким образом, множество векторов λ, для которых R λ-отделимо, представляет собой
конус.
Рассмотрим векторный критерий Н(и). Для каждого u ∈ U, Н(и) есть вектор пространства E
n
. Сфор-
мулируем понятие оптимальности для произвольного бинарного отношения R. Управление u
*
∈ U на-

Страницы