復(fù)習(xí)2運(yùn)籌學(xué)課件胡運(yùn)權(quán)第四版復(fù)習(xí)要點(diǎn).ppt

,一般線性規(guī)劃問題的對偶問題,對偶問題對應(yīng)表,例：設(shè)整數(shù)規(guī)劃問題如下,首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。,且為整數(shù),用圖解法求出最優(yōu)解 x13/2, x2 = 10/3 且有Z = 29/6,x1,x2,3,3,(3/2,10/3),現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)即(1，3), (2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。,按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如圖所示。,有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？,指派問題,求解過程如下： 第一步，變換系數(shù)矩陣：,5,第二步，試指派：,找到 3 個(gè)獨(dú)立零元素 但 m = 3 n = 4,指派問題,第三步，作最少的直線覆蓋所有0元素：,獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即lm=3n=4；,第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打各行都減去1；打各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進(jìn)行試指派：,指派問題,得到4個(gè)獨(dú)立零元素， 所以最優(yōu)解矩陣為：,15,指派問題,（三）用節(jié)點(diǎn)標(biāo)號法計(jì)算工期并確定關(guān)鍵線路 1) 設(shè)網(wǎng)絡(luò)計(jì)劃起點(diǎn)節(jié)點(diǎn)的標(biāo)號值為零，即b10。 2) 順箭線方向逐個(gè)計(jì)算節(jié)點(diǎn)的標(biāo)號值。每個(gè)節(jié)點(diǎn)的標(biāo)號值，等于以該節(jié)點(diǎn)為完成節(jié)點(diǎn)的各工作的開始節(jié)點(diǎn)標(biāo)號值與相應(yīng)工作持續(xù)時(shí)間之和的最大值，即： bjmaxbi+Dij 將標(biāo)號值的來源節(jié)點(diǎn)及得出的標(biāo)號值標(biāo)注在節(jié)點(diǎn)上方。 3)節(jié)點(diǎn)標(biāo)號完成后，終點(diǎn)節(jié)點(diǎn)的標(biāo)號值即為計(jì)算工期。 4) 從網(wǎng)絡(luò)計(jì)劃終點(diǎn)節(jié)點(diǎn)開始，逆箭線方向按源節(jié)點(diǎn)尋求出關(guān)鍵線路。,【例3】某已知網(wǎng)絡(luò)計(jì)劃如圖所示，試用標(biāo)號法求出工期并找出關(guān)鍵線路。,關(guān)鍵線路是由關(guān)鍵工序連成的線路，其特點(diǎn)： 關(guān)鍵線路指從網(wǎng)絡(luò)圖起始節(jié)點(diǎn)到終止節(jié)點(diǎn)作業(yè)時(shí)間最長的線路，其長度就是網(wǎng)絡(luò)計(jì)劃的工期。 關(guān)鍵線路上各工序總時(shí)差為零或?yàn)樨?fù)值或?yàn)樽钚≌怠?一個(gè)網(wǎng)絡(luò)計(jì)劃中可以有多條關(guān)鍵工序，且至少有一條關(guān)鍵線路。,期望值法,期望值最大方案為最優(yōu)方案。例:,生產(chǎn)10年，減去投資：,最優(yōu)方案 a*= a1,這也是一種基于期望值的方法，但它所用的不是決策表，而是用圖（樹）：,決策樹法,2,1,大廠,3,小廠,0.7,0.3,100,-20,0.7,0.3,40,20,190,340,把上例改為