선형 프로그래밍을 사용하여 게임을 해결합니다. 선형 계획법을 이용한 행렬 게임 해결 알고리즘

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

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

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

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

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

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

첫 번째 플레이어와 두 번째 플레이어라는 두 명의 참가자가 있는 게임을 생각해 보세요. 첫 번째 플레이어가 마음껏 사용할 수 있도록 하세요. 중 순수 전략, 두 번째 플레이어는 자신의 처분에 따라 - 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최적의 혼합 전략과 .

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

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

.

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

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

결제 매트릭스 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 셀에는 목적 함수의 종속성에 대한 수식을 입력합니다.

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

솔루션 검색 결과:

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

최종 결과: .

m X n 크기의 게임에는 일반적으로 기하학적 해석이 없습니다. 이 솔루션은 노동 집약적이지만 한 쌍의 이중 선형 프로그래밍 문제를 해결하는 것으로 축소될 수 있으므로 근본적인 어려움은 없습니다.

행렬 12월 m X n이 지불 행렬(13.1)에 의해 주어진다고 가정합니다.

모든 항을 v로 나누고, v> 0이라는 표기법을 도입하여 시스템(13.2)을 변환해 보겠습니다.

모든 항을 v로 나누고, v> 0이라는 표기법을 도입하여 시스템(13.6)을 변환해 보겠습니다.

문제 (13.8), (13.9)는 선형 프로그래밍 문제로 이를 해결하여 행렬 게임에 대한 최적의 솔루션을 얻습니다.

결과적인 선형 계획법 문제 (13.4), (13.5) 및 (13.8), (13.9)를 분석한 후, 우리는 이들이 상호 이중 선형 계획법 문제 한 쌍을 구성한다는 결론을 내릴 수 있습니다. 분명히 최적의 전략을 찾을 때 특정 작업상호 이중 문제 중 하나를 해결해야 하며 그 해결 방법은 덜 노동 집약적이며 두 번째 해결 방법은 이중성 정리를 사용하여 찾아야 합니다.

m X n 크기의 매트릭스 게임을 풀 때의 동작 순서

차원 줄이기 결제 매트릭스이전에 수익성이 없었던 전략을 제거하여 게임

게임의 상한 가격과 하한 가격을 결정하고 게임 매트릭스에서 안장 지점이 있는지 확인하십시오. 안장점이 있는 경우 해당 전략이 최적이 되며 게임 가격은 게임 가격의 상한 및 하한과 일치합니다.

안장점이 없는 경우 매트릭스 쌍 게임을 이중 문제로 축소하여 혼합 전략 중에서 해결책을 찾아야 합니다.

심플렉스 방법을 사용하여 쌍대 문제 쌍 중 하나를 해결합니다.

혼합 전략에서 매트릭스 게임의 솔루션을 추출합니다.

예제 13.1. 기업은 수요에 따라 세 가지 유형의 제품 A1, A2, A3을 생산하면서 이익을 얻을 수 있으며 이는 B1, B2, B3, B4 네 가지 상태 중 하나를 취할 수 있습니다. 세 번째 유형의 제품을 출시할 때 회사가 얻게 되는 이익

정의하다 최적의 비율제품 출시.

해결책. 게임의 보상 매트릭스의 차원을 줄이는 것은 이전에 수익성이 없었던 전략을 포함하지 않기 때문에 불가능합니다.

최대값(minimax)을 찾는 알고리즘을 사용하여 게임의 상한 가격과 하한 가격을 결정해 보겠습니다.

따라서 이 게임은 행렬쌍 게임을 이중문제로 축소하여 혼합전략으로 해결할 수 있다.

플레이어 A의 최적 전략 정의에 해당하는 선형 프로그래밍 문제는 다음과 같은 형식을 갖습니다.

플레이어 B의 최적 전략 정의에 해당하는 선형 프로그래밍 문제는 다음과 같은 형식을 갖습니다.

