선형 프로그래밍을 사용하여 매트릭스 게임을 해결합니다. 매트릭스 게임: 문제 해결의 예

각 플레이어가 자신이 마음대로 사용할 수 있는 유한한 전략 세트를 갖는 제로섬 게임입니다. 매트릭스 게임의 규칙은 지불 매트릭스에 의해 결정되며, 그 요소는 첫 번째 플레이어의 승리이자 두 번째 플레이어의 손실이기도 합니다.

매트릭스 게임 적대적인 게임이다. 첫 번째 플레이어는 게임 가격과 동일한 최대 보장 상금(두 번째 플레이어의 행동과 관계 없음)을 받습니다. 마찬가지로 두 번째 플레이어도 최소 보장 손실을 달성합니다.

아래에 전략 현재 상황에 따라 플레이어의 각 개인 움직임에 대한 행동 선택을 결정하는 일련의 규칙(원칙)으로 이해됩니다.

이제 모든 것에 대해 순서대로 자세히 설명합니다.

결제 매트릭스, 순수 전략, 게임 가격

안에 매트릭스 게임 그 규칙은 정해져 있다 결제 매트릭스 .

첫 번째 플레이어와 두 번째 플레이어라는 두 명의 참가자가 있는 게임을 생각해 보세요. 첫 번째 플레이어가 마음껏 사용할 수 있도록 하세요. 중순수한 전략, 그리고 두 번째 플레이어의 처분에 따라 - N순수한 전략. 승부를 고려하고 있는 이상 이번 경기에서는 승패가 있는 것이 당연하다.

안에 결제 매트릭스 요소는 플레이어의 승패를 나타내는 숫자입니다. 승패는 포인트, 금액 또는 기타 단위로 표현될 수 있습니다.

결제 매트릭스를 만들어 보겠습니다.

첫 번째 플레이어가 선택한 경우 나-순수전략, 그리고 두 번째 플레이어- 제이순수 전략의 경우, 첫 번째 플레이어의 보수는 다음과 같습니다. ㅏij유닛, 두 번째 플레이어의 손실도 ㅏij단위.

왜냐하면 ㅏij + (- ㅏ ij) = 0, 그렇다면 설명된 게임은 제로섬 매트릭스 게임입니다.

매트릭스 게임의 가장 간단한 예는 동전 던지기입니다. 게임의 규칙은 다음과 같습니다. 첫 번째와 두 번째 플레이어가 동전을 던지며 결과는 앞면 또는 뒷면입니다. "앞면"과 "앞면" 또는 "꼬리" 또는 "꼬리"가 동시에 던져지면 첫 번째 플레이어가 유닛 1개를 획득하고, 그렇지 않은 경우에는 유닛 1개를 잃습니다. (두 번째 플레이어가 유닛 1개를 획득합니다.) . 두 번째 플레이어도 동일한 두 가지 전략을 사용할 수 있습니다. 해당 지불 매트릭스는 다음과 같습니다:

게임 이론의 임무는 첫 번째 플레이어의 전략을 결정하여 최대 평균 승리를 보장하고 두 번째 플레이어의 전략을 선택하여 최대 평균 손실을 보장하는 것입니다.

매트릭스 게임에서 전략을 어떻게 선택합니까?

지불 매트릭스를 다시 살펴보겠습니다.

먼저, 첫 번째 플레이어가 다음을 사용하면 승리할 금액을 결정해 보겠습니다. 나순전한 전략. 첫 번째 플레이어가 사용하는 경우 나순수 전략이라면, 두 번째 플레이어가 첫 번째 플레이어의 보상이 최소화되는 순수한 전략을 사용할 것이라고 가정하는 것이 논리적입니다. 차례로, 첫 번째 플레이어는 그에게 최대의 승리를 제공할 수 있는 순수한 전략을 사용할 것입니다. 이러한 조건에 따라 첫 번째 플레이어의 승리를 다음과 같이 표시합니다. V1 , 라고 불리는 최대 상금 또는 게임의 최저 가격 .

~에 이 값에 대해 첫 번째 플레이어는 다음과 같이 진행해야 합니다. 각 줄에서 최소 요소의 값을 기록하고 그 중에서 최대 요소를 선택합니다. 따라서 첫 번째 플레이어의 상금은 최소의 최대 금액이 됩니다. 따라서 이름은 최대 승리입니다. 이 요소의 줄 번호는 다음과 같습니다. 순수 전략, 첫 번째 플레이어가 선택합니다.

이제 두 번째 플레이어가 다음을 사용하면 손실 금액을 결정해 보겠습니다. 제이번째 전략. 이 경우 첫 번째 플레이어는 두 번째 플레이어의 손실이 최대가 되는 자신만의 순수 전략을 사용합니다. 두 번째 플레이어는 자신의 손실이 최소화되는 순수한 전략을 선택해야 합니다. 두 번째 플레이어의 손실을 다음과 같이 표시합니다. V2 , 라고 불리는 최소최대 손실 또는 게임의 최고 가격 .

~에 게임 가격에 대한 문제 해결 및 전략 결정 두 번째 플레이어에 대해 이러한 값을 결정하려면 다음과 같이 진행하십시오. 각 열에서 최대 요소의 값을 기록하고 그 중에서 최소값을 선택합니다. 따라서 두 번째 플레이어의 손실은 최대의 최소가 됩니다. 따라서 이름은 Minimax Win입니다. 이 요소의 열 번호는 두 번째 플레이어가 선택한 순수 전략의 번호가 됩니다. 두 번째 플레이어가 "minimax"를 사용하면 첫 번째 플레이어의 전략 선택에 관계없이 그는 다음보다 더 많이 잃지 않습니다. V2 단위.

예시 1.

.

행의 가장 작은 요소 중 가장 큰 요소는 2입니다. 이는 게임의 낮은 가격이며 첫 번째 행이 이에 해당하므로 첫 번째 플레이어의 최대 전략이 첫 번째입니다. 열의 가장 큰 요소 중 가장 작은 요소는 5입니다. 이는 게임의 상위 가격이고 두 번째 열은 이에 해당하므로 두 번째 플레이어의 미니맥스 전략은 두 번째입니다.

이제 게임의 최저 가격과 최고 가격, 최대값과 최소값 전략을 배웠으므로 이러한 개념을 공식적으로 정의하는 방법을 배울 차례입니다.

따라서 첫 번째 플레이어의 보장된 승리는 다음과 같습니다.

첫 번째 플레이어는 최소 상금 중 최대를 얻을 수 있는 순수한 전략을 선택해야 합니다. 이 이득(최대값)은 다음과 같이 표시됩니다.

.

