第二章線性規(guī)劃運(yùn)籌學(xué)中應(yīng)用最廣泛的方法之一，歷史悠久，理論成熟。運(yùn)籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大線性規(guī)劃模型特點(diǎn)決策變量：x1,...,xn表示要尋求的方案，每一組值就是一個(gè)方案；約束條件：線性等式或不等式目標(biāo)函數(shù)：Z=?(x1

…xn)線性式，求Z極大或極小一般式minz=c1x1+c2x2+…+cnxnai1x1+ai2x2+…+ainxn

=bi,i=1,…,pai1x1+ai2x2+…+ainxn

bi,i=p+1,…,mxj

0,j=1,…,qxj

符號無限制，

j=q+1,…,ns.t.目標(biāo)函數(shù)（LP）3隱含的假設(shè)比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比可加性：每個(gè)決策變量對目標(biāo)和約束的影響?yīng)毩⒂谄渌兞窟B續(xù)性：每個(gè)決策變量取連續(xù)值確定性：線性規(guī)劃中的參數(shù)aij,bi,ci為確定值

矩陣形式說明：

A1A2………Ana11a12………a1nA=a21a22………

a2n

…am1am2………amn

x1x=x2

xn…

b1b=b2

bm…

c1c=c2

cn…約束矩陣決策向量右端向量價(jià)值向量

LP問題的規(guī)范型：LP問題的標(biāo)準(zhǔn)型：LP問題的三種形式是等價(jià)的：minz=cTxAx

bx0

s.t.minz=cTxAx=bx0

s.t.LP問題的規(guī)范型LP問題的標(biāo)準(zhǔn)型LP問題的一般型LP問題的規(guī)范型LP問題的一般型LP問題的標(biāo)準(zhǔn)型LP問題的一般型例：將線性規(guī)劃問題化成標(biāo)準(zhǔn)型(P15例2.1.3)

：解的概念：滿足所有約束條件的一組x1,x2，…xn的值稱作線性規(guī)劃的可行解，所有可行解構(gòu)成的集合稱作可行域。使目標(biāo)函數(shù)取得最大或最小值的可行解稱為線性規(guī)劃問題的最優(yōu)解；對應(yīng)的目標(biāo)函數(shù)的取值稱為最優(yōu)值。求解線性規(guī)劃問題就是求其最優(yōu)解和相應(yīng)的最優(yōu)值。圖解法？對于只有兩個(gè)變量的線性規(guī)劃問題，可以用在平面上作圖的方法求解，這種方法稱為圖解法。

特點(diǎn)：圖解法簡單、直觀，便于初學(xué)者了解線性規(guī)劃基本原理和幾何意義。§2.2可行區(qū)域與基本可行解step1.畫直角坐標(biāo)系；線性規(guī)劃問題圖解法的步驟對每個(gè)約束（包括非負(fù)約束）條件，先取等式得到一條直線（平面）并在坐標(biāo)圖中畫出該直線，然后取一已知點(diǎn)來判斷該點(diǎn)的坐標(biāo)是否滿足該約束條件，若滿足，則可行域與已知點(diǎn)在所畫直線的同側(cè)，否則可行域在直線的另一側(cè)。若所有的約束均已畫出，則可在坐標(biāo)系中畫出可行域。step2.依次做每條約束線，找出可行域;若不存在可行域,則該問題無可行解；step3.做目標(biāo)函數(shù)線，根據(jù)目標(biāo)類型平移,直到該線即將離開可行域時(shí)與該線接觸的最后一點(diǎn)即為一最優(yōu)解;

若該線可無限制地在可行域內(nèi)移動,則該問題無界。例1.maxZ=-X1+X2

2X1-X2-2X1-2X22X1+X25

X1,X20

1.圖解法示例解：確定可行域0123X2123X12X1-X2=-2()(0,2)(-1,0)2X1-X2

=-2X1+X2=5()(0,5)(5,0)

X1-2X2=2()(0,-1)(2,0)

X1-2X2

=2X1+X2

=5Z=-X1+X2(1,4)在該點(diǎn)取到最大值32310123X2A1BC42X1-X2

=-2X1-2X2

=2X1+X2

=5(1,4)若目標(biāo)函數(shù)改為minZ=4X1-2X2

2X1-X2-2X1-2X22X1+X25

X1,X20A2A3A4O最優(yōu)解：A1A2線段上所有的點(diǎn)，最優(yōu)值為-4X(1)=(0,2)T,X(2)=(1,4)TX=X(1)+(1-)X(2)(01)X1=1-X2=2+4(1-)=4-2(01)minZ=4X1-2X2=-4

2310123X2A1BC42X1-X2

=-2X1-2X2

=2X1+X2

=5(1,4)A2A3A4O可行域：由約束平面圍起來的凸多邊形區(qū)域，可行域內(nèi)的每一個(gè)點(diǎn)代表一個(gè)可行解。最優(yōu)解：總是在可行域的邊界上，一般由可行域的頂點(diǎn)表示。有效與無效(緊與松)約束：與最優(yōu)解相關(guān)的約束為有效(緊)約束。圖解法的觀察【1】無界無有限最優(yōu)解例2、maxZ=2X1+4X22X1+X28-2X1+X22X1,X20Z=02X1+X2=8-2X1+X2=28246X240X1例3、maxZ=3X1+2X2-X1-X21X1,X20無解無可行解-1X2-1X10-X1-X2

=1如果可行域?yàn)榭占?，線性規(guī)劃問題無可行解；如果目標(biāo)函數(shù)線可以無限制地在可行域內(nèi)向改善的方向移動，線性規(guī)劃問題無界；線性規(guī)劃問題可能存在無窮多個(gè)最優(yōu)解。圖解法的觀察（2）

唯一最優(yōu)解無窮多最優(yōu)解無有限最優(yōu)解無可行解有最優(yōu)解無最優(yōu)解總結(jié)兩個(gè)變量的LP問題的解：(1)、可行域?yàn)橥苟噙呅巍?2)、若有最優(yōu)解，定可在可行域的頂點(diǎn)得到。X(1)X(2)凸多邊形凹多邊形X(1)X(2)思考：兩個(gè)以上變量解的情況有又如何呢？2.可行區(qū)域的幾何結(jié)構(gòu)minZ=CTXAX

=bX0假設(shè)：秩(Am×n)=m<nD={X∈Rn|

AX=b,X0}≠Φ

a11a12………a1nA=a21a22………

a2n

…am1am2………amn其中：

b1b=b2

bm…X

=(x1…xn)TC

=(c1…cn)T凸集沒有凹陷部分，該集合內(nèi)任取兩點(diǎn)連線上的任何點(diǎn)都應(yīng)該在集合內(nèi)。定義1：xSy凸集：S是n維歐氏空間的一個(gè)集合,如果對任意

x,yS,0≤≤

1,

有x+(1-)yS。證明：設(shè)LP問題的可行解域?yàn)榧螪D={X|AX=bX0}任取X(1),X(2)D,則

X=X(1)

+(1-)X(2)

0

(0

1)

又因?yàn)锳X(1)

=b，AX(2)

=b

所以AX=A[X(1)

+(1-)X(2)

]=b

+(1-)b=b

則

XD，D為凸集定理1

D={X∈Rn|AX=b,X0}是凸集。定義2：

給定b∈R1,及非零向量a∈Rn稱集合

H={X∈Rn|aTX=b}是Rn中的一個(gè)超平面.H+={X∈Rn|aTX

b}H-={X∈Rn|aTX

b}H+，H-和超平面H都是凸集.H+和H-是由超平面H產(chǎn)生的兩個(gè)閉的半空間定理2任意多個(gè)凸集的交集仍是凸集。定義3：結(jié)論：線性規(guī)劃的可行域是凸集。凸集S的頂點(diǎn)X：—S是一個(gè)凸集，X∈S，對任意X(1),

