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

Пусть дана задача линейного программирования

F(x) = c₁x₁ + … + c_mx_n → max

а₁₁х₁ + а₁₂х₂ + … + с_m1х_n ≤ в₁

а₂₁х₁ + а₂₂х₂ + … + с_m2х_n ≤ в₂

....а_m1х₁ + а_m2х₂ + … + с_mnх_n ≤ в_m

Двойственной задачей является задача

Ζ (Y)= в₁у₁ + в₂у₂ + … + в_mу_m → min

а₁₁у₁ + а₁₂у₂ + … + с_m1у_n ≥ с₁

а₂₁у₁ + а₂₂у₂ + … + с_m2у_n ≥ с₂

….

а_n1у₁ + а_n2у₂ + … + с_mnу_n ≥ с_m

y_j ≥0, j = 1, 2 … m

y₁, y₂…y_m – неизвестные двойственной задачи

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

Если одна из задач не имеет решения, то так же не имеет решения и двойственная задача. Это утверждение позволяет сводить задачи на min, max.

Пример: Ζ (x) = 6x₁ + 7х₂ + 9x₃ → min

1х₁ + 2х₂ + 3х₃ ≥ 5

1х₁ + 1х₂ + 1х₃ ≥2

1х₁ + 2х₂ + 6х₃ ≥7

Х₁≥0; Х₂≥0; Х₃≥0

F(Y)= 5у₁ + 2у₂ + 4у₃ → max A = A^T =

1у₁ + 2у₂ + 1у₃ ≤ 6

2у₁ + 1у₂ + … + 2у₃ ≤ 7

3у₁ + 1у₂ + 6у₃ ≤ 9

Формулы вычисления среднего выигрыша

Чтобы найти средние или математические ожидания нужно каждое значение случайной величины умножить на соответствующую вероятность и результат сложить. Значению a_ij соответствующей вероятности р_i, q_j

a_ij соответствующая вероятность р_i, q_j; Н_А(Р,Q)

Н_А(Р,Q) = (для первого)

Н_B(Р,Q) = (для второго)

Биматричные игры. Основные понятия.

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

В бескоалиционных играх исключается сотрудничество между игроками, игроки принимают решения независимо друг от друга. А в кооперативных играх до начала игры игроки образуют коалиции и принимают взаимо-обязывающие соглашения о своих стратегиях. Некооперативные игры далее будем называть (Биматричными) Биматричная игра – подобна антагонистической игре и задается платежной матрицей, но теперь каждому игроку принадлежит своя матрица. Пусть игрок А имеет m стратегий [А1..А2…Аm], тогда игрок В имеет n стратегий [В1..В2..Вn]. Если игрок В применяет стратегию i, тогда игрок А применяет стратегию j, то в результате первый игрок получит выигрыш Аij а второй игрок получит выигрыш Вij. Общий вид платежных матриц игроков:

Платежная матрица игрока А

	В1	В2	…	Вn
A1	A11	A12	…	A1n
A2	A21	A22	…	A2n
…	…	…	…	…
Am	Am1	Am2	…	Amn

Платежная матрица игрока В

	В1	В2	…	Вn
A1	B11	B12	…	B1n
A2	B21	B22	…	B2n
…	…	…	…	…
Am	Bm1	Bm2	…	Bmn

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

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

Р1- частота принятия стратегии А1

Р2- частота принятия стратегии А2

Р3- частота принятия стратегии А3 Все эти величины положительны и их сумма = 1.

Аналогично и для игрока В:

q1- частота принятия стратегии B1

q2- частота принятия стратегии B2

q3- частота принятия стратегии B3 Все эти величины также положительны и их сумма = 1.

Формулы вычисления средних выигрышей Что бы найти среднее и максимальное значение, нужно каждое значение величины умножить на вероятность и результат сложить. Аij – соответствует вероятность Рi x qi

Отсюда: Ha (P,Q) = НB (P,Q) =

21. Примеры биматричных игр в экономике.

