運(yùn)籌學(xué)實(shí)驗(yàn)與案例指導(dǎo) 課件 第8-10章 圖與網(wǎng)絡(luò)分析實(shí)驗(yàn)、排隊(duì)論實(shí)驗(yàn)、博弈論實(shí)驗(yàn)

第8章圖與網(wǎng)絡(luò)分析實(shí)驗(yàn)8.1基礎(chǔ)知識(shí)8.2使用Lingo軟件求解圖與網(wǎng)絡(luò)分析問題8.3使用WinQSB軟件求解圖與網(wǎng)絡(luò)分析問題8.4使用MATLAB軟件求解圖與網(wǎng)絡(luò)分析問題8.1基礎(chǔ)知識(shí)圖與網(wǎng)絡(luò)分析作為運(yùn)籌學(xué)的分支，應(yīng)用范圍廣泛。其理論已成為研究經(jīng)濟(jì)管理、計(jì)算機(jī)科學(xué)、通信理論、自動(dòng)控制、系統(tǒng)控制和軍事科學(xué)等領(lǐng)域相關(guān)問題的重要數(shù)學(xué)手段。圖論起源于1736年瑞士著名數(shù)學(xué)家歐拉（Euler）解決的哥尼斯堡七橋問題。圖是對(duì)于實(shí)際問題的數(shù)學(xué)抽象，由一些點(diǎn)及連接這些點(diǎn)的邊所組成。圖與網(wǎng)絡(luò)分析這一分支通過研究圖與網(wǎng)絡(luò)的性質(zhì)，結(jié)合優(yōu)化知識(shí)，解決設(shè)計(jì)與管理中的實(shí)際問題。圖的基本概念無向圖：如果圖G是由點(diǎn)和邊（兩點(diǎn)之間的不帶箭頭的連線）所構(gòu)成的。有向圖：如果圖G是由點(diǎn)和?。▋牲c(diǎn)之間用箭頭表示方向的連線）所構(gòu)成的。簡(jiǎn)單圖：無環(huán)（邊e的兩個(gè)端點(diǎn)相重）、無多重邊（兩點(diǎn)之間的邊多于一條）的圖。鏈：圖G中一個(gè)以點(diǎn)和邊交替的序列,若滿足,

則稱之為G中一條連接點(diǎn)和點(diǎn)的鏈。若點(diǎn)與點(diǎn)相同，則稱為圈。連通圖：圖G中任意兩點(diǎn)之間至少有一條鏈，則稱為連通圖?；芈罚簣DG中的一條鏈，對(duì)

均有弧，則稱之為從點(diǎn)到點(diǎn)的一條

路；若點(diǎn)與點(diǎn)相同，則稱為回路。若回路中的各點(diǎn)都不相同，則稱為初等路。支撐子圖：給定一個(gè)圖G=(V,E)，如果圖G?=(V?,E?)，使V=V?及

，則稱圖G?是圖G

的一個(gè)支撐子圖。樹：無圈的連通圖稱為樹；樹的各條邊稱為樹枝。支撐樹：圖T=(V,E?)是圖G=(V,E)的支撐子圖，如果圖T=(V,E?)同時(shí)是樹圖，則稱圖T是圖

G的一個(gè)支撐樹。最小支撐樹問題及求解方法最小支撐樹：樹枝權(quán)重總和最小的支撐樹，稱為最小支撐樹。求解方法：破圈法：在賦權(quán)連通圖G中任選一個(gè)圈，從圈中去掉一條權(quán)重最大的邊，在余下的圖中重復(fù)上述過程，直到圖中沒有圈為止。避圈法（Kruskal

算法）：在賦權(quán)連通圖G中選擇一條權(quán)重最小的邊，之后從剩余的邊中再選擇權(quán)重最小的邊，要求所選的邊與已選的邊不構(gòu)成圈，重復(fù)上述步驟，直到選不出這樣的邊為止。最短路徑問題及求解方法最短路徑問題給定一個(gè)賦權(quán)有向圖D=(V,A)，為弧

的權(quán)重，設(shè)P是圖D中從點(diǎn)

到點(diǎn)

的一條路，定義路P的權(quán)重w(P)為路P中所有弧的權(quán)重之和。則最短路徑問題是指從點(diǎn)

到點(diǎn)

的所有路中，找一條權(quán)重最小的路，即

，稱

為從點(diǎn)

到點(diǎn)

的最短路徑。最短路徑問題的求解方法(Dijkstra算法)（1）標(biāo)注；（2）找出與點(diǎn)

