Chapter線性規(guī)劃及單純形法實(shí)用

會計(jì)學(xué)1Chapter線性規(guī)劃及單純形法實(shí)用22023/1/17§1線性問題的數(shù)學(xué)模型問題的提出

例1.用一塊邊長為a的正方形鐵皮做一個容器，應(yīng)如何裁剪，才能使做成容器的容積最大？ax解：利用高等數(shù)學(xué)的知識

V=(a-2x)2x

求V(x)的最大值即可。

[問題？]第1頁/共74頁32023/1/17線性規(guī)劃的數(shù)學(xué)模型問題的提出–

例2

(生產(chǎn)計(jì)劃安排，要求利潤最大)解：設(shè)在計(jì)劃期內(nèi)生產(chǎn)產(chǎn)品I和產(chǎn)品II分別為x1和x2件(決策變量)目標(biāo)是要使

z=2x1+3x2達(dá)到最大。(目標(biāo)函數(shù))限制條件是：

（約束條件）

2x1+2x2

12和

2x1

16以及

5x2

15

要求x1,x20加工設(shè)備ABC單件利潤產(chǎn)品I2402元產(chǎn)品II2053元設(shè)備時(shí)限12h16h15h——第2頁/共74頁42023/1/17線性規(guī)劃的數(shù)學(xué)模型問題的提出–

例子之三(合理下料問題)

現(xiàn)有一批10m長的貴重鋼筋，需要截取3m和4m長的鋼筋各50根，試問如何截取，才能使原料最??？問題分析：先確定截取方案建立數(shù)學(xué)規(guī)劃模型問題：模型是否有別的形式？截取方案IIIIII3m鋼筋2304m鋼筋102廢料長0m1m2m第3頁/共74頁52023/1/17線性規(guī)劃問題數(shù)學(xué)模型的定義線性規(guī)劃模型組成的三要素：決策變量目標(biāo)函數(shù)約束條件定義1

在線性規(guī)劃數(shù)學(xué)模型中，如果決策變量為可控的連續(xù)變量，目標(biāo)函數(shù)和約束條件都是線性的，稱這類模型為線性規(guī)劃問題的數(shù)學(xué)模型。問題：例一中的問題是否為線性規(guī)劃模型？第4頁/共74頁62023/1/17線性規(guī)劃問題數(shù)學(xué)模型的一般形式關(guān)于幻燈片中的數(shù)學(xué)符號：小寫斜體字母表示實(shí)數(shù)，如a,b,c,x,x1,y,z等小寫黑體字母表示向量，如x,y,z等大寫黑體字母表示矩陣，如A,B,C等線性規(guī)劃(LP)數(shù)學(xué)模型的一般形式或第5頁/共74頁72023/1/17線性規(guī)劃數(shù)學(xué)模型向量和矩陣形式(LP)向量形式(LP)矩陣形式

第6頁/共74頁82023/1/17線性規(guī)劃問題的標(biāo)準(zhǔn)形式什么是(LP)問題的標(biāo)準(zhǔn)形式？

滿足如下條件：目標(biāo)函數(shù)是求極大值；約束條件全為等式；bi和xj全為非負(fù)數(shù)。第7頁/共74頁92023/1/17(LP)一般形式向標(biāo)準(zhǔn)形式的轉(zhuǎn)化(LP)一般形式向標(biāo)準(zhǔn)形轉(zhuǎn)化的情況：目標(biāo)函數(shù)是求極小值；約束條件為不等式“”的情形（松弛變量，例2）；約束條件為不等式“”

的情形（剩余變量，例3）；取值無約束的變量；某個變量xj0問題：某個變量有上下界限制，比如lxju，如何處理？例3.見書P12。第8頁/共74頁102023/1/17線性規(guī)劃問題解的若干重要概念線性規(guī)劃問題的任務(wù)

從滿足約束條件（2）和非負(fù)條件（3）的方程組中，找到使目標(biāo)函數(shù)（1）取得最大值的解?？尚薪夂涂尚杏?/p>

滿足約束和非負(fù)條件的解x。最優(yōu)解基、基向量、基變量

設(shè)A=(aij)mn，r(A)=m，稱A的一個m階滿秩子矩陣B稱為(LP)問題的的一個基?；?/p>