첫 번째 플레이어는 두 번째 플레이어의 손실이 최대가 되도록 순수 전략을 사용합니다. 이 손실은 다음과 같이 표시됩니다.

두 번째 플레이어는 손실이 최소화되도록 순수한 전략을 선택해야 합니다. 이 손실(최소최대)은 다음과 같이 표시됩니다.

.

같은 시리즈의 또 다른 예입니다.

예시 2.보수 행렬이 있는 행렬 게임이 주어지면

.

첫 번째 플레이어의 최대화 전략, 두 번째 플레이어의 최소최대화 전략, 게임의 낮은 가격과 높은 가격을 결정합니다.

해결책. 지불 매트릭스 오른쪽에는 행의 가장 작은 요소를 기록하고 최대값을 기록하며, 매트릭스 아래에는 열의 가장 큰 요소인 최소값을 선택합니다.

라인의 가장 작은 요소 중 가장 큰 것은 3입니다. 이것은 게임의 낮은 가격이고 두 번째 라인은 이에 해당하므로 첫 번째 플레이어의 최대 전략은 두 번째입니다. 열의 가장 큰 요소 중 가장 작은 요소는 5입니다. 이는 게임의 상위 가격이고 첫 번째 열은 이에 해당하므로 두 번째 플레이어의 미니맥스 전략이 첫 번째입니다.

매트릭스 게임의 안장점

게임의 상한 가격과 하한 가격이 동일하면 매트릭스 게임에 안장점이 있는 것으로 간주됩니다. 반대의 경우도 마찬가지입니다. 매트릭스 게임에 안장점이 있는 경우 매트릭스 게임의 상한 가격과 하한 가격은 동일합니다. 해당 요소는 행에서 가장 작고 열에서 가장 크며 게임 가격과 같습니다.

따라서 , then 은 첫 번째 플레이어의 최적 순수 전략이고, 두 번째 플레이어의 최적 순수 전략입니다. 즉, 동일한 전략 쌍을 사용하여 동일한 낮은 게임 가격과 높은 게임 가격을 달성합니다.

이 경우 매트릭스 게임은 순수 전략에 대한 해결책을 가지고 있습니다 .

예시 3.보수 행렬이 있는 행렬 게임이 주어지면

.

해결책. 지불 매트릭스 오른쪽에는 행의 가장 작은 요소를 기록하고 최대값을 기록하며, 매트릭스 아래에는 열의 가장 큰 요소인 최소값을 선택합니다.

게임의 낮은 가격은 게임의 높은 가격과 일치합니다. 따라서 게임의 가격은 5입니다. 즉 . 게임의 가격은 게임의 가치와 동일합니다. 안장 포인트. 첫 번째 플레이어의 맥신 전략은 두 번째 순수 전략이고, 두 번째 플레이어의 미니맥스 전략은 세 번째 순수 전략입니다. 이 매트릭스 게임은 순수한 전략으로 솔루션을 제공합니다.

매트릭스 게임 문제를 직접 해결하고 해결책을 살펴보세요.

예시 4.보수 행렬이 있는 행렬 게임이 주어지면

.

게임의 최저 가격과 최고 가격을 찾아보세요. 이 매트릭스 게임에 안장 지점이 있나요?

최적의 혼합 전략을 갖춘 매트릭스 게임

대부분의 경우 매트릭스 게임에는 안장점이 없으므로 해당 매트릭스 게임에는 순수 전략에 대한 솔루션이 없습니다.

그러나 최적의 혼합 전략에는 솔루션이 있습니다. 이를 찾으려면 경험을 바탕으로 어떤 전략이 더 바람직한지 추측할 수 있도록 게임이 충분한 횟수만큼 반복된다고 가정해야 합니다. 따라서 결정은 확률과 평균(수학적 기대)의 개념과 관련이 있습니다. 최종 솔루션에는 안장점과 유사한 것도 있습니다(즉, 하단과 하단의 평등). 최고 가격게임) 및 해당 전략과 유사합니다.

따라서 첫 번째 플레이어가 최대 평균 승리를 얻고 두 번째 플레이어가 최소 평균 손실을 얻으려면 일정 확률로 순수 전략을 사용해야 합니다.

첫 번째 플레이어가 확률이 있는 순수 전략을 사용하는 경우 , 그 다음 벡터 혼합된 첫 번째 플레이어 전략이라고 합니다. 즉 순수 전략의 '혼합'이다. 이 경우 이러한 확률의 합은 1과 같습니다.

.

두 번째 플레이어가 확률이 있는 순수 전략을 사용하는 경우 , 그 다음 벡터 두 번째 플레이어 혼합 전략이라고 합니다. 이 경우 이러한 확률의 합은 1과 같습니다.

.

첫 번째 플레이어가 혼합 전략을 사용하는 경우 피, 그리고 두 번째 플레이어 - 혼합 전략 큐그렇다면 말이 되는군요 기대값 첫 번째 플레이어의 승리(두 번째 플레이어의 패배). 이를 찾으려면 첫 번째 플레이어의 혼합 전략(1행 행렬이 됨)의 벡터, 보수 행렬 및 벡터를 곱해야 합니다. 혼합 전략두 번째 플레이어(단일 열 매트릭스가 됨):

.

실시예 5.보수 행렬이 있는 행렬 게임이 주어지면

.

첫 번째 플레이어의 혼합 전략이 이고 두 번째 플레이어의 혼합 전략이 이면 첫 번째 플레이어의 승리(두 번째 플레이어의 패배)에 대한 수학적 기대치를 결정합니다.

해결책. 첫 번째 플레이어의 승리(두 번째 플레이어의 패배)에 대한 수학적 기대 공식에 따르면, 이는 첫 번째 플레이어의 혼합 전략 벡터, 지불 매트릭스 및 두 번째 플레이어의 혼합 전략 벡터의 곱과 같습니다.

첫 번째 플레이어는 게임이 충분한 횟수만큼 반복되면 최대 평균 보상을 제공하는 혼합 전략이라고 합니다.

최적의 혼합 전략 두 번째 플레이어는 게임이 충분한 횟수만큼 반복되면 최소 평균 손실을 제공하는 혼합 전략이라고 합니다.

순수 전략의 경우 maximin 및 minimax 표기법과 유사하게 최적의 혼합 전략은 다음과 같이 표시됩니다. 수학적 기대즉, 첫 번째 플레이어의 승리와 두 번째 플레이어의 손실의 평균입니다.

,

.

이 경우 해당 기능에 대해 이자형 안장점이 있어요 , 이는 평등을 의미합니다.

최적의 혼합전략과 안장점을 찾기 위해서는, 즉 혼합 전략으로 매트릭스 게임을 해결하다 , 우리는 매트릭스 게임을 문제로 줄여야 합니다 선형 프로그래밍, 즉 최적화 문제에 대해 대응하는 선형 계획법 문제를 해결합니다.

