運(yùn)籌學(xué)第二章線性規(guī)劃

第二章線性規(guī)劃教學(xué)目的和要求：目的：使學(xué)生具備線性規(guī)劃的基本知識以及應(yīng)用線性規(guī)劃的基本能力。要求：理解線性規(guī)劃概念，標(biāo)準(zhǔn)型，解的概念，基本定理；掌握單純形法，人工變量法，了解圖解法。重點(diǎn)：線性規(guī)劃標(biāo)準(zhǔn)型，解的概念，單純形法，人工變量法。難點(diǎn)：線性規(guī)劃基本定理，單純形法。教學(xué)方法：講授法，習(xí)題法。學(xué)時(shí)分配：12學(xué)時(shí)作業(yè)安排：見教材P*解：設(shè)產(chǎn)品A、解：設(shè)產(chǎn)品A、B、C產(chǎn)量分別為X,X,X件,Z表示利潤，要求總利潤最大，即求Z=4.5X+5X+7X32另外對甲、乙、丙、丁設(shè)備需滿足2X1+2X2+4X3^8002，3滿足線性規(guī)劃是運(yùn)籌學(xué)的一個重要分支。1939年蘇聯(lián)科學(xué)家康托羅維奇提出了生產(chǎn)組織和計(jì)劃中的線性規(guī)劃模型。1947年美國學(xué)者丹捷格(GeorgeB.Dantzig)提出了求解一般線性規(guī)劃問題的方法。此后，線性規(guī)劃理論日趨成熟，應(yīng)用也日益廣泛和深入。第一節(jié)線性規(guī)劃問題一、問題的提出在企業(yè)的生產(chǎn)經(jīng)營活動中經(jīng)常會面臨這樣兩類問題：一是如何合理地利用有限的人力、物力、財(cái)力等資源，取得最佳的經(jīng)濟(jì)效果；二是在取得一定的經(jīng)濟(jì)效果的前提下，如何合理安排使用人力、物力、財(cái)力等資源，使花費(fèi)的成本最低。例1.生產(chǎn)計(jì)劃問題某工廠利用甲、乙、丙、丁四種設(shè)備生產(chǎn)A、B、C三種產(chǎn)品，具體數(shù)據(jù)如下表所示。A、B、C單位產(chǎn)品的利潤分別是4.5、5、7(百元)。問如何安排生產(chǎn)計(jì)劃，才能使所獲總利潤最大？產(chǎn)品設(shè)備、\^ABC設(shè)備可供工時(shí)(h)甲224800乙123650丙423850丁242700單位利潤4.557銷地產(chǎn)地B1B2???Bn產(chǎn)量A1C11C12???C1na1A2C21C22???C2na2??????????????????AmCm1Cm2???Cmnam銷量b1b2???bnmn￡a.=￡bi=11i=1j解：設(shè)Xjj（i=1,2,...,m;j=1,2,...,n）表示由土到B.的物資運(yùn)輸量，則總運(yùn)費(fèi)為mn，另外，對Z=￡￡C..X..i=1jmn，另外，對Z=￡￡C..X..i=1j=1ijijA應(yīng)有n，i=1,2,...,m對B，應(yīng)有

