確定型決策ppt課件

1、小組成員： 鄭鄭 婕婕1;.確定型決策確定型決策 -確定型決策概述 -確定型決策應具備的條件 -確定型決策主要方法線性規(guī)劃法線性規(guī)劃法 -線性規(guī)劃法概述 -線性規(guī)劃法數學模型 -線性規(guī)劃法求解2;.確定型決策是指決策的自然狀態(tài)是一種既定的情況，即在已知未來可能發(fā)生的情況的條件下，根據每一個行動方案只能產生的唯一的結果，選擇最優(yōu)方案。自然狀態(tài)：指各種可行方案可能遇到的客觀情況和狀態(tài)。 例如：公司可以生產兩種產品1和2，生產產品1在銷量好的情況下獲利100萬，不好的情況下獲50萬，產品2在好的情況下獲利90萬，差的時候獲利60萬。3;.（1）存在著決策人希望達到的一個明確目標。（2）只存在一個確定

2、的自然狀態(tài)。（3）存在著可供選擇的兩個或兩個以上的行動方案。（4）不同的行動方案在確定狀態(tài)下的損失或利益值可以計算出來。 例如：某企業(yè)可向三家銀行借貸，但利率不同，分別為8%、7.5%、和8.5%。企業(yè)需決定向哪家銀行借款。很明顯，向利率最底的銀行借款為最佳方案。這就是確定型決策。此外，象企業(yè)中確定狀態(tài)下的庫存管理庫存管理，生產日程計劃生產日程計劃或設備計劃設備計劃的決策都屬于確定型決策。4;.（1）線性規(guī)劃法線性規(guī)劃法（2）直觀分析法（3）盈虧平衡分析方法（4）投資回收期法（5）排隊法 5;.線性規(guī)劃（Linear Programming),簡稱LP。線性規(guī)劃法產生于20世紀40年代，廣泛應

3、用于生產制造生產制造、物料分配物料分配、人力資源計人力資源計劃劃、運輸問題運輸問題和投資決策投資決策等方面。這種方法的本質是尋求如何使用有限的資源獲得最大的效果，或者用最小的成本完成一項既定的任務。通常是在一些線性等式或不等式的約束條件下，尋求目標函數的最優(yōu)值最優(yōu)值。6;.p 問題的提出問題的提出 例1 ：生產計劃問題 某公司可以生產兩種新產品，其主要數據如下表 所示。 問：產品、各生產多少件，使利潤最大？限制 設備臺時128臺時 材料A4016kg材料B0412kg利潤23 顯然，此問題是在設備可用時間和材料重量受到限制的情況下來尋求每周利潤最大化，其決策方案是決定產品一和產品二各自的產量為

4、多少才最佳？ 7;.線性規(guī)劃的幾個概念線性規(guī)劃的幾個概念（1）決策變量 變量 是運籌學問題或系統(tǒng)中待確定的某些量，在實際問題中常常把變量X叫決策變量。在例1中，就可以記x1為生產產品1的產量；x2為生產產品二的產量。（2）約束條件 求目標函極值時的某些限制稱為約束條件。在例1中，設備可用時間和材料重量的約束，全為“”的不等式約束。（3）目標函數 在例1中，生產計劃安排的“最優(yōu)化”要有一定的標準或評價方法，目標函數就是這種標準的數學描述，這里的目標要求生產的利潤為最大。Tnxxxx),(218;.根據上面的規(guī)定，例1的產品組合問題可抽象地歸結為一個數學模型，如下：限制 設備臺時128臺時 材料A

5、4016kg材料B0412kg利潤23目標函數： max z = 2x1 + 3x2約束條件： 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 9;.線性規(guī)劃的假定條件線性規(guī)劃的假定條件（1）比例性假定。意味著每種經營活動對目標函數的貢獻是一個常數，對資源的消耗也是一個常數。（2）可加性假定。每個決策變量對目標函數和約束方程的影響是獨立于其他變量的，目標函數值是每個決策變量對目標函數貢獻的總和。（3）連續(xù)性假定。決策變量應取連續(xù)值。（4）確定性假定。所有參數都是確定的參數，不包含隨機因素。 10;.線性規(guī)劃模型所需的數據線性規(guī)劃模型所需的數據資源單位活動對資源的使用量資源可

6、利用量12n1a11a12a1nb12a21a22a2nb2mam1am2amnbm單位活動對Z的貢獻c1c2cn11;.線性規(guī)劃的數學模型：線性規(guī)劃的數學模型：其中，目標函數可以是min的形式，函數約束中“”可以是“=”或“”，變量的非負性限制也可以取消。 0, 0, 0. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz12;.說明： (1)決策變量：x1，x2，xn 。 一組決策變量表示為問題的一個方案； (2)目標函數：max(min)z z為決策變量的線性函數; (3)約束條件 一

7、組線性不等式。cj為價值系數, bi為資源， aij為技術系數(i=1,m;j=1,n).13;.線性規(guī)劃的標準型線性規(guī)劃的標準型標準型標準型（z極大值，等式，b非負，x非負） njxmibxaxczjinjjijnjjj,10,1 max簡記11 ，：0,0,0.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz14;.用向量表示用向量表示 njxbxptscxzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapccccxxxx) , , , ( :) , , ,(

8、), , , ( ) , , , (:21212121 的系數列向量其中15;. 用矩陣描述為：用矩陣描述為： 其中: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 為系數矩陣 212222111211 mnmmnnaaaaaaaaaA njxbAxtscxzj, 1, 0 .max16;.標準型的化法標準型的化法 (1)minmax。 令z = -z即可。 (2)不等式。對于“”情況，在“”左邊加上一個松弛變量（非負），變?yōu)榈仁剑鐇14,可令x1+x3=4,則x30； 對于“”情況：在“”左邊減去一個剩余變量（非負），變?yōu)榈仁剑?.6x1+

