рефераты конспекты курсовые дипломные лекции шпоры

Раздел Программирование
/
МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН

Реферат Курсовая Конспект

Выберите учебное заведение

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН - раздел Программирование, Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения Постановка Матричной Игры Двух Лиц С Нулевой Суммой....

Постановка матричной игры двух лиц с нулевой суммой.

Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданной платежной матрицей C=||c_ij||, i=1...,m, j=1...,n (игрока I1 игроку I2).

Основные определения и теоремы.

Смешанные стратегии игроков I1 и I2 — это векторы x=(x₁...,xm) и y=(y₁...,yn)', компоненты которых удовлетворяют условия:

x_i ³ 0, i=1...,m, x₁ +...+ x_m = 1

y_j ³ 0, j=1...,n, y₁ +...+ y_n = 1.

Можно считать, что числа x_i (i=1...,m) и y_j (j=1...,n) есть не что другое, как вероятности выбора і-ї и j-ї стратегий, соответственно, игроками I1 и I2 (і-го строки матрицы C первым игроком та j-го столбца этой же матрицы вторым игроком).

Функция F(x,y)=xCy' называется математической ожиданием платежа игрока I1 игроку I2 (средним выигрышем игрока I2).

Точка (x*,y*) (x*ÎX, y*ÎY) называется седловой точкой функции f(x,y), xÎX, вÎВ, если для произвольных xÎX, вÎВ имеет место неравенство

f(x*,y) £ f(x*,y*) £ f(x,y*).

Теорема.Пусть заданная действительная функция f(x,y), xÎX, вÎВ, для которой существуют

min max f(x,y) max min f(x,y).

xÎX вÎВ вÎВ xÎX

Для того, чтобы выполнялось соотношение

min max f(x,y)= max min f(x,y).

xÎX вÎВ вÎВ xÎX

необходимо и достаточно, чтобы функция f(x,y) имела седловую точку.

Теорема.Функция F(x,y) (средний выигрыш игрока I2) всегда имеет седловую точку.

Компоненты x*, y* точки (x*,y*) седла функции F(x,y) определяют оптимальные смешанные стратегии игроков I1 и I2, соответственно, а цена игры v определяется соотношением:

v = min max F(x,y)= max min F(x,y)= F(x*,y*)

xÎX вÎВ вÎВ xÎX

X = { x = (x₁...,xm) : x_i ³ 0, i=1...,m, x₁ +...+ x_m = 1}

В = { в = (y₁...,yn)' : y_j ³ 0, j=1...,n, y₁ +...+ y_n = 1}.

Теорема.Задача определения оптимальных смешанных стратегий x*и y*игроков I1 и I2 эквивалентная пару двойственных задач линейного программирования:

v ® min

c_1j x₁ +...+ c_mj x_m £ v, j=1...,n

x₁ +...+ x_m = 1, x_i ³ 0, i=1...,m;

v ® max

c_i1 y₁ +...+ с_і_n y_n ³ v, i=1...,m

y₁ +...+ y_n = 1, y_j ³ 0, j=1...,n.

Метод Брауна-Робинсона.

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

Пусть на s-у шаге полученные векторы

M(s)= (m₁(s),...,m_m(s)), N(s)= (n₁(s),...,n_n(s))

компоненты которых m_i(s) и n_j(s) соответственно уровни количествам выбора і-ї и j-ї чистых стратегий первым и вторым игроками на предыдущих шагах. Указанные векторы определяют очевидно частоты выбора соответствующих чистых стратегий игроков. Рассматриваются также векторы относительных частот

x(s)= (x₁(s),...,x_m(s)) но в(s)= (y₁(s),...,y_n(s))'

где x_i(s)= m_i(s)/s, i=1...,m, y_j(s)= n_j(s)/s, j=1...,n.

На s-у шаге величина

c_i1 y₁(s) +...+ с_іn y_n(s), i=1...,m

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

c₁_j x1(s) +...+ c_mj x_m(s), j=1...,n — средний выигрыш второго игрока при условии, что второй игрок выбирает j-й столбец.

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

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

Теорема Брауна-Робинсон.

При неограниченном росте s величины x(s)и в(s) следуют к оптимальным смешанным стратегиям x* и y* первого и второго игроков соответственно.

Программное обеспечение.

Обучающий модуль, с помощью которого матричная игра Решается в диалоге с пользователем за алгоритмом Брауна-Робинсона, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить методом Брауна-Робинсона матричные игры, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9).

