Глава 15. Бинарные отношения в критериальном пространстве

ДИСКРЕТНЫЕ МАТЕМАТИЧЕСКИЕ МОДЕЛИ

НАЧАЛЬНЫЕ ПОНЯТИЯ И СТАНДАРТНЫЕ ЗАДАЧИ

Учебное пособие

Александр Рубчинский

Национальный исследовательский университет «Высшая школа экономики»

Международный университет природы, общества и человека «Дубна»

Москва

ПРЕДИСЛОВИЕ

«Труден первый шаг и скучен первый путь.

Преодолел я ранние невзгоды. Ремесло

Поставил я подножием искусству;

Я сделался ремесленник: перстам

Придал послушную, сухую беглость

И верность уху»,

говорит Сальери у Пушкина. Следует подчеркнуть, что без такой, на первый взгляд, рутинной, работы невозможно не только какое-либо творчество, но даже и сколько-нибудь заметное продвижение в любой разумной профессиональной деятельности.

Конечно, математика не является исключением из этого общего правила. Обучаться любо-му искусству можно на примерах и подражании. И в той степени, в какой математика является искусством (а она им является, на мой взгляд, в значительной степени), именно так – на приме-рах и подражании – должно быть основано математическое образование, особенно на началь-ном и среднем уровне. Применительно к более конкретным вещам, мне представляется, что не-обходимо уделять значительно бóльшее внимание обучению техническим аспектам математи-ки. Ещё конкретнее это значит, что следует уделять внимание методам решения разнообразных стандартных задач, чтобы студент видел, что математика позволяет упрощать ситуации, а не усложнять их (если речь не идёт о наиболее «крутых» математических олимпиадах).

Несмотря на множество книг по дискретной математике и дискретным моделям (часть которых активно использовалась при подготовке предлагаемого материала), книги, в которой подробные определения основных понятий сопровождаются десятками примеров и сотнями стандартных задач почти по каждой теме, просто нет. Мой опыт в преподавании большого чис-ла курсов по этой тематике – от основ дискретной математики до математических моделей и методов принятия решений – говорит о том, что преодолеть естественный страх и скованность большинства студентов можно только одним способом. Надо давать такие задания, которые «получаются», о которых не говорят «вообще не понятно, что и как здесь делать». Только на базе освоения таких простых и подробно описанных заданий можно – для части студентов – пе-реходить к более серьёзным вещам.

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

1. Что является содержанием предлагаемого материала?

2. Для кого предназначен этот материал?

3. Чему могут научиться предполагаемые читатели?

Постараюсь дать мои ответы.

1. Предлагаемое пособие посвящено дискретным математическим моделям – в первую очередь, решению разнообразных стандартных задач, в которых надо что-то посчитать, найти, построить и т.д., но не доказать. Я совсем не против доказательств как таковых. Просто кажется, что интуитивное представление об элементарных функциях и их графиках (которое есть даже у слабых студентов) помогает при изучении математического анализа, если не при решении задач на «доказательства», то хотя бы для понимания доказательств из учебника. Та-кого интуитивного представления о дискретных объектах: кортежах, графах, таблицах, булевых функциях, кодировании, бинарных отношениях, функциях выбора, индексах влияния, стратеги-ях в играх и т.д. – у обычного школьника, поступившего в ВУЗ, совсем нет. И тем более нет ни-какого представления о том, как «работают» эти (да и многие другие) дискретные понятия.

Более того, сам характер дискретных моделей и связанных с ними рассуждений ориенти-рован больше на алгоритмы, чем на что-либо другое. Основной вопрос состоит не в том «как это доказать», а в том, «как это сделать». Да и сами доказательства в дискретной математике в большинстве случаев представляют собой, по сути дела, алгоритмы. Поэтому материал посо-бия, кроме введения и объяснения многих новых и непривычных понятий, содержит большое число алгоритмов – от совсем очевидных, но всё же специально выделенных именно как алго-ритмы, правил выполнения теоретико-множественных операций, до достаточно сложных алго-ритмов Форда-Фалкерсона, Дейкстры, нахождения равновесий в биматричных играх, построе-ния устойчивых паросочетаний, различных правил пропорционального представительства, агрегации индивидуальных предпочтений и сравнения векторных оценок методом Подиновско-го. Не только упомянутые, но все другие рассматриваемые алгоритмы не просто излагаются и поясняются, но подробно расписываются «в числах» в обозримых и доведённых до конца при-мерах.

2. Конечно, хотелось бы сказать, что пособие может быть полезным для студентов, магис-тров и аспирантов, обучающихся по математическим, программистским, экономическим, уп-равленческим и многим гуманитарным специальностям. Но это не так. Выдающийся математик Питер Халмош в своей известной статье «Как писать математические книги» призывал авторов чётко определять предполагаемую аудиторию. Очень выразителен один из его советов по этому поводу – «книги, нужные всем, не нужны никому».

