經(jīng)濟(jì)學(xué)運(yùn)籌學(xué)

1三、課堂教學(xué)內(nèi)容章次內(nèi)容總學(xué)時(shí)數(shù)緒論1一線性規(guī)劃及單純形法16/2二對(duì)偶理論與靈敏度分析12/2三運(yùn)輸問(wèn)題6/1四整數(shù)規(guī)劃6/1五動(dòng)態(tài)規(guī)劃5/1六動(dòng)態(tài)規(guī)劃應(yīng)用舉例4七圖與網(wǎng)絡(luò)分析10/1八網(wǎng)絡(luò)計(jì)劃2九排隊(duì)論10總學(xué)時(shí)數(shù)72/82運(yùn)籌學(xué)的工作步驟明確問(wèn)題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評(píng)價(jià)結(jié)果簡(jiǎn)化？YesNoNo明確問(wèn)題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評(píng)價(jià)結(jié)果結(jié)束Yes滿(mǎn)意？3

數(shù)學(xué)規(guī)劃是管理科學(xué)中求最優(yōu)或最有效使用有限資源的方式以達(dá)到既定目標(biāo)的一個(gè)領(lǐng)域，又稱(chēng)為最優(yōu)化。有限的資源：從地下抽出的原油、傾倒垃圾和有害廢物的場(chǎng)地、企業(yè)招聘的人員、餐館放座位的空間、一個(gè)人每天工作活動(dòng)的時(shí)間，做某件事情需要花的錢(qián)……1、確定產(chǎn)品組合：多數(shù)企業(yè)可以生產(chǎn)多種產(chǎn)品，但不同產(chǎn)品所需的原材料和工時(shí)不同，類(lèi)似地，它們產(chǎn)生的利潤(rùn)也不同，管理者必須決定每種產(chǎn)品產(chǎn)量以使利潤(rùn)最大或以最小成本滿(mǎn)足需求。2、選路與物流：許多零售公司在各地都有提供商店貨物的倉(cāng)庫(kù)，倉(cāng)庫(kù)可供的貨物數(shù)量和各商店所需的貨物數(shù)量是不同的，需要確定從倉(cāng)庫(kù)運(yùn)送到商店的貨物所需成本最低的方法。4

線性規(guī)劃

(LinearProgramming——LP)是數(shù)學(xué)規(guī)劃的一個(gè)分支，是一種解決在線性約束條件下追求最大或最小的線性目標(biāo)函數(shù)的方法。一般可以表達(dá)成以下兩個(gè)問(wèn)題中的一個(gè)：

當(dāng)資源給定時(shí)，要求完成的任務(wù)最多；當(dāng)任務(wù)給定時(shí)，要求為完成任務(wù)所消耗的資源最少。數(shù)學(xué)規(guī)劃中的模型都是線性函數(shù)時(shí)，稱(chēng)線性規(guī)劃。5第一章線性規(guī)劃及單純形法

第一節(jié)線性規(guī)劃問(wèn)題及數(shù)學(xué)模型（P8）III設(shè)備原材料A原材料B單件利潤(rùn)140220438臺(tái)時(shí)16kg12kg6設(shè)X1﹑X2為工廠1﹑2的日處理量

MinZ=1000X1+800X2

X1≥1(1)0.8X1+X2≥1.6(2)X1≤2(3)X2≤1.4(4)X1﹑X2≥0環(huán)保要求：(污水量/河水量)≤0.2%，河流自?xún)袅Γ?0%500萬(wàn)m3200萬(wàn)m31.4萬(wàn)m3，800元/萬(wàn)m3

o工廠2例2（P9）

2萬(wàn)m3

，1000元/萬(wàn)m3

o工廠17

LP問(wèn)題的共同特征：每一個(gè)問(wèn)題變量都用一組決策變量（x1,x2,…,xn）表示某一方案，這組決策變量的值代表一個(gè)具體方案，這些變量是非負(fù)的。

存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示。目標(biāo)函數(shù)用決策變量的線性函數(shù)來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。

目標(biāo)：objective,goal,target8LP模型一般形式目標(biāo)函數(shù)Max(Min)Z=C1X1+C2X2+...+CnXn