X(2)∈S，X(1)≠X(2),和任意的，0<<1,都有X≠X(1)+(1-)X(2).定義4：a11…a1ma1m+1…a1na21…

a2ma2m+1…

a2n………am1…

amm

amm+1…

amnBN(m<n)r(A)=m,至少有一個(gè)m階子式不為03、基本可行解及線性規(guī)劃的基本原理定義5：基(基陣)——秩為m的約束矩陣Am×n的一個(gè)m階子矩陣B是可逆矩陣，則方陣B稱為對應(yīng)LP問題的一個(gè)基。A=(A1…

AmAm+1…

An)=(BN)

基向量非基向量…X=(X1…

Xm

Xm+1…

Xn

)T=(XBT

，XNT)T

基變量非基變量

XBT

XNT…AX=b的求解A=(BN)X=(XBXN)TXBXN(BN)=bBXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXN定義5：基本解——對應(yīng)于基B，X=為AX=b的一個(gè)解。B-1b0基本可行解——基B，基本解X=若B-1b0，稱基B為可行基。

B-1b0※基本解中最多有m個(gè)非零分量?！窘獾臄?shù)目不超過Cnm=個(gè)。n!m!(n-m)!（續(xù)）X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50121003201002001A1A2A3A4A5A=例：MaxZ=40X1+50X2

X1X2X3X4X5X=b=306024基B=(A3A4A5)=I可逆非基N=(A1A2)X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2121003201002001A1A2A3A4A5A=Z=40X1+50X2

令X1=

X2=0,X3=30,X4=60,X5=24X===XN0XBB-1b00306024

121又：Ｂ1=(A1A2A3)=320020|B1|=6≠0,

可逆X1=12-(1/3X4-1/3X5)X2=12-(1/2X5)X3=-6-(-1/3X4-2/3X5)令X4=X5=0X=(12,12,-6,0,0)T不是可行解Ｂ1=(A1A2A3)不是可行基?？梢灾苯域?yàn)證B-1b是否大于等于零。定理3：LP問題的可行解X是基本可行解X的非0分量對應(yīng)的系數(shù)列向量線性無關(guān)證明：()顯然。不妨設(shè)前k個(gè)分量非零。若A1,…,Ak

線性無關(guān)，則必有k≤m。若k=m,構(gòu)成基，則X就是基本可行解；若k<m,可以在其余n-k列向量中再找出m-k個(gè)，構(gòu)成m個(gè)線性無關(guān)的列向量構(gòu)成基，X就是該基對應(yīng)的基本可行解。D={X|AX=b，X0}，若A1,…,Ak

線性相關(guān)，必有不全為0的1,…,

k使1A1+…+

k

Ak

=0,記＝(1,…,

k,0…,0)T則有A

＝1A1+…+

k

Ak

=0可行域D中點(diǎn)X是頂點(diǎn)X是基本可行解定理4：Xj

>0j=1,…,kXj

=0j=k+1,…,nX＝(X1,…,Xn

)T證：X是D頂點(diǎn).。不妨設(shè)若A1,…,Ak

線性無關(guān),則X是基本可行解.選＝min{|

j≠0}>0Xjj做

X(1)

=X+

0

X(2)

=X-

0又AX(1)

=AX+A＝b

AX(2)

=AX-A=b

所以X(1)DX(2)D而X＝1/2X(1)+1/2X(2)矛盾(j=1,…,K)所以，A1,…,Ak

線性無關(guān)，即X為基本可行解.證明：()不妨設(shè)X為基本可行解Xj

>0j=1,…,kXj

=0j=k+1,…,n若X不是頂點(diǎn)，則有X(1)≠X(2)D

X=X(1)

+(1-)X(2)

(0<

<1)

Xj

=Xj

(1)

+(1-)Xj

(2)

(j=1,…,n)因?yàn)?gt;0，1->0，Xj

(1)

0，

Xj

(2)

0所以Xj

(1)＝

Xj

(2)＝

