Теория принятия решений в научно-исследовательской работе

Содержание

Слайд 2

Содержание: Основные понятия 3 Задача линейного программирования 11 Задачи принятия решений,

Содержание:
Основные понятия 3
Задача линейного программирования 11
Задачи принятия решений, связанные с
оптимизацией

на графах 33
Теория игр 57
Дерево решений 79
Список рекомендуемой литературы 90

Москва, 2018

Кафедра КБ-5 «Аппаратного, программного и математического
обеспечения вычислительных систем»

#

Слайд 3

Теория принятия решений (ТПР) – это совокупность методов и моделей, предназначенных

Теория принятия решений (ТПР) – это совокупность методов и моделей, предназначенных

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

Основные понятия

#

Слайд 4

Решение – это любой выбор параметров, зависящих от лица, принимающего решение.

Решение – это любой выбор параметров, зависящих от лица, принимающего решение.
Элементы

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

Основные понятия

#

Слайд 5

Решение называется допустимым, если оно удовлетворяет ограничениям: ресурсным, юридическим, правовым, морально-этическим.

Решение называется допустимым, если оно удовлетворяет ограничениям: ресурсным, юридическим, правовым, морально-этическим.
Решение

является оптимальным, если по тем или другим признакам оно предпочтительнее перед другими.
Для того, чтобы сравнивать между собой по эффективности разные решения, необходимо иметь какой-то количественный критерий, показатель эффективности F (или «целевая функция»).

Основные понятия

#

Слайд 6

