"Чистая"
и прикладная математика

Математические модели в виде графов. Дерево решений. Дерево игры

Дерево решений

Дерево игры

Типы и принципы построения моделей в виде графов

Виды моделей в виде графа

Математические модели создаются с целью лучшего понимания изучаемого явления. Достаточно сложные системы невозможно анализировать без помощи упрощённых моделей. Исследование системы с перенесением его свойств на модель называется моделированием. Математическое моделирование позволяет абстрагироваться от физических и прочих специфических свойств объекта. Математическая модель - это упрощённое и самодостаточное в понятийном плане отображение реальности.

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

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

Любая математическая модель предполагает наличие объектов и взаимосвязей между ними.

Графы оказались очень удобным объектом для моделирования многих ситуаций и систем из жизни. Разберём два вида математических моделей в виде графов: дерево решений и дерево игры.

Дерево решений

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

Дерево решений строится в виде графа-дерева, обладающего следующими свойствами:

  • имеются вершины альтернативных решений, которые обычно отображаются в виде прямоугольников;
  • имеются вершины событий, которые обычно отображаются с помощью окружностей;
  • имеются вершины конечных решений (листья), которые обычно отображаются с помощью прямоугольников, имеющих другой цвет, чем вершины альтернативных решений;
  • вершина альтернативных решений вместе с дугами, выходящими из данной вершины, называется вилкой решений;
  • вершина событий вместе с дугами, выходящими из данной вершины, называется стохастической вилкой (стохастической - имеющей вероятностный характер, так как в процессе принятия решения учитываются вероятности каждого из событий);
  • каждой дуге вилки решений приписаны весы, которые характеризуют приобретения или убытки при реализации данного решения;
  • каждой дуге стохастической вилки приписываются весы, которые характеризуют вероятность соответствующего события, а также приобретения и убытки при реализации данного события.

При решении прикладных задач с помощью модели в виде дерева решений поступают следующим образом:

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

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

Строительная фирма собирается принять решение о строительстве жилого комплекса (ЖК) в элитном районе. Сначала требуется принять решение: проводить ли информационно-рекламную кампанию. Она стоит 500000 условных единиц (у.е.). Опыт показывает, что лишь в 25 % случаев этот шаг обеспечивает успех на рынке.

Если информационно-рекламная кампания успешна, требуется принять решение: строить ли большой или малый ЖК. Строительство малого ЖК обойдётся в 50000000, при этом можно построить 300 квартир. Строительство большого ЖК обойдётся в 200000000, при этом можно построить 900 квартир.

Имеются исследования прогноза спроса. Они показывают, что существует вероятность в 40 % того, что произойдёт падение спроса на элитное жильё.

По предварительным расчётам, средние цены на квартиры будут определяться следующим образом:

Большой ЖКМалый ЖК
Спрос снизится100 000150 000
Спрос не снизится250 000400 000

Рассчитано, что расходы фирмы перед и в период продажи всех квартир в ЖК составят 5000000, независимо от величины ЖК.

Требуется принять решение: проводить ли информационно-рекламную кампанию и начинать строительство ЖК.

Решение.

Строим дерево решений:

Последствия альтернативных решений получены при расчётах, которые приведены ниже.

Шаг 1 (не учитываются вероятности событий).

Малый ЖК

Спрос не снизится

ДоходыРасходыПрибыль
400000 * 300 = 12000000050000000 + 5000000 = 55000000120000000 - 55000000 = 65000000

Спрос снизится

ДоходыРасходыПрибыль
150000 * 300 = 4500000050000000 + 5000000 = 5500000045000000 - 55000000 = -10000000

Большой ЖК

Спрос не снизится

ДоходыРасходыПрибыль
250000 * 900 = 225000000200000000 + 5000000 = 205000000225000000 - 205000000 = 20000000

Спрос снизится

ДоходыРасходыПрибыль
100000 * 900 = 90000000200000000 + 5000000 = 20500000090000000 - 205000000 = -115000000

Шаг 2 (учитываются вероятности событий).

На этом шаге прогнозируемые приобретения фирмы рассчитываются с учётом вероятности событий, предшествующих альтернативам решений.

Расходы
Малый ЖК0,60 * 65000000 + 0,40 * (-10000000) = 35000000
Большой ЖК0,60 * 20000000 + 0,40 * (-115000000) = -34000000

Теперь следует рассчитать приобретения при вершине 3 (проводить информационно-рекламную кампанию). Для этого нужно рассчитать приобретения при вершинах 4 (неуспешная информационно-рекламная кампания) и 5 (успешная информационно-рекламная кампания).

Наступление события при вершине 5 (строительство ЖК) означает максимальную прибыль 35000000, которую только можно получить при выборе данного решения. Наступление события при вершине 4 (неуспешная информационно-рекламная кампания) означает убытки в 500000.

