第一章線性規(guī)劃與單純形法

天津大學(xué)老教授協(xié)會(huì)2011考研輔導(dǎo)運(yùn)籌學(xué)輔導(dǎo)§1線性規(guī)劃模型第一章線性規(guī)劃例1.1生產(chǎn)計(jì)劃問題（資源利用問題）

勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子銷售價(jià)格30元/個(gè)，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每個(gè)月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問該廠如何組織生產(chǎn)才能使每月的銷售收入最大？解：將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：解：將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：1．確定決策變量：x1=生產(chǎn)桌子的數(shù)量

x2=生產(chǎn)椅子的數(shù)量解：將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：1．確定決策變量：x1=生產(chǎn)桌子的數(shù)量

x2=生產(chǎn)椅子的數(shù)量2．確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大

maxz=50x1+30x2解：將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：1．確定決策變量：x1=生產(chǎn)桌子的數(shù)量

x2=生產(chǎn)椅子的數(shù)量2．確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大

maxz=50x1+30x23．確定約束條件：

4x1+3x2

120（木工工時(shí)限制）

2x1+x2

50（油漆工工時(shí)限制）解：將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：1．確定決策變量：x1=生產(chǎn)桌子的數(shù)量

x2=生產(chǎn)椅子的數(shù)量2．確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大

maxz=50x1+30x23．確定約束條件：

4x1+3x2

120（木工工時(shí)限制）

2x1+x2

50（油漆工工時(shí)限制）4．變量取值限制：

一般情況，決策變量只取正值（非負(fù)值）

x1

0,x2

0解：將一個(gè)實(shí)際問題轉(zhuǎn)化為線性規(guī)劃模型有以下幾個(gè)步驟：1．確定決策變量：x1=生產(chǎn)桌子的數(shù)量

x2=生產(chǎn)椅子的數(shù)量2．確定目標(biāo)函數(shù)：家具廠的目標(biāo)是銷售收入最大

maxz=50x1+30x23．確定約束條件：

4x1+3x2

120（木工工時(shí)限制）

2x1+x2

50（油漆工工時(shí)限制）4．變量取值限制：

一般情況，決策變量只取正值（非負(fù)值）

x1

0,x2

0數(shù)學(xué)模型

maxS=50x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0線性規(guī)劃數(shù)學(xué)模型三要素：

決策變量、約束條件、目標(biāo)函數(shù)

線性規(guī)劃模型的三要素3.約束條件：為實(shí)現(xiàn)優(yōu)化目標(biāo)需受到的限制，用決策變量的等式或不等式表示；1.決策變量：需決策的量，即待求的未知數(shù)；2.目標(biāo)函數(shù)：需優(yōu)化的量，即欲達(dá)的目標(biāo)，用決策變量的表達(dá)式表示；建立線性規(guī)劃問題的數(shù)學(xué)模型的例子例1.2營養(yǎng)配餐問題假定一個(gè)成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價(jià)格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費(fèi)用最小？食品名稱熱量（千卡）蛋白質(zhì)（克）鈣（毫克）價(jià)格（元)豬肉10005040014雞蛋800602006大米900203003白菜200105002各種食物的營養(yǎng)成分表解：設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為：

minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4

300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800x1，x2，

x3，x4

0線性規(guī)劃問題的一般形式：Max(Min)S=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn

(=,

)b1a21x1+a22x2+….+a2nxn

(=,

)b2

….am1x1+am2x2+….+amnxn

(=,

)bmx1,x2….xn

0§2線性規(guī)劃問題圖解法圖解法是用畫圖的方式求解線性規(guī)劃的一種方法。它雖然只能用于解二維（兩個(gè)變量）的問題，但其主要作用并不在于求解，而是在于能夠直觀地說明線性規(guī)劃解的一些重要性質(zhì)?！?線性規(guī)劃問題圖解法（1）滿足約束條件的變量的值，稱為可行解。§2線性規(guī)劃問題圖解法（1）滿足約束條件的變量的值，稱為可行解。（2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解?！?線性規(guī)劃問題圖解法（1）滿足約束條件的變量的值，稱為可行解。（2）使目標(biāo)函數(shù)取得最優(yōu)值的可行解，稱為最優(yōu)解。例1.1的數(shù)學(xué)模型

