математическое моделирование / Вопрос 38 39 40

38.Понятие сетевого графика. Основные понятия и определения. Критический путь. Резервы времени выполнения работ.

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

Составляющие сетевого графика.

Событие - геометрическая фигура, например, круг с шифром внутри.

Работа (с затратой времени) – стрелка или направленная дуга.

Фиктивная работа ( без затрат времени) – пунктирная стрелка.

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

Исходное событие(исток)- первоначальное событие(обозначается I).

Завершающее событие(сток) - конечное событие (обозначается С).

Шифр работы- (i,j), где i – шифр события начала работы, j– шифр события окончания работы.

Путь – последовательность работ, в которой конечное событие одной работы совпадает с начальным событием следующей (обозначается (i,j)- путь между событиями i и j).

Продолжительность работы - t_ij

Длина пути – сумма продолжительностей работ пути.

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

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

Полный путь – путь от истока к стоку.

Путь, предшествующий событию s – путь (I,s).

Путь, последующий за событием s – путь (s,C).

Характерные ошибки.

1. Работа не должна иметь одинаковых шифров, т.е. два события не должны быть соединены более, чем одной стрелкой.

2. В сети должно быть только одно тупиковое событие – сток (обозначается C).

3. В сети должно быть только одно начальное событие – исток (обозначается I).

4. В сети не должно быть циклов.

Свойства сетевых графиков.

1. Ни одно событие не может произойти ранее окончания всех входящих в него работ.

2. Ни одна работа, выходящая из данного события, не может произойти ранее данного события.

Правильная нумерация.

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

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

Шаг 0. Истоку присваивается ранг 0.

Вычеркиваем все работы, выходящие из события 0.

Шаг k. Всем оставшимся событиям без входящих дуг присваиваем ранг k.

Вычеркиваем все работы, выходящие из событий k.

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

Параметры сетевого графика.

Критический путь – путь максимальной длины от истока к стоку.

А) Сроки событий и работ.

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

,

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

,

,

.

Самый ранний срок начала работы

.

Самый ранний срок окончания работы

.

Самый поздний срок начала работы

.

Самый поздний срок окончания работы

.

Б) Резервы времени.

Резерв времени события - это промежуток времени, на который может быть отсрочено свершение этого события.

.

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

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

.

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

Вопрос № 39. Основные понятия теории игр.

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

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

От реального конфликта игра отличается тем, что ведется по определенным правилам. 

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

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

Классификация:

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

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

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

4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).

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

6.  По виду описания игры подразделяются на позиционные игры (или игры в развернутой форме) и игры в нормальной форме. Позиционные игры задаются в виде дерева игры. Но любая позиционная игра может быть сведена к нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. В позиционных играх ходы делаются в дискретных моменты времени. Существуют дифференциальные игры, в которых ходы делаются непрерывно. Эти игры изучают задачи преследования управляемого объекта другим управляемым объектом с учетом динамики их поведения; поведение объектов описывается дифференциальными уравнениями. Существуют также рефлексивные игры, которые рассматривают ситуации с учетом мысленного воспроизведения возможного образа действий и поведения противника

7. Если любая возможная партия некоторой игры имеет нулевую сумму выигрышей f_i, i=1,N всех N игроков (), то говорят об игре с нулевой суммой. В противном случае игры называются играми с ненулевой суммой. Очевидно, что парная игра с нулевой суммой является антогонистической, так как выигрыш одного игрока равен проигрышу второго, а следовательно цели этих игроков прямо противоположны. Конечная парная игра с нулевой суммой називается матричной игрой. Такая игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответвует номеру применяемой стратегии первого игрока, столбец - номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока). Конечная парная игра с ненулевой суммой называется биматричной игрокой. Такая игра описывается двумя платежными матрицами, каждая для соответствующего игрока.

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

Классификация деловых игр

1. По времени проведения:

   1. без ограничения времени;

   2. с ограничением времени;

   3. игры, проходящие в реальное время;

   4. игры, где время сжато.

2. По оценке деятельности;

   1. балльная или иная оценка деятельности игрока или команды;

   2. оценка того, кто как работал, отсутствует.

3. По конечному результату:

   1. жесткие игры – заранее известен ответ (например, сетевой график), существуют жесткие правила;

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

4. По конечной цели:

   1. обучающие – направлены на появление новых знаний и закрепление навыков участников;

   2. констатирующие - конкурсы профессионального мастерства;

поисковые – направлены на выявление проблем и поиск путей их решения.

Вопрос № 40. Примеры моделирования конфликтных ситуаций в экономике

Моделирование конфликтных ситуаций в экономике 

      Большинство  задач финансово-экономической сферы  сводится к необходимости принятия  решения.

      Проблема  в том, что принимать решения  приходится в условиях неопределенности.

      Неопределенность  связана:

      - с сознательной деятельностью  конкурентов;

      - с риском, в котором необходимо  принять решение;

      - неопределенность целей задачи  и др.

 

Моделирование конфликтных ситуаций в экономике 

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

    В  условиях частичной или полной  неопределен-ности результаты анализа  не обладают однозначностью. 

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

Черты  конфликтной ситуации:

    - наличие заинтересованных сторон

    - наличие набора возможных действий  у каж-    дой из сторон

    - наличие своих интересов у  каждой стороны.

Игры с природой

• Определение. Игра, в которой осознанно действует только один из игроков, называется игрой с природой.

• Природа может принимать одно из своих возможных состояний и не имеет целью получение выигрыша.

• Игра с природой представляется в виде платежной матрицы, элементы которой – выигрыши игрока А, но не являются проигрышами природы П.

• Имеем. Игрок А, SА={p1,p2,…,pm}, FA(P,Пj)

• Природа П с состояниями SП={п1,п2,…,пn}

Игры с природой

Игры с природой

• Определение. Показателем благоприятности состояния Пj природы П для увеличения выигрыша называется наибольший выигрыш игрока А при этом состоянии природы, т.е. наибольший элемент в j-ом столбце платежной матрицы: βj=max(aij), j=1,2,…,n.

• Для характеристики «удачности» применения игроком стратегии Ai в состоянии природы Пj вводится понятие риска.

• Определение. Риском rij игрока А при выборе стратегии Аi называется разность между показателем благоприятности βj в состоянии природы Пj и выигрышем аij: rij = βj-aij.

• Риск – упущенная возможность получения максимального выигрыша в данном состоянии природы.

• Из определения следует: rij ≥ 0.

• Определение. Верхняя граница рисков для каждого состояния природы: wj=min(aij), j=1,2,…,n.

• Или Wi –минимальный выигрыш при данном состоянии природы

• Колебание выигрыша в заданном состоянии природы: Δrj=βj-wj.

• Если aij= Wi – то риск является максимальным. Следовательно по критерию риска эта стратегия наихудшая

• Если aij= βj (rjj=0), то стратегия Ai - безрисковая

• Каждой платежной матрице игры можно поставить в соответствие матрицу рисков.

• Обратное не верно.