상호 쌍대 선형 계획법 문제 (13.10), (13.11) 및 (13.12), (13.13) 쌍을 분석한 결과 심플렉스 방법을 사용하여 문제 (13.12), 13.13)을 해결하는 것이 좋습니다. 인위적인 변수를 도입할 필요가 없습니다.

목적함수의 최적값을 찾는 단순법은 다음과 같습니다. 보편적인 방법 J. Danzing이 개발한 선형 프로그래밍 문제(LPP)에 대한 솔루션입니다. 이는 시스템의 단순 변환을 위한 알고리즘을 기반으로 합니다. 선형 방정식, 어떤 전환도 아닌 "최고의" 참조 계획으로의 전환을 보장하는 규칙으로 보완됩니다.

단순 방법의 본질은 먼저 우리가 얻는 것입니다. 유효한 솔루션, 이는 모든 제약 조건을 충족하지만 반드시 최적은 아닙니다(초기 참조 계획). 여러 번의 반복을 통해 초기 버전을 순차적으로 개선함으로써 최적성이 달성됩니다. 하나의 참조 계획에서 다른 참조 계획으로의 전환 방향은 최적성 기준(목적 함수)에 따라 선택됩니다.

심플렉스 방법은 ZLP의 속성을 기반으로 합니다.

1. 극단이 있다면 그것은 유일한 극단이다.

2. 모든 ZLP 계획의 집합은 볼록합니다.

3. 목적 함수는 해 다각형의 꼭지점에서 최적의 값에 도달합니다. 둘 이상의 꼭지점에서 최적의 값을 취하면 각 점에서 동일한 값에 도달합니다. 이는 이러한 점의 선형 결합입니다.

4. 솔루션 다각형의 각 꼭지점은 ZLP의 지원 계획에 해당합니다.

목적 함수를 최대화해야 하는 경우 최소 max Ly = min(-Ly)으로 이동할 수 있습니다.

추가 변수(y5, y6, y7)를 도입하여 문제 (13.12), (13.13)을 정식 형식으로 줄여 보겠습니다.

ZLP 제한 시스템의 불평등에 "≤" 기호가 있는 경우 "+" 기호와 함께 추가 변수가 도입됩니다. 부등식에 "≥" 기호가 있으면 "-" 기호와 함께 추가 변수가 도입됩니다.

정식 형식의 ZLP(13.12), (13.13)은 다음과 같은 형식을 갖습니다.

변수 x1, x2, x3, x4는 기본이고 x5, x6, x7은 추가입니다. 벡터 p5, p, p7은 단위 기저를 형성하며 기본 벡터라고 하며 p5가 첫 번째 기저 벡터입니다.

기본 변수가 있는 벡터로 구성된 단위 행렬을 생성하려면 다음과 같이 제한 시스템에 인공 변수를 도입해야 합니다.

추가 변수에 마이너스 기호가 있으면 플러스 기호가 있는 인공 변수가 이 방정식에 도입됩니다.

추가 변수에 더하기 기호가 있으면 이 방정식에 인위적인 변수를 도입할 필요가 없습니다.

인공 변수는 알 수 없는 양의 계수 M을 사용하여 목적 함수에 동시에 도입됩니다.

우리의 경우 인위적인 변수를 도입해서는 안 됩니다.

첫 번째 단순 테이블을 채워 보겠습니다. 초기 심플렉스 테이블은 다음과 같이 채워집니다. 첫 번째 줄에는 목적 함수의 계수가 포함됩니다. 기본 벡터는 "기본" 열에 기록됩니다. "C"열에는 기본 벡터에 대한 목적 함수의 계수가 기록됩니다. "p0", "p1", "P2", "p3", "p4", "p5", "p6", "p7" 열에는 해당 벡터의 구성 요소가 기록됩니다.

