2010生第五章單純形法

1概念回顧2目標函數(shù)：max50x1+100x21

2

1約束條件：x

+x

+s

≤300，2x1+x2+s2≤400，x2+s3≤250.xj≥0

（j=1，2）,sj≥0

（j=1，2,3）

1

0

1

0

1

1

1

0

0

A

=(p1,

p2

,

p3,

p4

,

p5

)

=

2

1

0

1

0

0基：已知A是約束條件的m×n系數(shù)矩陣，其秩為m。若B是A中

m×m階非奇異子矩陣（即可逆矩陣），則稱B是線性規(guī)劃問題中的一個基。初始可行基：由單位矩陣的各列向量所組成?；蛄浚夯鵅中的一列即稱為一個基向量?；鵅中共有m個基向量。非基向量：在A中除了基B之外的一列則稱之為基B的非基向量。基變量：與基向量pi相應的變量xi叫基變量，基變量有m個。

非基變量：與非基向量pj相應的變量xj叫非基變量，非基變量有

n－m個。3如果我們在約束方程組系數(shù)矩陣中找到一個基，令這個基的非基變量為零，再求解這個m元線性方程組就可得到唯一的解了，這個解我們稱之為線性規(guī)劃的基本解。把滿足非負條件的一個基本解叫做基本可行解。初始基本可行解？？？可行解？？？單純形法迭代原理4從引例中了解了線性規(guī)劃的求解過程，將按上述思路介紹一般的線性規(guī)劃模型的求解方法——單純形法迭代原理。5觀察法:直接觀察得到初始可行基≤約束條件:加入松弛變量即形成可行基。（下頁）≥約束條件:加入非負人工變量,以后討論.1、初始基可行解的確定

6

..........................................

x1,

x2

,...,

xn

?

0xm

+

amm+1

xm+1

+...

+

amn

xn

=

bmx2

+

a2m+1

xm+1

+...

+

a2n

xn

=

b2+

a1m+1

xm+1

+...

+

a1n

xn

=

b1

x11、初始基可行解的確定不妨設程組可表示為x1,x2為,

松,弛x變m

量，則約束方X

=(b1

,b2

,...,bm

,0,0,...,0)是一初始基可行解。7有：(i

=1,2,...m)

..........................................

令：xm+1

=

...

=

xn

=

0xi

=

bixm

=

bm

-

amm+1

xm+1

-...

-

amn

xnx2

=

b2

-

a2m+1

xm+1

-...

-

a2n

xn

x1

=

b1

-

a1m+1

xm+1

-...

-

a1n

xn1、初始基可行解的確定單純形法的表格形式8為了使單純形法更加簡潔明了，經(jīng)常通過表格進行計算。9max

50x1+100x2+0·s1+0·s2+0·s3.x1+x2+s1=300，2x1+x2+s2=400，x2+s3=250，x1,x2,s1,s2,s3≥0.把上面的數(shù)據(jù)填入如下的單純形表格按照線性規(guī)劃模型在表中填入相對應的值，如上表所示；在上表中有一個m*m的單位矩陣，對應的基變量為s1,s2,s3；在zj行中填入第j列與cB列中對應的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位數(shù)填入0；在列的交匯處為主元，這里是a32=1，在表中畫圈以示區(qū)別。在s

j

=c

j

-z

j行中填入cj-zj所得的值，如

s

1

；迭代 基變次數(shù)

量cBx1x2s1s2s3b比值Bi/ai2501000000s1s2s300020111001250100300300/1010400400/1250/1zjδj=cj-zj0500100000000z=0=

50

-

0

=

5

0由于s

2>

s1

z表示把初始基本可行解代入目標函數(shù)求得的目標函數(shù)值，即b列*cB列；初始基本可行解為s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此確定s3為出基變量；>0

，因此確定x2為入基變量。出基變量所在行，入基變量所主1元00110以下進行第一次迭代，其變量為x2,s1,s2,通過矩陣行的初等變換，求出一個新的基本可行解，具體的做法用行的初等變換使得x2的系數(shù)向量p2變換成單位向量，2由于主元在p

的第3

分量上，所以這個單位向量是素變成1。這樣我們又得到的第1次迭代的單純表如下所示。在上表中第3個基變量s1已被x2代替，故基變量列中的第3個基變量應變?yōu)閤2。由于第0次迭代表中的主元a32已經(jīng)為1，因此第3行不變。為了使第1行的a12為0，只需把第3行*(-1)加到第1行即可。同樣可以求得第2行。求得第1次迭代的基本可行解為s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.3e