maxS=50x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0x2504030201010203040x14x1+3x2

120由4x1+3x2

120x1

0x2

0圍成的區(qū)域x2504030201010203040x12x1+x2

50由2x1+x2

50x1

0x2

0圍成的區(qū)域x2504030201010203040x12x1+x2

504x1+3x2

120可行域同時(shí)滿足：2x1+x2

504x1+3x2

120x1

0x2

0的區(qū)域——可行域x2504030201010203040x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點(diǎn)都是可行解，它的全體組成問題的解集合。該問題的可行域是由O，Q1，Q2，Q3作為頂點(diǎn)的凸多邊形x2504030201010203040x1可行域目標(biāo)函數(shù)是以S作為參數(shù)的一組平行線x2=

S/30-（5/3）x1x2504030201010203040x1可行域當(dāng)S值不斷增加時(shí)，該直線x2=

S/30-（5/3）x1沿著其法線方向向右上方移動(dòng)。x2504030201010203040x1可行域當(dāng)該直線移到Q2點(diǎn)時(shí)，S（目標(biāo)函數(shù)）值達(dá)到最大：MaxS=50*15+30*20=1350此時(shí)最優(yōu)解=（15，20）Q2（15，20）二個(gè)重要結(jié)論：滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場合。二個(gè)重要結(jié)論：滿足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場合。最優(yōu)解必定能在凸多邊形的某一個(gè)頂點(diǎn)上取得，這一事實(shí)也可以推廣到更多變量的場合。解的討論：最優(yōu)解是唯一解；解的討論：最優(yōu)解是唯一解；無窮多組最優(yōu)解：例1.1的目標(biāo)函數(shù)由

maxS=50x1+30x2變成：

maxS=40x1+30x2s.t.4x1+3x2

1202x1+x2

50x1,x2

0x2504030201010203040x1可行域目標(biāo)函數(shù)是同約束條件：4x1+3x2

120平行的直線x2=

S/30-（4/3）x1x2504030201010203040x1可行域當(dāng)S的值增加時(shí)，目標(biāo)函數(shù)同約束條件：4x1+3x2

120重合，Q1與Q2之間都是最優(yōu)解。Q1（25，0）Q2（15，20）解的討論：無界解：例：maxS=x1+x2s.t.-2x1+x2

40x1-x2

20x1,x2

0x2504030201010203040x1該可行域無界，目標(biāo)函數(shù)值可增加到無窮大，稱這種情況為無界解或無最優(yōu)解。解的討論：無可行解：例：maxS=2x1+3x2s.t.x1+2x2

8x1

4x2

3-2x1+x2

4x1,x2

0該問題可行域?yàn)榭占?，即無可行解，也不存在最優(yōu)解。解的情況：有可行解⊙有唯一最優(yōu)解⊙有無窮最優(yōu)解⊙無最優(yōu)解無可行解§3線性規(guī)劃問題的標(biāo)準(zhǔn)形式MaxS=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn=b1a21x1+a22x2+….+a2nxn=b2

….am1x1+am2x2+….+amnxn=bmx1,x2….xn

0其中：bi

0(i=1,2,….m)線性規(guī)劃問標(biāo)準(zhǔn)形的向量形式線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式Max

S=CX

s.t.

AX=bX

0

a11a12….a1nb1A=a21a22….a2nb

=

b2…….am1am2….amn

bn

c1x10c2x20C=X=0=……………..

cn

xn0如何將一般問題化為標(biāo)準(zhǔn)型：若目標(biāo)函數(shù)是求最小值MinS=CX令S’=-S,則

MaxS’=-CX如何將一般問題化為標(biāo)準(zhǔn)型：若目標(biāo)函數(shù)是求最小值MinS=CX令S’=-S,則

MaxS’=-CX若約束條件是不等式如何將一般問題化為標(biāo)準(zhǔn)型：若目標(biāo)函數(shù)是求最小值MinS=CX令S’=-S,則

MaxS’=-CX若約束條件是不等式若約束條件是“

”不等式

n

aijxj

+si=bij=1

si

0是非負(fù)的松馳變量如何將一般問題化為標(biāo)準(zhǔn)型：若約束條件是“

”不等式

n

aijxj

-si

=bi

j=1

si