相鄰的點(diǎn)中距離最小的一個(gè)點(diǎn)，標(biāo)注；（3）從已標(biāo)號(hào)的點(diǎn)出發(fā)，找出與這些點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)，標(biāo)注；（4）重復(fù)步驟（3），直到點(diǎn)

被標(biāo)號(hào)為止。網(wǎng)絡(luò)最大流問題及求解方法網(wǎng)絡(luò)最大流問題指的是在給定網(wǎng)絡(luò)D上找出流量v(f)為最大的一個(gè)可行流。網(wǎng)絡(luò)最大流問題的求解方法（Ford-Fulkerson算法）（1）從點(diǎn)開始標(biāo)號(hào)。逐段檢查從一個(gè)標(biāo)號(hào)但未檢查點(diǎn)到相鄰的未標(biāo)號(hào)點(diǎn)的弧上的流量：①若在弧上有，給標(biāo)號(hào)，成為標(biāo)號(hào)且已檢查點(diǎn)；②若在弧上有，給標(biāo)號(hào)，成為標(biāo)號(hào)且已檢查點(diǎn)；重復(fù)上述步驟，當(dāng)點(diǎn)被標(biāo)號(hào)，表明得到一條從點(diǎn)到點(diǎn)的增廣鏈，轉(zhuǎn)入第②步調(diào)整過程。若所有標(biāo)號(hào)都是已檢查過的，而標(biāo)號(hào)過程進(jìn)行不下去，則算法結(jié)束。（2）按點(diǎn)及其第一個(gè)標(biāo)號(hào)，用反向追蹤的方法，找出增廣鏈。最小費(fèi)用最大流問題及求解方法最小費(fèi)用最大流問題給定網(wǎng)絡(luò)D=(V,A,C)，已知每一條弧的容量和單位流量費(fèi)用，尋找一個(gè)最大流f

，使流的總輸送費(fèi)用最小。最小費(fèi)用最大流問題的求解方法（1）從可行流開始，通常在第步得到最小費(fèi)用流。（2）構(gòu)造賦權(quán)有向圖，在中尋求從點(diǎn)到點(diǎn)

