運籌學(xué)基礎(chǔ)

1、運籌學(xué)基礎(chǔ),運籌學(xué)分析的主要步驟,發(fā)現(xiàn)和定義待研究的問題;構(gòu)造數(shù)學(xué)模型;尋找經(jīng)過模型優(yōu)化的結(jié)果;通過應(yīng)用這些結(jié)果對系統(tǒng)進行分折和改善系統(tǒng)的運行。,一、運籌學(xué)模型,數(shù)學(xué)建模：(Mathematical Modelling)把現(xiàn)實世界中的實際問題加以提煉，抽象為數(shù)學(xué)模型，求出模型的解，驗證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學(xué)知識的這一應(yīng)用過程稱為數(shù)學(xué)建模。,數(shù)學(xué)建模的幾個過程：,模型準備 ：了解問題的實際

2、背景，明確其實際意義，掌握對象的各種信息。用數(shù)學(xué)語言來描述問題。模型假設(shè) ：根據(jù)實際對象的特征和建模的目的，對問題進行必要的簡化，并用精確的語言提出一些恰當?shù)募僭O(shè)。模型建立 ：在假設(shè)的基礎(chǔ)上，利用適當?shù)臄?shù)學(xué)工具來刻劃各變量之間的數(shù)學(xué)關(guān)系，建立相應(yīng)的數(shù)學(xué)結(jié)構(gòu)。（盡量用簡單的數(shù)學(xué)工具）,模型求解 ：利用獲取的數(shù)據(jù)資料，對模型的所有參數(shù)做出計算（估計）。模型分析 ：對所得的結(jié)果進行數(shù)學(xué)上的分析。模型檢驗 ：將模型分析結(jié)果與實際情形進行

3、比較，以此來驗證模型的準確性、合理性和適用性。如果模型與實際較吻合，則要對計算結(jié)果給出其實際含義，并解釋。如果模型與實際吻合較差,則應(yīng)該修改假設(shè)，在次重復(fù)建模過程。模型應(yīng)用 ：應(yīng)用方式因問題的性質(zhì)和建模的目的而異。,二、線性規(guī)劃,生產(chǎn)計劃問題,設(shè)生產(chǎn)桌子x個，生產(chǎn)椅子y個（決策變量為2個）. 要達到銷售收入最大： Max z=50x＋30 y （目標函數(shù)）。 工時要求：4x＋3y ? 120, 2 x＋y ?

4、 50. （約束條件） 變量取值要求：x?0, y?0. （約束條件）。線性規(guī)劃模型為： max z = 50 x＋30 y s.t. 4 x＋3 y ? 120 2 x＋y ? 50 x ? 0, y ? 0.,線性規(guī)劃模型,線性規(guī)劃模型的結(jié)構(gòu)目標函數(shù) ：max，min約束條件：≥,=,≤變量符號：：≥0, or, ≤0線性規(guī)劃的標準形式目標函數(shù)：mi

5、n約束條件：=變量符號：≥0,數(shù)學(xué)規(guī)劃問題有三個組成部分：,1.有一組決策變量；2.有一個與決策變量有關(guān)的目標函數(shù)，并是決策變量的線性函數(shù)，需要解決max或min問題；3.有一組與決策變量有關(guān)的約束限制，用線性等式或線性不等式表示。,,,,,,,,,,,x2,x1,40,50,30,2x1+ x2 ? 50,20,10,10,20,30,4x1+3x2 ? 120,,z = 50x1+30x2= 600,,z = 50x1+

6、30x2= 900,z = 50x1+30x2= 1350,,,(15, 20),,,線性規(guī)劃的圖解,max z=x1+3x2s.t. x1+ x2≤6-x1+2x2≤8x1 ≥0, x2≥0,,,,,,,,,,,可行域,目標函數(shù)等值線,最優(yōu)解,6,4,-8,6,0,x1,x2,目標函數(shù)： Max z = 50 x1 + 100 x2 約束條件： s.t. x1 + x2

7、 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)得到最優(yōu)解： x1 = 50， x2 = 250 最優(yōu)目標值 z = 27500,,,

