第5章線性模型及求解

線性規(guī)劃問題的求解方法一、圖解法特點(diǎn)：1、只能求解只有兩個變量的線性規(guī)劃問題（適用范圍比較?。?、不需要對模型進(jìn)行標(biāo)準(zhǔn)化二、單純形法特點(diǎn)：1、可以求解任意多個變量的問題（適用范圍比較廣）2、求解前必須將模型化為標(biāo)準(zhǔn)型的線性規(guī)劃問題第五章單純形法線性規(guī)劃問題的標(biāo)準(zhǔn)形式為了使線性規(guī)劃問題的解法標(biāo)準(zhǔn)，就要把一般形式化為標(biāo)準(zhǔn)形式這可是個重點(diǎn)哦！21bi,xj≥0(i=1,2,…,m;j=1,2,…,n)43不標(biāo)準(zhǔn)化標(biāo)準(zhǔn)的方法：

目標(biāo)函數(shù)為min型，價值系數(shù)一律反號。令z=-z=-CX,有minz=-max[-z]=-maxzExample:

minZ=x1+2x2+

x3maxZ’=-x1-2x2-

x31MaxzMinz’ab注意：z與z’的解相同但目標(biāo)函數(shù)值相差一負(fù)號zz’

第i個約束的bi

為負(fù)值，則該行左右兩端系數(shù)同時反號，同時不等號也要反向Example:

4x1-2x2-3x3=-6-4x1+2x2+3x3=6

第i個約束為型，在不等式左邊增加一個非負(fù)的變量xn+i

，稱為松弛變量；同時令cn+i

=0Example:

-2x1+x2+x39-2x1+x2+x3+x4=9

第i個約束為型，在不等式左邊減去一個非負(fù)的變量xn+i

，稱為剩余變量；同時令cn+i

=0Example:

-3x1+x2+2x34-3x1+x2+2x3–x5=4若xj0，令

xj=-xj

，代入非標(biāo)準(zhǔn)型，則有xj

0若xj不限，令

xj=xj-xj，xj

0，xj0，代入非標(biāo)準(zhǔn)型234

變換舉例：解:令z`=-z，x3=x`3-x``3，并引入剩余變量x4和松弛變量x5、x6，將其代如原數(shù)學(xué)模型，則原模型轉(zhuǎn)換為如下標(biāo)準(zhǔn)形式例題將下列線性規(guī)劃模型化為標(biāo)準(zhǔn)形式，寫出相應(yīng)的矩陣表達(dá)式，并寫出相應(yīng)的技術(shù)系數(shù)矩陣A、資源向量b、價格系數(shù)向量C、決策變量X，指出其松弛變量和剩余變量。

minZ=-x1-2x2+x3-x4-4x5+2x6x1+x2+x3+x4+x5+x6≤62x1-x2-2x3+x4≤-4x3+x4+2x5+x6=

4X1,x2,x3≥0,x4,x5≤0,x6正負(fù)不限S.t.maxZ`=x1+2x2-x3+x`4+4x`5-2x`6+2x``6+0x7+0x8x1+x2+x3-x`4-x`5+x`6-x``6+x7=6-2x1+x2+2x3+x`4

=4x3-x`4-2x`5+x`6-x``6-x8=4x1,x2,x3,x`4,x`5,x`6,x``6,x7,x8≥0S.t.解：令Z`=-Z,x`4=-x4,x`5=-x5,x6=x`6-x``6

minZ=-x1-2x2+x3-x4-4x5+2x6x1+x2+x3+x4+x5+x6≤62x1-x2-2x3+x4=

-4x3+x4+2x5+x6≥4X1,x2,x3≥0,x4,x5≤0,x6正負(fù)不限S.t.

maxZ`=CXS.t.AX=bX≥0X=[x1,x2,x3,x`4,x`5,x`6,x``6,x7,x8]TC=[1,2,-1,1,-4,-2,2,0,0]b=[6,4,4]T

A=111-1-11-110-212100000001-1-21-101其矩陣形式表示為：其中：maxZ`=x1+2x2-x3+x`4+4x`5-2x`6+2x``6+0x7+0x8x1+x2+x3-x`4-x`5+x`6-x``6+x7=6-2x1+x2+2x3+x`4

