對(duì)策模型和算法

對(duì)策模型和算法第1頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月在對(duì)策論中，應(yīng)有以下要素：(1)局中人。是指參與對(duì)抗的各方，可以是一個(gè)人，也可以是一個(gè)集團(tuán)。在例1.1的甲、乙兩名兒童就是局中人。(2)

策略。是指局中人所擁有的對(duì)付其他局中人的手段、方案的集合。如例1.1中共有石頭、剪子、布三種策略。(3)支付函數(shù)（或收益函數(shù)）。是指一局對(duì)策后各局中人的得與失，通常用正數(shù)字表示局中人的得，用負(fù)數(shù)字表示局中人的失。在例1.1的局中人甲的支付函數(shù)如表所示。7/11/20232第2頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月乙石頭剪子布甲石頭01-1剪子-101布1-10例1.1“石頭--剪子--布”中兒童甲的支付函數(shù)第3頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月當(dāng)局中人得失總和為零時(shí)，稱(chēng)這類(lèi)對(duì)策為零和對(duì)策；否則稱(chēng)為非零和對(duì)策。當(dāng)局中人只有兩個(gè)，且對(duì)策得失總和為零，則稱(chēng)為二人零和對(duì)策，若總得失總和為常數(shù)，則稱(chēng)為二人常數(shù)和對(duì)策，若得失總和是非常數(shù)的，則稱(chēng)為二人非常數(shù)和對(duì)策。若二人對(duì)策雙方的得失是用矩陣形式表示，則稱(chēng)支付函數(shù)為支付矩陣，相應(yīng)的對(duì)策稱(chēng)為矩陣對(duì)策。通常，支付矩陣表示局中人A的支付函數(shù)。第4頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月鞍點(diǎn)對(duì)策是對(duì)策的最基本策略，為更好地理解鞍點(diǎn)對(duì)策，先看一個(gè)簡(jiǎn)單的例子。1.對(duì)策的基本策略---鞍點(diǎn)對(duì)策例9.2設(shè)A、B兩人對(duì)策，各自擁有三個(gè)策略：a1,a2,a3和b1,b2,b3,局中人A的支付（收益）矩陣由表1.2所示。試求A、B各自的最優(yōu)策略。b1b2b3mina11391a26575a38422max859第5頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月問(wèn)題分析： 從直觀來(lái)看，局中人A應(yīng)該出策略a1,因?yàn)檫@樣選擇，他有可能得到9.但局中人B看到了這一點(diǎn)，他出策略b1，這樣局中人A不能得到9，而只能得到1.因此，局中人A也充分認(rèn)識(shí)到這一點(diǎn)，他應(yīng)當(dāng)出策略a3,這樣做，就有可能得到8，而這種情況下局中人B，就要出策略b3，局中人A也只能得到2. 這樣做下來(lái)，局中人A只能選擇策略a2,而局中人B也只能選擇策略b2，大家達(dá)到平衡，最后局中人A贏得的值為5，局中人B輸?shù)舻闹禐?.第6頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 從上面的分析可以看出，無(wú)論局中人A選擇什么策略，他贏得的值總是小于等于5，而無(wú)論局中人B選擇什么策略，他輸?shù)舻闹悼偸谴笥诘扔?，5就是支付矩陣的鞍點(diǎn)。 現(xiàn)討論一般情況。假設(shè)局中人A的支付矩陣由表1.3所示。12…n1C11C12…Cn12C21C22…Cn2┆┆┆┆mCm1Cm2…Cmn第7頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 其中局中人A有m個(gè)策略α1,…,α

m,局中人B有n個(gè)策略β1,…,β

n,分別記為S1={α1,…,α

m},S2={β1,…,β

n} C為局中人A的支付矩陣，而-C為局中人B的支付矩陣。因此，矩陣對(duì)策記為G={A,B;S1,S2,C},或G={S1,S2,C} 對(duì)于一般矩陣對(duì)策，有如下定義和定理。第8頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月定義9.1設(shè)G={S1,S2,C}是一矩陣對(duì)策，若等式成立，則記vG=,ci*j*并稱(chēng)vG為對(duì)策G的值。 稱(chēng)使式(1)成立純局勢(shì)(α

i*,β

j*)為G在純策略下的解（或平衡局勢(shì)），稱(chēng)α

i*和β