由基矩陣B確定的m個基變量，并上非基變量取0的解?；?本)可行解

同時(shí)是可行解的基解?？尚谢?頁/共74頁112023/1/17利用初等變換求基可行解例4.教材14頁，列出(LP)問題的全部基，基解、基可行解并指出最優(yōu)解。問題:I)如何判斷一個解是基可行解；

II）表1-1中為何少了兩行？利用p1,p2,p4

求基解的過程第10頁/共74頁122023/1/17§2圖解法求最優(yōu)解什么時(shí)候用圖解法？

(LP)模型僅含兩個決策變量。

求解方法和根據(jù)：根據(jù)約束畫出求解區(qū)域，一般為第一象限的凸多邊形

(有界或無界)，標(biāo)記出頂點(diǎn)坐標(biāo)；求目標(biāo)函數(shù)的梯度：設(shè)目標(biāo)函數(shù)是z=c1x1+c2x2，則

n=gradz=(c1,c2)

為等值線c1x1+c2x2=h的法線方向，沿n的方向函數(shù)值增加的最快，沿-n方向函數(shù)值減少的最快。移動等值線c1x1+c2x2=h在區(qū)域頂點(diǎn)或邊界達(dá)到最大最小值。

書中的方法是把目標(biāo)函數(shù)z當(dāng)做參數(shù)處理。第11頁/共74頁132023/1/17一般情況求解區(qū)域的確定約束一般都可化成ax1+bx2+c=0(a>0，b0)的形式[特殊情形？]第12頁/共74頁142023/1/17一個用圖解法求極值的例子用圖解法求如下線性規(guī)劃問題的極值。最大值點(diǎn)x*=(1,4),Zmax=3；最小值點(diǎn)x*=(4,1),Zmin=3；A(2,0)B(4,1)C(1,4)D(0,2)第13頁/共74頁152023/1/17圖解法的其他情形–無窮多最優(yōu)解無窮多最優(yōu)解(書，P16，見下圖)

問題1：什么情況下發(fā)生？問題2：這個最優(yōu)解如何表示？第14頁/共74頁162023/1/17圖解法的其他情形–無界解(無最優(yōu)解)求下面規(guī)劃問題的最優(yōu)解。

問題1：如果目標(biāo)函數(shù)是求極大，是否有最優(yōu)解？問題2：能否定量說明z是無下界的？第15頁/共74頁172023/1/17圖解法的其他情形–無可行解求下面規(guī)劃問題的最優(yōu)解。第16頁/共74頁182023/1/17§3單純形基本原理–預(yù)備知識凸集定義1.1：如果集合C中任意兩點(diǎn)x(1)，x(2)，其連線上的所有點(diǎn)也在集合C中，即對任何x(1)C，x(2)C，0<<1，都有

x(1)+(1)x(2)C，則稱C為凸集。

頂點(diǎn)定義1.2：如果凸集C中不存在任何兩個不同的點(diǎn)x(1)、x(2)

，使x成為x(1)和x(2)連線上的某個點(diǎn)，這樣的x稱為C的頂點(diǎn)。

（問題：書上的數(shù)學(xué)描述是否妥當(dāng)？）第17頁/共74頁192023/1/17單純形法的基本定理定理1.1

若(LP)問題有可行解，則問題的可行域?yàn)橥辜?/p>

利用凸集的定義，結(jié)合LP的矩陣形式[P8]證明。引理1.1(LP)問題可行解x為基可行解的充要條件是x的非零分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。

利用基可行解的定義證明。定理1.2(LP)問題的可行解x是可行域(凸集)頂點(diǎn)的充要條件是x為一個基可行解。

利用分塊矩陣的形式，結(jié)合引理1.1利用反證法

(較長,最后證)。第18頁/共74頁202023/1/17引理1.1的證明引理1.1(LP)問題可行解x為基可行解的充要條件是x的非零分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。證明：充分性設(shè)x為一可行解，不妨設(shè)其非零分量(正分量)為前k個，即x=(x1,

x2

,

,

xk,

0,,0)T，xi>0(1

ik),若x是基可行解，則必有km(為什么？)，由可行基的定義，部分向量組p1,p2,,pk必線性無關(guān)。