a11X1+a12X2+...+a1nXn≤(=,≥)b1約束條件a21X1+a22X2+...+a2nXn≤(=,≥)b2

┆┆am1X1+am2X2+...+amnXn≤(=,≥)bm

非負(fù)條件X1﹑X2...Xn≥(=,≤)0或無(wú)約束94x1=164x2=12x1+2x2=8x1x248430Q(4,2)Z=2x1+3x2最優(yōu)生產(chǎn)計(jì)劃為：生產(chǎn)I產(chǎn)品4件，生產(chǎn)II產(chǎn)品2件。三、兩變量線性規(guī)劃問(wèn)題的圖解法作出LP問(wèn)題的可行域作出目標(biāo)函數(shù)的等值線移動(dòng)等值線到可行域邊界得到最優(yōu)點(diǎn)圖解法步驟（圖解法意義不大，但可直觀揭示有關(guān)概念）10有可行解有最優(yōu)解唯一解無(wú)窮多解無(wú)最優(yōu)解（可行域?yàn)闊o(wú)界）無(wú)可行解（無(wú)解）LP解的可能情況：

若LP問(wèn)題有最優(yōu)解，則要么最優(yōu)解唯一，要么有無(wú)窮多最優(yōu)解。

110 48 12 x1963x2①③②可行域Z=364,6多重解舉例

MaxZ=3X1+4X2

X1≤8①2X2≤12②3X1+4X2≤36③X1﹑X2≥0此線段上的點(diǎn)均為最優(yōu)點(diǎn)12-1 01 2 3x121x2可行域無(wú)界解舉例MaxZ=3X1+2X2

-2X1+X2≤2①X1-3X2≤3②X1﹑X2≥0①②Z增大方向130 24 6 8x1x2無(wú)可行解舉例：

MaxZ=2X1+3X2

X1+2X2≤8①4X1≤16②4X2≤12③

-2X1+X2≥4④X1﹑X2≥0①③

6 420

④無(wú)公共區(qū)域(可行域)②14

四、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型15線性規(guī)劃標(biāo)準(zhǔn)形矩陣描述(A,C,b,X均為矩陣)：X—決策變量列向量。b—約束條件右端常數(shù)（資源）列向量。C—目標(biāo)函數(shù)價(jià)值系數(shù)行向量。Amxn—約束條件左端系數(shù)矩陣。

a11a12...a1na21a22...a2nA=┆┆┆am1am2...amn

=[P1，P2...Pn]C=[c1c2...cn]

b1x1b2x2b=┆X=┆bmxnMaxZ=CX|AX=b，X≥016非標(biāo)準(zhǔn)形LP問(wèn)題化為標(biāo)準(zhǔn)形：1）若目標(biāo)函數(shù)為MinZ，令Z'=-Z，則MinZ等價(jià)于MaxZ'2）

若為不等式約束：若為≤，在方程左邊加一非負(fù)新變量，稱(chēng)松弛（Slack）變量若為≥，在方程左邊減一非負(fù)新變量，稱(chēng)剩余（Surpius）變量或松弛變量四個(gè)特點(diǎn)：極大化目標(biāo)﹑等式約束﹑約束右端常數(shù)bi≥0﹑決策變量Xj≥0。17非標(biāo)準(zhǔn)形LP問(wèn)題化為標(biāo)準(zhǔn)形：3）

若bi<0,方程兩邊同乘（-1）4）

若變量不滿(mǎn)足非負(fù)：若xK≤0，令xK=-xK',xK'≥0，用此式替換模型中xk

若xK無(wú)約束，令xK=xK'-xK'',xK'﹑xK''≥0，用此式替換模型中xk18例1可化為例4MinZ=-1X1+2X2-3X3X1+X2+X3≤7X1-X2+X3≥2-3X1+X2+2X3=5X1﹑X2≥0﹑X3無(wú)約束MaxZ'=X1-2X2+3（X4-X5）+0X6-0X7X1+X2+（X4-X5）+X6=7X1-X2+（X4-X5）-X7=2-3X1+X2+2（X4-X5）