j*分別為局中人A、B的最優(yōu)純策略。第9頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月定理9.1 矩陣對(duì)策G={S1,S2,C}在純策略意義下有解的充分必要條件是：存在純局勢(shì)(α

i*,β

j*)使得定義9.27/11/202310第10頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月當(dāng)矩陣對(duì)策的最優(yōu)解不唯一時(shí)，有如下定理：定理9.2定理9.3第11頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月2.無(wú)鞍點(diǎn)的對(duì)策策略---混合對(duì)策如果支付矩陣有鞍點(diǎn)，選擇鞍點(diǎn)對(duì)策是最優(yōu)的對(duì)策策略，如果支付矩陣無(wú)鞍點(diǎn)，則需要選擇混合對(duì)策。 我們回過(guò)頭再看例9.1（“石頭--剪子--布”），對(duì)于支付矩陣,有 沒(méi)有純最優(yōu)策略。因此無(wú)法用定理9.1來(lái)確定最優(yōu)策略。在這種情況下，只能求相應(yīng)的混合策略。類(lèi)似于純策略，混合策略有如下定義和定理。第12頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月定義9.3設(shè)有矩陣對(duì)策G＝｛S1，S2，C｝稱(chēng)分別為局中人A和B的混合策略。稱(chēng)(x,y)(xS1*,yS2*)為一個(gè)混合局，稱(chēng)為局中人A的支付函數(shù)（贏得函數(shù)）。第13頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月定義9.4 設(shè)G*＝｛S1*，S2*，C｝是G＝｛S1，S2，C｝的混合擴(kuò)充，若則稱(chēng)vG為對(duì)策G*的值。稱(chēng)使式(7)成立混合局勢(shì)(x*,y*)為G在混合策略下的解，稱(chēng)x*和y*分別為局中人A和B的最優(yōu)混合策略。第14頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月定理9.4 矩陣對(duì)策G＝｛S1，S2，C｝在混合策略意義下有解的充分必要條件是：存在(xS1*,yS2*)使(x*,y*)為函數(shù)E(x,y)的一個(gè)鞍點(diǎn)，即第15頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月3.混合對(duì)策求解方法通常用線(xiàn)性規(guī)劃方法求混合策略的解。設(shè)局中人A分別以x1,x2,…,xm的概率混合使用他的m種策略，局中人B分別以y1,y2,…,ym的概率混合使用他的n種策略。第16頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月當(dāng)A采用混合策略，B分別采用純策略bj(j=1,2,…,n),A的贏得分別為依據(jù)最大最小原則，應(yīng)有其中vA是局中人A的贏得值。第17頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月將問(wèn)題（9）寫(xiě)成線(xiàn)性規(guī)劃問(wèn)題 也就是說(shuō)，線(xiàn)性規(guī)劃問(wèn)題(10)～(13)的解就是局中人A采用混合策略的解。類(lèi)似可求局中人B的最優(yōu)策略的解。第18頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.3 用線(xiàn)性規(guī)劃方法求解例1的 最優(yōu)混合策略。按照線(xiàn)性規(guī)劃（10）～（13）寫(xiě)出相應(yīng)的LINGO程序，程序名：exam0903a.lg4MODEL:1]sets:2]playerA/1..3/:x;3]playerB/1..3/;4]game(playerA,playerB):C;5]endsets第19頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月6]data:7]C=01-18]-1019]1-10;10]enddata11]max=v_A;12]@free(v_A);13]@for(playerB(j):14]@sum(playerA(i):C(i,j)*x(i))>=v_A);15]@sum(playerA:x)=1;END第20頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月得到最優(yōu)解（只保留相關(guān)部分）Globaloptimalsolutionfoundatiteration:3Objectivevalue:0.000000VariableValueReducedCostV_A0.0000000.000000X(1)0.33333330.000000X(2)0.33333330.000000X(3)0.33333330.000000第21頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 即兒童甲以1/3的概率出石頭、剪子、布中每種策略的一種，其贏得值為0. 用線(xiàn)性規(guī)劃求出兒童乙有同樣的結(jié)論。 計(jì)算到此，讀者可能會(huì)產(chǎn)生一個(gè)問(wèn)題：一個(gè)具有鞍點(diǎn)的對(duì)策問(wèn)題，如果采用線(xiàn)性規(guī)劃方法求解，將會(huì)出現(xiàn)什么情況？第22頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.4用線(xiàn)性規(guī)劃方法求解例2解：寫(xiě)出LINGO程序，程序名：exam0904.lg4MODEL:1]sets:2]playerA/1..3/:x;3]playerB/1..3/;4]game(playerA,playerB):C;5]endsets6]data:7]C=139第23頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月8]6579]842;10]enddata11]max=v_A;12]@free(v_A);13]@for(playerB(j):14]@sum(playerA(i):C(i,j)*x(i))>=v_A);15]@sum(playerA:x)=1;END第24頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月計(jì)算結(jié)果為（保留有效部分）Globaloptimalsolutionfoundatiteration:0Objectivevalue:5.000000VariableValueReducedCostV_A5.0000000.000000X(1)0.0000002.000000X(2)1.0000000.000000X(3)0.0000001.000000第25頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 由結(jié)果可以看到，局中人A仍然選擇純策略。對(duì)局中人B的計(jì)算也會(huì)出現(xiàn)同樣的情況。 從例9.3和例9.4可以看出，無(wú)論矩陣對(duì)策有無(wú)鞍點(diǎn)，我們均可以采用線(xiàn)性規(guī)劃的方法求其對(duì)策，只不過(guò)具有鞍點(diǎn)的對(duì)策可以有更簡(jiǎn)單的算法罷了。第26頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月1.2二人常數(shù)和對(duì)策 所謂常數(shù)和對(duì)策是指局中人A和局中人B所贏得的值之和為一常數(shù).顯然，二人零和對(duì)策是二人常數(shù)和的特例，即常數(shù)為零。 對(duì)于二人常數(shù)和對(duì)策，有純策略對(duì)策和混合策略對(duì)策。其求解方法基本上是相同的。1.鞍點(diǎn)對(duì)策 對(duì)于二人常數(shù)和對(duì)策，仍然有鞍點(diǎn)對(duì)策，其求解方法與二人零和對(duì)策相同。第27頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.4 在晚8點(diǎn)至9點(diǎn)這個(gè)時(shí)段，兩家電視臺(tái)在競(jìng)爭(zhēng)100萬(wàn)電視觀眾收看自己的電視節(jié)目，并且電視臺(tái)必須實(shí)時(shí)公布自己在下一時(shí)段的展播內(nèi)容。電視臺(tái)1可能選擇的展播方式及可能得到的觀眾如表所示。電視臺(tái)min西部片連續(xù)劇喜劇片電視臺(tái)1西部片35156015連續(xù)劇45585045喜劇片38147014max455870第28頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月解：事實(shí)上，對(duì)方得到的，就是自己失去的，完全利用二人零和的方法確定最優(yōu)純策略，即 因此，電視臺(tái)1選擇播放連續(xù)劇，贏得45萬(wàn)觀眾，電視臺(tái)2播放西部片，贏得100-45=55萬(wàn)觀眾。2.混合對(duì)策 對(duì)于常數(shù)和對(duì)策，也存在混合對(duì)策，同樣可以采用線(xiàn)性規(guī)劃方法求解，這里就不舉例子了。第29頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月§2二人非常數(shù)和對(duì)策 二人非常數(shù)和對(duì)策也稱(chēng)為雙矩陣對(duì)策。在前面介紹的常數(shù)和（零和）對(duì)策中，均包含兩種情況，純策略和混合策略。對(duì)于非常數(shù)對(duì)策，也包含這兩種策略。1.純對(duì)策問(wèn)題例9.6：囚徒的困境(表9.2.1)乙坦白不坦白甲坦白（-3，-3）(0,-10)不坦白（-10，0）(-1,-1)第30頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.6 設(shè)有甲、乙兩名嫌疑犯因同一樁罪行被捕，由于希望他們坦白并提供對(duì)方的犯罪證據(jù)，規(guī)定如兩人均坦白各判刑3年；如上方坦白另一方不坦白，坦白一方從輕釋放，不坦白一方判刑10年；如兩人均不坦白，由于犯罪事實(shí)很多不能成立，只能各判1年，見(jiàn)表9.2.1所示。 試分析甲、乙兩犯罪嫌疑人各自采用什么策略使自己的刑期最短。第31頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.6給出了典型的二人非常數(shù)和對(duì)策，每人的收益矩陣是不相同的，因此稱(chēng)為雙矩陣對(duì)策。通常規(guī)定，雙矩陣中，第一個(gè)元素是局中人A的贏得值，第二個(gè)元素是局中人B的贏得值。 問(wèn)題分析：這是一個(gè)二人非常數(shù)和對(duì)策問(wèn)題。從表面看，兩犯罪嫌疑人拒不坦白，只能被判1年徒刑，結(jié)果是最好的。但仔細(xì)分析，確無(wú)法做到這一點(diǎn)。因?yàn)榉缸锵右扇思兹绻捎貌惶拱撞呗?，他可能被判的刑期?到10年，而犯罪嫌疑人乙可能判的刑期為0到1年。第32頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 而甲選擇坦白，他被判的刑期為0到3年，此時(shí)，犯罪嫌疑人乙可能判的刑期為3到10年。因此，犯罪嫌疑人甲一定選擇坦白。 基于同樣的道理，犯罪嫌疑人乙也只能選擇坦白。 選擇坦白是他們最好的選擇，各自被判3年。第33頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 事實(shí)上，設(shè)(cijA,cijB)是甲、乙贏得值，則甲、乙采用的策略是1.純對(duì)策問(wèn)題的基本概念 按照上面的論述，對(duì)于一般純對(duì)策問(wèn)題，局中人A、B的支付（贏得）矩陣由表9.2.2所示。第34頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月局中人A、B的支付矩陣β1β2…βnα1…α2…┆┆┆┆αm…第35頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 為局中人A的支付（贏得）矩陣， 為局中人B的支付（贏得）矩陣。因此，矩陣對(duì)策記為：