마지막 두 행에 있는 테이블의 셀을 채우려면 "C" 열의 요소에 계산 중인 열의 해당 요소를 곱하고 첫 번째 줄의 숫자를 빼야 합니다(" 열 제외). 예를 들어, "p2" 열의 셀을 채우려면 "C" 열의 요소에 "p2" 열의 해당 요소를 곱하고 숫자 - 1을 뺍니다. 0 * 3 + 0 * 4 + 0 * 5 - (- 1) = 1.

표 13.1. 첫 번째 단순 테이블

단순 테이블의 마지막 행을 인덱스라고 합니다. 여기에는 "p1" 열부터 시작하여 이 테이블에 해당하는 참조 계획의 최적성을 확인하는 데 도움이 되는 최적성 추정이 포함되어 있습니다. 참조 계획의 구성 요소 값은 "p0" 열에 있으며 기본이 아닌 변수에는 0 값이 할당됩니다.

참조 계획의 최적성은 최적성 기준을 사용하여 지표선으로 확인됩니다. 참조 계획의 최적 기준:

인덱스 라인에 최적성 추정치 중 하나 이상의 긍정적 추정치가 포함되어 있으면 참조 계획은 최적이 아닙니다.

인덱스 라인에서 비기본 변수에 대한 모든 최적성 추정치는 다음과 같습니다. 음수이면 참조 계획은 최적이고 고유합니다.

인덱스 라인에서 기본이 아닌 변수가 0 추정치에 해당하고 최적성 추정치 중에 양수 추정치가 있는 경우 참조 계획이 최적이지만 유일한 것은 아닙니다.

우리의 경우 첫 번째 심플렉스 테이블에 해당하는 참조 계획은 최적이 아닙니다.

다음 심플렉스 테이블로 이동하려면 열부터 시작하여 인덱스 행에서 가장 긍정적인 추정치를 선택하세요.

우리의 경우 일치하는 가장 큰 긍정적 추정치가 4개 있으므로 그 중에서 하나를 선택합니다. 예를 들어 이것은 "p3" 열의 숫자 1입니다.

가장 긍정적인 평가에 해당하는 열을 결정적이라고 합니다. 기저에 입력될 벡터를 보여줍니다.

우리의 경우에는 "p3" 벡터를 기저에 입력해야 합니다.

Qo에서 단순 최적성 관계를 찾아보겠습니다. 열 "p0"의 요소를 결정적인 열의 양수 요소로 나눕니다. 문자열, 성냥 가장 낮은 비율 Qo의 최적성은 결정적이라고 합니다. 이는 기저에서 파생되는 벡터를 보여줍니다.

일반요소는 결정열과 결정행의 교차점에 위치한 요소이다. 우리의 경우 이것은 숫자 6입니다.

다음 단순표로 이동하기 위한 규칙: 결정적인 행의 모든 ​​요소를 ​​일반 요소로 나눕니다.

결정적인 열을 0으로 완성하세요. 결정적인 행에 0이 있으면 변경 없이 해당 열을 다시 작성합니다.

따라서 두 번째 심플렉스 테이블은 다음과 같습니다.

표 13.2. 두 번째 심플렉스 테이블

인덱스 라인에 플러스 마크가 있기 때문에 최적이 아닙니다.

위에 설명된 규칙에 따라 세 번째 단순 테이블로 넘어가겠습니다.

표 13.3. 세 번째 심플렉스 테이블

인덱스 라인에 플러스 마크가 있기 때문에 최적이 아닙니다.

네 번째 단순 테이블로 넘어가겠습니다.

표 13.4. 네 번째 심플렉스 테이블

Simplex 표 13.4는 참조 계획에 해당합니다.

기저가 아닌 벡터에 대한 인덱스 라인에는 양의 추정치가 없기 때문에 최적이고 고유합니다.

따라서 회사(A업체)는 A제품 50%, A3 제품 50%를 생산해야 하며, A1 제품은 생산하지 않아야 합니다. 이를 통해 회사는 보증을 받을 수 있습니다. 평균값도착했다,

수요 상태에 기초하여 최적 수요는 상태 B1에서 75%이고 상태 B4에서 25%라는 결론을 내릴 수 있습니다.

어떻게 더 큰 크기게임의 결제 매트릭스 더 복잡한 분석. 따라서 매트릭스 게임을 해결하기 전에 먼저 플레이어가 지배하는 전략(있는 경우)을 제거하여 보상 매트릭스의 차원을 줄이는 것이 좋습니다. 그러나 지배적인 전략이 제외되더라도 각 플레이어는 여전히 두 가지 이상의 순수 전략을 가질 수 있습니다. (승, 피> 2) 그래픽분석방법을 적용할 수 없는 경우.

매트릭스 게임을 선형 계획법 문제로 줄이는 비교적 간단한 방법이 개발되었으며, 이는 다시 잘 풀릴 수 있습니다. 알려진 방법(예: 단순 방법 사용) 또는 다양한 컴퓨터 모델링 도구 사용(예: "솔루션 검색" 모듈 사용) MS 엑셀).