必要性若x為可行解(同上假設(shè))，其對應(yīng)系數(shù)列向量p1,p2,,pk線性獨(dú)立(無關(guān))，同樣km(為什么？)。

(1)、若k=m,則p1,p2,,pk剛好構(gòu)成一個基矩陣，而x=(x1,

x2

,

,

xk,

0,,0)T為對應(yīng)基可行解。

(2)、若k<

m

，則可以利用p1,p2,,pk構(gòu)造一個基，因?yàn)閞ank(A)=m,從pk+1,p2,,pn中必可以選出mk列，和p1,p2,,pk共同組成一個基，這樣一定可以辦到(為什么？)

，其對應(yīng)基解恰為x。這樣的x稱為退化的基可行解。第19頁/共74頁212023/1/17單純形法的基本定理–凸組合性質(zhì)凸組合定義1.3設(shè)x(1),x(2),,

x(m)是En中的m個向量，而1,2,,

m是滿足1+2++

m=1，i0的m個實(shí)數(shù)，稱向量x=

1x(1)+2x(2)

++

mx(m)為x(1),x(2),,

x(m)的凸組合。 問題：凸組合和普通線性組合有什么區(qū)別？引理1.2

En中的點(diǎn)集為凸集的充要條件是對任何正整數(shù)m,中任意m個點(diǎn)x(1),x(2),,

x(m)的凸組合x都在內(nèi)。

充分性：利用定義證凸集；必要性：數(shù)學(xué)歸納法+凸集定義。第20頁/共74頁222023/1/17單純形法的基本定理-頂點(diǎn)表示定理引理1.3

設(shè)(LP)問題的可行域C有界，則任何可行解xC都可以表示成C的頂點(diǎn)的凸組合。

(證明略，圖解示意，考慮x的三種情況：頂點(diǎn)、邊界點(diǎn)和內(nèi)點(diǎn))第21頁/共74頁232023/1/17一個頂點(diǎn)表示的例子例設(shè)x是三角形中任意一點(diǎn)，x(1),x(2),x(3)是三角形的三個頂點(diǎn)，試將x表示為x(1),x(2)和x(3)的凸組合。解：連接x(1)和x交x(2)x(3)于x，因三角形是凸集,

x

=x(1)+(1)x(1)

x

=x(2)+(1)x(3)

(2)0<,<1

(2)代入(1)得：x

=x(1)+(1)x(2)+(1)(1)x(3)

，驗(yàn)證組合系數(shù)之和為1即可。第22頁/共74頁242023/1/17基可行解和最優(yōu)解的關(guān)系定理1.3

若(LP)問題有最優(yōu)解，則一定存在一個基可行解是最優(yōu)解。

定理的應(yīng)用：定理1.1(可行域是凸集)

定理1.2(凸集頂點(diǎn)對應(yīng)基的可行解)

定理1.3(某個基可行解是最優(yōu)解)

證明思路：設(shè)x*是最優(yōu)解，全部基可行解

x(1),x(2),,

x(m)，

希望最優(yōu)值在某個頂點(diǎn)x(k)達(dá)到，利用引理1.3建立x*和x(1),x(2),,

x(m)之間的關(guān)系，再利用最優(yōu)解性質(zhì)和不等式放縮證明即可。

問題：關(guān)于書上的證明?第23頁/共74頁252023/1/17§4單純形法迭代求解的基本思想第24頁/共74頁262023/1/17迭代法求解(續(xù)1)上述操作的實(shí)質(zhì)是消元法主元素的選取，進(jìn)基和離基。第25頁/共74頁272023/1/17迭代法求解(續(xù)2)問題：那個變量離基？第26頁/共74頁282023/1/17迭代法求解(續(xù)3)迭代法小結(jié)：先求得一個初始基可行解，一般要獲得一個單位陣基；判斷獲得的解是否是最優(yōu)解，如判斷目標(biāo)函數(shù)中非基變量的系數(shù)；如果不是最優(yōu)解，按照消元法進(jìn)行基可行解的轉(zhuǎn)換；重復(fù)和，直至求得最優(yōu)解。第27頁/共74頁292023/1/17第1次作業(yè)總結(jié)首頁寫清專業(yè)+姓名+學(xué)號

（單頁、草紙、背面?。┳鳂I(yè)版本拷貝！基本概念不清晰

最優(yōu)解和最優(yōu)值。

