運(yùn)籌學(xué)補(bǔ)考復(fù)習(xí)知識(shí)點(diǎn)歸納及樣題

1、文檔編碼 : CO5C7W2P1B2 HF7K1D6J8N10 ZP3I7A6Y1X4運(yùn)籌學(xué)補(bǔ)考復(fù)習(xí)學(xué)問(wèn)點(diǎn)歸納及樣題 總體要求：1、2 小時(shí),閉卷考試；2、只需帶黑色簽字筆、鉛筆、橡皮,不要帶書(shū)包、紙來(lái)；繪圖部分可以用鉛筆,其余 部分不得用鉛筆、圓珠筆答題；3、五道題目, 每題 20 分,每題小問(wèn)可能包含運(yùn)算、解題步驟不規(guī)范、說(shuō)明不清楚要扣分；簡(jiǎn)答、 填空、作圖；比照樣題答題,4、以下給出的全部是樣題,而不是原題；需要你比照樣題復(fù)習(xí)、把握課件中講過(guò)的所有學(xué)問(wèn)點(diǎn)；樣題中不行能將全部考點(diǎn)都告知你；填空填寫(xiě)運(yùn)算表達(dá)式而非公式；5、考試時(shí)間和地點(diǎn)：開(kāi)學(xué)的第一周,地點(diǎn)等候通知；6、考試無(wú)須帶運(yùn)算器,但你

2、自己仍是需要有確定的筆算才能；7、遵守考試紀(jì)律,作弊嚴(yán)懲不貸；一、線性規(guī)劃之“ 運(yùn)輸問(wèn)題” 的建模與求解1、樣題：已知某運(yùn)輸問(wèn)題其供銷關(guān)系及單位運(yùn)價(jià)、各產(chǎn)地產(chǎn)量、各銷地銷量如表 1 所示,問(wèn)如何調(diào)運(yùn)物品,使得總運(yùn)輸費(fèi)用（單位：百元 / 萬(wàn)件）最??？表 1 產(chǎn)銷平穩(wěn)表和單位運(yùn)價(jià)表銷地 Bj B1 B2 B3 產(chǎn)量（萬(wàn)件）產(chǎn)地 Ai A1 4 2 5 8 A2 3 5 3 7 A3 1 3 3 4 銷量（萬(wàn)件）4 8 5 要求：（1）請(qǐng)建立該問(wèn)題的線性規(guī)劃模型；（2）假如有必要再化為標(biāo)準(zhǔn)問(wèn)題；（3）用表上作業(yè)法求解：用最小元素法確定初始方案（假如每一步劃線之初同時(shí)有多個(gè)最小運(yùn)價(jià)元素, 請(qǐng)從行、 列

3、標(biāo)號(hào)最小的元素開(kāi)頭進(jìn)行支配；假如未進(jìn)行到最終一步但需要補(bǔ)充；0 元素作為基變量, 請(qǐng)加在與該剩余最小元素所畫(huà)十字線上運(yùn)價(jià)最小且未支配運(yùn)量的位置）用閉回路法或者位勢(shì)法驗(yàn)證初始方案是否最優(yōu)？假如非最優(yōu),請(qǐng)用閉回路法調(diào)整 （假如調(diào)整后得到多個(gè)0 元素,將對(duì)應(yīng)運(yùn)價(jià)最小的0 元素保留為基變量） ,直至求出最優(yōu)方案；解：（1）設(shè)從產(chǎn)地Ai 調(diào)運(yùn)到銷地Bj 的物品為 xij 萬(wàn)件,可建立如下線性規(guī)劃模型：miin z4x 112x 125 x 133 x 215x 223x 23x 313 x 323 x 33x 11x 12x 138x 21x 22x 237x 31x 32x 334s.t.x 11x

4、21x 31=4x 12x 22x 32=8x 13x 23x 33=5x ij0i, j1 2 3（ 2） 總產(chǎn)量 =8+7+4=19總銷量 =4+8+5=17,所以這是產(chǎn)大于銷的非標(biāo)準(zhǔn)運(yùn)輸問(wèn)題；可增加虛擬銷地即庫(kù)存積壓倉(cāng)庫(kù)B4,各個(gè)產(chǎn)地到它的單位運(yùn)價(jià)都是0,它的虛擬銷量即生產(chǎn)過(guò)剩量為 2 萬(wàn)件（ =19-17）；（3）第一步：用最小元素法確定初始方案,如下所示：4265028 60初始調(diào)運(yùn)方案X046523523507 201433004 020 4 8 5 2 0 2 0 0 0其次步：求非基變量檢驗(yàn)數(shù),驗(yàn)證初始方案是否最優(yōu)；法一 ：用位勢(shì)法求檢驗(yàn)數(shù)；求解見(jiàn)表 2 所示：表 2 產(chǎn)地銷地

5、B1 B2 B3 B4 Ui A1 3 4 2 5 5 0 0 0 0 A2 -1 3 5 0 3 -3 0 3 0 A3 0 1 3 3 3 0 0 0 1 Vj 1 2 0 0 由于 min11, 13,21,24,33,34| ij0=24= -30,所以初始方案并非最優(yōu)方案,需進(jìn)一步調(diào)整, x24 為進(jìn)基變量； 24表示假如產(chǎn)地A2 增運(yùn) 1 萬(wàn)件物品給虛擬銷地B4,將導(dǎo)致初始方案總運(yùn)費(fèi)削減3 百元；法二：用閉回路法求非基變量檢驗(yàn)數(shù)6 24 2 5 02 53 5 3 0 11=4-0+0-1=3； 13=5-3+5-2=5； 21=3-5+2-0+0-1=-1；4 01 3 3 0

6、24=0-5+2-0=-3 32=3-2+0-0=1； 33=3-3+5-2+0-0=3 （注：圖中畫(huà)出了非基變量 x21 的閉回路）；下面“ 驗(yàn)證初始方案是否最優(yōu)” 的分析同“ 法一”；第三步：求 值,調(diào)整初始方案,得到改進(jìn)方案二 X1；過(guò)程如下：+ 6-280 min2,2=2,0 運(yùn)量的 x14；X 1-25+=524040以 X24 作為進(jìn)基變量,由其所在閉回路的偶數(shù)序號(hào)格調(diào)運(yùn)量確定調(diào)整量依據(jù)“ 奇加偶減”的原就所示進(jìn)行調(diào)整, 選擇 x22 作為出基變量但保留調(diào)整后為用伏格爾法求出的初始方案就是調(diào)整方案X1；用位勢(shì)法可求出方案二X1 的非基變量檢驗(yàn)數(shù),如表3 所示：表 3 銷地產(chǎn)地 B

7、1 B2 B3 B4 Ui A1 4 2 5 0 0 3 0 2 0 A2 2 3 3 5 0 3 0 0 0 1 3 3 0 A3 0 0 1 0 0 Vj 1 2 3 0 由于全部非基變量檢驗(yàn)數(shù)都不小于 0 但 33=0,所以此題有無(wú)窮多最優(yōu)解；再以 x33為進(jìn)基變量比照上述方法進(jìn)行方案調(diào)整,可得到另一個(gè)最優(yōu)方案,如下：8 0*X 2 5 2,這個(gè)方案實(shí)際上與調(diào)整方案 X1是相同的；4 0決策結(jié)論：產(chǎn)地 A1向銷地 B2 調(diào)運(yùn)物品 8 萬(wàn)件；產(chǎn)地 A2 向銷地 B3 調(diào)運(yùn)物品 5 萬(wàn)件；產(chǎn)地 A3 向銷地 B1 調(diào)運(yùn)物品 4 萬(wàn)件；產(chǎn)地 A2 存在過(guò)剩生產(chǎn)物品 2 萬(wàn)件,存放在積壓倉(cāng)庫(kù) B

8、4；最小總運(yùn)費(fèi) =8 2+5 3+2 0+4 1=35（百元）；2、復(fù)習(xí)學(xué)問(wèn)點(diǎn)：（1）產(chǎn)大于銷、或者銷大于產(chǎn)的運(yùn)輸問(wèn)題建模（第三版89 頁(yè)（第 4 版 104 頁(yè)）“ 模型可寫(xiě)成” 始終到“ 由于總的產(chǎn)量” 之前的模型這是“ 產(chǎn)大于銷” 的情形；假如是其次種情形,就模型約束條件中的符號(hào)變?yōu)?:“=ai”、“ bj” ,其余與前者相同） ；（2）判定題目中的運(yùn)輸問(wèn)題是否為標(biāo)準(zhǔn)運(yùn)輸問(wèn)題（判別方法見(jiàn)第三版 89 頁(yè)（第 4 版 104頁(yè)）“ 前面講的表上作業(yè)法” 那一段文字,標(biāo)準(zhǔn)化確定是產(chǎn)銷平穩(wěn),不平穩(wěn)就是非標(biāo)準(zhǔn)運(yùn)輸問(wèn)題）；假如不是,請(qǐng)轉(zhuǎn)化為標(biāo)準(zhǔn)問(wèn)題,要把握“（ 1）中” 所述兩種非標(biāo)準(zhǔn)運(yùn)輸問(wèn)題進(jìn)行

9、標(biāo)準(zhǔn)化的方法（見(jiàn)第三版 90 頁(yè)（第 4 版 105 頁(yè)）從“ 如當(dāng)產(chǎn)大于銷時(shí)” 到“ 同樣可以轉(zhuǎn)化為 一個(gè)產(chǎn)銷平穩(wěn)的運(yùn)輸問(wèn)題；” 為止的表達(dá)； ）；（3）嫻熟把握用表上作業(yè)法求標(biāo)準(zhǔn)運(yùn)輸問(wèn)題最優(yōu)解的方法：用最小元素法確定初始方案；用位勢(shì)法或者閉回路法求變量檢驗(yàn)數(shù)并能據(jù)此判別當(dāng)前解是哪一種情形（唯獨(dú)最優(yōu)解仍是多 個(gè)最優(yōu)解？） ；用閉回路求 值法調(diào)整初始方案；（4）下結(jié)論,會(huì)求最小總費(fèi)用會(huì)判定是哪一個(gè)產(chǎn)地產(chǎn)量過(guò)?；蛘吣囊粋€(gè)銷地銷量未中意；（5）應(yīng)當(dāng)知道 ij=某個(gè)值的經(jīng)濟(jì)涵義；以下這兩個(gè)學(xué)問(wèn)點(diǎn)你在做考試題時(shí)會(huì)用上,當(dāng)然不會(huì)出簡(jiǎn)潔題, 而是融入具體做法來(lái)考；（6）在用最小元素法確定初始方案的過(guò)程中,

10、假如某元素對(duì)應(yīng)的行產(chǎn)量和列銷量相等,該 如何處理？答：假如每一步劃線之初同時(shí)有多個(gè)最小運(yùn)價(jià)元素,請(qǐng)從行、 列標(biāo)號(hào)最小的元素開(kāi)頭進(jìn)行支配（如樣題第一選擇了第 1 行第 4 列的 0 元素進(jìn)行支配） ；假如未進(jìn)行到最終一步但需要補(bǔ)充 0 元素作為基變量,請(qǐng)加在與該剩余最小元素（如運(yùn)價(jià)為“1” 的元素）所畫(huà)十字線上（樣題中即是劃去了第1 列和第 3 行的十字線）運(yùn)價(jià)最?。宇}中可以添0 的位置有5個(gè),即 x11、x21、x32、x33、x34,但 x34 對(duì)應(yīng)的運(yùn)價(jià)c34=0 是這五個(gè)位置中最小的,所以選擇在x34位置添加 0 將其作為基變量）且未支配運(yùn)量（如樣題中 x34 在添 0 之前并未支配運(yùn)

11、量）的位置；（7）在用閉回路求 值的過(guò)程中,假如最小 值對(duì)應(yīng)多個(gè)基變量,又該如何處理？答：假如進(jìn)基變量所在閉回路上的頂點(diǎn)偶數(shù)序號(hào)格（如在本樣題中即是 x14和 x22所在位置）,減去 值進(jìn)行調(diào)整后得到多個(gè) 0 元素（本樣題中：x14-2=x22-2=0,所以得到兩個(gè) 0 元素）,將對(duì)應(yīng)運(yùn)價(jià)最小的 0 元素保留為基變量（在本樣題中,將 x34=0 明確寫(xiě)出來(lái)而非變成非基變量即空格,由于 c34=0c22=5；也就是說(shuō)： x34 仍保留為基變量,但 x22 為出基變量變?yōu)榭崭瘢▽?shí)際上取值仍是 0,非基變量取值一律等于 0 但不寫(xiě)出來(lái)） ；）二、線性整數(shù)規(guī)劃之“ 指派問(wèn)題” 的建模與求解1、樣題支配