的最短路徑。（3）若不存在最短路徑，則為最小費(fèi)用最大流；若存在最短路徑，則在原網(wǎng)絡(luò)D中得到相應(yīng)的增廣鏈。（4）在增廣鏈上對(duì)做流量調(diào)整，可得新的可行流，再對(duì)進(jìn)行步驟（2）的操作。旅行商問題及求解方法旅行商問題旅行商問題是從給定的賦權(quán)圖中找出一個(gè)最小權(quán)(Hamilton圈)的問題。Hamilton圈指的是包含圖G的每個(gè)頂點(diǎn)的圈。旅行商問題的求解方法旅行商問題可以寫成整數(shù)規(guī)劃問題：8.2使用Lingo軟件求解圖與網(wǎng)絡(luò)分析問題例8.1用Lingo軟件求解所示網(wǎng)絡(luò)圖的最小支撐樹。model:sets:node/1..5/:v;edge(node,node):d,x;endsetsdata:d=0129999999999105299999250179999921069999999999760;enddata（1）打開Lingo軟件，在編輯窗口中輸入下列代碼：N=@size(node);min=@sum(edge:d*x);@for(node(k)|k#gt#1:@sum(node(i)|i#ne#k:x(i,k))=1;@for(node(j)|j#gt#1#and#j#ne#k:v(j)>=v(k)+x(k,j)-(n-2)*(1-x(k,j))+(n-3)*x(j,k);););@sum(node(j)|j#gt#1:x(1,j))>=1;@for(edge:@bin(x););@for(node(k)|k#gt#1:@bnd(1,v(k),99999);v(k)<=n-1-(n-2)*x(1,k););end（2）單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到結(jié)果。由求解結(jié)果可知，最小支撐樹由邊(v1,v2)、(v2,v4)、(v4,v3)、(v4,v5)組成，最小支撐樹的總長為10。該問題中有30個(gè)變量，而最優(yōu)解中只有其中的4個(gè)變量取非零值。從求解結(jié)果中尋找非零值較困難。我們可以選擇“LINGO”→“Solution”菜單命令彈出對(duì)話框，在“Attribute(s)orRowName(s)”下拉列表中選擇變量X，勾選“NonzeroVarsandBindingRowsOnly”復(fù)選框，然后單擊“OK”按鈕，則解報(bào)告中只顯示非零值最優(yōu)解。例8.2用Lingo軟件求解所示的從點(diǎn)s到點(diǎn)t的最小費(fèi)用最大流。（1）在編輯窗口中輸入下列代碼：model:sets:node/s,v1,v2,v3,t/:d;edge(node,node)/s,v1s,v2v1,v3v1,tv2,v1v2,v3v3,t/:b,c,f;endsetsdata:d=11000-11;b=4161232;c=108275104;enddatamin=@sum(edge:b*f);@for(node(i)|i#ne#1#and#i#ne#@size(node):@sum(edge(i,j):f(i,j))-@sum(edge(j,i):f(j,i))=d(i));@sum(edge(i,j)|i#eq#1:f(i,j))=d(1);@for(edge:@bnd(0,f,c));end（2）單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到結(jié)果。由求解結(jié)果可知，(s,v1)的流量為3，(s,v2)的流量為8，(v1,v3)的流量為0，(v1,t)的流量為7，(v2,v1)的流量為4，(v2,v3)的流量為4，(v3,t)的流量為4。最小費(fèi)用為55。例8.3（旅行商問題）一位游客從A城市出發(fā)，去往B、C、D和E四個(gè)城市旅游，最后返回A城市，各城市之間的距離如表所示。問該游客如何安排出游路線可以使總行程最短？各城市之間的距離單位：km（1）在編輯窗口中輸入下列代碼：model:sets:city/A,B,C,D,E/:c;line(city,city):d,x;endsetsdata:d=013517768130607067516005736777057020686736200;enddatan=@size(city);min=@sum(line:d*x);@for(city(k):@sum(city(i)|i#ne#k:x(i,k))=1;@sum(city(j)|j#ne#k:x(k,j))=1;);@for(line(i,j)|i#gt#1#and#j#gt#1#and#i#ne#j:c(i)-c(j)+n*x(i,j)<=n-1);@for(line:@bin(x));end（2）單擊“LINGO”菜單中的“Solve”選項(xiàng)或單擊工具欄中的按鈕，求解該模型，得到結(jié)果。（3）選擇“LINGO”→“Solution”菜單命令，彈出對(duì)話框，在“Attribute(s)orRowName(s)”下拉列表中選擇變量X，勾選“NonzeroVarsandBindingRowsOnly”復(fù)選框，然后單擊“OK”按鈕，顯示非零值解。8.3使用WinQSB軟件求解圖與網(wǎng)絡(luò)分析問題用WinQSB軟件求解圖與網(wǎng)絡(luò)分析問題時(shí)，需要調(diào)用“NetworkModeling”模塊，該模塊中有七個(gè)子塊，能求解網(wǎng)絡(luò)流問題、運(yùn)輸問題、分配問題、最短路徑問題、最大流問題、最小支撐樹問題和旅行商問題。WinQSB軟件求解網(wǎng)絡(luò)模型是基于表格的建模方式，且可以在圖上顯示求解結(jié)果（圖形解）。例8.4用WinQSB軟件求解所示網(wǎng)絡(luò)圖的最小支撐樹。（1）選擇“開始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話框，選擇問題的類型，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入節(jié)點(diǎn)間權(quán)重。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，得到結(jié)果。（4）選擇“Results”→“GraphicSolution”菜單命令，得到例8.4的最小支撐樹的網(wǎng)絡(luò)圖。由求解結(jié)果可知，最小支撐樹由邊(A,B)，(B,C)，(C,E)，(D,E)，(D,F)組成，最小支撐樹的總長為15。例8.5用WinQSB軟件求解下圖從點(diǎn)到點(diǎn)的最短路徑。（1）選擇“開始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話框，選擇問題的類型，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入節(jié)點(diǎn)間權(quán)重。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話框，選擇求解最短距離的起、訖點(diǎn)。（4）單擊“Solve”按鈕，得到結(jié)果。（5）選擇“Results”→“GraphicSolution”菜單命令，顯示點(diǎn)v1到各點(diǎn)的最短路徑的網(wǎng)絡(luò)圖。由求解結(jié)果可知，點(diǎn)v1到點(diǎn)v9的最短路徑為v1→v3→v6→v5→v9，最短距離是14。例8.6用WinQSB軟件求解下圖的網(wǎng)絡(luò)最大流。（1）選擇“開始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話框，選擇問題的類型，輸入問題的標(biāo)題和節(jié)點(diǎn)數(shù)，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入各邊容量。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話框，選擇出發(fā)點(diǎn)和終點(diǎn)。（4）單擊“Solve”按鈕，得到結(jié)果。（5）選擇“Results”→“GraphicSolution”菜單命令，顯示點(diǎn)s到點(diǎn)t的最大流量。由求解結(jié)果可知，(s,v1)的流量為7，(s,v2)的流量為7，(v1,v2)的流量為2，(v1,v3)的流量為5，(v2,v4)的流量為9，(v3,t)的流量為5，(v4,t)的流量為9，最大流量為14。例8.7（旅行商問題）一位游客從A城市出發(fā)，去往B、C、D和E四個(gè)城市旅游，最后返回A城市，各城市之間的距離如表所示。問該游客如何安排出游路線可以使總行程最短，

用WinQSB軟件求解。各城市之間的距離單位：km

（1）選擇“開始”→“程序”→“WinQSB”→“NetworkModeling”→“File”→“NewProblem”菜單命令，生成對(duì)話框，選擇問題的類型，輸入問題的標(biāo)題和城市個(gè)數(shù)，單擊“OK”按鈕。（2）選擇“Edit”→“NodeNames”菜單命令，彈出對(duì)話框，更改節(jié)點(diǎn)名，單擊“OK”按鈕，輸入各城市之間的距離。（3）選擇“SolveandAnalyze”→“SolvetheProblem”菜單命令，彈出對(duì)話框，選擇求解模型方法。（4）單擊“Solve”按鈕，得到結(jié)果。（5）選擇“Results”→“GraphicSolution”菜單命令，顯示該游客出游的最短路線的圖形。由求解結(jié)果可知該游客出游的最短路線為A→C→E→D→B→A，總行程為190km。8.4使用MATLAB軟件求解圖與網(wǎng)絡(luò)分析問題對(duì)于求解圖與網(wǎng)絡(luò)分析問題，MATLAB軟件優(yōu)化工具箱也沒有提供相應(yīng)的可直接調(diào)用的函數(shù)。本節(jié)通過編程用Kruskal算法求解最小支撐樹問題；用Dijkstra算法求解最短路徑問題；用Ford-Fulkerson算法求解網(wǎng)絡(luò)最大流問題。例8.8用MATLAB軟件求所示網(wǎng)絡(luò)圖的最小支撐樹。（1）創(chuàng)建一個(gè)新的“.m”文件，在編輯窗口中輸入下列代碼：function[x,f]=NETPexample1()b=[112233445;233445566;561572344];[B,i]=sortrows(b',3);B=B';m=size(b,2);n=6;t=1:n;k=0;T=[];c=0;fori=1:mift(B(1,i))~=t(B(2,i))k=k+1;T(k,1:2)=B(1:2,i);c=c+B(3,i);tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i)));forj=1:nift(j)==tmaxt(j)=tmin;endendendifk==n-1break;endendMinimal_Spanning_Tree=Ttotal_length=c（2）選擇“Debug”→“RunNETPexample1.m”菜單命令或單擊工具欄中的運(yùn)行按鈕，運(yùn)行程序，得到下面的結(jié)果。由求解結(jié)果可知，最小支撐樹由邊(A,B)，(B,C)，(C,E)，(D,E)，(D,F)組成，最小支撐樹的總長為15。例8.9用