0(j=k+1,…,n)36因?yàn)锳X(1)

=bAX(2)

=bA

jXj(1)=bkj=1A

jXj(2)=bkj=1即A1X1(1)+…+Ak

Xk(1)=bA1X1(2)+…+Ak

Xk(2)=b由－得(X1(1)－X1(2))A1+…+(Xk(1)－Xk(2))Ak=0矛盾所以，A1,…,Ak

線性相關(guān).證明：D={X|AX=bX0}，X為可行解X＝(X1,…,Xn

)TXj

>0j=1,…,kXj

=0j=k+1,…,n若A1,…,Ak

線性相關(guān)，必有不全為0的1,…,

k使1A1+…+

k

Ak

=0做

＝(1,…,

k,0…,0)T則有A

＝1A1+…+

k

Ak

=0標(biāo)準(zhǔn)形式的LP問題有可行解該LP問題一定有基本可行解定理5：選＝min{|

j≠0}>0Xjj做

X(1)

=X+

0

X(2)

=X－

0又AX(1)

=AX+A＝b

AX(2)

=AX－A=b

所以X(1)DX(2)D顯然X(1)和

X(2)中至少有一個(gè)非零分量至少比X少一個(gè).若該解為基本可行解，則停止.否則，繼續(xù)進(jìn)行該過程，直到剩下一個(gè)非零分量，其對應(yīng)的列向量一定是線性無關(guān)的，也就得到了基本可行解。(j=1,…,K)若X為最優(yōu)解，不妨設(shè)Xj

>0j=1,…,kXj

=0j=k+1,…,n若X不是基本可行解，類似定理5，證明：得

X(1)

=X+

0

X(2)

=X－

0顯然CT

X(1)

=CTX+CT

CTX

CT

X(2)

=CTX-CT

CTX所以CT

X(1)

=CTX(2)=CTX,即X(1)和X(2)都是最優(yōu)解。仿照定理5的方法，一定可以構(gòu)造出一個(gè)基最優(yōu)解。標(biāo)準(zhǔn)形式的LP問題有有限的最優(yōu)值該LP問題一定有基本可行解是最優(yōu)解定理6:40LP問題解的性質(zhì)若(LP)問題有可行解，則可行解集(可行域)是凸集(可能有界，也可能無界)，有有限個(gè)頂點(diǎn)。

(LP)問題的基本可行解可行域的頂點(diǎn)。若(LP)問題有最優(yōu)解，必可以在基本可行解(頂點(diǎn))達(dá)到?？尚薪饣窘饣究尚薪鈧€(gè)數(shù)有限，當(dāng)約束條件為m個(gè)，n個(gè)變量時(shí)，基本可行解個(gè)數(shù)不超過:Cnm=

n!m!(n-m)!(m<n)§2.3單純形法引例maxZ=40X1+50X2X1+2X2≤303X1+2X2≤602X2≤24X1，X20minW=-40X1-50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50解：(1)、確定初始可行解B=(A3A4A5)=I令X1=

X2=0X(1)=(0,0,30,60,24)TW(1)=0minW=-40X1-50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(2)、判定解是否最優(yōu)W=0-40X1-50X2當(dāng)X1從0↗或X2從0↗W從0↘，∴X(1)不是最優(yōu)解(3)、由一個(gè)基可行解→另一個(gè)基可行解?！?0>40選X2從0↗，X1=0X3=30-2X20，X230/2

X4=60-2X20，X260/2

X5=24-2X20，X224/2√

X2=min(30/2,60/2,24/2)=12X2進(jìn)基變量，

X5出基變量。minW=-40X1-50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50B2=(A3A4A2)minW=-40X1-50X2

④X1+2X2+X3=30①3X1+2X2+X4=60②2X2+X5=24③X1…X50minW=-600-40X1+25X5X1+X3-X5=63X1+X4-X5=36X2+1/2X5=12X1…X50③×1/2

，③代入④式，①－③，②－③令X1=X5=0X(2)=(0,12,6,36,0)TW(2)=-600(2)'

