運籌學(xué)復(fù)習(xí)參考資料知識點及習(xí)題

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

2、設(shè)備上加工所需的工時不同，這些產(chǎn)品銷售后所能獲得利潤以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時數(shù)如下表所示：設(shè)消備產(chǎn) 品 耗ABC利潤（萬元）甲35970乙95330有效總工時540450720問：該廠應(yīng)如何組織生產(chǎn)， 即生產(chǎn)多少甲、 乙產(chǎn)品使得該廠的總利潤為最大？ 此題也可用“單純形法”或化“對偶問題”用大 M法求解）max z = 70x 1+30x2解：設(shè) x1、x2 為生產(chǎn)甲、乙產(chǎn)品的數(shù)量3x19x25405x15x24509x13x2720x1，x2 0、可行解域為 oabcd0，最優(yōu)解為 b 點由方程組解出 x1=75， x2=155x1 5x2 4509x1 3x2

3、720* x1 X*= x1 =（75，15）x2 max z =Z = 70 75+30 15=5700max z = 6x 1+4x2例 2：用圖解法求解2x1x210x1x28x27x1，x20、解：由方程組*x1X*=x2解出 x1=2， x2=62x1 x2 10 x1 x2 82，6)Tmax z = 6 2+46=36例 3：用圖解法求解min z = 3x1+x2解：x14x2 32x1 5x2 12x1 2x2 8x1， x2 0、最優(yōu)解為b 點?？尚薪庥驗閎cdefb ，由方程組x1 42x1 5x212解出 x1=4，x2=25X*=x1x244，45)41 min z

4、= 34+ = 1155、標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形解法： 一般思路：1、用簡單易行的方法獲得初始基本可行解；3；3，直2、對上述解進行檢驗，檢驗其是否為最優(yōu)解，若是，停止迭代，否則轉(zhuǎn)入3、根據(jù) L 規(guī)則確定改進解的方向；4、根據(jù)可能改進的方向進行迭代得到新的解；5、根據(jù)檢驗規(guī)則對新解進行檢驗，若是最優(yōu)解，則停止迭代，否則轉(zhuǎn)入 至最優(yōu)解。具體做法（可化歸 標(biāo)準(zhǔn)型 的情況）：設(shè)已知max z = c 1x1+ c 2x2+ c nxna11x1a12x2. a1n xnb1a21x1a22x2. a2nxnb2am1x1am2 x2. amnxnbmxj0，j1 ，2 ，.，n對第 i 個方程加

5、入松弛變量xn+i，i =1，2，m，得到a11x1a12x2. a1n xnxn 1b1a21x1a22x2. a2nxnxn 2b2am1x1am2 x2. amnxnxn mbmxj0，j1 ，2 ，.，n列表計算，格式、算法如下：CBXBbc1x1c2x2cn+mxn+mLcn+1xn+1b1a11a12a1 n+mc n+2xn+2b2a21a22a2 n+mcn+mxn+mbnam1am2am n+mz1z2zn+m1 2 n+mm注： zj =cn+1 a1j+ c n+2 a2j + c n+m amj= cn iaij ，（ j=1 ，2， n+m）i1j =cjzj ,當(dāng)j

6、 0 時，當(dāng)前解最優(yōu)。注： 由 maxj 確定所對應(yīng)的行的變量為“入基變量”；由 L=min bi aik 0 確定所對應(yīng)的行的變量為“出基變量”，行、列交i aik叉處為主元素，迭代時要求將主元素變?yōu)?1，此列其余元素變?yōu)?0。例 1：用單純形法求解 （本題即是本資料 P2“圖解法”例 1 的單純形解法 ；也可化“對偶 問題”求解）max z =70x 1+30x23x1 9x2 5405x1 5x2 4509x1 3x2 720x1， x2 0解：加入松弛變量 x3， x4，x5，得到等效的標(biāo)準(zhǔn)模型：max z =70x 1+30x2+0 x 3+0 x 4+0 x 53x19x2x354

