Основы математического моделирования социально-экономических процессов (стр. 9 )

Y1, Y2, Y3 і 0 X1, X2, X3 і 0

Решение этих задач симплексным методом дает оптимальные значения

X = {11/37, 4/37, 5/37}, Y = {8/37, 7/37, 5/37}

и экстремумы целевых функций, равные 20/37.

Отсюда V = 37/20, P = {11/20, 4/20, 5/20}, Q = {8/20, 7/20, 5/20}.

3. Итеративный метод решения матричных игр

Как мы показали выше, игры могут решаться методами линейного программирования. Здесь мы рассмотрим итеративный метод Брауна-Робинсон, обычно используемый при решении игр большой размерности.

Используется многократная реализация игры на основе знания предыстории с последовательным совершенствованием стратегий.

Для примера возьмем задачу, которую мы только что решили.

Пусть игрок 1 сделал выбор 1 с ожидаемыми выигрышами 1, 2, 3. Противник, стремясь минимизировать свой проигрыш, прибегнет к выбору 1 с ожиданием проигрыша 1, 4, 2. Игрок 1 в стремлении максимизировать свой выигрыш прибегнет к выбору 2, что даст ему надежду на суммарный выигрыш (1+4, 2+0, 3+1). Но тогда его противник найдет среди этих значений меньшее и прибегнет к выбору 2 с ожидаемым суммарным проигрышем (1+2, 4+0, 2+3) и т. д.

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

В результате 10 выборов для 1-го игрока частоты составили 0.6, 0.2, 0.2; для игрока , 0.3, 0.3; оценка цены игры в диапазоне от 1.7 до 1.9.

4. Многошаговые игры. Игры на выживание

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

Однако в реальной игре с ограниченными ресурсами политика игроков зависит от результата предыдущих действий и от длительности игры.

Соответственно для матричной игры

где Fk(A, B) - ожидаемый выигрыш игрока 1 в k последовательных реализациях при начальных ресурсах A и B и использовании оптимальной политики.

Пусть общий начальный ресурс игроков A + B = C и игра продолжается до разорения одного из игроков. Обозначим через F(A) ожидаемую вероятность выживания (шансы не разориться) игрока 1 при его начальном ресурсе А и оптимальной политике обоих игроков.

Тогда

F(A і 0) = 0,
F(A Ј C) = 1.

Ecли игра не обладает седловой точкой в пространстве чистых стратегий, то оптимальные значения вероятностей использования выборов соответствуют внутренним точкам множества планов (0 < P < 1, 0 < Q < 1) и напрашивается мысль прибегнуть к аппарату производных.

Пример. Рассмотрим игру на выживание с матрицей при полном капитале игроков С = 4.

Здесь в силу целочисленности данных берем целочисленные значения А от 0 до 4. Ecли обозначить вероятности соответствующих выборов игроков через P, 1-P, Q, 1-Q, то F(A Ј 0) = 0, F(A і 4) = 1,

Отыскиваем частные производные и строим системы уравнений для поиска оптимальных значений P(A), Q(A):

Решение приведенных систем дает

Подставляя полученные выражения в исходные выражения функций, имеем

Решая полученную нелинейную систему, имеем оценки

F(1)=0.3, F(2)=0.5, F(3)=0.7

и

P(1)=0.41, P(2)=0.5, P(3)=0.59, Q(1)=0.41, Q(2)=0.3, Q(3)=0.41.

5. Многошаговые игры. Игры погони

Простейшим примером таких игр может служить задача для двух игроков, расположившихся на прямой на расстоянии d. На каждом шаге игры игроки могут одновременно смещаться влево или вправо при полной информации о позиции друг друга После очередного шага игрок 2 уплачивает игроку 1 величину G(S), где S - расстояние между ними. С вероятностью A(d) игра может быть продолжена и с вероятностью 1-A(d) окончена.

Если обозначить через P1, P2, Q1, Q2 вероятности смещения игроков в ту или иную сторону, то одна из возможных формулировок задачи имеет вид

Существенно больший интерес может представить игра погони на плоскости или в пространстве, где устанавливается принципиальная возможность поимки одного игрока другим или отыскивается траектория, минимизирующая время поимки. Эти игры относятся к т. н. непрерывным многошаговым играм, решение которых сводится к дискретным моделям [18].

6. Статистические решения. Основные понятия

Теория статистических решений может быть истолкована как теория поиска оптимального недетерминированного поведения в условиях неопределенности. Современная концепция статистического решения выдвинута А. Вальдом и считает поведение оптимальным, если оно минимизирует риск в последовательных экспериментах, т. е. математическое ожидание убытков статистического эксперимента. В такой постановке любая задача статистических решений может рассматриваться как игра двух лиц, в которой одним из игроков является "природа".

Выбор наилучших решений в условиях неполной информации является одним из основных занятий людей.

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

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

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

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