Основные этапы решения задач ТПР. 1. Постановка задачи (приведение входных данных

Основные этапы решения задач ТПР.
1. Постановка задачи (приведение входных данных к

виду, удобному для построения модели).
2. Построение математической модели.
3. Нахождение метода решения.
4. Проверка и корректировка модели.
5. Выдача рекомендаций (реализация найденного решения на практике).

Основные понятия

#

Слайд 7

Схема решения задачи методами теории принятия решений выглядит следующим образом Основные понятия #

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

Основные

понятия

#

Слайд 8

Классификация задач ТПР. 1. Решения принимаются в условиях определенности. Каждому решению

Классификация задач ТПР.
1. Решения принимаются в условиях определенности.
Каждому решению можно поставить

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

Основные понятия

#

Слайд 9

2. Решения принимаются в условиях риска. Между решениями и результатами имеет

2. Решения принимаются в условиях риска.
Между решениями и результатами имеет

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

Основные понятия

#

Слайд 10

3. Решения принимаются в условиях неопределенности. Определенному решению соответствует более одного

3. Решения принимаются в условиях неопределенности.
Определенному решению соответствует более одного результата,

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

Основные понятия

#

Слайд 11

Программирование – нахождение экстремума (max или min) функции при заданных ограничениях,

Программирование – нахождение экстремума (max или min) функции при заданных ограничениях,

т.е. нахождение оптимального решения функции f(x1, x2, …, xn) при наложенных ограничениях.
Линейное программирование (задачи линейного программирования) – это нахождение оптимального решения при условии, что функция цели f(x1, x2,…, xn) линейна, все условия ограничения линейны и x1, x2,…, xn ≥ 0.

Задача линейного программирования

#

Слайд 12

Пусть имеется n переменных x1, x2, …, xn. Необходимо найти такие

Пусть имеется n переменных x1, x2, …, xn. Необходимо найти такие

значения этих переменных, чтобы достигался max или min функции цели (линейной):
F=c1x1+c2x2+…+cnxn→max(min),
при соответствующей системе ограничений

Задача линейного программирования

#

Слайд 13

Для конкретной задачи система ограничений может содержать любой из знаков неравенства.

Для конкретной задачи система ограничений может содержать любой из знаков неравенства.

Но переменные x1, x2, …, xn всегда должны быть больше либо равны нулю.
Необходимо найти решение системы ограничений X=(x1,x2,…,xn), при котором функция цели будет принимать экстремальное значение (max или min).
При этом данное решение должно удовлетворять системе ограничений. Нахождение такого решения и составляет задачу линейного программирования (ЗЛП)

Задача линейного программирования

#

Слайд 14

Стандартной задачей линейного программирования называется задача, система ограничений в которой состоит

Стандартной задачей линейного программирования называется задача, система ограничений в которой состоит

только из одних неравенств и все неизвестные больше либо равны нулю:

Задача линейного программирования

#

Слайд 15

Канонической задачей линейного программирования называется задача, которая состоит в определении максимального

Канонической задачей линейного программирования называется задача, которая состоит в определении максимального

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

Задача линейного программирования

#

Слайд 16

Пример Составить математическую модель задачи. Имеется два вида корма «№1» и

Пример
Составить математическую модель задачи.
Имеется два вида корма «№1» и «№2», содержащие

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

Задача линейного программирования

#

Слайд 17

Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого


Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого

вида питательных веществ было бы не менее установленного предела.

Задача линейного программирования

#

Слайд 18

Решение. Пусть x1 и x2 – количество кормов «№1» и «№2».

Решение.
Пусть x1 и x2 – количество кормов «№1» и «№2».
Тогда условия

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

#

Задача линейного программирования

Слайд 19

Поэтому: условие - ограничение для белков имеет вид: 3x1 + 1x2

Поэтому:
условие - ограничение для белков имеет вид:
3x1 + 1x2 ≥ 9,
условие

– ограничение для жиров:
1x1 + 2x2 ≥ 8,
условие – ограничение для углеводов:
1x1 + 6x2 ≥ 12.
Переменные x1, x2 должны быть больше или равны нулю:
. x1 ≥ 0, x2 ≥ 0

#

Задача линейного программирования

Слайд 20

Общая стоимость рациона составит: F = 4x1 + 6x2 (руб). Т.к.

Общая стоимость рациона составит:
F = 4x1 + 6x2 (руб).
Т.к. общая стоимость

дневного рациона должна быть минимальна, то необходимо найти минимум функции цели
F = 4x1 + 6x2 .
Математическая модель задачи имеет вид:

#

Задача линейного программирования

Слайд 21

Задача линейного программирования сформулирована как задача минимизации или максимизации линейной формы,

Задача линейного программирования сформулирована как задача минимизации или максимизации линейной формы,

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

#

Задача линейного программирования

Слайд 22

Алгоритм Шаг 1. В системе ограничений ЗЛП заменить знаки неравенств на

Алгоритм
Шаг 1. В системе ограничений ЗЛП заменить знаки неравенств на знаки точных

равенств и построить соответствующие прямые.
Шаг 2. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств ЗЛП.
Для этого необходимо подставить в конкретное неравенство координаты какой-либо точки (например, (0;0)), и проверьте истинность полученного неравенства.

#

Задача линейного программирования. Графический метод

Слайд 23

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку; иначе

  Если  неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать

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

#

Задача линейного программирования. Графический метод

Слайд 24

Шаг 3. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным

 
Шаг 3. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям,

и выделить ее. При отсутствии ОДР задача не имеет решений.
Шаг 4. Если ОДР – не пустое множество, то построить целевую прямую, т.е. любую из линий уровня c1x1 + c2x2 = F , где F – произвольное число.
Шаг 5. Построить вектор C = (c1; c2), из точки (0;0), направленный в точку (c1; c2). Если целевая прямая и вектор C построены верно, то они перпендикулярны.

#

Задача линейного программирования. Графический метод

Слайд 25

Шаг 6. При поиске максимума целевой функции необходимо передвигать целевую прямую

 
Шаг 6. При поиске максимума целевой функции необходимо передвигать целевую прямую в

направлении вектора С, при поиске минимума целевой функции – против направления вектора С. Последняя по ходу движения вершина ОДР будет точкой max или min целевой функции.
Если такой точки (точек) не существует, то целевая функция не ограничена на множестве планов сверху (при поиске max) или снизу (при поиске min).

#

Задача линейного программирования. Графический метод

Слайд 26

Шаг 7. Определить координаты точки max (min) целевой функции X* =

 
Шаг 7. Определить координаты точки max (min) целевой функции X* = (x1*;

x2*) и вычислить значение самой целевой функции F(X*).
Для вычисления координат оптимальной точки X* необходимо решить систему уравнений прямых, на пересечении которых находится X*.

#

Задача линейного программирования. Графический метод

Слайд 27

Пример Найти оптимальное решение задачи, математическая модель которой имеет вид # Задача линейного программирования. Графический метод

Пример 
Найти оптимальное решение задачи, математическая модель которой имеет вид

#

Задача

линейного программирования. Графический метод
Слайд 28

Решение. Для построения прямых ограничений необходимо вычислить координаты точек пересечения этих

Решение. 
Для построения прямых ограничений необходимо вычислить координаты точек пересечения этих

прямых с осями координат
(1) – (2) –
(3) –
Прямая (4) проходит через точку x2 =2 параллельно оси x1

#

Задача линейного программирования. Графический метод

Слайд 29

Графическое решение примера # Задача линейного программирования. Графический метод

Графическое решение примера

#

Задача линейного программирования. Графический метод

Слайд 30

Далее следует определить ОДР. Например, подставив точку (0;0) в исходное ограничение

Далее следует определить ОДР. Например, подставив точку (0;0) в исходное ограничение

(3), результатом является неравенство , что является истинным. Поэтому стрелкой (или штрихованием) обозначается полуплоскость, содержащая точку (0;0), т.е. расположенная правее и ниже прямой (3). Аналогично определяются допустимые полуплоскости для остальных ограничений. Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDEF.

#

Задача линейного программирования. Графический метод

Слайд 31

Целевую прямую можно построить по уравнению 3x1 + 2x2 = 6

Целевую прямую можно построить по уравнению
3x1 + 2x2 = 6
Вектор строится

из точки (0;0) и направляется в точку (3;2). Точка Е – это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому Е – это точка максимума целевой функции.

#

Задача линейного программирования. Графический метод

Слайд 32

Координаты точки Е определяются из системы уравнений прямых ограничений (1) и

Координаты точки Е определяются из системы уравнений прямых ограничений (1) и

(2)
Максимальное значение целевой функции равно
[тыс. руб./сутки]

#

Задача линейного программирования. Графический метод

Слайд 33

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

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

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

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 34

Графом называется пара объектов, состоящая из множества точек и отрезков, соединяющих

Графом называется пара объектов, состоящая из множества точек и отрезков,

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

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 35

Пусть: G – граф; X1, X2,…, Xn – вершины графа; uij

Пусть:
G – граф;
X1, X2,…, Xn – вершины графа;
uij – дуга,

соединяющая вершину Xi c Xj в направлении от Xi к Xj;
G – граф, образованный множеством вершин X и множеством дуг
U, обозначают G(X,U).
Тогда G(X,U) – граф, образованный множеством вершин X и множеством дуг U.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 36

Путь в ориентированном графе – это последовательность дуг, в которой конец

Путь в ориентированном графе – это последовательность дуг, в которой

конец предыдущей дуги совпадает с началом следующей. Путь µ={X1, X2,…, Xk} – это пусть, состоящий из последовательности вершин X1,X2,…,Xk.
Путь, в котором ни одна вершина не встречается дважды, называется элементарным.
Путь, в котором ни одна дуга не встречается дважды, называется простым, в противном случае – составным.
Конечный путь, у которого конечная вершина совпадает с
начальной, называется контуром.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 37

Задача о максимальном потоке в сети Рассматривается ориентированный граф с (n+1)

Задача о максимальном потоке в сети
Рассматривается ориентированный граф с (n+1)

вершинами X0, X1, X2,…, Xn, где некоторые упорядоченные пары точек Xi, Xj соединены дугами uij, причем каждой такой дуге поставлено в соответствие неотрицательное число cij=c(uij) называемое пропускной способностью.
Пусть зафиксированы какие-нибудь две вершины графа, например, X0 и Xn, где
X0 – вход сети, Xn – выход сети.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 38

Пропускная способность cij дуги (Xi, Xj) определяет максимальное количество вещества, которое

Пропускная способность cij дуги (Xi, Xj) определяет максимальное количество вещества,

которое может пропустить эта дуга за единицу времени.
Потоком zij по дуге (Xi, Xj) называется количество вещества, проходящее через эту дугу в единицу времени.
Потоком по сети, или просто потоком, называется совокупность {zij} потоков по всем дугам сети. Потоки удовлетворяют следующим ограничениям:
0≤ zij ≤ cij , i, j=0, 1, 2, …, n, i ≠ j (1)
k=1, 2, …, n-1. (2)

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 39

Из (1) следует – поток по любой дуге неотрицателен и не

Из (1) следует – поток по любой дуге неотрицателен и

не превышает пропускной способности дуги.
Из (2) следует – количество вещества, притекающего в произвольную точку сети (кроме X0 и Xn), равно количеству вещества, вытекающего из этой точки.
Из (2) следует – общее количество вещества , вытекающего из вершины X0 (входа сети), совпадает с общим количеством вещества , притекающего в вершину Xn (выход сети), т. е. (3) ,
где w – величина потока в сети.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 40

Задача о максимальном потоке в сети представляет собой задачу ЛП: среди


Задача о максимальном потоке в сети представляет собой задачу ЛП:

среди всех решений системы линейных ограничений (1) – (2) следует найти такое решение, которое максимизирует линейную форму (3). Это решение называется максимальным потоком в сети.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 41

Дуга uij с началом в Xi и концом в вершине Xj


Дуга uij с началом в Xi и концом в вершине

Xj является насыщенной, если zij=cij, т. е. величина потока по этой дуге равна пропускной способности дуги.
Если же величина потока по дуге меньше пропускной способности дуги zij < cij , то такую дугу называют ненасыщенной.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 42

Алгоритм определения максимального потока Шаг 1. Построить какой-нибудь начальный поток .

Алгоритм определения максимального потока
Шаг 1. Построить какой-нибудь начальный поток .
Шаг

2. Проверить, можно ли построить путь из X0 в Xn, состоящий только из ненасыщенных дуг. Если нет, то построенный поток максимален. Иначе, перейти к шагу 3.
Шаг 3. Выделить любой путь, ведущий из X0 в Xn по ненасыщенным дугам, найти минимальную пропускную способность дуг этого пути θ и увеличить поток через каждую дугу этого пути на θ . Построить новый поток. Перейти к шагу 2.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 43

Вычисления продолжаются до тех пор, пока удается построить путь из X0

Вычисления продолжаются до тех пор, пока удается построить путь из X0

в Xn по ненасыщенным дугам.
Алгоритм обрывается, как только будет получена сеть, в которой нельзя построить ни одного пути из X0 в Xn, идущего по ненасыщенным дугам.
Если по пути µ пропустить поток θ, то пропускные способности всех дуг этого пути следует уменьшить на θ, т. е. с'ij=cij – θ. При этом пропускные способности всех дуг, симметричных дугам старого пути, следует увеличить на θ, т. е. с'ji=cji + θ.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 44

Пример. Определить максимальный поток в сети, изображенный на рисунке 1 из

Пример. Определить максимальный поток в сети, изображенный на рисунке 1 из

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

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 45

Решение. В качестве начального взять нулевой поток, когда все zij =

Решение.
В качестве начального взять нулевой поток, когда все zij =

0.
Найти какой-нибудь путь из X0 в X8, например, µ1={ X0, X5, X8}.
По этому пути можно пропустить поток величиной не более
θ1 = min{ c05, c58} = min {5, 2} = 2.
Пропустить поток величины 2 единицы по указанному пути. Получен новый поток . При этом пропускные способности дуг пути и симметричных им дуг изменяются.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 46

Пропускные способности дуг пути уменьшаются на 2 единицы: , , т.

Пропускные способности дуг пути уменьшаются на 2 единицы:
, ,
т. е.

дуга (X5, X8) становится насыщенной, а пропускные способности дуг, симметричных дугам пути, увеличиваются на 2 единицы:
, .

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 47

Сеть с новыми пропускными способностями дуг приведена на рисунке 2. #

Сеть с новыми пропускными способностями дуг приведена на рисунке 2.

#

Задачи

принятия решений, связанные с оптимизацией на графах
Слайд 48

Определить новый путь из X0 в X8, проходящий по ненасыщенным дугам,

Определить новый путь из X0 в X8, проходящий по ненасыщенным дугам,

например, µ2={X0, X5, X4, X6, X8}, где
θ2 = min{c05, c54, c46, c68} = min {3, 3, 1, 6} = 1,
и пропустить по этому пути поток величиной в одну единицу. Поменяв пропускные способности дуг этого пути и симметричных им дуг формируются новые пропускные способности:

#

Задачи принятия решений, связанные с оптимизацией на графах

,

,

,

,

,

,
,

Слайд 49

Дуга (X4, X6) становится насыщенной. Сеть с измененными пропускными способностями приведена

Дуга (X4, X6) становится насыщенной. Сеть с измененными пропускными способностями приведена

на рисунке 3.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 50

Далее последовательно найти пути µ3, µ4, µ5, µ6 и по ним

Далее последовательно найти пути µ3, µ4, µ5, µ6 и по ним

пропустить потоки величиной θ3, θ4, θ5, θ6 соответственно:
µ3={ X0, X5, X4, X1, X6, X8}, θ3 = min {2, 2, 1, 2, 5} = 1

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 51

µ4={ X0, X1, X6, X8}, θ4 = min {1, 1, 4}

µ4={ X0, X1, X6, X8}, θ4 = min {1, 1, 4}

= 1

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 52

µ5={ X0, X2, X7, X8}, θ5 = min {4, 3, 2}

µ5={ X0, X2, X7, X8}, θ5 = min {4, 3, 2} =

2

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 53

µ6={ X0, X2, X3, X6, X8}, θ6 = min {2, 2,

µ6={ X0, X2, X3, X6, X8}, θ6 = min {2, 2, 3,

3} = 2

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 54

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

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

сети измененные пропускные способности тех же дуг последней сети

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 55

Положительные значения найденных разностей дают величины zij потоков по соответствующим дугам

Положительные значения найденных разностей дают величины zij потоков по соответствующим дугам

(Xi, Xj) в максимальном потоке из X0 в X8. Искомый максимальной поток приведен на рисунке

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 56

Числа, стоящие у каждой дуги, показывают величину потока по данной дуге,

Числа, стоящие у каждой дуги, показывают величину потока по данной дуге,

а стрелки – направление потока по этой дуге. Величина максимального потока равна
wmax= θ1+ θ2+ θ3+ θ4+ θ5+ θ6 = 2 + 1 + 1 + 1 + 2 + 2 = 9
или, как видно из последнего графа
wmax= z05+ z01+ z02 = 4 + 1 + 4 = 9,
wmax= z58+ z68+ z78 = 2 + 5 + 2 = 9.
Ответ.
Максимальный поток по заданной сети равен 9 единицам.

#

Задачи принятия решений, связанные с оптимизацией на графах

Слайд 57

Пусть имеется игра, в которой участвуют два игрока, причем каждый из

Пусть имеется игра, в которой участвуют два игрока, причем каждый из

игроков имеет конечное число стратегий.
Пусть игрок А имеет т стратегий – А1, А2, … , Ат, а игрок В имеет п стратегий В1,B2,… ,Bn.
Пусть игрок А выбрал стратегию Ai, а игрок В – стратегию Вj. Тогда выбор игроками стратегий Ai и Вj одно­значно определяет исход игры – выигрыш aij игрока А и выигрыш bij игрока B, причем эти выигрыши связаны равенством bij = - aij
(отрицательный выигрыш обычно называют про­игрышем).

#

Теория игр

Слайд 58

Значения aij выигрыша при каждой паре стратегий (в каждой ситуации) {Ai,

Значения aij выигрыша при каждой паре стратегий (в каждой ситуации) {Ai,

Вj}, i=1,2,… ,т, j = 1, 2, … , п (если они известны), удобно записывать или в виде:
1) прямоугольной таблицы, где 2) матрицы
строки – стратегиям игрока A,
а столбцы – стратегиям игрока В

#

Теория игр

Слайд 59

Равновесная ситуация Два игрока А и В, не глядя друг на

Равновесная ситуация
Два игрока А и В, не глядя друг на друга,

кладут на стол по кар­тонному кружку красного (r), зеленого (g) или синего (b) цветов, сравнивают цвета кружков и расплачиваются друг с другом так, как показано в матрице игры
(строки – стратегии игрока А,
а столбцы – стратегии игрока В).
Считая, что эта игра повторяется многократно, необходимо опреде­лить оптимальные стратегии каждого из игроков.

#

Теория игр

Слайд 60

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

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

расчет ответную стратегию игрока В, которую он может выбрать так, чтобы свести выигрыш игрока А к минимуму.
На стратегию Ar он может ответить стратегией Вr (минимальный вы­игрыш равен -2 означает проигрыш игрока А, равный 2),
на стратегию Аg – стратегией Вg или Вb (минимальный выигрыш игрока А равен 1),
на стратегию Аb – стратегией Вg (минимальный выигрыш игро­ка А равен -3).

#

Теория игр

Слайд 61

Минимальные выигрыши записаны в правом столбце таблицы Maxmin. Игрок А останавливает

Минимальные выигрыши записаны в правом столбце таблицы
Maxmin. Игрок А останавливает свой

выбор на стратегии Ag, при которой его минимальный выигрыш максимален (из трех чисел -2, 1 и -3 максимальным является 1):
max min = 1

#

Теория игр

Слайд 62

Если игрок А будет придерживаться этой стратегии, то ему гарантирован вы­игрыш,

Если игрок А будет придерживаться этой стратегии, то ему гарантирован вы­игрыш,

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

#

Теория игр

Слайд 63

Выбирая свою стратегию, игрок В должен учитывать, что при этом стра­тегией

Выбирая свою стратегию, игрок В должен учитывать, что при этом стра­тегией

его противника А может оказаться та, при которой выигрыш игрока А будет максимальным:
– на стратегию Вr он может ответить стратегией Аb (максимальный выигрыш игрока А равен 3),
– на стратегию Bg – стратеги­ей Ar (максимальный выигрыш игрока А равен 2),
– на стратегию Вb – стратегией Аg или Аb (максимальный выигрыш игрока А равен 1).

#

Теория игр

Слайд 64

Мак­симальные выигрыши записаны в нижней строке таблицы Minmax. Игрок В остановит

Мак­симальные выигрыши записаны в нижней строке таблицы
Minmax. Игрок В остановит свой

выбор на стратегии Вb, при которой максимальный выигрыш игрока А минимален (из трех чисел 3, 2 и 1 минимальным является 1):
min max = 1

#

Теория игр

Слайд 65

Если игрок В будет придерживаться этой стратегии, то при любом поведении

Если игрок В будет придерживаться этой стратегии, то при любом

поведении противника он проиграет не больше 1.
В рассматриваемой игре числа maxmin и minmax совпали:
max min = min max = 1
стратегии Аg и Вb
являются оптимальными
стратеги­ями игроков А и В

#

Теория игр

Слайд 66

В общем виде: Число α называется нижней ценой игры. Число β

В общем виде:
Число α называется нижней ценой игры.
Число β называется верхней

ценой игры.
Если α=β то ситуация оказывается равновесной, и ни один из игро­ков не заинтересован в том, чтобы ее нарушить.
В этом случае, общее значение α и β называется просто ценой игры и обозначается через ν = α = β.

#

Теория игр

Слайд 67

Цена игры совпадает с элементом aij матрицы игры А, рас­положенным на

Цена игры совпадает с элементом aij матрицы игры А, рас­положенным на

пересечении i-й строки (стратегия Ai игрока А) и j-го столбца (стратегия Bj игрока B) – минимальным в своей строке и максимальным в своем столбце.
Этот элемент называют седловой точкой матрицы А, или точ­кой равновесия, а про игру говорят, что она имеет седловую точку.
Стратегии Ai и Bj, соответствующие седловой точке, называ­ются оптимальными.

#

Теория игр

Слайд 68

Смешанные стратегии Пусть имеется произвольная т×п игра, заданная т×п –матрицей Т.к.

Смешанные стратегии
Пусть имеется произвольная т×п игра, заданная т×п –матрицей
Т.к. игрок А

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

#

Теория игр

Слайд 69

Смешанная стратегия второго игрока В, имеющего п чистых стратегий, описывается набором

Смешанная стратегия второго игрока В, имеющего п чистых стратегий, описывается

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

#

Теория игр

Слайд 70

Мате­матическое ожидание выигрыша игрока А в условиях ситуации в смешанных стратегиях

Мате­матическое ожидание выигрыша игрока А в условиях ситуации в смешанных

стратегиях (P, Q) равно
Это число принимается за средний выигрыш игрока А при смешанных стратегиях .
Стратегии и называются оптимальными смешанными стратегиями игроков А и В соответственно, если
Пара называется решением игры, а число – ценой игры.

#

Теория игр

Слайд 71

Пример. Пусть имеется игра, заданная 2×6 матрицей: Найти цену игры и

Пример.
Пусть имеется игра, заданная 2×6 матрицей:
Найти цену игры и оптимальные

стратегии игроков А и В.
Решение.
Шаг 1. Анализ игры на наличие седловой точки.
Нижняя цена игры рав­на –1, верхняя цена игры равна 1.
Седловой точки нет. Решение игры нужно искать в смешанных стратегиях.

#

Теория игр

Слайд 72

Шаг 2. Вычисление средних выигрышей игрока А (проводится при условии, что

Шаг 2. Вычисление средних выигрышей игрока А (проводится при условии, что

игрок В выбирает только чистые стратегии).
Из таблицы
легко получить:
(1): ,
(2): ,
(3): ,
(4): ,
(5): ,
(6): .

#

Теория игр

Слайд 73

Шаг 3. Построение нижней огибающей. Аккуратно построив на координат­ной плоскости (р,

Шаг 3. Построение нижней огибающей.
Аккуратно построив на координат­ной плоскости (р,

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

#

Теория игр

Слайд 74

Шаг 4. Отыскание цены игры и оптимальной смешанной стратегии игро­ка А.

Шаг 4. Отыскание цены игры и оптимальной смешанной стратегии игро­ка А.


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

#

Теория игр

Слайд 75

Решая систему уравнений вычисляется р0: р = – р + 5(1

Решая систему уравнений
вычисляется р0:
р = – р + 5(1 – р),
7р

= 5,
Верхняя точка p0 построенной нижней огибающей определяет цену игры v и оптимальную стратегию P0={p0,1–p0} игрока А.
Цена игры , а оптимальная стратегия игрока А равна

#

Теория игр

Слайд 76

Зная стратегии игрока А определим оптимальную смешанную стратегию игрока B. Для

Зная стратегии игрока А определим оптимальную смешанную стратегию игрока B.
Для этого:
Шаг

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

#

Теория игр


Слайд 77

Шаг 2. Приравнять любой из двух средних выигрышей игрока В (игрок

Шаг 2. Приравнять любой из двух средних выигрышей игрока В

(игрок А выбирает только чистые стратегии), отвечающих предложенной смешанной стратегии
к цене игры
при А1: ,
при А2: .

#

Теория игр


Слайд 78

Шаг 3. Получить результат Полное решение игры имеет следующий вид # Теория игр

Шаг 3. Получить результат
Полное решение игры имеет следующий вид

#

Теория игр


Слайд 79

Дерево решений — это графическое изображение процесса принятия решений, в котором

Дерево решений — это графическое изображение процесса принятия решений, в

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

#

Дерево решений


Слайд 80

Дерево решений состоит из узлов и ветвей. Располагаются деревья слева направо.

Дерево решений состоит из узлов и ветвей. Располагаются деревья слева

направо.
Узлы дерева бывают двух видов:
1) места, где принимаются решения, обозначают квадратами □;
2) места появления исходов — кругами ○.
Ветви обозначают возможные альтернативные решения, которые могут быть приняты, и возможные исходы, возникающие в результате этих решений:
1) (------) – соединение квадратов возможных решений
2) (——) – соединение кружков возможных исходов

#

Дерево решений


Слайд 81

Когда все решения и их исходы указаны на дереве, просчитывается каждый

Когда все решения и их исходы указаны на дереве, просчитывается

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

#

Дерево решений


Слайд 82

Пример. Главному инженеру компании надо решить, монтировать или нет новую производственную

Пример.
Главному инженеру компании надо решить, монтировать или нет новую

производственную линию (ПЛ), использующую новейшую технологию. Если новая ПЛ будет работать безотказно, компания получит прибыль 200 млн. рублей. Если же она откажет, компания может потерять 150 млн. рублей.
По оценкам главного инженера, существует 60% шансов, что новая ПЛ откажет. Можно создать экспериментальную установку, а затем уже решать, монтировать или нет ПЛ.

#

Дерево решений


Слайд 83

Эксперимент обойдется в 10 млн. рублей. Главный инженер считает, что существует

Эксперимент обойдется в 10 млн. рублей.
Главный инженер считает, что существует

50% шансов, что экспериментальная установка будет работать.
Если экспериментальная установка будет работать, то 90% шансов за то, что смонтированная ПЛ также будет работать. Если установка не будет работать, то только 20% шансов за то, что ПЛ заработает.
Следует ли строить экспериментальную установку? Следует ли монтировать ПЛ? Какова ожидаемая стоимостная оценка наилучшего решения?

#

Дерево решений


Слайд 84

# Дерево решений


#

Дерево решений


Слайд 85

Решение. В узле F возможны исходы «линия работает» с вероятностью 0,4

Решение.
В узле F возможны исходы «линия работает» с вероятностью 0,4 (что

приносит прибыль 200) и «линия не работает» с вероятностью 0,6 (что приносит убыток -150). Следовательно, оценка узла F определяется следующим образом:
EMV( F) = 0,4 ∙ 200 + 0,6 ∙ ( -150) = -10.
Это число записывается над узлом F.
Оценка узла G: EMV(G) = 0.

#

Дерево решений


Слайд 86

В узле 4 необходимо выбрать между решениями: 1) «монтируем линию» (оценка

В узле 4 необходимо выбрать между решениями:
1) «монтируем линию» (оценка

этого решения EMV( F) = -10) ,
2) «не монтируем линию» (оценка этого решения EMV(G) = 0)
EMV(4) = max {EMV( F), EMV(G)} =
= max {-10, 0} = 0 = EMV(G).
Эта оценка записывается над узлом 4, а решение «монтируем линию» отбрасывается и зачеркивается.