0是非負(fù)的松馳變量如何將一般問題化為標(biāo)準(zhǔn)型：若約束條件右面的某一常數(shù)項(xiàng)bi<0這時(shí)只要在bi相對(duì)應(yīng)的約束方程兩邊乘上-1。如何將一般問題化為標(biāo)準(zhǔn)型：若約束條件右面的某一常數(shù)項(xiàng)bi<0這時(shí)只要在bi相對(duì)應(yīng)的約束方程兩邊乘上-1。若變量xj無非負(fù)限制引進(jìn)兩個(gè)非負(fù)變量xj’

xj”

0令xj=

xj’-xj”（可正可負(fù)）如何將一般問題化為標(biāo)準(zhǔn)型：若約束條件右面的某一常數(shù)項(xiàng)bi<0這時(shí)只要在bi相對(duì)應(yīng)的約束方程兩邊乘上-1。若變量xj無非負(fù)限制引進(jìn)兩個(gè)非負(fù)變量xj’

xj”>=0令xj=

xj’-xj”（可正可負(fù)）任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型例1.3將下列問題化成標(biāo)準(zhǔn)型:MinS=-x1+2x2-3x3s.t.x1+x2+x3

7x1-x2+x3

2-3x1+x2+2x3=5x1,x2

0x3無非負(fù)限制MaxS=x1-2x2+3x3’-3x3”s.t.x1+x2+x3’-x3”+x4=7x1-x2+x3’-x3”-x5=2-3x1+x2+2x3’-2x3”=5x1,x2,x3’,x3”,x4,x5

0§4

單純形方法一線性規(guī)劃問題解的概念線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式：

MaxS=CX（1-9）

s.t.AX=b（1-10）

X

0（1-11）

a11a12….a1nb1A=a21a22….a2nb

=

b2………am1am2….amn

bn

c1x10c2x20C=X=0=……………..

cn

xn0解、可行解、最優(yōu)解⊙滿足約束條件（1-10）的X，稱為線性規(guī)劃問題的解。解、可行解、最優(yōu)解⊙滿足約束條件（1-10）的X，稱為線性規(guī)劃問題的解?！褲M足約束條件（1-10）與（1-11）的X，稱為線性規(guī)劃的問題可行解。解、可行解、最優(yōu)解⊙滿足約束條件（1-10）的X，稱為線性規(guī)劃問題的解?！褲M足約束條件（1-10）與（1-11）的X，稱為線性規(guī)劃的問題可行解?！褲M足目標(biāo)函數(shù)（1-9）的可行解X，稱為線性規(guī)劃的問題最優(yōu)解?；?、基向量、基變量⊙設(shè)r(A)=m,并且B是A的m階非奇異的子矩陣（det(B)

0),則稱矩陣

B為線性規(guī)劃問題的一個(gè)基?；?、基向量、基變量⊙設(shè)r(A)=m,并且B是A的m階非奇異的子矩陣（det(B)<>0),則稱矩陣

B為線性規(guī)劃問題的一個(gè)基?！丫仃嘊=（P1，P2….Pm)，其列向量

Pj

稱為對(duì)應(yīng)基B的基向量?；?、基向量、基變量⊙設(shè)r(A)=m,并且B是A的m階非奇異的子矩陣（det(B)<>0),則稱矩陣

B為線性規(guī)劃問題的一個(gè)基?！丫仃嘊=（P1，P2….Pm)，其列向量

Pj稱為對(duì)應(yīng)基B的基向量?！雅c基向量Pj

相對(duì)應(yīng)的變量xj就稱為基變量，其余的就稱為非基變量?；?基可行解.可行基⊙對(duì)于某一特定的基B，非基變量取

0值的解，稱為基解?；?基可行解.可行基⊙對(duì)于某一特定的基B，非基變量取

0值的解，稱為基解?！褲M足非負(fù)約束條件的基解，稱為基可行解。基解.基可行解.可行基⊙對(duì)于某一特定的基B，非基變量取

0值的解，稱為基解。⊙滿足非負(fù)約束條件的基解，稱為基可行解。⊙與基可行解對(duì)應(yīng)的基，稱為可行基。為了理解基解.基可行解.最優(yōu)解的概念，用下列例子說明：例1.4：maxS=2x1+3x2（1-12）