Однако большинство процессов характеризуется "дурной неопределенностью" и невозможно найти законы распределения и другие вероятностные характеристики. В таких ситуациях приходится прибегнуть к экспертным оценкам.

Возникает и проблема выбора критерия оптимальности, поскольку решение, оптимальное для каких-то условий, бывает неприемлемым в других и приходится искать некоторый компромисс.

Пусть задан некоторый вектор S = (S1,S2,..,Sn), описывающий n состояний внешней среды, и вектор X = (X1,X2,..,Xm), описывающий m допустимых решений. Требуется найти вектор X* =(0,0,..,0, Xi,0,..,0), который обеспечивает оптимум некоторой функции полезности W(X, S) по некоторому критерию K.

Информация oб указанной функции представляют матрицей размерности m x n c элементами Wij = F(Xi, Sj), где F - решающее правило.

Рассмотрим типичный пример формирования такой матрицы

Планируется выпуск новой продукции, для чего необходимо закупить станки. Система оптовой торговли может поставить не более 50 станков; комплект поставки - 10 станков. Минимальный объем поставок - 20 станков. Соответственно, вектор решений об объеме поставок X = (20,30,40,50).

Ежегодный доход от продукции, снимаемой с одного станка, cоставляет 21.9 тыс. руб. Оптовая цена одного станка 4.775 тыс. руб., эксплуатационные расходы - 3.6 тыс. руб. Затраты на подготовку производства составляют 25.5 тыс. руб. и не зависят от числа станков и объема выпуска.

Пусть спрос пропорционален количеству продукции, снимаемой с S работающих станков, и для простоты ограничимся вектором состояний спроса S = (0,10,20,30,40,50).

Если решающее правило сформулировать как "доход - издержки", то можно рассчитать элементы матрицы полезности:

Wij = (2* min( Xi, SjXi - 25.5

Например

W11 = -(4.775 20+25.5) = -121,
W12 = (21.9-3.6) * 10-(4.775 20+25.5) = 62,
W13 = (21.9-3.6) * 20-(4.775 20+25.5) = 245,
W14 = W15 = 245 (спрос останется неудовлетворенным).

7. Выбор критерия принятия решения

Предположим, что в нашем распоряжении имеются статистические данные, позволяющие оценить вероятность того или иного спроса, и этот опыт может быть использован для оценки будущего. При известных вероятностях Pj для спроса Sj можно найти математическое ожидание W(X, S,P) и определить вектор X*, дающий

Если для вышеприведенного примера задать вектор P = (0.01, 0.09, 0.2, 0.3, 0.3, 0.1), то математические ожидания прибыли при разных выборах:

W1 =-121*0.01 + 62*0.09 + 245*0.2 + 245*0.3 + 245*0.3 + 245*0.1 = 224.87,

W2 = 305.22, W3 = 330.675, W4 = 301.12

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

7.1. Критерий Лапласа

В основе этого критерия лежит "принцип недостаточного основания".

Если нет достаточных оснований считать, что вероятности того или иного спроса имеют неравномерное распределение, то они принимаются одинаковыми и задача сводится к поиску варианта, дающего

Для нашего примера

W1 = (-121 + 62 + 245 + 245 + 245 + 245)/6 = 153.5,
W2 = 197.25, W3 =210.5, W4 = 193.5

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

7.2. Критерий Вальда

Критерий Вальда обеспечивает выбор осторожной, пессимистической стратегии в той или иной деятельности и его суждения близки к тем суждениям, которые мы использовали в теории игр для поиска седловой точки в пространстве чистых стратегий: для каждого решения Xi выбирается самая худшая ситуация (наименьшее из Wij) и среди них отыскивается гарантированный максимальный эффект

В нашем примере W = max(-121, -168.75, -216.5, -264.25) = -121, т. е. по этому критерию следует закупить 20 станков и максимальный возможный убыток не превысит 121 тыс. руб. (если бы мы включили и вариант отказа от покупки станков вообще, то этот критерий рекомендовал бы нам воздержаться от какой-либо деятельности, но "кто не рискует, тот не пьет шампанского").

Можно принять и критерий выбора оптимистической стратегии

где оценивается гарантированный выигрыш при самых благоприятных условиях. Для нашего примера W = min (245, 380.25, 515.5, 650.75)= 245.

7.3. Критерий Гурвица

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

где параметр a принимает значение от 0 до 1 и выступает как коэффициент оптимизма. Так в нашем примере при различных a значения W определяются таблицей:

При a=0.5 (равновероятных шансах на успех и неудачу) следует закупить 50 станков и ожидать прибыль порядка 193.25 тыс. руб.

При вероятности успеха 0.2 не следует закупать более 20 станков с надеждой, что убытки не превысят 47 тыс. руб.

7.4. Критерий Сэвиджа

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

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

Для нашего примера отыскиваем матрицу D, вычитая (-121) из первого столбца матрицы полезности, 62 из второго и т. д.

Наибольшее значение среди минимальных элементов строк здесь равно max[-405.75, -270.5, -135.25, -143.25]=-135.25 и, покупая 40 станков, мы уверены, что в худшем случае убытки не превысят 135.25 тыс. руб.

Таким образом, различные критерии приводят к различным выводам:

1) по критерию Лапласа приобретать 40 станков,

2) по критерию Вальда - 20 станков,