#

Дерево решений


Слайд 87

Аналогично оцениваются узлы B, C, 2, D, E, 3, A: EMV(

Аналогично оцениваются узлы B, C, 2, D, E, 3, A:
EMV(

B) = 0,9 ∙ 200 + 0,1 ∙ (-150) = 180 – 15 = 165.
EMV(С) = 0.
EMV(2)= max{EMV(В), EMV(С} = max {165, 0} = 165 = EMV(5).
Поэтому в узле 2 отбрасывается возможное решение «не монтируем линию».

#

Дерево решений


Слайд 88

EMV(D) = 0,2 ∙ 200 + 0,8 ∙ (-150) = 40

EMV(D) = 0,2 ∙ 200 + 0,8 ∙ (-150) = 40

– 120 = -80.
EMV( E) = 0.
EMV(3) = max {EMV(D), EMV(E)} = max {-80, 0} = 0 = EMV( E).
Поэтому в узле 3 отбрасывается возможное решение «монтируем линию».
ЕМV(A) = 0,5 ∙ 165 + 0,5 ∙ 0 – 10 = 72,5.
EMV(l)=max{EMV(A), EMV(4)}= max {72,5; 0}= 72,5= EMV( A).
Поэтому в узле 1 отбрасывается возможное решение «не строим установку».

#

Дерево решений


Слайд 89

Ответ. Экспериментальную установку строить следует. Если установка работает, то монтируем линию.

Ответ.
Экспериментальную установку строить следует.
Если установка работает, то монтируем линию. Если

установка не работает, то линию монтировать не надо.
Ожидаемая стоимостная оценка наилучшего решения равна 72,5 млн. рублей.

#

Дерево решений


- Предыдущая
Рельеф Смоленской области
Следующая -
Административное право

Похожие презентации

Метод Дельфи
Народный костюм
Арт-терапия
Организация, планирование, мотивация и контроль. Тема 1.3
ГРУППА ПРОДЛЕННОГО ДНЯ ГУО «Ольшанская средняя школа №1»
Ростов Великий
Элементарные сведения о компьютере и устранение простейших неисправностей
Известные протестанты
Культурное развитие России в XIX веке
Трудности адаптации первоклассников в школе. Штурмуйте каждую проблему с энтузиазмом…как если бы от этого зависела Ваша жизнь. Л.Кьюби
Презентация на тему "Об использовании дистанционных образовательных технологий в образовательном процессе" - скачать презен
Архитектура ОС
Кижи
Химия в строительстве
Религия Средневековья
Социальный проект “«Second Hand» для бытовых отходов” Авторы: учащиеся 11Б класса МОАУ СОШ №30 г. Кирова Боровикова В. А. Нестерова Д. С. Ефимова Е. А. Руководитель: Толстова И. Н.
Прерывания
«Программа деятельности педагогического коллектива в работе со слабоуспевающими и неуспевающими учащимися» Булатова Л.П. – ди
Конструирование алгоритмов. Вспомогательный алгоритм. (9 класс)
Государственная экономическая политика
Государство, как политический институт
Видеорегистратор. Видеокамера
Совершенствование вычислительных машин
Презентация «Несовершенная конкуренция на рынке труда».
Теодор Драйзер
Выжигание
Пять самых известных храмов Японии
Судебно-медицинская токсикология
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть