確定型決策ppt課件

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

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

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

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

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

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

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

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

9、0.4x26,可令0.6x1+0.4x2+x4=6 。 注意注意：松弛變量、剩余變量在目標(biāo)函數(shù)中的價(jià)值系數(shù)為0。 (3)無約束變量。令xj = xj - xj”，xj,xj” 0，代入即可。 (4)變量xj0。令xj=- xj即可。 17;. 將下述問題化為標(biāo)準(zhǔn)型 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； 式加上一個(gè)松弛變量x4；式減去一個(gè)剩余變量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;. 圖解法圖解法比較簡單、直觀，適用于只有兩個(gè)變量的線性規(guī)劃問題。單純形法單純形法適用于兩個(gè)或兩個(gè)以上變量的線性規(guī)劃問題，比較復(fù)雜的問題需要借助計(jì)算機(jī)軟件求解。 19;.線性規(guī)劃解的概念線性規(guī)劃解的概念 設(shè)線性規(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ī)劃問題的一個(gè)基。為線性規(guī)劃問題的一個(gè)基。 取取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基解個(gè)數(shù)TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 個(gè)個(gè)基解：21;.5、基可行解 滿足式要求的基解。 如右圖所示，各邊交點(diǎn)O,QO,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4均為基可行解；而其延長線的交點(diǎn)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、可行基 基可行解對(duì)應(yīng)的B為可行基。可行解可行解基可行解基可行解非可行解非可行解基解基解22;. 圖解法圖

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坐標(biāo)；x2x1 (2)約束條件的幾何表示； Q1Q2Q3Q4 (3)目標(biāo)函數(shù)的幾何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx31321223;. 首先取z = 0，然后，使z逐漸增大，直至找到最優(yōu)解所對(duì)應(yīng)的點(diǎn)。* 可見，在Q2點(diǎn)z取到最大值。 因此， Q2點(diǎn)所對(duì)應(yīng)

15、的解為最優(yōu)解。 Q2點(diǎn)坐標(biāo)為(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* *時(shí)，解唯一，如上例。 (2)無窮多最優(yōu)解 對(duì)例1，若目標(biāo)函數(shù) z z = 2x2x1 1 + + 4x4x2 2，此時(shí)表示 目標(biāo)函數(shù)的直線與表示 條件的直線平行， 最優(yōu)點(diǎn)在線段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 。 即存在無界解。 在實(shí)際問題中，可能 是缺少約束條件。o2241x2x26;.(4)無可行解 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 無公共部分，無可行域。 即無可行解。 在實(shí)際問題中，可能是關(guān)系錯(cuò)。1124x1x227;. 單純形法單純形法 基本思路：基本思路：從可行域的一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)迭代求最優(yōu)解。 初始基可行解的確定初始基可行解的確定 1、松弛基（松弛變量對(duì)應(yīng)的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 化標(biāo)準(zhǔn)型 取x3、x4為基變量,令非基變量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA則系數(shù)矩陣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àn)與解的判別最優(yōu)性的檢驗(yàn)與解的判別 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111對(duì)于代入目標(biāo)函數(shù)為非基變量可行為基變量設(shè) , 1, , 1, 1 njjijiinjinxabxnjxmix30;.則njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )(

19、)(miijinjjjjmiiinaczzcbcZ110 , , 其中31;.解的判別：1. 若 ，則此時(shí)的基可行解為最優(yōu)解；2. 若存在某個(gè)非基變量 的檢驗(yàn)數(shù) ，且 ，則該線性規(guī)劃問題具有無界解（或稱無最優(yōu)解）；3. 若所有 ，又，對(duì)于某個(gè)非基變量 有 ，則該線性規(guī)劃問題具有無窮多最優(yōu)解。. .的檢驗(yàn)數(shù)為稱jjxkx0knjj, 1, 0 0kp0j0kkx32;. 為主元出基行對(duì)應(yīng)的變量則若、出基變量 0minmin02lkllklikikiiiiikikiiaxlabaabaab為入基變量。則，若、入基變量kkjjx 0max1 基變換基變換33;. 旋轉(zhuǎn)運(yùn)算（消元運(yùn)算）旋轉(zhuǎn)運(yùn)算（消元運(yùn)算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重復(fù)上面的步驟， 求出最優(yōu)解。34;. 單純形表單純形表 mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，設(shè)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;.