3) по критерию Гурвица - 20 при пессимистическом настроении и 50 в состоянии полного оптимизма,

4) по критерию Сэвиджа - 40 станков.

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

Модульная единица 2. Теория графов

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V, E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

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

Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.

Теория графов может рассматриваться как раздел дискретной математики (точнее – теории множеств), и тогда определение графа таково:

Граф – это конечное множество Х, состоящее из n элементов называемых вершинами графа, и подмножество V декартова произведения называемое множеством дуг.

Ориентированным графом G (орграфом) называется совокупность (Х, V).

Неориентированным графом называется совокупность множеств Х и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству Х.

Дугу между вершинами i и j, будем обозначать (i, j). Число дуг графа будем обозначать

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

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

Граф называется полным, если каждые две вершины его соединены одним и только одним ребром.

Граф, для которого из следует называется симметричным. Если из следует , то соответствующий граф называется антисимметричным.

Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.

Приведем ряд примеров приложений теории графов.

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

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

3. Обменные схемы, являющиеся моделями таких явлений как бартер, взаимозачёты и т. д. Вершины графа при этом описывают участников обменной схемы (цепочки), а дуги – потоки материальных и финансовых ресурсов между ними. Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями.

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

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

6. Модели организационных структур, в которых вершинами являются элементы организационной системы, а рёбрами или дугами – связи (информационные, управляющие, технологические и др.) между ними.

1. Степень вершины

Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат.

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

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

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

Если в графе с n вершинами в точности две вершины имеют одинаковую степень, то в этом графе всегда найдётся либо в точности одна вершина степени 0, либо в точности одна вершина степени

2. Маршруты, цепи, циклы

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

Если то маршрут замкнут, в противном случае открыт.

Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.

Простой путь – путь, в котором ни одна дуга не встречается дважды.

Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Цепью называется множество рёбер (в неориентированном графе), которые можно расположить так, что конец (в этом расположении) одного ребра является началом другого. Другое определение: цепь – последовательность смежных вершин. Замкнутая цепь называется циклом. Можно определить простые и элементарные цепи.

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

Простая цепь (цикл, путь, контур), содержащая все рёбра (дуги) графа называется эйлеровой цепью.

Если любые две вершины графа можно соединить цепью, то граф называется связным. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами.

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

3. Ориентированные графы

Если элементы множества Е графа упорядоченные пары, то граф называется ориентированным или орграфом.

Ребро графа G называется ориентированным, если одну вершину считают началом ребра, а другую – концом, на рисунке его изображают стрелкой между вершинами. Таким образом, граф, все рёбра которого ориентированы, называется ориентированным графом.

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

Степенью выхода вершины орграфа называется число выходящих из вершины рёбер.

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

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

Изолированной вершиной называется вершина, у которой и степень входа и степень выхода равна 0.

Источником называется вершина, степень выхода которой положительна, а степень входа равна 0.

Стоком называется вершина, степень входа которой положительна, а степень выхода равна 0.

Путём в ориентированном графе называется последовательность ориентированных рёбер, т. е. для орграфов цепь называется путём.

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

Замкнутый путь в ориентированном графе называется ориентированным циклом или контуром.

Длиной пути называется число рёбер в этом пути.

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

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

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

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

4. Изоморфизм графов

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

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

Алгоритм распознания изоморфизма двух графов и

1. Подсчитаем число вершин каждого графа (число вершин должно совпадать, в противном случае графы неизоморфные).

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

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

4. Выписываем подстановку, которая переводит граф в граф .

5. Плоские графы

Граф называется плоским, если на плоскости его можно изобразить так, что все пересечения его рёбер являются вершинами графа .

В качестве характеристики плоского представления графа вводится понятие грани.

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

6. Операции над графами

Рассмотрим графы и

а) Дополнением графа называется граф множеством вершин которого является множество а множеством его рёбер является множество

б) Объединением графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер является множество

в) Пересечением графов и называется граф множеством вершин которого является множество а множеством его рёбер является множество

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

7. Способы задания графов

Существуют три эквивалентных способа задания графов: аналитический, геометрический и матричный. Рассмотрим каждый из них.

Аналитический способ задания графов

Граф задан, если задано множество элементов V и отображение E множеств V в V. Отображение Е может быть как однозначным, так и многозначным.

Пусть дано множество которое имеет мощность

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

Другой формой аналитического способа задания является задание графа как совокупности множества элементов V и подмножества множества упорядоченных пар

Геометрический способ задания графов

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

Матричный способ задания графов

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