Аудитория предполагаемого пособия вполне определена. Она состоит из студентов бака-лавриата и магистратуры, обучающихся по специальностям, попадающим между точными, ес-тественными и инженерными науками, с одной стороны, и гуманитарными науками, с другой. В этих специальностях – экономике, менеджменте, социологии, политологии, государственном и муниципальном управлении, бизнес-информатике и др, – всё в бóльшей степени используется не традиционная математика с точными количественными зависимостями, а формально более простая математика, оперирующая более наглядными и качественными дискретными моделя-ми. В различных ВУЗах для студентов этих или близких к ним специальностей читаются курсы с названиями «Моделирование и управление», «Методы оптимальных решений», «Математи-ческие методы моделирования социальных процессов», «Анализ политической и политологи-ческой информации», «Методы анализа и обработки данных для принятия управленческих ре-шений», «Математика конфликтов», «Интеллектуальные системы поддержки управленческих решений» и пр. Здесь перечислены только некоторые курсы, которые я читал, начиная с 2006 г. в Академии внешней торговли, университете «Дубна» и Высшей школе экономики. Учебных пособий, учитывающих реальные нужды этой аудитории и хоть как-то покрывающих указан-ные курсы, практически нет. Частичным исключением является книга Ф.Т. Алескерова, Э.Л. Хабиной и Д.А. Шварца «Бинарные отношения, графы и коллективные решения», которая вышла уже двумя изданиями. Однако её структура, излагаемый материал и цели далеко не охватывают весь упомянутый выше набор курсов и специальностей, не говоря о многих других. Именно это обстоятельство – отсутствие необходимых для работы материалов – и иниции-ровало подготовку настоящего пособия.

3. Как уже говорилось, пособие не рассчитано на математиков и программистов. Тем не менее, представляется, что часть выпускников по упомянутым выше «промежуточным» – меж-ду математиками и гуманитариями – специальностям будет встречаться в своей профессиональ-ной деятельности – и не только в научной – с самыми различными дискретными моделями. По-этому студенты должны получить не только формальное представление о подобных моделях. Они должны привыкнуть к ним («понять – это значит привыкнуть»), не бояться их и уметь ра-ботать с ними, точнее, со связанными с такими моделями алгоритмами. Именно поэтому цент-ральной и наиболее важной частью пособия являются многочисленные таблицы и рисунки для «ручной» реализации алгоритмов в небольших размерностях. Только проделав необходимые операции собственными руками, пропустив их перед этим через собственную голову, можно действительно освоить описанный в пособии простой, но разнообразный и непривычный для большинства материал. И уже зная, что, как и зачем делают эти алгоритмы, можно значительно более осознанно и эффективно использовать разнообразное программное обеспечение для ре-шения тех же самых или даже других дискретных задач в реальных размерностях. Таким обра-зом, освоение изложенных в пособии алгоритмов работы с дискретными моделями и представ-ляет собой ответ на третий из поставленных вопросов. Ещё раз стоит повторить, что обучение на примерах и подражании – основной путь начального освоения любой разумной области деятельности.

Стоит остановиться на некоторых технических вопросах. Пособие состоит из 20-и глав с независимой нумерацией формул, примеров, рисунков и т.д. внутри каждой главы. При ссылках на материал из любой другой главы к номеру добавляется отделённый дефисом (-) номер главы. Главы сгруппированы в 4 части, но номера частей при ссылках не указываются. Предметные указатели завершают каждую главу, а небольшие списки литературы – каждую часть. Концы примеров, утверждений, заданий и пр. отмечены знаком ■

Следует сказать, что данное пособие предполагает некоторое продолжение. Предполагает-ся подготовка более «продвинутого» пособия по дискретным моделям, в которой будет и более сложный материал, и задачи разной степени трудности «на доказательства», и более структури-рованное изложение, определяемое одной основной задачей системного анализа – задачей дос-тижения цели. Предполагается также и ещё одно, важное для меня (надеюсь, интересное и для других) пособие, посвящённое реальным прикладным задачам и игровым лабораторным рабо-там, связанными с некоторыми из приложений. В нём предполагается отразить опыт моей (и не только моей) работы с реальными прикладными проектами. Но всё это, как писал в своих днев-никах Л.Н. Толстой, задумывая новые произведения – ЕБЖ (если буду жив).

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

ОГЛАВЛЕНИЕ

Предисловие

Часть 1. Элементы математического языка ……...……………………………………………6

Глава 1. Высказывания ……….………………………………………………………………7

Глава 2. Множества …...………………………………………………………………………24

Глава 3. Кортежи …………...…………………………………………………………………32

Глава 4. Высказывательные формы и кванторы ………...………………………………40

Глава 5. Булева алгебра ………………………………………………………………………49

Часть 2. Оптимизация на графах ………………………………………………………………50

Глава 6. Элементы теории графов …….……………………………………………………51

Глава 7. Потоки в сетях ………………………………………………………………………73

Глава 8. Кратчайшие пути...…………………………………………………………………90

Глава 9. Паросочетания ……………………………………………………………………..113

Глава 10. Многошаговая оптимизация ……...……………………………………………123

Часть 3. Взаимодействие: конфликты и сотрудничество …………………………………144

Глава 11. Матричные игры …………..…………………………………………………….145

Глава 12. Другие игровые модели …………………………………………………………161

Глава 13. Неигровые модели взаимодействия..………………………………………….180

Часть 4. Принятие решений ……...……………………………………………………………202

Глава 14. Бинарные отношения ……………………………………………………………203

Глава 15. Бинарные отношения в критериальном пространстве

Дата добавления: 2015-10-16