12、甲、乙、丙、丁四個(gè)人去完成A、B、C、 D、E 五項(xiàng)任務(wù)；每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間（單位：小時(shí)）如表 4 所示；假如： a.甲或丙之中有一人完成兩項(xiàng)任務(wù),乙和丁各完成一項(xiàng)； b.每人只能完成一項(xiàng),其中A 和 B 必需完成, C、D、E 中可以有一項(xiàng)不完成,甲必需做任務(wù) A 或 C,E不能交給乙來(lái)做；要求：（ 1）對(duì)于問(wèn)題 a 請(qǐng)給出標(biāo)準(zhǔn)化以后的效率矩陣并用匈牙利法求出最優(yōu)支配方案；（2）對(duì)于問(wèn)題 b 建立線性整數(shù)規(guī)劃模型,然后寫(xiě)出標(biāo)準(zhǔn)化以后的效率矩陣,但不必求解；表 4 人任務(wù)A B C D E 甲25 29 31 42 37 乙39 38 26 20 33 丙34 27 28 43 32 丁

13、24 42 36 23 30 解：（1）標(biāo)準(zhǔn)化以后的效率矩陣見(jiàn)表5：表 5 人任務(wù)A B C D E 由于任務(wù)數(shù)5 多于人數(shù) 4,所以此題并非標(biāo)準(zhǔn)指派問(wèn)題；增加一名假想的人戊；其完成各項(xiàng)工作的甲25 29 31 42 37 效率為甲、丙完成同一項(xiàng)工作效率的最小值；乙39 38 26 20 35 求解過(guò)程如下：丙34 27 28 43 32 丁24 42 36 23 30 戊25 27 28 42 32 -min2529314237-250461712045177m=n=35 19185083938262033-20191860133427284332-27701165試指派7001602442

14、362330-23119130711912022527284232-25023177022172不成功 -min 0 0 -1 0 -5 0 4 5 17 7-2 0 2 3 17 5 0 2 3 17 519 18 5 0 8-2 19 16 3 0 6 19 16 3 0 6m=n= 5 指派7 0 0 16 0 9 0 0 18 0 或 9 0 0 18 0 終止1 19 12 0 2-2 1 17 10 0 0 1 17 10 0 00min 2 2 17 2-2 0 0 0 17 0 0 0 0 17 0+2 +2結(jié)論：最優(yōu)支配方案： 甲 A；乙 D；丙 B 和 C；丁 E；最少的總

15、時(shí)間為：25+20+28+30+27=130 小時(shí)；1,表示指派第 人做第 項(xiàng)任務(wù)（2）設(shè) ix j i=1,2,3,4;j=1,2,.,5 ；該問(wèn)題的 0-1 整數(shù)規(guī)劃模0,否就4 5min z c ij x iji 1 j 1x i 1 + x i 2 + x i 3 + x i 4 + x i 5 1i 1, 2, 3, 4型如下：x 1 j + x 2 j + x 3 j + x 4 j 1j 1, 2x 1 j + x 2 j + x 3 j + x 4 j1j 3, 4, 5s t . .x 11 + x 13 1x 25 =0 x ij 0 或 1由于任務(wù)數(shù) 5 多于人數(shù) 4,所

16、以本問(wèn)題不是標(biāo)準(zhǔn)指派問(wèn)題；增加一名假想的人, 設(shè)為戊；其完成各項(xiàng)工作的效率分別為 M、M 、0、0、0；（注解：完工效率 M一個(gè)很大的正數(shù) 說(shuō)明任務(wù) A、B 不能交給虛擬人戊來(lái)做,甲確定不能做任務(wù) B、D 和 E,乙不能做任務(wù) E）；效率矩陣如表 6 所示：表 6 人任務(wù)A B C D E 甲25 M 31 M M 乙39 38 26 20 M 丙34 27 28 43 32 丁24 42 36 23 30 戊M M 0 0 0 2、學(xué)問(wèn)點(diǎn)：（1）人多任務(wù)少、人少任務(wù)多兩種非標(biāo)準(zhǔn)指派問(wèn)題的建模；（2）上述兩種非標(biāo)準(zhǔn)指派問(wèn)題的標(biāo)準(zhǔn)化方法；（3）會(huì)用 0-1 變量表達(dá)式寫(xiě)出某人不能完成某些任務(wù)、或