判斷：minW=-600-40X1+25X5∵40>0，∴X(2)不是最優(yōu)解。(3)'

選X1從0↗，X5=0X3=6-X10

√X4=

36-3X10

X2=120

X1=min(6/1,36/3)=6X1進(jìn)基，

X3出基。minW=-600-40X1+25X5X1+X3-X5=63X1+X4-X5=36X2+1/2X5=12X1…X50B3=(A1A4A2)minW=-840+40X3-15X5X1+X3-X5=6

-3X3+

X4+2X5=18X2+1/2X5=12令X3=X5=0,X(3)=(6,12,0,18,0)TW(3)=-840minW=-600-40X1+25X5④X1+X3-X5=6①3X1+X4-X5=36②X2+1/2X5=12③X1…X50①代入④式，②-3*①(2)"判斷：minW=-840+40X3-15X5

∵15>0∴X(3)不是最優(yōu)解(3)"

選X5從0↗，X3=0X1=6+X50

X4=

18-2X50

√X2=12-1/2X5

0

X5=min(18/2,12/1/2)=9X5進(jìn)基，

X4出基。minW=-840+40X3-15X5X1+X3-X5=6

-3X3+

X4+2X5=18

X2+1/2

X5

=12B4=(A1A5A2)minW=-975+35/2X3+15/2X4X1-1/2X3+1/2X4=15

-3/2X3+1/2X4+

X5=

9X2+3/4X3-1/4X4=15/2

令X3=X4=0,X(4)=(15,15/2,0,0,9)TW(4)=-975minW=-840+40X3-15X5④X1+X3-X5=6

①-3X3+

X4+2X5=18②

X2+1/2

X5

=12③②

×1/2

，②代入④式，①+(1/2)②

，③-(1/4)②

判斷：minW=-975+35/2X3+15/2X4，maxZ=975達(dá)到最優(yōu)。例1

x1x2x3x4x5-z04050000x3x4x5306024

121003201002001maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(-z)+40X1+50X2=0X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50X230/2

X260/2

X224/2回顧min例1

x1x2x3x4x5-z-60040000-25x3x4x2636121010-13001-101001/2(-z)+40X1-25X5=-600X1+X3-X5=63X1+X4-X5=36X2+(1/2)X5=12X1…X50X16/1

X136/3例1

x1x2x3x4x5-z-840

00-40015x1x4x2618121010-100-31201001/2(-z)-40X3+15X5=-840X1+X3-X5=6-3X3+X4+2X5=18X2+1/2X5=12X1…X50X518/2

X512/1/2例1(-z)-35/2X3-15/2X4=-975X1-1/2X3+1/2X4=15-3/2X3+1/2X4+X5=9X2+3/4X3-1/4X4=15/2X1…X50

x1x2x3x4x5-z-975

00-35/2

-15/20x1x5x215915/210-1/21/2000-3/21/21013/4-1/40X(4)=(15,15/2,0,0,9)TmaxZ=9750(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)X(1)=(0,0,30,60,24)T；Z(1)=0X(2)=(0,12,6,36,0)T

；

Z(2)=600X(3)=(6,12,0,18,0)T；Z(3)=840

X(4)=(15,7.5,0,0,9)T；Z(4)=975思考：線性規(guī)劃問題的求解方法minZ=CTXAX

=bX0其中，Am×n

滿秩X

=(x1…xn)T

D={X∈Rn|

AX=b,X0}≠Φ單純形法的理論基礎(chǔ)對應(yīng)基B，其基本解為XB=B-1b,XN=0;

當(dāng)B-1b≥0，為基本可行解。

當(dāng)B-1b>0，為非退化的基本可行解。對應(yīng)可行基B：XB=B-1b-B-1NXNZ=CBTB-1b+(CNT

-CBT

B-1N)XNminZ=CTXAX=b

X0XB+B-1NXN=B-1bXB

，XN0原線性規(guī)劃可變形為minZ=CBT