MATLAB軟件求解下圖從點(diǎn)到點(diǎn)的最短路徑。（1）創(chuàng)建一個(gè)新的“.m”文件，在編輯窗口中輸入下列代碼：（2）選擇“Debug”→“RunNETPexample2.m”菜單命令或單擊工具欄中的運(yùn)行按鈕，運(yùn)行程序，得到下面的結(jié)果。由求解結(jié)果可知，點(diǎn)v1到點(diǎn)v9的最短路徑為v1→v3→v6→v5→v9，最短距離是14。例8.10用MATLAB軟件求解下圖的網(wǎng)絡(luò)最大流。（1）創(chuàng)建一個(gè)新的“.m”文件，在編輯窗口中輸入下列代碼：（2）選擇“Debug”→“RunNETPexample3.m”菜單命令或單擊工具欄中的運(yùn)行按鈕，運(yùn)行程序，得到下面的結(jié)果。由求解結(jié)果可知，(s,v1)的流量為7，(s,v2)的流量為7，(v1,v2)的流量為2，(v1,v3)的流量為5，(v2,v4)的流量為9，(v3,t)的流量為5，(v4,t)的流量為9，最大流量為14。第9章排隊(duì)論實(shí)驗(yàn)基礎(chǔ)知識(shí)使用Lingo軟件求解排隊(duì)論問題使用WinQSB

