《運(yùn)籌學(xué)》復(fù)習(xí)參考資料知識點(diǎn)和習(xí)題

./第一部分線性規(guī)劃問題的求解一、兩個(gè)變量的線性規(guī)劃問題的圖解法：㈠概念準(zhǔn)備：定義：滿足所有約束條件的解為可行解；可行解的全體稱為可行〔解域。定義：達(dá)到目標(biāo)的可行解為最優(yōu)解。㈡圖解法：圖解法采用直角坐標(biāo)求解：x1——橫軸；x2——豎軸。1、將約束條件〔取等號用直線繪出；2、確定可行解域；3、繪出目標(biāo)函數(shù)的圖形〔等值線,確定它向最優(yōu)解的移動方向；注：求極大值沿價(jià)值系數(shù)向量的正向移動；求極小值沿價(jià)值系數(shù)向量的反向移動。4、確定最優(yōu)解及目標(biāo)函數(shù)值。㈢參考例題：〔只要求下面這些有唯一最優(yōu)解的類型例1：某廠生產(chǎn)甲、乙兩種產(chǎn)品,這兩種產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工,每種產(chǎn)品在不同設(shè)備上加工所需的工時(shí)不同,這些產(chǎn)品銷售后所能獲得利潤以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時(shí)數(shù)如下表所示：品產(chǎn)耗消備設(shè)品產(chǎn)耗消備設(shè)ABC利潤〔萬元甲乙3599537030有效總工時(shí)540450720——問：該廠應(yīng)如何組織生產(chǎn),即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤為最大？〔此題也可用"HYPERLINK單純形法"或化"HYPERLINK對偶問題"用大M法求解解：設(shè)x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。⑴maxz=70x1+30x⑴⑵⑵⑸、⑹⑸、⑹⑷⑶可行解域?yàn)閛abcd0,最優(yōu)解為b點(diǎn)。由方程組解出x1=75,x2=15∴X*==〔75,15T∴maxz=Z*=70×75+30×15=5700例2：用圖解法求解⑴maxz=6x1+4x⑴⑵⑵⑸、⑹⑸、⑹⑷⑶解：可行解域?yàn)閛abcd0,最優(yōu)解為b點(diǎn)。由方程組解出x1=2,x2=6∴X*==〔2,6T∴maxz=6×2+4×6=36例3：用圖解法求解⑴minz=－3x1+x⑴s.t.⑵⑵⑶⑷⑸⑹、⑺解：可行解域?yàn)閎cdefb,最優(yōu)解為b點(diǎn)。由方程組解出x1=4,x2=∴X*==〔4,T∴minz=－3×4+=－11二、標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形解法：㈠一般思路：1、用簡單易行的方法獲得初始基本可行解；2、對上述解進(jìn)行檢驗(yàn),檢驗(yàn)其是否為最優(yōu)解,若是,停止迭代,否則轉(zhuǎn)入3；3、根據(jù)θL規(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=c1x1+c2x2+…+cnxns.t.對第i個(gè)方程加入松弛變量xn+i,i=1,2,…,m,得到列表計(jì)算,格式、算法如下：CBXBbc1c2…cn+mθLx1x2…xn+mcn+1xn+1b1a11a12…a1n+mcn+2xn+2b2a21a22…a2n+m…………cn+mxn+mbnam1am2…amn+mz1z2…zn+mσ1σ2…σn+m注①：zj=cn+1a1j+cn+2a2j+…+cn+mamj=,〔j=1,2,…,σj=cj－zj,當(dāng)σj≤0時(shí),當(dāng)前解最優(yōu)。注②：由max{σj}確定所對應(yīng)的行的變量為"入基變量"；由θL=確定所對應(yīng)的行的變量為"出基變量",行、列交叉處為主元素,迭代時(shí)要求將主元素變?yōu)?,此列其余元素變?yōu)?。例1：用單純形法求解〔本題即是本資料P2"HYPERLINK圖解法"例1的單純形解法；也可化"HYPERLINK對偶問題"求解maxz=70x1+30x2s.t.解：加入松弛變量x3,x4,x5,得到等效的標(biāo)準(zhǔn)模型：maxz=70x1+30x2+0x3+0x4+0x5s.t.列表計(jì)算如下：CBXBb7030000θLx1x2x3x4x50x354039100540/3=1800x445055010450/5=900x5720〔93001720/9=800000070↑300000x33000810-1/3300/8=37.50x4500〔10/301-5/950/10/3=1570x18011/3001/980/1/3=2407070/30070/9020/3↑00－70/90x3180001－12/5130x2150103/10-1/670x175100-1/101/6570070300220/3000-2－20/3∴X*=〔75,15,180,0,0T∴maxz=70×75+30×15=5700例2：用單純形法求解maxz=7x1+12x2s.t.解：加入松弛變量x3,x4,x5,得到等效的標(biāo)準(zhǔn)模型：maxz=7x1+12x2+0x3+0x4+0x5s.t.列表計(jì)算如下：CBXBb712000θLx1x2x3x4x50x336094100360/4=900x420045010200/5=400x53003〔10001300/10=3000000712↑0000x324078/10010-2/5240/78/10=2400/780x450〔5/2001-1/250/5/12x2303/101001/1030/3/18/512006/517/5↑000－6/50x384001－78/2529/257x1201002/5-1/512x224010－3/254/28428712034/2511/35000－34/25－11/35∴X*=〔20,24,84,0,0T∴maxz=7×20+12×24=428三、非標(biāo)準(zhǔn)型線性規(guī)劃問題的解法：1、一般地,對于約束條件組：若為"≤",則加松弛變量,使方程成為"＝"；若為"≥",則減松弛變量,使方程成為"＝"。我們在前面標(biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實(shí)際問題中遇到的是求極小值,則為非標(biāo)準(zhǔn)型?？勺魅缦绿幚恚河赡繕?biāo)函數(shù)minz=變成等價(jià)的目標(biāo)函數(shù)max〔－z=令－z=z/,∴minz=－maxz/2、等式約束——大M法：通過加人工變量的方法,構(gòu)造人造基,從而產(chǎn)生初始可行基。人工變量的價(jià)值系數(shù)為－M,M是很大的正數(shù),從原理上理解又稱為"懲罰系數(shù)"?！舱n本P29類型一：目標(biāo)函數(shù)仍為maxz,約束條件組≤與＝。例1：maxz=3x1+5x2s.t.解：加入松弛變量x3,x4,得到等效的標(biāo)準(zhǔn)模型：maxz=3x1+5x2s.t.其中第三個(gè)約束條件雖然是等式,但因無初始解,所以增加一個(gè)人工變量x5,得到：maxz=3x1+5x2－Mx5s.t.單純形表求解過程如下：CBXBb3500－MθLx1x2x3x4x50x34〔101004/1=40x41202010——－Mx5183200118/3=6－3－200－M3M＋35＋20003x1410100——0x4120201012/2=6－Mx560〔2－3016/2=33－23＋30－M05↑－3－3003x14101004/1=40x4600〔31－16/3=25x2301－3/201/23/<－2/3>=－9/235－9/205/2009/2↑0－M－5/2305x12100－1/31/3x320011/3－1/3x260101/20363503/21000－3/2－M－1∴X*=〔2,6,2,0T∴maxz=3×2+5×6=36類型二：目標(biāo)函數(shù)minz,約束條件組≥與＝。例2：用單純形法求解minz=4x1+3x2s.t.解：減去松弛變量x3,x4,并化為等效的標(biāo)準(zhǔn)模型：maxz/=－4x1－3x2s.t.增加人工變量x5、x6,得到：maxz/=－4x1－3x2－Mx5－Mx6s.t單純形表求解過程如下：CBXBb－400－M－MθLx1x2x3x4x5x6－Mx5162〔4－101016/4=4－Mx612320－10112/2=6－5－6MM－M－M5M－6M－3－M－M00－3x241/21－1/401/404/1/2=8－Mx64〔201/2－1－1/214/2=2－2M－33/4－M/2MM/2－3/4－M2M－5/20M/2－3/4－M3/4－3M0－3x2301－3/81/43/8－1/4－4x12101/4－1/2－1/41/2－17－4－31/85/4－1/8－5/400－1/8－5/4－M＋1/8－M＋5/4∴X*=〔2,3,0,0T∴minz=－maxz/=－〔－17=17四、對偶問題的解法：什么是對偶問題？1、在資源一定的條件下,作出最大的貢獻(xiàn)；2、完成給定的工作,所消耗的資源最少。引例〔與本資料P2例1"HYPERLINK圖解法"、P7例1"HYPERLINK單純形法"同：某工廠生產(chǎn)甲、乙兩種產(chǎn)品,這些產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工,每種產(chǎn)品在不同設(shè)備上加工時(shí)需要不同的工時(shí),這些產(chǎn)品售后所能獲得的利潤值以及這三種加工設(shè)備因各種條件下所能使用的有效總工時(shí)數(shù)如下表：品產(chǎn)耗消備設(shè)品產(chǎn)耗消備設(shè)ABC利潤〔萬元甲乙3599537030有效總工時(shí)540450720——問：該廠應(yīng)如何組織生產(chǎn),即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤為最大？解：原問題——設(shè)x1、x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。maxz=70x1+30x2s.t.將這個(gè)原問題化為它的對偶問題——設(shè)y1、y2、y2分別為設(shè)備A、B、C單位工時(shí)數(shù)的加工費(fèi)。minw=540y1+450y2+720y3s.t.用大M法,先化為等效的標(biāo)準(zhǔn)模型：maxw/=－540y1－450y2－720y3s.t.增加人工變量y6、y7,得到：maxz/=－540y1－450y2－720y3－My6－My7s.t大M法單純形表求解過程如下：CBXBb－540－450－72000－M－MθLy1y2y3y4y5y6y7－My670359－101070/3－My730〔9530－10130/9=10/3－12－10－12MM－M－M12M－54010M－4512M－72－M－M00－My660010/3〔8－11/31－1/360/8=2.5－540y110/315/91/30－1/901/910/3/1/3=10-300+10/3-8M－－M－M/3+60－MM/3－600-150+10/38M-540MM/3－600－M/3+60－720y315/205/121－1/81/241/8－1/2415/2/5/12=18－540y15/61〔5/1201/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720－450y320/3－1011/61/61/6－1/6y2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴該對偶問題的最優(yōu)解是y*=〔0,2,,0,0T最優(yōu)目標(biāo)函數(shù)值minw=－〔－5700=5700五、運(yùn)輸規(guī)劃問題：運(yùn)輸規(guī)劃問題的特殊解法——"表上作業(yè)法"解題步驟：1、找出初始調(diào)運(yùn)方案。即在<m×n>產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字格?！沧钚≡胤?、〔對空格求檢驗(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ì)算,得新的基本可行解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萬噸和30萬噸,這三個(gè)鐵礦與四個(gè)煉鐵廠的距離如下：礦鐵廠鐵離距煉礦鐵廠鐵離距煉B1B2B3B4A1A2A3152033070814201232015問：該公司應(yīng)如何組織運(yùn)輸,既滿足各煉鐵廠需要,又使總的運(yùn)輸費(fèi)用為最小〔按噸.公里計(jì)？解：用"表上作業(yè)法"求解。⑴先用最低費(fèi)用法〔最小元素法求此問題的初始基礎(chǔ)可行解：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4產(chǎn)量