s.t.-2x1+3x2

6（1-13-1）

3x1-2x2

6（1-13-2）

x1+x2

4（1-13-3）

x1,x2

0（1-14）將其劃為標(biāo)準(zhǔn)形式：例1.4：maxS=2x1+3x2（1-12）

s.t.-2x1+3x2+s1=6（1-13-1）

3x1-2x2+s2=6（1-13-2）

x1+x2+s3=4（1-13-3）

x1,x2

0,si

0,(i=1,2,3)

（1-14）

x243211234x1O-1-1-2-2-3-3-2x1+3x2=63x1-2

x2=6x1+x2=4AQ1Q2Q3Q4Bx243211234x1O-1-1-2-2-3-3-2x1+3x2<=63x1-2

x2<=6x1+x2<=4ABx243211234x1O-1-1-2-2-3-3-2x1+3x2<=63x1-2

x2<=6x1+x2<=4AQ1Q2Q3Q4Bx243211234x1O-1-1-2-2-3-33x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域-2x1+3x2

6本問題解的情況：基礎(chǔ)解：點(diǎn)（O，A，B，Q1，Q2，Q3，Q4，P1，P2，P3）可行域：由點(diǎn)（O，Q1，Q2，Q3，Q4）圍成的區(qū)域。基可行解：點(diǎn)（O，Q1，Q2，Q3，Q4）最優(yōu)解：

Q3解的集合：非可行解可行解解的集合：基礎(chǔ)解解的集合：可行解基礎(chǔ)解基礎(chǔ)可行解解的集合：可行解基礎(chǔ)解基礎(chǔ)最優(yōu)解基礎(chǔ)可行解兩個(gè)基本概念：凸組合：

設(shè)x(1),x(2)…..x(k)是n維線性空間Rn中的k個(gè)點(diǎn)，若存在數(shù)u1,u2,….uk

且0<ui<1(i=1,2,…k),

ui=1,使得x=u1x(1)+u2x(2)+…..+

uk

x(k)成立，則稱x為x(1),x(2)…..x(k)的凸組合。兩個(gè)基本概念：頂點(diǎn)：設(shè)D是凸集,若D中的點(diǎn)x不能成為D中任何線段上的內(nèi)點(diǎn)，則稱x為凸集D的頂點(diǎn)。即：若D中的任意兩點(diǎn)x(1),x(2)

，不存在數(shù)

（0<

<1）使得

x=

x(1)+(1-

)x(2)成立，則稱x為凸集D的一個(gè)頂點(diǎn)。例1.9：多邊形上的點(diǎn)是頂點(diǎn)圓周上的點(diǎn)都是頂點(diǎn)二線性規(guī)劃的基本定理定理1-1

線性規(guī)劃問題的可行域是凸集。（即連接線性規(guī)劃問題任意兩個(gè)可行解的線段上的點(diǎn)仍然是可行解。)證：設(shè)X1,X2是兩個(gè)可行解，對(duì)于0<

<1由于AX=A(X1+

(1-)

X2)=AX1+

(1-)AX2=

b+(1-)b=b

所以X=X1+

(1-)

X2也是可行解，所以線性規(guī)劃問題的可行域是凸集。定理1-2

線性規(guī)劃問題的可行解x為基礎(chǔ)可行解的充分必要條件是：x的非零分量所對(duì)應(yīng)的系數(shù)矩陣A的列向量是線性無關(guān)。證：必要性設(shè)X=(x1,x2,…,xm,0,…,0)是基可行解，x1,x2,…,xm是基變量，其對(duì)應(yīng)的向量P1,P2,…,Pm構(gòu)成基，故P1,P2,…,Pm是線性無關(guān)。充分性設(shè)可行解X=(x1,x2,…,xk,0,…,0),xj>0,j=1,2,…,k,若P1,P2,…,Pk線性無關(guān)，則應(yīng)有k≤m,當(dāng)k=m時(shí),則P1,P2,…,Pm

恰好構(gòu)成一個(gè)基，從而X=(x1,x2,…,xm,0,…,0)為基可行解。當(dāng)k<m時(shí),則一定把P1,P2,…,Pk擴(kuò)充成一個(gè)基，其對(duì)應(yīng)的解為X=(x1,x2,…,xk,0,…,0),故X為基可行解。定理1-3