게임 이론의 창시자이자 선형 계획법 이론의 개발자 중 한 명인 J. von Neumann이 처음 보여주었듯이, 모든 유한한 2인 제로섬 게임은 선형 계획법 문제로 표현될 수 있습니다. . 이 방법은 이전 단락에서 설명했던 간단한 게임을 포함하여 모든 매트릭스 게임에 적용할 수 있습니다.

매트릭스 게임을 선형 계획법 문제로 축소하는 방법을 고려하려면 매트릭스 게임의 또 다른 속성, 즉 아핀 규칙.지불 매트릭스의 요소가 동등하게 관련된 매트릭스 게임 A와 B의 최적 전략

어디 엑스> 0이고 p는 임의의 실수입니다. 균형 상황(순수 전략이든 혼합 전략이든), 게임 가격은 다음 조건을 만족합니다. vB = XvA+ r.

이 규칙에는 실질적인 의미, 매트릭스 게임을 해결하기 위한 많은 알고리즘은 보수 매트릭스의 모든 요소가 양수라는 가정에 기반을 두고 있으며, 이는 결과적으로 게임에 대해 양의 가격을 보장합니다. 행렬에 양수가 아닌 요소가 있는 경우 행렬의 모든 요소에 최대값보다 큰 숫자를 추가할 수 있습니다. 절대값음수 행렬 요소.

우리는 결제 매트릭스가 있는 게임의 가격을 가정합니다. TXP양수(및 > 0). 그렇지 않은 경우 아핀 규칙에 따라 지불 매트릭스의 모든 요소에 이를 추가하면 양수 요소가 있는 매트릭스가 제공되고 따라서 다음을 제공하도록 숫자 p를 선택하는 것이 항상 가능합니다. 양수 값게임 가격. 이 경우 두 플레이어의 최적 혼합 전략은 변경되지 않습니다.

최적의 혼합 전략의 정의에 따르면 최적의 혼합 전략을 고수하는 첫 번째 플레이어는 두 번째 플레이어(순수 전략 포함)의 모든 전략에 대해 o 이상 승리할 것이며 두 번째 플레이어는 최적의 혼합 전략을 고수하는 것으로 나타났습니다. 혼합 전략은 첫 번째 플레이어의 전략(클린 전략 포함)에 대해 O 이상을 잃지 않습니다. 이로 인해 혼합 전략이 도출됩니다. 엑스 = = (x v x t), y = (y v ..., ~에 n) 첫 번째와 두 번째 플레이어 각각, 그리고 게임 가격 o 관계를 충족해야 합니다.

이 시스템의 모든 방정식과 부등식을 and로 나누고(o > 0이라는 가정에 의해 수행될 수 있음) 표기법을 소개합니다.

그러면 우리는 얻는다

첫 번째 플레이어는 가치를 선택하여 게임 비용을 최대화하려고 하기 때문에 x [와이그런 다음 역수 값 1/o는 다음을 선택하여 최소화해야 합니다. rg따라서 첫 번째 문제를 해결하는 것은 음수가 아닌 값을 찾는 것입니다. 아르 자형., 2=1,..., 저것어느 곳에서

두 번째 플레이어는 그러한 가치를 찾으려고 하기 때문에 와이)따라서 qy게임 비용이 최소가 되도록 두 번째 문제에 대한 해결책은 음수가 아닌 값을 찾는 것으로 줄어듭니다. q jy j = 1, ..., 피어느 곳에서