=4x3-x`4-2x`5+x`6-x``6-x8=4x1,x2,x3,x`4,x`5,x`6,x``6,x7,x8≥0S.t.松弛變量：x7剩余變量：x8教科書:P31練習(xí)（1）課堂操練要求：將其化為標(biāo)準(zhǔn)形式，寫出相應(yīng)的矩陣表達(dá)式，并寫出相應(yīng)的技術(shù)系數(shù)矩陣A、資源向量b、價格系數(shù)向量C、決策變量X，指出其松弛變量和剩余變量。教科書:P31練習(xí)（2）課外作業(yè)要求：將其化為標(biāo)準(zhǔn)形式，寫出相應(yīng)的矩陣表達(dá)式，并寫出相應(yīng)的技術(shù)系數(shù)矩陣A、資源向量b、價格系數(shù)向量C、決策變量X，指出其松弛變量和剩余變量。線性規(guī)劃問題標(biāo)準(zhǔn)型的矩陣形式：

MaxZ=CX

s.t.AX=bX0

a11a12….a1nb1A=a21a22….a2nb

=b2………am1am2….amnbm一、關(guān)于標(biāo)準(zhǔn)型解的若干基本概念

a11a12…….a1nA=a21a22…….a2n……………am1am2……..amnP1,P2,…

Pnx1,x2,

…..,xn=(P1,P2,…

Pn)假若標(biāo)準(zhǔn)型有n個變量，m個約束行且m<=n“基”的概念在標(biāo)準(zhǔn)型中，系數(shù)矩陣有n列，即

A=(P1,P2,…,Pn)A中線性獨(dú)立的m列，構(gòu)成該標(biāo)準(zhǔn)型的一個基，即

B=(P1,P2,…,Pm)，|B|0

P1,P2

,…,Pm稱為基向量，

其余的Pm+1,Pm+2

,…,Pn稱為非基向量與基向量對應(yīng)的變量稱為基變量，記為

XB=(x1,x2,…,xm)T，其余的變量稱非基變量，記為XN=(xm+1,xm+2,…,xn)T

，故有

X=(XB,XN)T

舉例說明一000032020001010x1x2x4x3001300321=目標(biāo)函數(shù)約束條件行列式|B1|≠0x1,x2,x3為基變量,x4為非基變量p1,p2,p3為基向量,p4為非基向量B1為A的基矩陣A=B1=標(biāo)準(zhǔn)型的線性規(guī)劃問題舉例說明二000030020011010x1x2x4x3001300321=目標(biāo)函數(shù)約束條件行列式|B2|=0x3,x4會不會同時為基變量？B2為A的基矩陣？A=B2=標(biāo)準(zhǔn)型的線性規(guī)劃問題線性規(guī)劃的基矩陣、基向量、非基向量、基變量、非基變量=目標(biāo)函數(shù)約束條件行列式≠0基矩陣右邊常數(shù)Cnm可行解滿足約束條件和非負(fù)條件的解X稱為可行解，基解(基本解、基礎(chǔ)解)令非基變量

XN=0，求得基變量

XB的值：

AX=b令A(yù)=(B,N),X=(XB,XN)

TBXB+NXN=b令

XN=0得XB=B1b

因此X=（B1b，0）T稱為基本解(基解)基可行解（基本可行解、基礎(chǔ)可行解）基解

X

的非零分量都0時，稱為基本可行解，否則為基本非可行解基本可行解的非零分量個數(shù)<

m

時，稱為退化解最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解

線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解退化解最優(yōu)解基、可行基、最優(yōu)基

可行解、基解和基可行解舉例說明

系數(shù)矩陣:A=11001101001001x1x2x3x4x5

系數(shù)矩陣:A=11001101001001x1x2x3x4x5100010001

B=x3x4x5211100x1x2

N=A=(B,N)令非基變量X1=0,X2=0得：X3=10,X4=8,X5=7因此可得一基解：X=(0,0,10,8,7)T行列式|B|≠0B為A的基矩陣知識點(diǎn)總結(jié)n個變量，m個約束條件的標(biāo)準(zhǔn)形的線性規(guī)劃問題（秩為m）中最多有（