G={A,B;S1,S2,CA,CB}或G={S1,S2,CA,CB}第36頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月定義9.5：設(shè)G={S1,S2,CA,CB}是一雙矩陣對(duì)策，若等式 成立，則記vA=，并稱(chēng)vA為局中人A的贏得值，記vB=，并稱(chēng)vB為局中人B的贏得值，稱(chēng)（αi*,β

j*)為G在純策略下的解（或Nash平衡點(diǎn)），稱(chēng)αi*和β

j*分別為局中人A、B的最優(yōu)純策略。第37頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月2.純對(duì)策問(wèn)題的求解方法 實(shí)際上，定義9.5也同時(shí)給出了純對(duì)策問(wèn)題的求解方法。因此，對(duì)于例9.6,((1,0),,(1,0))是Nash平衡點(diǎn)，也就是說(shuō)，坦白他們的最佳策略。再看一個(gè)例子。例：9.7（夫妻周末安排問(wèn)題）一對(duì)夫妻，商量周末安排。丈夫喜歡看足球，妻子喜歡聽(tīng)音樂(lè)會(huì)。他們的贏得值由表9.7所示。請(qǐng)為這對(duì)夫妻設(shè)計(jì)最好的度周末的方案。第38頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月解：由定義9.5可知，對(duì)于策略((1,0),(1,0))或策略((0,1),(0,1))均是Nash平衡點(diǎn)，也就是最優(yōu)解，即他們選擇是共同看足球，或共同聽(tīng)音樂(lè)會(huì)。表中帶有下劃線(xiàn)是他們采用策略的贏得值。妻足球音樂(lè)會(huì)夫足球(3,1)(-1,-1)音樂(lè)會(huì)(-1,-1)(1,3)第39頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月2.混合對(duì)策問(wèn)題如果不存在使式(18)成立的對(duì)策，則需要求混合對(duì)策。類(lèi)似于二人常數(shù)和對(duì)策情況，需要給出混合對(duì)策的最優(yōu)解。1.混合對(duì)策問(wèn)題的基本概念定義9.6在對(duì)策G=\{S1,S2,CA,CB}中，若存在策略對(duì)使得第40頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月則稱(chēng) 為G的一個(gè)非合作平衡點(diǎn)。記則稱(chēng)vA,vB分別為局中人A、B的贏得值。對(duì)于混合對(duì)策問(wèn)題有如下定理定理9.5每個(gè)雙矩陣對(duì)策至少存在一個(gè)非合作平衡點(diǎn)。定理9.6混合策略為對(duì)策G=\{S1,S2,CA,CB}的平衡點(diǎn)的充分必要條件是：第41頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月2.混合對(duì)策問(wèn)題的求解方法 由定義9.6可知，求解混合對(duì)策就是求非合作對(duì)策的平衡點(diǎn)。進(jìn)一步，由定理9.6得到，求解非合作對(duì)策的平衡點(diǎn)，就是求解滿(mǎn)足不等式約束(20)的可行點(diǎn)。因此，混合對(duì)策問(wèn)題的求解問(wèn)題就轉(zhuǎn)化為求不等式約束(20)的可行點(diǎn)，而LINGO軟件可以很容易做到這一點(diǎn)。第42頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.8