9、0.4x26,可令0.6x1+0.4x2+x4=6 。 注意注意：松弛變量、剩余變量在目標函數中的價值系數為0。 (3)無約束變量。令xj = xj - xj”，xj,xj” 0，代入即可。 (4)變量xj0。令xj=- xj即可。 17;. 將下述問題化為標準型 min z = -x1+2x2-3x3 x1+ x2+ x3 7 x1- x2+ x3 2 -3x1+ x2+2x3 = 5 x1,x2 0，x3無約束 解：令x3 = x3-x3”，x3,x3” 0； 式加上一個松弛變量x4；式減去一個剩余變量x5； 令z = -z、； max z = x1- 2x2 + 3(x3 - x3”)

10、+ 0 x4 + 0 x5 x1 + x2 + (x3 - x3”) + x4 = 7 x1 - x2 + (x3 - x3”) - x5 = 2 -3x1 + x2 + 2(x3 - x3”) = 5 x1,x2,x3,x3”,x4,x5 0 18;. 圖解法圖解法比較簡單、直觀，適用于只有兩個變量的線性規(guī)劃問題。單純形法單純形法適用于兩個或兩個以上變量的線性規(guī)劃問題，比較復雜的問題需要借助計算機軟件求解。 19;.線性規(guī)劃解的概念線性規(guī)劃解的概念 設線性規(guī)劃為 maxmax z z = cx cx Ax Ax = b b x x 0 0 A A為為m m n n矩陣矩陣, , n n m,

