運(yùn)籌學(xué)期末考試復(fù)習(xí)資料

1、1. 最小費(fèi)用最大流例1 求下圖所示網(wǎng)絡(luò)中的最小費(fèi)用最大流，弧旁的權(quán)是（bij,cij）.解：（1）取初始可行流為零流f(0)=0,構(gòu)造賦權(quán)有向圖M(f(0),求出從vs到vt的最短路(vs,v2,v1,vt),如下圖中雙箭頭所示。（2）在原網(wǎng)絡(luò)D中，與這條最短路相對(duì)應(yīng)的增廣鏈為=（vs,v2,v1,vt）。（3）在上對(duì)f(0)=0進(jìn)行調(diào)整，取=5，得到新可行流f(1)，如下圖所示。按照以上的算法，依次類推，可以得到f(1)，f(2)，f(3)，f(4)，流量分別為5，7，10，11，并且分別構(gòu)造相對(duì)應(yīng)的賦權(quán)有向圖 M(f(1),(Mf(2),(Mf(3),(Mf(4) 由于在Mf(4)中已經(jīng)

2、不存在從vs到vt的最短路，因此，可行流f(4)，v(f(1)=11是最小費(fèi)用最大流。 2. 靈敏度分析（1）資源數(shù)量br變化的分析 最優(yōu)單純形表如下 這里B=求b2的增量Dbr變化范圍：所以b2的增量Dbr變化范圍是-8，16，顯然b2的變化范圍是8，32。（2）目標(biāo)函數(shù)中價(jià)值系數(shù)cj的變化分析1）非基變量對(duì)應(yīng)的價(jià)值系數(shù)的靈敏度分析例 Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0 求C3的變化范圍？解：最優(yōu)單純形表從表中看到可得到c3 9/5 時(shí)，c3 -

3、4+9/5=-11/5原最優(yōu)解不變。2） 基變量對(duì)應(yīng)的價(jià)值系數(shù)的靈敏度分析例 Max z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0解：下表為最優(yōu)單純形表,考慮基變量系數(shù)c2發(fā)生變化j=cj-(c1×a1j+c5 × a5j+(c2+c2)×a2j)j=3,4可得到 -3c21時(shí)，原最優(yōu)解不變。（3） 增加一個(gè)約束3.割平面法例：用割平面法求解數(shù)規(guī)劃問(wèn)題Cj1100CBXBbx1x2x3x40x3621

4、100x4204501Z1100CBXBbx1x2x3x41 x15/3105/61/61x28/3012/31/3Z-13/3001/61/6在松弛問(wèn)題最優(yōu)解中，x1, x2 均為非整數(shù)解，由上表有：將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和 以上式子只須考慮一個(gè)即可，解題經(jīng)驗(yàn)表明，考慮式子右端最大真分?jǐn)?shù)的式子，往往會(huì)較快地找到所需割平面約束條件。以上兩個(gè)式子右端真分?jǐn)?shù)相等，可任選一個(gè)考慮?，F(xiàn)選第二個(gè)式子，并將真分?jǐn)?shù)移到右邊得： 引入松弛變量s1 后得到下式，將此約束條件加到上表中，繼續(xù)求解。 Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x

5、28/3012/31/300s12/3001/31/31Z13/3001/61/60Cj11000CBXBbx1x2x3x4s11 x15/3105/61/601x28/3012/31/300s12/3001/31/31Z13/3001/61/60 得到整數(shù)最優(yōu)解，即為整數(shù)規(guī)劃的最優(yōu)解，而且此整數(shù)規(guī)劃有兩個(gè)最優(yōu)解： X= (0, 4), Z = 4, 或 X= (2, 2), Z = 4。4. 分支定界法例：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）記為（IP） 解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問(wèn)題記為（LP）用圖解法求（LP）的最優(yōu)解，如圖所示。 x118/11, x2 =

6、40/11 Z(0) =218/11(19.8)即Z 也是（IP）最小值的下限。對(duì)于x118/111.64，取值x1 1， x1 2對(duì)于x2 =40/11 3.64，取值x2 3 ，x2 4先將（LP）劃分為（LP1）和（LP2）,取x1 1, x1 2有下式： 現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。先求（LP1）,如圖所示。此時(shí)B 在點(diǎn)取得最優(yōu)解。 x11, x2 =3, Z(1)16找到整數(shù)解，問(wèn)題已探明，此枝停止計(jì)算。同理求（LP2） ,如圖所示。在C 點(diǎn)取得最優(yōu)解。即x12, x2 =10/3, Z(2) 56/318.7 Z2 < Z116 原問(wèn)題有比（16）更小的最