線性規(guī)劃問題的可行解集D中的點(diǎn)x是頂點(diǎn)的充分必要條件是：x是基礎(chǔ)可行解。定理1-3

線性規(guī)劃問題的可行解集D中的點(diǎn)x是頂點(diǎn)的充分必要條件是：x是基礎(chǔ)可行解。推論：可行解集D中的頂點(diǎn)個(gè)數(shù)是有限的。定理1-3

線性規(guī)劃問題的可行解集D中的點(diǎn)x是頂點(diǎn)的充分必要條件是：x是基礎(chǔ)可行解。推論：可行解集D中的頂點(diǎn)個(gè)數(shù)是有限的。推論：若可行解集D是有界的凸集，則D中任意一點(diǎn)x，都可表示成D的頂點(diǎn)的凸組合。定理1-4

若可行解集D有界，則線性規(guī)劃問題的最優(yōu)解，必定在D的頂點(diǎn)上達(dá)到。說明1：若可行解集D無界，則線性規(guī)劃問題可能有最優(yōu)解，也可能無最優(yōu)解。若有最優(yōu)解，也必在頂點(diǎn)上達(dá)到。說明2：有時(shí)目標(biāo)函數(shù)也可能在多個(gè)頂點(diǎn)上達(dá)到最優(yōu)值。這些頂點(diǎn)的凸組合也是最優(yōu)值。（有無窮多最優(yōu)解）三線性規(guī)劃的單純形方法單純形方法基本思路：從可行域中某個(gè)基可行解（一個(gè)頂點(diǎn)）開始（稱為初始基可行解）。如可能，從可行域中求出具有更優(yōu)目標(biāo)函數(shù)值的另一個(gè)基可行解（另一個(gè)頂點(diǎn)），以改進(jìn)初始解。繼續(xù)尋找更優(yōu)的基礎(chǔ)可行解，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值。當(dāng)某一個(gè)基礎(chǔ)可行解不能再改善時(shí)，該解就是最優(yōu)解。例1-18：一個(gè)企業(yè)需要同一種原材料生產(chǎn)甲乙兩種產(chǎn)品，它們的單位產(chǎn)品所需要的原材料的數(shù)量及所耗費(fèi)的加工時(shí)間各不相同，從而獲得的利潤也不相同（如下表）。那么，該企業(yè)應(yīng)如何安排生產(chǎn)計(jì)劃，才能使獲得的利潤達(dá)到最大？解：數(shù)學(xué)模型

maxS=6x1+4x2s.t.2x1+3x2≤1004x1+2x2≤120x1,x2≥0解：引進(jìn)松弛變量x3,x4≥0數(shù)學(xué)模型標(biāo)準(zhǔn)形式：

maxS=6x1+4x2

s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,

x3,x4≥0

約束條件的增廣矩陣為：

2310100（Ab)=4201120顯然r(A)=r(Ab)=2<4,該問題有無窮多組解。令A(yù)=（P1，P2，P3，P4）=23104201X=（x1,x2,x3,x4)

A=（P1，P2，P3，P4）

=23104201X=（x1,x2,x3,x4)B=(P3，P4

）=1001P3，P4線性無關(guān)，x3,x4是基變量，x1,x2,是非基變量。

用非基變量表示的方程：

S=6x1+4x2x3=100-2x1-3x2(I)x4=120-4x1-2x2

稱(I)為消去系統(tǒng)，若

b=(100,120)t≥

0則稱為正消去系統(tǒng)。

令非基變量

(x1,

x2)t=(0，0)t

得基礎(chǔ)可行解：

x(1)=(0,0,100,120)tS1=0

經(jīng)濟(jì)含義：不生產(chǎn)產(chǎn)品甲乙，利潤為零。分析：S=6x1+4x2（分別增加單位產(chǎn)品甲、乙，目標(biāo)函數(shù)分別減少6、4，即利潤分別增加6百元、4百元。）增加單位產(chǎn)品對(duì)目標(biāo)函數(shù)的貢獻(xiàn)，這就是檢驗(yàn)數(shù)的概念。

增加單位產(chǎn)品甲（x1）比乙對(duì)目標(biāo)函數(shù)的貢獻(xiàn)大（檢驗(yàn)數(shù)最大），把非基變量x1換成基變量，稱x1為進(jìn)基變量，而把基變量x4換成非基變量，稱x4為出基變量。（在選擇出基變量時(shí)，一定保證消去系統(tǒng)為正消去系統(tǒng)）（最小比值原則）2x1+3x2+x3=100

4x1+2x2+x4=1202x2+x3-1/2x4=40

x1+1/2x2+1/4x4=30x3=40-2x2+1/2x4

x1=30-1/2x2-1/4x4

確定了進(jìn)基變量x1

，出基變量x4

以后，得到新的消去系統(tǒng)：

S=180+x2-（3/2）x4x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)令新的非基變量（x2，x4）=（0，0）t得到新的基礎(chǔ)可行解：x(2)=(30,0,40,0)tS2=180經(jīng)濟(jì)含義：生產(chǎn)甲產(chǎn)品30個(gè)，獲得利潤18000元。