7、05x15x2x4 4509x13x2x5 720xj0,j1,2,.,5X*=（75，15，180，0，0）列表計算如下：7030000CBXBbx1x2x3x4x5L0x354039100540/3 =1800x445055010450/5 =900x5720（9）3001720/9 =800000070300000x33000810- 1/3300/8 =0x4500（10/3 ）01- 5/950/10/3 =1570x18011/3001/980/1/3 =2407070/30070/9020/30070/90x318000112/5130x2150103/10- 1/670x175

8、100- 1/101/65700703002-220/300020/3Tmax z =70 75+30 15=5700例 2：用單純形法求解max z =7x 1+12x29x1 4x2 3604x1 5x2 2003x1 10x2 300x1， x2 0解：加入松弛變量 x3， x4，x5，得到等效的標(biāo)準(zhǔn)模型：max z =7x 1+12x2+0 x 3+0 x 4+0 x 59x14x2x33604x15x2x4 2003x110x2x5 300xj0, j1,2,.,5列表計算如下：712000CBXBbx1x2x3x4x5L0x336094100360/4 =900x420045010

9、200/5 =400x53003（10）001300/10 =30000007120000x324078/10010- 2/5240/78/10 =2400/780x450（5/2）001- 1/250/5/2 =2012x2303/101001/1030/3/10 =10018/512006/517/50006/50x38400178/2529/257x1201002/5- 1/512x224010 3/254/28428712034/2511/3500034/2511/35*TX*=（20，24，84，0，0）Tmax z =7 20+12 24=428三、非標(biāo)準(zhǔn)型線性規(guī)劃問題的解法：1、

10、一般地，對于約束條件組：若為“”，則加松弛變量，使方程成為“” ；若為“”，則減松弛變量，使方程成為“” 。我們在前面標(biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。如果在實際問題中遇到的是求極小值，則為 非標(biāo)準(zhǔn)型 ?？勺魅缦绿幚恚河赡繕?biāo)函數(shù) min z= cjxj 變成等價的目標(biāo)函數(shù) max（ z） = （ cj xj）j 1 j 1 /令 z=z ， min z= max z2、等式約束大 M法：通過加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。人工變量的價 值系數(shù)為 M， M是很大的正數(shù)，從原理上理解又稱為“懲罰系數(shù)” 。（課本 P29） 類型一 ：目標(biāo)函數(shù)仍為 max z，約束條件組與。例 1：

11、max z =3x 1+5x2x142x2 123x1 2x2 18x1， x2 0解：加入松弛變量 x3， x4，得到等效的標(biāo)準(zhǔn)模型：max z =3x 1+5x2x1 x3 42x2x4 123x1 2x218xj 0, j 1,2,3,4其中第三個約束條件雖然是等式，但因無初始解，所以增加一個人工變量x5，得到： max z =3x 1+5x2 Mx5x1 x3 42x2x4 12.3x1 2x2x5 18xj 0, j 1,2,.,5單純形表求解過程如下：3500MCBXBbx1x2x3x4x5L0x34（1）01004/1 =40x41202010Mx5183200118/3 =63

12、M2M00M3M352M0003x14101000x4120201012/2 =6Mx560（2）3016/2 =332M33M0M0533M003x14101004/1 =40x4600（3）116/3 =25x23013/201/23/（ 2/3） = 9/2359/205/2009/20M5/23x121001/31/30x320011/31/35x260101/203503/21360003/2M1TX=（2，6，2，0） max z =3 2+56=36類型二 ：目標(biāo)函數(shù) min z ，約束條件組與例 2：用單純形法求解min z =4x 1+3x22x1 4x2 163x1 2x2

13、 12x1， x2 0解：減去松弛變量 x3， x4，并化為等效的 標(biāo)準(zhǔn) 模型：max z/ = 4x1 3x22x1 4x2 x3 163x1 2x2 x4 12 xj 0, j 1,2,3,4增加人工變量 x5、x6，得到：max z/ = 4x1 3x2Mx5Mx62x1 4x2 x3x5 163x1 2x2x4x6 12xj 0, j 1,2,.,6單純形表求解過程如下：CBXBb40 x30 x4Mx5Mx6Lx1x2Mx5162（4）101016/4=4Mx61232010112/2=65M6MMMMM5M46M3MM003x241/211/401/404/1/2=8Mx64（2）

