Основные понятия математической статистики. Математическая статистика как наука (стр. 3 )

27. ВТОРАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ. УСЛОВИЯ ПРИМЕНЕНИЯ.

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

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

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

                            (1)

                               (2)

Доказательство: Пусть и – оптимальные решения пары двойственных задач. Тогда для

,

они удовлетворяют следующим ограничениям:

.                    (3)

Умножим (3), соответственно, на и , и просуммируем полученные выражения:

.                          (4)

Из основной теоремы двойственности следует

.                                                  (5)

И с учетом (4) получаем:

,

.

Первое из этих выражений можем переписать в виде

,

и так как все и выражения в скобках неотрицательны, то опуская å, получим:

.

Аналогично получим:

.

Что и требовалось доказать.

Справедлива и обратная теорема.

28. ОБЪЕКТИВНО ОБУСЛОВЛЕННЫЕ ОЦЕНКИ И ИХ ЭКОНОМИЧЕСКИЙ СМЫСЛ.

Объективно обусловленные оценки

Объективно обусловленные оценки

 термин, употребляемый для обозначения частных производных целевой функции, взятых по отношению к ограничениям в задачах линейного или выпуклого программирования. Введён советским учёным в 1959 и в основном используется при решении экономических задач методами математического программирования. Аналогичен терминам «оптимальные оценки», «двойственные оценки», «теневые цены», «разрешающие множители». О. о. о. в экономических задачах показывают, к каким экономическим результатам приведёт появление в хозяйственном процессе дополнительной единицы того или иного производственного компонента. о. о. соответствует размерности критерия оптимальности (натуральные или натурально-условные единицы измерения, денежные и т. д.). О. о. о. объективно вытекают из условий постановки и решения экономической задачи и целиком обусловлены совокупностью тех конкретных хозяйственных факторов, которые учтены при математической формализации производственно-экономической деятельности. Поэтому они являются эффективным средством анализа текущей хозяйственной деятельности, позволяют выявить и количественно оценить «узкие места», а при предположении некоторой устойчивости О. о. о. дают возможность наметить направления улучшения показателей работы хозяйственного объекта.

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

29. ОПРЕДЕЛЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ. ЗАДАЧИ ЗАКРЫТОГО И ОТКРЫТОГО ВИДА.

30. ЭММ ТРАНСПОРТНОЙ ЗАДАЧИ И ЕЕ ОСОБЕННОСТИ.

31. ПОЛУЧЕНИЕ ПЕРВОНАЧАЛЬНОГО РАСПРЕДЕЛЕНИЯ ПОСТАВОК В ТРАНСПОРТНОЙ ЗАДАЧЕ.

32. ПЕРЕРАСПРЕДЕЛЕНИЕ ПОСТАВОК. ЦИКЛЫ ПЕРЕСЧЕТА.

33. КРИТЕРИЙ ОПТИМАЛЬНОСТИ В ТРАНСПОРТНОЙ ЗАДАЧЕ.

34. АЛГОРИТМ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ.

Транспортная задача (задача Монжа — Канторовича) — задача об оптимальном плане перевозок продукта(-ов) из пунктов отправления в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной или входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной.

Постановка задачи

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

История поиска методов решения

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году[1]. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем[2]. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

Методы решения

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

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

Итерационное улучшение плана перевозок

Нахождение опорного плана

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

Метод северо-западного угла (диагональный)

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

Метод наименьшего элемента

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

Алгоритм:

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

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

3.  Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.

Решение с помощью теории графов

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

К верхней доле искусственно присоединяется исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Цена за единицу потока у этих рёбер равна 0.

Аналогично к нижней доле присоединяется сток. Пропускная способность рёбер из каждого пункта потребления в сток равна потребности в продукте в этом пункте. Цена за единицу потока у этих рёбер тоже равна 0.

Дальше решается задача нахождения максимального потока минимальной стоимости (mincost maxflow). Её решение аналогично нахождению максимального потока в алгоритме Форда — Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной.

