第二章 單純型法

第二章單純形法

線性規(guī)劃問題的矩陣表示 單純形表的結(jié)構(gòu)和性質(zhì)單純形表的運算初始基可行解的確定基可行解的判別和改進

非基變量基變量==1、線性規(guī)劃的矩陣表示===BNIIB-1b非基變量σ基變量σ=CBB-1B-CB=0=Z+(CBB-1N-CN)XN=CBB-1b

XB+B-1NXN=B-1b

Z+（CBB-1A-C）X=CBB-1b

B-1AX=B-1b

X右端ZCBB-1A-CCBB-1bXBB-1AB-1b基變量在目標函數(shù)中的系數(shù)等于0，基變量在約束條件中的系數(shù)是一個單位矩陣約束條件的右端B非負2、單純形表的結(jié)構(gòu)和性質(zhì)注意：Z行中有m個0，它們與基變量相對應。一般情況下，這m個0分散在Z行的各列中，并與基變量相對應。其余m行中有一個m階單位矩陣I，其各列與基變量相對應。一般情況下，組成I的各列分散在表的各列中，它們與基變量相對應。單純形表的結(jié)構(gòu)我們將用單純形表解決以下三個問題：如何找出第一個（初始的）基可行解？如何判斷這個初始基可行解是不是最優(yōu)解？如果不是，怎樣將它調(diào)整成一個“更好的”基可行解，以致最終求出最優(yōu)解？3、單純形表的運算當線性規(guī)劃問題的約束條件全為“小于等于約束”，并且右邊常數(shù)全部“大于等于0”，化標準問題時在每個約束中添加的松弛變量恰構(gòu)成一個單位矩陣，這單位矩陣可作為初始可行基。添加的松弛變量即為基變量，其他變量為非基變量。對于不能直接獲得初始可行基的問題，可以用引入人工變量的方法構(gòu)造一初始可行基。這將在“人工變量法”中作介紹。（1）初始基可行解的確定用檢驗數(shù)σj=Zj

–Cj

進行判斷，若所有檢驗數(shù)σj≤0，則X是最優(yōu)解。若存在某個檢驗數(shù)σj>0,它所對應的列向量全部分量為非正，則所給問題的目標函數(shù)值無下界，因而無最優(yōu)解。若存在σj>0,且它（們）所對應的列向量中都有正分量，則這時可進行基變換。（2）基可行解的判別和改進若存在σj>0,且它（們）所對應的列向量中都有正分量，則這時可進行基變換。取max={σ1.。。。σj}所對應的非基變量為進基變量。將“右端”列中各數(shù)分別和“進基變量列”的各數(shù)作比式（只對進基變量列中的正數(shù)作比式），并以θ記這些比式中最小一個。獲得θ行所對應的基變量即為離基變量。進基變量列和離基變量行相交處的元素成為“主元”，在其上加以圓圈。進行單純形變換，即令主元為1，主元所在列的其他元素為0。即得一新的單純形表，繼續(xù)進行判斷。（3）基可行解的基變換=目標函數(shù)約束條件基矩陣右邊常數(shù)

進基變量、離基變量、基變換=基變量=進基變量離基變量目標函數(shù)約束條件右邊常數(shù)==目標函數(shù)約束條件新的基矩陣右邊常數(shù)==進基變量離基變量目標函數(shù)約束條件基矩陣==目標函數(shù)約束條件新的基矩陣右邊常數(shù)=

單純形表法的運算步驟單純形表的運算Step0獲得一個初始的單純形表，確定基變量和非基變量Step1檢查基變量在目標函數(shù)中的系數(shù)是否等于0，在約束條件中的系數(shù)是否是一個單位矩陣Step2如果表中非基變量在目標函數(shù)中的系數(shù)全為負數(shù)，則已得到最優(yōu)解。停止。否則選擇系數(shù)為正數(shù)且絕對值最大的變量進基。Step3如果進基變量在約束條件中的系數(shù)全為負數(shù)或0，可行域開放，目標函數(shù)無界。停止。否則選取右邊常數(shù)和正的系數(shù)的最小比值，對應的基變量離基。Step4確定進基變量的列和離基變量的行交叉的元素為“主元”，對單純形表進行行變換，使主元變?yōu)?，主元所在列的其他元素變?yōu)?。將離基的基變量的位置用進基的非基變量代替。轉(zhuǎn)Step1。設X1表示I型餅干日產(chǎn)量，X2表示II型餅干日產(chǎn)量（單位為噸），z表示I型和II型餅干所創(chuàng)造的日總利潤目標：

maxz=5X1+4X2約束條件：

3X1+5X2≤15

（攪拌機的限制）

2X1+X2≤5

（成形機的限制）

2X1+2X2≤11

（烘箱的限制）

X1≥0，X2≥0

例題：餅干生產(chǎn)問題轉(zhuǎn)化為標準模型設z’=-z,引入松弛變量X3,X4,X5≥0

目標：

minz’=-5X1-4X2約束條件：

3X1+5X2+

X3=15

（攪拌機的限制）

2X1+X2+

X4=5

（成形機的限制）

2X1+2X2+

X5=11

