33.Осн.Теорема теории игр, выр-е оптимальных стратегий игроков через решение пары двойств.Задач лп (возможно, к этому стоит прибавить часть вопроса №31).

Основная теорема теории игр:

1.всякая матричная игра имеет решения.

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

Основная теорема теории матричных игр:

В матр.игре с нулевой суммой у игроков есть оптим.стратегии. Другими словами, всякая матр.игра им.седловую точку в смешанных стратегиях.Исх.задача (для 1го игрока):,,x_i≥0. Двойств.задача (для 2го игрока):

, ,y_j≥0. х=p/гамма, y=q/гамма. Решая эти задачи, найдем цену игры и оптим.стратегии.

35.Графы:осн.понятия.Задача о кратчайшем пути в графе и ее реш-е. Задача о построении критич.пути в графе и ее решение. Граф–совок-ть точек (вершин) и линий (ребер),соединяющих нек-рые пары этих точек.Линии не обяз-но прямые. Нек-рые ребра снабжены стрелками, они наз-ся ориентированными ребрами или дугами. Две вершины м.соединяться неск-ми ребрами или дугами, идущими в одном направлении. Такие ребра наз.кратными (параллельными), а граф, содержащий кратные ребра,-мультиграфом. Если у графа вершины соединены дугами–ориентированный граф (сеть), если нет – неориентированный. Если граф сод.ориент. и неориент.отрезки-смешанный.//Матем-ки граф G – пара объектов G=(X,U), где Х-непустое конечное мн-во (мн-во вершин),U–бинарное отношение на нем (мн-во ребер – отображение мн-ва Х в себя, U=FX).Дуги обозн-ся:(x_i,x_j,v) (начало, конец и номер дуги соотв-но).Ребра–подмн-во дуг вида:{(x_i,x_j,v),(x_j,x_i,v)}U. Если дуга(ребро) единств-я,то число v м.опустить.// Вершины,соед-е ребром или дугой,наз. смежными.Ребра, имеющие общую вершину, также наз.смежными. Ориентир. граф наз.симметрическим, если любые 2 смежные вершины его соед-ны 2мя противоп-но ориентир-ми дугами. Если кажд.пара смежных вершин соед-на только в одном направлении и петли отсутствуют – антисимметрический. Для неориентир. графов меняются только названия:вместо пути-цепь, вместо дуги-ребро, вместо контура-цикл.//Говорят, что в графе данная дуга инцидентна д.вершине, если эта вершина явл.началом или концом д.дуги. Вершина, не инцидентная никакому ребру, наз.изолированной.//Граф, состоящий только из изолир.вершин, наз.нуль-графом. Граф наз.простым(элементарным), если он не сод.петель и параллельных дуг. Граф наз.полным, если он простой и каждая пара вершин смежна. Полный ориентированный граф наз. турниром. Неориентир.граф наз.связным, если 2 любые вершины его м. соед. цепью. Конечный связный граф наз, не имеющий циклов, наз.деревом.Граф, предст.собой объединение деревьев – лес. //Число ребер, инцидентных вершине x_i, наз.степенью графа. //Вершина на графе, кот.следует за всеми вершинами нек-рого мн-ва, наз. мажорантой. Вершина, предшествующая вершинам нек-рого мн-ва, наз.минорантой. Граф конечен, если число его вершин конечно.//Путь на графе–последов-ть дуг, когда конец каждой предшествующей совпадает с началом следующей. Путь простой, когда никакая дуга не встречается дважды (в прот.случае – составной).//Конечный путь,у кот. конечная вершина совп.с начальной, наз.контуром. Контур, образованный одной дугой – петля. Матрица смежности графа с n вершинами-матрица порядка n, в которой в случае неориентированного графа a_ij=k (если вершина x_i смежна с x_j) или 0 в противном случае, для ориентированного графа a_ij=k, k–число дуг от вершины x_i в x_j. М.получить нес-ко разл.матриц смежностей графа, меняя обозначения его вершин.//Задача о кратчайшем пути в графе и ее решение

Пусть дан граф G(X,U).Кажд.дуге u графа G поставим в соотв-е l(u) –длину дуги.Тогда длина пути µ-сумма длин дуг, входящих в µ:Выделим две вершины графа –a и b. Требуется на графе G найти путь кратчайшей длины из вершины a в вершину b. Алгоритм реш-я задачи:1.Перенумеровать вершины графа так, чтобы вершина a получила обознач-е x₀, а вершина b – x_n (последняя по обознач-ю вершина).2.Кажд.вершине, кроме x_i присваиваем метку U_j=+ (i>0), а x_i=0. 3.Найти дугу u=u_ij=(x_i,x_j), для кот.вып-ся нер-во U_j-U_i>l(u_ij) (полагая, что -=0). Для вершины x_j заменить метку на новую,меньшую, метку U_j=U_i+l(u_ij).4.Выполнять процедуру 3 до тех пор, пока для каждой дуги u_ij не станет справедливым нерав-во U_j-U_i≤l(u_ij). Двигаясь по смежным вершинам, пересчитываем их и доходим до последней. Новые метки вершин – расстояние от входа до данной вершины. После нек-рого числа шагов некоторая вершина совпадет с x₀=a. Путь µ (а=x_p,…x_m,x_k,x_n=b) будет кратчайшим и его длина – U_n. (Чтобы найти кратчайш.путь, идут обратно, проверяя рав-во: U_j=U_i+u_ij). Если вершины графа правильно пронумерованы,то их метки м. вычислить реккурентно по ф-ле: , принявU₀=0.

Задача о построении критического пути в графе и ее решение.

В нек-рых сл.надо найти не кратчайший путь, а самый длинный.Пусть задан конечный ориентированный граф G(X,U) без контуров. Кажд.дуге u графа поставим в соотв-е l(u) –длину дуги.Заданы 2 вершины: a=x₀ – вход графа, ,x=x_n – выход. Треб-ся найти путь из а в z, имеющий макс.длину (критич.путь).Алгоритм:1.перенумеровать вершины графа так, чтобы вершина а получила обозначение х₀, а вершина z – x_n (выход графа,т.е. последн.вершина); 2.присвоить каждой вершине x_i метку U_i, так чтобы U₀=0, U_i=- (i>0); 3.найти дугу u_ij=(x_i,x_j),для кот.вып-ся нер-во U_j-U_i<l(u_ij) (полагая,что -=0).Для вершины x_j заменить метку на новую, большую: U_j=U_i+l(u_ij); 4.процедуру 3 повторять, пока для кажд.вершины не станет справедливым нер-во: U_j-U_i≥l(u_ij), 5.найти такую вершину xk, что U_n=U_k+l(u_kn), затем вершину x_m, для которой U_k=U_m+l(u_ij) и т.д. После нек-рого числа шагов вершина совпадет с x₀=а. Этот путь будет критическим.

Если вершины графа правильно пронумерованы,то их метки м. вычислить реккурентно по ф-ле: , принявU₀=0.