Розв’язування ігор у загальному випадку

Як показав автор теорії ігор, відомий американський математик Дж. фон Нейман, кожна скінчена матрична гра може бути записана у формі задачі лінійного програмування і, навпаки, кожну задачу лінійного програмування можна розглядати як матричну гру. Побудуємо математичну модель задачі пошуку оптимальної стратегії гравця 1 у формі задачі лінійного програмування. Позначимо через T₁ очікуване максимінне значення для довільної стратегії x = (x₁, x₂, …, x_m). Тоді, згідно з означенням T₁ £ a_ijx_i, j = 1, n, і шукана математична модель приймає вигляд

F = T₁ ® max,

a_ijx_i ³ T₁, j = 1, n,

x_i = 1, x_i ³ 0, i = 1, m.

Отримана задача може бути спрощена шляхом заміни змінних. Припустимо, T₁ > 0. Тоді, поділивши усі обмеження на T₁, маємо

a_ij x_i/T₁ ³ 1, j = 1, n,

x_i/T₁ = 1/T₁, x_i/T₁ ³ 0, i = 1, m.

Оскільки максимізація T₁ при T₁ > 0 еквівалентна мінімізіції 1/T₁, після підстановки u_i = x_i/T₁ переходимо до еквівалентної задачі у такій формі

F = u_i ® min,

a_ij u_i ³ 1, j = 1, n,

u_i ³ 0, i = 1, m.

Остання модель отримана у припущенні T₁ > 0, але до розв’язання задачі значення T₁ не відомо. Тому треба скористатися деякою нижньою оцінкою T₁. Такою оцінкою є максимінне значення гри.

Дата добавления: 2014-01-13