Сведение задачи теории И. к ЗЛП

Рассм-ся И. m*n.Матрица известна.Седл.точки нет.Треб-ся опред-ть смеш.стр-гии игроков S_a^*,S_b^*.Найдем стр-ю S_a^* сначала.Эта стр-гия д.обеспечивать ирг.А выиг-ш не <V,при любой стр-гии противника и выиг-ш,=V при испол-нии игроком В оптим.стр-гии S_b^*.цена И.нам пока неизвестна,но б. полагать,что она «+».Предположим,что игр.А применяет оптим.стр-ию S_a^*,а противник отвечает стр-гией В1,тогда матем.ожидание выиг-ша игр.А составит а₁₁р₁+а₂₁р₂+…+а_m1p_m>=V. Оптим.стр-гия S_a^* обладает свойством при любом поведении противника обесп-ть игр.А выиг-ш не меньше,чем цена игры(V).Аналог. условия запис-ся и для др.чистых стр-гиях игр.В.:

а₁₁р₁+а₂₁р₂+…+а_m1p_m>=V,

а₁₂р₁+а₂₂р₂+…+а_m2p_m>=V,

а_1nр₁+а_2nр₂+…+а_mnp_m>=V.

р1+р2+…+р_n=1-д.б. такими,чтобы V было максимально.F(P,V)=V→max; р_1,2,..,m>=0.Разделим обе части каждого ограничения на V:

а₁₁р₁/V+а₂₁р₂/V+…+а_m1p_m/V>=V/V,

а₁₂р₁/V+а₂₂р₂/V+…+а_m2p_m/V>=V/V,

а_1nр₁/V+а_2nр₂/V+…+а_mnp_m/V>=V/V.Введем новые переменные:х₁=р₁/v,х₂=р₂/v,…,x_m=p_m/v.

а₁₁х₁+а₂₁х₂+…+а_m1х_m>=1,

а₁₂х₁+а₂₂х₂+…+а_m2х_m>=1,

а_1nх₁+а_2nх₂+…+а_mnх_m>=1.

x1+x2+…+x_m=1/v.х(1,2,..,m)>=0. F(x)=x1+x2+…+x_m→min.Получим ЗЛП,для реш-я кот. испол-ся симплекс.метод.При реш-и найдем оптим.знач-я переменных х1,х2,..,хm.Можно рассчитать V,а затем вычислить вер-сти р1,р2,..,рm.Определим теперь S_b^*.Составим условия для игр.В. Математ. ожидание проигрыша:

а₁₁q₁/V+а₂₁q₂/V+…+а_m1q_m/V<=V/V,

а₁₂q₁/V+а₂₂q₂/V+…+а_m2q_m/V<=V/V,

а_1nq₁/V+а_2nq₂/V+…+а_mnq_m/V<=V/V.Введем новые переменные:y₁=q₁/v,y₂=q₂/v,…,y_m=q_m/v.

а₁₁y₁+а₂₁y₂+…+а_m1y_m<=1,

а₁₂y₁+а₂₂y₂+…+а_m2y_m<=1,

а_1ny₁+а_2ny₂+…+а_mny_m<=1.

y1+y2+…+y_m=1/v.y(1,2,..,m)>=0. F(y)=y1+y2+…+y_m→max.Мы получили ЗЛП(симплекс),опред-м оптим. знач-е переменных у1,у2,…,у_m.затем рассч-т V,а затем вычислить вер-сти q1,q2,..,qm.Также для опред-я оптим.смеш.стр-гий А и В м.использовать теорию двойственности.