Двойственный Симплексный Метод

(2 часа)

 

1. ЦЕЛЬ РАБОТЫ:

1.1. Закрепление навыков преобразования условий задач ЛП;

1.2. Формирование навыков записи условий двойственных задач;

1.3. Формирование навыков решения двойственных пар симплексным методом;

1.4. Формирование навыков решения двойственных пар в Excel с использованием надстройки Поиск решения;

1.5. Формирование навыков решения двойственных пар в MathCAD с использованием функций Minimize и Maximize.

2. СОДЕРЖАНИЕ РАБОТЫ:

2.1. Ознакомьтесь с теоретическим материалом;

2.2. Выполните задания из пункта 4;

2.3. Ответьте на контрольные вопросы.

3. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:

3.1. ПК;

3.2. MS Office 2007;

3.3. MS Excel 2007с надстройкой Поиск решения;

3.4. MathCAD

4. ВЫПОЛНЕНИЕ:

4.1. Ознакомьтесь с математической моделью задачи линейного программирования. Установите форму полученной записи задачи ЛП. Преобразуйте ее к формам: общая, симметричная, основная ЗЛП.

4.2. На основе исходной математической модели постройте условие задачи двойственной к заданной.

4.3. Установите возможность решения одной из задач двойственной пары симплексным методом. Выполните решение симплексным методом. Запишите полученные решения прямой и двойственной задач.

4.4. Решите обе задачи двойственной пары используя утилиту Поиск решения в MS Excel.

4.5. Решите обе задачи двойственной пары используя среду MathCAD.

5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

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

(2)

, (3)

, (4)

где - заданные постоянные величины.

Основной или канонической задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (1) при ограничениях вида (3) и (4).

Для записи условия двойственной задачи используют следующие правила:

1. Число переменных двойственной задачи равно числу ограничений исходной задачи. Число ограничений двойственной задачи равно числу переменных исходной задачи.

2. Коэффициентами целевой функции F* являются числа . Если исходная целевая функция (1) стремилась к максимуму, то двойственная целевая функция стремится к минимуму и наоборот.

3. Коэффициентами системы ограничений двойственной задачи будут коэффициенты полученные транспонированием матрицы коэффициентов системы ограничений исходной задачи. Правыми частями ограничений двойственной задачи будут коэффициенты целевой функции исходной задачи.

4. Если j-ая переменная исходной задачи была неотрицательна, то j-ое ограничение двойственной задачи имеет знак >=. Если j-ая переменная исходной задачи была произвольной, то j-ое ограничение двойственной задачи имеет знак =.

Если i—ое ограничение исходной задачи было неравенством, то i-ая переменная двойственной задачи будет неотрицательной. Если i—ое ограничение исходной задачи было равенством, то i-ая переменная двойственной задачи будет произвольной.

Задание 1.

По условию задачи вашего варианта:

1. Установите форму записи полученного условия.

2. Внесите изменения в форму записи задачи так, чтобы она соответствовала остальным формулировкам ЗЛП.

Задание 2.

1. Запишите условие задачи двойственной к исходной.

Задание 3.

1. Установите какую из задач двойственной пары возможно решить симплексным методом.

2. Запишите условие этой задачи в форме основной задачи и в векторной форме.

3. Решите задачу симплексным методом.

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

5. Сделайте выводы.

Задание 4.

1. Внесите на лист 1 электронной таблицы условие прямой задачи в форме адаптированной для решения ЗЛП утилитой поиск решения.

2. Заполните разделы окна поиск решения и выполните его. Сохраните результаты и составьте отчет по результатам.

3. Внесите на лист 2 электронной таблицы условие двойственной задачи в форме адаптированной для решения ЗЛП утилитой поиск решения.

4. Заполните разделы окна поиск решения и выполните его. Сохраните результаты и составьте отчет по результатам.

Задание 5.

1. Запишите на электронный лист среды MathCAD матричную форму условия исходной задачи. А именно: а—матрицы коэффициентов системы ограничений, b—матрицы свободных коэффициентов системы ограничений, с—матрица коэффициентов целевой функции, х—начальные значения неизвестных.

