運(yùn)籌學(xué)線性規(guī)劃及單純性表法

第一章線性規(guī)劃與單純形法本章重點(diǎn)內(nèi)容線性規(guī)劃模型與解的主要概念線性規(guī)劃的單純形法，線性規(guī)劃多解分析線性規(guī)劃的應(yīng)用——建模1第一節(jié)線性規(guī)劃問題及數(shù)學(xué)模型一、實(shí)例二、線性規(guī)劃問題（LP問題）的共同特征三、兩變量線性規(guī)劃問題的圖解法四、線性規(guī)劃問題的標(biāo)準(zhǔn)型五、標(biāo)準(zhǔn)型LP問題解的概念六、可行解、基解和基可行解舉例2一、實(shí)例例1生產(chǎn)計(jì)劃問題(書P8)Step1:明確問題，設(shè)定決策變量設(shè)I、II兩種產(chǎn)品的產(chǎn)量分別為x1,x2

。Step2:確定約束條件產(chǎn)品

I

II資源限量設(shè)備

1

2

8臺(tái)時(shí)原料A

4

0

16公斤原料B

0

4

12公斤利潤

2

3問應(yīng)如何安排生產(chǎn)使該廠獲利最多？3說明：OBJ表示Objective;

s.t.表示Subjectto

Step3:給出目標(biāo)函數(shù)Step4:整理數(shù)學(xué)模型4例2下料問題現(xiàn)要做100套鋼架，每套需2.9米、2.1米和1.5米的圓鋼各一根。已知原料長7.4米，問如何下料，使用的原料最少（余料最少或根數(shù)最少）？分析：最簡(jiǎn)單的做法是：每根7.4米長的原材料各截取三種規(guī)格的元鋼一根，則料頭為0.9米，100套則浪費(fèi)材料90米。關(guān)鍵是要設(shè)計(jì)套裁方案，不能有遺漏。5解：設(shè)x1,x2,

x3,x4,x5分別代表五種不同的原料用量方案。0.86.6310x50.37.1021x40.27.2220x30.17.3102x207.4301x1余料合計(jì)1.5米2.1米2.9米方案余料最少的LP模型：6根數(shù)最少的LP模型：料頭最省根數(shù)最少＝解1:x1=30,x2=10,x4=50;料頭Z=16,根數(shù)90?？梢宰?00套鋼架，無圓鋼剩余。與解1相同≥解2:x1=100,x3=50;料頭Z=10,根數(shù)150?？梢宰?00套鋼架,但余1.5m圓鋼300根。與解1相同7LP是數(shù)學(xué)規(guī)劃的一個(gè)重要分支，數(shù)學(xué)規(guī)劃著重解決資源的優(yōu)化配置，一般可以表達(dá)成以下兩個(gè)問題中的一個(gè)：（1）當(dāng)資源給定時(shí)，要求完成的任務(wù)最多；（2）當(dāng)任務(wù)給定時(shí)，要求為完成任務(wù)所消耗的資源最少。若上述問題的目標(biāo)﹑約束都能表達(dá)成變量的線性關(guān)系，則這類優(yōu)化問題稱LP問題。LP是一種解決在線性約束條件下追求最大或最小的線性目標(biāo)函數(shù)的方法。8

目標(biāo)函數(shù)用決策變量的線性函數(shù)來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化和最小化。

每一個(gè)問題變量都用一組決策變量（x1,x2,…,xn）表示某一方案，這組決策變量的值代表一個(gè)具體方案，這些變量是非負(fù)且連續(xù)的。存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。結(jié)論：線性規(guī)劃是研究在一組線性不等式或線性等式約束下，使得某一線性目標(biāo)函數(shù)取最大或最小的極值問題。二、線性規(guī)劃問題（LP問題）的共同特征9Max(Min)Z=c1x1+c2x2+…+cnxn(1)

a11x1+a12x2+…+a1nxn

≤(=,≥)b1a21x1+a22x2+…+a2nxn

≤

(=,≥)b2

s.t.

……(2)am1x1+am2x2+…+amnxn

≤

(=,≥)bmxj≥0,j=1,2,…，n(3)(1)—目標(biāo)函數(shù)；(2)約束條件；(3)決策變量非負(fù)n－變量個(gè)數(shù)；m－約束行數(shù)；cj－價(jià)值系數(shù)；bi－右端項(xiàng)或限額系數(shù)；aij－技術(shù)系數(shù)；xj—決策變量線性規(guī)劃模型的一般形式為：10線性規(guī)劃模型的緊縮形式n－變量個(gè)數(shù)；m－約束行數(shù)；cj－價(jià)值系數(shù)；bi－右端項(xiàng)或限額系數(shù)；aij－技術(shù)系數(shù)；xj—決策變量11練習(xí)題：是否為線性規(guī)劃模型？121.線性不等式的幾何意義—半平面作出LP問題的可行域作出目標(biāo)函數(shù)的等值線移動(dòng)等值線到可行域邊界得到最優(yōu)點(diǎn)2.圖解法步驟三、兩變量線性規(guī)劃問題的圖解法134x1=164x2=12x1+2x2=8x1x248Q1

4Q4

30例3