有甲、乙兩支游泳隊(duì)舉行包括三個(gè)項(xiàng)目的對(duì)抗賽。這兩支游泳隊(duì)各有一名健將級(jí)運(yùn)動(dòng)員（甲隊(duì)為李，乙隊(duì)為王），在三個(gè)項(xiàng)目中成績(jī)很突出。但規(guī)則準(zhǔn)許他們每個(gè)人分別只能參加兩項(xiàng)比賽，而每隊(duì)的其他兩名運(yùn)動(dòng)員則可參加全部三項(xiàng)比賽。各運(yùn)動(dòng)員的成績(jī)?nèi)绫?-8所示。甲隊(duì)乙隊(duì)趙錢(qián)李王張孫蝶泳54.758.252.153.656.459.8仰泳62.263.458.256.559.761.5蛙泳69.170.565.367.868.471.3第43頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月解：分別用甲1、甲2和甲3表示甲隊(duì)中李姓健將不參加蝶泳、仰泳、蛙泳比賽的策略，分別用乙1、乙2和乙3表示乙隊(duì)中王姓健將不參加蝶泳、仰泳、蛙泳比賽的策略。當(dāng)甲隊(duì)采用策略甲1，乙隊(duì)采用策略乙1時(shí)，在100米蝶泳中，甲隊(duì)中趙獲第一、錢(qián)獲第三得6分，乙隊(duì)中張獲第二，得3分；在100米仰泳中，甲隊(duì)中李獲第二，得3分，乙隊(duì)中王獲第一，張獲第三，得6分；在100米蛙泳中，甲隊(duì)中李獲第一，得5分，乙隊(duì)中王獲第二、張獲第三，得4分。也就是說(shuō)，對(duì)應(yīng)于策略（甲1，乙1），甲、乙兩隊(duì)各自的得分為(14,13).表9-9中給出了在全部策略下各隊(duì)的得分。第44頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月表9-9甲、乙兩隊(duì)采用不同策略的得分乙1乙2乙3甲1(14,13)(13,14)(12,15)甲2(13,14)(12,15)(12,15)甲3(12,15)(12,15)(13,14) 按照定理9.6，求最優(yōu)混合策略，就是求不等式約束(20)的可行解.寫(xiě)出相應(yīng)的LINGO程序，程序名：exam0908.lg4"第45頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月MODEL:1]sets:2]optA/1..3/:x;3]optB/1..3/:y;4]AXB(optA,optB):Ca,Cb;5]endsets6]data:7]Ca=1413128]131212第46頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月9]121213;10]Cb=13141511]14151512]151514;13]enddata14]Va=@sum(AXB(i,j):Ca(i,j)*x(i)*y(j));15]Vb=@sum(AXB(i,j):Cb(i,j)*x(i)*y(j));16]@for(optA(i):第47頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月17]@sum(optB(j):Ca(i,j)*y(j))<=Va);18]@for(optB(j):19]@sum(optA(i):Cb(i,j)*x(i))<=Vb);20]@sum(optA:x)=1;@sum(optB:y)=1;21]@free(Va);@free(Vb);END用LINGO軟件求解，得到第48頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月Feasiblesolutionfoundatiteration:3VariableValueVA12.50000VB14.50000X(1)0.5000000X(2)0.000000X(3)0.5000000Y(1)0.000000Y(2)0.5000000Y(3)0.5000000第49頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月即甲隊(duì)采用的策略是甲1、甲3方案各占50%,乙隊(duì)采用的策略是乙2、乙3方案各占50%,甲隊(duì)的平均得分為12.5分，乙隊(duì)的平均得分為14.5分。當(dāng)純對(duì)策的解不唯一時(shí)，也存在混合對(duì)策的平衡點(diǎn)。第50頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.9用混合對(duì)策方法求解例9.7。解：寫(xiě)出求不等式(20)的LINGO程序，程序名："ex0909.lg4“MODEL:1]sets:2]optA/1..2/:x;3]optB/1..2/:y;4]AXB(optA,optB):Ca,Cb;5]endsets第51頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月6]data:7]Ca=3-1-11;8]Cb=1-1-13;9]enddata10]Va=@sum(AXB(i,j):Ca(i,j)*x(i)*y(j));11]Vb=@sum(AXB(i,j):Cb(i,j)*x(i)*y(j));12]@for(optA(i):13]@sum(optB(j):Ca(i,j)*y(j))<=Va);14]@for(optB(j):第52頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月15]@sum(optA(i):Cb(i,j)*x(i))<=Vb);16]@sum(optA:x)=1;@sum(optB:y)=1;17]@free(Va);@free(Vb);END 計(jì)算得到混合對(duì)策的平衡點(diǎn)((2/3,1/3),(1/3,2/3)各自的贏得值為1/3. 從上述分析來(lái)看，二人常數(shù)和對(duì)策是非常數(shù)和對(duì)策的特例，因此也可以用求解非常數(shù)和對(duì)策的方法求解常數(shù)和對(duì)策。第53頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月例9.10用求解非常數(shù)和對(duì)策的方法求解例9.5解：寫(xiě)出相應(yīng)的LINGO程序，程序名：exam0910.lg4MODEL:1]sets:2]optA/1..3/:x;3]optB/1..3/:y;4]AXB(optA,optB):Ca,Cb;5]endsets第54頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月6]data:7]Ca=3515608]4558509]381470;10]Cb=65854011]55425012]628630;13]enddata第55頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月14]Va=@sum(AXB(i,j):Ca(i,j)*x(i)*y(j));15]Vb=@sum(AXB(i,j):Cb(i,j)*x(i)*y(j));16]@for(optA(i):17]@sum(optB(j):Ca(i,j)*y(j))<=Va);18]@for(optB(j):19]@sum(optA(i):Cb(i,j)*x(i))<=Vb);20]@sum(optA:x)=1;@sum(optB:y)=1;21]@free(Va);@free(Vb);END第56頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月計(jì)算結(jié)果如下（只保留有效部分）Feasiblesolutionfoundatiteration:12VariableValueVA45.00000VB55.00000X(1)0.000000X(2)1.000000X(3)0.000000Y(1)1.000000Y(2)0.000000Y(3)0.000000第57頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月 即局中人A采用第二種策略，贏得45萬(wàn)觀眾，局中人B采用第一種策略，贏得55萬(wàn)觀眾，與前面計(jì)算的結(jié)果相同。第58頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月§3n人合作對(duì)策初步