如作業(yè)1.2（a）中，最優(yōu)解

為x(1)=(0,3,0,0,7/2,0)T,

和x(2)=(0,0,3/2,0,8,0)T,

最優(yōu)值為z*=3。問題：參考圖解法的(a)，利用x(1)和x(2)給出一個新最優(yōu)解？第28頁/共74頁302023/1/17一個求解所有基解的matlab程序(作業(yè)1.2)%BFSBase’sFeasiblesolutionbyyaomingchen,2011.03.12c=[312];%目標(biāo)函數(shù)系數(shù)A=[1236300;81-4020;30000-1];%約束矩陣b=[9100]';%右端項(xiàng)[mn]=size(A);%矩陣規(guī)模MaxNumofBase=nchoosek(n,m);%最大的基數(shù)量comb=combntns(1:n,m);%具體的列組合fori=1:MaxNumofBase%對每個可能的基

x=zeros(1,n);%解分量全賦0值

ploc=comb(i,:);%基列的位置

B=A(:,ploc);%取出A的作為基的各列

ifrank(B)>m-1%如果r(B)=3Base=[];forj=1:m%將B表示成（p1p2...pk）的形式

Base=[Base,blanks(10),'p',int2str(ploc(j))];enddisp([‘BASE=’,Base]);%顯示基是哪些列構(gòu)成的

x(ploc)=B\b%求x_B并放入基列位置

zvalue=c*x(1:m)'%計(jì)算最優(yōu)值

endend第29頁/共74頁312023/1/17初始基可行解的獲得設(shè)法構(gòu)造一個初始單位陣基。如果約束條件都是“”形式，化標(biāo)準(zhǔn)型直接獲得；如果約束條件是“=”或“”形式，采用人工變量法(稍后講)。不妨設(shè)(LP)標(biāo)準(zhǔn)形前m列是單位陣，即典型形式(典式)。第30頁/共74頁322023/1/17最優(yōu)解的判別-檢驗(yàn)數(shù)最優(yōu)解的判別：用非基變量表示目標(biāo)函數(shù)值。第31頁/共74頁332023/1/17單純形表的建立cjc1c2cmcm+1cjcnCBBbx1x2xmxm+1xjxnc1x1b11a1m+1a1ja1nc2x2b21a2m+1a2ja2ncmxmbm1amm+1amjamnj=cj-zj000B–基(變量)；CB-

基變量對應(yīng)目標(biāo)函數(shù)系數(shù)；b–右端項(xiàng)

檢驗(yàn)數(shù)的計(jì)算：j=cj

zj=cj(c1a1j+c2a2j+…+cmamj)第32頁/共74頁342023/1/17用單純形表求解的例子(書p26.例5)cj23000CBBbx1x2x3x4x50x312221000x416400100x51505001j=cjzj23000化標(biāo)準(zhǔn)型建立初始單純形表，計(jì)算檢驗(yàn)數(shù)；確定進(jìn)基變量，x2進(jìn)基

(檢驗(yàn)數(shù)最大);確定離基變量，=min{12/2,16/0,15/5}

=3，x5離基。

由主元a32確定。第33頁/共74頁352023/1/17單純形表上的迭代算法cj23000CBBbx1x2x3x4x50x312221000x416400100x51505001j=cjzj2300001001/533x22010-2/562000-3/5所有檢驗(yàn)數(shù)非正，最優(yōu)解x*=(3,3,0,4,0)T，最優(yōu)值z*=15第1次迭代：對主元所在行和列進(jìn)行初等變換，并計(jì)算檢驗(yàn)數(shù)。第2次迭代：x1進(jìn)基，x3離基，主元a12=2，消元并計(jì)算檢驗(yàn)數(shù)。2x13101/20-1/50x43x2400-214/5301001/5j=cjzj00-10-1/5第34頁/共74頁362023/1/17單純形算法的一般形式cjc1clcmckcjCBBbx1xlxmxkxjc1x1b11a1ka1jcixibiaikaijclxlbl1alkaljcmxmbm1amkamjj=cj-zj000kj第35頁/共74頁372023/1/17單純形算法的計(jì)算步驟把(LP)化成標(biāo)準(zhǔn)形式，建立初始單純形表；

