第二章內(nèi)客提要ー、線性規(guī)劃的實際模型】?規(guī)劃間施數(shù)學(xué)模型三個要素(1)決策變信(2)目標函數(shù)(3)約束條件2.線性規(guī)劃何聞的敷學(xué)模型(D一般形式*目標函數(shù):max(或min)z=￡c丹X ,2)"(i=1.2.…?m)約束條件:J，TXj^O其中エ,0=1,2,…通)為決策變雖?a.G=l,2,…,mげ=1,2,…,n)為エ芭系數(shù),仇(i=l,2,…,m)為資源系數(shù),ク。=1,2為價值系數(shù).(2)標準型式(也稱規(guī)范形式)■maxt=〉\cjXf￡%エノ=A,(t=1.2,,???》!)與＞〇 (j=1,2,,?,,ね)二、線性規(guī)劃的求解方法.圖解法(1)優(yōu)缺點:(D圖解法:圖解法簡單直觀,求解線性規(guī)劃問題時不需將數(shù)學(xué)模型化為標準型,可以直接在平面上作圖,但此法只適用于二維問題,故有一定局限性.②用圖解法求解,冇助于了解絞性規(guī)劃冋題求解的基本原理。它可以直接看出線性規(guī)劃問題解的幾種情況:1e有推ー最優(yōu)解;ァ有無窮多組最優(yōu)解;3t無可行解;4t無有限最優(yōu)解(即為無界解).(2)圖解法的步驟:①建立平面直角坐標系;②圖示約束條件,找出可行城;③圖示目標函數(shù),即為一條直線;④將目標函數(shù)直線沿其法線方向在可行域內(nèi)向可行域邊界平移直至目標函數(shù)..單純形法(1)單純形法原理①基本思想:從可行域中的某個基本可行解開始到另ー個基本可行解,直到目標函數(shù)達到最優(yōu).②理論基礎(chǔ)：定理1若LP問題可行域存在,則可行域是個凸集。定理2LP問題的基可行解與可行域的頂點ーー對應(yīng).定理3若しP問題存在最優(yōu)解,則一定存在ー個基可行解是最優(yōu)解.(2)單純形法的步驟及解法①找出初始可行基,確定初始基本可行解,建立初始單純形表.②檢驗此基本可行解是否為最優(yōu)解.即檢驗各非基變盤xi的檢驗數(shù)%,若所有の&O(j=m+l,…述)則已經(jīng)得到最優(yōu)解,計算停止;否則轉(zhuǎn)下一步.④根據(jù)max('>0)=6,確定非基變量4為換人變量;再根據(jù)G法則Q—mjn(--1a?>0)=--確定基變量”為換出變量。⑤實施樞軸運算,即以む為主元素進行樞軸運算(亦即進行矩陣的行變換),使P?變換為第1行的元素為1.其余的元素為0;并將Xb列中的?換為“,從而得新的單純形表;重復(fù)②?⑤,直到終止.3.兩階段法、大M法以及運用人工變?法求解非規(guī)范型的線性規(guī)劃問題(1)兩階段法①原理:此方法是將加入人工變量后的線性規(guī)劃問題分成兩個階段來求解.第一階段:其目的是為原問題求初始基本可行解.為此,對于求極大化(或極小化)的線性規(guī)劃問題,建立一個新的人工變量的目標函數(shù) 人工變量的系數(shù)均為ー1或(+1),對新的問題:maxw=-x,+i-x.+t-x.+.或 minw=x,+l4-xir+,4--+x(,+.4“あ+…ユ?+n?+i =b\t.Ja-Ui+…+a■?ユ? +ム+?.=ねェ1,???,〇:?ユ〇,n.+i，…,z?一.》〇用單純形法求解.若w=0,即所有的人工變量都變換為非基變量,說明原同題已得到了初始基本可行解;反之,若目標函數(shù)m的值為負(或為正)，則人エ變量中至少有一個為正,這表示原問題無可行解,應(yīng)停止計算.第二階段:將第一階段求得的基本可行解對原冋題的目標函數(shù)進行優(yōu)化，即將目標函數(shù)換成原目標函數(shù),以第一階段得到的最終單純形表除去人工變量的列后作為第二階段計算的初始表,繼續(xù)用單純形法以求得冋題的最優(yōu)②計算方法:單純形法.(2)大M法(D原理：人工變量在目標函數(shù)中的系數(shù)確定：若目標函數(shù)為maxz?則系數(shù)為一M;否則為M.②計算方法:單純形法.