這個(gè)方案比前方案好，但是否是最優(yōu)？分析：S=180+x2-（3/2）x4非基變量x2系數(shù)仍為正數(shù)，確定x2為進(jìn)基變量。在保證常數(shù)項(xiàng)非負(fù)的情況下，確定x3為出基變量。

2x2+x3-1/2x4=40x1+1/2x2+1/4x4=30x2+1/2x3-1/4x4=20x1-1/4x3+3/8x4=20x2=20-1/2x3+1/4x4

x1=20+1/4x3-1/8x4

將其帶入目標(biāo)函數(shù)得到新的消去系統(tǒng)：

S=200-（1/2）x3-（5/4）x4x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)令新的非基變量（x3,x4）t=（0,0）t得到新的基礎(chǔ)可行解：x(3)=(20,20,0,0)tS3=200

經(jīng)濟(jì)含義：分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得利潤20000元。分析：S=200-（1/2）x3-（5/4）x4目標(biāo)函數(shù)中的非基變量的系數(shù)無正數(shù)，S3=200是最優(yōu)值，x(3)=(20,20,0,0)t是最優(yōu)解。該企業(yè)分別生產(chǎn)甲乙產(chǎn)品20個(gè)，可獲得最大利潤20000元。上例給出單純形法基本過程。為理解單純形表的構(gòu)造，把上面求解過程用矩陣來表示。-S+6x1-+4x2=02x1+3x2+x3=1004x1+2x2+x4=120對(duì)應(yīng)的基可行解為（0，0，100，120），目標(biāo)函數(shù)值為0。顯然當(dāng)x1增大時(shí)，目標(biāo)函數(shù)值仍然可以增大，故此基可行解不是最優(yōu)解。令x2=0,x1大于零，（即x1進(jìn)基）當(dāng)x1=30時(shí)，首先x4=0，所以x4出基。

-S+x2

-3/2x4=-1802x2+x3-1/2x4=40x1+1/2x2+1/4x4=30對(duì)應(yīng)的基可行解為（30，0，40，0），目標(biāo)函數(shù)值為180。顯然當(dāng)x2增大時(shí)，目標(biāo)函數(shù)值仍然可以增大，故此基可行解不是最優(yōu)解。令x4=0,x2大于零，（即x2進(jìn)基）當(dāng)x2=20時(shí)，首先x3=0，所以x3出基。S-(1/2)x3-(5/4)x4=-200x2+1/2x3-1/4x4=20x1-1/4x3+3/8x4=20對(duì)應(yīng)的基可行解為（20，20，0，0），目標(biāo)函數(shù)值為200。顯然當(dāng)x3,x4增大時(shí)，目標(biāo)函數(shù)值不會(huì)增大，故此基可行解是最優(yōu)解。單純形法就是根據(jù)上面求解過程的矩陣形式，構(gòu)造單純形表進(jìn)行求解。單純形法計(jì)算步驟：步驟1

將LP化為標(biāo)準(zhǔn)形式,取得初始基可行解,步驟2(最優(yōu)性檢驗(yàn)),若σj≥0(j=1,2,…,n),則得到最優(yōu)解，若否,轉(zhuǎn)入第3步，步驟3(選擇進(jìn)基變量),選擇最小負(fù)的σj

所在列對(duì)應(yīng)的非基變量xj進(jìn)基步驟4(利用最小比值原則選擇出基變量),Cj6400CB基bx1x2x3x40x31000x4120