2. Допишите к ним матрицы для двойственной задачи. А именно: y—матрица начальных значений неизвестных. Вычислите матрицу d—коэффициентов системы ограничений двойственной задачи по формуле d:=a^T

3. Составьте целевые функции задач двойственной пары f(x):=cx и g(y):=by

4. Решите прямую задачу. В ее разделе Given запишите ax<=b и x>=0. Вычислите k:=Maximize(f,x) и k= f(k)=

5. Решите двойственную задачу. В ее разделе Given запишите dy>=c и y>=0. Вычислите m=Minimize(g,y) и m= g(m)=

6. ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:

6.1. Номер практической работы, ее название, номер выполняемого варианта.

6.2. Номер задания.

6.3. Условие решаемой задачи.

6.4. Математическая модель задачи.

6.5. Решение ЗЛП симплексным методом в ручную.

6.6. Распечатка результата решения ЗЛП в Excel включающая фрагмент эл.листа с условием задачи и отчет по результатам.

6.7. Распечатка результата решения в MathCAD.

7. КОНТРОЛЬНЫЕ ВОПРОСЫ:

7.1. Определение основной, симметричной и общей ЗЛП.

7.2. Запись условия двойственной ЗЛП и правила ее получения.

7.3. Алгоритм решения ЗЛП симплексным методом.

7.4. Алгоритм использования утилиты Поиск решения для решения ЗЛП.

7.5. Решения ЗЛП симплексным методом в MathCAD.

 

 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №3

ТРАНСПОРТНАЯ ЗАДАЧА

(2 часа)

 

1. ЦЕЛЬ РАБОТЫ:

1.1. Формирование навыков составления математических моделей транспортных задач;

1.2. Формирование навыков определения опорных планов транспортных задач методами северо-западного угла, минимальной стоимости и аппроксимации Фогеля;

1.3. Формирование навыков оптимизации опорных планов транспортных задач;

1.4. Формирование навыков решения транспортных задач в Excel с использованием надстройки Поиск решения;

1.5. Формирование навыков решения транспортных задач в MathCAD с использованием функции Minimize.

2. СОДЕРЖАНИЕ РАБОТЫ:

2.1. Ознакомьтесь с теоретическим материалом;

2.2. Выполните задания из пункта 4;

2.3. Ответьте на контрольные вопросы.

3. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:

3.1. ПК;

3.2. MS Office 2007;

3.3. MS Excel 2007с надстройкой Поиск решения;

3.4. MathCAD

4. ВЫПОЛНЕНИЕ:

4.1. Ознакомьтесь с условием транспортной задачи. Составьте ее математическую модель.

4.2. Определите опорные план транспортной задачи тремя методами: Северо-западного угла; Минимальной стоимости; Аппроксимации Фогеля. Для каждого плана вычислите значение целевой функции.

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

4.4. Решите транспортную задачу используя утилиту Поиск решения в MS Excel.

5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

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

при условиях

где – заданные постоянные величины.

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

Опорный план транспортной задачи называется невырожденным, если содержит ровно n+m-1 ненулевое значение.

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

Сравниваются количества запасов и потребностей. То количество, которое меньше, записывается в рассматриваемую ячейку. Если это запасы, то из рассмотрения убирается строка, в противном случае убирается столбец. Оставшаяся величина уменьшается на количество, записанное в рассматриваемую ячейку.

В соответствии с методом северо-западного угла для заполнения выбирается ячейка в левом верхнем углу невычеркнутой части таблицы.

В соответствии с методом минимальной стоимости для заполнения выбирается ячейка, тариф перевозок в которой является наименьшим.

В соответствии с методом аппроксимации Фогеля в каждом столбце и каждой строке вычисляются разности между двумя максимальными тарифами. Среди вычисленных разностей выбирается минимальная. В соответствующем элементе таблицы выбирается минимальный тариф – эта ячейка и заполняется.

Задание 1.

По условию задачи вашего варианта:

1. Установите количество переменных.

2. Составьте целевую функцию. Если по условию задачи требуется определить максимальное значение целевой функции, то используя правила работы с условиями ЗЛП преобразуйте ее так, чтобы она стремилась к минимуму.

