運籌學(xué)線性規(guī)劃及單純形法

運籌學(xué)

OperationalResearch運籌帷幄，決勝千里史記《張良傳》理學(xué)院姚君第1章線性規(guī)劃及單純形法★線性規(guī)劃的數(shù)學(xué)模型★線性規(guī)劃的圖解法★單純形法原理★單純形法的計算步驟LinearProgrammingandSimplexAlgorithm本章主要內(nèi)容線性規(guī)劃（LinearProgramming縮寫為LP）通常解決下列兩類問題

（1）當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時間等）去完成確定的任務(wù)或目標(biāo)；

（2）在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤最大）.

§1線性規(guī)劃的數(shù)學(xué)模型1、問題的提出生產(chǎn)計劃問題

問：產(chǎn)品Ⅰ、Ⅱ各生產(chǎn)多少件，使利潤最大？

ⅠⅡ限制

設(shè)備A臺時設(shè)備B臺時設(shè)備C臺時21422012臺時

816設(shè)備D臺時0412利潤232、線性規(guī)劃的數(shù)學(xué)模型：

max(min)z=c1x1+c2x2+···+cnxna11x1+a12x2+···+a1nxn≤(=,≥)b1a21x1+a22x2+···+a2nxn≤(=,≥)b2┆┆am1x1+am2x2+···+amnxn≤(=,≥)bmx1，x2，···，xn≥0

s.t.說明：

(1)決策變量：x1，x2，···，xn。

一組決策變量表示為問題的一個方案；

(2)目標(biāo)函數(shù)：max(min)zz為決策變量的線性函數(shù);(3)約束條件一組線性不等式。cj為價值系數(shù),bi為資源，aij為技術(shù)系數(shù)(i=1,…,m;j=1,…,n)在實際中一般xj≥0,但有時xj≤0或xj無符號限制。為了書寫方便，上式也可寫成向量:nmaxz=cjxj

j=1

n

s.t

pjxj≤b

（i=1,2,……,m）

j=1 xj≥0（j=1,2,……,n)矩陣形式在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。3、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)型線性規(guī)劃問題的標(biāo)準(zhǔn)型為1．目標(biāo)函數(shù)求最大值（有時求最小值）2．約束條件都為等式方程；3．變量xj為非負(fù)。4．常數(shù)bi都大于或等于零；max(或min)Z=c1x1+c2x2+…+cnxn或用矩陣形式:或?qū)懗上铝行问剑?/p>

將下列線性規(guī)劃問題化為標(biāo)準(zhǔn)型

【解】(1)因為x3無符號要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令

(2)第一個約束條件是“≤”號，在“≤”左端加入松馳變量x4，x4≥0,化為等式；

(3)第二個約束條件是“≥”號，在“≥”號左端減去剩余變量（也稱松馳變量）x5，x5≥0.

(4)第三個約束條件是≤號且常數(shù)項為負(fù)數(shù)，因此在≤左邊加入松馳變量x6，x6≥0，同時兩邊乘以－1。

(5)目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當(dāng)Z達(dá)到最小值時Z′達(dá)到最大值，反之亦然。綜合起來得到下列標(biāo)準(zhǔn)型

復(fù)習(xí)思考題：1.什么是模型結(jié)構(gòu)的三要素？2.什么是線性規(guī)劃模型？能舉出線性規(guī)劃模型的例子嗎？LP模型中目標(biāo)函數(shù)系數(shù)、約束條件系數(shù)、約束右端項的含義指的是什么？通常以什么符號表示？LP模型的一般表示方法有幾種形式？能否寫出這些形式？什么是線性規(guī)劃模型的標(biāo)準(zhǔn)形式？為何提出標(biāo)準(zhǔn)形式？你能否把一個線性規(guī)劃模型的非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式？模型

nmaxz=cjxj

j=1ns.t.aijxj=bi

（i=1,2,……,m)②

j=1xj≥0（j=1,2,……,n)③4、線性規(guī)劃解的基本概念

可行解：滿足約束條件②、③的解為可行解。所有可行解的集合為可行域。

最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最大值的可行解。

基：設(shè)A為約束條件②的m×n階系數(shù)矩陣(m<n)，其秩為m，B是矩陣A中m階滿秩子矩陣（∣B∣≠0），稱B是規(guī)劃問題的一個基。稱B中每個列向量Pj(j=12……m)

為基向量。與基向量Pj

對應(yīng)的變量xj

為基變量。除基變量以外的變量為非基變量。設(shè)：

基解：某一確定的基B，令非基變量等于零，由約束條件方程②解出基變量，稱這組解為基解。在基解中變量取非0值的個數(shù)不大于方程數(shù)m，基解的總數(shù)不超過