Алгоритм «mincost maxflow» можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за операций. ( — количество рёбер,  — количество вершин.) При случайно подобраных данных обычно требуется гораздо меньше — порядка операций.

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

35. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР.

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

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

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

Все такие модели в теории игр принято называть играми.

Игры можно классифицировать по различным признакам: стратегические и чисто случайные, бескоалиционные и коалиционные, игры 1, 2, …, n лиц (по числу игроков), конечные и бесконечные (по числу стратегий), игры в нормальной форме и динамические, с нулевой суммой («антагонистические») и с ненулевой суммой.

Рассмотрим простейшую модель – игру, в которой участвуют два игрока, множество стратегий каждого игрока конечно, а выигрыш одного игрока равен проигрышу другого (бескоалиционная, конечная, антагонистическая игра двух лиц). Такую игру (Г) называют матричной. Она определяется тройкой Г=(X,Y,K), где Х – множество стратегий 1-го игрока, Y – множество стратегий 2-го игрока, K=K(x,y) – функция выигрыша (выигрыш 1-го игрока и соответственно проигрыш 2-го при условии, что 1-й игрок выбрал стратегию , а 2-й – стратегию ). Пару (x,y) называют ситуацией в игре Г.

Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2, …, m}, Y=N={1,2, …, n}. Тогда игра Г полностью определяется заданием матрицы , где aij=K(i,j) – выигрыш 1-го игрока при условии, что он выбрал стратегию (т. е. строку) i, а 2-й игрок – стратегию (т. е. столбец) j (эти стратегии называют чистыми).

Матрица А называется матрицей игры или платежной матрицей.

Пусть матрица игры . Цель каждого игрока – получить как можно больший выигрыш. Но 1-му игроку нет смысла выбирать стратегию i=1 в надежде выиграть 5 ед., так как 2-й игрок, действуя разумно, не станет выбирать стратегию j=2, чтобы не проиграть максимальную сумму 5 ед. Игрокам удобнее выбрать «осторожные» стратегии.

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

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

Схема:

Например,

Соответствующие стратегии: i0=1 (максиминная), j0=1,2 (минимаксная).

Справедливо неравенство: .

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

Ситуация (i*,j*) называется ситуацией равновесия, или седловой точкой, если для любых , выполняется неравенство . Соответствующие стратегии i*, j* называются оптимальными чистыми стратегиями 1-го и 2-го игроков, а число называется ценой игры. Элемент является одновременно минимумом в своей строке и максимумом в своем столбце.

Ситуация равновесия существует тогда и только тогда, когда (это значение и является ценой игры v).

Например,

(2,3)-ситуация равновесия, v=4 – цена игры, i*=2, j*=3 – оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.

Наряду с чистыми стратегиями игроков рассматривают также смешанные стратегии.

Смешанной стратегией для 1-го игрока называется упорядоченная система m действительных чисел x=(x1, x2, …, xm), , , которые можно рассматривать как относительные частоты (вероятности), с которыми 1-й игрок выбирает чистые стратегии i=1, 2, …, m.

Аналогично определяется смешанная стратегия для 2-го игрока: y=(y1, y2, …, yn), , .

Множества всех смешанных стратегий 1-го и 2-го игроков будем обозначать соответственно Sm и Sn.

Чистые стратегии можно рассматривать как частный случай смешанных стратегий. Например, чистую стратегию j=2 можно рассматривать как смешанную y=(0,1,0,…,0), чистую стратегию i=1 – как смешанную x=(1,0,…,0).

Пару смешанных стратегий (x,y) называют ситуацией в смешанных стратегиях.

Функция выигрыша K(x,y) в ситуации (x,y) определяется как математическое ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали соответственно стратегии x=(x1, x2, …, xm) и y=(y1, y2, …, yn): .

Если для некоторых и и для всех и выполняется неравенство , то x*, y* называются оптимальными смешанными стратегиями игроков, число называется ценой игры, пара (x*, y*) – стратегической седловой точкой, а тройка x*, y*, v – решением игры.

