1、運籌學(xué),靈敏度分析,價值系數(shù)C發(fā)生變化： m 考慮檢驗數(shù) j = cj - cri arij j = 1,2,n i = 1 1、若 ck 是非基變量的系數(shù)： 設(shè) ck 變化為 ck + ck k= ck + ck - cri arik = k+ ck 只要 k 0 ，即 ck - k ，則最優(yōu)解不變；否則，將最優(yōu)單純形表中的檢驗數(shù) k 用 k取代，繼續(xù)單純形法的表格計算。 例: Max Z = - 2x1 - 3x2 - 4x3 S.t. - x1 - 2x2 - x3 + x4 = - 3 - 2x1 + x2 - 3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5

2、 0,2、線性規(guī)劃問題的進一步研究（2.3）,進一步理解最優(yōu)單純性表中各元素的含義考慮問題 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,3.靈敏度分析,3、靈敏度分析,無防設(shè)，xj = 0 j = m+1, , n ; xi = bi i = 1 , , m 是基本可行解, 對應(yīng)的目標(biāo)函數(shù)典式為：z = -f + m+1xm+1+ nxn 以下是初始單

3、純形表： m m 其中：f = - ci bi j = cj - ci aij 為檢驗數(shù)。 向量 b = B-1 b i = 1 i = 1 A= p1, p2, , pn , pj = B-1 pj, pj = ( a1j , a2j , , amj )T ， j = m+1, , n,ci , bj發(fā)生變化 本段重點 增加一約束或變量及A中元素發(fā)生變化通過例題學(xué)會處理,對于表格單純形法，通過計算得到最優(yōu)單純形表。 應(yīng)能夠找到最優(yōu)基 B 的逆矩陣 B-1 ， B-1b 以及 B-1N，檢驗數(shù) j 等。,3.靈敏度分析,價值系數(shù)c發(fā)生變化： m 考慮檢驗數(shù) j = cj - cri arij

4、j =1,2,n i = 1,1. 若ck是非基變量的系數(shù)： 設(shè)ck變化為 ck + ck k= ck + ck -cri arik = k+ ck 只要 k 0 ,即 ck - k ，則 最優(yōu)解不變；否則，將最優(yōu)單純形表 中的檢驗數(shù) k 用 k取代，繼續(xù)單 純形法的表格計算。,3.靈敏度分析,例3.3: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0,3.靈敏度分析,例：最優(yōu)單純形表,從表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/

5、5 時，原最優(yōu)解不變。,3.靈敏度分析,2、若 cs 是基變量的系數(shù)： 設(shè) cs 變化為 cs + cs ，那么 j= cj -cri arij - ( cs + cs ) asj = j - cs asj ， i s,對所有非基變量，只要對所有非基變量 j 0 ，即 j cs asj ，則最優(yōu)解 不變；否則，將最優(yōu)單純形表中的檢驗數(shù) j 用 j取代，繼續(xù)單純形法的表格計算。 Maxj/asjasj0csMinj/asjasj0,3.靈敏度分析,例3.4: Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5,s.t. x1 + 2x2 + x3 = 8 4x1 + x4

6、 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0,3.靈敏度分析,例: 下表為最優(yōu)單純形表,考慮 基變量系數(shù)c2發(fā)生變化,從表中看到 j=cj-(c1a1j+c5 a5j+(c2+c2) a2j)j=3,4 可得到 -3c21時，原最優(yōu)解不變。,3.靈敏度分析,右端項 b 發(fā)生變化 設(shè)分量 br 變化為 br + br ，根據(jù)第1章的討論，最優(yōu)解的基變量 xB = B-1b，那么只要保持 B-1(b + b) 0 ，則最優(yōu)基不變，即基變量保持，只有值的變化；否則，需要利用對偶單純形法繼續(xù)計算。 對于問題 (LP) Max z = cT x s.t. Ax

