1、第一部分線性規(guī)劃問題的求解一、兩個(gè)變量的線性規(guī)劃問題的圖解法：概念準(zhǔn)備：定義：滿足所有約束條件的解為可行解；可行解的全體稱為可行（解）域。定義：達(dá)到目標(biāo)的可行解為最優(yōu)解。圖解法：圖解法采用直角坐標(biāo)求解：X1橫軸；X2豎軸。1、將約束條件（取等號(hào)）用直線繪出；2、確定可行解域；3、繪出目標(biāo)函數(shù)的圖形（等值線），確定它向最優(yōu)解的移動(dòng)方向；注：求極大值沿價(jià)值系數(shù)向量的正向移動(dòng)；求極小值沿價(jià)值系數(shù)向量的反向移動(dòng)。4、確定最優(yōu)解及目標(biāo)函數(shù)值。參考例題：（只要求下面這些有唯一最優(yōu)解的類型）例1:某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工所需的工時(shí)不同，

2、這些產(chǎn)品銷售后所能獲得利潤以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時(shí)數(shù)如下表所示：消設(shè)備ABC利潤'一耗'、（萬兀）產(chǎn)品甲35970乙95330啟效總工時(shí)540450720問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤為最大（此題也可用“單純形法”或化“對偶問題”用大M法求解）max z = 70X+30X2解：設(shè)XI、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量3x19x25405x15x24509x13x2720x1,x20、可行解域?yàn)閛abcd。，最優(yōu)解為b點(diǎn)由方程組.X*=5xi 5X24509x1 3x2720解出 x1=75, x2=15xix2(75, 1

3、5) T.maxz=Z=70x75+30x15=5700例3:用圖解法求解2x1乂210Xi乂28乂27xi,乂20、max z = 6x+4x2max z = 6 X2+4X6=36解:可行解域?yàn)閛abcd。，最優(yōu)解為b點(diǎn)由方程組.X*=XiX22x1x210x1x28(2,6)T解出xi=2,X2=6例5:用圖解法求解minz=-3xi+x2、x14x232x15x212x12x28x1,X20解:->(6)<-8可行解域?yàn)閎cdefb,最優(yōu)解為b點(diǎn)由方程組x142x15x212解出x1=4'x2=5.X*=x24(4,5)minz=-3X4+Z=1155二、標(biāo)準(zhǔn)型線性

4、規(guī)劃問題的單純形解法：一般思路：1、用簡單易行的方法獲得初始基本可行解；2、對上述解進(jìn)行檢驗(yàn)，檢驗(yàn)其是否為最優(yōu)解，若是，停止迭代，否則轉(zhuǎn)入3；3、根據(jù)0l規(guī)則確定改進(jìn)解的方向；4、根據(jù)可能改進(jìn)的方向進(jìn)行迭代得到新的解；5、根據(jù)檢驗(yàn)規(guī)則對新解進(jìn)行檢驗(yàn)，若是最優(yōu)解，則停止迭代，否則轉(zhuǎn)入3，直至最優(yōu)解。具體做法（可化歸標(biāo)準(zhǔn)型的情況）：設(shè)已知maxz=0x1+ax2+nxn.a11x1a12x2a21x1a22x2am1x1am2x2xj0，j對第i個(gè)方程加入松弛變量a11x1a12x2a21x1a22x2am1x1am2x2xj0，ja1nxna2nxnamnxn列表計(jì)算，格式、算法如下：2，xn+