軟件求解排隊(duì)論問題基礎(chǔ)知識(shí)

在日常生活中經(jīng)常遇到排隊(duì)現(xiàn)象，如乘公共汽車、到醫(yī)院看病掛號(hào)。如果服務(wù)系統(tǒng)不能滿足要求的服務(wù)數(shù)量，就會(huì)產(chǎn)生排隊(duì)現(xiàn)象。若增加服務(wù)設(shè)施，就會(huì)增加投資或發(fā)生空閑浪費(fèi)；若服務(wù)設(shè)施太少，排隊(duì)現(xiàn)象就會(huì)嚴(yán)重，降低服務(wù)質(zhì)量，帶來不利影響。因此，管理人員面臨著既能降低成本，又可提高服務(wù)質(zhì)量的問題。排隊(duì)論也稱為隨機(jī)服務(wù)系統(tǒng)理論，它是研究如何才能既保證一定的服務(wù)質(zhì)量的指標(biāo)，又使服務(wù)設(shè)施費(fèi)用經(jīng)濟(jì)合理，恰當(dāng)?shù)亟鉀Q顧客排隊(duì)時(shí)間及設(shè)施服務(wù)費(fèi)用大小這對(duì)矛盾的一門學(xué)科。排隊(duì)論的基本構(gòu)成任何排隊(duì)過程都可以由圖9-1進(jìn)行描述，各個(gè)顧客由顧客總體出發(fā)，到達(dá)服務(wù)機(jī)構(gòu)前排隊(duì)等候接受服務(wù)，服務(wù)完畢即可離開。一般的排隊(duì)系統(tǒng)都有三個(gè)基本組成部分：輸入過程（指顧客來到排隊(duì)系統(tǒng)）、排隊(duì)規(guī)則和服務(wù)機(jī)構(gòu)。各部分的特征如下所述?；A(chǔ)知識(shí)

輸入過程。輸入過程描述的是顧客到達(dá)排隊(duì)系統(tǒng)，可能有下列各種不同情形：①顧客總體的組成是有限的也可能是無限的。②顧客到達(dá)的類型是單個(gè)到達(dá)，也可能是成批到達(dá)。③顧客相繼到達(dá)的時(shí)間間隔是確定型的，也可能是隨機(jī)型的。④顧客的到達(dá)可以是相互獨(dú)立的，即以前的到達(dá)情況對(duì)以后顧客的到來沒有影響，否則就是有關(guān)聯(lián)的。⑤輸入過程可以是平穩(wěn)的，是指描述相繼到達(dá)的時(shí)間間隔分布和所含參數(shù)都是與時(shí)間無關(guān)的，否則為非平穩(wěn)的。排隊(duì)規(guī)則。排隊(duì)規(guī)則是指顧客按照規(guī)定的次序接受服務(wù)。常見的有等待制和損失制。當(dāng)一個(gè)顧客到達(dá)時(shí)所有服務(wù)臺(tái)都不空閑，則該顧客排隊(duì)等待直到得到服務(wù)后離開，稱為等待制。在等待制中，可以是先到先服務(wù)，即按到達(dá)次序接受服務(wù)，如排隊(duì)買票；也有后到先服務(wù)，如乘坐電梯的顧客常是后入先出的；也有隨機(jī)服務(wù)，如電話服務(wù)；也有有優(yōu)先權(quán)的服務(wù)，如危重病人可優(yōu)先看病。當(dāng)一個(gè)顧客到來時(shí)，所有服務(wù)臺(tái)都不空閑，則該顧客立即離開不等待，稱為損失制。服務(wù)機(jī)構(gòu)。服務(wù)機(jī)構(gòu)主要包括一個(gè)或多個(gè)服務(wù)臺(tái)；在有多個(gè)服務(wù)臺(tái)的情形中，它們可以是并列的也可以是串聯(lián)的；服務(wù)方式可以是對(duì)單個(gè)顧客進(jìn)行的，也可以是對(duì)成批顧客進(jìn)行的；服務(wù)時(shí)間可以分為確定型的和隨機(jī)型的基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

基礎(chǔ)知識(shí)

使用Lingo軟件求解排隊(duì)論問題

使用Lingo軟件求解排隊(duì)論問題

model:lp=8;u=9;T=1/u;load=lp/u;S=1;Pwait=@PEB(load,S);W_q=Pwait*T/(S-load);L_q=lp*W_q;End使用Lingo軟件求解排隊(duì)論問題