=5X1﹑X2﹑X4﹑X5﹑X6﹑X7≥0191.4LP問(wèn)題解的概念（可行解﹑基﹑基可行解﹑可行基）MaxZ=2X1+3X2+4X3+7X42X1+3X2-X3-4X4=8X1-2X2+6X3-7X4=-3X1﹑X2﹑X3﹑X4≥020X1=(1,14/7,0,0);X2=(45/13,0,-14/13,0)X3=(34/5,0,0,7/5);X4=(0,45/16,7/16,0)X5=(0,68/29,0,-7/29);X6=(0,0,-68/31,-45/31)基可行解X1﹑X3﹑X4,最優(yōu)解X3，Z=117/5思考：X=(-9/7,27/7,1,0)、X=(7,1,1,2)是何解？21例1

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基可行解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)型22線性規(guī)劃標(biāo)準(zhǔn)型問(wèn)題解的關(guān)系約束方程的解空間基解可行解非可行解基可行解23MaxZ=3X1+5X2+0X3+0X4+0X5系數(shù)矩陣:X1+X3=8① 10100

2X2+X4

=12②020103X1+4X2+X5

=36③ 34001X1,X2,,X3,X4,X5≥0C=（35000）令x1,x2=0，得：X=(0081236)z=0

1令x2,x3=0，得：X=(8001212)z=24

2

保留的變量稱(chēng)基變量，由解方程求得。移到右邊并令為零的變量稱(chēng)非基變量。相應(yīng)于基變量的系數(shù)列稱(chēng)基。24令x4,x5=0，得：X=(46400)z=425令x2,x5=0，得：X=(120-4120)z=366令x1,x4=0，得：X=(068012)z=303令x3,x5=0，得：X=(83060)z=39425令x1,x5=0，得：X=(098-60)z=45

7令x3,x4=0，得：X=(8600-12)z=54

8∵000210=0401

∴無(wú)解9

∵110000=0301

∴無(wú)解10

26小結(jié)

本例3階系數(shù)行列式共有10個(gè)，其中有8個(gè)行列式≠0，它們稱(chēng)為基，其中的每一列Pj(j=1,2,…,m)稱(chēng)基向量，另2個(gè)行列式=0，無(wú)意義。與基向量Pj對(duì)應(yīng)的變量xj稱(chēng)為基變量，記為XB

，其余變量稱(chēng)為非基變量，記為XN

根據(jù)基求出的解稱(chēng)基解，本例有8個(gè)基解，其中有5個(gè)解的所有變量都≥0(即可行)，這5個(gè)解稱(chēng)基可行解，給出這5個(gè)可行解的基稱(chēng)為可行基。在5個(gè)可行解中，第5個(gè)解的目標(biāo)函數(shù)值最大，故又稱(chēng)這個(gè)解的可行基為最優(yōu)基。27

線性規(guī)劃解的概念與定理

可行解：滿(mǎn)足約束方程組和非負(fù)條件的解?；?B)：約束方程系數(shù)矩陣Am*n(m為方程個(gè)數(shù)，n為變量個(gè)數(shù))中滿(mǎn)足行列式≠0的m階方陣。對(duì)應(yīng)于基系數(shù)列的變量稱(chēng)基變量 XB，非基系數(shù)列對(duì)應(yīng)變量稱(chēng)非基變量XN

?；猓焊鶕?jù)某個(gè)基，令非基變量=0而求出的解。28線性規(guī)劃解的概念與定理