17、者某人必需完成某項(xiàng)任務(wù)、或者某任務(wù)可完成也可不完成的約束條件；在效率矩陣中,會(huì)應(yīng)用大M 處理這些情形；（4）嫻熟把握用匈牙利法求解指派問(wèn)題最優(yōu)解法方法和步驟；并且可以求出最優(yōu)支配方案和最小總時(shí)間（或總費(fèi)用）；126130 頁(yè)有關(guān)內(nèi)容或者第4 版 146151 頁(yè)有關(guān)內(nèi)容,注解：上述學(xué)問(wèn)復(fù)習(xí), 請(qǐng)看第三版其中的定理證明可不看,可比照樣題以及本樣題把握解題方法和步驟；三、動(dòng)態(tài)規(guī)劃之“ 一維資源連續(xù)支配問(wèn)題” 的建模與求解1、樣題（注解：考試時(shí)題目運(yùn)算量比樣題要小,可能只有三個(gè)階段）某廠有 100 臺(tái)設(shè)備,可用于加工甲,乙兩種產(chǎn)品；據(jù)以往體會(huì), 這些設(shè)備加工甲產(chǎn)品每季末損壞 1/3 ,而加工乙產(chǎn)品每

18、季末損壞 1/10 ,損壞的設(shè)備當(dāng)年不能復(fù)修；每臺(tái)機(jī)器一季全加工甲或乙產(chǎn)品,其創(chuàng)利為 10 或 7 百元；問(wèn)如何支配各季加工任務(wù),能使全年獲利最大？請(qǐng)建立該問(wèn)題的動(dòng)態(tài)規(guī)劃模型并用逆序解法求解,畫(huà)出狀態(tài)轉(zhuǎn)移圖得出結(jié)論；解：（1）將問(wèn)題按季度數(shù)分為 4 個(gè)階段, k=1,2,3,4；設(shè)狀態(tài)變量 s k ：表示第 k 季度初擁有的完好設(shè)備的臺(tái)數(shù)；s1=100；設(shè)決策變量 uk：表示第 k 季度初投入甲產(chǎn)品生產(chǎn)的設(shè)備臺(tái)數(shù),就投入乙產(chǎn)品生產(chǎn)的設(shè)備臺(tái)數(shù) vk =sk -uk；明顯 uk Dksk =uk|0 uksk ；狀態(tài)轉(zhuǎn)移方程：sk +1=auk+bv k =2/3u k+9/10s k -u k

19、；指標(biāo)函數(shù)：階段指標(biāo)函數(shù) dkS k,u k 表示第 k 期從 Sk臺(tái)設(shè)備中抽出 uk臺(tái)投入甲產(chǎn)品生產(chǎn)、sk -u k臺(tái)投入乙產(chǎn)品生產(chǎn)時(shí)得到的利潤(rùn)；dkS k,u k 10uk+7s k -u k ；最優(yōu)指標(biāo)函數(shù) f ks k 表示 sk 臺(tái)設(shè)備從第 k 至第 4 期支配時(shí)所得到的最大利潤(rùn)總和 . 逆序解法的基本方程如下：fks kumaxk D k skdks ,ukfk1s k1,k4 3, 2,1f5s 50 （2）用逆序解法求解第 4 階段, k=4 s5= 2/3 u4+9/10 s4 u4 f s 0 u max10u4 s 4 4 7s 4 u f s 0 u max3u4 s

20、4 4 7s 10s 4u4 * =s4時(shí) f 4s 4=10s 4；第 3 階段, k=3 s4=2/3u 3+9/10s 3 u3 f s 0 u max10u3 s 3 3 7s 3 u f s = max10u 0 u 3 s 3 3 7s 3 u 10s 2 9 2 500 u max3 s 3 10u 3 7s 3 u 103 u 310 s 3 u 0 u max 3 s 3 3 u 3 16s =3 s 3u3 * =s3時(shí) f 3s 3=50/3 s3；第 2 階段, k=2 s3= 2/3u 2+9/10s 2 u2 f s max 10u 2 7s 2 u f s max