7、 b x 0,3.靈敏度分析,最優(yōu)單純形表中含有 B-1=( aij ）i=1,m; j=n+1,n+m 那么 新的xi=(B-1b)i+brair i=1, m 。 由此可得，最優(yōu)基不變的條件是 Max -bi/airair0br Min-bi/airair0,3.靈敏度分析,例3.5: 上例最優(yōu)單純形表如下,3.靈敏度分析,0 0.25 0 這里 B-1 = -2 0.5 1 0.5 -0.125 0,各列分別對應(yīng) b1、b2、b3 的單一變化 因此，設(shè) b1 增加 4，則 x1 ,x5 ,x2 分別變?yōu)椋?4+04=4, 4+(-2)4=-40, 2+0.54=4 用對偶單純形法進一步求

8、解，可得： x* = ( 4, 3, 2, 0, 0 )T f* = 17,3.靈敏度分析,增加一個變量 增加變量 xn+1 則有相應(yīng)的pn+1 ,cn+1 。 那么 計算出B-1pn+1 , n+1=cn+1-cri ari n+1 填入最優(yōu)單純形表, 若 n+1 0 則 最優(yōu)解不變； 否則，進一步用單純形法求解。,3.靈敏度分析,例3.6: 例3.4增加x6 , p6=( 2, 6, 3 )T, c6=5 計算得到,用單純形法進一步求解，可得： x* = ( 1,1.5,0,0,0,2 )T f* = 16.5,3.靈敏度分析,增加一個約束 增加約束一個之后，應(yīng)把最優(yōu)解帶 入新的約束，若滿

