Контрольные вопросы и задания

1. Придумать для рассмотренного выше примера такие множества Y и Z, чтобы нарушалось условие С.

2. Пусть на элементах множества Х задана векторная функция F(x) = { f ₁(x), f ₂(x),..., f _n(x) }.

Механизм голосования определяется так: если f _i (х) > f _i(y), то i-й избиратель голосует за кандидата х против кандидата у. Записать выражение для функции выбора, соответствующей механизму выбора по большинству голосов.

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

4. На множестве Х = {1, 2, ... 5} задано бинарное отношение R с помощью матрицы [R]:

[R] =

Построить на Х выбор согласно механизмам:

а) доминирования по R; б) блокировки по R;

в) блокирующих ограничений при u = 5; г) турнирному.

5. Пусть G_R(х) и H_R(х) – соответственно верхний и нижний срез отношения R в точке х; |G_R(х)| и |H_R(х)| – их мощности. Построить выбор на множестве Х = {2, 3, ..., 15} согласно следующим механизмам:

1) C₁(X) = { xХ | max |H_R(х)| }; 2) C₂(X) = { xХ | min |G_R(х)| }.

Отношение R определяется условиями:

а) б)

6. Доказать, что для любого асимметричного отношения R выполняется включение С_R(Х)  С^R(Х). Привести пример, когда это включение строгое. Показать, что условие асимметричности, вообще говоря, не является необходимым, т.е. из С_R(Х)  C^R(X) не следует асимметричность R.

7*. Доказать, что для функции выбора, заданной на предъявлении Х и определяемой скалярным максимизирующим механизмом, выполняются следующие условия:

а)   x, y  C(X) f(x) = f(y) = f _max;

б)   z  X\C(X) f(z) < f _max.

8*. Доказать, что функция выбора, определяемая скалярным оптимизирующим механизмом удовлетворяет условию константности.

9*. Доказать, что если функция выбора на конечном множестве А определяется механизмом блокировки по асимметричному транзитивному бинарному отношению R, то

 х  А\ C^R(A)   y  C^R(A) : (y, x)  R .

Иными словами, для любого элемента х, не попавшего в выбор, существует элемент y, лучший, чем х, в смысле отношения R.

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

а) f ₀ = 2x₁² + x₂² – 2x₁x₂ + 6x₁ – 11x₂  min

 0  x₁  6;   0  x₂  7;

x₁² + (x₂ – 7)²  36.

б) f ₀ = 2x₁² + x₂² – 2x₁x₂ – 4x₁ – 6x₂  min

0  x  9; 0  x₂  4;

x₁² + (x₂ – 4)²  81.

Примеры решения

Задача 7.

Выберем два произвольных элемента x,y С(Х). Очевидно, что f(x) = f(y). В противном случае, например при f(x) > f(y), оптимальным был бы элемент х, а y – не был. Поскольку множество С(Х) состоит из элементов, доставляющих максимум f, то в этом случае элемент y не попал бы в выбор С(Х). Условие а) доказано.

Для доказательства условия б) введем на множестве Х бинарное отношение I: xIy  f(x) = f(y). Нетрудно убедиться, что отношение I – эквивалентность. Следовательно, множество Х можно разбить на классы эквивалентности, на которых функция f постоянна. По доказанному условию а), выбор С(Х) целиком содержится в одном из таких классов.

Выберем произвольный элемент zX \ C(X). В силу определения С(Х), f(z)  f(x), где х – произвольный элемент С(Х). Но равенства быть не может, т.к. в этом случае, в силу произволь-ности z, все множество Х состояло бы из одного-единственного класса эквивалентности и f(x) была бы постоянна на нем. Ясно, что такого быть не может. Полученное противоречие доказывает условие б).

Задача 9.

Предположим противное, т.е. существует такой х  А\ C^R (А), что (y, x)  R для любого y  C^R(А). Тогда либо х  C^R(А), что невозможно по предположению, либо существует такой z₁  А\ C^R(А), что (z₁, x)  R. Т.е. если элемент х не доминируется никаким элементом из C^R(А), то он должен доминироваться некоторым z₁ из А\C^R(А). В противном случае получим, что х  C^R(А), а это противоречит предположению. Но, в свою очередь, z₁ должен доминироваться либо некоторым z₂  А\C^R(А), либо некоторым t  C^R(А), так как иначе получим z₁  C^R(A), что невозможно в силу определения z₁. Если верно второе предположение, то, в силу транзитивности R, х доминируется элементом t из множества C^R(А), что невозможно. Следовательно, верно первое предположение о существовании z₂  А\C^R(А).

Продолжая эти рассуждения, получим последовательность точек z_i  A\C^R(А), таких, что z_i R z_{i -1} и ни одна из них не доминируется никакой точкой из C^R(А), т.к. иначе, вследствие транзитивности R, получится, что х доминируется элементом C^R(А), что невозможно по предположению.

Поскольку R асимметрично и транзитивно, то оно и ациклично. Значит, в этой последовательности не может быть повторяющихся элементов. Поэтому, в силу конечности A, последовательность должна оборваться на элементе z_n  А\C^R(А), для которого уже не найдется доминирующего элемента множества А\C^R(А). Но он не может доминироваться и элементом C^R(А), так как тогда вследствие транзитивности R получим, что и x доминируется этим элементом . Значит, z_n недоминируем на A и, следовательно, должен принадлежать C^R(А), что противоречит условию z_n  А\C^R(А) . Полученное противоречие доказывает утверждение задачи.