5、i，i=1a1nxna2nxnamnxn2，b2bm2，m，得到xn1b1xn2b2xnmbmCbXbbC1C2Cn+mXn+melXiX2Cn+1xn+1b1ana12an+mCn+2.xn+2.b2.a21a22a2n+m.Cn+m.xn+m.bnam1am2amn+mZ1Z2Zn+ma1(T2,(Xn+mm注：Z=Cn+1aij+Cn+2a2j+.+Cn+mamj=cniaij,(j=1,2,n+m)i1(Tj=Cj-Zj，當(dāng)(TjW0時(shí)，當(dāng)前解最優(yōu)。注：由maxbj確定所對應(yīng)的行的變量為“入基變量”；由eL=min旦鼠0確定所對應(yīng)的行的變量為“出基變量”，行、列交iaik叉處為主元素，

6、迭代時(shí)要求將主元素變?yōu)?,此列其余元素變?yōu)?。例1：用單純形法求解(本題即是本資料P2“圖解法”例1的單純形解法；也可化”對偶問題”求解)maxz=70x+30x23x19x25405x15x24509x13x2720x1,x20解：加入松弛變量x3,x4,x5,得到等效的標(biāo)準(zhǔn)模型:maxz=70x+30x2+0x3+0%+0月3xi9x2X35405x15x2x44509x13x2x5720Xj0,j1,2,5列表計(jì)算如下*7030000CbXbbx1x2x3x4x5eL0x354039100540/3=1800x445055010450/5=900x5720(9)3001720/9=800

7、000070T300000x33000810-1/3300/8=0x4500(10/3)01-3950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3T0070/90x3180001-12/5130x2150103/10-1/670x175100-1/101/65700700300002-220/320/3X*=(75,15,180,0,0)T.maxz=70X75+30X15=5700例2：用單純形法求解maxz=7x1+12x29x14x23604x15x22003x110x2300x1，x20解：加入松弛變量x3，x4，x5，得到等效的

8、標(biāo)準(zhǔn)模型：maxz=7x1+12x2+0x3+0x4+0x59x14x2x33604x15x2x42003x110x2x5300xj0,j1,2,.,5列表計(jì)算如下：712000XbbX1X2X3X4X5el0X336094100360/4=900X420045010200/5=400X53003(10)001300/10=3000000712T0000X32407&10010-25240/78/10=2400/780X450(32)001-1/250/32=2012X2303101001/1030/310=10013512006/5175T0006/50X384001-78/2529

9、/257X1201002/5-1/512X2240103254/28428712034/2511/35000-34/2511/35X*=(20,24,84,0,0)T.maxz=7X20+12X24=428三、非標(biāo)準(zhǔn)型線性規(guī)劃問題的解法：1、一般地，對于約束條件組：若為公”，則加松弛變量，使方程成為“=”；若為，則減松弛變量，使方程成為一。我們在前面標(biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問題中遇到的是求極小值，則為非標(biāo)準(zhǔn)型?？勺魅缦绿幚恚河赡繕?biāo)函數(shù)minz=cjxj變成等價(jià)的目標(biāo)函數(shù)max(z)=(cjxj)jiji令一z=Z,.minz=maxz/2、等式約束一一大M法：通過加人工變量的

10、方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價(jià)值系數(shù)為M,M是很大的正數(shù)，從原理上理解又稱為“懲罰系數(shù)”。(課本P29)類型一:目標(biāo)函數(shù)仍為maxz,約束條件組w與=。例1：maxz=3x+5x2.x142x2123x12x218x1,x20解：加入松弛變量x3,x4,得到等效的標(biāo)準(zhǔn)模型：maxz=3x+5x2xix342x2x4123x12x218xj0,j1,2,3,4其中第三個(gè)約束條件雖然是等式，但因無初始解，所以增加一個(gè)人工變量乂5,得至U:maxz=3x+5x2Mx5x1x342x2x4123x12x2x518xj0,j1,2,5單純形表求解過程如下：CbXbb3Xi5X20X3

11、0X4MX5el0X34(1)01004/1=40X41202010MX5183200118/3=6-3M-2M00-M3M+3T5+2M0003Xi4101000X412020101Z2=6-MX560(2)-3016/2=33-2M3+3M0M05T-3-3M003X14101004/1=40X4600(3)1-16/3=25X23013201/23(23)=-9/2359/2032009/2T0M323Xi2100-1/31/30X320011/3-1/35X260101/203503213600032M1TX*= (2, 6, 2, 0).maxz=3X2+5X6=36類型二:目標(biāo)函數(shù)

12、minz,約束條件組n與=。例2:用單純形法求解minz=4x+3x2.2x14x2163xi2x212x1,x20解：減去松弛變量x3,x4,并化為等效的標(biāo)準(zhǔn)模型:maxZ=-4x13x2.2x14x2x3163x12x2x412xj0,j1,2,3,4增加人工變量拈、x6,得到：maxZ=-4x13x2Mx5Mx62x14x2x?x§163x12x2x4x612xj0,j1,2,6單純形表求解過程如下：Xbb一40X30X4MX5MX6elX1X2-MX5162(4)-1010164=4MX612320-101122=65M-6MMM-M-M5M46M3T-M-M00-3X241

13、/211/401/4041/2=8MX64(2)01/2-11/214/2=2-2M-J2-33/4-M/2MM/234一M2M-5/2t0M/234一M343M/20-3X2301381/438-1/4一4Xi2101/41/2-1/41/2-17一40-301/8-1/85454-1/8M+1/834-M+5/4X*=(2,3,0,0)T.minz=maxz/=(17)=17四、對偶問題的解法:什么是對偶問題1、在資源一定的條件下，作出最大的貢獻(xiàn)；2、完成給定的工作，所消耗的資源最少。引例（與本資料P2例1“圖解法”、P7例1“單純形法”同）：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品均需在A、B

14、、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工時(shí)需要不同的工時(shí)，這些產(chǎn)品售后所能獲得的利潤值以及這三種加工設(shè)備因各種條件下所能使用的有效總工時(shí)數(shù)如下表：設(shè)ABC利潤（萬元）消、備耗m甲35970乙95330啟效總工時(shí)540450720問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤為最大解:原問題設(shè)XI、X2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量maxz=70X+30X23xi9X25405xi5X24509x13x2720X1,x20將這個(gè)原問題化為它的對偶問題設(shè)yi、y2、y2分別為設(shè)備A、B、C單位工時(shí)數(shù)的加工費(fèi)。minw=540y1+450y2+720y3.3y15y29y3709y1

15、5y23y330yi0，i1，2，3用大M法，先化為等效的標(biāo)準(zhǔn)模型：maxw/=540y1450y2720y3.3y15y29y3y4709y15y23y3y530yj0,j1,2,.,5增加人工變量y6、y7，得到：maxz/=540y1450y2720y3My6My73y15y29y3y4y6709y15y23y3y5y730yj0,j1,2,.,5大M法單純形表求解過程如下：CbXbb540y1450y2720y30y40y5My6My7el-My670359-101070/3My730(9)530-10130/9=10/3-12M-10M-12MMM-M-M12M-540f10M-45

16、012M-720-M-M00My660010/3(8)-11/311/360/8=540yi10/31391/301/901/910/31/3=10-300+10/3M-8M-180-M-M/3+60-MM/3600-150+10/3M8M-540fMM/3-600M/3+60720y315/205/1211/81/241/8-1/2415/2/312=18540y1361(5/12)01/241/81/241/85/&312=2540572720135/247312135275/20125T0133247312135/2-M75/2M-720y320/3-1011/61/61/61/

17、6450y2212/5101/10-3/101/1031036045072075157515570018000751575M15-M.該對偶問題的最優(yōu)解是y*=(0,2,203,°，0)T最優(yōu)目標(biāo)函數(shù)值minw=(5700)=5700五、運(yùn)輸規(guī)劃問題:運(yùn)輸規(guī)劃問題的特殊解法一一“表上作業(yè)法”解題步驟:1、找出初始調(diào)運(yùn)方案。即在（mxn）產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格。（最小元素法）2、（對空格）求檢驗(yàn)數(shù)。判別是否達(dá)到最優(yōu)解。如已是最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)到下一步。（閉回路法）3、對方案進(jìn)行改善，找出新的調(diào)運(yùn)方案。（根據(jù)檢驗(yàn)結(jié)果選擇入基變量，用表上閉回路法調(diào)整一一即迭代計(jì)算，得新

18、的基本可行解）4、重復(fù)2、3,再檢驗(yàn)、再迭代，直到求得最優(yōu)調(diào)運(yùn)方案類型一:供求平衡的運(yùn)輸規(guī)劃問題（又稱“供需平衡”、“產(chǎn)銷平衡”）引例：某鋼鐵公司有三個(gè)鐵礦和四個(gè)煉鐵廠，鐵礦的年產(chǎn)礦石量分別為100萬噸、80萬噸和50萬噸，煉鐵廠年需礦石量分別為50萬噸、70萬噸、80萬噸解：用“表上作業(yè)法”求解先用最低費(fèi)用法（最小元素法）求此問題的初始基礎(chǔ)可行解:費(fèi)銷公BiB2B3B4SAi152067330-6510020X80xA708144420803020X30A3125332033251050x50xx銷量dj50708030230230Z=15X20+3X80+70X30+8X20+20X30+

19、3X50=3550（噸.公里）對的初始可行解進(jìn)行迭代（表上閉回路法），求最優(yōu)解:費(fèi)銷BiB2B3B4SAi1520143301210020X80XA7053814一92080X50X30A312320202510503020Xx銷量dj50708030230230用表上閉回路法調(diào)整后，從上表可看出，所有檢驗(yàn)數(shù)0,已得最優(yōu)解最優(yōu)方案:Z=15X20+3X80+8x50+20X30+12X30+3X20=1960（噸公里）解法分析：如何求檢驗(yàn)數(shù)并由此確定入基變量有數(shù)字的空格稱為“基格”、打x的空格稱為“空格”，標(biāo)號(hào)為偶數(shù)的頂點(diǎn)稱為偶點(diǎn)、標(biāo)號(hào)為奇數(shù)的頂點(diǎn)稱為奇點(diǎn)，出發(fā)點(diǎn)算0故為偶點(diǎn)。找出所有空格的閉

20、回路后計(jì)算它們的檢驗(yàn)數(shù)jGjGj,必須j00,才得到最優(yōu)奇點(diǎn)偶點(diǎn)解。否則，應(yīng)選所有中正的最大者對應(yīng)的變量xj為入基變量進(jìn)行迭代（調(diào)整）。檢驗(yàn)后調(diào)整運(yùn)輸方案的辦法是：在空格的閉回路中所有的偶點(diǎn)均加上奇點(diǎn)中的最小運(yùn)量，所有的奇點(diǎn)均減去奇點(diǎn)中的最小運(yùn)量。重復(fù)以上兩步，再檢驗(yàn)、再調(diào)整，直到求得最優(yōu)運(yùn)輸方案。類型二:供求不平衡的運(yùn)輸規(guī)劃問題若sidj，則是供大于求（供過于求）問題，可設(shè)一虛銷地Bn+1，令i1j1mnmncin+1=0，dn+1=sidj，轉(zhuǎn)化為產(chǎn)銷平衡問題。若sidj，則是供小于,i1j1i1j1nm求（供不應(yīng)求）問題，可設(shè)一虛產(chǎn)地Am+1，令cm+1j=0，sm+1=djsi，轉(zhuǎn),j

21、1i1化為產(chǎn)銷平衡問題。（,2,，m；,2,，n）六、工作指派問題：工作指派問題的數(shù)學(xué)模型假定有n項(xiàng)工作需要完成，恰好有n個(gè)人每人可去完成其中一項(xiàng)工作，效果要好。工作指派問題的特殊解法“匈牙利法”（考?。┙忸}步驟：1、使系數(shù)矩陣（效率矩陣）各行、各列出現(xiàn)零元素。作法：行約簡一系數(shù)矩陣各行元素減去所在行的最小元素，列約簡一再從所得矩陣的各列減去所在列最小元素。2、試求最優(yōu)解。如能找出n個(gè)位于不同行不同列的零元素，令對應(yīng)的xij=1，其余xij=0，得最優(yōu)解，結(jié)束；否則下一步。作法：由獨(dú)立0元素的行（列）開始，獨(dú)立0元素處畫（）標(biāo)記，在有（）的行列中劃去（也可打*）其它0元素；再在剩余的0元素中重