SiA11520－67330－6510020×80×A2708144420803020×30A312533203325－1050×50××銷量dj50708030230230∴初始方案：B2B2203030B1B3A22080B1B3A1BB250A3Z=15×20+3×80+70×30+8×20+20×30+3×50=3550〔噸.公里⑵對⑴的初始可行解進(jìn)行迭代〔表上閉回路法,求最優(yōu)解：地產(chǎn)用費(fèi)地銷地產(chǎn)用費(fèi)地銷B1B2B3B4產(chǎn)量

SiA11520－14330－1210020×80×A270－53814－92080×50×30A312320－2025－10503020××銷量dj50708030230230用表上閉回路法調(diào)整后,從上表可看出,所有檢驗(yàn)數(shù)σ＜0,已得最優(yōu)解?！嘧顑?yōu)方案：3020B3020B1B2A35030B2B4A22080B1B3A1Z=15×20+3×80+8×50+20×30+12×30+3×20=1960〔噸.公里解法分析：①如何求檢驗(yàn)數(shù)并由此確定入基變量？有數(shù)字的空格稱為"基格"、打×的空格稱為"空格",標(biāo)號為偶數(shù)的頂點(diǎn)稱為偶點(diǎn)、標(biāo)號為奇數(shù)的頂點(diǎn)稱為奇點(diǎn),出發(fā)點(diǎn)算0故為偶點(diǎn)。找出所有空格的閉回路后計(jì)算它們的檢驗(yàn)數(shù),必須≤0,才得到最優(yōu)解。否則,應(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ī)劃問題若,則是供大于求〔供過于求問題,可設(shè)一虛銷地Bn+1,令ci,n+1=0,dn+1=,轉(zhuǎn)化為產(chǎn)銷平衡問題。若,則是供小于求〔供不應(yīng)求問題,可設(shè)一虛產(chǎn)地Am+1,令cm+1,j=0,sm+1=,轉(zhuǎn)化為產(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元素中重復(fù)此做法,直至不能標(biāo)記〔為止。3、作能覆蓋所有0元素的最少數(shù)直線集合。作法：①對沒有〔的行打√號；②對已打√號的行中所有0元素的所在列打√號；③再對打有√號的列中0元素的所在行打√號；④重復(fù)②、③直到得不出新的打√號的行<列>為止；⑤對沒有打√號的行畫一橫線,對打√號的列畫一縱線,這就得到覆蓋所有0元素的最少直線數(shù)。⑥未被直線覆蓋的最小元素為cij,在未被直線覆蓋處減去cij,在直線交叉處加上cij。4、重復(fù)2、3,直到求得最優(yōu)解。類型一：求極小值的匈牙利法：〔重點(diǎn)掌握這種基本問題例1：有甲、乙、丙、丁四個(gè)人,要派去完成A、B、C、D四項(xiàng)工作,他們完成的工時(shí)如下表：人務(wù)時(shí)工任人務(wù)時(shí)工任ABCD甲乙丙丁61213410312147141316881210試問：應(yīng)如何分配任務(wù)可使總工時(shí)為最少？解：用"匈牙利法"求解。已知條件可用系數(shù)矩陣〔效率矩陣表示為：列約簡行約簡〔cij=列約簡行約簡ABCDABCD標(biāo)號甲乙丙丁標(biāo)號甲乙丙丁∴使總工時(shí)為最少的分配任務(wù)方案為：甲→D,乙→B,丙→A,丁→C此時(shí)總工時(shí)數(shù)W=4+3+7+12=26例2：求效率矩陣的最優(yōu)解。列約簡行約簡解：列約簡行約簡標(biāo)號所畫〔0元素少于n,未得到最優(yōu)解,需要繼續(xù)變換矩陣〔求能覆蓋所有0元素的最少數(shù)直線集合：標(biāo)號√√√√√√未被直線覆蓋的最小元素為cij=1,在未被直線覆蓋處減去1,在直線交叉處加上1。標(biāo)號標(biāo)號∴得最優(yōu)解：類型二：求極大值的匈牙利法：minz=－max〔－z〔cij→〔M－cij=〔bij,〔cij中最大的元素為Mmaxz===－HYPERLINK第一部分到此結(jié)束第二部分動態(tài)規(guī)劃只要求掌握動態(tài)規(guī)劃的最短路問題——用"圖上標(biāo)號法"解決：具體解題步驟請參看教材P103〔這是本套資料少見的與教材完全相同的算法類型之一,務(wù)必看書掌握學(xué)員們只有完全理解了這種作法〔思路：逆向追蹤才有可能做題,考試時(shí)數(shù)字無論如何變化都能作出正確求解！HYPERLINK第二部分到此結(jié)束第三部分網(wǎng)絡(luò)分析一、求最小生成樹〔最小支撐樹、最小樹問題：破圈法——任取一個(gè)圈,從圈中去掉一條權(quán)最大的邊〔如果有兩條或兩條以上的邊都是權(quán)最大的邊,則任意去掉其中一條。在余下的圖中,重復(fù)這個(gè)步驟,直到得到一個(gè)不含圈的圖為止,這時(shí)的圖便是最小樹。參考例題：例：求下圖的最小生成樹：6767941510v2v1v3v5v4v632899415v2v1