14、01/211/214/2=22M3/233/4 M/2MM/23/4M2M5/2 0M/23/4M3/4 3M/203x23013/81/43/81/44x12101/41/21/41/21740301/81/85/45/41/8 M1/8 5/4M5/4X*=(2，3，0，0)Tmin z = max z/ = ( 17) =17四、對偶問題的解法：什么是對偶問題？1、在資源一定的條件下，作出最大的貢獻；2、完成給定的工作，所消耗的資源最少。引例（與本資料 P2例1 “圖解法”、P7例1 “單純形法”同）：某工廠生產(chǎn)甲、乙兩種 產(chǎn)品，這些產(chǎn)品均需在 A、 B、 C三種不同的設(shè)備上加工，每種產(chǎn)

15、品在不同設(shè)備 上加工時需要不同的工時，這些產(chǎn)品售后所能獲得的利潤值以及這三種加工設(shè)設(shè) x1、 x2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量max z = 70x 1+30x23x19x25405x15x24509x13x2720x1，x2 0將這個原問題化為它的對偶問題設(shè) y1、y2、y2 分別為設(shè)備 A、B、C單位工時數(shù)的加工費。min w = 540y 1+450y2+720y33y1 5y2 9y3 709y1 5y2 3y3 30yi 0，i 1，2，3用大 M法，先化為等效的 標(biāo)準(zhǔn) 模型：max w/ = 540y1450y2 720y33y15y29y3y4709y15y23y3y5 30yj0,j

16、1,2,.,5增加人工變量 y6、y7，得到：max z/ = 540y1450y2720y3 My6My73y15y29y3y4y6 709y15y23y3y5y7 30yj0,j1,2,.,5大 M法單純形表求解過程如下：54045072000MMCBXBby1y2y3y4y5y6y7LMy670359101070/3M30/9=10/y730（9）530101312M10M12MMMMM12M54010M45012M 720MM00My660010/3（8）11/311/360/8=10/3/1/3540y110/315/91/301/901/9=10-300+10/3M-8M180M

17、M/3+60MM/3600-150+10/3M8M-540MM/3600M/3+6015/2/5/1720y315/205/1211/81/241/81/242=18(5/12 )5/6/5/12540y15/6101/241/81/241/8=2540572720 135/2475/12135/275/201250135/2475/12135/2 M75/2 M720y320/31011/61/61/61/6450y2212/5101/103/101/103/1036045072075157515570018000751575M15M該對偶問題的最優(yōu)解是y*=(0，2，20，0，0)T最優(yōu)目

18、標(biāo)函數(shù)值 min w = （ 5700） =5700五、運輸規(guī)劃問題：運輸規(guī)劃問題的特殊解法“ 表上作業(yè)法” 解題步驟：1、找出初始調(diào)運方案。即在 （mn） 產(chǎn)銷平衡表上給出 m+n-1個數(shù)字格。（最小元素法）2、（對空格）求檢驗數(shù)。判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一 步。（閉回路法）3、對方案進行改善，找出新的調(diào)運方案。 （根據(jù)檢驗結(jié)果選擇入基變量，用 表上閉回路法 調(diào) 整即迭代計算，得新的基本可行解）4、重復(fù) 2、 3，再檢驗、再迭代，直到求得最優(yōu)調(diào)運方案。 類型一：供求平衡的運輸規(guī)劃問題（又稱“供需平衡” 、“產(chǎn)銷平衡”） 引例：某鋼鐵公司有三個鐵礦和四個煉鐵廠，

19、 鐵礦的年產(chǎn)礦石量分別為 100萬噸、 80萬噸和 50萬噸，煉鐵廠年需礦石量分別為 50萬噸、 70萬噸、80 萬噸解：用“表上作業(yè)法”求解先用最低費用法 （最小元素法） 求此問題的初始基礎(chǔ)可行解：費銷產(chǎn) 地用地B1B2B3B4產(chǎn)量SiA1152067330 651002080A270814442080302030A312533203325 105050銷量 dj50708030230230初始方案：A350B2Z=1520+380+7030+820+2030+350=3550（噸.公里）對的初始可行解進行迭代 （表上閉回路法），求最優(yōu)解：費銷產(chǎn) 地用地B1B2B3B4產(chǎn)量SiA115201