매트릭스 게임을 선형 계획법 문제로 축소

혼합 전략의 매트릭스 게임을 해결하려면 직선을 구성해야 합니다. 선형 프로그래밍 문제그리고 이중 작업. 쌍대 문제에서는 제약 조건의 변수 계수, 자유 항 및 목적 함수의 변수 계수를 저장하는 확장 행렬이 전치됩니다. 이 경우 원래 문제의 목표 함수의 최소값은 이중 문제의 최대값과 일치합니다.

직접 선형 계획법 문제의 목표 함수:

.

직접 선형 계획법 문제의 제약 조건 시스템:

쌍대 문제의 목표 함수는 다음과 같습니다.

.

이중 문제의 제한 시스템:

직접 선형 계획법 문제에 대한 최적 계획은 다음과 같이 표시됩니다.

,

이중 문제에 대한 최적 계획은 다음과 같이 표시됩니다.

해당 최적 계획의 선형 형태를 다음과 같이 나타냅니다.

최적 계획의 해당 좌표의 합으로 찾아야 합니다.

이전 단락의 정의와 최적 계획의 좌표에 따라 첫 번째와 두 번째 플레이어의 다음 혼합 전략이 유효합니다.

.

이론 수학자들은 다음을 증명했습니다. 게임 가격 최적 계획의 선형 형태를 통해 다음과 같이 표현됩니다.

,

즉, 최적계획의 좌표합의 역수이다.

우리 실무자들은 혼합 전략의 매트릭스 게임을 해결하는 데에만 이 공식을 사용할 수 있습니다. 좋다 최적의 혼합 전략을 찾기 위한 공식 첫 번째와 두 번째 플레이어는 각각 다음과 같습니다.

두 번째 요소는 벡터입니다. 최적의 혼합 전략은 이전 단락에서 이미 정의한 대로 벡터이기도 합니다. 따라서 숫자(게임 가격)에 벡터(최적 계획의 좌표 포함)를 곱하면 벡터도 얻을 수 있습니다.

실시예 6.보수 행렬이 있는 행렬 게임이 주어지면

.

게임 가격 알아보기 V최적의 혼합 전략과 .

해결책. 우리는 이 매트릭스 게임에 해당하는 선형 프로그래밍 문제를 만듭니다.

우리는 직접적인 문제에 대한 해결책을 얻습니다.

.

발견된 좌표의 합으로 최적 계획의 선형 형태를 찾습니다.

결제 매트릭스에 새들 포인트가 있는지 확인합니다. 그렇다면 우리는 순수한 전략으로 게임에 대한 해결책을 작성하고, 그렇지 않다면 계속해서 매트릭스를 분석합니다.

지배적인 행과 지배적인 열이 있는 경우 이를 제거합니다. 대신 플레이어의 최적 전략에서 해당 구성 요소는 0과 같습니다.

H. 우리는 다음 중 하나를 사용하여 매트릭스 게임을 해결합니다. 알려진 방법: 선형 프로그래밍 방법, 대략적인 방법 또는 그래픽 방식(플레이어 중 최소한 한 명이 두 가지 순수 전략만 가지고 있는 경우).

모든 매트릭스 게임은 한 쌍의 대칭 이중 선형 계획법 문제로 축소될 수 있습니다. 이는 단순 방법을 사용하여 최적의 플레이어 전략과 게임 가격을 찾을 수 있음을 의미합니다.

맞춤형 솔루션의 예.

예. 보수 매트릭스에 의해 주어진 게임의 해법 찾기

먼저 행렬에 안장점이 있는지 확인해보자. 첫 번째 행의 가장 작은 요소 -3은 다음이 아닙니다. 세 번째 열에서 가장 크다. 두 번째 행의 가장 작은 요소 -1은 첫 번째 열의 가장 큰 요소가 아닙니다. 마지막으로 세 번째 행의 가장 작은 요소 2는 세 번째 열에서도 가장 큰 요소입니다. 결과적으로 행렬에는 요소가 위치하는 안장점(3, 3)이 있습니다. ㅏ zz = 2. 이는 게임이 다음과 같은 순수 전략의 솔루션을 가지고 있음을 의미합니다.

- 첫 번째 플레이어의 최적 전략

- 두 번째 플레이어의 최적 전략

V= 2 - 게임 가격.

예. 보수 매트릭스에 의해 주어진 게임의 해법 찾기

.

매트릭스에는 안장 지점이 없으므로 게임에는 혼합 전략의 솔루션이 있습니다.

행렬에 주요 행과 주요 열이 있는지 확인해 보겠습니다. 첫 번째 행의 모든 ​​요소는 세 번째 행의 해당 요소보다 크지 않으므로 첫 번째 행이 지배적이며 삭제될 수 있습니다. 두 번째 열과 다섯 번째 열을 지배하는 세 번째 열을 제거할 수도 있습니다. 처음 세 열을 지배하는 열입니다. 결과적으로 우리는 행렬을 얻습니다.

행렬의 모든 요소를 ​​​​추가하여 ㅏ",예를 들어, 숫자 c = 3이면 행렬을 얻습니다.

.

모든 요소는 음수가 아니며 두 번째 행의 요소는 엄격하게 양수입니다.

원래 문제가 표준 최대화 문제이고 이 문제의 계수 행렬이 보상 행렬과 일치하도록 한 쌍의 대칭 쌍대 문제를 만들어 보겠습니다. ㅏ",· 그리고 목적 함수의 미지수에 대한 계수와 부등식의 자유 항은 1과 같습니다.

심플렉스 방법을 사용하여 문제 1을 해결해 보겠습니다. 일반과제 형태로 제공됩니다. 추가 미지수를 사용하여 주요 항목으로 줄이겠습니다. 엑스 4 ≥0, 엑스 5 ≥0. 결과적으로 다음과 같은 문제가 발생합니다.

엑스 제이 ≥ 0 (제이 = 1,…,5),

에프(엑스) = x 1 + x 2 + × 3 → 타.

문제는 표준적이며 단순법 알고리즘을 문제에 적용하여 다음 형식의 단순 테이블을 얻습니다.

기본 변수 열과 색인 행에서 우리는 한 쌍의 이중 문제에 대한 최적의 계획을 작성합니다. 즉:

에프(엑스*)= g(와이*)=

이중 문제의 해결로부터 우리는 게임의 가격과 매트릭스를 통해 게임에 참여하는 플레이어의 최적 전략을 얻습니다. ㅏ":

v" = = ;

=v" = = ;

= V" = =