n人合作對(duì)策在理論上較為復(fù)雜，這里只用一些例子簡(jiǎn)單介紹n人合作對(duì)策的基本思想，和用LINGO軟件求解對(duì)策的方法。例9.11

甲有一匹馬，對(duì)他自己來(lái)說(shuō)，其價(jià)值為0,而對(duì)乙和丙（買(mǎi)主）來(lái)說(shuō)分別價(jià)值90和100個(gè)貨幣單位。試建立3人合作對(duì)策，使得每人的利益最大。第59頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月解：設(shè)甲、乙、丙三人的價(jià)值分別為x1,x2,x3,因此對(duì)于每個(gè)人來(lái)說(shuō)，其價(jià)值為0，即v{1}=v{2}=v{3}=0 如果甲與乙合作，其價(jià)值為90，甲與丙合作，其價(jià)值為100，若乙與丙合作，其價(jià)值仍為0，因此有v{1,2}=90,v{1,3}=100,v{2,3}=0.但三人合作的總價(jià)值為100，即v{1,2,3}=100.建立相應(yīng)的數(shù)學(xué)規(guī)劃問(wèn)題第60頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月第61頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月寫(xiě)出相應(yīng)的LINGO程序，程序名：exam0909.lg4MODEL:1]sets:2]condition/1..3/:b;3]players/1..3/:x;4]constraint(condition,players):A;5]endsets6]data:7]A=110第62頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月8]1019]011;10]b=901000;11]total=100;12]enddata13]max=z;14]@for(players:z<=x);15]@for(condition(i):16]@sum(players(j):A(i,j)*x(j))>=b(i));17]@sum(players:x)<=total;END第63頁(yè)，課件共69頁(yè)，創(chuàng)作于2023年2月經(jīng)計(jì)算得到（只保留有用部分）Globaloptimalsolutionfoundatiteration:8Objectivevalue:0.000000Variable ValueReducedCostTOTAL 100.00000.000000Z 0.0000000.000000X(1) 90.000000.000000X(2) 0.0000000.000000