36. ПЛАТЕЖНАЯ МАТРИЦА. СЕДЛОВАЯ ТОЧКА.

Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица. Отсюда, кстати, происходит еще одно их название — матричные игры. Каждый элемент платежной матрицы аij содержит числовое значение выигрыша игрока I (проигрыша игрока II), если первый применяет стратегию i, а второй — стратегию j. Термины выигрыш и проигрыш следует понимать в широком смысле, т. к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи прежде всего заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.

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

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

Более сложная и содержательная платежная матрица может быть получена, если несколько модифицировать предложенную игру. Допустим, что оба участника имеют право загадывать числа от 1 до 4, что составляет их соответствующие стратегии. В случае, если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый — второму. Запишем платежную матрицу для такой игры:

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

Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица А=║aij║mxn. При выборе игроком I стратегии i его гарантированный доход независимо от действий игрока II составит min ai, j. Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т. е. обеспечивал получение max (min ai, j). Такой принцип выбора стратегии получил название «принцип максимина». С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит max ai, j, и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить min (max ai, j). в этом суть принципа минимакса.

Можно доказать справедливость следующего соотношения:

Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии

В этом случае говорят, что игра имеет седловую точку. Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии i* и j*, образующие седловую точку, называются оптимальными, а значение v = ai*j* называют ценой игры. Тройка (i*, j*, v) считается решением матричной игры с седловой точкой.

Нетрудно заметить, что не всякая игра обладает седловой точкой. В частности, как игра (6.1), так и игра (6.2) седловой точки не имеют. Примером игры, имеющей седловую точку, является игра с платежной матрицей (6.5).

В данной матрице минимальные (гарантированные) выигрыши первого игрока по строкам равны 1, 5 и (-3). Следовательно, его максиминному выбору будет отвечать стратегия 2, гарантирующая выигрыш 5. Для второго игрока максимальные проигрыши по столбцам матрицы составят 8, 10, 5, 17, поэтому имеет смысл остановиться на стратегии 3, при которой он проиграет только 5. Таким образом, вторая стратегия первого игрока и третья стратегия второго образуют седловую точку со значением 5, т. е. для игры с матрицей (6.5) имеет решение (2; 3; 5).

37. НИЖНЯЯ И ВЕРХНЯЯ ЦЕНА ИГРЫ. РЕШЕНИЕ ИГРЫ В ЧИСТЫХ СТРАТЕГИЯХ.

Найдем наилучшую стратегию игрока A, для чего проанализируем последовательно все его стратегии. Выбирая стратегию Ai, мы должны рассчитывать, что игрок B ответит на нее такой стратегией Bj, для которой выигрыш A будет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его, запишем его в добавочный столбец. Аналогично для каждой стратегии Ai выбираем, т. е. αi – минимальный выигрыш при применении стратегии Ai.
В примере 1:
α1 = min {0, –1, –2} = –2;
α 2 = min {1, 0, –1} = –1;
α 3 = min {0, –1, –2} = 0.
Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A? Конечно же, ту стратегию, для которой αi максимально. Обозначим. Это гарантированный выигрыш, который может обеспечить себе игрок A, т. е. ; этот выигрыш называется нижней ценой игры или максимином. Стратегия Ai, обеспечивающая получение нижней цены игры, называется максиминной (перестраховочной). Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш ≥α при любом поведении игрока B.
В примере 1 . Это означает, что если A будет писать «3», то он хотя бы не проиграет. Игрок B заинтересован уменьшить выигрыш A. Выбирая стратегию B1, он из соображений осторожности учитывает максимально возможный при этом выигрыш A. Обозначим. Аналогично при выборе стратегии Bj максимально возможный выигрыш A– ; запишем эти числа в добавочной строке. Чтобы уменьшить выигрыш A, надо из чисел β j выбрать наименьшее. Число  называется верхней ценой игры или минимаксом. Это гарантированный проигрыш игрока B (т. е. он проиграет не больше, чем β). Стратегия игрока B, обеспечивающая выигрыш ≥ - β, называется его минимаксной стратегией.
В примере 1:
;
;
;
.
Это означает, что оптимальная стратегия B – писать «3», тогда он хотя бы не проиграет.

