第2章-線性規(guī)劃與單純形法-第7節(jié)課件

單純形法的矩陣描述設線性規(guī)劃問題可以用如下矩陣形式表示：目標函數(shù)maxz=CX

約束條件AX≤b非負條件X≥0將該線性規(guī)劃問題的約束條件加入松弛變量后，得到標準型：maxz=CX+0Xs

AX+IXs=bX，X

s≥0其中I是m×m單位矩陣。若以Xs為基變量，并標記成XB，可將系數(shù)矩陣（A，I）分為（B，N）兩塊。B是基變量的系數(shù)矩陣，N是非基變量的系數(shù)矩陣。并同時將決策變量也分為兩部分：相應地可將目標函數(shù)系數(shù)C分為兩部分：CB和CN，分別對應于基變量XB和非基變量XN，并且記作C=（CB,CN）若經(jīng)過迭代運算后，可表示為：線性規(guī)劃問題可表示為：將（2-2）式移項及整理后得到：令非基變量=0，由上式得到：7.1資源數(shù)量變化的分析資源數(shù)量變化是指資源中某系數(shù)br發(fā)生變化，即br′=br+Δbr。并假設規(guī)劃問題的其他系數(shù)都不變。這樣使最終表中原問題的解相應地變化為XB′=B-1(b+Δb)這里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最終表中檢驗數(shù)不變，故最優(yōu)基不變，但最優(yōu)解的值發(fā)生了變化，所以XB′為新的最優(yōu)解。新的最優(yōu)解的值可允許變化范圍用以下方法確定。新的最優(yōu)解的值可允許變化范圍用以下方法確定。例如求第1章例1中第二個約束條件b2的變化范圍。解：可以利用第1章例1的最終計算表中的數(shù)據(jù)：可計算Δb2：由上式，可得Δb2≥?4/0.25=?16，Δb2≥?4/0.5=?8，b2≤2/0.125=16。所以Δb2的變化范圍是［?8，16］；顯然原b2=16，加它的變化范圍后，b2的變化范圍是［8，32］。例7從表1-5得知第1章例1中，每設備臺時的影子價格為1.5元，若該廠又從其他處抽調(diào)4臺時用于生產(chǎn)產(chǎn)品Ⅰ，Ⅱ。求這時該廠生產(chǎn)產(chǎn)品Ⅰ，Ⅱ的最優(yōu)方案。

解：先計算B-1Δb,將結(jié)果反映到最終表1-5中，得表2-10。由于表2-10中b列有負數(shù)，故用對偶單純形法求新的最優(yōu)解。計算結(jié)果見表2-11。即該廠最優(yōu)生產(chǎn)方案應改為生產(chǎn)4件產(chǎn)品Ⅰ，生產(chǎn)3件產(chǎn)品Ⅱ，獲利z*=4×2+3×3=17(元)從表2.11看出x3=2，即設備還有2小時未被利用。7.2目標函數(shù)中價值系數(shù)cj的變化分析例8試以第1章例1的最終表表1-5為例。

設基變量x2的系數(shù)c2變化Δc2，在原最優(yōu)解不變條件下，確定Δc2的變化范圍。

解：這時表1-5最終計算表便成為表2-12所示。若保持原最優(yōu)解，從表2-12的檢驗數(shù)行可見應有

由此可得Δc2≥?3和Δc2≤1。

Δc2的變化范圍為?3≤Δc2≤1

即x2的價值系數(shù)c2可以在［0，4］之間變化，而不影響原最優(yōu)解。7.3增加一個變量xj例9分析在原計劃中是否應該安排一種新產(chǎn)品。以第1章例1為例。設該廠除了生產(chǎn)產(chǎn)品Ⅰ，Ⅱ外，現(xiàn)有一種新產(chǎn)品III。已知生產(chǎn)產(chǎn)品III，每件需消耗原材料A，B各為6kg，3kg，使用設備2臺時；每件可獲利5元。問該廠是否應生產(chǎn)該產(chǎn)品和生產(chǎn)多少?解：分析該問題的步驟是：(1)設生產(chǎn)產(chǎn)品II為x3′臺，其技術系數(shù)向量P3′=(2,6,3)T，然后計算最終表中對應x3′的檢驗數(shù)σ3′=c3′?CBＢ-1Ｐ3′=5?(1.5,0.125,0)(2,6,3)T=1.25＞0說明安排生產(chǎn)產(chǎn)品III是有利的。由于b列的數(shù)字沒有變化，原問題的解是可行解。但檢驗數(shù)行中還有正檢驗數(shù)，說明目標函數(shù)值還可以改善。(3)將x3′作為換入變量，x5作為換出變量，進行迭代，求出最優(yōu)解。計算結(jié)果見表2-13(b)，這時得最優(yōu)解：x1=1,x2=1.5，x3′=2?？偟睦麧櫈?6.5元。比原計劃增加了2.5元。7.4技術系數(shù)aij的變化例10分析原計劃生產(chǎn)產(chǎn)品的工藝結(jié)構(gòu)發(fā)生變化。仍以第1章例1為例，若原計劃生產(chǎn)產(chǎn)品Ⅰ的工藝結(jié)構(gòu)有了改進，這時有關它的技術系數(shù)向量變?yōu)镻1′=(2,5,2)T，每件利潤為4元，試分析對原最優(yōu)計劃有什么影響?解：把改進工藝結(jié)構(gòu)的產(chǎn)品Ⅰ看作產(chǎn)品Ⅰ′，設x1′為其產(chǎn)量。于是在原計算的最終表中以x1′代替x1，計算對應x1′的列向量。同時計算出x1′的檢驗數(shù)為c1′?CBB-1P1′=4?(1.5,0.125,0)(2,5,2)T=0.375將以上計算結(jié)果填入最終表x1′的列向量位置，得表2-14。可見x1′為換入變量，x1為換出變量，經(jīng)過迭代。得到表2-15表2-15表明原問題和對偶問題的解都是可行解。所以表中的結(jié)果已是最優(yōu)解。即應當生產(chǎn)產(chǎn)品Ⅰ′，3.2單位；生產(chǎn)產(chǎn)品Ⅱ，0.8單位。可獲利15.2元。靈敏度分析的步驟1.將參數(shù)的改變通過計算反映到最終單純形表中2.檢查原問題是否為可行解3.檢查對偶問題是否為可行解4.按下表所列情況進行處理五、增加一個約束條件相當于實際問題中增加一道工序，方法是：將原問題最優(yōu)解代入新增的約束條件，如滿足，則新增約束未起到限制作用，原最優(yōu)解不變，否則，將新增約束反映到最終單純形表中分析例仍然考慮第一章例1，若增加一道檢測程序，產(chǎn)品I每件檢測2小時，產(chǎn)品II每件檢測4小時，檢測程序每天能力為12小時，分析最優(yōu)生產(chǎn)方案解原問題最優(yōu)解，代入檢測工序的約束條件，因原問題最優(yōu)解不是本例最優(yōu)解檢測工序約束條件加松弛變量，得以為基變量，將上式反映到最終