三、了解線性規(guī)劃的解及其幾何意義.可行解:凡滿足線性規(guī)劃約束條件的解稱為可行解。.最優(yōu)解:使目標函數(shù)達到最大的可行解稱為最優(yōu)解。.基:設(shè)A是約束方程組mXn維系數(shù)矩陣,其秩為m,B是矩陣A中mXn階非奇異子矩陣,則稱B是線性規(guī)劃問題的一個基..解的幾何意義:(1)若線性規(guī)劃問題有可行解.其所有可行解構(gòu)成的區(qū)域稱為可行域,則此可行域D={XI=bi，i=1,2,…，20}必是ー個凸集.(2)線性規(guī)劃問題的基本可行解與可行域D的頂點ーー對應(yīng).(3)如果線性規(guī)劃問題有有限的最優(yōu)解,則其目標函數(shù)的最優(yōu)值一定可以在可行域的頂點上達到.修)1.1］用圖解法求解下列線性規(guī)劃問題,并指出問題是具有惟ー最優(yōu)解、無窮多最優(yōu)斛、無界解還是無可行解，(l)maxz=Xi+3(l)maxz=Xi+3エ］5Xj+10處450X1+S?t?VS44マ】(3)max?=2xi+2xj(2)minz=xi+1.5x：(x\+3Xz23s.t.JXt+X>>2工］,工zi0(4)maxz=X|+x2Xi—Xiユ〇S?l?<3xj-よ?4-3Xi,x：^0解(1)圖1一2中的陰影部分為此線性規(guī)劃問題的可行域,目標函數(shù)z=xi+3x,,即ム=一よ?與+う是斜率為ーく的一族平行線,易知ぢ=3,及=0為可行解,由線性規(guī)劃的性質(zhì)知,其最值在可行域的頂點取得,將直線ち+3ロ=3沿其法線方向逐漸向上平移,直至A點,人點坐標為（2,4）.圖1-2所以 max?=2+3X4=14此線性規(guī)劃問題有惟一最優(yōu)解.（2）圖1一3中的陰影部分為此線性規(guī)劃問題的可行域,目標函數(shù)2=あ+1.5も,即x,=ー/り+ヒ是斜率為ー?1"的一族平行線,易知り=3,厶=0為可行解,由線性規(guī)劃的性質(zhì)知,其最值在可行域的頂點取得.將直線あ+1.5皿=3沿其法線方向逐漸向下平移,直至B點,B點坐標為仔子）所以 minz="1"+l.5X；=?此線性規(guī)劃問題有惟一最優(yōu)解.r-4Xi+厶—2よ3+ムー+xw=2Xi+x：+3x1-x$+x,+X7 =14s.tJ—2X]+3xt-X)+2ムー2x?—Xg+z0=2Xi，12，エj，Xs，よ，，N7，ム，孫，初ユ〇其中M是ー個任意大的正數(shù).初始單純形表見表1一2.我!-2Cjf3一42-5500-M-M0C.X.bXiXiXj4X|厶X|X|X10一Mxl02-41-21-1000120XT14113T1100014一MX|2-2[3]-12-20-11023t一W4M3-6M4M—42-3M3M—55-3M0一M00(2)在上述冋題的約束條件中加入人工變量エ1ホハ…,エ?,得max$=夕a.xコーMx]ーMj[2一???max$=A-1卜+2xa=l(￡=1,2,???,/!)[ハユ〇,エユ。(￡=1,2,***fn；i=l,2,-tm)其中M是ー個任意大的正數(shù).初始單純形表見表1-3.表1一3町MM???<hi薪￡11“<1*ハ???d.lPkph???<2?b770CbXBbェ1xi2.*11XUX?1N-MXI1100111000MXX1010000000??**■?****?*?(????**?*???M1001000111-9nM000乎+M&+M等+M察+Mp*等+M力占+Mん01.21將下列線性規(guī)劃問題變換成標準型,并列出初始單純形表,minz=—3あ+4ムー211+5ム4xi-xI+2xj-x4=—2X|+xj+3x>-s.t.J, .一-2xi+3xz-xs+2x4》2X],ム,.ユ0,よく無約束max$=zj%Za=ととむい?い1l】m?2i一H.二一1 (i=l,…，n)上-1xヨi0 (i=l「??,れ議=1,…，m)分析本題考査了線性規(guī)劃問題的標準形式和初始單純形表。解(D將此線性規(guī)劃問題化為標準型。令ユ=x5-X, =Z其中“5,X,20所以 maxz=_min(——)=—minz則得到標準型為maxz'=3xj-4x>+2x>-5(x$-X6)+0?x?+0?xt-Mk,—Mx\0?1.6]分別用單純形法中的大M法和兩階段法求解下述線性規(guī)劃冋題?并指出屬哪ー類解.(1)maxn=2xi+3n,-5x3Xi+Xi4-Xj=7s.t.J2Xi—5xi+x3^10X|，x3》0分析本題考査、了単純形法中的大M法,兩階段法以及解的類型的概念.解(1)解11大M法,在上述線性規(guī)劃問題的約束條件中加上人工變量ち,エ,,減去剩余變量上,得maxz=2xi+3れー—Mx4+0x5—Mx?Xi+x1+xj+x4 =7s.t.J2xi-5x：+x3 -x$+x1=10Xi,x2ixJ，/，ム用ユ〇其中M是ー個任意大的正數(shù)。據(jù)此可列出單純形表表1—6,表1一6ウ23 -S一M0MftCbXb6X1X：x1x<X?x<-Mェ471111007.Mx?10[2]-510-115ウーり3M+23-4M2M-50一M0-MX420[7/2]1/211/2-1/24/72エ】51T/21/201/21/2一ウー叼03M/2+8M/2-60M/2+13M/213XI4/7011/72/71/7-1/72XI45/7106/75/7-1/71/7ウー身00SO/7M16/7-1〃M+l"由單純形表的計算結(jié)果得:最優(yōu)解X，二（竽,小,0,0,0,0）T,目標函數(shù)的最優(yōu)值ビ=2X竿+3X^=半.解2:兩階段法?先在上述線性規(guī)劃問題的約束條件中加入人工變量ム,ム,減去剰余變量ム,得第一階段的數(shù)學(xué)模型minw=x<+ム，X\+xi+x>+z< =7s.t.J2X\—5z1 -zs+z1=10Z]?ZjfZj,z4,z§,z.ユ〇據(jù)此可列出單純形表表1-7：