매트릭스 게임 ㅏ"동일한 최적의 전략을 갖게 됩니다. 그리고 , 매트릭스 게임과 동일 ㅏ",그리고 게임 가격

V"= V"- c = - 3 = .

그리고 마지막으로 행렬 A를 사용한 원래 게임은 최적의 전략을 가지고 있습니다.

피*= 그리고 질문*=

그리고 게임 가격 V= V"= .

최적의 전략 아르 자형*그리고 큐* 우리는 최적의 전략을 통해 얻었습니다 그리고 , 삭제된 행과 열 대신 0을 추가합니다.

전략 최적성 기준을 사용하여 게임 솔루션의 정확성을 확인할 수 있습니다. 이를 위해서는 발견된 최적 전략의 구성요소를 부등식 M(P i , Q*) ≤ v≤ M(P*, Q j)로 대체해야 합니다. 아르 자형*그리고 큐*,순수 전략의 구성요소 아르 자형나 (i = 1, 2, 3) 및 큐 제이 (j = 1, 2, 3, 4, 5)

그리고 게임 가격 v = .

게임 이론 문제는 다음과 같은 경우에만 이중 LP 문제 쌍으로 축소되어야 합니다. 모든 요소 결제 매트릭스의 최소 한 행 엄격하게 긍정적 . 이 경우 두 문제 모두 최적의 계획을 갖게 되며, 이를 통해 플레이어의 최적 전략을 얻을 수 있습니다. 그렇지 않으면 원래 문제에서 목적 함수는 무한한 것으로 판명될 수 있으며 쌍대 문제에서는 단일 계획이 존재하지 않게 됩니다. 따라서 다음 예에서는 매트릭스가 있는 게임에서 이중 문제 쌍을 생성하면

,

그러면 문제 1에서는 목적 함수가 계획 집합에 대해 위에서 제한되지 않고 문제 2에서는 계획이 전혀 없습니다. 그러나 위에서 본 것처럼 행렬을 사용한 게임은 ㅏ"해결책이 있습니다.

첫 번째 플레이어(플레이어)의 최적 혼합 전략 ㅏ) 형식을 갖습니다.

,

두 번째 플레이어(플레이어)의 최적 혼합 전략 비) 형식은 다음과 같습니다.

.

이 매트릭스 게임은 명백히 수익성이 없는 전략을 제거하여 단순화되었으며 최종 솔루션은 다음과 같은 형식을 갖습니다.

게임을 그래픽으로 해결합니다.

그래픽 방법은 적어도 한 명의 플레이어가 두 가지 전략만 가지고 있는 게임에 적용할 수 있습니다.

예시 1.

이 게임에는 안장 지점이 없습니다. 최적의 해법은 혼합전략 분야에서 모색되어야 한다. 두 번째 플레이어의 전략에 해당하는 평면의 세그먼트를 구성해 보겠습니다.

플레이어 A의 상금 하한선은 파선입니다 안에 3 HF 4 ,. 전략 안에 3 , 그리고 안에 4 는 플레이어 B의 활성 전략입니다. 교차점 에게플레이어의 최적 전략과 게임 가격을 결정합니다. 두 번째 플레이어가 전략을 사용하는 것은 수익성이 없습니다. 안에 1 그리고 안에 2 , ~에 1 =y 2 = 0. 게임의 해법은 (2x2) 행렬을 사용하는 게임의 해법으로 축소됩니다.

엑스 1 = 2/5, 엑스 2 = 3/5; 와이 3 = 3/5, ~에 4 = 2/5; V = 11/5.

답변.

엑스 (2/5, 3/5) 및 와이 (0, 0.3/5, 2/5), 게임 가격은 V = 11/5.

확률이 2/5인 첫 번째 플레이어가 첫 번째 전략을 사용하고 확률이 3/5인 경우 두 번째 전략을 사용하면 충분합니다. 대량이 매트릭스를 사용하는 게임에서 그의 평균 상금은 최소 11/5입니다.

두 번째 플레이어가 3/5의 확률로 세 번째 전략을 사용하고 네 번째 플레이어가 2/5의 확률로 첫 번째 및 두 번째 전략을 사용하지 않으면 주어진 매트릭스를 사용하여 충분히 많은 수의 게임에서 손실을 입습니다. 평균은 11/5을 넘지 않습니다.

예시 2. 매트릭스가 제공하는 게임의 해결책 찾기

이 게임에는 안장 지점이 없습니다. 최적의 해법은 혼합전략 분야에서 모색되어야 한다. 첫 번째 플레이어의 전략에 해당하는 평면의 세그먼트를 구성해 보겠습니다.

플레이어 B의 손실 상한선은 파선입니다 ㅏ 1 캘리포니아 4 . 전략 ㅏ 1 그리고 ㅏ 2 플레이어 A의 활성 전략입니다. 교차점 에게플레이어의 최적 전략과 게임 가격을 결정합니다. 첫 번째 플레이어가 전략을 적용하는 것은 수익성이 없습니다. ㅏ 3 그리고 ㅏ 4 , 따라서 사용 확률은 0입니다. 엑스 2 = x 3 = 0. 게임의 해는 행렬(2x2)을 사용하는 게임의 해로 축소됩니다.

공식 (1)~(3)을 사용하여 최적의 전략과 게임 가격을 찾습니다.

엑스 1 = 7/8, 엑스 4 = 1/8; ~에 1 = 3/8, ~에 2 = 5/8; V = 27/8.

답변.최적의 혼합 플레이어 전략

엑스 (7/8, 0, 0, 1/8) 및 와이 (3/8, 5/8), 게임 가격은 V = 27/8.

이 답변은 다음을 의미합니다.

7/8의 확률을 가진 첫 번째 플레이어가 첫 번째 전략을 사용하고 1/8의 확률로 네 번째 플레이어가 두 번째 및 세 번째 전략을 사용하지 않으면 주어진 매트릭스를 사용하여 충분히 많은 수의 게임에서 그의 승리를 얻습니다. 평균은 최소 27/8입니다.

두 번째 플레이어가 3/8 확률로 첫 번째 전략을 사용하고 두 번째 전략을 5/8 확률로 사용하는 경우 이 매트릭스를 사용하는 충분히 많은 수의 게임에서 그의 평균 손실은 27/8을 넘지 않습니다.

"적대적 게임"이라는 주제를 연구하는 데 컴퓨터 기술을 사용합니다.

매트릭스 게임을 그래픽적으로 풀려면 Microsoft Word와 Microsoft Excel을 사용하고, 선형 계획법을 사용하여 매트릭스 게임을 풀려면 Microsoft Excel의 "해 찾기" 옵션을 사용합니다. 또한, 알고리즘 개발, 데이터 시각화 및 분석, 수치계산을 위한 고급 기술 컴퓨팅 언어이자 대화형 환경인 MATLAB 프로그램을 계산에 사용할 수도 있습니다.