3. Составьте и запишите систему ограничений.

4. Запишите условие транспортной задачи в виде таблицы. Определите форму записи модели открытая или закрытая. Если модель является открытой, то измените таблицу так, чтобы модель стала закрытой.

Задание 2.

1. Определите опорный план в соответствии с методом северо-западного угла.

2. Проверьте его на не вырожденность.

3. Вычислите значение целевой функции для найденного плана.

4. Определите опорный план в соответствии с методом минимальной стоимости.

5. Проверьте его на не вырожденность.

6. Вычислите значение целевой функции для найденного плана.

7. Определите опорный план в соответствии с методом аппроксимации Фогеля.

8. Проверьте его на не вырожденность.

9. Вычислите значение целевой функции для найденного плана.

Задание 3.

1. Установите какой из найденных планов дает лучший результат.

2. Проверьте его на оптимальность методом потенциалов.

3. Если план не оптимален, то постройте цикл и проведите операцию сдвига по циклу.

4. Вновь полученный план проверьте на оптимальность.

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

Задание 4.

1. Внесите на лист электронной таблицы условие прямой задачи в форме адаптированной для решения ЗЛП утилитой поиск решения. А именно:

2. В ячейки B1, C1, D1 … впишите B1, B2, B3 …

3. В ячейки A2, A3, A4 … впишите A1, A2, A3 …

4. Блок B2:D4 (последняя ячейка соответствует примеру) внесите 0—это начальные значения переменных.

5. В конце каждого столбца и каждой строки создайте формулу из суммы переменных—это левые части системы ограничений.

6. Блок B6:D8 заполните коэффициентами целевой функции.

7. В ячейку G10 внесите формулу (=) полученную как сумму произведений ячеек коэффициентов на ячейки переменные.

8. В ячейки B9, C9, D9 … внесите потребности

9. В ячейки F6, F7, F8 … внесите запасы.

10. Выделите ячейку с целевой функцией. Перейдите к утилите поиск решения.

11. Заполните разделы окна поиск решения. Создавая систему ограничений внесите дополнительно условие о том, что все переменные—целые числа. Выполните Поиск решения. Сохраните результаты и составьте отчет по результатам.

 

6. ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:

6.1. Номер практической работы, ее название, номер выполняемого варианта.

6.2. Номер задания.

6.3. Условие решаемой задачи.

6.4. Математическая модель задачи.

6.5. Решение транспортной задачи в ручную.

6.6. Распечатка результата решения транспортной задачи в Excel включающая фрагмент эл.листа с условием задачи и отчет по результатам.

7. КОНТРОЛЬНЫЕ ВОПРОСЫ:

7.1. Определение транспортной задачи.

7.2. Математическая модель транспортной задачи.

7.3. Методы поиска опорного плана транспортной задачи.

7.4. Метод проверки опорного плана транспортной задачи на оптимальность.

7.5. Цикл. Правило сдвига по циклу.

 

 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №4

МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА

(2 часа)

 

1. ЦЕЛЬ РАБОТЫ:

1.1. Формирование навыков составления математических моделей задач нелинейного программирования;

1.2. Формирование навыков решения задач нелинейного программирования методом Лагранжа;

1.3. Формирование навыков решения задач нелинейного программирования в MathCAD.

2. СОДЕРЖАНИЕ РАБОТЫ:

2.1. Ознакомьтесь с теоретическим материалом;

2.2. Выполните задания из пункта 4;

2.3. Ответьте на контрольные вопросы.

3. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:

3.1. ПК;

3.2. MS Office 2007;

3.3. MathCAD.

4. ВЫПОЛНЕНИЕ:

4.1. Ознакомьтесь с условием задачи нелинейного программирования. Составьте ее математическую модель.

4.2. Решите задачу нелинейного программирования методом множителей Лагранжа.

4.3. Решите задачу нелинейного программирования, используя среду MathCAD.

5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции

(1)

при условии, что её переменные удовлетворяют соотношениям

(2)

где f и g_i – некоторые известные функции n переменных, а b_i – заданные числа.

Рассмотрим частный случай общей задачи нелинейного программирования (1) – (2), предполагая, что система ограничений (2) содержит только уравнения, отсутствует условия неотрицательности переменных и - функции, непрерывные вместе со своими частными произведениями