表1一7ウ000101ACBXBbxiX2Xjx<xsA1ェ4711110071Xf10[2]-510115ウー句-3420101勾20[7/2]1/211/2T/24/70XI51-5/21/20-1/21/2一ウー町0一7/2T/20-1/23/20XI4/7011/72/71/7-1/70XI45/7106/75/7-1/71/7ウーち000101第一階段求得的最優(yōu)解X'=(竿",0,0,0,0)T,目標函數(shù)的最優(yōu)值ザ=0.因人工變量エ4=ム=0,所以岑ヨ,0,0,0,0)T是原線性規(guī)劃問題的基可行解.于是可以進行第二階段運算,將第一階段的最終表中的人工變量取消,并填入原問題的目標函數(shù)的系數(shù),進行第二階段的運算,見表1—8.盯23T0ftCbXbbX1X2X|Xf32X，XI4/745/701101/76/71/7-1/7ウーち00-50/71/7由表中計算可知,原線性規(guī)劃問題的最優(yōu)解X-=(竿キ。,0,0,0)T,目標函數(shù)的最優(yōu)值ザ=2X與+3X9華,第三章

ー、原問題與對偶問題的關(guān)系若某線性規(guī)劃（原問題）約束系數(shù)矩陣為ん約束條件右端為向量b,目標函數(shù)中的價值系數(shù)向量為C,則其對偶問題形式如表2-1所示,表2-1

原冋題（對偶冋題）■目標函數(shù)maxz=2J盯對偶冋題（原問題）■minw=￡ん"有n個。=1,對偶冋題（原問題）■minw=￡ん"有n個。=1,…,n）變’?量約束條件

りちう

>&=

“シ“

aaa