i￡xij=aij同時(shí)，運(yùn)輸量應(yīng)非負(fù)，故X可，以上問題數(shù)學(xué)模型為：極小化(i=1,2,...,m;j=1,2,...,n)滿足mnz=￡￡C..X..滿足i=1j=1ijijn，i=1,2,...,m￡x..=a.j=1ijim,j=1,2,...,n￡x..=b.i=1ijj七Xij可（i=1,2,...,m;j=1,2,...,n）例3.配料問題要配制一種面包，每只面包要求含甲、乙、丙3種營養(yǎng)成分至少各為20、24、30單位?，F(xiàn)有4種原料可供選用，下表給出了每10g原料所含各種營養(yǎng)成分的單位數(shù)。試確定每種原料各取多少，才能使面包的配制成本最低？原料營養(yǎng)種ABCD甲121/21/4乙3121/2丙3124價(jià)格（分/10g）10153025解：先假設(shè)配制一只面包，數(shù)量多只需擴(kuò)大相應(yīng)倍數(shù)即可。由觀察可知，原料上還是價(jià)格上都優(yōu)于C，故C不選用，設(shè)A、B、D各取X,^,^個10g。則可得數(shù)學(xué)模型如下：極小化Z=10X+15X+25X滿足12rx+2Xrx+2X+(1/4)X沱203X1+X2+(1/2)X4沱243X1+X2+4X4沱30匚X,,X,,X卷以上幾個問題各有不同，但其數(shù)學(xué)模型有共同之處：它們都是要求一組變量（稱為決策變量）X,X，…，X，這組變量全部或者其中一部分具有非負(fù)要求，且滿足一系列線性等式或不等式n12,i=1,2,n...,m,使一個用線性式表示的目標(biāo)（稱為目標(biāo)函￡aijXj=（-，-）%數(shù))Z=C1X1+C2X2+???+CnXn達(dá)到極值，這類問題稱為線性規(guī)劃。一般而言，線性規(guī)劃數(shù)學(xué)模型為：極大化(極小化)Z=CX+CX+???+CX…一般而言，線性規(guī)劃數(shù)學(xué)模型為：極大化(極小化)Z=CX+CX+???+CX…n,i=1,2,2...,m..^(②1a.x.(,)b.j1ijJ1X>0全部或部分j,j=1,2,…,n???…①式為目標(biāo)函數(shù)，②為約束條件，③為非負(fù)要求；式①②全為線性式，否則稱為非線性規(guī)劃。滿足②③的一組變量X1，X2,…，X」稱為線性規(guī)劃的可行解，由所有可行解組成的集合稱為可行解集合或可行域，若X=(X1，X：…，X)丁使目標(biāo)函數(shù)達(dá)到極值的可行解，稱為最優(yōu)解。為了表述方便及深入研究線性規(guī)劃，線性規(guī)劃底型可表三為矩陣和向量形式：極大化(極小化)Z=CX,滿足AX=(wW)b,X>0;滿足PX+PX+???+PXCn)，X=(X1???a1n?a2n或極大化(極小化)Z=CX其中C=(C1，C2，a11a21A=a12a22=(Pi，22nnX2,…，Xn)TP2,…，Pn)M習(xí)b,b=(b,b,X#???,DT，P=(a,a,???a)Tj=1,2,…，nmj1j2jmj第二節(jié)線性規(guī)劃的圖解法線性規(guī)劃的圖解法是一種解析幾何方法，它簡單直觀，有助于理解其基本概念和求解一般原理。例4.求解線性規(guī)劃極大化Z=600X1+700X2滿足］X1+2X2M60X1+X2M2043X1+X2<300X2<60'X1，X2>0解：(1在平面上建立直角坐標(biāo)系O-X1X2,X1為橫軸，X2為縱軸。(2戕出可行域，由解析幾何知識可知，X1+2X2M60代表直線X1+2X2=160左下半平面，X1+X2^20代表直線X1+X2=120左下半平面,3X1+X2<300代表直線3X1+X2=300左下半平面，X2三60代表直線X2=60下半平面，X1>0,X2>0表示第一象限，以上區(qū)域的公共部分D即為可行域。(3)在可行域中找最優(yōu)解，將Z視為參數(shù)，則Z=600X1+700X2可表示為以Z為參數(shù)的一族平行線，X2=(-600/700)X+(Z/700)其中同一條直線上任何一點(diǎn)都具有相同的Z值，故稱之為等值線。當(dāng)Z值由小變大時(shí)，等值線沿其法線方向垂直方向)向右上方移動，當(dāng)移動到過X*點(diǎn)時(shí)，Z值最大，因?yàn)槿鬦值再增大，則等值線與可行域無交點(diǎn)，不滿足約束條件。初始等值線可選擇一個適宜的Z值，與可行域相交即可，比如Z=42000,故本例最優(yōu)解為X*=(80,40t,最優(yōu)值為Z*=76000例5:用圖解法求解下列線性規(guī)劃例5:用圖解法求解下列線性規(guī)劃(1極大化Z=2X/A滿足［X1-X2>1J-X+孜<0〔X…（2）極小化Z=2X1+2X2滿足X-X沱1<-X+12X司,x1,X2^0解：這兩個問題約束條件相同，其可行域如圖2-3所示，是個無界集，從圖2-3中可看出無論Z多大，Z=2%+2X2總與D相交，故Z可無限增大，則（1）無最優(yōu)解但有可行解，當(dāng)Z減少時(shí)目標(biāo)函數(shù)等值線過X*例6：求解線性規(guī)劃極大化Z=X+X2滿足]X+X11?x+x2wx1，X2g解:如圖2-4所示，可行域?yàn)榭占什淮嬖诳尚薪庖矡o最優(yōu)解。例7：在例4中將目標(biāo)函數(shù)改為極大化Z=600X1+600X2其它不變，則極大化Z=600X1+600X2與X]+X2=120平衡,Z由0變大時(shí)，等值線最后將與可行域D的邊X*X（3）（X1+X2=120所形成的邊）重合,故線段X*X⑶上的每一點(diǎn)都是最優(yōu)解，（圖2-5）綜上可知，兩個變量的線性規(guī)劃有以下特點(diǎn)：1）可行域可能是空集，也可能是有界凸多邊形，或無界凸區(qū)域；2）當(dāng)D非空時(shí)，D至少有一個極點(diǎn)（頂點(diǎn)）；3）當(dāng)D非空有界時(shí)，線性規(guī)劃一定有最優(yōu)解，且最優(yōu)解必在D的一個極點(diǎn)上得到；4）當(dāng)線性規(guī)劃的最優(yōu)解不唯一時(shí)，那么必有無窮多個最優(yōu)解；5）如果D無界，則線性規(guī)劃可能無最優(yōu)解（例5（1））也可能有最優(yōu)解（例5（2））.以上結(jié)論對于nW也成立，下節(jié)將論證。第三節(jié)線性規(guī)劃的標(biāo)準(zhǔn)型和解線性規(guī)劃的圖解法雖直觀簡便，但對于n^2時(shí)就無能為力。下面介紹一種代數(shù)方法一單純形法，為了以后便于討論，先研究一下線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)型和解的基本性質(zhì)。對于一個具體的線性規(guī)劃應(yīng)先化為標(biāo)準(zhǔn)型再用單純形法求解。一、線性規(guī)劃的標(biāo)準(zhǔn)型規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)型為：

極大化Z=CX+CX+...+CX(2-10)1122nn滿足(aX+aX+...+aX=b1111221nn1aX+aX+.+aX=b2112222nn2aX+aX+.+aX=b(2-11)m11m22mnnm〔X可j=1,2,...,n(2-12)矩陣形式:MaxZ=CX,滿足AX=b,X^0.向量形式:MinZ=CX，滿足P1X1+P2X2+.+PnXn=b,X可二、化標(biāo)準(zhǔn)型若目標(biāo)函數(shù)為“MinZ=CX”，因?yàn)镸inZ=-Max(-Z),令z'=-Z=(-C)X，則目標(biāo)函數(shù)變?yōu)镸axz'=(-C)X,Z'值的相反數(shù)就是所求目標(biāo)函數(shù)值。若有b<0(1目盆)則將此約束條件兩邊同乘(-1),便得(-b)>0。若第ki個約束條件為aX+aX+...+aX斗則在左端加入一個非負(fù)松馳變量X,k11k22knnkn+k使之成為aX+aX+...+aX+X=bk11k22knnn+kk若第s個約束條件為aX+aX+...+aX斗則在左端減去一個非負(fù)剩余變量X,s11s22snnsn+s使之成為aX+aX+...+aX-X=bs11s22snnn+ss若決策變量X司，則用X'=-X代入目標(biāo)函數(shù)和約束條件中，則X'^0,jjjj若決策變量X無非負(fù)要求，則令x=x'-x〃,x',x"Z0ssssss代入線性規(guī)劃模型中，則變量都有了非負(fù)要求。例8.將線性規(guī)劃化為標(biāo)準(zhǔn)型MinZ=5X-2X+3X-6X(X+2X+3x+4女M18412342X+X+X+2X沱103X1-X-32X+X=-6X],1X；X4%,4X3無非負(fù)要求.解:1)令Z'=-Z=-5X1+2X2-3X3+6X4使目標(biāo)函數(shù)成為MaxZ=-5X1+2X2-3X3+6X4第一個約束條件左端加入松馳變量X5；3)第二個約束條件左端減去剩余變量X64)第三個約束條件兩邊同乘(-1)；4)第三個約束條件兩邊同乘(-1)；5)令x=x:—x:":,x；Z033333則線性規(guī)劃的標(biāo)準(zhǔn)型為：MaxZ'=-5X1+2X2-3X3'+3X3''+6X4+0X5+0X6{Xi+2X2+3X3‘-3X3''+4X4+X52X1+X2+X3'-X3''+2X4-3X1+X2+2X3'-2X3''-X4X1，X2,X3',X3'',X4,X5,三、線性規(guī)劃解的基本概念=18-X6=10=6X6可,111211121maa......a21222maa......am1m2mB=(P1，P2,……Pm)=線性規(guī)劃標(biāo)準(zhǔn)型即式(2-10)---(2-12)形式，且m<n,R(A)=m.基本解求解線性規(guī)劃，實(shí)質(zhì)上是求解具有特殊要求(變量非負(fù)及目標(biāo)函數(shù)值達(dá)到極大)的線性方程組，因?yàn)閙<n,R(A)=m.故約束方程組有無窮多解。設(shè)B是A中一個非奇異的m階子陣(即|B怙0)則稱B是線性規(guī)劃的一個基。不妨設(shè)B是由A的前m個向量組成，即P1,P2,Pm線性無關(guān)，稱Pj(j=1,2,m)為基向量，與基向量Pj相應(yīng)的變量Xj稱為基變量，其它的向量和變量稱為非基向量和非基變量。將約束方程組表示為ai1X1+ai2X2+.+a2mXm=bi-aim+1Xm+1-.-ainXn,i=1,2,...m.