基可行解：滿(mǎn)足非負(fù)條件的基解?？尚谢簩?duì)應(yīng)于可行解的基。最優(yōu)基：給出最優(yōu)目標(biāo)函數(shù)值的可行基。定理：若線性規(guī)劃問(wèn)題存在最優(yōu)解，則必定能在其基可行解中得到。從圖形上看，也就是說(shuō)最優(yōu)解一定能在其可行域的頂點(diǎn)處得到。29第2節(jié)LP理論基礎(chǔ)：(凸集、凸組合、頂點(diǎn)）凸集：設(shè)K為En的一點(diǎn)集，若對(duì)于任意X(1)﹑X(2)€K，都有αX(1)+（1-α）X(2)

€K，（0≤α≤1）；則稱(chēng)K為凸集。凸組合：設(shè)X(1)﹑X(2)…

X(k)為En的

K個(gè)點(diǎn)，若存在μ1、μ2…

μk，且0≤μi≤1，i=1，2…k;使X=μ1X(1)+μ2X(2)

…

+μkX(k)則稱(chēng)X為X(1)，X(2)

…

X(k)的凸組合。頂點(diǎn)：設(shè)K為凸集，X€K，若X不能用不同的兩點(diǎn)X(1)﹑X(2)€K的線性組合表示為αX(1)+（1-α）X(2)

（0≤α≤1）；則稱(chēng)X為K的一個(gè)頂點(diǎn)。30第2節(jié)LP理論基礎(chǔ)：(定理1、2*、3）證明：設(shè)X(1)﹑X(2)為L(zhǎng)P可行域D內(nèi)任意兩點(diǎn)，X(1)≠X(2)

，則AX(1)=b，AX(2)=b，X(1)≥0，X(2)≥0令X為X(1)﹑X(2)

連線上任意一點(diǎn)，即X=αX(1)+（1-α）X(2)

，（0≤α≤1）代入約束AX=αAX(1)+（1-α）AX(2)=αb+（1-α）b=b，又∵α≥0，（1-α）≥0，∴X≥0，即X(1)﹑X(2)

連線上任意一點(diǎn)也在D內(nèi)，由凸集定義，D為凸集。定理1：若LP問(wèn)題存在可行域，則其可行域D={X|}是凸集。31證明：設(shè)X(1)﹑...﹑X(k)為可行域頂點(diǎn)，相應(yīng)目標(biāo)值Z(1)﹑...﹑Z(k)

，其中第m個(gè)頂點(diǎn)X(m)處目標(biāo)值最大，記為Z(m)

，若X(0)

不是頂點(diǎn)但其目標(biāo)值最優(yōu)，則：X(0)=αiX(i)

，αi≥0，αi=1CX(0)=αiCX(i)=αiZ(i)≤αiZ(m)=Z(m)

據(jù)假使CX(0)

為最優(yōu)值，∴X(m)處也能達(dá)到最優(yōu)。定理3：若可行域有界，LP問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。32第3節(jié)單純形法(GeorgeDantgig于1947年提出)

由線性代數(shù)知，對(duì)標(biāo)準(zhǔn)形LP問(wèn)題，理論上可以求出所有基解（枚舉法），再通過(guò)觀察找出其中的可行解（基可行解），進(jìn)而找出最優(yōu)解。但如果變量和方程較多，比如m=50，n=100，所有基解有可能達(dá)1029個(gè)，即使計(jì)算機(jī)每秒能求解1億個(gè)這樣的方程組，也需要30萬(wàn)億年！因此，必須尋求有效的算法.33

為加快計(jì)算速度，算法必須具有兩個(gè)功能，一是每得到一個(gè)解，就來(lái)檢驗(yàn)是否已經(jīng)最優(yōu)，若是，停止。二是若不是最優(yōu)，要保證下一步得到的解不劣于當(dāng)前解。基于線性代數(shù)原理，并將上述功能貫穿于算法過(guò)程，這就是線性規(guī)劃的單純形法。

第3節(jié)單純形法(GeorgeDantgig于1947年提出)34Z=2X1+3X2,C1=2>0,C2=3>0,∴此解非最優(yōu),選X2進(jìn)基.

令X1,X2=0,稱(chēng)非基變量

X1+2X2+X3

=84X1+X4

=164X2+X5=12X=(0081612),Z=0MaxZ=2X1+3X2+0X3+0X4+0X5X1+2X2+X3

=84X1+X4

=164X2+X5

=12X1,X2,X3,X4,X5

≥0X3812100X41640010X51204001X1+2X2+X3

=84X1+X4

=164X2+X5=12用表表示：35當(dāng)X2=min(8/2,-,12/4)=3時(shí),X5=0,∴X5出基。X1+2X2+X3

=84X1+X4

=16

4X2+X5=128/2-12/4X1+2X2+X3

=84X1+X4

=164X2+X5=12X1+2X2+X3

=84X1+X4

=164X2+X5=12X1+2X2+X3

=84X1+X4

=164X2+X5=12基變換36X1+X3

-X5/2=2①’=①-2*③’4X1+X4

=16

②’=②

X2

+X5/4

=3③’=③/4

解基變量并保持右端常數(shù)是其值的形式,對(duì)系數(shù)作如下變換：X1+2X2+X3

=84X1+X4

=164X2+X5=12

①’=①-2*③’：X1+2X2+X3

=82（X2

+X5/4

=3）=X1+X3

-X5/2=2

204001X321010-1/2X41640010X2301001/4用表表示：X2X537X3812100X41640010X51204001X321010-1/2X41640010X2301001/4X1+X3

-X5/2=24X1+X4

=16

X2

+X5/4

=3X1+2X2+X3

=84X1+X4

=164X2+X5=12

令X1,X5=0,得X=(032160),將X1、X2代入目標(biāo)函數(shù)，并寫(xiě)成只含非基變量形式得：Z=2X1+3(3-X5/4)=9+2X1-3X5/4。∵X1

系數(shù)C1=2>0,∴此解非最優(yōu),選X1進(jìn)基。和前一步對(duì)比：38當(dāng)X1=min(2/1,16/4,-)=2時(shí),X3=0,∴X3出基。

X1

+X3

-X5/2=24X1

+X4

=16

X2

+X5/4

=32/116/4-

X1

+X3

-X5/2=24X1

+X4

=16

X2

+X5/4

=3X1+X3

-X5/2=24X1+X4

=16

X2

+X5/4

=3

X1

+X3

-X5/2=24X1

+X4

=16

X2

+X5/4

=3基變換39

解基變量并保持右端常數(shù)是其值的形式,對(duì)系數(shù)作如下變換：

②’=②-4*①

：

4X1+X4

=164（X1+X3-X5

/2=2)=-4X3+X4+2X5

=8

140100X121010-1/2X4800-412X230100-1/4用表表示：

X1

+X3

-X5/2=2①4X1

+X4

=16②

X2

+X5/4

=3

③X1X3X1

+X3

-X5/2

=2①’=①

-4X3+X4+2X5=8

②’=②-4*①

X2

-X5/4

=3③’=③40

令X3,X5=0,得X=(23080),將X1、X2代入目標(biāo)函數(shù)，并寫(xiě)成只含非基變量形式得：

Z=2(2-X3+X5/2)+3(3-X5/4)=13-2X3+X5/4

?！遆5

系數(shù)C5=1/4>0,∴此解非最優(yōu),選X5進(jìn)基。和前一步對(duì)比：X1

+X3

-X5/2

=2

-4X3+X4+2X5=8

X2

+X5/4

=3X121010-1/2X4800-412X230100-1/4X3210101/2X41640010X2301001/4X1+X3

-X5/2=24X1+X4

=16

X2

+X5/4

=341當(dāng)X5=min(-,8/2,3*4)=4時(shí),X4=0,∴X4出基。-8/23*4基變換X1

+X3

-X5/2

=2

-4X3+X4+2X5

=8

X2

+X5/4

=3X1

+X3

-X5/2

=2

-4X3+X4+2X5

=8

X2

+X5/4

=3X1

+X3

-X5/2

=2

-4X3+X4+2X5=8

X2

+X5/4

=3X1

+X3

-X5/2

=2

-4X3+X4+2X5

=8

X2

+X5/4

=342

解基變量并保持右端常數(shù)是其值的形式,對(duì)系數(shù)作如下變換：

①’=①+②’/2：

X1+X3-X5/2

=2+(-2X3+X4/2+X5=4)/2=X1+X4/4

=4

-1/221/4010X141001/40X5400-21/21X22011/2-1/80用表表示：X5X4X1

+X3

-X5/2

=2①

-4X3+X4+2X5

=8②

X2

+X5/4

=3③X1+X4/4

=4①’=①+

②’/2-2X3+X4/2+X5

=4

②’=

②/2X2

+X3/2-X4/8

=2

③’=③-②’/4

③’=③-②’/4

：

X2+X5/4

=3-(-2X3+X4/2+X5=4)/4=X2+X3/2-X4/8

=2

43

令X3,X4=0,得X=(42004),將X1、X2代入目標(biāo)函數(shù)，并寫(xiě)成只含非基變量形式得：

Z=2(4-X4/4)+3(2-X3/2+X4/8)=14-3X3/2-X4/8

。和前一步對(duì)比：X1+X4/4

=4-2X3+X4/2+X5

=4X2

+X3/2-X4/8

=2X141001/40X5400-21/21X22011/2-1/80X1

+X3

-X5/2

=2

-4X3+X4+2X5=8

X2

+X5/4

=3X121010-1/2X4800-412X230100-1/444∵目標(biāo)函數(shù)中所有變量的系數(shù)均<或=0,∴得最優(yōu)解：

X*=(42004),Z*=14

答：該廠生產(chǎn)I產(chǎn)品4件，II產(chǎn)品2件，可獲最大利潤(rùn)14元。

將上述方程組求解過(guò)程，用列表形式表達(dá)，即為線性規(guī)劃單純形法。Z=2(4-X4/4)+3(2-X3/2+X4/8)=14-3X3/2-X4/8

。45

x3x4x2←表1-3表1-421010-1/2301001/4

檢驗(yàn)行

j2000-3/42/1=2

16/4=4-↓↓←8/2=4

-12/4=31640010

00346表1-521010-1/2800-412301001/4

x1x4x2

203檢驗(yàn)行

j00-201/4

x3x4x2

00321010-1/21640010301001/4

檢驗(yàn)行

j2000-3/42/1=2

16/4=4-↓←-8/2=43*4=12↓←表1-447301001/421010-1/2800-412

x1x4x2

203檢驗(yàn)行

j

00-201/4-8/2=43*4=12↓←

20341001/40400-21/212011/2-1/80

檢驗(yàn)行

j00-1.5-1/80

x1x5x2表1-5表1-6最優(yōu)解：x1=4x2=2x3=0x4=0x5=4z=14484x1=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)渭冃伪硭惴ǎ?9第4節(jié)單純形步驟1.化標(biāo)準(zhǔn)形2.在系數(shù)矩陣中找出（構(gòu)造）m（方程個(gè)數(shù)）階單位矩陣，以其為初始基，對(duì)應(yīng)變量為基變量，畫(huà)初始單純形表；3.計(jì)算檢驗(yàn)數(shù)

