運籌學(xué)03單純形法的進一步討論人工變量法

1、復(fù)習(xí)：單純形法,,§5 單純形法的進一步討論: 人工變量法,人工變量法（確定初始可行基）：,原約束方程：AX=b,加入人工變量：xn+1，?，xn+m,人工變量是虛擬變量，加入原方程中是作為臨時基變量，經(jīng)過基變換，將人工變量均能換成非基變量，所得解是最優(yōu)解；若在最終表中檢驗數(shù)小于零，而且基變量中還有某個非零的人工變量，原問題無可行解。,,1、大M法方法：在約束條件中，加入人工變量后，要求目標(biāo)函數(shù)不受影響？目標(biāo)函數(shù)中人工變

2、量的系數(shù)?。?M）。,理由：目標(biāo)函數(shù)實現(xiàn)最大化，就必須將人工變量從基變量中換出，否則目標(biāo)函數(shù)就不可能取得最大化。,例1：用大M法求解如下線性規(guī)劃問題,,,,cj,最優(yōu)解是,目標(biāo)函數(shù)為-2。,,例4： max z=4x1+3x2 -3x1+2x2≤6 s.t. -x1+3x2≥3 x1, x2 ≥ 0,無可行解,2、兩階段法第一階段：建立一個輔助線性規(guī)劃并求解，以此判斷原線性規(guī)劃是

3、否存在可行解。輔助線性規(guī)劃問題：目標(biāo)函數(shù)取成所有的人工變量之和，并對目標(biāo)函數(shù)取極小化，約束條件依然為原問題的以單位矩陣作為可行基的標(biāo)準(zhǔn)型的約束條件。 所有人工變量都變成非基變量，目標(biāo)函數(shù)值為0，原問題存在基可行解。轉(zhuǎn)到第二階段。 若目標(biāo)函數(shù)值不為0，至少有一個人工變量不能從基變量中轉(zhuǎn)出，原問題沒有可行解。停止。第二階段：從第一階段最優(yōu)表格中去掉人工變量，將目標(biāo)函數(shù)系數(shù)換成原問題的目標(biāo)函數(shù)系數(shù)，用單純形法計算，直到得到最優(yōu)解為

4、止。,例2：同上,第一階段：求解輔助規(guī)劃問題,,,,,,,,cj,x6，x7是人工變量，第一階段求解的最優(yōu)結(jié)果是?=0，因此得最優(yōu)解為：,第二階段：取消人工變量，添入原問題目標(biāo)函數(shù)的系數(shù)，求解相應(yīng)的線性規(guī)劃。,最優(yōu)解為：,最優(yōu)值為： z= -2,兩階段法：?輔助規(guī)劃； ?去掉人工變量，單純形法。,對目標(biāo)函數(shù)求max的線性規(guī)劃問題,用單純形法計算步驟的框圖,用大M法和兩階段法求解以下問題,第二章 對偶理論與靈敏度分析,§

5、1 單純形法的矩陣描述 線性規(guī)劃 max z=CX max z=CX+OXs (1) AX≤b AX+IXs =b X≥0 X≥0, Xs

6、≥0其中 I 是m×m 單位矩陣，松弛變量Xs=( xn+1, xn+2,…,xn+m)T .設(shè)B是一個可行基矩陣，N表示非基變量的系數(shù)矩陣(A，I)→(B，N) 對應(yīng)決策變量,,約束條件,對應(yīng)目標(biāo)函數(shù)的價值向量,原線性規(guī)劃可改寫為,單純形表的幾個特征:1、檢驗數(shù): 非基變量的檢驗數(shù)(等于對應(yīng)的目標(biāo)系數(shù)) cj –zj=( CN–CBB-1N)j

7、 基變量的檢驗系數(shù)為零，即cj –zj= CB–CBB-1 B=0,進一步，非基底變量可分解XN →（XN1，Xs），其中 XN1 表示除去松弛變量以后的非基變量；Xs是松弛變量，其目標(biāo)系數(shù)為零。,Xs的檢驗數(shù)cj –zj=( 0–CBB-1)j= –CBB-1所有的檢驗數(shù)可用C–CBB-1A與–CBB-1表示,(B-1b)i是向量(B-1b)中的第i個元素， (B-1Pj)i是向量(B-1Pj)中的

8、第i個元素，j=1,2,…,n,2、θ規(guī)則的表達形式,,3、單純形表的矩陣表達形式,1）對應(yīng)初始單純形表中的單位矩陣I，迭代后的單純形表中為B-1；2）初始單純形表中基變量Xs=b，迭代后的表中變?yōu)閄B=B-1b；3）初始單純形表中的系數(shù)矩陣[A，I]=[B，N1，I]，迭代后的表中約束系數(shù)矩陣為： [B-1A，B-1I]=[B-1B，B-1N1，B-1I]=[I， B-1N1， B-1]；4）初始單純形表中變量