독립적인 작업을 위한 작업 옵션입니다.

결제 매트릭스를 통해 주어진 게임의 최적 전략과 가격을 찾아보세요. ㅏ.

보수 행렬을 사용하여 mxpifu를 생각해 보겠습니다. 일반성을 잃지 않고 행렬 A의 모든 요소가 양수라고 가정합니다(이는 게임의 주어진 행렬을 변환하는 아핀 규칙을 사용하여 항상 달성할 수 있지만 플레이어의 최적의 혼합 전략). 따라서 게임 v의 요구 가격은 다음과 같습니다. 정수. 플레이어 A의 이익 플레이어의 최적 혼합 전략 속성에 대한 정리에서 플레이어 B n의 순수 전략에 대해 최적 혼합 전략 P = 플레이어 A는 v보다 작지 않은 평균 보상을 보장한다는 결론이 나옵니다. 즉, 행렬 게임을 선형 계획법 문제로 축소하는 표기법을 고려하면 다음과 같이 작성할 수 있는 관계가 충족됩니다. 플레이어 A는 보장된 승리를 가능한 최대화하려고 노력하므로 이에 대한 해결책을 찾는 작업은 다음과 같습니다. 매트릭스 게임은 다음 작업으로 축소됩니다. 부등식을 만족하고 그 합이 최소가 되는 음이 아닌 수량을 찾습니다. 플레이어 B의 관심 우리는 마찬가지로 플레이어 m의 순수 전략 Ai에 대한 플레이어 B의 최적 혼합 전략이 다음을 보장한다고 결론을 내립니다. 그의 평균 손실은 v보다 크지 않습니다. 즉, 표기법을 고려하면 다음과 같이 쓸 수 있는 관계가 충족됩니다. 플레이어 B는 보장된 손실을 가능한 한 최소화하려고 노력하므로 매트릭스 게임에 대한 해결책을 찾는 작업은 다음과 같이 줄어듭니다. 다음 작업: 부등식을 만족하고 그 합이 최대가 되는 음수가 아닌 수량을 찾습니다. n 따라서 우리는 다음과 같은 중요한 결과를 얻습니다. 정리 3. 양의 보상 행렬(a,k)을 사용하여 행렬 게임을 푸는 것은 이중 선형 계획법 문제를 푸는 것과 동일합니다. 또한 0이 역수인 게임 비용은 전반적인 가치최적의 합과 p의 최적값은 등식을 통해 최적의 x°( 및 yj와 관련됩니다. 행렬 게임을 해결하는 알고리즘 1단계. 원래 행렬의 모든 요소에 동일한 양수 7이 추가됩니다. 새 행렬의 모든 요소가 순전히 양수가 되도록 게임을 진행합니다. 2단계. 이중 선형 계획법 문제 (A)와 (B)가 해결됩니다(예: 심플렉스 방법 또는 다른 방법을 사용하여). 세트 xJ, yk 3단계. 플레이어 A와 B 각각의 최적 혼합 전략 4단계. 게임 가격 계산 예 9. 행렬이 있는 2x2 게임을 고려 해당 선형 계획법 문제는 다음 형식을 갖습니다. 풀이 1단계 보수 행렬의 모든 요소는 양수입니다. 2단계. 그래픽 방법을 사용하여 두 선형 계획법 문제에 대한 해를 구성합니다. 결과적으로 우리는 다음을 얻습니다. 행렬 게임을 선형 계획법 문제로 환원 §4. 행렬로 환원 가능한 문제의 예 게임 B 순수한 형태적대적인 갈등은 거의 없습니다(군사 작전 및 스포츠 경기 제외). 그러나 당사자들이 유한한 행동 세트를 가지고 있다는 가정 하에 당사자들의 이익이 반대되는 갈등은 매트릭스 게임으로 모델링될 수 있습니다. 몇 가지 구체적인 상황을 고려해 봅시다. 예 10. "파종 계획." 농업 기업은 A\와 두 가지 작물을 재배할 기회가 있습니다. 다른 이유로 인해 이러한 작물을 심는 방법을 결정해야 합니다. 평등한 조건수확량은 날씨에 따라 다르며 파종 계획은 가장 큰 수입을 제공해야 합니다(재배된 작물 판매로 인한 이익은 수령한 양에 따라 결정됩니다). 위험한 농업 지역(러시아 대부분)에서는 가장 불리한 기상 조건을 고려하여 식재 계획을 수행해야 합니다. 따라서 당사자 중 하나는 가장 큰 수입을 얻는 데 관심이 있는 농업 기업(플레이어 A)이고, 다른 당사자는 농업 기업에 최대로 해를 끼칠 수 있는 자연입니다(그에 따라 다름). 날씨 ) 이를 통해 정반대의 목표를 추구합니다(플레이어 B). 자연을 적으로 착각하는 것은 가장 불리한 조건을 고려하여 작물을 계획하는 것과 같습니다. 기상 조건이 좋으면 선택한 계획이 소득을 늘릴 수 있는 기회를 제공할 것입니다. 플레이어 A가 두 가지 전략(A\ 및 L?)을 가지고 있고 플레이어 B가 세 가지 전략을 가지고 있는 적대적 갈등이 있습니다. //| (건조한 여름), B2(보통 여름) 및 B$(비오는 여름). 플레이어 A의 상금으로 판매 수익을 취하고 기상 조건에 따른 농업 기업의 수익 계산(10억 루블 단위)이 다음 매트릭스(2 3 b)에 요약되어 있다고 가정합니다. 이 행렬에는 새들 포인트가 없음을 알 수 있습니다. 따라서 플레이어 A의 최적 전략이 혼합됩니다. 그래픽 방법을 사용하여 MM을 얻습니다. 참고: 여기서는 최적의 혼합 전략이 있을 때 비교적 드문 상황에 직면합니다. 플레이어 중 하나는 소위 "물리적" 구현을 허용합니다. 농업 기업은 결과 솔루션을 다음과 같이 사용할 수 있습니다. | 모든 영역에서 작물 A\를 재배하고, 모든 영역에서 I에서 작물 A2를 재배하여 수익을 창출할 수 있습니다. 최소 10억 루블의 금액 예 11. "노조와 행정부 간의 계약 체결에 대한 협상" 행정부가 노동 조합 근로자 및 직원과 계약 체결에 대해 협상하고 있는 회사를 생각해 보겠습니다. 계약 당사자의 이익을 반영하는 지불 매트릭스의 형식은 다음과 같습니다. 지불은 시간당 센트로 표시되며 모든 첨가제와 함께 회사 직원의 평균 급여를 나타냅니다. 따라서 주어진 매트릭스는 노동조합의 이익(선수 A)과 회사 관리 비용(선수 B)을 설명합니다. 노조는 근로자와 근로자의 소득을 최대화하려고 노력하는 반면, 행정부는 손실을 최소화하기를 원한다는 것은 분명합니다. 지폐의 지급 매트릭스에 안장점이 있다는 것을 쉽게 알 수 있습니다. 또한, 추가 분석을 위해서는 플레이어 A의 전략 A\ 및 A4와 플레이어 B의 전략 Bi 및 B4만이 유의미합니다(이는 전략 우위 규칙을 사용하여 쉽게 확인할 수 있음). 해당 절단의 결과로 우리는 행렬을 얻습니다. 행렬의 요소는 관계에 의해 이전 행렬의 요소와 관련됩니다. 그래픽 방법을 사용하면 궁극적으로 다음과 같은 결과를 얻을 수 있습니다. 따라서 노동조합은 20%의 경우에 전략 A\를 선택하고 80%의 경우에 전략 A4를 선택해야 합니다. 행정부는 확률이 0.4인 전략 B3과 확률이 0.6인 전략 B4를 선택해야 한다. 이 경우 게임의 예상 가격은 53입니다. 참고. 협상 과정이 여러 번 반복되면 평균은 기대값인 53에 수렴해야 합니다. 협상이 한 번만 발생하면 각 플레이어가 자신의 순수 항목을 선택할 때 실제 결과를 얻을 수 있습니다. 전략. 따라서 선수 중 하나인 노조나 행정부가 불만을 가질 것이다. 예 12. "지역 갈등." 두 개의 작은 국가 A와 B 사이에 30일 동안 벌어진 전쟁을 생각해 보십시오. B 국가의 중요한 군사 시설인 작은 다리를 폭격하기 위해 A 국가는 사용 가능한 두 항공기를 모두 사용합니다. 파괴된 다리는 24시간 이내에 복원되며, 각 비행기는 이들 국가를 연결하는 두 개의 항공 노선 중 하나를 따라 하루에 한 번씩 비행합니다. B국에는 2개의 대공포, 이를 통해 A 국가의 비행기를 격추할 수 있습니다. 비행기가 격추되면 일부 제3국은 24시간 이내에 A 국가에 새 비행기를 공급할 것입니다. A 국가는 동일한 경로 또는 다른 경로로 비행기를 보낼 수 있습니다. B 국가는 한 경로에 두 개의 대공포를 배치하거나 각 경로에 하나의 대공포를 배치할 수 있습니다. 한 대의 비행기가 대공포 하나가 있는 경로를 따라 비행하면 이 비행기가 격추됩니다. 두 대의 대공포가 있는 경로를 따라 두 대의 비행기가 비행하면 두 대의 비행기가 모두 격추됩니다. 한 대의 대공포가 있는 경로를 따라 두 대의 비행기가 비행하는 경우 한 대의 비행기만 격추됩니다. 비행기가 목표물에 도달하면 다리가 파괴됩니다. 국가 A에는 두 가지 전략이 있습니다. 서로 다른 경로로 비행기 보내기 - L|, 한 경로로 비행기 보내기 - Ag- 국가 B에도 두 가지 전략이 있습니다. 서로 다른 경로에 대공포 배치 - B\, 한 경로에 대공포 배치 - 국가 A 기여 국가 B가 전략 A를 선택하면 국가 A는 목표에 도달할 비행기가 없기 때문에 이득이 0이 됩니다. A국가가 Ag전략을 선택한다면 B 국가가 전략 B를 선택하면 최소한 한 대의 비행기가 목표에 도달하고 다리를 파괴할 확률은 1이 됩니다. A 국가가 A 전략을 선택하고 B 국가가 Bj 전략을 선택하면 다시 한 대 이상의 비행기가 목표에 도달합니다. 비행기가 목표에 도달하고 다리를 파괴할 확률은 1이 됩니다. A 국가가 Ag 전략을 선택하고 B 국가가 전략 Bi를 선택하면 A 국가는 1/2 확률로 대공포가 진입할 경로를 선택합니다. 설치되어 있으므로 대상은 1/2의 확률로 파괴됩니다. 분석 결과를 표준 게임 형식으로 공식화하겠습니다. 매트릭스 게임을 선형 프로그래밍 문제로 축소 그래픽 방법플레이어의 최적의 혼합 전략과 게임 비용을 찾습니다. 즉, A 국가가 전쟁에 할당된 30일 중 10일 동안 다른 경로로 비행기를 보낸다면(따라서 20일 동안 한 경로로) 그러면 평균적으로 A 국가에서는 66.7%의 성공 사례가 있을 것입니다(교량은 작동하지 않을 것입니다). 대공포에 대한 제안된 선택을 활용하여 B 국가는 66.7%의 경우보다 더 자주 다리에 폭격을 가하는 것을 허용하지 않을 것입니다. § 5. 결론적으로 몇 마디 매트릭스 게임 모델 갈등 상황, 각 참여 측이 두 번째 측과 동시에 이동합니다. 이 경우 가장 큰 관심은 플레이어가 한 쌍의 동시 이동을 한 직후 게임이 종료되지 않고 여러 번 반복되는 경우입니다. 더욱이, 게임이 재개될 때마다 플레이어는 갈등이나 분쟁에 대한 새로운 정보를 받지 못하는 것으로 알려져 있습니다. 가능한 조치반대편. 즉, 매트릭스 게임이 여러 번 반복되면 각 측은 매번 동일한 전략 세트에서 특정 전략을 선택해야 하며 이는 각 플레이어에게 변경되지 않습니다. 하지만 이렇게 반복되는 상황에서는 예비와 중급의 게임 분석이 중요한 역할을 합니다. 현명하게 대처한 결과 예비 분석매트릭스 게임에서는 분석에 관심이 있는 당사자가 전체 게임 시리즈에 대한 행동 방향(전략 선택 규칙)을 결정할 수 있습니다. 물론 위에서 설명한 최대화 접근 방식이 유일한 수단은 아닙니다. 그러나 이 접근 방식의 근본적인 특징은 이 접근 방식에서 파생된 전략을 선택하는 규칙을 준수하는 플레이어가 보장된 상금의 적지 않은 규모를 미리 매우 정확하게 추정할 수 있다는 사실을 잊어서는 안 됩니다. 또한, maximin 접근 방식을 사용하면 게임에 대한 해결책을 찾는 문제를 줄여 상대적으로 간단한 선형 계획법 문제를 고려할 수 있으므로 특정 게임이 여러 번 반복될 때 특정 게임에서 전략을 가장 잘 선택하는 방법에 대한 효과적인 권장 사항을 얻을 수 있습니다. 게임이 여러 번 반복되면 일부 추가 정보- 상대방이 정확히 어떤 전략을 선택하고 전략 선택에 어떤 규칙이 적용되는지 - 플레이어는 계속해서 수신합니다. 이 정보와 게임의 예비 분석 결과를 바탕으로 그는 상대방을 상당히 정확하게 평가할 수 있으며, 타협 최대 접근 방식을 따르지 않는 경우 자신의 행동 방식을 적절하게 변경하여 승률을 높일 수 있습니다.