22、復(fù)此做法，直至不能標(biāo)記（）為止。3、作能覆蓋所有0元素的最少數(shù)直線集合。作法：對沒有（）的行打，號(hào)；對已打，號(hào)的行中所有0元素的所在列打，號(hào)；再對打有，號(hào)的列中0元素的所在行打，號(hào)；重復(fù)、直到得不出新的打，號(hào)的行（列）為止；對沒有打，號(hào)的行畫一橫線，對打，號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)。未被直線覆蓋的最小元素為cj,在未被直線覆蓋處減去cj,在直線交叉處加上cij。4、重復(fù)2、3，直到求得最優(yōu)解。類型一:求極小值的匈牙利法：（重點(diǎn)掌握這種基本問題）例1:有甲、乙、丙、丁四個(gè)人，要派去完成A、B、C、D四項(xiàng)工作，他們完成的工時(shí)如下表：任工ABCD時(shí)甲612134乙103121

23、4丙7141316丁881210試問：應(yīng)如何分配任務(wù)可使總工時(shí)為最少解：用“匈牙利法”求解。已知條件可用系數(shù)矩陣（效率矩陣）表示為:(Cij)610781213312141381241416行約簡10089097604DA B C2857(0)5(0)72* *00(0)(0)1192使總工時(shí)為最少的分配任務(wù)方案為:甲fD,乙-B,丙A,丁C此時(shí)總工時(shí)數(shù)W=4+3+7+12=26例2:求效率矩陣109785877的最優(yōu)解。546523451097解：587546234320032102012320032102012*32(0)0(0)321_1(0)20*所畫()0元素少于n,未*0122得到