Путем сведения двойственных задач линейного программирования и методом Брауна-Робинсона найти оптимальные смешанные стратегии и цену игры матричных игр с такими платежными матрицами:

1)	-8	2	2)	2	-5	3)	-1	5	4)	5	-6	5)	-3	1
	1	-8	,	-4	3	,	6	-4	,	-3	0	,	2	-1	,

6)	-3	3	3	7)	0	1	6	8)	1	0	-1	9)	1	0	-1
	-5	5	-3		7	1	3		0	2	1		-1	2	3
	3	-9	2	,	1	2	0	,	1	-1	3	,	-2	-3	3	.

Лабораторная работа 17.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Методические указания по изучению методов математического программирования Общие рекомендации по использованию программного обеспечения

СОДЕРЖАНИЕ... Общие рекомендации по использованию программного обеспечения... Элементарные преобразования матриц Метод Гаусса...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

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

Постановка задачи.
Решить систему линейных алгебраических уравнений a11x1 + . . . + a1n xn = a10 . . . . . . . . . . . . . . . . . .

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД
Постановка задачи линейного программирования в стандартной форме (СЗЛП). Найти вектор x=

МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.
Изложение модифицированного симплекс-метода. Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенапра

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Изложение двойственного симплекс-метода. Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного програм

Постановка транспортной задачи.
В каждом из пунктов Pi, i=1...,m, производится ai единиц некоторого однородного продукта, а в каждом из пунктов Qj, j=1...,n, потребляется b

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

Свойства транспортной задачи.
1. Сбалансированная транспортная задача всегда допустимая и имеет оптимальное решение. 2. Ранг матрицы А ограничений транспортной

Основные теоремы.
1. Решение транспортной задачи базисное, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл). 2. ДБР

Метод северо-западного угла.
Метод состоит из однотипных шагов, поэтому его формальное изложение дадим лишь для 1-го шага. Заполняем северо-западную клеточку таблицы, покладая x11 = min{a1,

Алгоритм метода потенциалов.
1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов. 2. В дальнейшем метод потенциалов с

Программное обеспечение.
Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО

СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ
Постановка транспортной задачи с ограниченными пропускными способностями (ТЗО). В пункте Pi (i=1

Свойства ТЗО и основные теоремы.
1. Ранг сложенной из векторов Aij матрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, чт

Выходной ДБР ТЗО. 1 этап.
На множестве невычеркнутых клеточек транспортной таблицы находят клеточку (i1,j1) с минимальными транспортными расходами

Выходной ДБР ТЗО. II этап.
Пусть X=||xij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим xi,n+1 = ai – (

Потенциалы.
Потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n, определяются как решение системы vj–ui=cij

Оценки.
Оценки Dijпеременных xij для всех небазисных клеточек вычисляются за формулой Dij=cij–vj+ui (оценки базисных переменных — нулевые). Те

Новый ДБР.
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим та

Алгоритм метода потенциалов.
1. Строится выходной ДБР. 2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых: i) Вычисляются потенциалы u

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА СЕТИ. МЕТОД МИНТИ
Постановка задачи о кратчайшем пути на сети. На сети, что задается графом (I,U), где И — множество вершин,

МЕТОД ФОРДА-ФАЛКЕРСОНА
Постановка задачи о максимальном потоке на сети. На сети, что задается графом (I,U), где I — множество вершин,

Постановка целочисленной задачи линейного программирования.
Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (9.1)

Изложение метода Гомори-1.
Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем. Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9

Алгоритм метода Гомори-1.
1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также

ПРОГРАММИРОВАНИЯ. МЕТОД ГОМОРИ-2
Постановка частично целочисленной задачи линейного программирования (ЧЦЗЛП). Найти вектор x=(x1...,xn

МЕТОД ГОМОРИ-3
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА
Постановка частично дискретной задачи линейного программирования (ЧДЗЛП). Найти вектор x=(x1...,xn

МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

Изложение метода Ленд-Дойга.
Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1

Алгоритм метода Ленд-Дойга.
1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления

ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД
Постановка задачи о назначении. Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию

ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА
Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4). Алгоритм метода Мака.

Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм мето

Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реа

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД
Постановка задачи нелинейного программирования. Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию

Градиентные методы безусловной оптимизации.
Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу x[s+1]=

Метод самого быстрого спуска.
Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага r[s] выбирается по правилу F(x[s]–r

Лiтература
1. Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя.Математические методы исследования операций. Киев, «Высшая школа», 1979. 2. Ю.Д.Попов. Линейное и нел