zhChinese    enEnglish
  ПМ-ПУ  » Структура » Преподаватели  » Ногин В.Д.  » Теоремы существования

Теоремы существования

Рассмотрим задачу максимизации векторного критерия f = (f_1,f_2, \dots ,f_m) на множестве возможных точек X, \ X \subset \mathbb{R}^n \,. Пусть f (X) \subset \mathbb{R}^m\, означает образ множества X\, при отображении f\, .

Напомним, что точка x^* \in X называется эффективной (Парето-оптимальной) относительно f \, на множестве X\, , если не существует такой допустимой точки x \in X, что выполнено

f_{i}(x) \ \underline{\underline{>}} \ f_{i}(x^*), \ i=1,2, \dots ,m, и f(x) \ne f(x^*);

собственно эффективной (оптимальной по Джеофриону) относительно f \, на множестве X\, , если x^*\, эффективна и существует такая положительная константа M\, , что для всякого x \in X и каждого i\, , при которых f_{i}(x) > f_{i}(x^*)\,, и некоторого j\, , такого что f_{j}(x) < f_{j}(x^*),\, выполнено неравенство

\frac{ f_{i}(x) - f_{i}(x^*)}{ f_{j}(x^*) - f_{j}(x)} \ \underline{\underline{<}} \ M.

Теорема 1 (1980, [I, 1], [III, 5]). Пусть все компоненты векторной функции f \, вогнуты и непрерывны на непустом выпуклом замкнутом множестве X\, и множество f(X)\, замкнуто. Собствено эффективные точки относительно f \, на множестве X\, существуют тогда и только тогда, когда найдутся такие положительные числа \mu _1, \mu_2, \dots ,\mu _m, \ \ \sum_{i=1}^m \mu _i=1, и константа const\, , что для всех \ x \in X имеет место неравенство

\sum_{i=1}^m \mu _i f_i(x) \ \underline{\underline{<}} \ const .

Следствие 1 (1980, [I, 1], [III, 5]). В условиях выполнения предположений теоремы 1 множество эффективных точек непусто тогда и только тогда, когда непусто множество собственно эффективных точек.

Множество эффективных точек называют внешне устойчивым [I, 1], если для любого x \in X\, найдется такая эффективная точка x^*\, , что f_i(x^*) \ \underline{\underline{>}} \ f_i(x), \ \ i=1,2, \dots , m.

Следствие 2 (1980, [I, 1], [III, 5]). В условиях выполнения теоремы 1 множество эффективных точек является внешне устойчивым.

Далее рассмотрение ограничим случаем линейных критериев:

f(x) = ( \left \langle c^1,x \right \rangle , \left \langle c^2,x \right \rangle ,\dots ,\left \langle c^m,x \right \rangle),(1)

где через \left \langle a , b \right \rangle обозначается скалярное произведение двух n\, -мерных векторов, т.е.

\left \langle a , b \right \rangle = \sum_{i=1}^{n} a_i b_i .

Обозначим символом K\, выпуклый конус, порожденный векторами c^1, c^2, \dots ,c^m\,, символом aff \, K\, аффинную оболочку этого конуса, ri \, K\, - его относительную внутренность, 0^+(X)\, - рецессивный конус выпуклого множества X\, и (0^+(X))^0\, - поляру рецессивного конуса (по поводу этой терминологии см. книгу Рокафеллара Р. Выпуклый анализ. - М.: Мир, 1973).

Теорема 2 (1975, [III, 5]). Пусть вектор функция f\, линейна и имеет вид  (1), множество X\, непусто, выпукло и замкнуто. Предположим, что выполняется по крайней мере одно из следующих двух условий:
(i) aff \, K \supset aff \, (0^+(X))^0\, (это условие заведомо выполняется, если \dim K=n\,);
(ii) для любого z \in [ (0^+(X))^0 \setminus ri \, (0^+(X))^0] линейная функция \left \langle z , \cdot \right \rangle достигает максимума на множестве X\, .

Тогда собственно эффективные точки относительно f\, на множестве X\, существуют тогда и только тогда, когда (0^+(X))^0 \bigcap ri \, K \ne \empty.