Теперь можно рассчитать приобретения при вершине 3 (проводить информационно-рекламную кампанию): 0,25 * 35000000 + 0,75 * (-500000) = 8750000 - 375000 = 8375000.

В результате выбирается следующая альтернатива: начать информационно-рекламную кампанию и готовиться к строительству ЖК, отдавая предпочтение малому ЖК.

Дерево игры

Дерево игры очень похоже на дерево решений.

Теория игр вообще занимается попыткой выразить особенности столкновения интересов через действия, которые имеют место в салонных играх. Правила любой салонной игры устанавливают последовательность вполне определённых ходов, причём каждый ход для данного игрока соответствует выбору одной из множества альтернатив.

В игре нужно учитывать все ходы, предшествующие данному ходу, и все возможные ходы, следующие за ним. Таким образом, значение каждого хода в игре зависит от других ходов. Если создать отвлечённое представление всех ходов игры и указать, какие выборы привели к каждому ходу, то можно узнать отвлечённую связь каждого хода со всеми другими ходами, которые повлияли на него или на которые он может повлиять.

Пример 2. В некоторой игре (на каком-то этапе партии) игроку 1 нужно выбрать между королём червей, двойкой пик и валетом бубен, а в другой игре игрок, также называемый игроком 1, должен выбрать между тем, чтобы пасовать, назначать игру или вистовать. В обоих случаях нужно выбрать между тремя альтернативами. Это можно представить на рисунке ниже.

Пример 3. Число, связанное с каждым ходом, указывает, какой игрок делает выбор на данном ходе. Следовательно, если имеется n игроков, то будут употребляться числа от 1 до n. Пусть n=4, тогда каждый ход, за исключением первого, назначается одному из игроков. Первому ходу приписывается обозначение "0". Ход с обозначением "0" является случайным ходом, как, например, тасовка карт перед партией покера. С каждым случайным ходом, который необязательно должен быть первым ходом, нужно связать распределение вероятностей или весов по нескольким альтернативным выборам. Если случайным ходом является бросание уравновешенной монеты, то в ходе имеются две альтернативы, и каждая из них может осуществиться с вероятностью 1/2.

Типы и принципы построения математических моделей в виде графов

Сформулируем основные принципы моделирования.

  1. Выбор модели существенно влияет на процесс решения задачи и на само решение.
  2. Степени детализации модели могут быть разными.
  3. Более подробная детализация означает бОльшую сложность модели.
  4. Лучшие модели - те, которые лучше отображают реальность.
  5. Желательно использовать одновременно несколько моделей.

Есть бесчисленное множество примеров, когда в явлении, системе или процессе усмотрели отношения в виде графа, реализовали математическую модель на основе этих отношений и эта реализация сделала анализ задачи и решение более эффективными. Приведём основные типы математических моделей в виде графов:

  • вершины и рёбра - физические объекты, объекты-рёбра физически связывают вершины;
  • вершины - физические или нефизические объекты, рёбра связывают вершины в зависимости от структурных или функциональных свойств вершин;
  • вершины - физические или нефизические объекты, возможно, в различных состояниях, зависящих от времени и развития, рёбра показывают временнУю, эволюционную или причинно-следственную связь между вершинами.

Есть два условия создания эффективной математической модели системы в виде графа.

  1. Определены важнейшие подсистемы или состояния моделируемой системы, которые отображаются в виде вершин графа.
  2. Определены важнейшие отношения между объектами-вершинами.

Чаще используются модели, в которых основную роль играют вершины графа, а не его рёбра.

Есть, однако, системы, для которых невозможно построить модели в виде графа. Обычно это системы, свойства которых непрерывны, например, атмосферные явления, потоки жидкостей и т.п. Таким образом, главное условие возможности построения модели в виде графа - дискретный (конечный, прерывный) характер системы, являения или процесса.

Системы со свойствами непрерывности целесообразнее моделировать с помощью уравнений математической физики.

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

Виды математических моделей в виде графа

