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

Пусть задана матрица игры

.

Для оптимальной стратегии первого игрока и цены игры u выполняется неравенство , или (разделив на u) , обозначая , получим:

Так как первый игрок стремится получить максимальный выигрыш, то он должен обеспечить минимум величине 1/u. С учётом этого определение оптимальной стратегии сводится к нахождению минимума функции

при условиях

.

Аналогично определение оптимальной стратегии второго игрока сводится к нахождению максимума функции

при условиях

,

где z_j /u.

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

Прямая задача ; .

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

Используя решения пары задач, можно выявить оптимальные стратегии и цену игры:

.

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

1) составляют пару двойственных задач, эквивалентных данной игре;

2) определяют оптимальные планы двойственных задач;

3) находят решение игры по соотношениям между планами задач, оптимальными стратегиями и ценой игры.

Пример 2.4.. Найти решение игры, определяемой матрицей

.

Решение.Пара двойственных задач:

Прямая

Двойственная

Из решения пары задач:

;

u⁰ = (1/3; 2/3; 0);

z⁰ = (0; 1/3; 2/3).

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

Пусть задана симметричная пара двойственных задач:

.

Тогда этой паре двойственных задач можно поставить в соответствие игру, определяемую матрицей

.

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

 

 

3. Методические указания по выполнению лабораторной работы

Перед выполнением лабораторной работы необходимо ознакомиться с её целью, основными теоретическими положениями, особенностями использования табличного процессора (ТП) Excel 7.0 при решении задач игрового выбора.

Каждый студент получает у преподавателя индивидуальное задание на выполнение лабораторной работы.

В процессе лабораторной работы необходимо:

1) подготовить исходные данные для решения задачи игрового выбора с использованием ТП Excel 7.0,

2) решить задачу игрового выбора в смешанных стратегиях,

3) решить задачи игрового выбора исходя из критериев минимального,максимального выигрыша, критерия Вальда, Гурвица, Сэвиджа.

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

4. форма отчётности по выполненной лабораторной работе

Отчёт должен содержать:

- титульный лист;

- содержательную и формальную постановку задачи игрового выбора (ЦП);

- распечатки результатов решения и исследования задач игрового выбора ТП Excel 7.0 ;

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

Отчёт о лабораторной работе представляется к моменту её защиты.