（書P8）：Q2(4,2)Z=2x1+3x2做目標(biāo)函數(shù)2x1+3x2的等值線，與陰影部分的邊界相交于Q2(4,2)點(diǎn)，表明最優(yōu)生產(chǎn)計(jì)劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。Q314目標(biāo)函數(shù)z=ax1+bx2的值遞增的方向與系數(shù)a、b有關(guān)a>0,b>0a<0,b>0X1X2a<0,b<0a>0,b<0z=ax1+bx2目標(biāo)函數(shù)等值線：ax1+bx2=k移項(xiàng)x2=-a/bx1+k/b目標(biāo)函數(shù)等值線在縱軸上的截距為k/b15例4Z=3616例用圖解法求解線性規(guī)劃問題4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+4x2當(dāng)Z值由小變大時(shí)，將與Q2Q3重合Q2Q3上任意一點(diǎn)都是最優(yōu)解有無窮多最優(yōu)解（多重解）Q3(2,3)17例用圖解法求解線性規(guī)劃問題可行域無界—無界解（“無有限最優(yōu)解”或“最優(yōu)解無界”）約束條件過分寬松x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00可行域無解（不閉合）一定就會(huì)出現(xiàn)無界解嗎？18例用圖解法求解線性規(guī)劃問題可行域無界—唯一最優(yōu)解X*=(1,0)，對(duì)應(yīng)于點(diǎn)Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0019例用圖解法求解線性規(guī)劃問題可行域無界—無窮多最優(yōu)解對(duì)應(yīng)于點(diǎn)B沿著OB向右上方發(fā)出的射線上的所有點(diǎn)x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0020例（書P11）：

無可行解（可行域?yàn)榭眨﹛14x1=164x2=12x1+2x2=8x248Q14Q430-2-2x1+x2=4

無最優(yōu)解213.圖解法的作用能解決少量問題揭示了線性規(guī)劃問題的若干規(guī)律解的類型可行域類型唯一最優(yōu)解無窮多最優(yōu)解最優(yōu)解無界（無有限最優(yōu)解）無解（不存在可行域）非空有界無界空集規(guī)律1：22規(guī)律2：線性規(guī)劃問題的可行域?yàn)橥辜€性規(guī)劃問題凸集的頂點(diǎn)個(gè)數(shù)是有限的最優(yōu)解可在凸集的某頂點(diǎn)處達(dá)到23小結(jié)：圖解法的基本步驟：1．在直角坐標(biāo)系作出可行域S的區(qū)域（一般是一個(gè)凸多邊形）2．令目標(biāo)函數(shù)值取一個(gè)已知的常數(shù)k，作等值線：c1x1+c2x2=k3．對(duì)于max問題，讓目標(biāo)函數(shù)值k由小變大，即讓等值線進(jìn)行平移，若它與可行域S最后交于一個(gè)點(diǎn)（一般是S的一個(gè)頂點(diǎn)），則該點(diǎn)就是所求的最優(yōu)點(diǎn)，若與S的一條邊界重合，此時(shí)邊界線上的點(diǎn)均是最優(yōu)點(diǎn)4．將最優(yōu)點(diǎn)所在的兩條邊界線所代表的方程聯(lián)立求解，即得最優(yōu)解X*，把最優(yōu)解X*帶入目標(biāo)函數(shù)，得最優(yōu)值Z*=CX*注意：若是求目標(biāo)函數(shù)最小值，等值線向反方向移動(dòng)24四、線性規(guī)劃問題的標(biāo)準(zhǔn)型1.標(biāo)準(zhǔn)型（1）目標(biāo)函數(shù)：max（2）約束條件：等式（3）變量約束：非負(fù)xj0（4）資源限量：非負(fù)bi

0標(biāo)準(zhǔn)型的構(gòu)成要素252.線性規(guī)劃標(biāo)準(zhǔn)型的緊縮形式263.線性規(guī)劃標(biāo)準(zhǔn)型的向量和矩陣表達(dá)式矩陣式:MaxZ=CTXs.t.AX=b

X≥0

n向量式:MaxZ=∑cjxj

j=1

ns.t.∑Pjxj=b

j=1

xj≥0,j=1,2,...,n274.所有LP問題均可化為標(biāo)準(zhǔn)型（1）最小轉(zhuǎn)換成最大y1=f(x)y2=-f(x)xyx*y1*y2*28（2）不等式約束條件轉(zhuǎn)換成等式約束條件（3）變量約束轉(zhuǎn)換（4）把bi0轉(zhuǎn)換成bi029例5

化標(biāo)準(zhǔn)型可化為1.處理決策變量

2.處理目標(biāo)函數(shù)

3.約束條件不等式

4.處理約束條件右端

常數(shù)項(xiàng)

30例6

化標(biāo)準(zhǔn)型1.處理決策變量

2.處理目標(biāo)函數(shù)

3.約束條件不等式

4.處理約束條件右端

常數(shù)項(xiàng)

31MaxZ’=x1+2x’2+3x4-3x5+0x6+0x7s.t.x1-x’2+x4-x5+x6=7

x1+x’2+x4

-x5-x7=2-3x1-x’2+3x4-3x5=5x’2≥0,xj≥0,j=1,4,5,6,7

MaxZ’=x1+2x’2+3(x4-x5)+0x6+0x7s.t.x1-x’2+(x4-x5)

+x6=7

x1+x’2+(x4

-x5)

-x7=2-3x1-x’2+3(x4-x5)=5x’2≥0,xj≥0,j=1,4,5,6,7