Cnm

）個基矩陣n個變量，m個約束條件的標(biāo)準(zhǔn)形的線性規(guī)劃問題（秩為m）中最多有（

Cnm

）個基解n個變量，m個約束條件的標(biāo)準(zhǔn)形的線性規(guī)劃問題（秩為m）的一個基矩陣B中有（m

）個基變量，（n-m）個非基變量n個變量，m個約束條件的標(biāo)準(zhǔn)形的線性規(guī)劃問題（秩為m）的最優(yōu)解中最多有（

m

）個非零分量n個變量，m個約束條件的標(biāo)準(zhǔn)形的線性規(guī)劃問題（秩為m）的最優(yōu)解中最少有（

n-m

）個零分量定理1.1

線性規(guī)劃問題的可行解集是凸集。（即連接線性規(guī)劃問題任意兩個可行解的線段上的點(diǎn)仍然是可行解。)定理1.2

線性規(guī)劃問題的可行解x為基可行解的充分必要條件是：x的非零分量所對應(yīng)的系數(shù)矩陣A的列向量線性無關(guān)。定理1.3

線性規(guī)劃問題的可行解集D中的點(diǎn)x是頂點(diǎn)的充分必要條件是：x是基礎(chǔ)可行解。二、線性規(guī)劃問題解的基本性質(zhì)推論1.1：可行解集D中的頂點(diǎn)個數(shù)是有限的。推論1.2

若可行解集D有界，則線性規(guī)劃問題的最優(yōu)解，必定在D的頂點(diǎn)上達(dá)到。注1：若可行解集D無界，則線性規(guī)劃問題可能有最優(yōu)解，也可能無最優(yōu)解。若有最優(yōu)解，也必在頂點(diǎn)上達(dá)到。注2：有時目標(biāo)函數(shù)也可能在多個頂點(diǎn)上達(dá)到最優(yōu)值。這些頂點(diǎn)的凸組合也是最優(yōu)值。（有無窮多最優(yōu)解）基本思想：從可行域中某一個頂點(diǎn)開始,判斷此頂點(diǎn)是否是最優(yōu)解，如不是則再找另一個使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解，直到找到一個頂點(diǎn)為其最優(yōu)解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止。這里，可行域的頂點(diǎn)已經(jīng)不再象圖解法中那樣直觀了，在單純形法中的可行域的頂點(diǎn)就是基本可行解，找到的第一個可行域的頂點(diǎn)叫做初始基本可行解。三、單純形法的基本思路和原理單純形法的基本步驟：初始概念回顧前提是標(biāo)準(zhǔn)型的線性規(guī)劃問題，假設(shè)n個變量，m個約束條件基（基矩陣）、可行基、最優(yōu)基基解、基可行解、最優(yōu)解、退化解決策變量、松弛變量、剩余變量、基變量m、非基變量n-m基向量m、非基向量n-m系數(shù)矩陣A：m*n基矩陣B:m*m最多有Cnm個基解:非零分量<=m（一）、單純形法的基本思路首先，將線性規(guī)劃問題化為標(biāo)準(zhǔn)形式；其次，尋找一個初始可行基，為確?；鶠榭尚谢?，我們這里以單位矩陣作為初始可行基，即可求出初始基可行解第三，判斷該可行解是否是最優(yōu)解，如果是，明確解的類型，結(jié)束；如果不是，繼續(xù)換基迭代，找出使目標(biāo)函數(shù)更優(yōu)的基可行解。第四，返回第三，循環(huán)往復(fù)直到找出最有解Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5x3x4x5非奇異子陣，做為一個基（可行基）基變量:x3x4x5非基變量:x1x2例1maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.可見，單位矩陣作為初始可行基，基變量在目標(biāo)中的系數(shù)為0將基變量用非基變量線性表示，即x3=8-x1x4=12-2x2x5=36-3x1-4x2

令非基變量x1=0，x2=0，找到一個初始基可行解：

x1=0，

x2=0，x3=8，x4=12，