(3)

. (4)

В курсе математического анализа в задачу (3) – (4) называют задачей на условный экстремум или классической задачей оптимизации.

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

находят частные производные и и рассматривают систему n+m уравнений

(6)

c n+m неизвестными . Всякое решение системы уравнений (19) определяет точку в которой может иметь место экстремум функции . Следовательно, решив систему уравнений (6), получают все точки, в которых функция (3) может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума.

Таким образом, определение экстремальных точек задачи (3) – (4) методом множителей Лагранжа включает следующие этапы:

1⁰. Составляют функцию Лагранжа.

2⁰. Находят частные производные от функции Лагранжа по переменным и и приравнивают их нулю.

3⁰. Решая систему уравнений (6), находят точки, в которых целевая функция задачи может иметь экстремум.

4⁰. Среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значения функций (3) в этих точках.

Задание 1.

По условию задачи вашего варианта:

1. Установите форму записи полученного условия.

2. Внесите изменения в форму записи задачи так, чтобы она соответствовала остальным формулировкам ЗНЛП.

Задание 2.

1. Составьте функцию Лагранжа.

2. Найдите частные производные функции Лагража по всем переменным.

3. Решите систему уравнений, составленную из частных производных.

4. Найдите значение функции в полученных точках.

Задание 3.

1) Откройте электронный лист системы MathCAD.

2) Составьте функцию f. Например: f(x1,x2):=2*x1+4*x2-x1²-2*x2² Количество переменных должно соответствовать условию задачи.

3) Составьте градиент функции f, используя для каждой частной производной отдельную функцию. Например: G1(x1,x2):=df(x1,x2)/dx1 и G2(x1,x2):=df(x1,x2)/dx2 Далее получите явный вид каждой части градиента.

4) Введите первую точку для организации вычислений. Точку задавайте как матрицу столбец, число строк в которой равно числу переменных в вашей задаче. Например: X:=

5) Далее следует решить задачу линейного программирования.

6) В этом решении ранее на первом шаге мы вводили с клавиатуры коэффициенты целевой функции, создавая матрицу с. В этот раз вычислим каждый коэффициент матрицы с используя градиент целевой функции. Например: с₀:=G1(X₀,X₁) c₁:=G2(X₀,X₁) Затем получим явный вид матрицы с.

7) На следующем шаге мы создавали матрицу начальных значений неизвестных х. Эта переменная уже используется нами в решении, поэтому заменим ее на y. Например: y:=

8) Далее создайте матрицы коэффициентов системы ограничений и свободных коэффициентов системы ограничений. Например: а:= и b:=

9) Создайте целевую функцию F(y):=c*y.

10) Заполните раздел Given записями a*y<=b и y>=0

11) Завершите решение задачи линейного программирования записями Z:=Maximize(F,y) и Z= В нашем примере должно получиться Z=

12) Составьте уравнения для х1 и х2 позволяющие определить координаты следующей точки. Вместо множителя лямбда используйте переменную m1 (чтобы не допускать двусмысленности в прочтении, т.к. l похожа на 1). Например: x1:=X₀+m1*(1.6-X₀) и x2:=X₁+m1*(3.2-X₁). Числа 1.6 и 3.2 взяли из записи Z=

13) Получите явный вид целевой функции для новых значений переменных х1 и х2. f(x1,x2)->

14) Запишите ее дифференциал по переменной m1. df(x1,x2)/dm1->

15) Составьте новую функцию M(m1) совпадающую по записи с явным видом дифференциала. Она нужна для решения уравнения и определения шага вычислений.

16) Для решения уравнения запишите m1:=0 и m:=root(M(m1),m1) и получите явное значение m1=

17) Присвойте переменным x1 и x2 новые значения. Например: x1:=X₀+m1*(1.6-X₀) И вычислите их значения x1=

18) Проверьте не является ли выполненная итерация последней. Для этого запишите |f(0,0)-f(x1,x2)|=

19) Для сохранения последнего результата выполните присваивание q:=f(x1,x2)