B A	B1	B2	B3
A1	0	– 1	–2	–2
A2	1	0	–1	–1
A3	2	1	0	0
	2	1	0	0 0

Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.
Можно доказать, что, т. е. .
В примере 1 α = β. Если , т. е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой. Седловая точка – это пара оптимальных стратегий ( Ai, Bj). В примере 1 игра имеет седловую точку (А3, B3). В этом случае число α = β называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0.
Оптимальные стратегии в любой игре обладают важным свойством, а именно – устойчивостью. Это означает, что каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, т. к. это ему невыгодно. Отклонение от оптимальной стратегии игрока А приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В – к увеличению проигрыша. Говорят, что седловая точка дает положение равновесия.
Пример 2. Первая сторона (игрок А) выбирает один из трех типов вооружения – А1, А2, А3, а противник (игрок В) – один из трех видов самолетов: В1, В2, В3. Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В1 вооружением А1 равна 0,5, самолета В2 вооружением А1 равна 0,6, самолета В3 вооружением А1 равна 0,8 и т. д., т. е. элемент aij платежной матрицы – вероятность поражения самолета В j вооружением Аi. Платежная матрица имеет вид:

В А	Вид самолета
В1	В2	В3
Тип вооружения	А1	0,5	0,6	0,8
А2	0,9	0,7	0,8
А3	0,7	0,5	0,6

 
Решить игру, т. е. найти нижнюю и верхнюю цену игры и оптимальные стратегии.

38. ОСНОВНАЯ ТЕОРЕМА ТЕОРИИ ИГР. РЕШЕНИЕ ИГРЫ В СМЕШАННЫХ СТРАТЕГИЯХ.

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

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

Введем специальное обозначение для смешанных стратегий. Пусть К, применяет свои стратегии K1 К2, К3с частотами соответственно p1 р2, р3 (р1 + р2 + р3 = 1). Эту смешанную стратегию будем обозначать:

Аналогично смешанную стратегию игрока С будем обозначать:

где q1 + q2 + q3 = 1.

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

В первом примере мы путем нестрогих соображений догадались, что решение игры должно быть:

а цена игры v = 0. Проверим это. Пусть мы ("красные") держимся своей стратегии Sk* , т. е. ищем С в убежищах I и II одинаково часто, чередуя эти стратегии случайным образом. Может ли С улучшить свое положение (повысить свой выигрыш), отступая любым образом от своей стратегии Sc* ? Очевидно, нет. А если одностороннее отступление от стратегии Sk* придет в голову нам (в то время как разумный С будет держаться стратегии Sc* ), то это нам тоже не может быть выгодно. Значит, мы и в самом деле нашли решение игры и ее цену v = 0. Правда, эта игра была довольно простой! Уже второй пример дает игру, решение которой не так очевидно. Из того, что в нем а не равно бета, следует только, что решение нужно искать в смешанных стратегиях.

39. ГЕОМЕТРИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ТЕОРИИ ИГР.

Графические методы решения игр. Следует отметить, что применение для решения задач (6.16)-(6.17), (6.18)-(6.19) стандартных алгоритмов линейного программирования далеко не всегда является рациональным. Помимо этого существуют иные методы, которые основываются на использовании специфики данных задач. В настоящем пункте мы остановимся на очень простом классическом способе поиска оптимальных смешанных стратегий в матричных играх, где один из участников имеет только две стратегии (это так называемые 2 х п и т х 2 игры).

Для определенности положим, что игрок I имеет возможность выбирать между двумя стратегиями с вероятностями x1 и x2 = 1-x1, тогда его ожидаемые выигрыши, соответствующие чистым стратегиям игрока II, примут вид

или

т. е. ожидаемые выигрыши могут быть представлены в виде графиков линейных функций, зависящих от переменной x1 ∊ [0; 1] (рис. 6.1, где предполагается, что игрок II имеет три стратегии).