용법 선형 프로그래밍안장 포인트가 없고 두 플레이어 모두를 위한 많은 전략이 있는 2인 제로섬 게임에 가장 효과적입니다. 원칙적으로 모든 유한한 2인 제로섬 게임은 해당 제로섬 게임으로 변환될 수 있습니다. 선형 프로그래밍 문제반대로, 모든 선형 계획법 문제는 유한한 2인 제로섬 게임으로 해석될 수 있습니다. 실제로 안장점이 없는 2인 제로섬 게임의 보수 행렬을 가정해 보겠습니다. 우리가 이미 알고 있듯이, 이 경우 첫 번째 플레이어의 최적 혼합 전략은 다음 조건에 따라 결정됩니다.

어디 ν * - 게임의 예상 가격; 피 ij - 교차점에 위치한 지불 매트릭스의 요소 나번째 줄과 제이- 상태 열이며 첫 번째 플레이어가 전략을 사용하고 상대방이 전략을 사용하는 경우 첫 번째 플레이어의 승리와 동일합니다. - 첫 번째 플레이어가 전략을 선택할 확률 . 이 경우 값은

는 혼합 전략을 사용할 때 첫 번째 플레이어의 예상 보수를 나타냅니다.

그리고 불평등이 있어요

따라서 첫 번째 플레이어에 대한 최적의 혼합 전략을 결정하는 문제는 다음과 같은 형태로 제시될 수 있습니다.

