運籌學(xué) 其他對策模型

其他對策模型姓名專業(yè)7.1陣地對策7.1陣地對策陣地對策

對策論中所謂局中人的一個策略是指局中人的一個完整地行動方案，例如賽馬的例子中，出賽馬的一個次序是一個完整地行動方案。但是有的對策現(xiàn)象中完整地行動方案是不容易說清楚的，例如下象棋，要走很多步，每步又有很多可供選擇的走法，那么一個由始至終的行動方案怎么說得清楚呢？但是這種類型的對策現(xiàn)象有它的特點，即它規(guī)定了各步該誰走，而走的局中人又有多少種走法可選擇，另外走的局中人走時是否能知道別的局中人在他此步之前是怎么走的信息等等。因此根據(jù)此類對策現(xiàn)象的特點來形成數(shù)學(xué)模型也是對策論的工作之一，由于這類對策現(xiàn)象是一步一步走的，所以給它起個名字叫“陣地對策”。7.1陣地對策特點

假如給局中人編上號碼1,2,…,n則每步上都規(guī)定了是哪個局中人的步，對于不是局中人的步而是機遇步，我們規(guī)定這種步是局中人”0”的步，那么每一步都有一個數(shù)與之對應(yīng)。而每一步上都是可供選擇的路（即走法）的集合。每一步都指出能知道什么信息。最后在各路的終點（即無擇路可走出去的點）上規(guī)定了各局中人的“得失”。所以這樣的對策可用樹狀圖來表達。即：（1）一棵定向的樹，樹根表示第一步，其后各分叉點表示后繼各步。

（2）每個分叉點上所有枝條的個數(shù)，即為該步擇路的個數(shù)。

（3）樹的各個分叉點上都給定0,1,…,n中一個數(shù)。即規(guī)定在這點上是哪個局中人的步（帶數(shù)“0”的步即為機遇步）。

（4）帶數(shù)”0”的分叉點上，如果它有k個枝條，則在這個枝條上規(guī)定了一個概率分布，即給出k個數(shù)

7.1陣地對策特點（5）諸分叉點全體組成的點集有一個劃分，它把一切分叉點完全無遺地分在互斥的子集（稱為信息集）內(nèi)。這些子集滿足下列假設(shè)：

（i）屬于同一信息集的一切分叉點都是屬于同一個局中人的步。（ii）同一信息集的各個分叉點有相同數(shù)目的擇路。（iii）帶數(shù)“0”的分叉點所在的信息集只能有這一個分叉點。（6）這棵樹的每一個樹梢上都定義有n個實數(shù)F1,F2,……,Fn分別表示局中人1,2,……,n的“得失”。7.1陣地對策例14猜數(shù)對策局中人甲秘密地選定1,2,3三個數(shù)之一。局中人乙猜甲所選的數(shù)，并且說出他所猜的是什么數(shù)，每一次局中人乙說出他所猜的數(shù)后，甲按照實際情況回答“太高”，“太低”或“正確”。對策繼續(xù)進行到乙回答出為止。甲的支付數(shù)等于乙回答出正確答案所需要的次數(shù)。顯然局中人甲的策略是選擇數(shù)1,2,或3。局中人乙的策略可以用一組數(shù)（G;H,L）來表示。其中G是第一次猜的數(shù)，H是局中人乙聽到甲回答“太高”后第二次猜的數(shù)。L是局中人乙聽到甲回答“太低”后第二次猜的數(shù)。很清楚，最多猜兩次對策就結(jié)束了。因此局中人乙有五個策略（1;0,2）,（1;0,3）,（2;1,3）,（3;1,0）,（3;2,0）其中0表示這種情況不存在。局中人甲得到的支付數(shù)，是局中人乙直到聽局中人甲說“正確”時共回答的次數(shù)。支付矩陣列出如下：7.1陣地對策猜數(shù)對策也是一個陣地對策，可用圖4-1的樹狀圖來描寫：7.2連續(xù)對策7.2連續(xù)對策在一個有限對策里，每個局中人的策略集是有限的，即策略的總數(shù)可以很大，但畢竟是一個有限數(shù)?？墒窃S多軍事和經(jīng)濟的對策往往涉及無窮多個策略的問題。例如在一海域里潛行的潛水艇，為躲過敵方飛機的偵察，該如何選擇出水換氣的地點的對策問題。其策略數(shù)目就是無窮多個。具有無窮多個策略的對策稱為無限對策。最簡單的一種是被稱為連續(xù)對策。連續(xù)對策在其最簡單的形式下可描述如下：局中人甲在[0,1]閉區(qū)間中選擇一個點X，同時局中人乙在[0,1]閉區(qū)間中選擇一個點Y，而在局勢

之下，局中人甲得到支付為。假定對策是零和的，則局中人乙得到的支付為

。并且假設(shè)支付函數(shù)

對于每個存在，而對于每個