21、 10u 2 7s 2 u 50 s 0 u 2 s 2 0 u 2 s 2 30 maxu 2 s 2 10u 2 7s 2 u 503 23 u 210 9 s 2 u 0 max 22su 2 s 22 89 u 22s 2u2 * =0 時(shí) f 2s 2=22 s2；第 1 階段, k=1 s2= 2/3u 1+9/10s 1 u 1 f s 0 u max10u1 s 1 1 7s 1 u f s 0 u max10u1 s 1 1 7s 1 u 22s 2 9 134 320 u max 10u1 s 1 1 7s 1 u 223 u 110 s 1 u 0 u max 1 s 1

22、 5 s 115 u u1 * =0 時(shí) f 1s 1=134/5 100=2680 百元,這就是四期的最大總利潤(rùn)和；狀態(tài)轉(zhuǎn)移圖如圖 1 所示：U1 *100=0 U2 *90=0 U3 *81=81 U4 *54=54 S1 *=100 k=1 S2 *=90 k=2 S3 *=81 k=3 S4 *=54 k=4 S5 *=36 s2=2/3u 1+ s3=2/3u 2+ s4=2/3u 3+ s5=2/3u 4+ 9/10100-u 1 9/10s 2-u 2 9/10s 3-u 3 9/10s 4-u4d1 *100,0=700 d2 *90,0=630 d3 *81,81=810 d

23、3 *54,54=504 圖 1 一維資源連續(xù)支配問(wèn)題的狀態(tài)轉(zhuǎn)移圖由狀態(tài)轉(zhuǎn)移圖得出結(jié)論：全年最大獲利即 f 1s 1=2680 百元； 最優(yōu)支配方案如下：四個(gè)季度投入甲產(chǎn)品生產(chǎn)的設(shè)備數(shù)量分別為 0、0、 81、54 臺(tái)；2、學(xué)問(wèn)點(diǎn)：（1）“ 一維資源連續(xù)支配” 問(wèn)題的動(dòng)態(tài)規(guī)劃建模；可見(jiàn)講課課件、 本樣題求解第一部分或者課本：第三版 217 頁(yè)（或第四版253254 頁(yè)）從“ 設(shè)階段序數(shù)k” 始終到“ 從第 5 年度開(kāi)頭 ”之前的表達(dá)；（2）把握用逆序解法求解動(dòng)態(tài)規(guī)劃模型的方法和步驟；可比照本樣題求解其次部分、講課課件或者課本：第三版217218 頁(yè)（或第四版254255 頁(yè)）從“ 當(dāng) k=5

24、時(shí),有” 下面進(jìn)一步來(lái)爭(zhēng)辯始端固定 ” 之前的表達(dá)；（3）把握用狀態(tài)轉(zhuǎn)移圖來(lái)順向推到最優(yōu)決策變量、狀態(tài)變量、階段指標(biāo)函數(shù)的方法,請(qǐng)看樣題求解其次部分的圖,或者課本第三版 203 頁(yè)圖 8-6（或第四版 238 頁(yè)圖 9-6）；（4）會(huì)求出全過(guò)程最優(yōu)指標(biāo)值,并且知道其確定的依據(jù)；請(qǐng)看本樣題的結(jié)論部分就有說(shuō)明；四、圖論之“ 最小費(fèi)用最大流” 問(wèn)題的求解1、樣題：試用對(duì)偶法求圖2 所示的最小費(fèi)用最大流；圖中數(shù)字 （cij,bij, fij）分別代表弧 （vi,vj）容量、單位流量費(fèi)用（元）和當(dāng)前可行流；v1 10,4,6 7,1,7vt vs 1,5,1 2,8,0 圖 26,2,48,1,5 10,3,4v 2 v3 解：用對(duì)偶法求解（費(fèi)用路 a、c、e 中標(biāo)記“ ” 的為最短路）,如圖 3ae所示：v1 v1 -44-1 10,4,7 7,1,7vt v t vs 1-5 82-2 vs 1,5,0 2,8,06,2,5-1 3 8,1,5