따라서 이중 선형 계획법(LP) 문제가 얻어졌으며, 이는 예를 들어 심플렉스 방법을 사용하여 풀 수 있습니다.

이러한 문제를 해결하면 값을 얻습니다. p®, 나 = 1,t q® y j = 1,..., 피.

그런 다음 게임 가격 o의 가치는 조건에 따라 결정됩니다.

최적의 혼합 전략, 즉 x®및 r/?는 다음 공식에 의해 구해집니다.

예제 4.7. "Fight for Markets"게임 버전을 고려하십시오. 경쟁하는 두 회사 A와 B는 세 가지 혁신적인 기술 프로젝트에 자금을 지원하기로 결정했습니다. 각 회사는 100 dsn을 투자할 수 있습니다. 단위 B사는 전통적으로 A사가 선두 자리를 지켜온 시장을 점유하려고 합니다. 동일한 프로젝트를 개발·개발할 경우 A사는 이익을 얻고 B사는 손실을 입게 된다. 만약 투자가 다른 프로젝트에 집중된다면 A사는 시장 재분배와 관련된 손실을 입을 것이고, B사의 이익은 A사의 손실에 상응할 것입니다. 최적의 전략기업. 다양한 전략적 상황에서 기업 A의 이익이 표에 나와 있습니다.

		B기업의 전략
기업 전략 A

솔루션 MS 엑셀

프로그램을 이용하여 문제를 해결해보자 MS 엑셀.테이블로 MS 엑셀게임 결제 매트릭스의 요소가 소개되고 MIN() 및 MAX() 함수를 사용하여 최소 및 최대값각각 행과 열로 계산한 다음 동일한 함수를 사용하여 최대값과 최소값을 찾습니다(표 4.2). 이 값들이 일치하지 않기 때문에 게임에 안장점이 없습니다. 순수한 전략으로는 해결할 수 없습니다. 게임 가격 값은 (-5, 10) 범위 내에 있어야 합니다.

표 4.2

게임에서 안장점 확인하기

게임을 선형 계획법 문제로 줄여서 해결하는 알고리즘을 사용하기 위해 아핀 규칙을 적용합니다. MIN() 함수를 사용하여 결제 매트릭스 요소의 최소값(-20)을 찾습니다. 이 숫자의 계수는 ABS(MHH(...))로 정의됩니다. 매개변수와 함께 아핀 변환 사용 엑스 = 1이고 p = 20이면 새로운 지불 매트릭스를 얻습니다(표 4.3).

표 4.3

게임을 선형 프로그래밍 문제로 축소

결제 매트릭스 오른쪽에는 필수 변수가 임의로 표시됩니다. 아르 자형.(이 단계에서는 모든 값을 지정할 수 있습니다). 결제 매트릭스 아래의 셀에서 값은 SUMPRODUCT() 함수를 사용하여 결정됩니다.

이는 LI 문제의 제약 조건에 사용됩니다. 이 값은 무작위로 선택된 것입니다. 태평양 표준시표에 나와 있습니다. 4.3.

"목적 함수"로 지정된 셀에 목적 함수의 표현식에 해당하는 수식 SUM(...)을 입력합니다.

"게임 가격"이라고 표시된 셀에 목적 함수의 값을 통해 게임 가격을 결정하는 수식을 입력합니다.

다음으로 표시된 셀에서 x 그것변수를 역변환하고 첫 번째 플레이어의 혼합 전략에 필요한 요소를 찾기 위한 공식이 도입되었습니다. x 나는= 당신 Pj.

첫 번째 선형 계획법 문제 공식화: 값 찾기

나도 마찬가지야 러시아최소한의 기능만 제공 YjPi * 조건 하의 핍 ^ a ij p i > 1,