j，若所有

j≤0，得最優(yōu)解，否則轉(zhuǎn)4；50第4節(jié)單純形步驟4.若某個(gè)

j>0，其對(duì)應(yīng)列系數(shù)均≤0，得無(wú)界解，停止，否則轉(zhuǎn)5；5.選最大

j(>0)對(duì)應(yīng)變量進(jìn)基，最小比值

對(duì)應(yīng)變量出基（這種做法稱(chēng)

規(guī)則），標(biāo)出主元(進(jìn)基變量和出基變量交叉處元素)；6.將主元變?yōu)?，主元列(主元所在列)其它元素變?yōu)?，得新表，返回3。51檢驗(yàn)數(shù)

j算法：

基變量檢驗(yàn)數(shù)總是0，只需求非基變量檢驗(yàn)數(shù)。方法是：將左列基變量?jī)r(jià)值系數(shù)與所求非基變量系數(shù)列分別相乘再相加，然后被該非基變量?jī)r(jià)值系數(shù)減去。

最小比值算法：

以b列為分子，主元列元素(>0)為分母,計(jì)算各行比值，其最小者為。

52

j算法公式推導(dǎo)：

設(shè)前m個(gè)為基變量，則xi=bi-aijxj(i=1…m)代入目標(biāo)函數(shù)