22. Равновесная ситуация. Теорема Нэша. Система неравенств, определяющая равновесную ситуацию.

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

Неравенство 2. На(0,q) ≤ Ha (p*q*)

Ha(1,q) ≤ Ha (p*q*)

Неравенство 3.

НB(p*,0) ≤ HB (p*q*)

HB(p*,1) ≤ HB (p*q*)

Неравенство 2 означает, что неравенство 1.1 достаточно проверить для двух крайних значений (когда р=0 и р=1).

Точнее говоря для чистых стратегий. Аналогично неравенство 3, это проверка неравенства 1.2 для чистых стратегий. Для нахождения точки равновесия будем решать неравенство (2 и 3) для этого воспользуемся формулой (*) Согласно этому представлению:

Ha(p*,q*) = Ср*q*-2p*+ Ɣq* + a22 (4)

Ha(0,q*) = Ɣq* + a22 (5)

Ha(1,q*) = Cq*- α + Ɣq* + a22 (6)

Первое неравенство (2) имеет вид:

Ha(p*,q*) - На(0,q*)≥0

или с учетом (4) и (5)

р*(Сq*- α) ≥0 (7)

Второе неравенство (2) имеет вид:

Ha(p*,q*) - На(1,q*)≥0 или с учетом (4) и (5) Ср*q* - αp* - (Cq*- α) ≥0 = Cq*-(p*-1) – α(p*-1) ≥0 (8)

Неравенство (8):

(р*-1)(Сq*- α) ≥0

p*(Cq*- α) ≥0 (9)

Аналогично решим неравенство (3)

Нв(p*q*) = Dp*q*- βq*+ Δ p + βq + B22 (10)

HB(p*q*) = Δ p+ B22 (11)

HB=(p*,1) = Dp*- β+ Δ p* + βq + B22 (12)

Первое неравенство (3)

Нв(р*,0) ≤ Нв(р*,q*)

Dp*q*- βq*≥0

q*(Dp*- β)≥0

Второе неравенство (3)

HB(p*q*) – HB (p*,1) ≥0

Учитывая (10) и (12)

Dp*q* - βp*-(Dp*-β) = p* x D(q*-1)- β(q*-1) ≥0

(q*-1)(Dp*- β) ≥0

q*(Dp*- β) ≥0

23. Решение биматричной игры .

Биматричная игра 2х2

А11	А12
А21	А22

А=

B11	B12
B21	B22

В =

Р – частота применения 1 игроком стратегии (А1)

1-Р – частота применения стратегии (А2)

q – частота применения стратеги (В1)

1- q – частота применения стратегии (В2)

Формулы

На (р, q); Нв (р, q)

1. На (р, q) = а11*(р q) + р(1- q) + а21*(1-р)q + а22*(1-р)(1- q)

На = (а11-а12-а21+а22)р q + (а12-а22)р + (а21-а22)* q + а22

3. Нв = (в11-в12-в21+в22)р q + (в12-в22)р + (в21-в22)* q + в22

Введем следующие обозначения:

С = А11- А12- А21+А22

D = B11- B12- B21+B22

α = A22-A12

β = B22-B21

Ɣ = А21-А22

Δ = B12-B22

Ha(p;q) = C*(pq) – αp+ Vq +A22

(*)

Hb(p;q) = D*(pq) – Δ p + βq + B22

Раздел II.

Определение: Пара чисел р* и q*, 0≤ р*≤ 1; 0 ≤ q*≤1.

Определим равновесие, если выполнены 2 условия;

1. (Неравенство)

1.1 На (рq) < Ha(p*,q*) Ɣ p ϵ [0;1]

1.2 HB(p*q) ≤ HB(p*q*)

где, На (средний выигрыш 1 го игрока)

НВ (средний выигрыш 2 го игрока)

Неравенство (1) означает стратегии (p*q*) – определяем равновесие, если отклонение одного из игроков или условие, что другой игрок сохраняет свой выбор приводит к тому, что выигрыш относившегося игрока только уменьшается, таким образом, отклонение от равновесия не выгодно самому игроку.