선형 프로그래밍 문제는 프로그램의 "Solution Search" 모듈을 사용하여 해결됩니다. MS 엑셀(이 모듈의 사용은 이미 2장에서 논의되었습니다.) "대상 셀 설정" 필드는 대상 함수의 값을 포함하는 셀의 주소를 지정합니다. "동일: 최소값" 모드를 선택합니다. "Changing cell" 필드에는 원하는 변수의 배열이 표시됩니다. rg"추가" 버튼을 클릭하고 작업 제약 조건에 해당하는 배열을 선택하면 "제약 조건" 필드에 해당 조건이 설정됩니다. "매개변수" 버튼을 클릭하면 "선형 모델" 및 "음수가 아닌 값" 매개변수를 선택할 수 있는 "솔루션 검색 매개변수" 대화 상자로 이동합니다. 다른 매개변수의 값은 변경되지 않습니다. "솔루션 검색 옵션" 창을 닫은 후( 좋아요)"솔루션 검색" 창에서 "실행" 버튼을 클릭하면 LP 문제에 대한 솔루션을 검색하는 반복 프로세스가 시작됩니다.

이 과정이 끝나면 “솔루션 검색 결과” 창이 나타납니다. 문제의 모든 조건이 올바르게 공식화되고 모든 데이터, 공식 및 매개변수가 올바르게 입력되면 창에 "해결책을 찾았습니다."가 표시됩니다. 모든 제한사항과 최적성 조건이 충족됩니다.” 이 경우 솔루션을 저장하려면 다음을 클릭해야 합니다. 좋아요.계산 결과는 표에 나와 있습니다. 4.4.

LP 문제는 두 번째 플레이어에 대해서도 유사하게 해결됩니다(표 4.5). 이 경우 기술적인 편의를 위해 필요한 변수의 배열은 행으로 배열되고(두 번째 플레이어의 전략은 지불 매트릭스의 열에 해당하므로) 제한이 있는 셀은 열로 배열됩니다. 문제는 최대로 해결되고 다음과 같이 공식화됩니다. 값을 찾으십시오. q jt

최대의 기능을 제공합니까? 나)* 최대 PRI 조건 ^ i) q- q) > 0.

표 4.4

첫 번째 플레이어의 LP 문제 해결 결과

두 번째 플레이어의 LP 문제 해결 결과

표 4.5

아핀 규칙을 예비적으로 적용하는 경우 참뜻게임 가격은 지불 매트릭스의 요소를 조정하는 데 사용된 숫자 p를 빼서 얻습니다. 게임의 최종 해결책:

결과에 따르면 A 회사의 최적 전략은 투자할 자금을 29%, 60%, 11% 비율로 분배하는 것입니다. 29일, 60일, 11일. 단위 이 경우 A사는 이익을 얻습니다. 그 이하도 아니다 0.5덴 단위 A사는 B사가 최적의 프로젝트 투자 전략, 즉 39, 25, 36%를 준수하는 경우 최소 이익 가치(0.5 화폐 단위)를 받게 됩니다. 39, 25, 36 den 프로젝트에 투자하세요. 단위 각기. B 회사가 이 전략에서 벗어나면(다른 투자 패턴을 추구) A 회사의 이익이 증가합니다.

솔루션 분석에 따르면 회사 B의 경우 이 게임수익성이 없습니다 (예상 손실은 약 0.5 화폐 단위입니다). 그러나 B사가 전통적으로 A사가 장악하고 있던 시장 진입이라는 목표 달성에 비해 이러한 손실이 상대적으로 미미하다고 판단하면 최적의 투자 배분 전략을 고수함으로써 B사는 0.5덴 이하의 손실을 입게 됩니다. 단위 A회사가 비합리적으로 행동하면 B회사의 손실은 줄어들 것이다.