也存在，所以對局中人甲來說，存在一個策略，使他至少得到。同樣對局中人乙來說，存在一個策略使他至少得到

容易證明下式成立：

7.2連續(xù)對策

如果上式的等號成立，那么設(shè)策略X0，Y0使

對于一切Y成立

對于一切X成立。則稱X0是局中人甲的最優(yōu)純策略，Y0是局中人乙的最優(yōu)純策略。（X0,Y0）稱為此連續(xù)對策的鞍點。如果上式的等號不成立。就沒有最優(yōu)純策略。于是和有限兩人零和對策中引入混合策略（即是有限集上的概率分布函數(shù)）的概念一樣，我們引無限集上的概率分布函數(shù)為無限對策中的混合策略。即連續(xù)對策的混合策略是一個從[0,1]閉區(qū)間中選擇一個不大于X的數(shù)的隨機過程。當甲取混合策略即某個分布函數(shù)F(x)，而乙取混合策略G(y)時，甲的期望支付是斯蒂爾杰積分：

類似于矩陣對策當

及

7.2連續(xù)對策

都存在且相等（其中D是[0,1]上的分布函數(shù)的全體組成的集合），則在混合策略中有平衡局勢。也就是存在甲的混合策略F0(X)，乙的混合策略G0(Y)使對任何的X,Y有：7.3多人對策7.3多人對策當局中人是兩個以上時，這樣的對策稱為多人對策。一般多人對策中不可避免會出現(xiàn)合作的情況，例如兩人有默契，合起來對付第三個，使第三個必敗。所以討論多人對策時，對局中人之間可能有怎樣的合作必需進行研究。所謂正規(guī)型不結(jié)盟多人對策是指三元體

其中I是局中人集合，Si是局中人I的策略集，Hi是局中人I的得失函數(shù)?，F(xiàn)在我們對這種多人對策來討論其中局中人之間可能有怎樣的合作。下面引入特征函數(shù)的概念。當我們把I的一個子集合R看成是一個聯(lián)盟，而把I中除去R后剩下元素全體記作I/R看成是另一個聯(lián)盟，然后構(gòu)造一個兩零和對策：

7.3對人對策

如果對策有值則把

看成是聯(lián)盟R的“得失”。假定對于任何子集而言，對策

的值都存在，記為

。然后我們假定（其中表示空集）。這樣我們就在

的一切子集上定義了一個函數(shù)，這個函數(shù)稱為對策P的特征函數(shù)。它必有如下的性質(zhì)：(1)(2)(3)

由性質(zhì)（3）可推得

特別有

光從特征函數(shù)來討論可能成立什么聯(lián)盟還為時過早，因為雖然結(jié)盟會增加共同贏得，但如果制定的分配共同贏得的方案不合適，也會引起聯(lián)盟的破裂。所以又引入了分配的概念。7.3對人對策在零和對策中，局中人如何結(jié)盟呢？這主要取決于分配對局中人的影響，所謂分配乃是指滿足下列條件的n個實數(shù)d=(a1,a2,……,an).對于一個分配a=(a1,a2……,an)而言，要使某個聯(lián)盟有可能形成，必須要這個條件如果滿足，則稱聯(lián)盟R對分配a有效。設(shè)為兩個分配，如果存在聯(lián)盟，R對分配a有效，且使得對一切

而言，ai>bi

那么說分配α優(yōu)于分配β，記為α>β。顯然當α>β時，聯(lián)盟R必至少包含有兩個局中人。因為若R只包含一個局中人i，那么由

但β乃是一個分配，所以bi>U(i)必成立。從而ai>U(i)，但已假設(shè)R對分配a有效，即必須成立，從而矛盾。7.3對人對策

引入這些概念之后，有人給出如下的解的概念。定義：命W是某些分配組成的集合，如果（1）對于任何

,α>β和β>α都不成立（2）對任何，必存在

使得

成立。

那么W就叫做對策P的一個解。下面舉一個多人對策的例子。此多人對策的樹狀圖為7.3對人對策這是一個全信息多人陣地對策。如果1,2合作，則上面陣地對策等價于如下的陣地對策（見圖4-3）（-1,1）（1,0）由于最后一步都是③的步；因此在這步上③一定選擇對他有利的擇路，也即絕不會選使他一無所得的擇路。但第一，二步是①、②聯(lián)盟的步，他們也一定選擇使他們總收入最大的擇路?，F(xiàn)在分析一下如果第一步選了右邊的擇路，最后肯定①、②只得到1而③可得到3.那么如果第一步選了左邊的擇路，而第二步分兩種情況：（1）如果選右邊的擇路，則①②可得1，而③只可得0。（2）如果選左邊的擇路，則①②可得-1，而③可得1。因此①②為了自己多得，也為了不讓③有所得，他們必須是第一步選左邊的擇路。所以①②聯(lián)盟時①②的總收入是1記作U(1,2)，而③的收入是0，記作U(3)。也即

