5.Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.

Если план перевозок X = {x_ij} – оптимальное, то ему соответствует m+n чисел, называется потенциалами:

U₁,U₂,…,U_m – поставщиков;V₁,V₂,…,V_n – потребителей, которые удовлетворяют условию:

x_ij>0 ((i,j) - базис), то U_i+V_j= x_ij (1)

x_ij=0 ((i,j) - свободные), то ∆_ij=(ij - U_i - V_j) (2)

если есть одна отрицательная оценка, следовательно, план не оптимален.

6.Понятие об игровых моделях

Часто выбор приходится делать в условиях риска. В элементах теории игр сталкиваются интересы нескольких сторон. Каждая из сторон стремится к оптимальности. Конфликт – ситуация которая порождается различием интересов нескольких сторон или интересов одной стороны, преследующей противоречивые цели. Конфликт может произойти не только в результате сознательного противодействия сторон, но и как действие стихийных сил. Игра – математическая модель конфликтной ситуации. Теория игр – раздел прикладной математики, разрабатывающей научно – обоснованные методы изучения конфликтной ситуации. Методы решения можно найти, если игра (научная ситуация) повторяется много раз. Игроки – заинтересованные стороны. Правила – система условий определяет: варианты действий игроков (возможные стратегии)→оптимальные;

Объем информации каждого игрока о поведении других; Выигрыш, к которому приводит каждая совокупность стратегии игроков.

Функция выигрыша – целевая функция. Цель – определить оптимальные стратегии каждого игрока (кроме случаев с природой). Оптимальные стратегии должны быть устойчивыми.

7.Классификация игр.

1.по числу игроков (от 2 до бесконечности). Парные игры – 2 игрока

2.по количеству стратегий (конечное число стратегий – конечная игра, и наоборот бесконечная). Мы изучаем конечные парные игры.

3.по свойству функции выигрыша: с нулевой суммой (антагонистические игры) – мы изучаем; с ненулевой суммой, с постоянной разностью.

4.в зависимости от возможности переговоров: кооперативные (по договору) – мы изучаем, некооперативные (без договора).

8.Формальное представление игр

А	А1	А2	Аn	Игрок А
В	В1	В2	Вm	Игрок В

A_iB_j=p_ij выигрыш игрока A и выигрыш игрока B q_ij

Игра с нулевой суммой A_ij+B_ij=0; p_ij выигрыш игрока A и проигрыш игрока B

Игра поиск А₁ – ищет в 1 месте, А₂ – ищет во 2 месте. В₁ – прячется в 1 месте, В₂ – прячется во 2 месте, проигрыш=отрицательный выигрыш.

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

Платежная матрица:

	В1	В2
А1	1	-1
А2	-1	1

Игра с ненулевой суммой (делема заключенного) А, В – заключенные.

А₁ – свидетельствует против В, А₂ – не свидетельствует, В₁ – свидетельствует против А, В₂ – не свидетельствует.

	В1	В2
А1	(5;5)	(0;10)
А2	(10;0)	(1;1)

9.Принцип минимакса для антагонистических игр

	В1	В2	Вn	min
А1	P11	P12	P1n	α1	max
А2	P21	P22	P2n	α2
Аm	Pm1	Pm2	pmn	αm
max	β1	β2	βn
	min

α – гарантированный выигрыш, β – гарантированный проигрыш.

α=maxα_i=max(min p_ij) – максмин – нижняя цена,

β=minβ_j=min (max p_ij) – минмакс – верхняя цена.

Игрок А какую стратегию я не выбрал, игрок В выберет стратегию, при которой мой выигрыш минимален. Игрок В какую стратегию я не выбрал, игрок А выберет стратегию, при которой его выигрыш максимален.