7、優(yōu)解，但 x2 不是整數(shù)，故利用3 10/34 加入條件。 加入條件： x23, x24 有下式： 只要求出（LP3）和（LP4）的最優(yōu)解即可。先求（LP3）,如圖所示。此時(shí)D 在點(diǎn)取得最優(yōu)解。即 x112/52.4, x2 =3, Z(3)-87/5-17.4<Z-19.8但x112/5不是整數(shù)，可繼續(xù)分枝。即 x12, x13 。求（LP4），如圖所示。無(wú)可行解，不再分枝。 在（LP3）的基礎(chǔ)上繼續(xù)分枝。加入條件x12, x13有下式： 只要求出（LP5）和（LP6）的最優(yōu)解即可。先求（LP5）,如圖所示。此時(shí)E 在點(diǎn)取得最優(yōu)解。即 x12, x2 =3, Z(5)17找到整數(shù)解，問(wèn)

8、題已探明，此枝停止計(jì)算。求（LP6），如圖所示。此時(shí) F在點(diǎn)取得最優(yōu)解。x13, x2 =2.5, Z(6)31/215.5 > Z(5) 如對(duì) Z(6) 繼續(xù)分解，其最小值也不會(huì)低于15.5 ，問(wèn)題探明,剪枝。 至此，原問(wèn)題（IP）的最優(yōu)解為：x1=2，x2 =3, Z* = Z(5) =-17以上的求解過(guò)程可以用一個(gè)樹形圖表示如右： 5. 貝葉斯例：某石油鉆探隊(duì)準(zhǔn)備在一遠(yuǎn)景區(qū)勘探石油，根據(jù)預(yù)測(cè)估計(jì)鉆井出油的概率為0.3，可以自己鉆探或是出租。 自己鉆探的費(fèi)用為1000萬(wàn)元，出油可收入4000萬(wàn)元； 如果出租，租金為200萬(wàn)元，若有油租金再增加100萬(wàn)元。為獲更多情報(bào)，可以先做地震試驗(yàn)

9、，再行決策。地震試驗(yàn)將有油區(qū)勘測(cè)為封閉構(gòu)造的概率為0.8；將無(wú)油區(qū)勘測(cè)為開放構(gòu)造的概率為0.6。地震試驗(yàn)費(fèi)為100萬(wàn)元。試用決策樹法進(jìn)行決策。由題意知，有油事件q1的概率P(1)=0.3，無(wú)油事件q2的概率P(2)=0.7，這是先驗(yàn)概率；后驗(yàn)概率則是封閉構(gòu)造而有油的概率P(1|I1)=0.8，開放構(gòu)造而無(wú)油的概率 P(2|I2)=0.4。6. 大M法例： 標(biāo)準(zhǔn)化 單純形表cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x711311-4-2-2101211000-10010001j3-6M-1+M-1+3M0-M000-M-1x4x6x3101130-2-21

10、00011000-10010-1-21j1-1+M00-M0-3M+10-1-1x4x2x3121130-2010001100-2-10210-5-21j1000-10-3M+13-1-1x1x2x34191000100011/302/3-2/3-1-4/32/314/3-5/3-2-7/3j000-1/3-1/3-M+1/3-M+2/3最優(yōu)值和最優(yōu)解 X*=（4，1，9，0，0）T，x6*=x7*=0； z*=2。7. 互補(bǔ)松弛性定理例：原問(wèn)題 的最優(yōu)解為X*=（0，0，4，4）T。試?yán)没パa(bǔ)松弛定理求對(duì)偶問(wèn)題最優(yōu)解。解：先寫出對(duì)偶問(wèn)題求解，Y*=（6/5，1/5，0），z*=w*=28。8

11、. 根據(jù)原問(wèn)題最優(yōu)表寫出對(duì)偶問(wèn)題的最優(yōu)解和最優(yōu)值例：原問(wèn)題 已知它的最優(yōu)表，求對(duì)偶最優(yōu)解。Cj1018000CBxBbx1x2x3x4x50x3540/7001-23/711/710x150/71005/7-3/718x2200/7010-1/72/7-Z-4100/7000-32/7-6/7解：寫出對(duì)偶問(wèn)題 計(jì)算步驟 原問(wèn)題的初始單純形表中的基變量的技術(shù)系數(shù)-最終單純形表中的檢驗(yàn)數(shù)即 y1*=0-0=0, y2*=0-(-32/7)=32/7, y3*=0-(-6/7)=6/7 則Y*=（0 ，32/7，6/7），W=4100/79. 目標(biāo)規(guī)劃某廠生產(chǎn)A、B、C三種產(chǎn)品，裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品時(shí)的工時(shí)消耗分別為6、8、10小時(shí)，生產(chǎn)線每月正常工作時(shí)間為200小時(shí)；三種產(chǎn)品銷售后，每臺(tái)可獲利分別為500