24、最優(yōu)解，需要繼續(xù)變換矩陣(求能覆蓋所有0元素的最少數(shù)直線集合)32(0)31(0)*01*(0)021V*20未被直線覆蓋的最小元素為cij4，在未被直線覆蓋處減去1,在直線交叉處加上1標(biāo)號(hào)*、42(0)0420002102020*(0)210*，、202(0)0011* , 、0(0)110010100000010100類型二:求極大值的匈牙利法:minz=max(z)Mcij）=（bij），（cij）maxz=cijxij=(Mcij)xijijij(Mcij)xijcijxijijij第一部分到此結(jié)束第二部分動(dòng)態(tài)規(guī)劃只要求掌握動(dòng)態(tài)規(guī)劃的最短路問題用“圖上標(biāo)號(hào)法”解決：具體解題步驟請參看教材P103（這是本套資料少見的與教材完全相同的算法類型之一，務(wù)必看書掌握）學(xué)員們只有完全理解了這種作法（思路：逆向追蹤）才有可能做題，考試時(shí)數(shù)字無論如何變化都能作出正確求解！第二部分到此結(jié)束第三部分網(wǎng)絡(luò)分析一、求最小生成樹（最小支撐樹、最小樹）問題：破圈法一一任取一個(gè)圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個(gè)步驟，直到得到一個(gè)不含圈的圖為止，這時(shí)的圖便是最小樹。參考例題：例：求下圖的最小生成樹:解：用“破圈法”求得最小生成樹為:V3V5已