使用Lingo軟件求解排隊(duì)論問題

model:min=S;lp=480;u=20;load=lp/u;Plost=@PEL(load,S);Plost<=0.05;lpe=lp*(1-Plost);L_s=lpe/u;eta=L_s/S;@gin(S);End使用WinQSB軟件求解排隊(duì)論問題

用WinQSB

軟件求解排隊(duì)論問題時(shí)需調(diào)用“QueuingAnalysis”模塊（用于排隊(duì)分析）和“QueuingSystemSimulation”模塊（用于排隊(duì)系統(tǒng)隨機(jī)模擬）。實(shí)驗(yàn)?zāi)康模?）熟悉WinQSB

軟件求解M/M/1/∞模型和M/M/S/S模型的方法。（2）通過用WinQSB

軟件求解排隊(duì)論問題，進(jìn)一步理解該問題的理論知識(shí)。實(shí)驗(yàn)內(nèi)容例9.3用WinQSB

軟件求解例9.1。使用WinQSB軟件求解排隊(duì)論問題

（1）選擇“WinQSB”→“QueuingAnalysis”→“File”→“NewProblem”菜單命令，生成對(duì)話框（見圖9-2），時(shí)間單位（TimeUnit）改為“hour”，格式輸入（EntryFormat）選擇“SimpleM/MSystem”，單擊“OK”按鈕。（2）彈出數(shù)據(jù)輸入窗口（見圖9-3），輸入相應(yīng)數(shù)據(jù)。（3）選擇“SolveandAnalyze”→“SolvethePerformance”菜單命令，得到運(yùn)行結(jié)果（見圖9-4）。圖9-2問題說明對(duì)話框圖9-3數(shù)據(jù)輸入窗口圖9-4運(yùn)行結(jié)果使用WinQSB軟件求解排隊(duì)論問題

圖9-5問題說明對(duì)話框使用WinQSB軟件求解排隊(duì)論問題

（2）彈出數(shù)據(jù)輸入窗口（見圖9-6），輸入相應(yīng)數(shù)據(jù)。（3）選擇“SolveandAnalyze”→“SolvethePerformance”菜單命令，得到運(yùn)行結(jié)果（見圖9-7）。由運(yùn)行結(jié)果可知，系統(tǒng)里有0個(gè)顧客，即系統(tǒng)空閑概率為57.1429%；系統(tǒng)里有1個(gè)顧客，即系統(tǒng)被占滿的概率為42.8571%。因此，系統(tǒng)的顧客損失率為42.8571%，即42.8571%的電話沒有接通。系統(tǒng)的有效到達(dá)率為0.3429，即真正進(jìn)入系統(tǒng)的電話平均為0.3429次/min。系統(tǒng)里平均顧客數(shù)為0.4286，即此電話系統(tǒng)里平均有0.4286個(gè)電話在使用。圖9-6數(shù)據(jù)輸入窗口圖9-7運(yùn)行結(jié)果使用WinQSB軟件求解排隊(duì)論問題

例9.5某雜貨店只有一名售貨員，已知顧客到達(dá)過程服從泊松流，已知平均到達(dá)率為每小時(shí)20人，不清楚這個(gè)系統(tǒng)的服務(wù)時(shí)間服從什么分布，但從統(tǒng)計(jì)分析知道，售貨員平均服務(wù)一名顧客的時(shí)間為2min，服務(wù)時(shí)間的均方誤差為1.5min，求這個(gè)排隊(duì)系統(tǒng)的數(shù)量指標(biāo)。解該問題是一個(gè)M/G/1的排隊(duì)系統(tǒng)，其中平均3min到達(dá)1名顧客，每位顧客的平均服務(wù)時(shí)間是2min，均方誤差是1.5min。用WinQSB

軟件求解的步驟如下所示。（1）選擇“WinQSB”→“QueuingAnalysis”→“File”→“NewProblem”菜單命令，生成對(duì)話框（見圖9-8），時(shí)間單位（TimeUnit）改為“minute”，格式輸入（EntryFormat）選擇“GeneralQueuingSystem”，單擊“OK”按鈕。圖9-8問題說明窗口使用WinQSB軟件求解排隊(duì)論問題

（2）彈出數(shù)據(jù)輸入窗口（見圖9-9），雙擊窗口中“Servicetimedistribution”選項(xiàng)右邊的“Exponential”選項(xiàng)，彈出概率分布函數(shù)對(duì)話框（見圖9-10），選擇“General/Arbitrary”選項(xiàng)，單擊“OK”按鈕。圖9-9數(shù)據(jù)輸入窗口圖9-10概率分布函數(shù)對(duì)話框使用WinQSB軟件求解排隊(duì)論問題