따라서 모든 매트릭스 게임은 게임을 두 개의 선형 프로그래밍 문제로 축소하여 해결할 수 있습니다. 그러나 이를 위해서는 많은 양의 계산이 필요하며 이는 순수 플레이어 전략의 수에 따라 증가합니다. 따라서 우선 지배전략을 제거하는 방법을 사용하여 가능하다면 순수 플레이어 전략의 수를 줄여야 한다. 예외 약한지배적인 전략은 일부 솔루션의 손실로 이어질 수 있습니다. 을 텐데 강하게전략이 지배적이라면 게임 솔루션 세트는 변경되지 않습니다. 그런 다음 모든 경우에 안장점이 있는지 확인해야 합니다. 조건 충족 확인 min a- = min ma ha...

이것이 성립한다면 플레이어는 최적의 순수 전략을 갖게 되며 솔루션은 자동으로 얻어집니다. 그렇지 않으면 최적의 전략이 혼합됩니다. 플레이어 중 최소한 한 명이 두 가지 전략만 갖고 있는 간단한 매트릭스 게임의 경우 섹션 4.2에서 논의한 그래픽 분석 솔루션 방법을 사용할 수 있습니다. 이상 도전적인 게임게임을 선형 프로그래밍 문제로 축소하는 방법과 이 문제를 해결하기 위한 적절한 도구를 사용할 필요가 있습니다.

이 섹션을 마무리하기 위해 우리는 게임을 수동으로 해결하는 경우 지배적인 전략을 제거하여 보상 매트릭스를 단순화하는 것이 중요하다는 점에 주목합니다. 최적의 전략을 찾기 위해 컴퓨터를 사용하는 경우, 원본 행렬과 단순화된 행렬의 수치해석은 동일한 알고리즘을 사용하여 수행되고, 계산 시간의 차이도 미미하므로 지배적인 전략을 찾는 데 소요되는 노력과 시간이 낭비될 수 있습니다. .

주어지게 하라 티엑스 피-그 게임이 설정한 게임 티엑스 피-행렬 ㅏ첫 번째 플레이어의 경우, ㅏ= [a^], G이자형 나= (1,..., ?n), 제이 € J== (1,..., ?r). 우리는 ay^O라고 가정하겠습니다. 이 경우 게임 가격은 v> 0. 또한 행렬에서 ㅏ동일한 행과 열이 없습니다(있는 경우 불필요한 항목을 제거해야 함). 마지막으로 매트릭스에 불필요한 전략이 없다고 가정합니다. 최대로 플레이한 첫 번째 플레이어(각각 최소로 플레이한 두 번째 플레이어)에 대한 다른 열(행)의 해당 요소 중 ^(^) 요소가 있는 열(행)은 이미 제외되었습니다.

이러한 표기법을 고려하여 제한 사항을 다시 작성합니다.

최대값을 찾으려면 V을 위한 v 9우리는 최소값을 찾아야 합니다

해당 기능을 입력하시면 z = - = X4,그것은 밝혀졌다

첫 번째 플레이어를 위한 최적의 전략을 찾으려면 다음 선형 계획법 문제를 풀어야 합니다.

마찬가지로 두 번째 플레이어(M)에 대한 최적의 전략을 찾기 위해 (R.Q) ^ ?;), 선형 계획법 문제를 해결해야 합니다.

우리는 요소가 ㅏ! 피 ^ a" i2, r = 1.3. 따라서 첫 번째 열을 제외할 수 있습니다.(전략 안에사령관 때부터 (안에)최소한으로 재생됩니다. 또한 요소 a" 3 ^ ㅏ[ 4 , G= 1.3. 따라서 네 번째 열(전략)을 제외할 수 있습니다. 안에4 ). 게임 매트릭스는

마지막으로 우리는 요소가 a”j ^ a 2 р j = 1.2. 따라서 지휘관(L)이 최대로 플레이하기 때문에 두 번째 라인(전략 L2)을 제외할 수 있다. 게임 매트릭스는

이 문제를 해결하려면 마지막 게임, 선형 프로그래밍을 적용해 보겠습니다. 이중 문제(1.30)가 있으며