Z=cixi+cjxj=ci(bi-aijxj)+cjxj=cibi-ciaijxj+cjxj=cibi+(cj-ciaij)xj53Z=cibi-ciaijxj+cjxj=cibi+(cj-ciaij)xj令Z0=cibi，Zj=ciaij,則Z=Z0+(cj-Zj)xj令

j=cj-Zj=cj-[c1a1j+c2a2j+…+cmamj]，則Z=Z0+

jxj54例8MinZ=-3X1+X2+X3

X1-2X2+X3≤11-4X1+X2+2X3≥3

-2X1+X3=1X1,X2,X3≥0化標(biāo)準(zhǔn)形：MinZ=-3X1+X2+X3+0X4+0X5

X1-2X2+X3+X4

=11-4X1+X2+2X3-X5=3

-2X1+X3=1X1,X2,X3,X4,X5

≥0

系數(shù)矩陣：1-2110-4120-1-20100系數(shù)矩陣：1-211000-4120-110-2010001加人工變量：MinZ=-X1+X2+X3+0X4+0X5+MX6+MX7

X1-2X2+X3+X4

=11-4X1+X2+2X3-X5+X6

=3

-2X1+X3+X7

=1X1,X2,X3,X4,X5,X6,X7

≥055松弛變量(X4,X5)是化不等式為等式而添加的變量,其意義表示約束兩邊不等的部分。