（3）在數(shù)據(jù)輸入窗口中輸入相應(yīng)數(shù)據(jù)（見圖9-11）。（4）選擇“SolveandAnalyze”→“SolvethePerformance”菜單命令，得到運(yùn)行結(jié)果（見圖9-12）。由運(yùn)行結(jié)果可知，系統(tǒng)中平均等待顧客數(shù)為1.0417人，平均等待時(shí)間為3.125min。圖9-11輸入相應(yīng)數(shù)據(jù)圖9-12運(yùn)行結(jié)果第10章博弈論實(shí)驗(yàn)基礎(chǔ)知識(shí)

使用WinQSB求解二人零和有限博弈使用Lingo求解二人有限博弈基礎(chǔ)知識(shí)

博弈論(gametheory)，也稱對(duì)策論，是用數(shù)學(xué)方法研究理性決策者之間競(jìng)爭(zhēng)和合作的理論。博弈論是運(yùn)籌學(xué)的一個(gè)重要分支，在經(jīng)濟(jì)學(xué)、管理學(xué)、政治學(xué)、軍事學(xué)、生物學(xué)、心理學(xué)等學(xué)科中有廣泛的應(yīng)用。

博弈論按照局中人之間能否達(dá)成有約束力的協(xié)議，可以分為合作博弈和非合作博弈。本章只討論非合作博弈中的完全信息靜態(tài)博弈。完全信息是指參與博弈的每個(gè)局中人對(duì)所有其他局中人的特征、策略空間及支付函數(shù)有準(zhǔn)確的知識(shí)。靜態(tài)是指局中人同時(shí)選擇行動(dòng)，或者雖非同時(shí)行動(dòng)，但后行動(dòng)者不知道先行動(dòng)者采取了什么具體行動(dòng)。完全信息靜態(tài)博弈也稱為策略型博弈。策略型博弈及納什均衡

描述一個(gè)策略型博弈需要三個(gè)基本要素：局中人、策略、支付。

局中人(players)是博弈的參與人，是博弈的決策主體。局中人根據(jù)自己的偏好選擇自己的行動(dòng)使得自己的效用最大化。

策略(strategies)是指每個(gè)局中人在博弈中的行動(dòng)規(guī)則或者行動(dòng)指南。策略是局中人的一個(gè)完整的行動(dòng)方案，規(guī)定局中人在什么情況下采取什么樣的行動(dòng)。

支付(payoffs)是指局中人從各個(gè)策略組合中獲得的效用。一個(gè)策略組合確定了博弈的一種結(jié)果，而這種結(jié)果又決定了局中人的支付。因此，每個(gè)局中人的支付是策略組合的函數(shù)。

如果對(duì)于每一個(gè)策略組合，全體局中人的支付之和都為零，則稱此博弈為零和博弈，否則稱為非零和博弈。策略型博弈及納什均衡

我們用表示一個(gè)策略型博弈，其中有n個(gè)局中人參與，各個(gè)局中人的策略集為支付函數(shù)為

。如果策略組合滿足：對(duì)每個(gè)局中人i,是針對(duì)其他參與人策略的最優(yōu)反應(yīng)策略，即對(duì)任意有則稱策略組合是該博弈的一個(gè)純策略納什均衡。策略型博弈及納什均衡

對(duì)任意局中人i,假設(shè)其有mi個(gè)純策略，記其策略集為，稱Si上的一個(gè)概率分布xi為局中人i的一個(gè)混合策略，其中.局中人i的混合策略集記為.則稱策略組合是該博弈的一個(gè)混合策略納什均衡。如果策略組合滿足：對(duì)每個(gè)局中人i,對(duì)任意有

納什證明了任何非合作n人有限博弈都存在納什均衡。二人零和有限博弈的求解

設(shè)G是二人零和有限博弈，局中人1,2的策略集分別為,.設(shè)在策略組合中，局中人1獲得的支付為，則局中人1的支付函數(shù)可以寫成矩陣的形式.由于博弈G是零和的，局中人2的支付矩陣為-A.因此，二人零和有限博弈可以記為.二人零和有限博弈也稱為矩陣博弈。如果存在,使得則策略組合是該博弈的一個(gè)純策略納什均衡?；旌喜呗越M合是矩陣博弈的納什均衡當(dāng)且僅當(dāng)稱為博弈的值，記為vG.二人零和有限博弈的求解