x5=36即X0=(0,0,8,12,36)T一個可行解就是一個生產(chǎn)方案，在上述方案中兩種產(chǎn)品都不生產(chǎn)，利潤Z=0

。1.求初始基可行解

確定進(jìn)基變量

Z=3x1+5x2

+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36從目標(biāo)函數(shù)Z=3x1+5x2+0x3+0x4+0x5可知：非基變量x1和x2的系數(shù)均為正數(shù)，生產(chǎn)哪種產(chǎn)品都會增加利潤。

增加單位產(chǎn)品對目標(biāo)函數(shù)的貢獻(xiàn)，這就是檢驗(yàn)數(shù)的概念。因?yàn)閤2的系數(shù)大于x1的系數(shù)，即生產(chǎn)單位乙產(chǎn)品比甲產(chǎn)品利潤更高一些，對目標(biāo)函數(shù)的貢獻(xiàn)大，故應(yīng)優(yōu)先多生產(chǎn)乙產(chǎn)品。（最大檢驗(yàn)數(shù)原則），把非基變量x2換成基變量，稱x2為進(jìn)基變量。同時為保證基變量的個數(shù)必須確定一個離基變量。（在選擇離基變量時，一定保證所有的變量是正的）（最小比值原則）2.第一次迭代

бX0=(0,0,8,12,36)T確定離基變量基變量用非基變量線性表示x3=8–x1x4=12-2x2

x5=36-3x1-4x2保持原非基變量x1=0，x2變成基變量時應(yīng)保證x3,x4,,x5非負(fù)，即有2.第一次迭代（續(xù)）x3=8≥0x4=12-2x2≥0x5=36-4x2≥0x2≤12/2x2≤36/4

x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥02.第一次迭代（續(xù)）主行主列主元x1+0x2+x3=82x2+x4=123x1+4x2+x5=36

進(jìn)基變量x2所在列為主列，離基變量x4所在行為主行主行和主列交叉項(xiàng)的系數(shù)為主元素

為了確保新構(gòu)成的基矩陣為可行基矩陣，將x2的系數(shù)列向量P2化為單位的，即主元素變?yōu)?，主列中其它項(xiàng)的系數(shù)化為0，使其與其它基變量的系數(shù)向量組成為單位矩陣基變換進(jìn)行初等變換，變主元為1，主列為單位列向量。2.第一次迭代（續(xù)）x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

x1+x3=8

x2+1/2x4=6

3x1+-2x4+x5=12

x1+0x2+x3=82x2+x4=123x1+4x2+x5=36Z=3x1+5x2+0x3+0x4+0x5

x1+x3=8

x2+1/2x4=63x1+4x2+x5=36Z=3x1+5x2+0x3+0x4+0x5Z=3x1+5x2+0x3+0x4+0x5Z=3x1+0x2+0x3–5/2x4+0x52.第一次迭代（續(xù)）將基變量用非基變量線性表示，即x3=8–x1x2=6-1/2x4

x5=12-3x1+4x4令非基變量x1=0，x4=0，找到另一個基可行解

x1=0，

x2=6，x3=8，x4=0，

x5=12即X1=(0,6,8,0,12)T原目標(biāo)函數(shù)Z=30這個方案比前方案好，但是否是最優(yōu)？確定進(jìn)基變量3.第二次迭代

第一次迭代結(jié)果

x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

Z=3x1+0x2+0x3–5/2x4+0x5=30目標(biāo)函數(shù)Z系數(shù)變化為:Z=3x1+0x2+0x3–5/2x4+0x5=-30非基變量x1的系數(shù)1=3（檢驗(yàn)數(shù)）為正數(shù)，確定x1為進(jìn)基變量。X4仍然為非基變量確定離基變量3.第二次迭代（續(xù)）x3=8-x1≥0x2=6≥0

x5=12-3x1≥0x1≤8/1x1≤12/3基變量用非基變量線性表示

x3=8–x1x2=6-1/2x4x5=12-3x1+4x4保持原非基變量x4=0，x1變成基變量時應(yīng)保證x2,x3,,x5非負(fù)，即基變換變主元為1，主列為單位列向量。3.第二次迭代（續(xù)）