最終結(jié)果中間結(jié)果32課堂練習(xí)33五、標(biāo)準(zhǔn)型LP問題解的概念34（1）（2）（3）約束系數(shù)矩陣：x1x2x3x4x5例：35約束系數(shù)矩陣：可能的基矩陣是A中任意三個(gè)列的組合，共10個(gè)。36令B==(P1,P2,…,Pm

)

且|B|0

，則稱Pj(j=1,2,…,m)

為基向量。與基向量Pj對(duì)應(yīng)的變量xj稱為基變量，記為XB=(x1,x2,…,xm

)T，其余的變量稱為非基變量，記為XN

=(xm+1,xm+2,…,xn

)T

。373839B1=(P1,P2)：基令：XB1=(x1,x2)x1=0，

x2=2X=(0,2,0,0)XB1=(0,2)對(duì)應(yīng)于B1的基解為也是基可行解40線性規(guī)劃標(biāo)準(zhǔn)型問題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解41例7

MaxZ=2x1+3x2

s.t.x1+2x2≤84x1≤164x2≤12

x1,x2

≥0

六、可行解、基解和基可行解舉例非基變量基變量圖中的點(diǎn)x4,x5x1=4x2=3x3=-2A基解x3,x5x1=2x2=3x4=8B基可行解x3,x4x1=4x2=2x5=4C基可行解，最優(yōu)解x2,x4x1=4x3=4x5=12D基可行解x2,x3x1=8x4=-16x5=12E基解x1,x5x2=3x3=2x4=16F基可行解x1,x3x2=4x4=16x5=-4G基解x1,x2x3=8x4=16x5=12H基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH標(biāo)準(zhǔn)型42例843LP標(biāo)準(zhǔn)型問題解的結(jié)論

根據(jù)LP的圖解法及解的基本概念可知：基解對(duì)應(yīng)約束條件的交點(diǎn)；基可行解對(duì)應(yīng)可行域的頂點(diǎn)某個(gè)基可行解一定是最優(yōu)解，即一定在可行域的頂點(diǎn)上得到最優(yōu)解。44第二節(jié)LP問題的基本理論一、基本概念45判斷以下圖形哪些是凸集，哪些不是凸集？判斷下列集合是否凸集？46定理1

LP問題的可行域?yàn)橐煌辜?。二、基本定?7引理線性規(guī)劃問題的可行解X=(x1,x2,…,xn)T是基可行解的充要條件為X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。48定理2

線性規(guī)劃問題的基可行解對(duì)應(yīng)于可行域的頂點(diǎn)。（即：若X是LP問題的可行解，則“X是LP問題的基可行解”等價(jià)于“X是LP問題可行域頂點(diǎn)”）因?yàn)閄是基可行解，則其對(duì)應(yīng)的向量組a1,a2,…,am線性無關(guān)(m<n)當(dāng)j>m時(shí)，有xj=xj(1)=xj(2)=0.49505152定理3

若可行域有界，則LP問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。引理若S是有界凸集，則任何一點(diǎn)X∈S可表示為S的頂點(diǎn)的凸組合。53

線性規(guī)劃問題的可行域是凸集(定理1)；凸集的頂點(diǎn)對(duì)應(yīng)于基可行解(定理2)，基可行解(頂點(diǎn))的個(gè)數(shù)是有限的；若線性規(guī)劃有最優(yōu)解，必在可行域某頂點(diǎn)上達(dá)到(定理3)。因此,我們可以在有限個(gè)基可行解中尋找最優(yōu)解。由線性代數(shù)知，對(duì)標(biāo)準(zhǔn)形LP問題，用枚舉法可以求出所有基解，再通過觀察找出其中的可行解（基可行解），進(jìn)而找出最優(yōu)解。但如果變量和方程較多，比如m=50，n=100，所有基解有可能達(dá)1029個(gè)，即使計(jì)算機(jī)每秒能求解1億個(gè)這樣的方程組，也需要30萬億年！因此，必須尋求有效的算法。為加快計(jì)算速度，算法必須具有兩個(gè)功能，一是每得到一個(gè)解，就來檢驗(yàn)是否已經(jīng)最優(yōu)，若是停止。二是若不是最優(yōu)，要保證下一步得到的解不劣于當(dāng)前解。這就是線性規(guī)劃的單純形法。

54第三節(jié)單純形法一、基本思想檢驗(yàn)解的最優(yōu)性結(jié)束Y樞軸運(yùn)算（旋轉(zhuǎn)運(yùn)算）確定另一個(gè)基本可行解N化LP問題為標(biāo)準(zhǔn)型，確定一個(gè)初始基本可行解化LP問題為標(biāo)準(zhǔn)型，從可行域的某個(gè)基可行解（一個(gè)頂點(diǎn)）開始，轉(zhuǎn)換到另一個(gè)基可行解（另一個(gè)頂點(diǎn)），并使目標(biāo)函數(shù)值得到改善，如此反復(fù)，從而求得問題的最優(yōu)解。其實(shí)質(zhì)是逐步迭代（逼近）法。55單純形法舉例（P20）化為標(biāo)準(zhǔn)型二、基本原理舉例561.初始基可行解的確定要得到一個(gè)初始基可行解，必須找到一個(gè)初始可行基。由于典型示例標(biāo)準(zhǔn)化后，x3、x4、x5的系數(shù)列向量構(gòu)成單位矩陣，該矩陣B0是一個(gè)基，并且是一個(gè)可行基（可以證明，標(biāo)準(zhǔn)化后的單位矩陣一定是可行基）。57