令非基變量Xm+1=???=Xn=0.則由P]Xi+P2X2+...+PmXm=b得唯一一組解X.=b.,i=1,2,…，mii因此X=(b,b，…,b,0,0,...,0)T為約束方程組的一個解,X稱為對應(yīng)基B的基本解。在基本解X中,非零分量最多為m個，線性規(guī)劃的每個基都對應(yīng)一個基本解,A的非奇異的令非基變量Xm+1=???=Xn=0.則由P]Xi+P2X2+...+PmXm=b得唯一一組解n!Cm=個nm!(n-m)!基可彳丁解滿足非負(fù)要求的基本解，即屬于可行域中的基本解，稱為線性規(guī)劃的基可行解，基本可行解最多有Cm個。n設(shè)B=(Pi,P2,Pm)是一個基，A=(BN),X=(XbXn)T,N=(Pm+1,Pm+2，.Pm),Xn=(Xm+1,Xm+2,-Xm)T,Xb=(X],X2,.Xm)T，則(2-11)式可化為AX=(BN)(XbXn)T=BXB+NXN=b，XB=B-1b-B-1NXN，令XN=0,貝0XB=B-1b，若XB^0，則X=(Xb，0)T=(B-1b，0)T是線性規(guī)劃(相應(yīng)于基B)的基可行解，B稱為可行基。最優(yōu)解:使目標(biāo)函數(shù)值Z達(dá)到極值的可行解稱為最優(yōu)解。四、線性規(guī)劃的基本定理它是從理論上深入論證解的基本性質(zhì)基本概念凸集：設(shè)S是n維歐氏空間En中的一個集合(即SuEn)若對VX⑴,X(2)孑及V實(shí)數(shù)入(0￡三1),都有入X(1)+(1-入)X(2)￡S,則S稱為凸集。凸組合：設(shè)X⑴，X⑵，...X(K)是En的K個點(diǎn)，實(shí)數(shù)入*,...入滿足入目,i=1,2,...,k.A1,則稱TOC\o"1-5"\h\z12kii(1)(2)(K)(1)(2)(K)(1)(2)(K)(1)(2)(K)人X十人X+..?十人X為X,X,...X的凸組合，若X=人X十人X+..?十人X則稱、X是X,X,...X的凸組合。2k12k⑶極點(diǎn)：對于凸集S,X￡S，若不存在這樣的兩個點(diǎn)X⑴,X(2)￡S,(X⑴以⑵,X(1)^X,X(2)^X)使X可以表示成X⑴和X(2)的凸組合，即X=X⑴+(1頃)X(2),0<X<1，則X是S的一個極點(diǎn)?；径ɡ矶ɡ?.線性規(guī)劃可行域D是凸集.推論.線性規(guī)劃最優(yōu)解集合是凸集.定理2.X是線性規(guī)劃的可行解，它是基可行解。X的非0分量對應(yīng)的系數(shù)列向量線性無關(guān).定理3.線性規(guī)劃的基可行解對應(yīng)可行域D的極點(diǎn)，即可行解X是基可行解。X是可行域D的極點(diǎn).定理4.若線性規(guī)劃有可行解，則一定有基可行解(即若線性規(guī)劃可行域非空，則D一定有極點(diǎn)).定理5.若線性規(guī)劃有最優(yōu)解，則一定有最優(yōu)基可行解.定理6.若線性規(guī)劃可行域D有界，則最優(yōu)解一定可以在D的極點(diǎn)上得到.推論：若線性規(guī)劃的最優(yōu)解可在D的兩個極點(diǎn)上得到，則線性規(guī)劃必有無窮多個最優(yōu)解.第四節(jié)單純形法一、概述單純形法是求解線性規(guī)劃的基本方法(代數(shù)方法),根據(jù)線性規(guī)劃的基本定理可知，若線性規(guī)劃有最優(yōu)解，一定可在基可行解中得到，單純形法的基本思想就是從一個基本可行解開始，通過更換基變量，轉(zhuǎn)換到另一個基可行解，同時(shí)使目標(biāo)函數(shù)的值逐步增大，當(dāng)目標(biāo)函數(shù)達(dá)到最大值時(shí)，問題就得到了最優(yōu)解。例10.求解線性規(guī)劃MaxZ=10X1+15X2+X3+3X4+2X5(2-20)滿足r-X1+2X2+X3=181X1+X2+X4=2...(2-21)X1+X5=15〔Xj可,j=1,2,3,4,5...(2-22)解：問題已是標(biāo)準(zhǔn)型[-1210018'1.確定初始基可行解(Ab)=[1101024]〔1000115JR(A)=3,m=3,n=5,B0=(P3，P4，P5)是A的一個基，相應(yīng)的基變量為X3，X4，X5，非基變量為X]，X2基向量為P3,P4,P5，非基向量為P1，P2.用非基變量表示基變量，約束條件(2-21)可變?yōu)椋篨3=18-(-X1)-2X2X4=24-Xi-X2(2-23)X5=15-Xi將(2-23)代入(2-20)得Z=120-(-6)X1-(-10)X2...(2-24)令X1=X2=0，則X(0)=(0,0,18,24,15)t為初始基可行解，對應(yīng)的目標(biāo)函數(shù)值為Z(0)=120.檢驗(yàn)由(2-24)Z=120-(-6)X1-(-10)X2可看出，若讓X］或X2變?yōu)榛兞?，即取值?變?yōu)檎龜?shù)，則Z將增大，故X(0)不是最優(yōu)解，Z(0)不是最優(yōu)值?；尚薪廪D(zhuǎn)換確定進(jìn)基變量：通過比較X1，X2的系數(shù)可知選X2為進(jìn)基變量，Z增加更快，稱其為進(jìn)基變量；確定出基變量：因?yàn)榛兞恐荒苡衜=3個，故須將原來的基變量換出一個為非基變量，稱其為出基變量，X1仍為非基變量，令X1=0，則(2-23)變?yōu)椋簗X3=18-2X2X4=24-X2(2-25)LX5=15為了使所有變量保持非負(fù)，則18-2X2^0,24-X2^0故可得X?M9，取X2=9使Z盡可能增大，此時(shí)X3=0即X3為出基變量，因此新基B1=(P2,P4,P5)，相應(yīng)的基變量為X2，X4,X5.基可行解轉(zhuǎn)換計(jì)算(迭代)由(2-23)得『X2=9-(-1/2)X1-(1/2)X3'X4=15-(3/2)X1+(1/2)X3......(2-26)'X5=15-X1以(2-26)代入(2-24)得Z=210-(-11)X1-5X3...(2-27)令X1=X3=0,則X(1)=(0,9,0,15,15)T,Z(1)=210.重復(fù)2-3步驟直至最優(yōu)解從(2-27)可看出將X1為進(jìn)基變量,Z將增大，令X3=0,則(2-26)變?yōu)椋軽2=9-(-1/2)X1X4=15-(3/2)X1X5=15-X1且9-(-1/2)X1^0,15-(3/2)X1^0,15-X1當(dāng))故可得X1三10,取X］=10，則X4=0,X4為出基變量，因此新基為B2=(P2,P1,P5),相應(yīng)的基變量為X2,X1,X5.由(2-26)得］X2=14-(1/3)X3-(1/3)X4，X1=10-(-1/3)X3-(2/3)X4...(2-28)LX5=5-(1/3)X3-(-2/3)X4將(2-28)代入(2-27)得Z=320-(4/3)X3-(22/3)X4...(2-29)令X3=X4=0,則X(2)=(10,14,0,0,5)T,Z⑵=320.從(2-29)可看出，此時(shí)X(2)為最優(yōu)解，即X*=X(2)，最優(yōu)值為Z*=Z⑵單純形法的主要步驟：找一個初始基可行解(要求標(biāo)準(zhǔn)型A中有R(A)=m階單位子陣)。檢驗(yàn)基可行解是否最優(yōu)(看Z能否增大)。若不是最優(yōu)解，進(jìn)行基可行解的更換，進(jìn)基變量應(yīng)使Z增加最快，出基變量選擇原則是保持所有變量要非負(fù)，進(jìn)行基可行解的轉(zhuǎn)換計(jì)算，這種計(jì)算稱為迭代。重復(fù)2)-3)直至最優(yōu)解。二、單純形法(針對一般線性規(guī)劃標(biāo)準(zhǔn)型)的求解步驟：初始基可行解的確定.為了確定初始基可行解，要先找出初始可行基，方法如下：(1)若從標(biāo)準(zhǔn)型中，可直接從A中找到m個線性無關(guān)的單位列向量，即m階單位矩陣，不妨設(shè)為B0=(P1,P2,Pm)，N0=(Pm+1，Pm+2,Pn)即得一可行基B0，即線性規(guī)劃標(biāo)準(zhǔn)型為：MaxZ=寸CX(2-30)jj'j=1X1+a1m+1m+amm+1Xm+1+???m+amm+1Xm+1+???+amnXn=bmX2+a2m+1Xm+1+???+a2nXn=b2???(2-31)

Xj尋j=1,2,.,n(2-32)bi可，(i=1,2,...,m)則初始基可行解為X(0)=(b1，b2,...bm，O...O)T,對應(yīng)的目標(biāo)函數(shù)值為Z0=CBXB+CNXN=CBb.(2)若從A中找不到m個線性無關(guān)的單位列向量，則采用人工變量法(見第五節(jié)).最優(yōu)性檢驗(yàn)得到初始基可行解后，要檢驗(yàn)一下是否是最優(yōu)解：如果是，則停止迭代(基變量的轉(zhuǎn)換計(jì)算)；若不是，則繼續(xù)迭代，…但每次迭代后都要檢驗(yàn)一下是否是最優(yōu)解。因此需要建立一個檢驗(yàn)準(zhǔn)則。假設(shè)一般情況下,經(jīng)過迭代后(基B0變換到UB1)約束條件(2-31)變?yōu)?把基變量仍然排在前m項(xiàng))：X.=bi-/ai.X.,i=1,2,...,m...(2-33)(用非基變量表示基變量)將(2-33)代入(2-30)得j=m+1mnm_Z=XC.b:-￡(XC.a:.-C,)X.???(2-34),令z=￡Cb',◎=￡Ca'一C,i=111.=m+1i=11ijjj1iij.ijji=1i=1則Z=Z-￡!oX.……(2-35)在(2-33)中令非基變量等于0,得基本可行解義1)，j=m+1(2-35)可以看出當(dāng)所有的Qj^0(j=m+1,...m),從z=z.-￡!ox°j=m+1X(1)為最優(yōu)解，Z1為最優(yōu)值，Qj為解的檢驗(yàn)數(shù)。用矩陣和向量的形式表達(dá)檢驗(yàn)數(shù)：XB=B-1b-B-1NXn,Z=CX=CBXB+CNXN=CBB-1b—(CbB-1N-Cn)Xn,QN=CbB-1N-Cn,QN=(CbB-1Pm+1-Cm+1，…CBB-1Pn-Cn)=(Qm+1(2-35)可以看出當(dāng)所有的Qj^0(j=m+1,...m),迭代(基可行解的轉(zhuǎn)換計(jì)算)若存在某些檢驗(yàn)數(shù)Qj<0，則X(1)不是最優(yōu)解，要進(jìn)行基可行解(可行基)的轉(zhuǎn)換。⑴進(jìn)基變量確定:從(2-35)可看出，當(dāng)某些Qj<0，則應(yīng)選Qj<0中絕對值最大者，即Qs=—MaxD|Qj||Qj<0｝對應(yīng)的Xs為進(jìn)基變量(最大換入原則).出基變量確定(最小換出原則)(A'b')=fX].Xr.XmXm+1.a1m+1-S….a1s.Xna1n..0...00.1.0'arm+1ars.a(A'b')=fX].Xr.XmXm+1.a1m+1-S….a1s.Xna1n..0...00.1.0'arm+1ars.arnb'r、0...0...1行初等變換得'amm+1'...ams-??amnbm「廣X]...Xr??-XmXm+1---XS.Xn1...-a1s/ars…0a1m+1??-0—a1nb'、b''1(A''b'')=0...1/ars0arm+1…1…arnb''r(1)主兀彳丁除以ars即ajj=arj/arsQ—12.?.n)br=br/ars(2)其匕彳丁兀素為a切=ajj-(arj/ars)ais,i女(j=1,2,...n),a”is=0,i女，b''i=b'i-(b'r/a'rs)a"i女，其中a”ij,b''i是迭代后的元素。由線性代數(shù)知識可得a''=(B)-1a',b''=(B)-1b',令非基變量等于0,則X(2)=(b"...b",0,b",0...0,b",0...0)T,Z=Cb''=(B)-1b'221r-1r+1r2B22若檢檢驗(yàn)數(shù)=^Ca〃+Ca〃一C，均>0,j=r,m+1,...,s_1,s+1,...n(。j=CbP''j-Cj=CB2(B2)-1P'j-Cj)J1ijsrjj2i=1i,r則X(2)為最優(yōu)解,Z為最優(yōu)值,否則重復(fù)前面步驟繼續(xù)迭代，直到求出最優(yōu)解或證明無最優(yōu)解為止.4.單純形表2為了方便地應(yīng)用單純形法求解線性規(guī)劃，設(shè)計(jì)一種表格，在表格上運(yùn)用單純形法運(yùn)算，這種表稱為單純形表，單純形表里面的數(shù)字隨著基可行解的變換而變換，每一個基可行解對應(yīng)著一段單純形表，如表2-4所示：單純形表CjC1C2...CmCm+1Cm+2...Cnbb/aisCbXbX1X2...XmXm+1Xm+2…XnCC12X乂21001...0...0‘1m+1'1m+2???&1n2m+1，2m+22nbb12CmXm00...1'mm+1'mm+2''''mnbmbj00...0bb...bm+1m+2nZ=tiC.b.T例11.運(yùn)用單純形表求解例9.解：標(biāo)準(zhǔn)型為：MaxZ=3X]+4X2+0X3+0X4+0X5TOC\o"1-5"\h\z滿足「-2X1+2X2+X3=2X1+X2+X4=5*X1+X5=4、Xj^0,J=1,2,3,4,5求解如表2-5所示：可得線性規(guī)劃的最優(yōu)解和最優(yōu)值分別為：X*=(23002)T,Z*=18.Cj34000bbi/aisCbXbX]X2X3X4X5000XX34X5-2[2]10011010100012541/5/bj-3-4000Z=0400X2X4X￡-111/200[2]0-1/21010001144/2/4b.-702004430jX2X1X.011/41/2010-1/41/20001/4-1/213225b.j001/47/2018第五節(jié)人工變量法和幾種特殊情況、人工變量法前面已提到，若從線性規(guī)劃標(biāo)準(zhǔn)型A中找不到線性無關(guān)的單位列向量，則采用人工變量法確定初始基本可行解，即在約束方程左端添加非負(fù)的人工變量，使A中出現(xiàn)m階單位子陣。在最優(yōu)解中人工變量必須為0,否則將違背原等式約束，因此經(jīng)過基的變換，必須把人工變量變?yōu)榉腔兞?，若最?yōu)解中人工變量為基變量且不為0,則原線性規(guī)劃無可行解。為了保證人工變量在最優(yōu)解中為0,所用的方法常見的有兩種：大M法和兩階段法。1.大M法：線性規(guī)劃約束條件中加進(jìn)人工變量后，假定人工變量在目標(biāo)函數(shù)中的系數(shù)為(-M)(M為任意大的正數(shù))，這樣目標(biāo)函數(shù)要實(shí)現(xiàn)最大化，必需把人工變量從基變量中換出，否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最大化。例13.求解線性規(guī)劃.MaxZ=3Xi-X2-X3滿足[X1-2X2+X3MII<-4X1+X2+2X3沱32X-X3=-1IXj^0,j=1,2,3解：標(biāo)準(zhǔn)化并加入人工變量X6,X7MaxZ=3X1-X2-X3+0X4+0X5-MX6-MX7TOC\o"1-5"\h\z滿足]X1-2X2+X3+X4=11J-4X1+X2+2X3-X5+X6=3]-2X1+X3+X7=1〔Xj^0,j=1,2,3,4,5,6,7用單純形表求解如表2-7所示：得線性規(guī)劃的最優(yōu)解和最優(yōu)值分別為：X*=(419)T,Z*=2.C;3-1-100-M-MbCX.X,X2X。XX,X,X70X41-211500011-MX6-4120-1103-MX7-20[11000116M-3-M+1-3M+10M00-4M0X43-20100-110-MX60[1100-11-21-1X-20100011-1-M+100M03M-1-M-10XF31001-22-512-1X2^0100-11-21-1X-20100011bj-10001M-1M+1-23X1—1001/3-2/32/3-5/34-1X20100-11-21-1X。0012/3-4/34/3-7/39bj0001/31/3M-1/3M-2/322.兩階段法用電子計(jì)算機(jī)求解含人工變量的線性規(guī)劃時(shí)，只能用很大的確定的數(shù)代替M，這可能造成計(jì)算上的錯誤，故采用兩階段法。第一階段：把原線性規(guī)劃標(biāo)準(zhǔn)化并加入人工變量，構(gòu)造一個輔助線性規(guī)劃如下：Minw=Xn+1+…+Xn+m(人工變量之和)fa11X1+-+a1nXn+Xn+1=b1a21X1+...+a2nXn+Xn+2=b2am1X1+?..+amnXn+Xn+m=bmlXj沱0j=1,2,...,n,...,n+m

對輔助線性規(guī)劃進(jìn)行標(biāo)準(zhǔn)化，并用單純形法求解，有兩種結(jié)果：一是目標(biāo)函數(shù)最小值為0,這說明原線性規(guī)劃存在一個可行解域，并且已得到了一個初始基可行解，可轉(zhuǎn)入第二階段計(jì)算；二是目標(biāo)函數(shù)最小值大于0,原問題沒有可行解，停止計(jì)算。注意：求目標(biāo)函數(shù)極小化，也可以不通過轉(zhuǎn)化為求極大化，由目標(biāo)函數(shù)表達(dá)式Z=mC.b!-￥(ZC.a，-C.)X.(2-34)可看出，若一個基可行解的檢驗(yàn)數(shù)全部非正，i=111j=m+1i=1iijjjm即=￡C.a'-C.<0,則目標(biāo)函數(shù)達(dá)到了最小值，得到了最優(yōu)解。否則，選取對應(yīng)。s=Max｛巧|巧>0｝的i=1非基變量Xs為進(jìn)基變量,再運(yùn)用最小比值原則尋求出基變量，確定主元，進(jìn)行迭代。第二階段：將第一階段最優(yōu)表格中目標(biāo)函數(shù)系數(shù)換成原目標(biāo)函數(shù)系數(shù)，劃去人工變量所在列，即得原線性規(guī)劃初始單純形表，然后繼續(xù)求解。仍以例13為例。第一階段：求輔助線性規(guī)劃MinW=X6+X7滿足［X1-2X2+X3+X4=11J-4X1+X2+2X3-X5+X6=3-2X1+X3+X7=1〔Xj^0,j=1,2,3,4,5,6,7列單純形表求解如下：C0000011bCXXX2^XXX5XX70X1-211000111X6-4120-11031X-20m000116-6130100W=40X43-20100-1101X0m00-11-210X.-2010001160100-10-310jX3001-22-5120X20100-11-210X~2-20100011600000-1-10j由上表可得輔助線性規(guī)劃的最優(yōu)解和最優(yōu)值分別為：X=(01112000)T,W*=0.由第一階段的最優(yōu)表得到了原線性規(guī)劃的一個初始基可行解：X=(011120)T,以及相應(yīng)的約束方程組表示形式(與原約束方程組形式等價(jià))。第二階段：求原線性規(guī)劃最優(yōu)解MaxZ=3X1-X2-X3+0X4+0X