第三講　單純形法

第1章線性規(guī)劃與單純形法第1節(jié)線性規(guī)劃問題及其數(shù)學(xué)模型第2節(jié)線性規(guī)劃問題的幾何意義第3節(jié)單純形法第4節(jié)單純形法的計(jì)算步驟第5節(jié)單純形法的進(jìn)一步討論第6節(jié)應(yīng)用舉例1線性規(guī)劃問題解的關(guān)系圖AX=b的解基解若非基變量為0基可行解基最優(yōu)解B是A的M階子矩陣基B若|B|

0可行基B當(dāng)B-1b

0最優(yōu)基B若基變量取非負(fù)若對應(yīng)目標(biāo)函數(shù)值最優(yōu)2非可行解線性規(guī)劃問題解的關(guān)系圖（2）可行解基可行解基解基可行基最優(yōu)基3二.幾個(gè)基本定理定理1若線性規(guī)劃問題存在可行解,則問題的可行域是凸集.定理2線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問題可行域(凸集)的頂點(diǎn).定理3若可行域有界,線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域頂點(diǎn)上達(dá)到最優(yōu).引理2若K是有界凸集，則任何一點(diǎn)X∈K可表示為K的頂點(diǎn)的凸組合。引理1線性規(guī)劃的可行解X＝(x1,x2,…,xn)T為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。4單純形法5單純形法引例考慮線性規(guī)劃問題：

約束方程的系數(shù)矩陣A很顯然A中的后3列是線性無關(guān)的，它們構(gòu)成一個(gè)基基B對應(yīng)的變量x3,x4,x5是基變量，則6單純形法引例（2）即：

將它們代入目標(biāo)函數(shù)中得令非基變量x1=x2=0,得目標(biāo)值Z＝0

一個(gè)基可行解X(0)＝(0,0,8,16,12)為了使目標(biāo)函數(shù)能更大，讓x2變成基變量，原基變量的x3，x4，x5要有一個(gè)變?yōu)榉腔兞慨?dāng)x1=0,由最上式得從上式可看出，當(dāng)x2=3仍可保證所有變量非負(fù)，并使目標(biāo)函數(shù)增大7單純形法引例（3）為了得到以x3,x4,x2為基變量的一個(gè)基可行解，則對左邊方程中的x2與x5互換得再令非基變量x1=x5=0,得目標(biāo)值Z＝9

一個(gè)基可行解X(0)＝(0,3,2,16,0)為了使目標(biāo)函數(shù)能更大，讓x1變成基變量，原基變量的x3，x4，x2要有一個(gè)變?yōu)榉腔兞磕繕?biāo)函數(shù)變?yōu)?單純形法引例（4）這樣如此下去，可得X(2)＝(2,3,0,8,0)為了使目標(biāo)函數(shù)能更大，讓x1變成基變量，原基變量的x3，x4，x2要有一個(gè)變?yōu)榉腔兞看藭r(shí)目標(biāo)函數(shù)變?yōu)閄(3)＝(4,2,0,0,4)由于目標(biāo)函數(shù)中的變量系數(shù)都小于等于0，所以X(3)＝（4,2,0,0,4)為最優(yōu)解，最優(yōu)值Z＊＝1491011單純形法迭代原理：確定初始可行解12最優(yōu)性檢驗(yàn)和解的判別檢驗(yàn)數(shù)13單純形解題步驟：（已知初始可行基）求最大化時(shí)一、作對應(yīng)B的單純形表：14二、判別若檢驗(yàn)數(shù)全小于等于零，則基B所對應(yīng)的基礎(chǔ)可行解X就是最優(yōu)解，終止。若存在檢驗(yàn)數(shù)大于零，但所對應(yīng)的換入變量Xk的系數(shù)向量Pk≤0,則原問題無最優(yōu)解，終止。若存在檢驗(yàn)數(shù)大于零，且對應(yīng)的系數(shù)列有大于零的分量，則需要換基迭代。15三、換基迭代確定換入變量Xk，其中max(σj>0)=σk,xk為換入變量確定換出基變量Xr,根據(jù)最小比值原則min(bi/aik,aik

>0,1≤i≤m)=bl/blkalk為主元素,Xl為換出基變量。16對單純形表進(jìn)行初等行變換（主元運(yùn)算）得到新的單純形表。經(jīng)過上述有限次的換基迭代，就可得到原問題的最優(yōu)解，或判定無最優(yōu)解。17六．單純形法舉例1(1)例用單純形法解下列線性規(guī)劃

解:將原問題化為標(biāo)準(zhǔn)形式則基變量為x3,x4,x5

取B1=(P3,P4,P5)=I

18最優(yōu)解X*=(4,2,0,1,0)T

最優(yōu)值Z*=1019六．單純形法舉例2(1)例2:用單純形法解下列線性規(guī)劃

解:將原問題化為標(biāo)準(zhǔn)形式取初始可行基為B1=(P3,P4,P5)=I

20

XB

b

X1X2X3X4X5

X3X4X5

438

101000101012001

-Z

012000

T(B1)X3X2X5-Z4101003010102100-21-6100-20

T(B2)六．單純形法舉例2(2)21

XB

b

X1X2X3X4X5

X3X2X5

432

1010001010100-21

-Z-6

100-20

T(B2)X3X2X1-Z2001221-80000-1

T(B3)六．單純形法舉例2(3)最優(yōu)解X*=(2,3,2,0,0)T

最優(yōu)值Z*=822

XB

b

X1X2X3X4X5

X3X2X1

232

0012-101010100-21-Z-8

0000-1

T(B3)X4X2X1-Z1001/21-1/2201-1/201/2410100-80000-1

T(B4)最優(yōu)解X*=(2,3,2,0,0)T

最優(yōu)值Z*=8六．單純形法舉例2(4)

最優(yōu)值Z*=8最優(yōu)解X*=(4,2,0,1,0)T23例用單純形法解下列線性規(guī)劃

解:將原問題化為標(biāo)準(zhǔn)形式取B1=(P1,P4)=六．單純形法舉例3(1)C=(2200)b=(10)TCB=(20)24

T(B1)XBX1X4-Zb1-1-10101-111-2由于X3的檢驗(yàn)數(shù)大于0，而其所對應(yīng)的列向量都小于等于0，則原問題無最優(yōu)解六．單純形法舉例3(2)X1X2X3X4042025開始判斷所有檢驗(yàn)數(shù)是否小于等于0得到最優(yōu)解構(gòu)造單純形表NO

輸入結(jié)束Yes

是否存在某個(gè)大于0的檢驗(yàn)數(shù)所對應(yīng)的列的元素全小于等于0？原問題無最優(yōu)解換基迭代選擇出基變量Yes

選擇入基變量NO

單純形法的框圖表示為如下:26舉例已知某一線性規(guī)劃與基B=(P4,P1)對應(yīng)的單純形表T(B)如下:

xB b x1 x2 x3 x4 x4 6 0