令非基變量x1＝0、x2＝0，得到基可行解及相應(yīng)的目標(biāo)函數(shù)值，X(0)＝(0,0,8,16,12)T，Z(0)＝0。結(jié)論：（1）在標(biāo)準(zhǔn)化的LP問題的約束系數(shù)矩陣中，只要存在單位矩陣，就可求得初始基可行解；（2）基變量確定后，目標(biāo)函數(shù)和基變量均可表示成非基變量的代數(shù)和形式（如(6)和(5)），從而便于求出基可行解及相應(yīng)的目標(biāo)函數(shù)值。582.最優(yōu)性檢驗(yàn)

考察變換后的目標(biāo)函數(shù)(6)式，非基變量x1、x2的系數(shù)都為正數(shù)，若讓x1、x2取正值，則目標(biāo)函數(shù)值會(huì)增大。因此，應(yīng)將非基變量x1、x2變換成基變量。結(jié)論：在非基變量的代數(shù)和形式表示的目標(biāo)函數(shù)中，若非基變量的系數(shù)（稱為檢驗(yàn)數(shù)）為正，則目標(biāo)函數(shù)值還有增加的可能，表明當(dāng)前的基可行解不是最優(yōu)解。59

當(dāng)確定x2為換入變量后，x1還是非基變量，故x1＝0。現(xiàn)在要保證x3、x4、x530，即(5)當(dāng)x2＝min（8/2，—，12/4）=3（最小比值規(guī)則）可保證x5=0則x5為換出變量。新的基變量為x3、x4、x2

，新的可行基為B1＝(P3,P4,P2)確定換入變量：一般選擇正系數(shù)最大的非基變量為換入變量。確定換出變量：（a）保證換出的變量取值為0，變成非基量；（b）其它的變量取值為非負(fù)。3.確定新的基可行解（基變換）604.旋轉(zhuǎn)迭代

基變量確定后，旋轉(zhuǎn)迭代就是把目標(biāo)函數(shù)和基變量均表示成非基變量x1、x5的代數(shù)和形式。可用高斯消去法實(shí)現(xiàn)。

令非基變量x1＝0、x5＝0，得到新的基可行解及相應(yīng)的目標(biāo)函數(shù)值，X(1)＝(0,3,2,16,0)T，Z(1)＝9。返回至第二步，直至求出最優(yōu)解。61這時(shí)目標(biāo)函數(shù)的表達(dá)式是z=14－1.5x3－0.125x4，當(dāng)將x1定為換入變量后，繼續(xù)利用上述方法確定換出變量，繼續(xù)迭代，再得到一個(gè)基可行解X(2)=(2,3,0,8,0)T，這時(shí)目標(biāo)函數(shù)的表達(dá)式是z=13－2x3+1/4x5，再經(jīng)過一次迭代，再得到一個(gè)基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+3x2Q3

將上述方程組求解過程，用列表形式表達(dá)，即為線性規(guī)劃單純形表。62以x2為主元素以x1為主元素例

2x1+x2+2x3=10(1)3x1+3x2+x3=6(2)

x1+1/2x2+x3=5(1)’0x1+3/2x2-2x3=-9(2)’(2)-(1)×3/2,(1)/2

x1+0x2+5/3x3=80x1+x2-4/3x3=-6(1)’-(2)’/3,(2)’×2/3三、旋轉(zhuǎn)運(yùn)算結(jié)論：旋轉(zhuǎn)運(yùn)算就是矩陣的初等變換，是高斯消元63結(jié)論：如果LP問題通過單純形法迭代到某步時(shí)，所有檢驗(yàn)數(shù)≤0,則該LP問題已得到最優(yōu)解。MaxZ=CXs.t.AX=b

X≥0若cj-CBB-1Pj=σj≤0,則Z≤Z0,Z0即為最優(yōu)解.(基變量的檢驗(yàn)數(shù)必為0)令A(yù)=(B,N),X=XB

,C=(CB,CN)

XN由AX=b(B,N)XB=b

BXB+NXN=b

B-1BXB+B-1NXN=B-1b

XN

XB=B-1b－B-1NXN(2)將(2)式代入目標(biāo)函數(shù)得Z=CX=(CB,CN)XB=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN

XN

=CBB-1b+(CN-CBB-1N)XN=Z0+∑(cj-CBB-1Pj)xj

xj為非基變量四、檢驗(yàn)數(shù)公式64對(duì)于線性規(guī)劃問題：MaxZ=CTX

AX=b，X≥0，可用如下三個(gè)判別定理來判別線性規(guī)劃問題是否已經(jīng)獲得最優(yōu)解或?yàn)闊o界解。判別定理1

設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切j∈J（J為非基變量的下標(biāo)集）有σj≤0，則X為線性規(guī)劃的最優(yōu)解。判別定理2

設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切j∈J（J為非基變量的下標(biāo)集）有σj≤0，同時(shí)有某個(gè)非基變量的檢驗(yàn)數(shù)σk=0(k∈J)，則該線性規(guī)劃有無窮多最優(yōu)解；設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切j∈J（J為非基變量的下標(biāo)集）有σj＜0，則該線性規(guī)劃有唯一最優(yōu)解。判別定理3設(shè)X為線性規(guī)劃的一個(gè)基可行解，若有σk>0(k∈J)，且pk≤0，即aik≤0（i=1,…,m），則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。65一、步驟Step1.化LP問題為標(biāo)準(zhǔn)型,建立初始單純形表;Step2.若所有檢驗(yàn)數(shù)≤0,則最優(yōu)解已達(dá)到。否則,計(jì)算