ES-一“s-i-1約束條件有m個(￡=1,???,m)n￡ヘウ&biノ?iゝへ巧》bij-i乙も巧=biy,y,>0 變ッ4〇 SM無約束二、對偶理論及其性質(zhì).對稱性:對偶問題的對偶是原問題。.弱對偶性:若ア是原問題的可行解,テ是對偶問題的可行解,則有CX^Yb.無界性:若原問題（對偶問題）為無界解,則其對偶冋題（原問題）無可行解。.可行解是最優(yōu)解時的性質(zhì):設(shè)マ是原冋題的可行解,y是對偶問題的可行解,當。マ=為時,え，均為最優(yōu)解..對偶定理I若原問題有最優(yōu)解,那么對偶問題也有最優(yōu)解,且目標函數(shù)值相等..互補松弛性:若スヨ分別是原問題和対偶問題的可行解.那么えXs=O和YsX=O當且僅當ヌ、V為最優(yōu)解..設(shè)原問題是maxz=CX；AX+Xs=6;X,Xs20它的對偶問題是minw=YhtYA-Ys=CiY,Ys^Q則原問題單純形表的檢驗數(shù)行對應(yīng)其對偶問題的一個基解。三、對偶單純形法.對偶單純形法與單純形法的區(qū)別對偶單純形法是運用對偶原理求解原問題的ー種方法,而不是求解對偶問題的單純形法.它和單純形法的主要區(qū)別在于:單純形法是從ー個原始問題的基本可行解轉(zhuǎn)到另ー個基本可行解,即迭代中始終保持原問題的可行性,亦即常數(shù)列而檢驗數(shù)。=C-CB'A=C-YA由有正分量逐步變?yōu)槿?0（即變?yōu)闈M足YA》C,Y是對偶問題的基本可行解）為止.對偶單純形法則是保持對偶問題解是基本可行解（即全部檢驗數(shù)。》0）,而原問題在非可行解（即常數(shù)列ら有負的分量）的基礎(chǔ)上通過逐步迭代達到基本可行解（即常數(shù)列5全部>0）?這樣,同時得到原問題和對偶問題的最優(yōu)解..對偶單純形法的計算步驍（1）將問題化為標準型,列出初始單純形表格.（2）若存在初始對偶可行的基本解,則進行迭代.（3）檢驗b列的數(shù)字,若檢驗數(shù)全部非正而b列都為非負,則問題已得到最優(yōu)解,終止迭代;否則,若檢驗數(shù)全部非正而b列至少還有一個負分量,進行下ー步.（4）確定換出變量,即按min｛（B ,fr）i<O）=（B⑹,對應(yīng)的基變量ム為換出變量.（5）確定換人變量:檢査X,所所在行的各系數(shù)ル。=1,2,…,“）.若所有與ユ〇,則無可行解停止迭代,若存在ルV0,按タ法則,即0=min］纟|/V。i=—/1agiJa&所對應(yīng)的列的非基變量胃為換人變量.（6）實施樞軸運算,即以小為主元素按原單純形法在表中進行迭代運算,得新的單純形表格,轉(zhuǎn)步驟（3）繼續(xù)迭代.四、影子價格影子價格:根據(jù)資源在生產(chǎn)中作出的貢獻而作的估價,影子價格是ー種邊際價格,其值相當于在資源得到最優(yōu)利用的生產(chǎn)條件下,資源毎增加一個單位時目標函數(shù)增加量.影子價格的大小反映了資源的稀缺和富有程度.在完全市場經(jīng)濟的條件下,當某種資源的市場價格低于影子價格時,企業(yè)應(yīng)買進該資源以擴大再生產(chǎn);反之.則應(yīng)將已有資源賣掉.可見,影子價格對市場有周節(jié)作用.五、靈敏度分析由于可用資源的數(shù)最發(fā)生變化,右邊限制系數(shù)と會發(fā)生變化,由于市場條件發(fā)生變化,價值系數(shù)ら會發(fā)生變化;由于生產(chǎn)エ藝的改進,約束條件系數(shù)へ會發(fā)生變化.當線性規(guī)劃問題中的一個或幾個系數(shù)發(fā)生變化后,原來求得的結(jié)果一般會發(fā)生變化。靈敏度分析的步驟可歸納如下，1.將參數(shù)的改變計算反映到最終單純形表上來:具體計算方法是,按下列公式計算出由參數(shù)％、灰、G的變化而引起的最終單純形表上有關(guān)數(shù)字的變化:△b，=B'A6APJ=b1へPiM△（勺-Z/）?=△（勺-N/）ーダヘガ2,檢査原問題是否仍為可行解;.檢査對偶問題是否仍為可行解;.按表2-2所列情況得出結(jié)論和決定繼續(xù)計算的步驟.表2-2原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解仍為問題最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進人工變量,編制新的單純形表重新計算|O2.1|用改逬単純形法求的以下線性規(guī)劃冋題.（l）maxr-6xi~2x9+3x>2xi-x1+2N《2<Xi +4X《4分析先將線性規(guī)劃問題轉(zhuǎn)化為標準形式再用改進單純形法求解.解（1）將上述線性規(guī)劃向她轉(zhuǎn)化為標準形式maxr-6xi-2x>+3x>+0?x,+0?x$2xx-x>+2x|+x4 =2.lJq+5+工廠4X\?X|iX?tXj）0取Bo-（P-Ps）-（；；）， XBo=（x4,x,）t?。へ?（0,。），M=s，p,,p,）=（iズル x%=5,エ,,q）T,Cvf=（6,-2,3）, BJ=（：；）,氏=（：）非基變?的檢驗數(shù)“N.=C“，—C'Bo1No=Cv.=（6,-2,3）???皿的檢驗數(shù)%=6為正的最大，:?エ、為換人變量.…ぐ），&屮=（；）由。規(guī)則得ク丁n｛證證［出書）>。尸加符チ尸Ax?為換出變屬-（a B?4=（；）由0規(guī)則得

…網(wǎng)轡齡|(BJPJ>O)=min存ラ}=1エム為換出變國5?舊出)■(；]), X產(chǎn)出,厶)T, C^=(6,0),M-(P,，P,,匕)=(0 0 4>Xm=G.h)t,CM|=(0.—CM|=(0.—2,3),]0?Bノん?加;)非基變氣的檢驗效叫=C?-C與B,1M「1TOC\o"1-5"\h\z. ~2=(O,-2,3)-(6,O)1■"——=(0,-2,3)-(3,0)/ ,(0 04)-(0,-2,3)-(3,-3.6)=(-3,1,-3)Vx?的檢驗數(shù)s=l為正的最大,???乃為換人變片.由ク規(guī)則得片叫マ^^出書)》。由ク規(guī)則得片叫マ^^出書)》。『min{/『6???工,???工,為換出變址.ル=(刊出)=しo),X??(m)T, C^-(6,-2),A〇2ゝM=(Pい巴，巴)=( ] kX^-Cx.^.x,)7,Cm,-(0,0,3),-12非基變量的檢冷敷tfw, -C、B,Ni=(0.0.3)-(6.--12非基變量的檢冷敷tfw, -C、B,Ni=(0.0.3)-(6.-2)121001=(0,0,3)-(2,2)=(0.0.3)-(2,2,12)=(-2,-2,-9)???若茶變身的檢驗數(shù)均為負,???原問題已達到最優(yōu)解.最優(yōu)解X--Xlメ。或X-=(4.6.O)T目標函數(shù)最優(yōu)值maxz=6X4-2X6+3X0=12.02.3寫出下列線性規(guī)劃問題的對偶問題。02.3(l)min2=2為+2力+4馬2x\+3馬+5工1》2"X|+4x>+6xj^5Xj9X29Xj^^0分析本題考査了對偶問題的轉(zhuǎn)化.解(1)將原問題化為max(-z)=-2xi-2x1-4xs①②③④-2xi-3x?-5xs&-2①②③④3xi+?Z2+74&3X\+4て］+6ち45Xi，X［》0設(shè)”,山,“分別為與約束條件①②③對應(yīng)的對偶變量此問題的對偶問題為min(-w)=-2vi+3vz+5vaminw=5>i-5y2-8%+20シ，ーアi+yt-6>i+12y4>lyt~~7yi_9ソ4>2>i-シ+3山+9y4>—3t.《—3%+3“+5w+9Mユ43y-3"-5>,—9y4>—4Ji，”，“，“ユ。第四章:運輸問題表中2>，為各產(chǎn)地的產(chǎn)量之和,E加為各侑地的銷量之和當火ム=火や，即產(chǎn)最=銷量時,稱為產(chǎn)銷平衡。當Sa->wx，即產(chǎn)量>銷量時、- : 除稱為產(chǎn)銷不平衡當v￡8,即產(chǎn)量v銷量時二、表上作業(yè)法及其在產(chǎn)銷平衡問題中的應(yīng)用1.產(chǎn)銷平衡問題與表上作業(yè)法(1)產(chǎn)銷平衡問題的數(shù)學(xué)模型具有m個產(chǎn)地ん(i=l,2,…,m)和ヮ個銷地= …,Q的運輸問題的數(shù)學(xué)模型為:?Wmin?=2_j2jc*x?=4G=l?2t-tn)'1<Xム=ム(，=1.2,…,m)