人工變量(X6,X7)

是在標(biāo)準(zhǔn)化以后，為了湊成單位矩陣而添加的變量。只有在最優(yōu)解中人工變量=0，所得解才是原問(wèn)題解，若最優(yōu)解中含有人工變量，原問(wèn)題無(wú)解。在迭代過(guò)程中，為盡快剔除基變量中的人工變量，將目標(biāo)函數(shù)中人工變量系數(shù)賦以無(wú)窮大數(shù)M(對(duì)Max，則為-M)，使其對(duì)目標(biāo)函數(shù)構(gòu)成懲罰，也就是說(shuō)，只有人工變量=0，才有可能實(shí)現(xiàn)目標(biāo)最優(yōu)。這就是大M法基本思想。56用大M法求解MinZ=-3X1+X2+X3+0X4+0X5+MX6+MX7

X1-2X2+X3+X4=11-4X1+X2+2X3-X5+X6=3

-2X1+X3+X7=1X1,X2,X3,X4,X5,X6,X7≥0系數(shù)矩陣：1-211000-4120-110-2010001

Cj-31100MMCBXBbX1X2X3X4X5X6X70X4111-211000MX63-4120-110MX71-20100016M-31-M1-3M0M00↑113/21

1-2010001103-20100-1

10100-11-2X4X6X30M1

-11-M00M03M-1↑-1-←←57X4X6X3←10100-11-21-2010001123001-22-5X4X2X3011↑12/3--←41001/3-2/32/3-5/310100-11-290012/3-4/34/3-7/30001/31/3M-1/3M-2/3X1X2X3-10001M-1M+1-311最優(yōu)解：X*=(4190000)最優(yōu)（小）值：Z*=-2Cj-31100MMCBXBbX1X2X3X4X5X6X7

1-2010001103-20100-1

10100-11-2

-11-M00M03M-1↑0M158l

兩階段法(將LP問(wèn)題分成兩個(gè)階段來(lái)考慮)第I階段:不考慮原問(wèn)題是否存在可行解，給原LP問(wèn)題加入人工變量，構(gòu)造僅含人工變量的目標(biāo)函數(shù)w并要求最小化；然后用單純形法求解，若得w=0，則進(jìn)行第二階段計(jì)算，否則無(wú)可行解。第II階段：除去第一階段最終表中的人工變量，將目標(biāo)函數(shù)行的系數(shù)換為原問(wèn)題的系數(shù)，作為第二階段的初始表，繼續(xù)用單純形法求解。

59cj0000011CBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011σj6-1-301000x4103-20100-1-1x610100-11-210x31-2010001-σj0-1001030x4123001-22-540x210100-11-2-0x31-2010000-σj0000011此時(shí)，達(dá)到第一階段的最優(yōu)解，W=060

二、單純形法遺補(bǔ)1.存在兩個(gè)以上的最大正檢驗(yàn)數(shù)時(shí)，任選一個(gè)最大正檢驗(yàn)數(shù)對(duì)應(yīng)變量作為進(jìn)基變量。2.最小比值相同（退化）：當(dāng)最小比值不止1個(gè)時(shí)，在下一步迭代中就有1個(gè)或幾個(gè)基變量等于0，這種現(xiàn)象稱(chēng)退化。當(dāng)出現(xiàn)退化時(shí)，有可能使計(jì)算進(jìn)入死循環(huán)。為避免死循環(huán)，應(yīng)選擇下標(biāo)最小的基變量出基。

出現(xiàn)死循環(huán)的例子

MaxZ=3