Вместе с рассмотренными моделями дерева решений и дерева игры используются следующие математические модели в виде графа.

  1. Блок-схема компьютерной программы (вершины - команды, рёбра - переходы между команды), используемая для разработки и тестирования самой программы.
  2. Граф подпрограмм (вершины - подпрограммы, рёбра - порядок вызова подпрограмм), используемый для проектирования и анализа компьютерных программ.
  3. Граф структуры данных (вершины - данные или простейшие типы данных, рёбра - отношения между данными), используемый для проектирования и оптимизации структур данных.
  4. Граф зависимости команд машинного кода (вершины - команды, рёбра - зависимости между командами), используемый в оптимизационном компилировании и конвейеризации работы процессора.
  5. Граф процессов операционной системы (вершины - процессы операционной системы, рёбра - акты генерирования процессов), используемый в моделировании работы операционной системы.
  6. Граф конечного автомата (вершины - состояния автомата, рёбра - переходы), используемый в исследовании конечных автоматов и языков и в инженерии программного обеспечения.
  7. Граф утверждений математической теории (вершины - утверждения, рёбра - отношения логического следования), используемый для доказательства математических заключений и анализа математических теорий.
  8. Функциональный граф (вершины - элементы множества, рёбра - отношения логического следования), имеющий широкое использование в математике.
  9. Граф величин-зависимостей (вершины - численные величины и взаимосвязи между ними, рёбра - отношения вовлечённости величины), используемый в решении различных математических задач.
  10. Граф метрики (вершины - любые физические или нефизические объекты или их множества, рёбра - геометрическая, структурная, функциональная или эволюционная близость этих объектов), используемый для анализа больших множеств.
  11. Дерево решений (вершины - критические состояния, рёбра - решения), используемый в принятии решений в экономике, управлении, диагностике инженерных систем.
  12. Системный граф (вершины - компоненты системы, рёбра - взаимодействие компонент), используемый в проектировании и анализе систем.
  13. Граф обратных связей (вершины - параметры какого-либо процесса, ориентированные рёбра с весами "+" или "-" - зависимость изменений параметров, соответствующих вершинам), используемый в исследованиях изменений составных частей процессов или объектов.
  14. Граф причинно-следственных связей (вершины - состояния какой-либо системы, ориентированные рёбра - причинно-следственные связи), используемый в исследованиях больших систем и сложных процессов.
  15. Граф конфликтов (вершины - состояния какой-либо системы, рёбра - конфликты между состояниями), используемый в анализе систем.
  16. Граф игры (вершины - игровые состояния, рёбра - разрешённые правилами игры переходы между состояниями (ходы)), используемый в разработке победных стратегий в играх.
  17. Компьютерная сеть (вершины - компьютеры или коммуникационные узлы, рёбра - линии связи), используемая в проектировании и анализе компьютерных сетей.
  18. Социальный граф (вершины - люди или множества людей, рёбра - отношения знакомства, экономические отношения или другие отношения), используемый в анализе общества и планировании развития.
  19. Организационный граф (вершины - люди или множества людей, рёбра - отношения, характеризующие организации, например, частные фирмы, иерархии), используемый в создании организаций и управлении ими.
  20. Граф проекта (вершины - работы или состояния проекта, рёбра - отношения между работами или работы, соединяющие состояния), используемый в руководстве проектами.
  21. Генеалогическое древо (вершины - люди, рёбра - отношение "родители-дети"), используемый в личных исследованиях.
  22. Граф экономических агентов (вершины - экономические агенты - люди, фирмы и др., рёбра - экономические отношения), используемый в экономических исследованиях и планировании.
  23. Макроэкономический граф финансового потока (вершины - отрасли экономики, рёбра - финансовые потоки), используемый в экономических исследованиях и планировании.
  24. Граф дорог (вершины - города, рёбра - дороги), используемый в развитии транспортной сети.
  25. Граф улиц (вершины - перекрёстки, рёбра - улицы), используемый в анализе и планировании потока городского транспорта.
  26. Граф электрической цепи (вершины - электромагнитно-активные элементы, рёбра - провода и контакты), используемый в построении и анализе электрических счем.
  27. Цепь питания (вершины - породы животных, рёбра - отношения питания), используемый в анализе биосистем.
  28. Дерево эволюции (вершины - породы или популяции, рёбра - отношения эволюционного происхождения), используемый в биологии.
  29. Граф химических реакций (вершины - векторы количества химических веществ, рёбра - химические реакции), используемый в анализе химических реакций.
  30. Граф предшественников химического вещества (вершины - химические вещества, полученные в процессе производства, рёбра - изменения веществ-предшественников в процессе производства), используемый в химической промышленности.
  31. Граф реакционной способности химических веществ (вершины - химические вещества, рёбра - способности к реакции), используемый в анализе сложных химических реакций.
  32. Граф взрывоопасности (вершины - химические вещества, рёбра - возможности взрывной реакции между ними), используемый для нужд безопасности труда.
  33. Граф помех радиосвязи (вершины - радиостанции, рёбра - взаимное перекрытие полос радиоволн), используемый в планировании радиосвязи.
  34. Политический граф (вершины - государства, рёбра - границы), используемый в геополитике.
  35. Граф кровеносных сосудов (вершины - узлы кровеносных сосудов, рёбра - кровеносные сосуды), используемый в медицине.
  36. Граф нейронов (вершины - нейроны, рёбра - места соприкосновения нейронов), используемый в медицине.
  37. Граф приготовления кулинарного изделия (вершины - состояния готовности кулинарного изделия, рёбра - переходы между состояниями в процессе приготовлении), используемый в кулинарии.

Нет времени вникать в решение? Можно заказать работу!

Весь блок "Теория графов"

Понятие графа и отображение отношений в виде графа

Основные определения теории графов. Классы графов

Структуры данных для представления графов в памяти ЭВМ

К началу страницы