8、,,,,,,,,Z=36,圖解法的步驟,1.畫出直角坐標系。2.畫出可行域，即滿足約束條件的全部（x,y）點。3.對目標函數(shù)z給任意兩個常數(shù)，畫出兩條目標函數(shù)等值線，確定目標出函數(shù)的方向。沿這一方向，平移目標函數(shù)等值線到可行域的邊界，確定最優(yōu)解。4.求解過最優(yōu)解點的兩個約束等式組成的線性方程組，求出最優(yōu)解的數(shù)值。5.代最優(yōu)解數(shù)值到目標出函數(shù)中，得出最優(yōu)值。,整數(shù)規(guī)劃問題的提出,例 某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量

9、、可獲利潤以及托運所受限制如表5－1：,問兩種貨物各托運多少箱，可使獲得的利潤為最大？,三、整數(shù)規(guī)劃,1. 整數(shù)規(guī)劃一般形式,解：設(shè)托運甲、乙兩種貨物x1，x2箱，用數(shù)學(xué)式可表示為：,2. IP問題的求解,此IP問題的最優(yōu)解(值)為：,LP問題的最優(yōu)解(值)為：,做圖分析例的最優(yōu)解(直觀),某決策問題的方案和狀態(tài)的收益表如下：,4.1 不確定型決策方法,四、決策分析,1. 悲觀準則（ max—min 準則）從每個方案中最差結(jié)果出發(fā)

10、，從中選擇最有利的方案 u（Ai）=min a i,j i =1,2,…,m j最優(yōu)方案是u（A i※）=max u（A i） i本例中是最優(yōu)方案是A1,,,,,2. 樂觀準則（ max—max 準則）從每個方案中最好的結(jié)果出發(fā)，從中選擇最有利的結(jié)果 u (Ai)

11、 = max ai,j j最優(yōu)方案是 Ai* ， u (Ai*) = max u(Ai) i 本例中最優(yōu)方案是 A 2 。,,,,,,,,,,,3. 折衷準則悲觀準則和樂觀準則的折衷.樂觀系數(shù)為 ?，悲觀系數(shù)為1－ ?. （0 ≤ ? ≤1）

12、 j j i本例中：? = 0.8最優(yōu)方案A2 .,4. 等可能準則（ Laplace 準則）每個狀態(tài)出現(xiàn)的可能性是相等的。對每個方案計算各種狀態(tài)

13、下的平均結(jié)果，再從中選擇最有利的方案。u (Ai*) = max u(Ai) 本例中最優(yōu)方案是 A1或A4 。,5. 遺憾準則（ min－max準則，后悔值準則） 若某種狀態(tài)下未被考慮，將出現(xiàn)遺憾或后悔。對可能導(dǎo)致后悔最小的方案進行選擇。 先列出后悔值矩陣：,,,,,,后悔值的評價標準 r(Ai)= max b i, j i = 1,2,…,m.

14、 j r(A i *)= min r (A i ) i最優(yōu)方案為 A 1 ， A 4 。,,用各準則進行決策后，可再進行分析和比較,4.2 風險型決策方法,在不確定型決策中，將外部環(huán)境分成若干狀態(tài)：s1,s2,…,sm，但各種狀態(tài)的信息不知道。在風險型決策中，同樣將環(huán)境分成若干狀態(tài)：s1,s2,…,sm ，但每一

15、種狀態(tài)出現(xiàn)的概率可以直接預(yù)測或間接預(yù)測出來，即對每一狀態(tài)si，知道出現(xiàn)的概率 p ( s i ) ( i = 1,2,…,m ), 再進行決策。,1. 概率最大原則,根據(jù)所給出狀態(tài)空間的概率分布，選擇出現(xiàn)概率最大的狀態(tài)進行決策。例：按概率最大原則：P(S2)=0.4, 應(yīng)選擇 A 3 。,2. 最大期望原則,最大期望值法則 求各備選方案的期望收益 E（ A i ），根據(jù)期望收益的最大者決定采用的方案。

16、在上例題中，按最大期望法則應(yīng)選擇 A 1 。,,3. 決策樹方法 利用期望值法，用樹形圖討論多階段決策。,(1) 決策樹 （1）決策點，一般用方形節(jié)點表示，并用字母區(qū)別。 決策點后的弧表示不同的決策方案，弧旁的數(shù)字表示方案所需成本費用。 （2）狀態(tài)點，一般用園形節(jié)點表示，并用字母區(qū)別。 狀態(tài)點后的弧表示不同的狀態(tài)，弧旁的數(shù)字表示對應(yīng)狀態(tài)出現(xiàn)的概率。 （3）結(jié)果點，一般用三角形表示。 結(jié)果點后標注