=(0,0,1

)T也就是主元迭代次數(shù)基變量cBx1x2s1s2s3b比值bi/aij50100000s101010-15050/1s202001-1150150/21x210001001250—zjs

j

=

c

j

-

z

j0100001002500050000-

1001112為入基變量，從此值可知b1/a11=50為最小正數(shù)，因此，s1為出基變量，a11為主元，繼續(xù)迭代如下表所示。從上表可以看出，第一次迭代的

s

1

，因此不是最優(yōu)解。設x1從上表中可知第二次迭代得到的基本可行解為x1=50,x2=250,s1=0,s2=50,s3=0,這時z=27500。由于檢驗數(shù)都≤0，因此所求得的基本可行解為最優(yōu)解，z=27500為最優(yōu)目標函數(shù)值。實際上，我們可以連續(xù)地使用一個單純形表，不必一次迭代重畫一個表頭。=

50

>

0迭代次數(shù)基變量cBx1x2s1s2s3b比值bi/aij50100000x1501010-150s2000-211502x210001001250zj501005005027500s

j

=

c

j

-

z

j00-500-5013練習：用單純形法的表格形式求解下列問題max

Z

=

4

x1

+

x

2

x1

+

3

x

2

￡

7￡

9s

.t

4

x1

+

2

x

2x1

,

x

2

?

0第一步？？？練習：

s

.t

4

x1

+

2

x

2

+

s

2+

0

s1

+

0

s

2

x1

+

3

x

2

+

s1

=

7x1

,

x

2

,

s1

,

s

2

?

0=

9化為標準型max

Z

=

4

x1

+

x

2迭代 基變次數(shù)

量cBx1x2s1s2b比值bi/aij41000s1s20014321001797/19/4zjδj=cj-zj0401000001415迭代基變x1x2s1s2比值次數(shù)量cBbbi/aij4100s1002.51-1/419/4x1410.501/49/41zj42019δj=cj-zj0-10-1解得：最優(yōu)解為x1=9/4x2=0s1=19/4s2=016求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法一、大M法以第二章的例2來講解如何用單純形表的方法求解目標函數(shù)值最小的線性規(guī)劃問題。目標函數(shù)：約束條件：加入松弛變量和剩余變量變?yōu)闃藴市?，得到新的約束條件如下：x1

+

x2

-

s1

=

350,x1

-

s2

=125,2x1

+

x2

+

s3

=

600,x1

,

x2

,

s1

,

s2

,

s3

?

0.m

in

f

=

2

x1

+

3

x

2

.x1

+

x

2

?

350

,x1

?

125,2

x1

+

x

2

￡

600

,x1

,

x

2

?

0

.找不到初始基本可行解！??！17求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法引入人工變量，與松弛、剩余變量不同的。松弛變量、剩余變量它們可以取零值，也可以取正值，而人工變量只能取零值。規(guī)定人工變量在目標函數(shù)中的系數(shù)為－M，這里M為任意大的數(shù)。這樣只要人工變量M＞0，所求的目標函數(shù)最大值就是一個任意小的數(shù)。為了使目標函數(shù)實現(xiàn)最大就必須把人工變量從基變量中換出。應用單純形表格法求解。如果一直到最后，人工變量仍不能從基變量中換出，也就是說人工變量仍不為零，則該問題無可行解。對于目標函數(shù)，在標準型中并不一定要求求最大值或最小值，但是為了使單純形表解法有一個統(tǒng)一的解法，我們把所有求目標函數(shù)最小值的問

題化成求目標函數(shù)最大值的問題。具體做法只要把目標函數(shù)乘以（－1）。18§3

求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法此例的數(shù)學模型如下所示：目標函數(shù)：maxz=－2x1－3x2－Ma1－Ma2.約束條件：x1+x2－s1+a1=350，x1－s2+a2=125，2x1+x2+s3=600，x1，x2，s1，s2，s3，a1，a2≥0.像這樣，為了構造初始可行基得到初始可行解，把人工變量“強行”地加到原來的約束方程中去，又為了盡力地把人工變量從基變量中替換出來就令人工變量在求最大值的目標函數(shù)里的系數(shù)為－M，這個方法叫做大M法，M叫做罰因子。求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法面我們就用大M法來求解此題:下迭代次數(shù)基變量cBx1x2s1s2s3a1a2b比值-2-3000-M-M0a1-M11-10010350350/1a2-M100-1001125125/1s302100100600600/2zjs

j

=

c

j

-

z