（一般能獲得一個單位陣基作為初始可行基）計(jì)算所有變量的檢驗(yàn)數(shù)，若所有j0(1jn)，則當(dāng)前解x即為最優(yōu)解，迭代結(jié)束。否則轉(zhuǎn);確定k=max{j|j>0},則xk待進(jìn)基；若所有aik0,則停止計(jì)算，(LP)無最優(yōu)解，否則轉(zhuǎn)；計(jì)算=min{bi/aik|aik>0,1im}=bl/alk,則xl離基；以alk為主元,通過高斯消元法進(jìn)行基可行解的轉(zhuǎn)換，求得表中一新基可行解，轉(zhuǎn)步驟。

(注：若在和中出現(xiàn)多個k或者l,則按照自然順序選擇)第36頁/共74頁382023/1/17迭代一次之后的形式cjc1clcmckcjCBBbx1xlxmxkxjc1x110cixi0ckxk1cmxm10j=cj-zj000第37頁/共74頁392023/1/17迭代前后解,函數(shù)值,檢驗(yàn)數(shù)等的變化第38頁/共74頁402023/1/17一個講練的例子(大家參與)第39頁/共74頁412023/1/17最優(yōu)性檢驗(yàn)標(biāo)準(zhǔn)(※)若所有j<0(m+1jn),則x(k)為(LP)唯一的最優(yōu)解。設(shè)x(k)是最優(yōu)解，有某個r=0(m+1rn),且存在air>0(1im),則

(LP)有無窮多最優(yōu)解。若有某個j>0(m+1jn),但是

pj=(a1j,a2j,…,amj)0,則(LP)無有限的最優(yōu)解和最優(yōu)值（無最優(yōu)解）。采用人工變量方法時(shí)(大M法和二階段法)，滿足最優(yōu)條件時(shí)人工變量不為零，則原LP問題無可行解。第40頁/共74頁422023/1/17§5人工變量法–問題的提出如果原（LP）問題的約束全是“”號的形式，可以引入m個松弛變量xn+m，使得后m列自然形成初始單位陣基，再用單純形法進(jìn)行迭代求解。如果原（LP）問題的約束是“”和“”號，或者三種符號（、、）都有的的混合形式，且化成標(biāo)準(zhǔn)形式后約束矩陣不具備初始單位陣基，這時(shí)候怎么辦？解決辦法：自然的想法就是在標(biāo)準(zhǔn)形約束矩陣中，人工加入若干單位向量，(和已有的)形成初始單位陣基?；瘶?biāo)準(zhǔn)型第41頁/共74頁432023/1/17人工變量法–大M法例6求解如下線性規(guī)劃問題(書P29)標(biāo)準(zhǔn)形中只有p4是單位向量？強(qiáng)行加入兩列p6和p7

，或者說在第2、3個約束上分別加入人工變量，即x6和x7。人工變量的系數(shù)問題？目標(biāo)函數(shù)中人工變量系數(shù)都取M(M>0充分大)。第42頁/共74頁442023/1/17用大M法求解例6cj-30100-M-MCBBbx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cjzj-2M-34M10-M00檢驗(yàn)數(shù)比較：

形式aM+b1.a>0,aM+b>02.a<0,aM+b<03.若0<a1<a2

則a1M+b1<a2M+b2

此時(shí)可省略常數(shù)b1-21-10-110cjzj0x20x4-M

x7330211-10660403-316M04M03M-4M0第43頁/共74頁452023/1/17用大M法求解例6（續(xù)）cj-30100-M-MCBBbx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x11102/301/2-1/21/6cjzj00303/2-M-M0x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cjzj-9/2000-3/4-M-M

x*=(0,5/2,3/2,0,0,0,0)T,z*=3/2.第44頁/共74頁462023/1/17大M法的理論分析對標(biāo)準(zhǔn)形式的(LP)問題，設(shè)約束矩陣無單位陣基，令

xk=(xn+1,xn+2,…,xn+k)T,(k

m),則大M法是求解：第45頁/共74頁472023/1/17大M法的理論分析第46頁/共74頁482023/1/17一個無可行解的例子(P18,P42)cj2-100-MCBBbx1x2x3x4x50x3111100-Mx54-130-11cjzj-M3M0-M0單純形表的迭代過程：-1x2111100-Mx51-40-3-11cjzj-4M0-3M-M0