11、 Rankm, Rank A A = m (Am (A為行滿秩矩陣）為行滿秩矩陣） 1 1、可行解：滿足條件、可行解：滿足條件、的的X X； 2 2、最優(yōu)解：滿足、最優(yōu)解：滿足條件條件的可行解；的可行解； 3 3、基：取、基：取B B為為A A中的中的m m m m子矩陣，子矩陣，RankRank B B = m m，則稱則稱B B為線性規(guī)劃問題的一個基。為線性規(guī)劃問題的一個基。 取取B B = (p(p1 1,p,p2 2, ,p,pm m) p) pj j = (a(a1j1j,a,a2j2j, ,a,amjmj) )T T 則稱則稱x x1 1,x,x2 2, ,x,xm m為基變量，其

12、它為非基變量。為基變量，其它為非基變量。20;.4 4、基解：取、基解：取B B = (p(p1 1,p,p2 2, ,p,pm m) ) a a1111, ,a,a1m1m x x1 1 a a1m+11m+1, ,a,a1n1n x xm+1m+1 b b1 1 + + = a am1m1, ,a,ammmm x xm m a amm+1mm+1, ,a,amnmn x xn n b bm m 基基 基變量基變量 非基非基 非基變量非基變量 令令 x xm+1m+1 = = x xn n = 0 (0 (非基變量為非基變量為0)0) 則則 BXBXB B = b b )!( !mnmnCm

13、n基解個數TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 個個基解：21;.5、基可行解 滿足式要求的基解。 如右圖所示，各邊交點O,QO,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4均為基可行解；而其延長線的交點Q5為基解，但不是基可行解。O(0,0)O(0,0)Q Q1 1(4,0)(4,0)Q Q2 2(4,2)(4,2)Q Q4 4(0,3)(0,3)Q Q3 3(2,3)(2,3)Q Q5 5(4,3)(4,3)6、可行基 基可行解對應的B為可行基?？尚薪饪尚薪饣尚薪饣尚薪夥强尚薪夥强尚薪饣饣?2;. 圖解法圖

14、解法 用圖解法求用圖解法求例例1 1。 max max z z = 2x2x1 1 + + 3x3x2 2 1x 1x1 1 + + 2x2x2 2 8 8 4x 4x1 1 16 16 4x4x2 2 12 12 x x1 1，x x2 2 0 0 解： (1)建立x x1 1 - - x x2 2坐標；x2x1 (2)約束條件的幾何表示； Q1Q2Q3Q4 (3)目標函數的幾何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx31321223;. 首先取z = 0，然后，使z逐漸增大，直至找到最優(yōu)解所對應的點。* 可見，在Q2點z取到最大值。 因此， Q2點所對應

15、的解為最優(yōu)解。 Q2點坐標為(4，2)。 即: x1 = 4，x2 = 2 由此求得最優(yōu)解：x x1 1* * = 4 x4 x2 2* * = 2 2 最大值：maxmax z z = z z* * = 2x2x1 1 + + 3x3x2 2 = 1414x2x1Q1Q2(4,2)Q3Q4*4324;.討論： (1)唯一最優(yōu)解 maxmax z z = z z* *時，解唯一，如上例。 (2)無窮多最優(yōu)解 對例1，若目標函數 z z = 2x2x1 1 + + 4x4x2 2，此時表示 目標函數的直線與表示 條件的直線平行， 最優(yōu)點在線段Q3Q2上。 即存在無窮多最優(yōu)解。x2x1Q1 Q2(

16、4,2)Q3(2,3)Q4o43*25;. (3)無界解 max z = 2x1 + 3x2 4x1 16 x1，x2 0 則x2 ，z 。 即存在無界解。 在實際問題中，可能 是缺少約束條件。o2241x2x26;.(4)無可行解 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 無公共部分，無可行域。 即無可行解。 在實際問題中，可能是關系錯。1124x1x227;. 單純形法單純形法 基本思路：基本思路：從可行域的一個頂點到另一個頂點迭代求最優(yōu)解。 初始基可行解的確定初始基可行解的確定 1、松弛基（松弛變量對應的B） max z = x1 +

17、 3x2 x1 + 2x2 3 2x1 + 3x2 4 x1,x2 0max z = x1 + 3x2 + 0 x3 + 0 x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 = 4 x1,x2,x3,x4 0 化標準型 取x3、x4為基變量,令非基變量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA則系數矩陣28;. 2、觀察法 max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 0 選

18、 XB = (x1 x4)T 令x2 = x3 = 0 則 初始基可行解：X(0) = (3 0 0 4)T B , 1 1 3 00 3 2 1 :414321ppppppA則解29;.最優(yōu)性的檢驗與解的判別最優(yōu)性的檢驗與解的判別 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111對于代入目標函數為非基變量可行為基變量設 , 1, , 1, 1 njjijiinjinxabxnjxmix30;.則njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )(

19、)(miijinjjjjmiiinaczzcbcZ110 , , 其中31;.解的判別：1. 若 ，則此時的基可行解為最優(yōu)解；2. 若存在某個非基變量 的檢驗數 ，且 ，則該線性規(guī)劃問題具有無界解（或稱無最優(yōu)解）；3. 若所有 ，又，對于某個非基變量 有 ，則該線性規(guī)劃問題具有無窮多最優(yōu)解。. .的檢驗數為稱jjxkx0knjj, 1, 0 0kp0j0kkx32;. 為主元出基行對應的變量則若、出基變量 0minmin02lkllklikikiiiiikikiiaxlabaabaab為入基變量。則，若、入基變量kkjjx 0max1 基變換基變換33;. 旋轉運算（消元運算）旋轉運算（消元運算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重復上面的步驟， 求出最優(yōu)解。34;. 單純形表單純形表 mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，設35;. 建立單純形表cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j 用單純形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 036;.