x1+x3=8

x2+1/2x4=6

x1+-2/3x4+1/3x5=4

Z=3x1+0x2+0x3–5/2x4+0x5

x3+2/3x4-1/3x5=4

x2+1/2x4=6x1+-2/3x4+1/3x5=4

Z=3x1+0x2+0x3–5/2x4+0x5x3+2/3x4-1/3x5=4

x2+1/2x4=6x1+-2/3x4+1/3x5=4

Z=0x1+0x2+0x3-1/2x4-x5

1x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

Z=3x1+0x2+0x3–5/2x4+0x53.第二次迭代（續(xù)）將基變量用非基變量線性表示，即x3=4–2/3x4+1/3x5x2=6-1/4x4x1=4+2/3x4-1/3x5

令非基變量x4=0，x5=0，又找到一個基可行解

目標(biāo)函數(shù)Z系數(shù)變化為:

Z=42+0x1+0x2+0x3-1/2x4-x5=42x1=4，

x2=6，x3=4，x4=0，

x5=0即X2=(4,6,4,0,0)T檢驗(yàn)數(shù)σj非正，得最優(yōu)解X*=(4,6,4,0,0)T，Z*=42單純形法的幾何意義x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)DX0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX1=(4,6,4,0,0)TmaxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

為了計(jì)算步驟更加清晰，以下列表格的方式求解：CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000

35000-12/2=636/4=9檢驗(yàn)數(shù)j81010060101/2012300-21x3x2x5050

300-5/208-4CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000

35000-12/2=636/4=9CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010060101/2012300-21x3x2x5050

300-5/208-4檢驗(yàn)數(shù)j40012/3-1/360101/204100-2/31/3x3x2x1053

000-1/2-1原問題具有唯一最優(yōu)解

:X*=(4,6,4,0,0)T，Z*=42c1x10c2x20CT=……X=..….0=……cnxn0

并且r(A)=m<n.（二）、單純形法的基本原理線性規(guī)劃標(biāo)準(zhǔn)型的矩陣形式：MaxZ=CXs.t.

AX=b

X≥0

a11a12….a1nb1A=a21a22….a2nb

=

b2……am1am2….amn

bmAX=bZ=CX設(shè)A=（B,N）（B為一個基）

XT=(XB,XN)TC=(CB,CN)則有：AX=（B,N）(XB,XN)T=B

XB+N

XN=b移項(xiàng)得：B

XB=b-N

XN因?yàn)锽為基,故有XB=B-1b-B-1NXN

-----------（1）又因?yàn)閆=CX=

(CB,CN)(XB,XN)T=CBXB+CNXN

=CB（B-1b-B-1NXN）+CNXN=

CBB-1b+(CN-

CBB-1N)

XN--------（2）常數(shù)項(xiàng)非基變量的系數(shù)，即檢驗(yàn)數(shù)基變量的系數(shù)為0AX=bZ=CXXB=B-1b-B-1NXN-----------（1）Z=CBB-1b+(CN-

CBB-1N)

XN-----------（2）由（1）令非基變量XN=0，則有：XB

=B-1b所以XT=(XB,XN)T=（B-1b,0)T

代入（2），得到：

Z=

CBB-1b目標(biāo)函數(shù)中非基變量的系數(shù)C

N-

CBB-1N即為檢驗(yàn)數(shù)由（2）可知道：當(dāng)≤0時，Z沒有增大的可能了，CBB-1b就是原問題的最優(yōu)值。一個基可行解CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010060101/2012300-21x3x2x5050