17、該結(jié)果的損益值。,(2)計算 用逆向倒推法，對每一個節(jié)點（包括決策點和狀態(tài)點）計算權(quán)值。 （1）對各狀態(tài)點，用期望值方法計算期望損益。 （2）對各決策點，對各方案的期望損益值扣去該方案所花費的成本后，按最大收益準則對該策點后的方案進行比較選擇。選擇后的損益值作為該決策點的權(quán)值；并對未選中的決策方案進行“剪枝”。 過程： 從結(jié)果點開始 狀態(tài)點期望值 決策點收益值

18、 “剪枝” 狀態(tài)點期望值 決策點收益值 “剪枝” …… 初始決策點收益值 “剪枝”,,,,,,,,,,在例4.6中，計算順序為：此時對方法2“剪枝”；此時對方案2“剪枝”。 最后結(jié)果，該開發(fā)公司應(yīng)參加投標；若中標，采用方法1進行研制開發(fā)；期望收益為4萬元。,,,,五、對策論,局中人策略集 S＝{a1

19、,a2,…..an}局勢（ai, bj)贏得函數(shù)零和對策贏得矩陣,博弈論例,A采取低價策略；B采取低價策略,運輸問題網(wǎng)絡(luò)圖,六、運輸問題,運輸問題的一般數(shù)學(xué)模型,,最小元素法（1）,最小元素法（2）,最小元素法（3）,最小元素法（4）,最小元素法（5）,最小元素法（6）,7.1 圖的基本概念,一、幾個例子,例1 是北京、上海等十個城市間的鐵路交通圖。與此類似的還有電話線分布圖、煤氣管道圖、航空路線圖等。,

20、七、圖論,例2 分別用點v1,v2,v3,v4,v5分別代表甲、乙、丙、丁、戊五支球隊。若有兩支球隊之間比賽過，就在相應(yīng)的點之間聯(lián)一條線，且這條線不過其他點。如下圖所示：,,v1,v2,v3,v4,v5,,,可知各隊之間的比賽情況如下：甲—— 乙、丙、丁、戊乙—— 甲、丙丙—— 甲、乙、丁丁—— 甲、丙、戊戊—— 甲、丁,,,,,,7.2 樹,（一）、定義 ： 一個無圈的連通圖,在五個城市之間架設(shè)電話線，要求

21、任兩個城市之間都可以相互通話（允許通過其他城市），并且電話線的根數(shù)最少。,,,,,,,,,,v1,v5,v2,v3,v4,用v1,v2,v3,v4,v5代表五個城市,如果在某兩個城市之間架設(shè)電話線,則在相應(yīng)的兩點之間聯(lián)一條邊,這樣一個電話線網(wǎng)就可以用一個圖來表示。顯然,這個圖必須是連通的,而且是不含圈的連通圖。如左圖所示。,（二）、圖的支撐樹,定義 設(shè)圖T=(V,E’) 是圖的支撐子圖，如果圖T=(V, E’) 是一個樹，則

22、稱T是G的一個支撐樹。,支撐樹的求解方法,破圈法,例 用破圈法求解圖的一個支撐樹,,,,,,,,,v1,v2,v3,v4,v5,e1,e2,e3,e4,e5,e6,e7,e8,,,,,,,,,,,,,,,,,這就得到了該圖的一個支撐樹。,避圈法,,,,,,,,,,v1,v2,v3,v4,v5,v6,e1,e2,e3,e4,e5,e6,e7,e8,e9,,,,,,,,,,,這就得到了該圖的一個支撐樹。,（三）、最小支撐樹,定義1

23、 給圖G=(V,E) ，對G中的每一條邊[vi,vj]，相應(yīng)地有一個數(shù)wij，則稱這樣的圖G為賦權(quán)圖，wij稱為邊[vi,vj]上的權(quán)。,1. 定義,定義2 如果T=(V,E’) 是G的一個支撐樹，稱E’中所有邊的權(quán)之和為支撐樹T的權(quán)，記為w(T)，即,最小支撐樹 如果支撐樹T*的權(quán)w(T*)是G的所有支撐樹的權(quán)中最小者，則稱T*是G的最小支撐樹(簡稱最小樹),即,2. 最小支撐樹的求法：,方法一