i-i它包含mXn個變量,(m+ぬ個約束方程,其系數(shù)矩陣的結(jié)構(gòu)松散,且比較特殊.其系數(shù)矩陣為:(2)表上作業(yè)法.表上作業(yè)法是單純形法在求解運輸問題的ー種腐化方法.其計算步驟如下:①列出產(chǎn)銷平衡表.②確定初始基可行解,即在產(chǎn)銷平衡表上給出m+n-1個數(shù)字格,確定初始基可行解一般用最小元素法和伏格爾法?③求各非基變量的檢驗數(shù),即在表上計算空格的檢驗數(shù),判別是否達到最優(yōu)解。如已是最優(yōu)解,則停止計算,否則轉(zhuǎn)入下ー步.④確定換人變量的空格.⑤確定換出變量的空格.⑥沿閉回路調(diào)整運輸數(shù)最。⑦重復(fù)步驟③一⑥,直至所有空格的檢驗數(shù)ら均為非負為止,此時便可得到最優(yōu)方案。(1)產(chǎn)大于銷問題對于此類問題,設(shè)有一個假想銷地B.+1,其銷量ん+i=ミムーX8但實際上沒有運輸,故其單位運價為0:這樣就土化產(chǎn)銷平衡問題,但沒有破壞原冋題的性質(zhì).(2)銷大于產(chǎn)問題對于此類問題，設(shè)有一個假想產(chǎn)地ん7,其產(chǎn)量.■a.+iー〉:仇ー〉:ム但實際上沒有運輸,故其單位運價為〇:這樣就轉(zhuǎn)化為產(chǎn)侑平衡問題,但沒冇破壞原問題的性質(zhì).4.3用表上作業(yè)法和伏格爾法求表中的運輸問題的最優(yōu)解和近似最優(yōu)解。鎖 地產(chǎn) 地 、、、?甲乙丙T成i產(chǎn)量11020591052210830663120710424863759的量44624解表3—23:利用伏格爾法求出初始解,步驟和過程參考解表3-22.第一步:分別計算表3—23中各行、各列的最小運費和次最小運費的差額,并填入該表的最右列和最下行.第二步:從行或列差額中選出最大者,選擇它所在行或列中的最小元素.第三步:對未劃去的元索再分別計算出各行、各列的最小運鉗和次最小運費的差額,并填入該表的最右列和最下行,重復(fù)第一、二步,直到給出初始解為止.最后再利用位勢法檢驗.解表3—24：表3-33是產(chǎn)銷不平衡的運輸問題,所以増加一個假想銷地巳,并令其運價為〇,其銷量為5+6+2+9—(4+4+6+2+4)=2,見表3—36.表3—36、、、ヽ、^ 傳地產(chǎn)地 、、、、甲乙丙T戊巳產(chǎn)量110205910052210830606312071040248637S09銷量446242利用伏格爾法求出初始解,第一步:分別計算表3—36中各行、各列的最小運費和次最小運費的差額,并填入該表的最右列和最下行.第二步:從行或列差額中選出最大者,選擇它所在行或列中的最小元素.第三步:對未劃去的元索再分別計算出各行、各列的最小運費和次最小運費的差額.并填入該表的最右列和最下行,重復(fù)第一、二步,直到給出初始解為止.最后利用位勢法進行檢驗.所有檢驗數(shù)都非負,故解為最優(yōu)解。這時得到的總運費最少,為90.故該運輸問題有無窮多最優(yōu)解.2.衣3—23コ*串乙丙T產(chǎn)量110671242161059935410104的?5246

分析本題考査了表上作業(yè)法,可先利用伏格爾法求出初始解,再利用位勢法進行檢驗.解解表3—22:利用伏格爾法求出初始解?第一步:分別計算表3—22中各行、各列的最小運費和次最小運費的差額,并填入該表的最右列和最下行,見表3-26.表3-26、7、^銷地地甲乙丙丁列箱額137641224320343851列差額1132第二步I從行或列差額中選出最大者,選擇它所在行或列中的最小元素.在表3-26中,丙列是最大差額所在列，丙列中的最小元素為3,可確定產(chǎn)地2的產(chǎn)品先供應(yīng)給銷地丙,因為產(chǎn)地2的產(chǎn)髭等于銷地丙的銷姑，所以在（2,丁）處填入ー個。,得表3-27并同時將運價表中丙列數(shù)字和第二行數(shù)字劃去,如表3-28所示.*3-27'''、、、、^銷 地產(chǎn)地 、、、、甲乙內(nèi)T產(chǎn)量12320523銷量3322表3-281銷地地甲乙丙T產(chǎn)量1376452243223438S3策量3322第三步:對表3—28中未劃去的元素再分別計算出各行、各列的最小運費和次最小運費的差、額,并填入該表的最右列和最下行,重復(fù)第一、二步,直到給出初始解為止.用此法給出表3-22的初始解如表3-29所示.

表3-29地甲乙丙T產(chǎn)量130252202333銷量3322利用位勢法進行檢驗。第一步:在對應(yīng)表3-29的數(shù)字格處填入單位運價,見表3-30.a3-30的地產(chǎn)地甲乙丙T123373342第二步:在表3—30上增加一行一列,在列中填入“,,在行中填入q,得表3—31.表3—31地甲乙丙TUi13740232一233-4目3754先令均=0,然后按“,+叼相繼地確定ム,玲由表3—31可見,當“1=0時,由小+"i=3可得硏=3;由3+”=7可得“==7;由“|+ロ=4可得5=4;由vx=7,uJ+vI=3可得“j=-4;由リ=4,“2+q=2可得“z=-2;由“工=-2,%+vj=3可得vj=5第三步:按%=0一（“,+も）,i,，WN計算所有空格的檢驗數(shù),如表3—32所示.

表3-32、、、銷地產(chǎn)地 、、、甲乙丙T叱1030716040212-140302一2354037855-4叼3754on一(0+s)=2—(-2+3)=1如=Cu-(ih+s)=4—(-4+3)=5on=c?i—(%+5)=4-(-2+7)=-1,ffu=cij—(?!+”)=6-(0+5)=16：=c”-(%+s)=8-(-4+5)=7,64=c“一(%+q)=5-(—4+4)=5在表3—32中還有負檢驗數(shù),說明未得到最優(yōu)解,可以利用閉回路調(diào)整法加以改進。由表3—32得（2,乙）為調(diào)入格,以此格為出發(fā)點,作一閉回路,如表3—33所示.表3-33銷地產(chǎn)地 、、、甲乙內(nèi)T產(chǎn)量130(-1)2(+1)520(41)2 :0(-1)2333銷量3322（2,乙）格的調(diào)人量。是選擇閉冋路上具有（一1）的數(shù)字格中的最小者,即0=min{O,O},然后按照閉冋路上的正、負號,加上和減去此值,得到調(diào)整方案,如表3—34所示.表3—34銷地產(chǎn)地 、、、甲乙丙T產(chǎn)量130252022333值R3322對表3-34給出的解,再用位勢法求各空格的檢驗數(shù),如表3-35所示,所有檢驗數(shù)都非負,故表3—34中的解為最優(yōu)解.這時得到的總運費最少,為32由于表3—35中（1,丙）格的檢驗數(shù)為〇,故該運輸問題有無窮多最優(yōu)解.表3-35、、、、^ 侑地產(chǎn)地 、、、甲乙丙丁Ui1232506150-3一4叼3764第五章:目標規(guī)劃104.31用單純形法求解以下目標規(guī)劃問融的滿意解.（1） min +Pid]+2馬+カーd\=10lOxi+12xt+c/t—di=62.42xi+448ェi.xnd, 〇,i=l,2分析本題考査解目標規(guī)劃的單純形法?解（D將上述目標規(guī)劃問題化為如下形式：minz=Pidi+P>d,+P"iXi+2x,+dj~d\=010口+12耳+ムーd；=62.4,2xi+x*+x> =8皿?エ”,ユハー,d:其中馬為松弛變量.對于此問題用單純形法進行計算.見表4-1.

A4-1000Pl0p.PldC.x?*X|XiX]4dtdldlPidi101[?0I一100sPldi6L410120001一1ェ20821100008PlPl-107-12-200000100I00?n5T10Tー丄200Pldi2.4400-6w1I0.4ら000Pl0PlPiCBXbbxixiXididididiCF0X]3301]006Pi一4006一602PI00010000Xx5.2gT1000モ丄126.240dt0.4[もL3J0011丄6]V0.60Xi2.8L60100"121li2.4Pl000001iPl0001000由表4-1可得ni=0,z,=5.2為原問題的滿意解,而非基變量為的檢驗數(shù)為0,故原問題存在多重解.在実4-!的真礎(chǔ)卜以工,為槍人奇景.メナ為撤出有保?再次佳一用.很美4-2.衣4-Z000Pl0PiPi0CBXbbXiHlXididtdidt0xi4.70105_VgV]VV0xi0.6100w310XI2.100177VV3VPl0000011Pl0001000由表4—2可得よi=O.6,z：=4.7也為滿意解“由線性規(guī)劃的性質(zhì)可得:(0.6,4.7)和(0,5.2)這兩點之間的線段上的所有點均為原問題的滿意解.第六章:整數(shù)線性規(guī)劃QS.I］用分支定界法解:maxr=X|+工,,_9_ピ51，了‘十14工’￡14皿，エ,>0Xi,x2整數(shù)分析本題考査了分支定界法.解在原線性規(guī)劃問題約束條件中分別添加松弛變量も,ム,化為標準型,ロJ得maxz-x\+工,9 ,_51ェ1十訶エ2十工3=瓦S?く 3N1Hi,エ《ユ〇X1,X2整數(shù)不考慮整數(shù)條件,用單純形求解,計算結(jié)果如表5-4所示.表5-4盯1100ftC?X.bXIxiェ，00X1X451/141/3[1]-29/141100151/14。一町320010XIェ451/14160/21109/14[161]120151/9160/3381與ー旳05/14-1011よ】213/210/310017/167/8-9/327/16ちー，00—21/16-5/32因而最優(yōu)解為得ぎ,O,O)T,z?因為エ=0<ザ&豊=工,相原問題分解為兩個子問題:maxz—x\+工2,9 ピ51f十倉工(B,)得最優(yōu)解よ］=1,N2=く,た!=學(xué)maxz=X\+馬,9-51X1+l4X,<U(B2)-2xi+エ(B2)ェi>2工2>0得最優(yōu)解了「25一等,ml禁由此判定可取三二04ビ《萼再分解B1為兩支B,和Brmaxz=3エi+2ぬ9z51

x,+i4Xi<n(BO ?.t.r2x,+Xi<t。<エW1

O<xi<l得最優(yōu)解工廠卷口…宀イmaxx=3xi+2h.,9 —51x*+『(B() 3.3-2xi+x><yN141，xI23無可行解,故剪去ル分支.再分解Bt為兩支&和Bハmaxx=3xi4-2tj,9 ピ51x,+ミ上，(而(Bj)-2エ1+xiCyx,<2(Bj)0<x,<2得最優(yōu)解x,-2,x,-2I-4為整數(shù)解,由此判定可取エ=44ズ（甘maxr=3xi4~2xi,9 く51皿+ア(に—2x(+x,x,>2x,>3無可行ヌ,故剪去ル分支.因為ルVr-4,故剪去B,分支,從而可以斷定x；=2,x；=2為最優(yōu)整數(shù)解,ゴ=4.|〇5.6|解。1規(guī)劃:(l)minr=4xi+3xt+2x>f2x\—5Xi+3x3《44xI+x2+3xa)3Xi+ムユ1Xi?X1>X2,エ3=0或1分析本題考査了0—1型整數(shù)規(guī)劃.解（1）給各約束條件編號如下,

—5X2+3N3444xi+エ1+3工3s.t.＜工2+工ユ21ェ1,工＞,工?=0或1先找到（0,0.1）丁為可行解.相應(yīng)的N=2,故增加約束條件4エ1+3n*+2n?<2 (0)表5—10(X1VZ|X|)條件是否満足條件S《口）《1)《2)《3)(0.0.0)000X(0.0.1)233372＜〇“.〇）3X(0.1.1)5X(1.0.0)4X《1.0.1)6X《1?1,1)7X《1,1.1)9X所以,可判定最優(yōu)解X-=（0,0,l）T,目標函數(shù)最優(yōu)值ゴ=2.105.71有4個工人,要指派他們分別完成4種工作,每人做各種工作做消耗的時間如下表所示,問指派哪個人去完成那種工作,可使總的消耗時間為最小?表5-12、、、、^ X聆工人ヽ''ABCD甲IS182124乙19232218丙26171619T19212317分析本題考査的是指派問題,用匈牙利法求解.解變換系數(shù)矩陣為15182124150369rmin(q)=2923221818-A1540=（耙）26171619161010319212317172 46 0一再進行試分配,得0269'1 44◎10〇032 36 0因為m=3Vn=4.試指派不成功轉(zhuǎn)下步,所以指派成功,故此項工作有多種指派方案,Z=70,指派矩陣如下:oj10100oj10100000010001001.010即最優(yōu)指派方案為,(1)甲fA,乙fD,內(nèi)fC,丁?*Bi(2)甲一B.乙?*A.丙-C.丁"*D?第七章:動態(tài)規(guī)劃（5）狀態(tài)轉(zhuǎn)移方程（D逆序遞推的基本方程—，耀?{水…）+“=Q}（ん=n,n—1,…，2,1）,邊界條件為y?+!（>?+1）=0,式中?**+1-T?（j*,k>）?其求解過程,根據(jù)邊界條件從え=”開始,由后向前逆推,可逐步求得各段的最優(yōu)決策和相應(yīng)的最優(yōu)值,當最后求出力（刈）時,便得到整個問題的最優(yōu)解,其各階段和各變量之間的關(guān)系如圖8-1所示??/1（?!>ルメ*4<St> 4/,?.）圖8-1②順序遞推的基本方程/*（シー1）=Opt{??（?*+1，?*）+/*-!（0））“修ハ（*=l,2,-,n）,邊界條件為んg）=o;式中s,=n（$宀，一）,即狀態(tài)轉(zhuǎn)移是由s*-,必去確定5*.其求解過程,根據(jù)邊界條件從え=1開始,由前向后順推,可逐步求得件段的最優(yōu)決策和相應(yīng)的最優(yōu)值，當最后求得ん（S.H）時,便得到整個問題的最優(yōu)解.其各階段和各變量之間的關(guān)系如圖8—2所示,ュ曰，曰?…セ口F件」斉?圖8-2一般地說,當過程的始點給定時,用逆序遞推比較方便;而當過程的終點給定時，用順序遞推比較方便.解設(shè)階段變量る=1,2,3,4依次表示4個階段選路的過程,第1階段從A出發(fā)到Bi、BI或ル,第2階段從或B,出發(fā)到GC或G,第3階段從C,G或G出發(fā)到な或ル,第4階段從D,或D,出發(fā)到E,狀態(tài)變量”表示ん階段初可能的位置;決策ム表示と階段初可能選擇的路線;階段指標5表示ん階段與所選擇的路段相應(yīng)的路長;指標函數(shù)3=%s表示る至4階段的總路長;遞推公式:ん=min{xfk+ん+1）"=4,3,2,ls/s=0.解設(shè)階段變量ん=1,2,3,4依次表示4個階段選路的過程,第1階段從A出發(fā)到8いB或ユ,第2階段從B1、Bz或出發(fā)到G、Cフ或G?第3階段從GC或G出發(fā)到5或。,,第4階段從D,或Dt出發(fā)到Et狀態(tài)變量”表示セ階段初可能的位置;決策ち表示ん階段初可能選擇的路線;階段指標a表示ん階段與所選擇的路段相應(yīng)的路長;指標函數(shù)もS表示る至4階段的總路長;遞推公式:んumin{?i+/*+i>,i=4,3,2,h/l=0.表8-2kハs/*よ「4DiE3030+030EDiE4040+040E3GD,1010+3040DiDi4040+40CiDi6060+3070DiD*3030+40ClDi3030+300DiDi3030+402BiCi7070+40noC!、CtCt4040+70G6060+60BiCi3030+4070Gc.2020+70c,4040+60BiCl4040+4080Ci、CtCt1010+70C,5050+601ABi2020+110noル、品B.4040+70Bj3030+80由表中計算結(jié)果可以看出,運費最低的路線為:ABGAE或AB.QD.E或ABjGDzE,最低運費為110?。8引用遞推方法求解下列問題(l)maxz=4xI+9=,+2x}ゆ+工,+工,=10s.t.レ?ユ。?i=l,2.3分析當初始狀意給定時,使用逆推解法,當終止狀布給定時,使用眼推解法.解(1)由題意,將問題劃分為三個階段,設(shè)狀布変量為與.力,”,外,并記ハ二10.必,工,?胃為各階段的決策變量.各階段指標函數(shù)按加法方式結(jié)合.厶(シ)表示第?階段結(jié)束狀態(tài)為“,第1至第え階段的最大值則由約束條件可知xj=Sj*Ji-Fxj=ij? 力+工ハ,=10即Si=X1t〇&エ!<52， 0&N,&Ss由順推法f\(sj)=max(4xl)=4si最優(yōu)解tXi=Jj/?Gi)=max[9x>+/1(*i)J=最優(yōu)解:N；=S2/?Uj)=max[2xj+/t(j|)]=200。j〈io最優(yōu)解:ム?=10x；=s1=10—x；=0X)*=si=st—x；=0—0=0從而得到最優(yōu)解ェ:=0,xi=0?エ;=10最優(yōu)值為:200|O9.1I有一部貨車每天沿著公路給四個年轡店卸下6箱貨物,如果各零何店出仰該貨物所得利澗如表9—2所示,試求在各零售店卸下幾箱貨物,能使訣得的總利潤最大?其值是多少?*9-2?灣、、等會名こ123401234S604677770246891009S7S8a04s6666分析本題是一堆資源的分配問題,利用動態(tài)規(guī)劃的逆推關(guān)系式進行逐段計算.解將問題按零售店數(shù)分為4個階段,階段變量ん=1?2?3.4,第ん階段為第ん個零仔店分配貨物;狀態(tài)變量”表示分配給第ん至第4個零售店的貨物箱數(shù);決策變量ム表示分配給第え個零售店的貨物箱數(shù);狀態(tài)轉(zhuǎn)移方程=シーエ.,階段指標ん（4）表示將ち箱貨物分配給第ん個零售店的破利,最優(yōu)值嗔數(shù)ハ（ム）表示將シ箱貨物分配給第ん至第4個零售店的最大效利;r/*（?*）=max［ハ（エ?）+ル-1（ム7）］ノ=4.3,2,1遞推公式」 ーづ、1/5（町）=0計算過程如表9-3所示.

表9-3kPh/a4-1(“+i)ん（x*）+/*.+】（“+1〉ェf400000001140441225055233606634460664556066566606663000004010044130320055711347250530066921358254937074006611313692551037411480850066123,41369256113751248412580860066133,413692561137613485135841268080000000100444012022007770124624043009990,112792448