j-2M-MMM0-M-M-475M-2+2M-3+M-M-M0001a1

-Mx2

-2s3

0zjs

j

=

c

j

-

z

j01-1001-1225225100-1001125-----010210-2350350/2-2-MM-M+20-M-M-2-225M-0-3+M-MM-2002-2M2502a1-M01/2-10-1/2105050/1/2x1-211/2001/200300300/1/2s2001/2011/20-1175175/1/2zj-2-1/2M-1M01/2M-1-M0-50M-01/2M-2-M0-

1/2M+10-M600s

j

=

c

j

-

z

j1920§3

求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法從上表中可知檢驗數(shù)都小于零。已求得最優(yōu)解為：x1=250,x2=100,s1=0,s2=125,s3=0,a1=0,a2=0，其最優(yōu)值為f=-z=-(-800)=800。j

j

js

=

c

-

z迭代次數(shù)基變量cBx1x2s1s2s3a1a2b比值-2-3000-M-Mx2-301-20-120100x1-210101-102503s2000111-1-1125zj-2-3401-40-80000-40-1-M+4-M21求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法二、兩階段法兩階段法是處理人工變量的另一種方法，這種方法是將加入人工變量后的線性規(guī)劃劃分兩階段求解，仍以上面的例題為例，闡述兩階段法的求解過程。第一階段：要判斷原線性規(guī)劃是否有基可行解，方法是先求解下列線性規(guī)劃問題：目標函數(shù)：max

z

=-a1

-a2

;約束條件：x1

+

x2

-

s1

+

a1

=

350,x1

-

s2

+

a2

=125,2x1

+

x2

+

s3

=

600,x1,

x2

,

s1

,

s2

,

s3

,

a1,

a2

?

0.22求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法注意：此線性規(guī)劃的約束條件與原線性規(guī)劃一樣，而目標函數(shù)是求人工變量的相反數(shù)之和的最大值。如果此值大于零，則不存在使所有人工變量都為零的可行解，停止計算。如果此值為零，即說明存在一個可行解，使得所有的人工變量都為零。第二階段：將第一階段的最終單純形表中的人工變量取消，將目標函數(shù)換成原問題的目標函數(shù)，把此可行解作為初始可行解進行計算。求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法迭代次數(shù)基變量cBx1x2s1s2s3a1a2b比值00000-1-10a1-111-10010350350/1a2-1100-1001125125/1s302100100600600/2zj-2-1110-1-1-47021-1-10001a1-101-1101-1225x10100-1001125s30010210-2350zj0-11-10-1122501-1100-

22x2001-11010225x10100-1001125s3000111-1-1125zj0000000000000-1-123求目標函數(shù)值最小的線性規(guī)劃的問題的單純形表解法迭代次數(shù)基變量cBx1x2s1s2s3b比值-2-30000x2-301-110225225/1x1-2100-10125s3001021125125/2zj-2-33-10-92500-3101x2-301-20-1100x1-210101250s2000111125zj-2-3401-80000-40-1從表中可知其基本可行解x1=250,x2=100,s1=0,s2=125,s3=0是本例的最優(yōu)解，其最優(yōu)值為z=-(-800)=800。2425幾種特殊情況3

x1

+

10

x

2

￡

150

,x1

￡

30

,x1

+

x

2

?

40

,x1

,

x

2

?

0

.z

=

20

x1

+

30

x

2目標函數(shù)

max約束條件一、無可行解例1、用單純形表求解下列線性規(guī)劃問題解：在上述問題的約束條件中加入松馳變量、剩余變量、人工變量得到：m

ax

z

=

2

0

x1

+

3

0

x

2

-

M

a13

x1

+

1

0

x

2

+

s1

=

1

5

0

,x1

+

s

2

=

30

,x1

+

x

2

-

s3

+

a1

=

40

,x1

,

x

2

,

s1

,

s

2

,

s3

,

a1

?

0

.填入單純形表計算得：目標函數(shù)約束條件26幾種特殊情況迭代基變量CBx1x2s1s2s3a1b比值次數(shù)2030000-Ms103101000150150/10s2010010030—0a1-M1100-114040/1zj-M-M00M-M-40Mcj-zj20+M30+M00-M0x2303/1011/100001515/(3/10)s201001003030/11a1-M7/100-1/100-112525/(7/10)zj9-7/10M303+M/100M-M450-25Mcj-zj11+7/10M0-3-M/100-M0x230011/10-3/100062x12010010030a1-M00-1/10-7/10-114zj20303+M/1011+7M/10M-M780-4Mcj-zj00-3-M/10-11-7M/10-M027幾種特殊情況無法顯示該圖片。從第二次迭代的檢驗數(shù)都小于零來看，可知第2次迭代所得的基本可行解已經(jīng)是最優(yōu)解了，其最大的目標函數(shù)值為780-4M。我們把最優(yōu)解