B-1b-(CBT

B-1N-CNT)XNA=(B,N)XBXNX=AX=b

X0minZ=CBT

B-1b-(CBT

B-1A-CT)X令A(yù)=B-1A=(I,B-1N)b=B-1b,z0=CBT

B-1b

令A(yù)=B-1A=(I,B-1N)b=B-1b,z0=CBT

B-1b

10…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amnA=若A的前m列構(gòu)成基B，則minZ=CTX

AX=

bX0CBT

B-1bB-1bCBTB-1A-CTB-1A若CBT

B-1A-CT

0，則B為最優(yōu)基。0b-CTA對應(yīng)基B的單純形表為了敘述方便，我們不妨假設(shè)（LP）問題為如下形式：或典則方程組（典式）非基變量檢驗(yàn)數(shù)單純形表

X1X2…

Xm

Xm+1…

Xm+k

…XnXBZ000

…0m+1…m+k…

nX1b110…0a1m+1…a1m+k…a1nX2b201…0a2m+1…a2m+k…

a2nXr

br

00…0arm+1…arm+k…

arnXm

bm

00…1amm+1…amm+k

…

ann

P1P2

…PmPm+1…Pm+k

…Pn…………………………………………此時(shí)，B=(P1P2…Pm)＝I對應(yīng)的基本可行解為定理1：對解X(1)

，若檢驗(yàn)數(shù)j(j=1,…,n)全部

0,則X(1)為最優(yōu)解。證明：Xi=bi-aij

xjJ=m+1n令非基變量Xk

=(﹥0)X(2)

=(b1-a1k,…,bm

-amk

,0,…,,…,0)TAX(2)

=bX(2)0Z=Z0-k

，當(dāng)時(shí)

Z-定理2：對X(1)，若有某個(gè)非基變量Xk→k>0且相應(yīng)的Pk

=(a1k,…,amk

)T

0，則原問題無有限最優(yōu)解。換基迭代公式：(1)、決定進(jìn)基變量：maxj=k>0,則Xk

為進(jìn)基變量(2)、決定離基變量：bi-aikXk

0

(i=1,2,…,m)，Xk

biaik(aik>0θ=minaik

>0=biaikbrark則第r個(gè)基變量（XBr）為換出變量。定理3：經(jīng)單純形法得到的X(2)

=(b1-a1k,…,bm

-

amk

,0,…,,…,0)T是基本可行解，在非退化情況下有Z(2)<

Z(1)

θ=minaik

>0=biaikbrark注：證明：不妨設(shè)XBr

=Xm

=0,Xk

==bmamk(﹥0)X(1)中P1,…

Pm線性無關(guān)，下證P1,…

Pm-1,Pk線性無關(guān)。若否，因?yàn)镻1,…

Pm線性無關(guān)則Pk

=a1kP1+…+am-1,kPm-1+amk

Pm①而Pk

=l1P1+…+lm-1Pm-1②

①-②(a1k-

l1)P1+…+(am-1k-

lm-1)Pm-1+amkPm=0P1,…,Pm線性相關(guān)，矛盾。即X(2)是基本解，且是可行解.Z(2)=

Z(1)-

k<Z(1)單純形法基本步驟(1)、定初始基，初始基本可行解，典式，檢驗(yàn)數(shù)(3)、若有k>0，Pk全

0，停，沒有有限最優(yōu)解；否則轉(zhuǎn)(4)(2)、對應(yīng)于非基變量檢驗(yàn)數(shù)j全

0。

若是，停，得到最優(yōu)解；若否，轉(zhuǎn)(3)。θ=minaik

>0=biaikbrark定第r個(gè)基變量（XBr）為離基變量，ark為主元。由最小θ比值法求：k＝max{j|j=1,…,n}>0,k→Xk

Xk為進(jìn)基變量j>0(4)、轉(zhuǎn)(2)k0

……a1k0ark1amk

0初等行變換Pk

=…………(5)、以ark為中心，換基迭代在單純形表上解決下述問題maxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50MinZ’=-40X1-50X2X1X2X3X4X5Z’