,選取σk所對(duì)應(yīng)的變量xk為進(jìn)基變量;Step3.計(jì)算

,選取θl所對(duì)應(yīng)的變量xl為出基變量;Step4.以alk為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算,轉(zhuǎn)Step2;第四節(jié)單純形法的步驟66cj

CBXBb

x1x2

…

xm

xm+1…

xn

σj

基可行解：

x1=b1,x2=b2,…,xm=bm,xm+1=xm+2=…=xn=01.初始單純形表c1c2…

cm

cm+1…cnc1x1

c2

x2∶

∶

cm

xmb1

b2

∶bm10…0a1,m+1…

a1n01…0a2,m+1…

a2n∶∶

…

∶

∶

…∶00…1am,m+1…

amn00…0σm+1…

σn-CBTB-1b67對(duì)于上述單純形表：（1）一個(gè)基對(duì)應(yīng)一個(gè)單純形表，且單純形表中必須有一個(gè)初始單位基。（2）從單純形表中，可立即得到一個(gè)基可行解：

x1=b1,x2=b2,…,xm=bm,xm+1=xm+2=…=xn=0（3）用檢驗(yàn)數(shù)的計(jì)算公式很容易計(jì)算檢驗(yàn)數(shù)，并可根據(jù)三個(gè)判別定理判別上述基可行解是否為最優(yōu)解或線性規(guī)劃問題無最優(yōu)解。682.進(jìn)基變量的選擇cj

c1c2…

cmcm+1…ck…cnθ

CBXBb

x1x2

…

xm

xm+1…xk

…

xn

c1x1

c2

x2∶

∶

cm

xmb1

b2

∶bm

10…0a1,m+1…

a1k

…

a1n01…0a2,m+1…

a2k

…

a2n∶∶

…

∶

∶

…∶…∶00…1am,m+1…amk

…amnσj

-CBTB-1b

00…0σm+1…σk…σn選取

所對(duì)應(yīng)的變量xk為進(jìn)基變量。693.出基變量的選擇cj

c1…

cl

…

cmcm+1…ck…cnθ

CBXBb

x1…xl

…

xm

xm+1…xk

…

xn

c1x1

∶∶cl

xl∶

∶

cm

xmb1∶bl

∶bm

1…0…0a1,m+1…

a1k

…

a1n∶…∶

…

∶

∶

…∶…∶0…1…0al,m+1…

alk

…

aln∶…∶

…

∶

∶

…∶…∶0…0…1am,m+1…

amk

…amnθ1∶θl∶θmσj

-CBTB-1b

0…0…0σm+1…σk…σn選取

所對(duì)應(yīng)的變量xl為出基變量。704.旋轉(zhuǎn)運(yùn)算cj

c1…

cl

…

cmcm+1…ck…cnθ

CBXBb

x1…xl

…

xm

xm+1…xk

…

xn

c1x1

∶∶cl

xl∶

∶

cm

xmb1∶bl

∶bm

1…0…0a1,m+1…

a1k

…

a1n∶…∶

…

∶

∶

…∶…∶0…1…0al,m+1…

[alk]

…

aln∶…∶

…

∶

∶

…∶…∶0…0…1am,m+1…

amk

…amnσj

ck

xkbl/alk0…1/alk…0al,m+1/alk…1…aln/alkb1’1…-a1k/alk…0a1,m+1’…

0

…

a1n’bm’0…-amk/alk…1am,m+1’…

0

…

amn’71二、實(shí)例化為標(biāo)準(zhǔn)型72單純型表算法

X(0)＝(0,0,8,16,12)T以[1]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x1為換入變量，x3為換出變量

0

qi

3

0

0

x5

x2

x3

x40

x4

x3XB

b

sj

0

x1CB

2cj

x1

cj

x2

x3

x4

x5

1

4

0

2

0

4

1

0

0

0

1

0

0

0

1

2

3

0

0

0

b816

12

XB

x3

x4

x5

CB

0

0

0以[4]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x2為換入變量，x5為換出變量

sj

2

3

0

0

0

qi

8/2

—

12/4[4]

x2

3主元列主元行

0

0

0

1/43

1

4

0

1

016

0

0

1

1

0

-1/22X(1)＝(0,3,2,16,0)T

2

0

0

-3/4

016/4

2/1

—

[1]73此時(shí)達(dá)到最優(yōu)解。X*=(4,2),maxZ=14。

0

qi

3

0

0

x5

x2

x3

x40

x4

x23

XB

b

sj

x1CB

2cj

0

qi

3

0

0

x5

x2

x3

x4x23

x1XB

b

sj

2

x1CB

2cj

0

0

0

1/43

10

-2

0

1/4

0

x1

2

0

1

1

0

-1/22

[2]

0-4

128

08/2

12

—

x50

0

-2

1/2

14

0

1

0

1/4

04

0

1/2

-1/8

0

02

10

-3/2

-1/8

0