x1=30,x2=6,s1=0,s2=0,s3=0,a1=4,代入第三個約束方程得x1+x2-0+4=40,即有：

x1+x2=36≤40.并不滿足原來的約束條件3，可知原線性規(guī)劃問題無可行解，或者說其可行解域為空集，當然更不可能有最優(yōu)解了。像這樣只要求線性規(guī)劃的最優(yōu)解里有人工變量大于零，則此線性規(guī)劃無可行解。二、無界解在求目標函數(shù)最大值的問題中，所謂無界解是指在約束條件下目標函數(shù)值可以取

任意的大。下面我們用單純形表來求第二

章中的例子。例2、用單純形表求解下面線性規(guī)劃問題。目標函數(shù)

m

ax

z

=

x1

+

x

2約束條件

x1

-

x

2

￡

1,-

3

x1

+

2

x

2

￡

6

,x1

,

x

2

?

0

.82幾種特殊情況迭代次數(shù)基變量CBx1x2s1s2b比值11000s1s2001-3-121001161—zjcj-zj0101000001x1s21010-1-1130119zjcj-zj10-121-1001填入單純形表計算得：解：在上述問題的約束條件中加入松馳變量，得標準型如下：m

ax

z

=

x1

+

x

2x1

-

x

2

+

s1

=

1,2-

3

x1

+

2

x

2

+

s

=

6

,x1,

x

2

,

s1,

s

2

?

0

.目標函數(shù)

約束條件

幾種特殊情況移項可得：x1

=1+x2

-s1,s2

=

x2

-

3s1

+

9.x1

-

x2

+

s1

=1,-x2

+

3s1

+

s2

=

9.12x1

=

M

+1,x2

=

M

,s1

=

0,s2

=

M

+

9.不妨設x

=

M

,

s

=

0,可得一組解：顯然這是線性規(guī)劃的可行解，此時目標函數(shù)z

=

x1

+

x2

=

M

+1+

M

=

2M

+1.從單純形表中，從第一次迭代的檢驗數(shù)等于2，可知所得的基本可行解

x1=1,x2=0,s1=0,s2=9不是最優(yōu)解。同時我們也知道如果進行第2次迭代，那么就選x2為入基變量，但是在選擇出基變量時遇到了問題a：12 =-1a,22 =-1,找不到大于零的a

22

來確定出基變量。事實上如果我們碰到這種情況就可以斷定這個線性規(guī)劃問題是無界的，也就是說在此線性規(guī)劃的約束條件下，此目標函數(shù)值可以取得無限大。從1次迭代的單純形表中，得到約束方程：2930幾種特殊情況由于M可以是任意大的正數(shù)，可知此目標函數(shù)值無界。上述的例子告訴了我們在單純形表中識別線性規(guī)劃問題是無界的方法：在某次迭代的單純形表中，如果存在著一個大于零的檢驗數(shù)s

ij

，并且該列

的系數(shù)向量的每個元素aij(i=1,2,…,m)都小于或等于零，則此線性規(guī)劃問題

是無界的，一般地說此類問題的出現(xiàn)是由于建模的錯誤所引起的。三、無窮多最優(yōu)解例3、用單純形法表求解下面的線性規(guī)劃問題。m

ax

z

=

5

0

x1

+

5

0

x

2x1

+

x

2

￡

300

,2

x1

+

x

2

￡

400

,x

2

￡

250

,x1,

x

2

?

0

.目標函數(shù)約束條件31幾種特殊情況m

a

x

z

=

5

0

x1

+

5

0

x

2x1

+

x

2

+

s1

=

300

,解：此題我們用圖解法已求了解，現(xiàn)在用單純形表來求解。加入松弛變量s1

,s

2

,s

3，我們得到標準形：目標函數(shù)約束條件2

x1

+

x

2

+

s

2

=

400

,x

2

+

s

3

=

250

,x1,

x

2

,

s1

,

s

2

,

s

3

?

0