人工變量x5=10,由定理5.1,原問題無可行解。第47頁/共74頁492023/1/17人工變量法–兩階段方法大M方法的缺點(diǎn)：帶有非數(shù)值符號M，不方便計(jì)算。什么是兩階段方法？

和大M方法一樣，同樣引入人工變量xT=(xn+1,xn+2,…,xn+k)T,(k

m)，并設(shè)e=(1,1,…,1)

,構(gòu)造一新的線性規(guī)劃問題（TP，Two-PhaseProgramming）兩階段方法的計(jì)算步驟：引入人工變量并構(gòu)造新的(TP)問題：目標(biāo)函數(shù)中原決策變量系數(shù)全取0，人工變量系數(shù)皆取1，且目標(biāo)函數(shù)求極小)；

第一階段，求(TP)問題的最優(yōu)解(一般xT=0),同時(shí)得到原(LP)問題的基可行解(未必最優(yōu))；

第二階段，刪除(TP)最終單純表中人工變量列，利用第一階段的得到的基可行解，以及原(LP)的目標(biāo)函數(shù)繼續(xù)迭代求解。第48頁/共74頁502023/1/17兩階段方法求解的例子(習(xí)題1.1a)約束化等式構(gòu)造TP問題第49頁/共74頁512023/1/17第一階段:求解TP問題cj000011CBBbx1x2x3x4x5x61x5646-10101x64420-101cjzj-8-811001x5204-111-10x1111/20-1/401/4cjzj0-41-1020x21/201-1/41/41/4-1/40x13/4101/8-3/8-1/83/8cjzj000011x*=(3/4,1/2,0,0,0,0)T2300

第50頁/共74頁522023/1/17第二階段：求原LP問題因?yàn)閏4z4=3/2>0

但p4=(-1/2,-3)<0

故原LP無最優(yōu)解。

本幻燈片42頁。cj2300CBBbx1x2x3x43x21/201-1/41/42x13/4101/8-3/8cjzj001/203x22210-1/20x36801-3cjzj-4003/2第51頁/共74頁532023/1/17原問題如果是求極小(無窮多最優(yōu)解)因?yàn)榍髽O小，所有檢驗(yàn)數(shù)非負(fù)停止迭代；繼續(xù)迭代可得到另外一個最優(yōu)解。cj2300CBBbx1x2x3x43x21/201-1/41/42x13/4101/8-3/8cjzj001/200x4204-112x13/213/2-1/40cjzj001/20第52頁/共74頁542023/1/17兩階段方法的理論分析（情況1）首先若(LP)有可行解，(TP)問題一定有最優(yōu)解？ 這是因?yàn)閑=(1,...,1)T,對任意xT0,y=exT0有下界。 如xT=0

就是(TP)的一個最優(yōu)解，但這個最優(yōu)解未必能達(dá)到。第53頁/共74頁552023/1/17兩階段方法的理論分析（情況2）第54頁/共74頁562023/1/17情況2的例子cj000011CBBbx1x2x3x4x5x60x42-1211001x54-44-10101x6010-1001cjzj3-42000第一階段的求解過程（注意求極?。?x21-1/211/21/2001x50-20-3-2101x6010-1001cjzj104200第55頁/共74頁572023/1/17情況2的例子(續(xù)1)cj-110000CBBbx1x2x3x4x5x61x21-1/211/21/2000x50-20-3-2101x6010-1001cjzj104200第一階段的結(jié)果沒有獲得單位陣基，開始第二階段：1x210x50-1x10cjzj00-5-2120101/201/2-1x1

00-1-1/201/2

x4

005/21-1/2-101-5/401/4110-1001001/40--第56頁/共74頁582023/1/17情況2的例子(續(xù)2)cj-110000CBBbx1x2x3x4x5x61x2101-5/401/410x40005/21-1/2-1-1x1010-1001cjzj001/40--拋棄人工變量，繼續(xù)迭代：1x210101/20x300012/5-1x101002/5cjzj000-1/10x*=(0,1,0)T,z*=1.第57頁/共74頁592023/1/17兩階段方法的理論分析（情況3）第58頁/共74頁602023/1/17一個無可行解的例子(本幻燈片P49,和大M法關(guān)系)cj00001CBBbx1x2x3x4x50x31111001x54-130-11cjzj1-3010第一階段的迭代過程：0x21111001x51-40-3-11cjzj40310