24、 避圈法 開始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈。,v3,v5,,,,,,,,,v1,v2,v4,v6,6,5,1,5,7,2,3,4,4,,,,,,,,,,,,這就得到了該圖的一個最小支撐樹。,方法二 破圈法 任取一個圈，從圈中去掉一條權(quán)最大的邊。在余下的圖中，重復(fù)這個步驟，一直到一個不含圈的圖為止，這時的圖便是最小樹。,

25、,,,,,,,,v1,v2,v3,v4,v5,v6,6,5,1,5,7,2,3,4,4,,,,,,,,,,,,,,這就得到了該圖的一個最小支撐樹。,7.3 最短路問題,一、最短路問題的提出,,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,例1,左圖為單行線交通網(wǎng)，弧旁數(shù)字表示通過這條單行線所需要的費用。求從v1出發(fā)到v8總費用最小的路

26、線。,,,如上圖所示的路線為最短路。,,,,二、求解方法: 狄克斯特拉算法 (Dijkstra , 1959),,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,2,1,6,6,10,4,10,4,2,3,2,3,6,(0,0),,(v1,1),,標號法，找起點已標號而終點未標號的最小值。,,,,,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,v7,v8,v9,1,3,2,

27、2,1,6,6,10,4,10,4,2,3,2,3,6,(0,0),,(v3,5),(v1,3),(v1,1),最后，找出v1到v8的最短路為：,(v4,11),,,(v2,6),,(v5,10),(v5,9),(v5,12),,,,,,例2,2,3,7,1,8,4,5,6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,求從1到8的最短路徑,八、指派問題,問題提出： 需要 n 個人完成 n 項工作, 每人只能完成一項,

28、 第 i 個人需耗時 cij 完成第 j 項工作, 求需要時間最少的指派方案。 令 xij 為指派變量，xij = 1 表示指派第 i 個人完成第 j 項工作； xij = 0 表示不指派第 i 個人完成第 j 項工作,指派問題模型:,求解指派問題的匈牙利法畫 n ? n 表, 將目標函數(shù)系數(shù)填入（稱此為指 派矩陣）;2從每行中找出最小系數(shù), 本行系數(shù)都減去該最小系數(shù); 再從每列中找出最小系數(shù), 本列系數(shù)都

29、減去該最小系數(shù);,進行試指派，以尋求最優(yōu)解（1）進行行檢驗從第一行開始逐行檢查，當遇到只含有一個未標注的 0 元素的一行時，就在該0 元素上標記△，這表示分配 △ 所在行的那個人擔任△ 那一列的那項工作。然后在該0 元素所在列的其它0 元素上標記 ?，以免對那個任務(wù)再進行分配。,（2）進行列檢驗 與行檢驗類似，從第一列開始逐列檢查，當遇到只含有一個未標注的 0 元素的一列時，就在該0 元素上標記△，并在該0 元素所在

30、行的其它0 元素上標記 ?。,重復(fù)進行上述列檢驗，直到每一列都沒有未標記的0 元素或至少有兩個未標記的0 元素為止。,（3）反復(fù)進行（1），（2）,例 有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如表1所示，問如何指派，才使總的消耗時間最少？,表 1,解： (1) 先對各行分別減去本行的最小元素，對列也如此，得：,-2,0,8,7,5,-4,11,0,10,4,-11,2,3,5,0,-4,0,1

31、1,5,6,-5,2,5,0,0,（2）進行試指派：進行行檢驗，從第一行開始，第一行只有一個 0 元素，標以符號△，對第一列的其它 0 元素標以 ? 號，其它類似。,△,?,△,△,?,△,因為每一行都標記了符號△，其各數(shù)正好等于4，所以的最優(yōu)指派方案:工人甲—A，乙—B，丙—D，丁—C。相應(yīng)的最小總時間為26。,練習：設(shè)有指派矩陣，求最優(yōu)指派方案,-7,5,0,2,0,2,-6,2,3,0,0,0,-7,0,5,5,7