기하학적 방법을 사용하여 이러한 문제를 해결해 보겠습니다(그림 1.5).

점좌표 와 함께원래 문제에 대한 해결책을 제시하십시오. 점 C의 좌표를 찾기 위해 선형 대수 방정식 시스템을 푼다.

쌀. 1.5.

프로그램( x = x 2 = 1/2) 최소한의 경제적 기능을 제공합니다. z, z- Z m i n = 1.

점좌표 와 함께또한 준다 최적의 프로그램이중 문제의 경우. 프로그램 (와이 = ~에 2 = 1/2)은 경제적 기능의 최대값을 제공합니다. 승, 승 = = 1.

왜냐하면 z = 1= - 그러면 티/ = - = 1 => 가격 v = v"-l = 0.

지휘관을 위한 최적의 전략 얻기 (엘):

즉, 그는 자신이 처분할 수 있는 모든 군인을 활용하여 어떤 입구를 통해 시설에 들어가려고 노력해야 합니다.

지휘관을 위한 최적의 전략 (안에):

TS 한 입구는 두 명의 군인이 지키고 다른 입구는 한 명이 지켜야 합니다. ?

논평 6. 행렬의 크기를 줄이지 않으면 ㅏ!두 번째 순서로 게임을 풀려면 표준 형식으로 표시되어야 하는 쌍대 문제(1.31)에 단순 방법을 적용해야 합니다.

세 개의 단순 테이블을 채워 보겠습니다.

1 번 테이블
				2 *

k = 2T

해상도 요소 - 2*.

에게! = 3T

표 2

해상도 요소 - 2*.

표 3

모든 기준의 값 아지 ^ 0, (유인^0). 그러므로 프로그램은 (y 2 = 1/2; ?у 3 = 1/2; sch= 1; ?yi = 100만= 2У5 = 2У7 =

• 0) 경제 함수 gi, zD의 최대값을 제공합니다 = w 최대 =

mt = - = 1이므로, 티/ = 1 v = T/ - 1 = 0(왜냐하면

무엇 와이"=v+1). 최적의 지휘관 전략을 얻는다 (안에), 객체를 보호합니다.

주요 문제(1.30)에 대한 최적의 프로그램을 찾기 위해 우리는 Neumann의 정리(p. 34)를 적용합니다.

Min = Wmax- SO, 원래 문제의 ECONOMIC 함수 2의 MINIMUM은 다음과 같습니다. z - zmn ​​= 1.

변수 간의 대응 엑스(그리고 yj관계식 (1.24)에 의해 결정됩니다(p. 34). 따라서,

표 3에서 초기 문제에 대한 최적의 프로그램을 찾습니다.

여기서 우리는 지휘관(L)의 최적 전략을 얻습니다.

이 결과는 이전에 기하학적 방법을 사용하여 문제를 풀 때 얻었습니다. ?

괴츠젬김

이 매뉴얼은 세 부분으로 구성된 패키지인 Scientific Workplace를 사용하여 편집되었습니다. Scientific Word 부분은 텍스트를 입력하고 서식을 지정하는 데 사용됩니다. Maple V 또는 MuPAD의 두 번째 부분을 사용하면 기호 형식이나 수치 방법을 사용하여 수학적 계산을 수행하고 R 2 또는 R 3에서 그래프를 작성할 수 있습니다. Exam Builder의 세 번째 부분은 지식 수준 테스트를 구성하는 데 사용됩니다.

예를 들어 Scientific Work-Place를 사용하여 선형 프로그래밍 문제를 해결해 보겠습니다.

해결 방법: 키보드, 기본 메뉴 및 도구 모음을 사용하여 8 x 1 매트릭스를 채우십시오.

메인 메뉴에서 명령을 적용하십시오 계산 + 단순 + 최대화. 5개의 단순 테이블을 채우는 대신 다음과 같은 답을 얻습니다. 최대값은 다음과 같습니다. (23 = 0, ?'1 = O.X2 = 40}.

• atjs가 존재하는 경우