第二章單純形法

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

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

–Cj

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

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

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

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

3X1+5X2≤15

（攪拌機(jī)的限制）

2X1+X2≤5

（成形機(jī)的限制）

2X1+2X2≤11

（烘箱的限制）

X1≥0，X2≥0

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

目標(biāo)：

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

3X1+5X2+

X3=15

（攪拌機(jī)的限制）

2X1+X2+

X4=5

（成形機(jī)的限制）

2X1+2X2+

X5=11

（烘箱的限制）

X1,X2,X3,X4,X5≥0

寫(xiě)出初始單純形表15/35/2x4離基x1進(jìn)基x1x2X3X4X5右端Z540000x33510015x4210105X5220011111/2x1x2X3X4X5右端Z540000x33510015x4210105X52200111x101/205/21/210-5/20-25/23/201-3/2015/27/200-1161015/756x2進(jìn)基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利潤(rùn)（萬(wàn)元/噸）

941耗用原料（噸/噸）

425排放污染（m3/噸）

213銷售價(jià)格（萬(wàn)元/噸）

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

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

，右邊常數(shù)全為非負(fù)，則需要加上非負(fù)人工變量，建立輔助問(wèn)題。如果約束條件有“≥”，右邊常數(shù)全為非負(fù)，則需要減去非負(fù)人工變量，建立輔助問(wèn)題。4、人工變量法人工變量法舉例思路——人為構(gòu)造一個(gè)單位矩陣人工變量人工變量大M法的步驟引進(jìn)松弛變量，使約束條件全為等式。引進(jìn)人工變量，令人工變量在目標(biāo)函數(shù)中的系數(shù)為大M（任意大的正數(shù)）用單純形法求解，得到原問(wèn)題的最優(yōu)解。若基變量中有非零的人工變量，則該LP無(wú)可行解。(1)大M法的步驟求解以下LP問(wèn)題(大M法)化為標(biāo)準(zhǔn)型后加入人工變量，得到輔助問(wèn)題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練習(xí)：用大m法求解下列線性規(guī)劃問(wèn)題引進(jìn)松弛變量，使約束條件全為等式。引進(jìn)人工變量，建立輔助問(wèn)題。輔助問(wèn)題的目標(biāo)函數(shù)為各人工變量之和（僅含人工變量）。用人工變量作為輔助問(wèn)題的初始基變量，用單純形法求解輔助問(wèn)題，得到輔助問(wèn)題的最優(yōu)解和最優(yōu)解的目標(biāo)函數(shù)值。如果輔助問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值大于0，原問(wèn)題可行域?yàn)榭占?，無(wú)可行解。如果輔助問(wèn)題最優(yōu)解的目標(biāo)函數(shù)值等于0，輔助問(wèn)題的最優(yōu)解是原問(wèn)題的初始基礎(chǔ)可行解。將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換原問(wèn)題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表，用單純形法求解，得到原問(wèn)題的最優(yōu)解。(2)兩階段法的步驟求解以下LP問(wèn)題(兩階段法)minZ=X1+3X2s.t.2x1+x2=43x1+4x2-x3=6x1+3x2+x4=3x1,x2,x3,x4≥0

化成標(biāo)準(zhǔn)型第一階段：作輔助問(wèn)題minf=r1+r2s.t.2x1+x2+r1=43x1+4x2-x3+r2=6x1+3x2+x4=3x1,x2,x3,x4,r1,r2≥0

X1X2X3r1r2x4右端比f(wàn)000-1-100

r12101004

r234-10106

x41300013

X1X2X3r1r2x4右端比f(wàn)55-100010

r121010044/2r234-101066/3x413000133/1

X1X2X3r1r2x4右端比f(wàn)05/2-1-5/2000

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

X1X2X3r1r2x4右端比f(wàn)000-1-100