U(1,2)=1;U(3)=0

同樣的方法分析后可得

U(1,3)=3;U(2)=1U(2,3)=2;U(1)=07.3對人對策

如果①，②，③結(jié)成聯(lián)盟時，等價于一人對策

顯然此時第一步必走右邊的擇路，最后總收入是4，記作U(1,2,3)=4。然后令U(V)=0。如此得到了定義在局中人集合I的一切子集上的一個函數(shù)（但與前述特征函數(shù)不太一樣，因為此時對策不是零和的）。從此函數(shù)可以看到任何局中人不結(jié)盟總是一無所得的，但是哪樣的結(jié)盟會實現(xiàn)呢，這就與結(jié)盟時商定的總收入如何在盟員之間分配的協(xié)定有關(guān)了。例如三個人一起合作時，總收入4該如何分配呢，如果照樹梢上寫的支付函數(shù)分配，肯定有一人沒收入因而不滿意而退出聯(lián)盟。所以討論多人對策中的結(jié)盟問題，必須要涉及結(jié)盟后如何分配（也即有所謂“邊支付”）的問題。07.4微分對策7.4微分對策在追蹤對策中追趕雙方是在空間或地面運動的。這里逃的一方有時不是單純逃，而是企圖在被追到以前達到某種目的。而追的一方就要在逃方達到目的之前追到他。

設(shè)想有一只老鼠在園形的湖邊碰上了貓，它想回洞已來不及，只好跳入湖中企圖逃走。但貓在岸上跑的速度比鼠在湖中游的速度快得多，例如是鼠速的4倍。粗看起來，老鼠沒有好辦法，只有束手就擒。但是，仔細研究一下，老鼠還是可以跑掉的。我們將老鼠所跑路線的奧妙介紹如下：

圖4-5中大圓表示圓湖其半徑設(shè)為R，取1/4R為半徑作一同心小圓K于是老鼠跳入湖中后，先游到小圓K內(nèi)，然后轉(zhuǎn)圈游，貓在岸上按固定的路線跟著老鼠；但用同樣的時間，老鼠在圓k內(nèi)轉(zhuǎn)圈所轉(zhuǎn)過的角度比貓沿湖岸轉(zhuǎn)圈轉(zhuǎn)過的角度要大。所以老鼠可以游到和貓不在同一半徑，而在同一直徑的圓K的邊界點*的位置上去，然后沿此直徑游向湖岸。因為*點到湖岸的最短距離是3/4R，設(shè)鼠的速度為V,則鼠由*點到湖岸所需的時間是3R/4V，由于貓的位置同*點不在同一半徑上，所以貓的到達同一地點的路程正好是半圓周，即。那么，貓的速度是鼠的4倍（即4V），但貓所需時間是

所以鼠先上岸，且有時間迅速跑入附近的鼠洞而溜掉。貓鼠貓鼠貓鼠7.4微分對策

追蹤問題也存在對策現(xiàn)象所共有的根本要素：1.局中人此時局中人就是迫者與逃者，例如在空戰(zhàn)中一方的殲擊機和另一方的轟炸機，在空防中是攻方的轟炸機和守方的高射炮，在導(dǎo)彈戰(zhàn)中是一方的導(dǎo)彈和另一方的反導(dǎo)彈等等。2．策略追逃雙方都有自己的可選擇的行動方案，例如轟炸機可選擇飛行路線和投彈方式等，殲擊機可選擇攻擊時間，飛行路線和攻擊方式等，高射炮可選擇發(fā)射角度等等。不過在追蹤問題中局中人的完整的行動方案(所謂策略)比以前介紹的矩陣對策中的完整的行動方案要復(fù)雜得多了。因為在追蹤問題中，局中人例如殲擊機必須每時每刻都掌握對方相對位置和某些情況以便跟蹤追擊。同時轟炸機也得每時每刻都能掌握雙方的相對位置和某些情況以便躲過攻擊，飛達轟炸目標。所以用數(shù)學(xué)描述追蹤對策中的策略，也必須要反映出這種連續(xù)動態(tài)的決策過程，這就得借助微分方程的理論。因此這類對策理論稱為微分對策。在微分對策中，通常用向量X(t)表示時刻t時各方為繼續(xù)進行對策所必須知道的雙方的狀況變量。例如空戰(zhàn)中雙方飛機的相對位置和機頭所指方向等等，因此X(t)也被稱為狀況變量。7.4微分對策同時，各局中人都有控制自己運動路線的手段，例如飛機駕駛員可以做改變機速和使機頭拐彎等操作，于是機速和機頭拐彎的曲率半徑等是屬于局中人直接可控制的量，這些量的改變就能引起前述狀況變量的改變，并且這些量將怎么變，對方是不知道的，所以這些向量稱做控制量。于是局中人的一個策略就是決定一個連續(xù)控制的規(guī)律，即對任意狀況