0X(3)＝(4,2,0,0,4)TX(2)＝(2,3,0,8,0)T以[2]為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，x5為換入變量，x4為換出變量744x1=164x2=12x1+2x2=8x1x2484O三、單純形表與圖解法的對(duì)應(yīng)關(guān)系X1=(0,0)T,Z1=0X2=(0,3)T,Z2=9X3=(2,3)T,Z3=13X4=(4,2)T,Z4=14Q1Q2QQ3基可行解基可行解迭代

頂點(diǎn)相鄰的頂點(diǎn)迭代

圖解法：?jiǎn)渭冃伪硭惴ǎ?5對(duì)于極小化問題，其最優(yōu)解的判定定理和進(jìn)基變量的選取和極大化問題剛好相反，如下所示：判別定理1

設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切j∈J（J為非基變量的下標(biāo)集）有σj≥0，則X為線性規(guī)劃的最優(yōu)解。判別定理2

設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切j∈J（J為非基變量的下標(biāo)集）有σj≥0，同時(shí)有某個(gè)非基變量的檢驗(yàn)數(shù)σk=0(k∈J)，則該線性規(guī)劃有無窮多最優(yōu)解；設(shè)X為線性規(guī)劃的一個(gè)基可行解，且對(duì)于一切j∈J（J為非基變量的下標(biāo)集）有σj＞0，則該線性規(guī)劃有唯一最優(yōu)解。判別定理3

設(shè)X為線性規(guī)劃的一個(gè)基可行解，若有σk<0(k∈J)，且pk≤0，即aik≤0（i=1,…,m），則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。在進(jìn)基可行解的轉(zhuǎn)換過程中，進(jìn)基變量的選取原則是：min{σj

|σj<0}=σk，則可以確定xk為換入變量。出基變量的選取原則不變。76一、人工變量法第五節(jié)LP問題的進(jìn)一步討論1.大M法2.兩階段法771.大M法加入人工變量xn+1,xn+2,…,xn+m問題A問題B781.大M法加入人工變量xn+1,xn+2,…,xn+m問題C問題D791.大M法（M為任意大的正數(shù)）加入人工變量x6,x7加入松弛變量x4和剩余變量x5801)人工變量的識(shí)別2)目標(biāo)函數(shù)的處理3)計(jì)算(單純形法)81cj-31100MMθiCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011σj-4M-3+6M1-M1-3M0M000x4103-20100-1-Mx610100-11-211x31-2010001-σj-M-1-11-M00M03M-1注意：本例是求最小值，所以用所有來判別目標(biāo)函數(shù)是否實(shí)現(xiàn)了最小化。因而換入變量xk的選取標(biāo)準(zhǔn)為82結(jié)果得:X*=(4,1,9,0,0,0,0)Z*=-2cj-31100MMCBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001-σj-2-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3σj20001/31/3M-1/3M-2/3（接上表）831.大M法例用單純形法（大M法）求解下列線性規(guī)劃加入松弛變量x3,剩余變量x4，人工變量x584用單純形法計(jì)算，其過程如下表所示：Cj3200-MCBXBbx1x2x3x4x50x322[1]100-Mx512340-11σj12M3+3M2+4M0-M02x2221100-Mx54-50-4-11σj-4+4M-1-5M0-2-4M-M0雖然檢驗(yàn)數(shù)均小于等于0，但基變量中含有非零的人工變量x5=4，所以原問題無可行解851.大M法

大M法的幾點(diǎn)結(jié)論（1）問題B要實(shí)現(xiàn)極大化，必須將人工變量從基變量中換出，否則原問題目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)；（2）若在求解問題B的過程中，已將人工變量從基變量中換出，則已得到問題A的一個(gè)基可行解，可繼續(xù)求解，以獲得問題A的最優(yōu)解；（3）若求解問題B已得到最優(yōu)解，但最優(yōu)解的基變量中含有不為零的人工變量，則問題A無可行解；這是LP問題無解的判別條件。（4）若求解問題B已得到最優(yōu)解，且最優(yōu)解的基變量中不含有人工變量，則問題B的最優(yōu)解就是問題A的最優(yōu)解。86兩階段法(將LP問題分成兩個(gè)階段來考慮)

第I階段:

不考慮原問題是否存在可行解，給原LP問題加入人工變量，并構(gòu)造目標(biāo)函數(shù)，使其為僅含人工變量的和，并要求最小化；然后用單純形法求解，若得W=0，則進(jìn)行第二階段計(jì)算，否則無可行解。

第II階段：將第一階段得到的最終表除去人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問題的系數(shù)，作為第二階段的初始表。87加入松弛變量x4;剩余變量x5;人工變量x6,x7用單純形法求解第一階段的結(jié)果得：881100000-000010-21x30--21-100101x204-52-2100312x4030100-10-100010-21x301-21-100101x61--10010-2310x400010-3-161100010-21x713/201-1021-43x611100011-2111x40x7x6x5x4x3x2x1bXBCB1100000cj此時(shí)，達(dá)到第一階段的最優(yōu)解，W=0891/31/3000-4/32/31009x31-100101x21-2/31/30014x1-31000-1-0010-21x31--100101x214-2100312x40x5x4x3x2x1bXBCB0011-3cj由于人工變量x6=x7=0,所以（0,1,1,12,0）T是該線性規(guī)劃問題的基可行解。于是轉(zhuǎn)入第二階段運(yùn)算：此時(shí)達(dá)到該LP問題的最優(yōu)解：X*=(4,1,9,0,0)T;目標(biāo)函數(shù)值Z*=-2。901.存在兩個(gè)以上的最大正檢驗(yàn)數(shù)。選擇任何變量（對(duì)應(yīng)最大正檢驗(yàn)數(shù)）作為進(jìn)基變量。2.最小比值相同。在下一次迭代中就有一個(gè)或幾個(gè)基變量等于零。二、單純形法中存在的問題如果在一個(gè)基本可行解的基變量中至少有一個(gè)分量為0，則稱此基本可行解是退化的基本可行解，這樣的線性規(guī)劃問題稱為退化的線性規(guī)劃問題。91cj