20) Если результат меньше 0,01, то вычисления завершены. Если нет, то повторите весь процесс от пункта 4.

21) Для этого выделите нужные участки электронного листа, скопируйте их, во вновь полученных записях внесите изменения. Какие?

22) Вместо X:= запишите X:=

23) В записи соответствующей пункту 12 измените числа Z. И переменную m1 замените на m2.

24) Переменную m1 замените на m2 также во всех записях ниже.

25) Составьте новую формулу для M(m2)

26) В записи подмодульного выражения уберите f(0,0) и впишите вместо него q.

27) Оцените полученный результат.

6. ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:

6.1. Номер практической работы, ее название, номер выполняемого варианта.

6.2. Номер задания.

6.3. Условие решаемой задачи.

6.4. Математическая модель задачи.

6.5. Решение ЗНЛП методом множителей Лагранжа в ручную.

6.6. Распечатка результата решения в MathCAD.

7. КОНТРОЛЬНЫЕ ВОПРОСЫ:

7.1. Определение ЗНЛП.

7.2. Алгоритм решения ЗНЛП методом множителей Лагранжа.

7.3. Решения ЗНЛП методом множителей Лагранжа в MathCAD.

 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №5

ГРАДИЕНТНЫЕ МЕТОДЫ

(2 часа)

 

1. ЦЕЛЬ РАБОТЫ:

1.1. Формирование навыков составления математических моделей задач нелинейного программирования;

1.2. Формирование навыков решения задач нелинейного программирования градиентными методами.

1.3. Формирование навыков решения задач нелинейного программирования в MathCAD.

2. СОДЕРЖАНИЕ РАБОТЫ:

2.1. Ознакомьтесь с теоретическим материалом;

2.2. Выполните задания из пункта 4;

2.3. Ответьте на контрольные вопросы.

3. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:

3.1. ПК;

3.2. MS Office 2007;

3.3. MathCAD.

4. ВЫПОЛНЕНИЕ:

4.1. Ознакомьтесь с условием задачи нелинейного программирования. Составьте ее математическую модель.

4.2. Решите задачу нелинейного программирования градиентными методами.

4.3. Решите задачу нелинейного программирования, используя среду MathCAD.

5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

Пусть требуется найти максимальное значение вогнутой функции.

(1)

при условиях

. (3)

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

Процесс нахождения решения задачи начинают с определения точки, принадлежащей области допустимых решений задачи. Пусть эта точка x^(k), тогда в этой точке вычисляют градиент функции (1)

и строят линейную функцию

(4)

Затем находят максимальное значение этой функции при ограничениях (2) и (3). Пусть решение данной задачи определяется точкой Z^(k). Тогда за новое допустимое решение исходной задачи принимают координаты точки x^{(k+1 )} :

(5)