04050000θX3301210015X460

3

201030X5240(2)00112-60040000-25X36(1)010-16X4363001-112X21201001/2-84000-40015X161010-1X41800-31(2)9X21201001/224

z’-97500-35/2-15/20X11510-1/21/20X5900-3/21/21X215/2013/4-1/40本問題的最優(yōu)解X=(15,15/2,0,0,9)T

Z=975幾點(diǎn)說明：(1)、例minZ=-X1-2X2X1

4X2

3X1+2X2

8

X1,X20

X1+X3=

4X2+X4=

3X1+2X2+X5=

8

X1，…

，X50X1X2X3X4X5Z

012000X3410100X430(1)010X5812001Z

-6100-20X3410100X2301010X52

(1)00-21(接下表)

X1X2X3X4X5Z

-80000-1X32001(2)-1X2301010X12100-21Z

-80000-1X41001/21-1/2X2201-1/201/2X14

10100非基變量檢驗(yàn)數(shù)為0X(1)=(2,3)Z(1)=-8X(2)=(4,2)Z(2)=-8無窮多解全部解：X=α+(1-α)

(0α1)2432(2)、3X1+4X264X1+X223X1+2X23X1,X20MinZ=-10X1-12X2X1X2X3X4X5Z

01012000X363(4)100X4241010X5332001

X1X2X3X4X5

z

01012000θi

X363(4)1003/2

X42410102/1

X53320013/2

z-1810-300θi

X23/23/411/4002

X41/213/40-1/4102/13

X50

(3/2)0-1/2010

z

-1800-8/30-2/3

X23/2011/20-1/2

X41/2005/61-13/6

X1010-1/302/3退化解X*=(0,3/2,0,1/2,0)TZmin=-18X1X2X3X4X5Z

041000X32-11100X44(1)-4010X581-2001(3)例：minZ=-4X1-X2-X1+X2

2X1-4X2

4X1-2X2

8X1,X20Z-160170-40X360-3110X141-4010X540(2)0-11z-500009/2-17/2X312001-1/23/2X112100-12X22010-1/21/2本問題無界。X1X2OZ=0Z=-4X1-X2X1-2X2

8-X1+X2

2

X1-4X2

4

一、兩階段法：原問題minZ=Cj

xj

j=1nxj

0j=1naij

xj

=bi0

(i=1,2,…,m)作輔助問題minW=yi

i=1mxj

，

yi0j=1naij

xj

+yi

=bi(i=1,2,…,m)§2.4初始解第1階段最優(yōu)基B*min=*(1)、*﹥0

(2)、*=0

yi

≡0(i=1,2,…,m)①B*基變量無人工變量②B*基變量含人工變量yr單純形表中，yr+ark

yk

+arj

xj

=0(﹡)

k∈Jj∈JJ：非基變量下標(biāo)集合,判定原問題無可行解。1)arj

全=0

(﹡)

式多余方程2)arj

有0

元，設(shè)為ars

0

以ars為主元，換基迭代，最后得到①maxZ=-X1+2X2X1+X2

2-X1+X21X2

3X1X2

0例1：minZ’=X1-2X2minW=X6+X7X1+X2-X3+X6=2-X1+X2-X4+X7=1X2+X5=3X1…X7

0X1+X2-X3=2-X1+X2-X4=1X2+X5=3X1…X5

0第一階段：求

00000-1-1

X1X2X3X4X5X6X7W

3

0

2-1-10

00X6211-10010X71-1

(1)0-1001X530100100W

1

+20-1100-2X61(2)0-1101-1X21-1

10-1001X52100110-1

W

0

00000-1-1X11/210-1/21/201/2-1/2X23/20

1-1/2-1/201/21/2X53/2001/21/21-1/2-1/2

-12000X1X2X3X4X5z’

-5/2001/23/20X11/210-1/2(1/2)0X23/201-1/2-1/20X53/2001/21/21z’-4-30200X4120