基可行解：滿足變量非負(fù)約束條件的基本解，簡稱基可行解?？尚谢簩?yīng)于基可行解的基稱為可行基。非可行解可行解基解基可行解線性規(guī)劃問題

求所有基矩陣。

【解】約束方程的系數(shù)矩陣為2×5矩陣

容易看出r（A）=2，2階子矩陣有=10個，基矩陣只有9個，即Maxz=2x1+3x2st.x1+x2≤3 x1+2x2≤4 x1,x2≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T

等。設(shè)B=

1001，令，則|B|=1≠0,令x1=x2=0，則x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基變量令B=1110x1x3

，則令x2=x4=0，則x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解標(biāo)準(zhǔn)化復(fù)習(xí)思考題：

1.

一個標(biāo)準(zhǔn)化LP模型，最多可有多少個基？

2.

基本解是如何定義的？怎樣才能得到基本解？3.

可行解、基本解、基本可行解三者之間有什么關(guān)系？利用作圖方法求解。例：maxz=2x1+3x2 s.t2x1+2x212----------①

x1+2x28----------② 4x116----------③ 4x212----------④ x10,x20

§2線性規(guī)劃的圖解法x1x222468460①②④③Z=6Z=0(4,2)Zmax

maxz=2x1+3x2

s.t2x1+2x212----------①

x1+2x28----------② 4x116----------③ 4x212----------④ x10,x20

AAB唯一解無窮多解無界解無可行解步驟：（1）作平面直角坐標(biāo)系，標(biāo)上刻度； （2）做出約束方程所在直線，確定可行域； （3）做出一條目標(biāo)函數(shù)等值線，判定優(yōu)化方向； （4）沿優(yōu)化方向移動，確定與可行域相切的點，確定最優(yōu)解，并計算最優(yōu)值。討論一：模型求解時，可得到如下幾種解的狀況： （1）唯一最優(yōu)解：只有一點為最優(yōu)解點，簡稱唯一解； （2）無窮多最優(yōu)解：有許多點為最優(yōu)解點，簡稱無窮多解； （3）無界最優(yōu)解：最優(yōu)解取值無界，簡稱無界解； （4）無可行解：無可行域，模型約束條件矛盾。討論二：LP模型求解思路： （1）若LP模型可行域存在，則為一凸形集合； （2）若LP模型最優(yōu)解存在，則其應(yīng)在其可行域頂點上找到； （3）頂點與基本解、基本可行解的關(guān)系：復(fù)習(xí)思考題：1.LP模型的可行域是否一定存在?2.圖解中如何去判斷模型有唯一解、無窮多解、無界解和無可行解？3.LP模型的可行域的頂點與什么解具有對應(yīng)關(guān)系？4.你認(rèn)為把所有的頂點都找出來，再通過比較目標(biāo)函數(shù)值大小的方式找出最優(yōu)解，是否是最好的算法？為什么？可行域的性質(zhì)線性規(guī)劃的可行域是凸集線性規(guī)劃的最優(yōu)解在極點上凸集凸集不是凸集極點線性規(guī)劃可行域和最優(yōu)解的幾種情況1、可行域封閉唯一最優(yōu)解2、可行域封閉多個最優(yōu)解3、可行域開放唯一最優(yōu)解4、可行域開放多個最優(yōu)解5、可行域開放目標(biāo)函數(shù)無界6、無可行解一、預(yù)備知識

1、凸集：設(shè)K為En(n維歐式空間)的一點集，X(1)∈K，X(2)∈K。若αX(1)+(1-α)X(2)∈K，則稱K為凸集。（0<α<1）

非凸集X(1)X(1)X(2)X(2)凸集X(1)X(2)X(2)X(1)§3單純形法原理

2、頂點：X∈K，X(1)∈K，X(2)∈K(任意兩點)。若X不能用αX(1)+(1-α)X(2)表示，則稱X為K的一個頂點。(0<α<1)凸集中不成為任意兩點連線上的點，稱為凸集頂點。注：頂點所對應(yīng)的解是基可行解。

3、凸組合：設(shè)X(i)∈En，若存在0<μi<1，i=1,2,···,k，使,則稱X為X(i)(i=1,2,···,k)的凸組合。二、基本定理定理1若線性規(guī)劃存在可行域，則:

可行域

D={X|AX=b,X≥0}為凸集。

定理2線性規(guī)劃的基可行解對應(yīng)于可行域的頂點。定理3若線性規(guī)劃有解，則一定存在基可行解為最優(yōu)解?；舅枷氲砼c舉例§4單純形法的計算步驟結(jié)論：如果線性規(guī)劃有有限的最優(yōu)解，則它一定可以在可行域的一個頂點上達(dá)到。單純形法:否初始頂點轉(zhuǎn)移到新頂點(目標(biāo)值上升)是否最優(yōu)？停止迭代是0(0,3)(0,0)(2,3)(4,2)(4,0)可行域的頂點基本可行解等價定理:基本思想基本可行解基本可行解單純形法幾何解釋---頂點尋優(yōu)