3/4-201/2-60

00CBXBbx1x2x3x4x5x6x70x501/4-8-191000x601/2-12-1/230100x71001000103/4-201/2-600092cj

3/4-201/2-6000CBXBbx1x2x3x4x5x6x73/4x101-32-4364000x60043/2-150100x710010001σj0047/221-300選取x1為換入變量；選取下標(biāo)最小的x5為換出變量，得下表：此時(shí)換出變量為x1，換入變量為x4，迭代后目標(biāo)函數(shù)值不變。這時(shí)不同的基表示為同一頂點(diǎn)。93當(dāng)線性規(guī)劃問題出現(xiàn)退化時(shí)，用單純形法計(jì)算就會(huì)出現(xiàn)所謂的循環(huán)，即多次迭代，而基從B1,B2,…,又返回到B1，即出現(xiàn)計(jì)算過程的循環(huán)，永遠(yuǎn)達(dá)不到最優(yōu)解。1955年，Beale給出了如下退化與循環(huán)的例子，即用單純形法求解，經(jīng)過6次轉(zhuǎn)換，又回到初始基可行解上，其基變量的轉(zhuǎn)換次序?yàn)?(x5,x6,x7)→(x1,x6,x7)→(x1,x2,x7)→(x3,x2,x7)→(x3,x4,x7)→(x5,x4,x7)→(x5,x6,x7)94解決退化的方法有：“攝動(dòng)法”、“辭典序法”、Bland規(guī)則等1974年Bland提出Bland算法規(guī)則：953.最小比值原則失效cj2300CBXBbx1x2x3x40x36-20113x24-3101cj-Zj-121100-3經(jīng)過一次迭代后可得右表當(dāng)用單純形法求解LP問題迭代到某步時(shí),存在某σk>0,而σk對(duì)應(yīng)列向量Pk’≤0,則此LP問題有無界解.964.在最優(yōu)表中出現(xiàn)某非基變量檢驗(yàn)數(shù)為0（無窮多最優(yōu)解）97CBXBbx1x2x3x4x50x340012/3-1/34x260101/203x14100-2/31/3cj-Zj-360000-10x46003/21-1/24x2301-3/401/43x1810100cj-Zj-360000-1cj034000結(jié)論：若線性規(guī)劃問題存在某非基變量檢驗(yàn)數(shù)為0,而其對(duì)應(yīng)列向量Pk≤0,仍可判斷線性規(guī)劃問題有無窮多最優(yōu)解。98例1