（烘箱的限制）

X1,X2,X3,X4,X5≥0

寫出初始單純形表15/35/2x4離基x1進基x1x2X3X4X5右端Z540000x33510015x4210105X5220011111/2x1x2X3X4X5右端Z540000x33510015x4210105X52200111x101/205/21/210-5/20-25/23/201-3/2015/27/200-1161015/756x2進基x3離基得到最優(yōu)解，最優(yōu)解為：（x1，x2，x3，x4，x5）=（10/7，15/7，0，0，0，27/7）minz’=-110/7，maxz=110/7x1x2X3X4X5RHSZ′03/20-5/20-25/2x307/21-3/2015/2X111/201/205/2X5010-116x22/7-3/7015/710-3/7-13/70-110/700-1/75/7010/701-2/7-4/7127/700產(chǎn)品A產(chǎn)品B產(chǎn)品C利潤（萬元/噸）

941耗用原料（噸/噸）

425排放污染（m3/噸）

213銷售價格（萬元/噸）

301020總產(chǎn)量（噸）

111某工廠生產(chǎn)A、B、C三種產(chǎn)品，目標是這三種產(chǎn)品的總利潤最大化。和利潤有關的因素有原材料的消耗、排放的污染，產(chǎn)品的銷售總額和三種產(chǎn)品的產(chǎn)量。有關數(shù)據(jù)如下表所示。設生產(chǎn)的產(chǎn)品全部銷售，要求安排使總利潤最大的生產(chǎn)計劃，使得耗用原料不超過38噸，排放污染不超過25立方米，銷售總額不低于100萬元，三種產(chǎn)品的總產(chǎn)量不低于12噸。這是一個利潤目標最大化的單目標線性規(guī)劃問題。兩階段法舉例人工變量法如果約束條件全為“≤”，且右邊常數(shù)全為非負，則引進的松弛變量就可以作為初始的基變量，得到一個初始的基礎可行解。如果約束條件有“=”

，右邊常數(shù)全為非負，則需要加上非負人工變量，建立輔助問題。如果約束條件有“≥”，右邊常數(shù)全為非負，則需要減去非負人工變量，建立輔助問題。4、人工變量法人工變量法舉例思路——人為構(gòu)造一個單位矩陣人工變量人工變量大M法的步驟引進松弛變量，使約束條件全為等式。引進人工變量，令人工變量在目標函數(shù)中的系數(shù)為大M（任意大的正數(shù)）用單純形法求解，得到原問題的最優(yōu)解。若基變量中有非零的人工變量，則該LP無可行解。(1)大M法的步驟求解以下LP問題(大M法)化為標準型后加入人工變量，得到輔助問題Minz=x1+3x2s.t.2x1+x2=43x1+4x2-x3=6x1+3x2+x4=3x1,x2,x3,x4

≥0+mr1+mr2,r1,r2+r2+r1

X1X2X3r1r2X4rhs比Z-1-30-m-m00

r12101004

r234-10106

X41300013

X1X2X3r1r2X4rhs比Z5m-15m-3-m00010m

r1[2]1010044/2r234-101066/3X413000133/1

X1X2X3r1r2X4rhs比Z00-1-1-m1-m02

X1101/52-1/502X201-2/5-3/52/500X40011-111X1X2X3r1r2X4rhs比Z05/2m-5/2-m1/2-5/2m002

X111/201/20024r20[5/2]-1-3/21000X4000-1/20112/5最優(yōu)解x1=2,x2=0,x4=1,r1=r2=x3=0,minz=2練習：用大m法求解下列線性規(guī)劃問題引進松弛變量，使約束條件全為等式。引進人工變量，建立輔助問題。輔助問題的目標函數(shù)為各人工變量之和（僅含人工變量）。用人工變量作為輔助問題的初始基變量，用單純形法求解輔助問題，得到輔助問題的最優(yōu)解和最優(yōu)解的目標函數(shù)值。如果輔助問題最優(yōu)解的目標函數(shù)值大于0，原問題可行域為空集，無可行解。如果輔助問題最優(yōu)解的目標函數(shù)值等于0，輔助問題的最優(yōu)解是原問題的初始基礎可行解。將第一階段得到的最終表除去人工變量，將目標函數(shù)行的系數(shù)換原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表，用單純形法求解，得到原問題的最優(yōu)解。(2)兩階段法的步驟求解以下LP問題(兩階段法)minZ=X1+3X2s.t.2x1+x2=43x1+4x2-x3=6x1+3x2+x4=3x1,x2,x3,x4≥0

化成標準型第一階段：作輔助問題minf=r1+r2s.t.2x1+x2+r1=43x1+4x2-x3+r2=6x1+3x2+x4=3x1,x2,x3,x4,r1,r2≥0

X1X2X3r1r2x4右端比f000-1-100

r12101004

r234-10106

x41300013

X1X2X3r1r2x4右端比f55-100010

r121010044/2r234-101066/3x413000133/1

X1X2X3r1r2x4右端比f05/2-1-5/2000

X111/201/20024r205/2-1-3/21000x405/20-1/20112/5

X1X2X3r1r2x4右端比f000-1-100