Линии, изображенные на рис. 6.1, задают зависимости среднего выигрыша игрока I от значения вероятности x1 , с которой он выбирает свою первую стратегию, для случаев, когда его противник выбирает первую, вторую или третью чистую стратегию. Тогда значениям минимального гарантированного дохода первого игрока соответствует нижняя огибающая всех трех прямых. Согласно принципу максимина, оптимальному выбору игрока I будет соответствовать наивысшая точка, лежащая на данной огибающей, отмеченная на рисунке как (x1*, z*). Зная ее, можно определить оптимальную смешанную стратегию первого игрока х* = (x1*, 1-x2*) и цену игры, равную z*.

Исходя из отношения двойственности, которым, как было установлено в п. 6.1.5, связаны задачи обоих игроков, по оптимальной стратегии первого участника х* однозначно определяется оптимальная стратегия его противника у*. Поскольку у* является результатом решения задачи линейного программирования, то он обладает всеми свойствами допустимого базисного плана, т. е. в случае 2 х п игры имеет не более чем две ненулевых компоненты и не менее чем (п-2) нулевых. Номера ненулевых элементов у* определяются номерами линий, пересечение которых определило оптимальную стратегию первого игрока. Действительно, игрок II знает оптимальную стратегию соперника, и применение им стратегий, соответствующих прямым, проходящим выше точки (х1*, z*), только увеличило бы его проигрыш.

В рассматриваемом примере это линии z2 и z3, и, следовательно, в своей оптимальной стратегии второй игрок должен с ненулевыми вероятностями применять вторую и третью чистые стратегии (у2 >0, у3 >0). На основе этого, а также учитывая условие нормировки

можем выразить: y3 = l – y2 тогда оптимальное значение y2* может быть найдено из условия

или

В результате получаем оптимальную стратегию игрока II у*= (0, у2*, у3*).

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

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

40. СВЕДЕНИЕ КОНЕЧНОЙ ИГРЫ К ДЗЛП.

41. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.

42. МАТРИЧНЫЕ СПОСОБЫ ЗАДАНИЯ ГРАФОВ.

Пусть D = (V, Х) – орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой

Определение. Матрицей инцидентности орграфа D называется (nґm) –матрица B(D)=[bij], у которой

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Определение. Матрицей инцидентности графа G называется (nґm) –матрица B(G)=[bij], у которой

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

Пример 72.

Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 25).

Решение.

Матрица смежности имеет вид

.

Поскольку граф не имеет петель, то на главной диагонали стоят все нули. Для любого графа матрица смежности симметрична относительно главной диагонали.

43. УПОРЯДОЧЕНИЕ ГРАФОВ. АЛГОРИТМ ФАЛКЕРСОНА.

44. ПУТЬ И ЦИКЛ. СВЯЗНОСТЬ ГРАФА.

Пример 1. Представим себе схему дорог, соединяющих различные населенные пункты (рис. 16).
 
  рис. 16
Предположим, что нам надо попасть из А1 в А5. Какими путями это можно сделать?
Например, мы получили следующие ответы.

1.  (А1 А4); (А4 А5).

2.  (А1 А2); (А2 А4); (А4 А5).

3.  (А1 А4); (А4 А2); (А2 А1); (А1 А4); (А4, А5).

4.  (А1 А4); (А4 А2); (А2 А1); (А1 А3); (А3 А4); (А4, А5).

В одних последовательностях  – ребра повторяются, в других — не повторяются. Можно указать маршрут от А1до А5, содержащий все вершины графа. Таков, например, четвертый маршрут. Но не всякую последовательность ре­бер, ведущих из А1 в А5, называют путем из А1 в А5.
Путем от А1 до Аn в графе называется такая последователь­ность ребер, ведущая от A1 к Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.
Вершина А1 — начало пути, вершина Аn— конец.
Из определения следует, что третья и третья последовательность ребер не является путем в графе.
Заметим, что согласно определению вершины пути могут по­вторяться, т. е. путь может быть самопересекающимся.
Путь от А1 до Аn называется простым, если он не проходит ни через одну из вершин графа более одного раза.
Задание 3.1. Определите, какие последовательности ребер из примера 1 являются путями, и какие из них простые. Если последовательность не является путем, укажите почему.
Первая, вторая и четвертая последовательности являются путями, а третья нет, т. к. ребро (А1, А4) повторяется.
Первая и вторая последовательность являются простыми путями, а четвертая нет, т. к. вершины А1 и А4 повторяются.
Циклом называется путь, в котором совпадают его начальная и конечная вершины.
Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза.
Задача 3.1. Назовите в графе на рис. 17 циклы, содержащие a) 4 ребра; б) 6 ребер; в) 5 ребер; г) 10 ребер. Какие из этих циклов являются простыми?

