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

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

Для оптимальной стратегии первого игрока и цены игры 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 ;

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

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