例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x23標(biāo)準(zhǔn)化

s.tx1+x2+x3=3 x1+2x24 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4) （1）初始基本可行解的選擇：-----坐標(biāo)原點處 令x1=x2=0,由

x1+x2+x3=3

x1+2x2+x4=4

（2）是否為最優(yōu)解的判定 x3=3-(x1+x2)x4=4-(x1+2x2)

解得X=(0,0,3,4)T（3）找新的頂點（基本可行解）： 直觀看，x2↑1,則z↑3，∴應(yīng)找A點，即增加x2。x2可增加多少？需要保證x3=3-(x1+x2)0

x4=4-(x1+2x2)0， ∴

x2=min（3/1，4/2），從而 x3=1-(x1/2-x4

/2）

x2=2-(x1/2+x4/2)

令x1=x4=0，則新的基本可行解為X=(0，2，1，0)T重復(fù)上述過程基本可行解最優(yōu)性判別準(zhǔn)則確定入基變量確定出基變量換基運算迭代原理Cj→x1x2x3x4XBbCB1 1 1 01 2 012 3 0 034x3x400cj-zj23003/1=34/2=21/2 0 1 -1/21/2 1 01/2x3x212cj-zj1/2 00-3/203241 0 2 -10 1 -11x1x221cj-zj0 0 -1 -123單純形法計算θi單純形法計算過程總結(jié)：（1）化標(biāo)準(zhǔn)形，列初始單純形表；（2）計算檢驗數(shù)：σj=△z=cj-zj=cj-ciaij（3）最優(yōu)性判斷：當(dāng)所有檢驗數(shù)均有σj

0時，則為最優(yōu)解。否則 迭代求新的基本可行解。（4）迭代： 入基變量：取max{σj0}=

σk→xk 出基變量：取min{θi=bi/aikaik>0}=θl

→x(l)

主元素：[alk] 新單純表：pk=單位向量注：當(dāng)所有檢驗數(shù)σj

0時，若存在非基變量檢驗數(shù)為0時，則有無窮多解，否則只有唯一最優(yōu)解。i=1m否初始頂點轉(zhuǎn)移到新頂點(目標(biāo)值下降)是否最優(yōu)？停止迭代是初始基本可行解新的基本可行解單純形法的迭代思想：復(fù)習(xí)

例：

minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23標(biāo)準(zhǔn)化

s.tx1+x2

-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4) maxz=-2x1-3x2+0x3-Mx4-Mx5

s.tx1+x2

-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5) 引進(jìn)人工變量，及M——非常大正系數(shù)，模型轉(zhuǎn)變?yōu)檫@種處理方法稱為大M法，以下則可完全按單純形法求解。1．大M法§5單純形法的進(jìn)一步討論Cj→x1x2x3x4XBbCB1 1 -1 101 2 001

-2 -3 0 -M-M

34x4x5-M-Mcj-zj-2+2M-3+3M-M03/1=34/2=21/2 0 -1 1-1/21/2 1 001/2x4x212cj-zj-1/2+M/2

0-M

0

3/2-M/2-M-3241 0 -2 2-10 1 1-11x1x221cj-zj0 0 -1 -1-M-1-M-2-3θix50說明：

當(dāng)所有j0

，但存在人工變量x人0，則可以判定該模型無可行解。采用大M法求解線性規(guī)劃模型時，如果模型中各個系數(shù)與M的值非常接近時，若手工計算時，不會出現(xiàn)任何問題。如果利用計算機(jī)程序求解，則大M表現(xiàn)為一個較大的數(shù)字，由于綜合計算的影響，導(dǎo)致檢驗數(shù)出現(xiàn)符號誤差，引起判斷錯誤，從而使大M方法失效。在這種情況下，可采用下面的兩階段法進(jìn)行計算。2、兩階段法的思想：兩階段法：第一階段：第二階段：求解輔助(LP)，得到原(LP)的一個初始基本可行解。再用單純形法去求原的最優(yōu)解。

例：minz=2x1+3x2maxz=-2x1-3x2+0x3 s.tx1+x23標(biāo)準(zhǔn)化s.tx1+x2

-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4) obj:maxz=-x4-x5

s.tx1+x2

-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5) (1)

第一階段，構(gòu)造判斷是否存在可行解的模型：

用單純形法求解，若zmax=0，表明該模型有可行解，則可進(jìn)入第二階段，求原模型最優(yōu)解。Cj→x1x2x3x4XBbCB1 1 -1 101 2 001

0 0 0 -1-1

34x4x5-1-1