Методы упрощения платежной матрицы.

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

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

Стратегия первого игрока i доминирует стратегию i+1, если:

h_ij≥h_i+1,j(j=1,...,n). (2.6.1)

В этом случае стратегия i+1 называется доминируемой, а стратегия i - доминирующей.

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

Аналогично, если элементы j-го столбца не превосходят элементов j+1 столбца, т.е. выполняется соотношение:

h_ij≤h_{i, j+1} (i=1,..., m), (2.6.2)

то стратегия второго игрока j доминирует стратегию j+1 и соответственно стратегия j будет доминирующей, а стратегия j+1 - доминируемой.

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

Частным случаем доминирования является дублирование стратегий, которое существует, если выполняются соотношения:

h_ij=h_i+1,j(j=1,...,n)

h_ij=h_{i, j+1} (i=1,..., m).

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

Упрощение (уменьшение размерности) платежных матриц за счет исключения заведомо невыгодных чистых стратегий возможно ввиду справедливости следующей теоремы: «Пусть I- игра, в матрице которой i-ая стратегия первого игрока доминирует над i+l, a I¢- игра, матрица которой получена из матрицы I исключением i+1 стратегии (строки). Тогда:

• цена игры I равна цене игры I¢;

• оптимальная смешанная стратегия Q*=(q , q ,…, q ), второго игрока в игре I¢ является также его оптимальной смешанной стратегией и в игре I;

• если Р¢*=(р , р ,p , p ,…, р ) — оптимальная смешанная стратегия первого игрока в игре I¢ то его смешанная стратегия Р*=(р , р ,p ,0, p ,…, р ) является оптимальной в игре I».

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

21.Модели сетевого планирования и управления.

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

Расчет сетевой модели начинают с временных параметров событий, которые вписывают непосредственно в вершины сетевого графика.

· Tр(i) – ранний срок наступления события i, минимально необходимый для выполнения всех работ, которые предшествуют событию i;

· Tп(i) – поздний срок наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети;

·

· R(i)= Tп(i) -Tр(i) – резерв события i, т.е. время, на которое может быть отсрочено наступление события i без нарушения сроков завершения проекта в целом.

 

Временные параметры работ определяются на основе ранних и поздних сроков событий:

• Tрн(ij)=T р (i)– ранний срок начала работы;

• Tро(ij)=Tр(i) +t(i,j)– ранний срок окончания работы;

• Tпо(i,j)= Tп (j)– поздний срок окончания работы;

• Tпн(i,j)= Tп(j) −t (i,j)– поздний срок начала работы;

• Rп (i,j)=Tп (j)−T р (i) −t (i,j)– полный резерв работы показывает максимальное время, на которое можно увеличить длительность работы (i, j) или отсрочить ее начало, чтобы не нарушился срок завершения проекта в целом;

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

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