게임의 예상 가격을 가정해보자. ν* 이 문제는 긍정적입니다. ν* > 0. 새로운 변수를 도입해 보겠습니다.

값이 최대이므로 ν 가치에 해당

그런 다음 첫 번째 플레이어의 선형 프로그래밍 문제에 도달합니다.

이 문제에는 첫 번째 플레이어가 순수 전략을 선택할 확률을 연결하는 등식 유형 제약 조건이 없다는 점에 유의하세요. 이러한 상황은 고려 중인 선형 프로그래밍 문제에 대한 최적의 솔루션 좌표, 첫 번째 플레이어의 최적 혼합 전략 좌표 및 게임의 예상 가격 사이에 기능적 관계가 존재하기 때문입니다.

따라서,

그때 그리고 그때만

발견한 최적의 솔루션 ( ) 첫 번째 플레이어에 대한 T 선형 프로그래밍 문제를 통해 게임의 예상 가격을 계산할 수 있습니다. ν * 최적의 혼합 전략 첫 번째 플레이어.

두 번째 플레이어의 경우 최적의 혼합 전략은 다음 조건에 따라 결정됩니다.

어디 - 두 번째 플레이어가 전략을 선택할 확률 . 새로운 변수에서

두 번째 플레이어의 선형 프로그래밍 문제에 도달했습니다.

존재 이중 작업첫 번째 플레이어의 선형 프로그래밍 문제와 관련하여.

예시적인 예를 고려하기 전에 다음 사항에 유의하십시오.

1. 만일 ν < 0, то ко всем элементам платежной матрицы (Пij) 이렇게 큰 양수를 추가할 수 있습니다. 에게 > , 지불 매트릭스의 모든 요소가 양수가 될 것입니다. 이 경우 게임 가격은 다음과 같이 증가합니다. 에게, 그러나 결정은 변경되지 않습니다.

2. 첫 번째와 두 번째 플레이어에 대한 선형 프로그래밍 문제의 이중성은 둘 중 하나의 해결이 자동으로 다른 해결로 이어진다는 사실로 이어집니다. 이를 고려하면 일반적으로 제한이 적은 문제가 해결됩니다. 그리고 이는 각 플레이어가 사용할 수 있는 순수 전략의 수에 따라 달라집니다.

예제 3.10.예제 3.2, 3.4에서 살펴본 세 손가락 게임으로 돌아가 보겠습니다. 그녀를 위하여

행렬의 모든 요소에 추가(P ij) 숫자 케이= 5, 우리는 행렬에 도달합니다 수정된 게임

안장 포인트가 없는 2인 제로섬 게임에 대한 고려를 마무리하면서, 혼합 전략을 사용할 때 각 게임 전에 각 플레이어는 특정 메커니즘(동전 던지기, 주사위또는 난수 센서 사용) 각 순수 전략이 주어진 확률로 선택되도록 보장합니다. 이미 언급했듯이 혼합 전략은 수학적 모델입니다. 유연한 전술, 사용 시 상대방은 게임의 각 후속 게임에서 어떤 상황에 직면하게 될지 미리 알 수 없습니다. 동시에, 플레이되는 게임 수의 무한한 증가와 함께 예상되는 게임의 이론적 결과는 실제 값에 가까워지는 경향이 있습니다.

만약에각 플레이어는 두 가지 이상의 가능한 전략을 가지고 있으며, 그러면 게임에 대한 해결책은 선형 프로그래밍 문제를 해결하는 것으로 축소될 수 있습니다.

결제 매트릭스 mn을 사용하여 게임에 대한 솔루션을 찾아보겠습니다.

게임 매트릭스에 안장점이 포함되지 않도록 하세요. 그런 다음 혼합 전략 p = (p 1, p 2, ..., p m) 및 q = (q 1, q 2, ..., q m)에서 게임에 대한 솔루션을 찾을 것입니다. 여기서 p 1 + p 2 + ... + p m = 1 및 q 1 + q 2 +… + q n = 1

전략은 최적입니다. 즉, 플레이어 B의 모든 전략에 대해 플레이어 A의 평균 보상은 게임 가격보다 크거나 같으므로 제한 시스템을 얻습니다.

게임 가격이 0보다 크다고 가정해 보겠습니다. 실제로 0이면 게임 매트릭스의 일부 요소가 양수가 아니라는 의미입니다. 그런 다음 M>0이라는 숫자를 찾아 게임 행렬의 모든 요소에 추가하고 양수 요소가 있는 새 행렬을 얻습니다. 이 추가는 가격을 만들 것입니다 새로운 게임는 +M과 동일하며 양수이지만 게임의 솔루션을 변경하지는 않습니다.