23104201檢驗(yàn)數(shù)σj

64000x3406x130

021-1/211/201/4檢驗(yàn)數(shù)σj

010-3/24x2206x120011/2-1/410-1/43/8檢驗(yàn)數(shù)σj

00-1/2-5/4例1-20求解線性規(guī)劃問題：minS=x1-3x2+

2x3+4x4s.t.2x1+4x3+x4=6-x1+x2+

3x3=5x1,

x2,

x3,

x4≥0解：問題已是標(biāo)準(zhǔn)型-S+x1-3x2+2x3+4x4=0A=20-41-1130取基B1=（P4，P2）=10=I01Cj1-324CB基bx1x2x3x44x462x25

20-41-1130檢驗(yàn)數(shù)σj

1-3244x462x25

20-41-1130檢驗(yàn)數(shù)σj

-100270-3x231x1810-21/20111/2檢驗(yàn)數(shù)σj

0075例1-21求解線性規(guī)劃問題：

minS=x1-x2s.t.-x1+x2≤

22x1-x2≤

2x1,

x2≥

0解：化標(biāo)準(zhǔn)型：

minS=x1-x2s.t.-x1+x2+x3=22x1-x2+x4=2x1,

x2,

x3,

x4≥

0Cj1-100CB基bx1x2x3x40x320x42

-11102-101檢驗(yàn)數(shù)σj

1-100-1x220x44

-11101011檢驗(yàn)數(shù)σj

0010-1x261x1401211011檢驗(yàn)數(shù)σj

0010根據(jù)解的性質(zhì)：最優(yōu)解X=（0，2）t，

X=（4，6）t連線上的點(diǎn)仍是最優(yōu)解：X=a(0,2)t+(1-a)(4,6)t

(0≤

a≤

1)本題有無窮多組最優(yōu)解。例1-22求解線性規(guī)劃問題：

maxS=2x1+x2s.t.x1-x2≥-52x1-5x2≤

10x1,

x2≥

0解：化標(biāo)準(zhǔn)型：

maxS=2x1+x2

s.t.-x1+x2+x3=52x1-5x2+x4=10x1,

x2,

x3,

x4≥0Cj2100CB基bx1x2x3x40x350x410

-11102-501檢驗(yàn)數(shù)σj

21000x3102x15

0-3/211/21-5/201/2檢驗(yàn)數(shù)σj

0601非基變量X2的檢驗(yàn)數(shù)小于零，但X2所對(duì)應(yīng)的系數(shù)向量:(-3/2,-5/2)t<0所以原問題無最優(yōu)解.例1-23：求解下列線性規(guī)劃問題

maxz=10x1+6x2+4x3

x1+x2+x3≤100

10x1+4x2+5x3≤600

2x1+2x2+6x3≤300

xj≥0（j=1,2,3）化為標(biāo)準(zhǔn)形式maxz=10x1+6x2+4x3+0x4+0x5+0x6x1+x2+x3+x4=10010x1+4x2+5x3+x5=6002x1+2x2+6x3+x6=600xj≥0（j=1,2,…,6）基B1=(P4,P5,P6),基變量x4,x5,x6對(duì)應(yīng)的單純形表T(B1)檢驗(yàn)數(shù)中最大數(shù)10所在列的非基變量x1進(jìn)基min{100/1,600/10,300/2}=600/1010所在行的基變量x5出基以10為基元，換基迭代得B2=(P1,P4,P6)，基變量x1,x4,x6Cj1064000CB基bx1x2x3x4x5x60x41000x56000x6300

1111001045010226001檢驗(yàn)數(shù)σj

1064000Cj1064000CB基bx1x2x3x4x5x60x41000x56000x6300

1111001045010226001檢驗(yàn)數(shù)σj

10640000x44010x1600x6180

03/51/21-1/10012/51/201/10006/550-1/51檢驗(yàn)數(shù)σj

02-10-10檢驗(yàn)數(shù)中有2,Z=60非最優(yōu)解，2所對(duì)應(yīng)的x2進(jìn)基min{40/3/5,60/2/5,180/6/5}=40/(3/5)元素3/5所在行的基變量x4出基以3/5為主元換基迭代得B3=(P1,P2,P6),基變量x1,x2,x6Cj1064000CB基bx1x2x3x4x5x60x44010x1600x6180