某工廠要用三種原材料D、P、H混合調(diào)配出三種不同規(guī)格的產(chǎn)品A、B、C。已知產(chǎn)品的規(guī)格要求、單價(jià)和原材料的供應(yīng)量、單價(jià)。該廠應(yīng)如何安排生產(chǎn)使利潤最大？產(chǎn)品名稱規(guī)格要求單價(jià)(元/kg）A原材料D不少于50%原材料P不超過25%50B原材料D不少于25%原材料P不超過50%35C不限25原材料名稱每天最多供應(yīng)量(kg)單價(jià)(元/kg)D10065P10025H6035第六節(jié)應(yīng)用舉例解：設(shè)A中D、P、H的含量為x11、x12、x13B中D、P、H的含量為x21、x22、x23

C中D、P、H的含量為x31、x32、x3399用單純形法計(jì)算得結(jié)果：每天生產(chǎn)A產(chǎn)品200kg,分別需要原料:D為100kg;P為50kg;H為50kg.總利潤收入Z=500元/天.100max=-15*x11+25*x12+15*x13-30*x21+10*x22+0*x23-40*x31+0*x32-10*x33;x11+x21+x31<=100;x12+x22+x32<=100;x13+x23+x33<=60;x11/(x11+x12+x13)>=0.50;x12/(x11+x12+x13)<=0.25;x21/(x21+x22+x23)>=0.25;x22/(x21+x22+x23)<=0.50;end101例2華津機(jī)器制造廠專為拖拉機(jī)廠配套生產(chǎn)柴油機(jī)。今年頭四個(gè)月收到的訂單數(shù)量分別為2500臺(tái)，4500臺(tái)，2000臺(tái)，5000臺(tái)柴油機(jī)。該廠正常生產(chǎn)每月可生產(chǎn)柴油機(jī)3000臺(tái)，利用加班還可以生產(chǎn)1500臺(tái)。正常生產(chǎn)成本為每臺(tái)5000元，加班生產(chǎn)還要追加1500元成本，庫存成本為每臺(tái)每月200元。華津廠如何組織生產(chǎn)才能使生產(chǎn)成本最低？假設(shè)第一月初和第四月末庫存為0變量意義(生產(chǎn)成本/臺(tái)、能力）xi第i月正常生產(chǎn)臺(tái)數(shù)(5000、3000)yi第i月加班生產(chǎn)臺(tái)數(shù)(6500、1500)zi第i月月初庫存(200/月.臺(tái))需求2500、4500、2000、5000102設(shè)xi為第i月正常生產(chǎn)的柴油機(jī)數(shù)，yi為第i月加班生產(chǎn)的柴油機(jī)數(shù)，zi為第i月月初柴油機(jī)的庫存數(shù)。103min=5000*(x1+x2+x3+x4)+6500*(y1+y2+y3+y4)+200*(z2+z3+z4);x1+y1-z2=2500;x2+y2+z2-z3=4500;x3+y3+z3-z4=2000;x4+y4+z4=5000;x1<=3000;x2<=3000;x3<=3000;x4<=3000;y1<=1500;y2<=1500;y3<=1500;y4<=1500;一月二月三月四月正常生產(chǎn)臺(tái)數(shù)3000300030003000加班生產(chǎn)臺(tái)數(shù)0100001000月初庫存數(shù)量050001000104例3

某部門在今后5年內(nèi)連續(xù)給以下項(xiàng)目投資：

項(xiàng)目A，第一年至第四年每年年初投資，次年末回收本利115%；項(xiàng)目B，第三年初投資，第五年末回收本利125%，最大投資額不超過4萬元；項(xiàng)目C，第二年初投資，第五年末回收本利140%，最大投資額不超過3萬元；項(xiàng)目D，五年內(nèi)每年初可購買公債，當(dāng)年末歸還，并加利息6%。該部門現(xiàn)有資金10萬元，問該如何確定投資方案，使第五年末擁有的資金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D105第一年第二年第三年第四年第五年106max=1.15*x4A+1.4*x2C+1.25*x3B+1.06*x5D;x1A+x1D=100000;x2A+x2C+x2D=1.06*x1D;x3A+x3B+x3D=1.06*x2D+1.15*x1A;x4A+x4D=1.06*x3D+1.15*x2A;x5D=1.06*x4D+1.15*x3A;x3B<=40000;x2C<=30000;end107例4：營養(yǎng)配餐問題序號(hào)食品熱量蛋白質(zhì)鈣價(jià)格1豬肉100050400142雞蛋8006020063大米9002030034白菜200105002

需求量300055800設(shè)xj為第j種食品每天購入量Minz=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x4

55400x1+200x2+300x3+500x4

800xj

0，j=1，…，4108Min=14*x1+6*x2+3*x3+2*x4;1000*x1+800*x2+900*x3+200*x4>=3000;50*x1+60*x2+20*x3+10*x4>=55;400*x1+200*x2+300*x3+500*x4>=800;Globaloptimalsolutionfound.Objectivevalue:10.00000Totalsolveriterations:0VariableValueReducedCostX10.00000010.66667X20.0000003.333333X33.3333330.000000X40.0000001.333333用Lingo求解109例5：產(chǎn)品配套問題某廠生產(chǎn)一種產(chǎn)品，由兩個(gè)B1

零件和三個(gè)B2零件配置組裝而成。該廠有A1、A2、A3三種機(jī)床可加工上述兩種零件，每種機(jī)床的臺(tái)數(shù)以及每臺(tái)機(jī)床每個(gè)工作日全部用于加工某一種零件的最大產(chǎn)量（即生產(chǎn)率：件/日）見下表。試求該產(chǎn)品產(chǎn)量最大的生產(chǎn)方案。機(jī)床生產(chǎn)率（件/日）機(jī)床數(shù)量機(jī)床類型零件B2零件B118104A3354520302A23A1難點(diǎn)：1)同一臺(tái)機(jī)床加工零件B1和B2的時(shí)間分配；2)零件B1和B2的配套問題，2:3構(gòu)成一件產(chǎn)品。110解：（1）決策變量根據(jù)題意，設(shè)每臺(tái)Ai

(i=1,2,3)機(jī)床每個(gè)工作日加工Bj(j=1,2)零件的時(shí)間為xij(工作日)；Z為零件B1和B2按2:3比例配套的產(chǎn)品數(shù)量（套/日）。（2）約束條件工時(shí)約束：機(jī)床A1：x11+x12=1

機(jī)床A2：x21+x22=1

機(jī)床A3：x31+x32=1

配套約束：零件B1的產(chǎn)量：3′20x11＋2′35x21

＋4′10x31

零件B2的產(chǎn)量：3′30x12＋2′45x22

＋4′18x32111非負(fù)約束

xij30(i=1,2,3；j=1,2)（3）目標(biāo)函數(shù)

maxZ=f112設(shè)每臺(tái)Ai

(i=1,2,3)機(jī)床每個(gè)工作日加工Bj(j=1,2)零件的時(shí)間為xij(工作日)；Z為零件B1和B2按2:3比例配套的產(chǎn)品數(shù)量（套/日）。

maxZ=fx11+x12=1

x21+x22=1

x31+x32=1

xij30(i=1,2,3；j=1,2)

113

max=f;x11+x12=1;x21+x22=1;x31+x32=1;f<=30*x11+35*x21+20*x31;f<=30*x12+30*x22+24*x32;Globaloptimalsolutionfound.Objectivevalue:44.50000Totalsolveriterations:2VariableValueReducedCostF44.500000.000000X110.31666670.000000