人工變量x5=10,由情況3,原問題無可行解。第59頁/共74頁612023/1/17§6單純形法的矩陣形式(※)例6.1

單純形表迭代變化的實(shí)質(zhì)（本幻燈片P44-46）cj-30100-M-MCBBbx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cjzj-2M-34M10-M000x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/41/4cjzj-9/2000-3/4-M-M問題：B1對應(yīng)最終單純形表那些列，原來那些列是什么？第60頁/共74頁622023/1/17矩陣形式的單純形表目標(biāo)函數(shù)值：

z=cBB1b非基變量檢驗(yàn)數(shù)：

N=cN

cBB1N基變量檢驗(yàn)數(shù)：

B=cB

cB=0記號：y=cBB1稱為單純形乘子。ccBcNBxBxNbcBxB檢驗(yàn)數(shù)I=B1BB1NB1bB=0N=cNcBB1NcBB1b第61頁/共74頁632023/1/17例10.確定B1,單純形乘子y和計(jì)算檢驗(yàn)數(shù)（用矩陣形式）確定B=?

B1=?求B1b=?計(jì)算迭代后的p1和p3確定單純形乘子y=cBB1計(jì)算x3和x5的檢驗(yàn)數(shù)計(jì)算目標(biāo)函數(shù)值cj203000CBBbx1x4x2x3x4x50x3122021000x4164100100x515005001j=cjzj2030002x131001/20-1/50x44010-214/53x23001001/5j=cjzj000-10-1/5第62頁/共74頁642023/1/17例11.確定單純形表中的未知量（大家參與）如下表，給出了某線性規(guī)劃問題計(jì)算過程中的一個單純形表，目標(biāo)函數(shù)為maxz=28x4+x5+2x6,約束條件全為“”，表中x1,x2,x3為松弛變量，表中解的目標(biāo)函數(shù)值為

z=14。

（1）.求

a~g

的值；

（2）.求原約束矩陣的第五列p5。CBBbx1x2x3x4x5x62x6a30-14/30110x256d205/2028x400ef100cjzjbc00-1g第63頁/共74頁652023/1/17修正單純形算法為什么要引入修正單純形算法？單純形表每次迭代過程有m1列未發(fā)生變化[參見下2頁]；單純形表操作不適合大規(guī)模的LP問題計(jì)算。迭代前后兩個表中的基B和新基B的關(guān)系問題1.迭代前的基B是什么，B1是什么？問題2.迭代后的新基B是什么？B1如何計(jì)算？兩個基的逆之間的關(guān)系：(Bnew)1=(Blk)

1=ElkI=ElkB

1推導(dǎo)兩個逆矩陣之間的關(guān)系式用原基的逆表示新基表中其他量皆可以用B

1表示第64頁/共74頁662023/1/17迭代之前cjc1clcmckcjCBBbx1xlxmxkxjc1x1b11a1ka1jcixibiaikaijclxlbl1alkaljcmxmbm1amkamjj=cj-zj000kj第65頁/共74頁672023/1/17迭代之后cjc1clcmckcjCBBbx1xlxmxkxjc1x110cixi0ckxk1cmxm10j=cj-zj000第66頁/共74頁682023/1/17修正單純形算法的計(jì)算步驟對標(biāo)準(zhǔn)形式的LP問題，寫出矩陣A,b

和c;

確定初始單位陣基B(=I),記錄基向量下標(biāo)集合I、非基變量集合J和cB；計(jì)算xB=B1b.計(jì)算單純形乘子y=cBB1,并計(jì)算檢驗(yàn)數(shù)N=cN

yN

，若所有j0(m+1jn)，則當(dāng)前解x即為最優(yōu)解，迭代結(jié)束。否則轉(zhuǎn);計(jì)算k=max{j|j>0},確定k,并計(jì)算pk=B1pk；若所有aik0,則停止計(jì)算，(LP)無最優(yōu)解，否則轉(zhuǎn)；計(jì)算=min{bi/aik|aik>0,1im}=bl/alk,

修改集合I,J和cB；形成Elk,并計(jì)算B1=ElkB

1,xB=Elk