03/51/21-1/10012/51/201/10006/550-1/51檢驗(yàn)數(shù)σj

02-10-100x2200/310x1100/30x6100

015/65/3-1/60101/6-2/31/60004-201檢驗(yàn)數(shù)σj

00-8/3-10/3-2/30因檢驗(yàn)數(shù)全部為負(fù)，故最優(yōu)解為x1=100/3,x2=200/3,x3=0最優(yōu)值Z0=2200/3§5人工變量法用單純形法求解線性規(guī)劃，首先要有一個(gè)初始基可行解。在上一節(jié)中，約束都是小于等于，通過加入松弛變量化為標(biāo)準(zhǔn)形后，約束方程的系數(shù)矩陣中含有單位陣，單位陣可以作為初始基，并且很容易得到初始基可行解。但約束不是小于等于時(shí)，尋找初始基可行解比較困難。例如下面的例子。例1-24求解線性規(guī)劃問題：

minf=4x1+x2s.t.3x1+x2=

34x1+3x2≥

6(1.5)x1+2x2≤

4x1,

x2≥

0將其化為標(biāo)準(zhǔn)型：

minf=4x1+x2s.t.3x1+x2=34x1+3x2-x3=

6(1.6)x1+2x2+x4=4x1,

x2,

x3,

x4≥

0

minf=4x1+x2s.t.3x1+x2=34x1+3x2-x3=

6(1.6)x1+2x2+x4=4x1,

x2,

x3,

x4≥

0對(duì)于上面的標(biāo)準(zhǔn)型的線性規(guī)劃，尋找初始基可行解比較困難。為得到初始基可行解，在第一、二兩個(gè)約束中加入兩個(gè)稱為人工變量的非負(fù)變量x5、

x6，得到

minf=4x1+x2

s.t.3x1+x2+x5=34x1+3x2-x3+x6=

6(1.7)x1+2x2+x4=4x1,

x2,

x3,

x4,

x5,

x6≥

0

minf=4x1+x2

s.t.3x1+x2+x5=34x1+3x2-x3+x6=

6(1.7)x1+2x2+x4=4x1,

x2,

x3,

x4,

x5,

x6≥

0我們很容易得到(1.7)的初始基可行解(0,0,0,4,3,6),但他不滿足(1.6)。如果用單純形法對(duì)(1.7)進(jìn)行求解過程中，能將x5、

x6從基變量替換出，都變?yōu)榉腔兞?，?/p>

x5、

x6都取零，則(1.7)的解也滿足(1.6)。下面介紹能將人工變量x5、

x6從基變量替換出的方法。

大M法將

(1.7)的目標(biāo)函數(shù)中人工變量系數(shù)設(shè)置為充分大的正數(shù)M，變成如下的線性規(guī)劃問題：

minf=4x1+x2+Mx5+Mx6

s.t.3x1+x2+x5=34x1+3x2-x3+x6=

6(1.8)x1+2x2+x4=4x1,

x2,

x3,

x4≥

0在用單純形法對(duì)(1.8)進(jìn)行求解過程中，其基可行解中，只有三個(gè)變量不為零。因此，只有x5、

x6都取零時(shí)，才可能達(dá)到最優(yōu)，即將x5、

x6從基變量替換出，都變?yōu)榉腔兞?。上例的大M法求解過程如下：Cj4100MMCB基bx1x2x3x4x5x6Mx53Mx660x44

31001043-1001120100檢驗(yàn)數(shù)σj

4-7M1-4MM0004x1110x620x43

11/3001/3005/3-10-4/3105/301-1/30檢驗(yàn)數(shù)σj

0-(1+5M)/3M0-(4-7M)/30Cj4100MMCB基bx1x2x3x4x5x64x51Mx620x43

11/3001/3005/3-10-4/3105/301-1/30檢驗(yàn)數(shù)σj

0-(1+5M)/3M0-(4-7M)/304x13/51x26/50x41

101/503/5-1/501-3/50-4/53/500111-1檢驗(yàn)數(shù)σj

00-1/50-8/5+M1/5+M4x12/51x29/50x31

100-1/52/500103/5-1/5000111-1檢驗(yàn)