20、4330 121002080A27053814920805030A312320 2025 10503020銷量 dj50708030230230用表上閉回路法調(diào)整后，從上表可看出，所有檢驗數(shù)0，已得最優(yōu)解最優(yōu)方案：20B1A130B1A3Z=1520+380+850+2030+1230+320=1960（噸.公里） 解法分析：如何求檢驗數(shù)并由此確定入基變量？有數(shù)字的空格稱為“基格” 、打的空格稱 為“空格”，標(biāo)號為偶數(shù)的頂點稱為偶點、 標(biāo)號為奇數(shù)的頂點稱為奇點， 出發(fā)點算 0 故為偶點。找出所有空格的閉回路后計算它們的檢驗數(shù) ijcijcij ，必須 ij 0，才得到最優(yōu)奇點 偶點解。否則，應(yīng)

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

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

23、元素；再在剩余的 0 元素中重復(fù)此做法， 直至不能標(biāo)記 （ ）為止。3、作能覆蓋所有 0 元素的最少數(shù)直線集合。作法： 對沒有 （ ）的行打號；對已打號的行中所有 0 元素的所在列打號； 再對打有號的列中 0 元素的所在行打號； 重復(fù)、直到得不出新的打號的行 （ 列） 為止；對沒有打號的行畫一橫線，對打號的列畫一縱線，這就得到覆蓋所有 0 元素的 最少直線數(shù)。未被直線覆蓋的最小元素為 cij ,在未被直線覆蓋處減去 cij , 在直線交叉處加 上 cij 。4、重復(fù) 2、 3，直到求得最優(yōu)解。類型一：求極小值的匈牙利法： （重點掌握這種基本問題）例 1：有甲、乙、丙、丁四個人，要派去完成 A、

24、 B、 C、D四項工作，他們解：用“匈牙利法”求解已知條件可用系數(shù)矩陣（效率矩陣）表示為6121342890行約簡列約簡103121470911(cij）=7714131607698812100042ABCD2850甲285(0)70511標(biāo)號乙7 (0)5110729丙(0)7290002丁0*0*(0)2使總工時為最少的分配任務(wù)方案為： 甲 D，乙 B，丙 A，丁 C 此時總工時數(shù) W=4+3+7+12=26例 2：求效率矩陣10 9 7的最優(yōu)解587546解：10 95854行約簡203202列約簡3200321 0 20 1 2標(biāo)號3(0)10*23(0)1(0) 02120* 所畫(

25、) 0 元素少于 n，未22得到最優(yōu)解，需要繼續(xù)變換矩陣 (求能覆蓋所有 0 元素的最少數(shù)直線集合)未被直線覆蓋的最小元素為 cij=1 , 在未被直線覆蓋處減去 1, 在直線交叉處加上標(biāo)號 *4 2 (0)0*42000210202000111。(0) 2 1 02 0* 2 (0) 0* (0) 1 1得最優(yōu)解：0001類型二：求極大值的匈牙利法：min z= max( z)cij ）（ M cij ）=（ bij ），（ cij ）中最大的元素為 Mmax z=cij xij = (M cij )xiji j i j(Mcij )xij jicij xij j第一部分到此結(jié)束第二部分 動

26、態(tài)規(guī)劃只要求掌握 動態(tài)規(guī)劃的 最短路問題用“ 圖上標(biāo)號法 ”解決：具體解題步 驟請參看教材 P103（這是本套資料少見的與教材完全相同的算法類型之一，務(wù) 必看書掌握）學(xué)員們只有完全理解了這種作法（思路： 逆向追蹤）才有可能做題，考試時數(shù)字無論如 何變化都能作出正確求解！第二部分到此結(jié)束第三部分 網(wǎng)絡(luò)分析一、求最小生成樹 （最小支撐樹、最小樹） 問題：破圈法 任取一個圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條 以上的邊都是權(quán)最大的邊，則任意去掉其中一條） 。在余下的圖中，重復(fù)這個步 驟，直到得到一個不含圈的圖為止，這時的圖便是最小樹。參考例題：例：求下圖的最小生成樹：v210v6v3v5解：用“破圈法”求得最小生成樹為：v3v5v6已得最小樹，此時權(quán) w=1+2+4+5+9=2