而上式成立又等價(jià)于，存在數(shù)v使得是不等式組的解，且是不等式組的解。這樣求矩陣博弈的均衡就可以轉(zhuǎn)化為解不等式組。二人零和有限博弈的求解

考慮如下兩個(gè)線性規(guī)劃問題：和問題(P)和(D)是互為對(duì)偶的線性規(guī)劃問題，由線性規(guī)劃對(duì)偶理論知，問題(P)和(D)分別存在最優(yōu)解

和，且

.為博弈G的納什均衡，且博弈的值為.進(jìn)一步，做變換(不妨設(shè),否則可在支付矩陣A的每個(gè)元素上都加上一個(gè)足夠大的正數(shù)d,博弈的均衡不會(huì)變)二人零和有限博弈的求解

考慮兩個(gè)互為對(duì)偶的線性規(guī)劃問題和若

和分別是線性規(guī)劃問題

和的的最優(yōu)解，記

則為博弈G的納什均衡，且博弈的值為

二人非零和有限博弈的求解

設(shè)G是二人零和有限博弈，局中人1,2的策略集分別為,.局中人1和局中人2的支付矩陣分別為.二人非零和有限博弈也稱為雙矩陣博弈，記作.如果存在,使得則策略組合是該博弈的一個(gè)純策略納什均衡。混合策略組合是雙矩陣博弈的納什均衡當(dāng)且僅當(dāng)二人非零和有限博弈的求解

求解雙矩陣博弈的納什均衡可以轉(zhuǎn)化為求如下二次規(guī)劃問題的最優(yōu)解。若

是是該二次規(guī)劃的最優(yōu)解，則

為G的納什均衡，且使用WinQSB求解二人零和有限博弈

WinQSB只能夠求解二人零和有限博弈，利用“DecisionAnalysis”模塊可建立二人零和博弈模型并求解。只需要輸入局中人的策略個(gè)數(shù)和支付矩陣，就可以求解得到問題的納什均衡。

例13.1田忌賽馬是發(fā)生在我國戰(zhàn)國時(shí)期的故事。當(dāng)時(shí)，齊王和田忌賽馬，雙方各出三匹馬，分別為上等馬、中等馬、下等馬各一匹。雙方約定，每次選一匹馬來比賽，輸者付給勝者1千兩黃金。不同等級(jí)的馬相差非常懸殊，而同等級(jí)的馬，齊王的比田忌的都要強(qiáng)。求解田忌賽馬問題的一個(gè)納什均衡。

在該問題中，齊王和田忌均有六個(gè)策略：(上中下)、(上下中)、(中上下)、(中下上)、(下中上)、(下上中)。記齊王為局中人1，田忌為局中人2，則齊王的支付矩陣為：使用WinQSB求解二人零和有限博弈

利用WinQSB求解二人零和有限博弈的具體步驟如下。(1)啟動(dòng)程序，選擇“DecisionAnalysis”模塊。單擊“開始→程序→WinQSB→DecisionAnalysis”。(2)建立新問題。單擊“File→NewProblem”，出現(xiàn)新建問題對(duì)話框。在該對(duì)話框中，ProblemType選擇Two-player,Zero-sumGame，再依次輸入問題標(biāo)題，局中人1的策略個(gè)數(shù)6，局中人2的策略個(gè)數(shù)6。單擊“OK”生成問題輸入界面。(3)輸入數(shù)據(jù)。在表格中輸入支付矩陣(4)求解并顯示結(jié)果。單擊“SolveandAnalyze→SolvetheProblem”，得到求解結(jié)果。使用WinQSB求解二人零和有限博弈

由輸出結(jié)果知，找到該問題的一個(gè)混合策略納什均衡此時(shí)齊王的期望支付為1，即博弈的值.使用WinQSB求解二人零和有限博弈

例13.2

兩個(gè)人互相獨(dú)立地從1、2、3這三個(gè)數(shù)字中任意選擇一個(gè)數(shù)字。如果二人所寫數(shù)字之和為偶數(shù)，則局中人2付給局中人1數(shù)量為此和數(shù)的報(bào)酬；如果二人所寫數(shù)字之和為奇數(shù)，則局中人1付給局中人2數(shù)量為此和數(shù)的報(bào)酬。求解此博弈的納什均衡。

在該問題中，局中人1和局中人2均有三個(gè)策略，策略集為,則局中人1的支付矩陣為：

按照例13.1的步驟，建立二人零和