Решение. а) (AB, BC, CE, EA), (CD, DA, AB, BC), (EB, BC, CD, DE) и т. д. – простые циклы.
б) (DB, BE, EA, AB, BC, CD), (EC, CA, AB, BC, CD, DE) и т. д. – циклы.
в) (AB, BC, CD, DE, EA), (AC, CE, EB, BD, DA) и т. д. – простые циклы.
г) (AC, CE, EB, BD, DA, AB, BC, CD, DE, EA), (EB, BD, DA, AC, CE, EA, AB, BC, CD, DE) и т. д. – циклы.
Длиной пути называется число ребер этого пути.
Аналогично длиной цикла называется число ребер в этом цикле.

 
рис. 18
От вершины А1 до вершины А6 графа на рисунке 18 можно пройти четырьмя путями; один из них — длины 1, второй — дли­ны 2 и два пути длиной 6. (Назовите эти пути.)

1.  А1 - А6.

2.  А1 - А2 - А6.

3.  А1 - А2 – А5 – А4 – А3 - А2 – А6.

4.  А1 - А2 – А3 – А4 – А5 - А2 – А6.

Теорема 1. Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.
Доказательство. Для графа, являющегося простым циклом, утверждение теоремы очевидно. Допустим, что у графа, все простые циклы которого четной длины, все же найдется цикл нечеткой длины. Во всяком непростом цикле существует вершина, через которую путь проходит более одного раза. В такой вершине цикл разобьется на два, причем один из них, очевидно, будет иметь, нечетную длину, а другой — четную. Будем продолжать расчлене­ние нечетного цикла до тех пор, пока не дойдем до простых циклов. Хотя бы один из них обязательно должен иметь нечетную длину. Существование такого простого цикла противоречило бы условию. Следовательно, принятое предположение неверно.

рис. 19.

Предположим снова, что мы имеем граф G, который мы сейчас будем пред­ставлять себе как карту дорог. Мы начнем наш путь по графу Gиз некоторой вершины A, следуя сначала вдоль ребер, или дорог, до некоторой станции T.
Если вершина Т графа такова, что мы можем дойти до нее таким образом, то говорят, что Т связана с А в нашем графе. Это означает, что имеются дороги, ведущие из А в Т.
Две вершины А и В графа называются связными, если в графе существует путь с концами А и В.
Две вершины графа называются несвязными, если в графе не суще­ствует ни одного пути, связывающего их.

   
рис. 20   рис. 21

Например, в графе G (рис. 20) вершины А и D— связные, а вершины А и Н— несвязные.
Граф называется связным, если каждые две вершины его связные.
Граф называется несвязным, если хотя бы две вершины его не­связные.

Например, графы на рисунках 18 и 19 связные. Графы на рисунках 20 и 21 связными не являются.

45. ПОНЯТИЕ О СЕТЕВОМ МОДЕЛИРОВАНИИ

46. ПОСТРОЕНИЕ И РАСЧЕТ СЕТЕВОГО ГРАФИКА.

Построение сетевого графика

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

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

1) составляется список событий и работ;

2) устанавливается топология сети;

3) строится сетевой график по теме;

4) определяется длительность работ ();

5) рассчитываются характеристики сетевого графика;

6) определяется длительность критического пути;

7) проводится анализ и оптимизация сетевого графика, если это нужно.

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

Исходные данные для расчета получают способом экспертных оценок.

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

- минимальную;

- максимальную;

- более вероятную либо лишь две первые.

Эти величины являются исходными для расчета ожидаемого времени :