.填入單純形表計算得：32幾種特殊情況迭代基變量CBx1x2s1s2s3b比值次數(shù)5050000s1011100300300/1s2021010400400/10s3001001250250/1zj000000cj-zj5050000s101010-15050/1s202001-1150150/21x25001001250—zj050005012500cj-zj500000x1501010-150—2s2000-2115050/1x25001001250250/1zj5050500015000cj-zj00-500033幾種特殊情況這樣我們求得了最優(yōu)解為x1=50,x2=250,s1=0,s2=50,s3=0,此線性規(guī)劃的最優(yōu)值為15000。這個最優(yōu)解是否是惟一的呢？由于在第2次迭代的檢驗數(shù)中除了基變量的檢驗數(shù)

s

1

,

s

2

,

s

4 等于零外，非基變量s3的檢驗數(shù)也等于零，這樣我們可以斷定此線性規(guī)劃問題有無窮多最優(yōu)解。不妨我們把檢驗數(shù)也為零的非基變量選為入基變量進行第3次迭代。可求得另一個基本可行解，如下表所示：迭代次數(shù)基變量CBx1x2s1s2s3b5050000x15010-110100s3000-211503x250012-10200zj5050500015000cj-zj00-500034幾種特殊情況從檢驗數(shù)可知此基本可行解x1=100,x2=200,s1=0,s2=0,s3=50,也是最優(yōu)解，從圖解法可知連接這兩點的線段上的任一點都是此線性規(guī)劃的最優(yōu)解，不妨用向量Z1，Z2表示上述兩個最優(yōu)解即Z1

=（50，250，0，50，0），Z2=（100，200，0，0，50），則此線段上的任一點，即可表示為αZ1+（1-α

）Z2，其中0≤α≤1。如圖5-1所示：100200300100200300250Z1Z2圖5-135幾種特殊情況ss在一個已得到最優(yōu)解的單純形表中，如果存在一個非基變量的檢驗數(shù)為零，為什么我們把這個非基變量xs作為入基變量進行迭代時，得到的最優(yōu)解仍為最優(yōu)解呢？不妨設出基變量為xk，則原最優(yōu)單純形表可表示如下：x

kc

k

x1c1

0

x

sc

sa

1

s

a

k

-

1

,

sa

k

,

sa

k

+

1

,

s

a

m

,

s0c

k

-

1

0

c

k

1

c

k

+

1

0

c

m

0

0jx

k

-

1x

kx

k

+

1

x

ms

=

c

j

-

z

jm從此表可知s

s

=0,即有c1

a

1

s

+c

2

a

2

s

+

+c

m

a

m

s

-c

s

=0，也就是c

s

=

c

i

a

i

s。i

=

1幾種特殊情況通過迭代，我們得到了新的單純形表，其中x

為基變量了，s而xk為非基變量了。我們可得到下表。

(k

-1)s

aks1aks

(k

+1)s

(

)(

)x1

c1

xk

-1

ck

-1xs

cs011100ksm

1i

is1

k

-1csksmi

=1csksksmmksa-a1sxk

xsck

cs0-c

a

+-c

aa-aa-axk

+1ck

+1axcaz

j

zk

csc

j

-

z

j

c

j

-

zk

0

-ams+i

is

ks

i

=1

i

=

k

+1

=a

-

c

a

+

-c

ak ks

+

ks

i

is

在此表中zk

=a

1361cs

=

ck

.即又可得到：c

j

-zk

=c

j

-zk

=0.si

isi

=1m把c

=

c

a

，

代入上式得：kks

ksz

=a

a[-cs

+

ck

aks

]+37幾種特殊情況又顯然在新的單純形表中，基變量的檢驗數(shù)為零，用同樣的方法可證明其他的非基變量的檢驗數(shù)不變，仍然小于零，這樣就證明了新得到的基本可行解仍然是最優(yōu)解。這樣我們得到了判斷線性規(guī)劃有無窮多最優(yōu)解的方法：對于某個最優(yōu)的基本可行解，如果存在某個非基變量的檢驗數(shù)為零，則此線性規(guī)劃問題有無窮多最優(yōu)解。四、退化問題在單純形法計算過程中，確定出基變量時有時存在兩個以上的相同的最小比值，這樣在下一次迭代中就有了一個或幾個基變量等于零，這稱之為退化。目標函數(shù)

約束條件

m

ax

z

=

2

x

+

3

x1

2x1

-

x

2

￡

2,2

x1

+

x3

￡

4

,x1

+

x

2

+

x3

￡

3,x1

,

x

2

,

x3

?

0

.3例4.用單純形表，求解下列線性規(guī)劃問題。解：加上松馳變量s1,s2,s3化為標準形式后，填入單純形表計算得：38幾種特殊情況迭代基變量CBx1x2x3s1s2s3b比值次數(shù)203/2000s10