Указания к решению основных задач

Указания к решению основных задач

§ 1

1.Множество альтернатив – площадки около города, где постройка аэропорта нужного размера представляется возможной. Возможные критерии для оценки вариантов расположения аэропорта:

1) стоимость постройки. Желательно построить аэропорт с заданной пропускной способностью за наименьшую возможную цену.

2) расстояние от города. Желательно, чтобы поездка пассажиров от аэропорта в город и обратно занимала наименьшее время.

3) минимальное шумовое воздействие. Количество людей, подвергающихся нежелательным шумовым воздействиям, должно быть минимально.

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

В соответствии с выбранным принципом оптимальности холдинг «A&A» принял решение провести испытание в три этапа.

Первый этап – тестирование общих интеллектуальных способностей участников. На этом этапе решается задача выбора из множества W нескольких альтернатив (студентов) в соответствии со следующим принципом: число перешедших во второй тур не должно превышать m, число набранных по тесту баллов каждым из студентов должно быть не ниже n. Результатом выбора является формирование .

Второй этап – оценка реферата, посвященного экономическим проблемам региона. Работы оцениваются членами жюри (экспертами) по следующим критериям: 1) научная новизна и актуальность (в т.ч. соответствие проблематике); 2) обоснованность (реалистичность) полученных результатов; качество работы (используемый аппарат, оформление и т.п.); 3) наличие практических рекомендаций, их обоснованность и региональная направленность; 4) ожидаемая для региона эффективность внедрения полученных результатов.

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

. На основе данного принципа отбирается группа финалистов.

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

§ 2

1.В отношение R входят пары элементов

Матрица смежности для отношения R:

Нижние сечения элементов: , , , , .

Верхние сечения элементов: , , , , .

2. Для доказательства п. 1) достаточно доказать, что если , то и если , то .

, а так как , то , что и требовалось доказать. Аналогично доказывается второе условие.

1) Докажем, что .

Рассмотрим , следовательно, , а так как , то , а значит, , т.е. .

Аналогично доказывается, что .

3.Докажем, что .

Пусть , то есть .

Равенство доказывается аналогично.

4. = =R.

Аналогично в матричном виде: =1- =1-1-(- )= .

5. Докажем, что = .

Рассмотрим .

Если , то это равносильно тому, что .

Следовательно, = .

п. 2) доказывается аналогично п.1.

6. . Аналогично доказывается и вторая формула.

7.Докажем, что .

= , что и требовалось доказать.

8. Пусть . Покажем, что в этом случае =1.

По определению произведения : и , то есть, , .

Пусть , тогда хотя бы одно слагаемое в формуле (*) равно 1, т.е. существует . Тогда , и , т.е. , что и требовалось доказать.

9.Рассмотрим формирование элемента матрицы .

Аналогично: .

Аналогично формируются остальные элементы матрицы. Итоговая матрица имеет вид:

10. Предположим, что R симметрично. Докажем, что .

Так как по определению симметричного отношения, то достаточно показать, что .

Рассмотрим , тогда в силу симметричности R , следовательно, .

Обратно, если , то , следовательно, R – симметрично.

11. Предположим противное: R не является антирефлексивным. Тогда существует такое, что . Из определения обратного отношения это эквивалентно тому, что , следовательно, , т.е. Æ, что противоречит асимметричности R.

12. 1) Для точки a отношения выполнено: , , , следовательно, a – мажоранта данного отношения. Аналогично b- миноранта ( , , ). Точка c не является мажорантой, так как не выполнено, и не является минорантой, так как не выполнено. Максимумов и минимумов у данного отношения нет.

2) Мажорантами отношения являются a и c, так как , , и , , . Аналогично b- миноранта.

3) Точка a является максимумом, так как , , . Элементы b,c – миноранты.

13. Пусть R – отношение частичного порядка.

Предположим противное: существуют два максимума по отношению R: и . Тогда , для любого . Следовательно, и . Так как R – антисимметрично, то и тогда и только тогда, когда , получили противоречие. Следовательно, максимум по частичному порядку единственен.

Для произвольного R данное утверждение не всегда верно. Например, рассмотрим R:

a b . Точки a, b – максимумы.

14. Предположим противное: пусть a – максимум по отношению R, b- мажоранта.

a – максимум по отношению R, тогда , . Следовательно, ;

b – мажоранта, тогда , . Следовательно, . Тогда и, следовательно, Æ. Но так как по определению =Æ, то получили противоречие, следовательно, максимумы и мажоранты одновременно существовать не могут. Аналогично доказывается п. 2).

15. 1) Пусть . Тогда : . Это равносильно тому, что выполнено , следовательно, - не выполнено. Из последнего следует, что не выполнено . Это эквивалентно тому, что . Таким образом, .

Аналогично доказывается п.2).

§ 3

1.Опишем каждое из перечисленных в условии бинарных отношений, воспользовавшись определением сужения и двойственного отношения:

, тогда , .

С другой стороны: , тогда , что и требовалось доказать.

2.Докажем п. 1). Для доказательства воспользуемся задачей 15 § 2 и задачей 1 § 3. Рассмотрим , , , - определяемые, как и в задаче 1 из §2. , тогда в силу произвольности выбора множества X получаем, что . Пункт 2) доказывается аналогично.

3.Рассмотрим . Бинарные отношения и ( ) зададим графами:

Построим функцию , определив ее на каждом из подмножеств .

a) . .Так как , то .

b) . Так как не выполнено, то Æ;

c) . Так как не выполнено, то ; так как не выполнено, то . Следовательно, =Æ.

строится аналогично:

, Æ, Æ.

Таким образом, , но .

4.Рассмотрим функцию выбора, определяемую на подмножествах множества следующим образом: , =Æ, .

Предположим противное: существует отношение такое, что . Построим данное отношение.

a) . . Следовательно, для любого элемента выполнено: , т.е. .

b) . =Æ, следовательно, в множестве не существует элемента такого, что , , т.е. для любого . Следовательно, .

c) . , следовательно, , , но из п.b) следует, что для R должно быть выполнено . Получили противоречие. Следовательно, такого отношения R не существует и функция выбора не является нормальной.

Заметим, что аналогично можно доказать, что не существует такого бинарного отношения R, что .

5.1) Для функции построим : .

a) : ;

b) : ;

c) : , ;

, .

Граф отношения имеет вид:

Построим : .

a) : ;

b) : ;

c) : , ; , .

Граф отношения имеет вид:

x y

2) Для функции построим : .

a) : ;

b) Æ: ;

c) : , ;

, . Но из п. b). Отношение и, следовательно, построить невозможно, данная функция не является нормальной.

1) Для функции построим : .

a) : ;

b) Æ: ;

c) : , ;

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

( выполнено)

x y

( не выполнено)

x y

Аналогично строится :

a) : ;

b) =Æ: ;

c) : , ;

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