300-5/20單純形表格中的檢驗(yàn)數(shù)有兩種方法得到：一種是迭代中的初等變換，一種是利用公式計(jì)算；初始單純形表中的檢驗(yàn)數(shù)只能用公式計(jì)算方法得到；中間單純形表兩種方法都可以，一般先采用迭代方法得到，再使用公式計(jì)算進(jìn)行驗(yàn)證，可以確保相鄰兩張表中數(shù)據(jù)的準(zhǔn)確無誤。j=Cj-CBB-1pj=Cj-CBp`j

（三）、表格形式的單純形法

利用單純形表的方法求解線性規(guī)劃——重點(diǎn).

此項(xiàng)內(nèi)容是本章的重點(diǎn)，學(xué)習(xí)中應(yīng)注意掌握表格單純形法求解線性規(guī)劃問題的基本過程。要通過讀懂教材內(nèi)容以及大量練習(xí)來掌握。表格單純形法，是對上節(jié)討論的方法步驟進(jìn)行具體化、規(guī)范化、表格化的結(jié)果。1、單純形法表CjC1C2…Cj…CnθiCBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1n1CB2xB2b2a21a22…a2j…a2n2………………………CBnxBnbmam1am2…amj…amnmj→12…j…n①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。②找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。③計(jì)算各非基變量xj的檢驗(yàn)數(shù)j=Cj-CBPj′，若所有j≤0，則問題已得到最優(yōu)解（唯一最優(yōu)或無窮多最優(yōu)解），停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個k所對應(yīng)的系數(shù)列向量Pk≤0，則此問題是無界解，停止計(jì)算，否則轉(zhuǎn)入下步。⑤根據(jù)max{j｜j＞0}=k原則，確定xk為換入變量(進(jìn)基變量)，再按規(guī)則計(jì)算：=min{bi/aik|aik＞0}=bl/aik

確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。⑥以aik為主元素進(jìn)行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③步。2、單純形法的計(jì)算步驟

課堂舉例用單純形法求解下述線性規(guī)劃問題首先化為標(biāo)準(zhǔn)形如下：+0x3+0x4CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x3x498001050034105201105009/38/5CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x3x121/501010500014/51-3/512/501/5010-28/5CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x2x13/251010500015/14-3/1410-1/72/700-5/14-25/1413/28/2原問題具有唯一最優(yōu)解

:

maxZ=12x1+8x2+5x33x1+2x2+x3≤20x1+x2+x3≤1112x1+4x2+x3≤48x1,x2,x3≥0課堂作業(yè)用單純形法求解下列問題:minZ=x1+2x2-x32x1+2x2-x3≤4X1-2x2+2x3≤8x1+x2+x3≤5x1,x2,x3≥0maxZ=4x1+x2x1+3x2≤74X1+2x2≤9x1,x2≥0課后作業(yè)用單純形法求解下列問題:課堂例題1用單純形法求解下列線性規(guī)劃問題

CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x62-11000x4x5x600060311100101-1201060/310/120/12011-1001

2-11000+0x4+0x5+

0x6CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x62-11000x4x1x60203004-51-30101-1201030/4--10/21002-30-11

01-30-20CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x62-11000x4x1x202-1100011-1-215101/201/21/2501-3/20-1/21/2

00-3/20-3/2-1/2原問題具有唯一最優(yōu)解

:目標(biāo)函數(shù)為Max的標(biāo)準(zhǔn)型線性規(guī)劃問題的單純性表格中唯一最優(yōu)解的判斷標(biāo)準(zhǔn)如下:當(dāng)所有非基變量的檢驗(yàn)數(shù)都＜0時當(dāng)所有非基變量的檢驗(yàn)數(shù)都≤0且存在某個非基變量xj的檢驗(yàn)數(shù)為0，而它所對應(yīng)的系數(shù)Pj全部≤0maxZ=

40x1+45x2+25x32x1+x2+x3≤1003x1+3x2+2x3≤120x1,x2,x3≥0S.t.maxZ=

40x1+45x2+25x3+0x4+0x52x1+x2+x3+x4=1003x1+3x2+2x3+x5=120x1,x2,x3,x4,x5≥0S.t.解:首先，化為標(biāo)準(zhǔn)型:其次，列出初始單純形表格:課堂例題2CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x540452500x4x5001002311012033201

40452500100/3120/3CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x540452500x2x5450100/32/311/31/3020101-11

10010-150100/220/1CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x540452500x2x145402001-1/31-2/320101-11

000-5-10CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x540452500x2x3452580/31/3102/3-1/320101-11

000-5-10最優(yōu)解為：x*=(20,20,0)T最優(yōu)值為：Z*=1700最優(yōu)解為：x*=(0,80/3,0)T最優(yōu)值為：Z*=1700有兩個最終單純形表，所以有兩個最優(yōu)解：

x1*=(20,20,0)T

x2*=(0,80/3,0)T

最優(yōu)值為：Z*=1700

因此原問題具有無窮多個最優(yōu)解目標(biāo)函數(shù)為Max的標(biāo)準(zhǔn)型線性規(guī)劃問題的單純性表格中無窮多最優(yōu)解的判斷標(biāo)準(zhǔn)如下:

當(dāng)所有非基變量的檢驗(yàn)數(shù)都≤0且存在某個非基變量xj的檢驗(yàn)數(shù)為0，而它所對應(yīng)的系數(shù)Pj不全≤0（即存在＞0的系數(shù)）解

:+0x5+0x6+

0x7課堂例題3CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x762108000x5x6x70002056-4-4100253-328010--25/210/1104-213001

62108000θiCjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x762108000x5x6x300106021-2081045-510201-2--5/1--104-213001

-34220-2200-10θiCjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x762108000x5x2x30210701100121205-510201-220-601702-3

7600-660-2234原問題具有無界解

目標(biāo)函數(shù)為Max的標(biāo)準(zhǔn)型線性規(guī)劃問題的單純性表格中無界解的判斷標(biāo)準(zhǔn)如下:

當(dāng)存在某個非基變量的檢驗(yàn)數(shù)＞

0且它所對應(yīng)的系數(shù)Pj全部≤0原問題解的類型的判斷

對于所有約束條件都是≤的線性規(guī)劃問題的解的類型有三種：唯一最優(yōu)解無窮多最優(yōu)解無界解CjCBXBb檢驗(yàn)數(shù)80-512x3x10331-3010110-3x1x2x3x43200原問題具有無界解判斷原問題解的類型(一)CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x535000x3x2x105340012/3-1/360101/204100-2/31/3

000-1/2-1原問題具有唯一最優(yōu)解

:X*=(4,6,4,0,0)T，Z*=42判斷原問題解的類型(二)CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x540452500x2x145402001-1/31-2/320101-11

000-5-10判斷原問題解的類型(三)原問題具有無窮多個最優(yōu)解CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x54045-2500x2x145402001-1/31-2/32010-1/4-11

000-5-10判斷原問題解的類型(四)原問題具有唯一最優(yōu)解例：分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對照指出單純形表中的各基本可行解對應(yīng)圖解法中可行域的哪一頂點(diǎn).課堂練習(xí)由圖知：單純形法：化為標(biāo)準(zhǔn)形如下：CjθiCBXBb檢驗(yàn)數(shù)jx1x2x3x410500x3x4009341085201

10500

9/38/5CjCBXBb檢驗(yàn)數(shù)jx1x2x3x410500x3x4009341085201

10500

CjCBXBb檢驗(yàn)數(shù)jx1x2x3x410500x2x15103/2015/14-3/14110-1/72/7

00-5/14-25/14

最終單純形表初始單純形表原問題具有唯一最優(yōu)解

:①將線性規(guī)劃問題化成標(biāo)準(zhǔn)型。②找出或構(gòu)造一個m階單位矩陣作為初始可行基，建立初始單純形表。③計(jì)算各非基變量xj的檢驗(yàn)數(shù)j=Cj-CBPj′，若所有j≤0，則問題已得到最優(yōu)解（唯一最優(yōu)或無窮多最優(yōu)解），停止計(jì)算，否則轉(zhuǎn)入下步。④在大于0的檢驗(yàn)數(shù)中，若某個k所對應(yīng)的系數(shù)列向量Pk≤0，則此問題是無界解，停止計(jì)算，否則轉(zhuǎn)入下步。⑤根據(jù)max{j｜j＞0}=k原則，確定xk為換入變量(進(jìn)基變量)，再按規(guī)則計(jì)算：=min{bi/aik|aik＞0}=bl/aik

確定xBl為換出變量。建立新的單純形表，此時基變量中xk取代了xBl的位置。⑥以aik為主元素進(jìn)行迭代，把xk所對應(yīng)的列向量變?yōu)閱挝涣邢蛄?，即aik變?yōu)?，同列中其它元素為0，轉(zhuǎn)第③步。單純形法的計(jì)算步驟

CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1n1CB2xB2b2a21a22…a2j…a2n2………………………CBmxBmbmam1am2…amj…amnm檢驗(yàn)數(shù)j12…j…nbi,xj≥0(i=1,2,…,m;j=1,2,…,n)Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5x3x4x5例1maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.分析CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000

35000Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始單純形表格Z=3x1+5x2+0x3+0x4+0x5x1-x3=82x2-x4=123x1+4x2-x5=36x1,x2,x3,x4,x5≥0例1maxZ=

3x1+5x2x1

≥82x2

≥123x1+4x2

≥36x1≥0,x2≥0S.t.分析úúú?ùx1x2x3x4x5êêê?é=-100-100043020-101Aúúú?ùêêê?é=100010001B100010001x6x7x8x6x7x8人工變量+x6

=8+x7

=12+x8=36x6,x7,x8

≥0CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x7x8810-100100x6x7x8x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始單純形表格部分+x6

=8+x7

=12+x8=36x6,x7,x8

≥012020-10010363400-1001Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2-x4=123x1+4x2-x5=36x1,x2,x3,x4,x5≥0x1x2x3x4x5例1maxZ=

3x1+5x2x1

≤82x2

≥123x1+4x2

≥36x1≥0,x2≥0S.t.分析úúú?ùêêê?é=-100-100043020

101Aúúú?ùêêê?é=100010001B100100x6x7x3x6x7人工變量=8+x6

=12+x7=36x6,x7≥0CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x6x781010000x3x6x7x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始單純形表格部分12020-1010363400-101=8+x6

=12+x7=36x6,x7≥0Z=3x1+5x2+0x3+0x4+0x5x1+x3=82x2-x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0x1x2x3x4

x5例1maxZ=

3x1+5x2x1

≤82x2

≥123x1+4x2

≤

36x1≥0,x2≥0S.t.分析úúú?ùêêê?é=100-100043020

101Aúúú?ùêêê?é=100010001B010x6x3x6x5人工變量=8+x6=12=36x6≥0CjCBXBb檢驗(yàn)數(shù)jx1x2x3x4x5x68101000x3x6x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0初始單純形表格部分12020-10136340010=8+x6

=12=36x6≥0單純形法的進(jìn)一步討論主要討論初始基本可行基不明顯時常用的方法，要弄清它的原理，并通過例題掌握這些方法，同時進(jìn)一步熟悉用單純形法解題。考慮一般問題：

bi>=0i=1,…,m

Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0此時若系數(shù)矩陣中無單位矩陣，則可以引入人工變量。Maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn+

xn+1

=b1a21x1+a22x2+…+a2nxn

+

xn+2

=b2s.t.…

am1x1+am2x2+…+amnxn+xn+m

=bm

x1，x2，…，xn≥0此時人工變量xn+1、xn+2、….xn+m

的系數(shù)向量構(gòu)成一個m*m的單位矩陣，因此可以作為初始可行基。但是由于人工變量在原問題的解中是不能存在的，因此應(yīng)盡快被迭代出去，為此人工變量在目標(biāo)函數(shù)中對應(yīng)的價值系數(shù)應(yīng)具有懲罰性，稱為罰系數(shù)。罰系數(shù)的取值視解法而定.兩種方法大M法兩階段法s.t.a11x1+a12x2+…+a1nxn

+xn+1

=b

a21x1+a22x2+…+a2nxn

+

xn+2

=b2

…………

…………

am1x1+am2x2+…+amnxn

+xn+m

=bm

xj≥0（j=1,2,…,n,n+1,…,n+m）Maxz=c1x1+c2x2+…+cnxn-M(xn+1+xn+2+…+xn+m

)1、大M法例：用大M法求解下列問題:maxz=3x1-x2-x3s.t.x1-2x2+x3≤11-4x1+x2+2x3≥3-2x1+x3=1x1,x2,x3≥0maxz=3x1-x2-x3+0x4+0x5x1-2x2+x3+x4=11-4x1+x2+2x3–x5=3s.t.2