183753 (584785), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

tij(ро) , tij(по) - ранний и поздний сроки окончания работы;

R(L) - полный резерв времени пути;

Rij(п) - полный резерв времени работы;

- частные резервы времени.

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

Продолжительность пути t(L) есть сумма продолжительности работ, составляющих этот путь.

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

Рассмотрим один из них.

Введем ряд дополнительных условий. Если сетевой график не содержит отрезка, соединяющего работы i и j, то считаем tij = - . Далее положим tii = 0. Тогда с математической точки зрения задача состоит в следующем: найти такой путь , где Еj - работы, n - число работ, при котором величина достигает максимума.

В основе метода лежит метод динамического программирования. Обозначим через vi (i = 1, 2, ..., n-1) величину максимального пути от вершины i до конечной вершины. (Предполагается, что вершины занумерованы так, что начальная имеет номер 1, а последняя, завершающая, ‑ номер n).

Поиск критического пути осуществляется в несколько этапов.

На первом этапе определяем величины:

, i = 1, 2, ..., n-1;

, i = 1, 2, ..., n-1.

Ясно, что они выражают продолжительности времени, необходимого для того, чтобы достичь вершины n от i-ой вершины за один шаг.

Далее переходим к вычислению:

, i = 1, 2, ..., n-1; , j = 1, 2, ..., n,

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

Рассуждая аналогично, шаг за шагом, вычисляем:

, i = 1, 2, ..., n-1,

, j = 1, 2, ..., n,

до тех пор, пока не окажется, что выполнены условия:

, i = 1, 2, ..., n.

Найденное значение vi^(k) будет выражать величину критического пути, соединяющего первую и n-ую вершины, а число k укажет, из скольких звеньев этот путь состоит. Можно указать, что если график состоит из n вершин, то для нахождения критического пути достаточно n-2 этапа последовательных вычислений.

Тема 8. Методы теории игр

1. Основные понятия теории игр.

2. Подход к решению задач теории игр.

Краткое содержание темы

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

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

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

Игра может быть парной или множественной (многие участники).

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

Процесс (развитие) игры происходит в результате последовательного выполнения тех или иных ходов.

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

Задание пары стратегий (А и В) (своей и противника) в парной игре полностью определяет ее исход, т.е. выигрыш одного и проигрыш другого (при случайных ходах определяются математические ожидания выигрыша и проигрыша).

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

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

Если первая сторона имеет m стратегий, а вторая – n, то имеем дело с игрой mn.

Рассмотрим игру mn со следующей матрицей:

где Ai (i = 1, 2, ..., m) - стратегии первого игрока, Bj (j = 1, 2, ..., n) - стратегии второго игрока, аij - плата в сеансе игры со стратегиями Ai и Bj.

Если первый игрок применяет стратегию А_i, то другой будет стремиться к тому, чтобы выбором соответствующей стратегии свести выигрыш первого игрока к минимуму. Из "арсенала" - набора своих стратегий второй выбирает такую стратегию В_j, чтобы величина а_ij была бы минимальной, т.е. если _i есть величина этого минимума, то:

.

C точки зрения первого игрока (при любых ответах противника) целесообразно стремиться найти такую стратегию, при которой  _i будет обращаться в максимум. Пусть этот максимум равен . Он называется нижней ценой игры. Так как значение  вычисляется по формуле: или , то его называют максимином. Ему соответствует максиминная стратегия (их может быть несколько), придерживаясь которой первый игрок при любых стратегиях противника обеспечит себе выигрыш, не меньший чем  (в зависимости от знака  это может быть проигрыш, который в этом случае окажется минимальным).

Аналогичным образом определяется минимальный проигрыш (который может быть в действительности и выигрышем) для второго игрока:

.

Величина  называется верхней ценой игры или минимаксом. Ей соответствует минимаксная стратегия второго игрока.

Имеет место неравенство: .

При  <  первый игрок может существенно увеличить свой средний выигрыш по сравнению с , если он будет пользоваться не чистой (одной единственной стратегией), а так называемой смешанной стратегией.

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

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

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

Величина выигрыша (может быть, отрицательного) первого игрока при пользовании парой оптимальных стратегий называется ценой игры и обозначается .

Цена игры заключена между нижней и верхней ценой игры:

.

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

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

Известно, что у игры mn число полезных стратегий с каждой стороны не превосходит минимального из чисел m и n.

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

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

Так как при оптимальной стратегии средний выигрыш первого игрока не меньше при любой стратегии противника, то ищем n неравенств:

Вводим новые неизвестные:

.

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

Так как

= 1, то .

Таким образом, имеем систему неравенств:

, (8.1)

где все .

Так как цель оптимальной стратегии – максимизация выигрыша, то при ее достижении линейная функция:

должна обратиться в минимум. Итак, оптимальная стратегия первого игрока (т.е. набор вероятностей ) находятся в результате минимизации функции:

при , удовлетворяющих системе неравенств (8.1).

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

Зная цену игры, оптимальную стратегию (а1, а2, ..., аn) второго игрока можно находить уже без решения задачи линейного программирования (хотя оптимальную стратегию второго игрока можно находить и через решение этой задачи, если поменять игроков местами). Для этого выбирается n-1 полезных стратегий первого игрока (имея возможность менять местами игроков можно считать, что ) и для каждой из них записывается средний выигрыш, который при этом должен быть обязательно равен цене игры . Например, если для первого игрока полезна стратегия Аi, то ей соответствует уравнение:

.

Кроме этого имеется еще одно уравнение:

.

Всего имеем n уравнений для n величин q1, q2, ..., q_n.

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

Тема 9. Имитационное моделирование

1. Понятие имитационного моделирования.

2. Общая постановка задачи имитационного моделирования.

Характеристики

Список файлов ответов (шпаргалок)