모든 불평등의 양변을 양수로 나누고 다음을 나타냅니다.

그러면 제한 시스템은 다음과 같은 형태를 취하게 됩니다.

플레이어 A는 평균 보수를 최대화하려고 합니다. 즉, 비율을 최소화하려고 합니다.

따라서 우리는 선형 프로그래밍 문제를 얻습니다.

이 문제에는 항상 최적의 솔루션이 있다는 점에 유의하세요. Simplex 방법이나 Excel을 사용하여 찾을 수 있습니다. 그 다음은 게임 가격입니다. 첫 번째 플레이어의 최적 혼합 전략은 다음과 같습니다.

유사한 추론은 플레이어 B에 대한 최적의 전략을 제공합니다. 플레이어 A의 어떤 전략에 대해서도 플레이어 B의 손실은 게임 비용을 초과해서는 안됩니다. 우리는 제한 시스템을 얻습니다.

나타내자

그런 다음 플레이어 B의 최적 혼합 전략을 찾으려면 다음 선형 프로그래밍 문제를 해결해야 합니다.

이는 이전에 컴파일된 작업에 대한 이중 작업입니다. 문제에는 항상 최적의 솔루션이 있으며, 이는 이전에 구성된 문제에 대한 솔루션을 알고 있는 심플렉스 방법이나 평형 정리를 사용하여 찾을 수 있습니다. 그런 다음 새 게임의 가격. 두 번째 플레이어의 최적 혼합 전략은 다음과 같습니다.

보수 매트릭스에 의해 주어진 게임의 해법을 찾으십시오:

가장 높은 것을 찾아보자. 더 낮은 가격계략.

결과적으로 게임에는 안장점이 없으며 솔루션은 혼합 전략에 있습니다.

플레이어 A의 매트릭스 게임을 선형 프로그래밍 문제로 줄이기 위해 다음을 변환합니다. 결제 매트릭스모든 요소가 0보다 크도록 매트릭스의 모든 요소에 숫자 4를 추가하여 변환된 지불 매트릭스를 얻습니다.

평균 보수 A는 다음과 같아야 합니다. 저렴한 가격플레이어 B의 모든 행동에 대한 게임입니다. 따라서 플레이어 B가 첫 번째 전략을 사용하면 플레이어 A의 평균 보상은 다음과 같습니다. 마찬가지로 전략 B 2 및 B 3에 대한 부등식을 작성하면 선형 제약 조건 시스템을 얻을 수 있습니다.

조건 p 1 + p 2 + p 3 = 1에서 방정식의 양변을 >0(변환된 행렬의 모든 요소가 0보다 크기 때문에 게임의 가격은 0보다 큽니다)으로 나누어 다음을 얻습니다. 목적 함수. 플레이어 A의 목표는 최대 평균 승리를 얻는 것입니다. 최대, 즉 우리가 ( 나=1, 2, 3), 그 다음 목적 함수입니다.

제한 시스템의 변수 x i로 이동하여 각 부등식을 >0으로 나누어 보겠습니다.

해결책을 찾는 중입니다.

1. 문제를 해결하기 위해 Excel에서 "Game Solution"이라는 이름의 통합 문서를 만들어 보겠습니다. 시트의 데이터를 준비합시다.

먼저 솔루션 결과가 배치될 셀을 정의합니다. 이를 B2, C2, D2 셀로 두고 머리글로 만들어 보겠습니다. 이 셀에는 데이터가 없으므로 Excel에서 계산해야 하며 색상으로 강조 표시됩니다. 다음으로, 제약 조건 시스템의 오른쪽 변과 미지수에 대한 계수를 입력합니다(5-7행). 대상 함수에 대한 라인 10을 만들어 보겠습니다. 찾은 최적해에 대한 목적 함수 값이 위치하게 될 셀이 강조 표시됩니다.

B2:D2 및 D10 셀의 경우 숫자 형식을 소수점 이하 4자리로 설정합니다. 이렇게 하려면 해당 셀을 선택하고 마우스 오른쪽 버튼을 사용하여 상황에 맞는 메뉴에서 명령을 선택합니다. 셀 형식...그리고 나타나는 창에서 셀 형식탭에 숫자필요한 형식을 설정합니다.

2. 다음으로 솔루션 검색 추가 기능을 사용해야 합니다. 데이터 탭의 분석 그룹에서 솔루션 찾기를 선택합니다. 솔루션 검색 대화 상자가 나타나면 다음과 같이 입력해야 합니다. 제한 사항을 추가하려면 추가 버튼을 사용하세요.

창문에서 해결책 찾기버튼을 누른 후 실행하다 창이 나타난다 솔루션 검색 결과, 발견된 값 저장을 선택하고 버튼을 누릅니다. 좋아요 .

솔루션 검색 결과:

갖다. 이므로, 우리는 그것이 변환된 행렬에 의해 지정된 게임에 대한 해임을 발견합니다. 원래 행렬의 경우 혼합 전략의 구성 요소는 변하지 않으며 게임 가격은 행렬의 모든 요소에 추가된 수만큼 적습니다. 4시까지.

최종 결과: .

마찬가지로, 플레이어 B에 대한 선형 프로그래밍 문제를 만들고 풀 수 있습니다. 플레이어 B의 평균 손실은 플레이어 A의 모든 행동에 대한 게임 비용보다 커서는 안 됩니다. 우리는 선형 제약 시스템을 얻습니다.

조건 q 1 + q 2 + q 3 = 1에서 방정식의 양쪽을 >0으로 나누어 목적 함수를 얻습니다. 플레이어 B의 목표는 최소 평균 손실을 얻는 것입니다. 분, 즉. (j=1, 2, 3)을 나타내면 목적 함수입니다.

제한 시스템의 변수 y j로 이동하여 각 부등식을 >0으로 나누어 보겠습니다.

따라서 찾기 위해서는 최적의 전략플레이어 A는 선형 프로그래밍 문제를 해결해야 합니다.

설정을 사용하여 MS Excel 스프레드시트 편집기를 사용하여 문제를 해결해 보겠습니다. 해결책을 찾는 중입니다.

1. 시트에 데이터를 준비합니다.

F5, F6, F7 셀에는 제약 조건 시스템의 왼쪽 부분의 종속성에 대한 수식을 입력하고 D10 셀에는 목적 함수의 종속성에 대한 공식을 입력합니다.

창문에서 솔루션 검색 옵션음수가 아닌 값 상자를 확인하십시오.

솔루션 검색 결과:

갖다. 이므로, 우리는 그것이 변환된 행렬에 의해 지정된 게임에 대한 해임을 발견합니다.

최종 결과: .