9、足則最優(yōu)解不變，否則 填入最優(yōu)單純形表作為新的一行，引入一 個新的非負變量（原約束若是小于等于形 式可引入非負松弛變量，否則引入非負人 工變量），并通過矩陣行變換把對應(yīng)基變 量的元素變?yōu)?，進一步用單純形法或?qū)?偶單純形法求解。,3.靈敏度分析,例3.7: 例3.4增加3x1+ 2x215，原最優(yōu)解不 滿足這個約束。于是,3.靈敏度分析,經(jīng)對偶單純形法一步，可得最優(yōu)解為（3.5, 2.25, 0, 0, 3, 2 )T，最優(yōu)值為 13. 75,A中元素發(fā)生變化(只討論 N 中某一列 變化情況） 與增加變量 xn+1 的情況類似，假設(shè) pj 變化 。那么，重新計算出 B-1pj j = cj -

10、 cri ari j 填入最優(yōu)單純形表，若 j 0 則最 優(yōu)解不變；否則，進一步用單純形法求解。 （例子從略）,3.靈敏度分析,Chapter5 目標(biāo)規(guī)劃( Goal programming ),目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型 目標(biāo)規(guī)劃的圖解分析法 求解 方法 目標(biāo)規(guī)劃應(yīng)用舉例,本章主要內(nèi)容：,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,問題的提出： 目標(biāo)規(guī)劃是在線性規(guī)劃的基礎(chǔ)上，為適應(yīng)經(jīng)濟管理多目標(biāo)決策的需要而由線性規(guī)劃逐步發(fā)展起來的一個分支。 由于現(xiàn)代化企業(yè)內(nèi)專業(yè)分工越來越細，組織機構(gòu)日益復(fù)雜，為了統(tǒng)一協(xié)調(diào)企業(yè)各部門圍繞一個整體的目標(biāo)工作，產(chǎn)生了目標(biāo)管理這種先進的管理技術(shù)。目標(biāo)規(guī)劃是實行目標(biāo)管理的有效工具，它根據(jù)

11、企業(yè)制定的經(jīng)營目標(biāo)以及這些目標(biāo)的輕重緩急次序，考慮現(xiàn)有資源情況，分析如何達到規(guī)定目標(biāo)或從總體上離規(guī)定目標(biāo)的差距為最小。,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,例5.1 某企業(yè)計劃生產(chǎn)甲，乙兩種產(chǎn)品，這些產(chǎn)品分別要在A,B,C,D四種不同設(shè)備上加工。按工藝文件規(guī)定，如表所示。,問該企業(yè)應(yīng)如何安排計劃，使得計劃期內(nèi)的總利潤收入為最大？,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,解：設(shè)甲、乙產(chǎn)品的產(chǎn)量分別為x1，x2，建立線性規(guī)劃模型：,其最優(yōu)解為x14，x22，z14元,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,但企業(yè)的經(jīng)營目標(biāo)不僅僅是利潤，而且要考慮多個方面，如： 力求使利潤指標(biāo)不低于12元； 考慮到市場需求，甲、乙兩種產(chǎn)品的生產(chǎn)量需保持

12、1:1的比例； C和D為貴重設(shè)備，嚴格禁止超時使用； 設(shè)備B必要時可以加班，但加班時間要控制；設(shè)備A即要求充分利用，又盡可能不加班。,要考慮上述多方面的目標(biāo)，需要借助目標(biāo)規(guī)劃的方法。,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,線性規(guī)劃模型存在的局限性： 1）要求問題的解必須滿足全部約束條件，實際問題中并非所有約束都需要嚴格滿足。 2）只能處理單目標(biāo)的優(yōu)化問題。實際問題中，目標(biāo)和約束可以相互轉(zhuǎn)化。 3）線性規(guī)劃中各個約束條件都處于同等重要地位，但現(xiàn)實問題中，各目標(biāo)的重要性即有層次上的差別，同一層次中又可以有權(quán)重上的區(qū)分。 4）線性規(guī)劃尋求最優(yōu)解，但很多實際問題中只需找出滿意解就可以。,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,

13、目標(biāo)規(guī)劃怎樣解決上述線性規(guī)劃模型建模中的局限性？,1. 設(shè)置偏差變量，用來表明實際值同目標(biāo)值之間的差異。,偏差變量用下列符號表示：,d+超出目標(biāo)的偏差，稱正偏差變量 d-未達到目標(biāo)的偏差，稱負偏差變量,正負偏差變量兩者必有一個為0。 當(dāng)實際值超出目標(biāo)值時： d+0, d-=0; 當(dāng)實際值未達到目標(biāo)值時： d+=0, d-0; 當(dāng)實際值同目標(biāo)值恰好一致時： d+=0, d-=0; 故恒有d+d-=0,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,2. 統(tǒng)一處理目標(biāo)和約束。,對有嚴格限制的資源使用建立系統(tǒng)約束，數(shù)學(xué)形式同線性規(guī)劃中的約束條件。如C和D設(shè)備的使用限制。,對不嚴格限制的約束，連同原線性規(guī)劃建模時的目標(biāo)，均

14、通過目標(biāo)約束來表達。,1）例如要求甲、乙兩種產(chǎn)品保持1:1的比例，系統(tǒng)約束表達為： x1=x2。由于這個比例允許有偏差， 當(dāng)x1x2時，出現(xiàn)正偏差d+，即： x1-d+ =x2或x1x2-d+ =0,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,正負偏差不可能同時出現(xiàn)，故總有： x1x2+d-d+ =0,若希望甲的產(chǎn)量不低于乙的產(chǎn)量，即不希望d-0,用目標(biāo)約束可表為:,若希望甲的產(chǎn)量低于乙的產(chǎn)量，即不希望d0,用目標(biāo)約束可表為:,若希望甲的產(chǎn)量恰好等于乙的產(chǎn)量，即不希望d0,也不希望d-0用目標(biāo)約束可表為:,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,3）設(shè)備B必要時可加班及加班時間要控制，目標(biāo)約束表示為：,2）力求使利潤指標(biāo)不低

15、于12元，目標(biāo)約束表示為：,4）設(shè)備A既要求充分利用，又盡可能不加班，目標(biāo)約束表示為：,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,3. 目標(biāo)的優(yōu)先級與權(quán)系數(shù),在一個目標(biāo)規(guī)劃的模型中，為達到某一目標(biāo)可犧牲其他一些目標(biāo)，稱這些目標(biāo)是屬于不同層次的優(yōu)先級。優(yōu)先級層次的高低可分別通過優(yōu)先因子P1,P2,表示。對于同一層次優(yōu)先級的不同目標(biāo)，按其重要程度可分別乘上不同的權(quán)系數(shù)。權(quán)系數(shù)是一個個具體數(shù)字，乘上的權(quán)系數(shù)越大，表明該目標(biāo)越重要。,現(xiàn)假定：,第1優(yōu)先級P1企業(yè)利潤； 第2優(yōu)先級P2甲乙產(chǎn)品的產(chǎn)量保持1:1的比例 第3優(yōu)先級P3設(shè)備A,B盡量不超負荷工作。其中設(shè)備A的重要性比設(shè)備B大三倍。,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,

16、上述目標(biāo)規(guī)劃模型可以表示為：,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式,達成函數(shù),目標(biāo)約束,其中：gk為第k個目標(biāo)約束的預(yù)期目標(biāo)值， 和 為pl 優(yōu)先因子對應(yīng)各目標(biāo)的權(quán)系數(shù)。,目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型,用目標(biāo)規(guī)劃求解問題的過程：,明確問題，列出目標(biāo)的優(yōu)先級和權(quán)系數(shù),構(gòu)造目標(biāo)規(guī)劃模型,求出滿意解,滿意否？,分析各項目標(biāo)完成情況,據(jù)此制定出決策方案,N,Y,目標(biāo)規(guī)劃的圖解分析法,目標(biāo)規(guī)劃的圖解法：,適用兩個變量的目標(biāo)規(guī)劃問題，但其操作簡單，原理一目了然。同時，也有助于理解一般目標(biāo)規(guī)劃的求解原理和過程。,圖解法解題步驟：,1. 將所有約束條件（包括目標(biāo)約束和絕對約束，暫不考慮正負偏差變量

17、）的直線方程分別標(biāo)示于坐標(biāo)平面上。 2. 確定系統(tǒng)約束的可行域。 3. 在目標(biāo)約束所代表的邊界線上，用箭頭標(biāo)出正、負偏差變量值增大的方向,目標(biāo)規(guī)劃的圖解分析法,3. 求滿足最高優(yōu)先等級目標(biāo)的解 4. 轉(zhuǎn)到下一個優(yōu)先等級的目標(biāo)，再不破壞所有較高優(yōu)先等級目標(biāo)的前提下，求出該優(yōu)先等級目標(biāo)的解 5. 重復(fù)4，直到所有優(yōu)先等級的目標(biāo)都已審查完畢為止 6. 確定最優(yōu)解和滿意解。,目標(biāo)規(guī)劃的圖解分析法,例5.2 用圖解法求解下列目標(biāo)規(guī)劃問題,目標(biāo)規(guī)劃的圖解分析法,(a),(b),(c),(d ),x2,x1,(e),(f),d1-,d1+,d2+,d2-,d3-,d3+,d4-,d4+,滿意解(3,3),0

18、,4,6,8,3,4,6,2,2,目標(biāo)規(guī)劃的圖解分析法,x1,x2,(a),(b),d1+,d1-,(c),d2-,d2+,(d),d3-,d3+,G,D,滿意解是線段GD上任意點,其中G點X(2,4),D點X(10/3,10/3),0,5.5,10,5,5.6,11,2,4,10/3,10/3,5,10,7,例5.3,目標(biāo)規(guī)劃的圖解分析法,O,x1,x2,20,40,60,50,20,40,60,50,a,b,d1-,d1+,d2-,d2+,c,d,d3-,d3+,d4-,d4+,(24,26),滿意解X=(24，26),例5.4,目標(biāo)規(guī)劃應(yīng)用舉例,例5.5 已知一個生產(chǎn)計劃的線性規(guī)劃模型如下，