где λ^k –некоторое число, называемое шагом вычислений и заключенное между нулем и единицей (0≤λ^k≤1). Это число λ^k берут произвольно или определяют таким образом, чтобы значение функции в точке f( , зависящее от λ^k, было максимально. Для этого необходимо найти решение уравнения и выбрать его наименьший корень. Если его значение больше единицы, то следует положить λ^k=1. После определения числа λ^k находят координаты точки , вычисляют значение целевой функции в ней и выясняют необходимость перехода к новой точке . Если такая необходимость имеется, то вычисляют в точке градиент целевой функции, переходит к соответствующей задаче линейного программирования и находит ее решение. Определяет координаты точки и исследуют необходимость проведения дальнейших вычислений. После конечного числа шагов получают с необходимой точностью решение исходной задачи.

Итак, процесс нахождения решения задачи (1) – (3) методом Франка-Вулфа включает следующие этапы:

1⁰. Определяют исходное допустимое решение задачи.

2⁰. Находят градиент функции (1) в точке допустимого решения.

3⁰. Строят функцию (4) и находят ее максимальное значение при условиях (2) и (3).

4⁰. Определяют шаг вычислений.

5⁰. По формулам (5) находят компоненты нового допустимого решения.

6⁰. Проверяют необходимость перехода к последующему допустимому решению. В случае необходимости переходят к этапу 2⁰, в противном случае найдено приемлемое решение исходной задачи.

Задание 1.

По условию задачи вашего варианта:

1. Установите форму записи полученного условия.

2. Внесите изменения в форму записи задачи так, чтобы она соответствовала остальным формулировкам ЗНЛП.

Задание 2.

1. Построить область допустимых решений функции.

2. Определить точку, принадлежащую области допустимых решений задачи.

3. Найти градиент функции в этой точке.

4. Составить линейную функцию и найти ее максимальной или минимальное решение на области допустимых решений функции.

5. Определить шаг вычислений. Найти компоненты нового допустимого решения.

6. Проверить необходимость перехода к следующему допустимому решению.

6. ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:

6.1. Номер практической работы, ее название, номер выполняемого варианта.

6.2. Номер задания.

6.3. Условие решаемой задачи.

6.4. Математическая модель задачи.

6.5. Решение ЗНЛП градиентным методом.

7. КОНТРОЛЬНЫЕ ВОПРОСЫ:

7.1. Определение ЗНЛП.

7.2. Алгоритм решения ЗНЛП градиентным методом.

 

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №6-7

ТЕОРИЯ ИГР

(6 часов)

1. ЦЕЛЬ РАБОТЫ:

1.1. Научиться решать задачи теории игр.

2. СОДЕРЖАНИЕ РАБОТЫ:

2.1. Ознакомьтесь с теоретическим материалом;

2.2. Выполните задания из пункта 4;

2.3. Ответьте на контрольные вопросы.

3. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:

3.1. ПК;

3.2. MS Office 2007;

3.3. MathCAD.

4. ВЫПОЛНЕНИЕ:

4.1. Найти решение игры в смешанных стратегиях. Сравнить найденное решение с верхней и нижней ценой игры.

5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

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

· Игра – упрощённая модель конфликтной ситуации.

· Игрок – сторона, участвующая в конфликте.

· Парная игра – игра, в которой сталкиваются интересы двух сторон.

· Игра с нулевой суммой – парная игра, в которой выигрыш одной стороны равен проигрышу другой.

· Ход – выбор допустимого действия и его осуществление.

· Личный ход – сознательный выбор игроком допустимого действия и его осуществление.

· Случайный ход – выбор допустимого действия с помощью механизма случайного выбора (например, подбрасывания монеты) и его осуществление.

· Правила игры – совокупность условий, регламентирующая:

Ö возможные действия игроков,

Ö объём сведений каждой стороны о поведении другой,

Ö результат, к которому приводит каждая совокупность ходов.

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

· Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает игроку максимальный средний выигрыш[1].

· Конечная игра – у каждого игрока имеется конечное количество стратегий.

· m ´ n игра – конечная парная игра, в которой у одного игрока имеется m стратегий, а у второго n стратегий.

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

Платёжная матрица игры

Платёжной матрицей m ´ n игры с нулевой суммой (или, просто, матрицей игры) называется матрица

 

 

B A	B1	B2	…	Bn
A1	a11	a12	…	a1n
A1	a21	a22	…	a2n
…	…	…	…	…
Am	am1	am2	…	amn

в которой

A₁, …, A_m – все стратегии игрока A,

B₁, …, B_m – все стратегии игрока B,

a_ij – выигрыш (положительный или отрицательный) игрока A при выборе им стратегии A_i и стратегии B_j игроком B.

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

Стратегии игроков:

игрок A: A1 – спрятаться в убежище № 1,

A2 – спрятаться в убежище № 2;

игрок B: B1 – искать в убежище № 1,

B2 – искать в убежище № 2;

Матрица игры "поиск":

B A	B1	B2
A1	-1
A1		-1

Некоторые выводы, вытекающие из игры "поиск".

Если игра проводится один раз, то говорить о преимуществе той или иной стратегии смысла нет.

Если при многократном проведении игры игрок будет придерживаться одной стратегии или чередования стратегий в определённой последовательности, то противник догадается об этом и начнёт выигрывать. Поэтому от верного проигрыша игроков может спасти только случайное чередование стратегий. Например, игрок перед своим ходом подбрасывает монету и, если выпала "решка", то игрок выбирает первую стратегию, а если "орёл", то вторую.