答疑與更正.ppt

1、運(yùn)籌學(xué)課堂教學(xué) 答疑與更正,1.破圈法求解,2. 逐步生長(zhǎng)法求解,3.海斯算法中間點(diǎn)矩陣編號(hào)選擇,寫出距離矩陣,第一次迭代,第一種取法,第二種取法,第二次迭代,第一種取法,第二種取法,V3如何到V6？ V1如何到V5？,第三次迭代,第一種取法,第二種取法,由于 ， 中的元素就是最短距離。,最短路線：,SUMMARY （1）每次迭代，中間點(diǎn)的選擇都不一定唯一。往往首次迭代由于路徑不通，中間點(diǎn)唯一的可能性較大，但后面的迭代中間點(diǎn)可能有24個(gè)。 （2）反映自連接的中間點(diǎn)實(shí)際上沒(méi)有有用信息，與起點(diǎn)和終點(diǎn)不同的中間點(diǎn)才有價(jià)值。 （3）盡管中間點(diǎn)的選擇多種多樣，但得到的最短路線卻完全相同，最短距離也完全相

2、同。 （4）在中間點(diǎn)矩陣中，對(duì)角線及下三角中的元素是冗余元素。,4.設(shè)備更新問(wèn)題更正（P133134）,當(dāng)完成各階段求解過(guò)程后，如何查表？ 例：考慮役齡為4的設(shè)備如何制定今后十年（十個(gè)階段）的更新計(jì)劃？ （1）順序從第1階段f1(t)和當(dāng)前役齡t=4查起，得最大回收額為82萬(wàn)元，相應(yīng)的決策是K或P,選擇K。 （2）查第2階段f2(t)和役齡t=5,得回收額為74萬(wàn)元，相應(yīng)決策為P （3）查第3階段f3(t)和役齡t=1,得回收額為71萬(wàn)元，相應(yīng)決策為K （4）查第4階段f4(t)和役齡t=2,得回收額為60萬(wàn)元，相應(yīng)決策為K （5）查第5階段f5(t)和役齡t=3,得回收額為50萬(wàn)元，相應(yīng)決策

3、為K （6）查第6階段f6(t)和役齡t=4,得回收額為41萬(wàn)元，相應(yīng)決策為K,(7)查第7階段f7(t)和役齡t=5,得回收額為33萬(wàn)元，相應(yīng)決策為P (8)查第8階段f8(t)和役齡t=1,得回收額為30萬(wàn)元，相應(yīng)決策為K (9)查第9階段f9(t)和役齡t=2,得回收額為19萬(wàn)元，相應(yīng)決策為K (10)查第10階段f10(t)和役齡t=3,得回收額為9萬(wàn)元，相應(yīng)決策為K 最后得最優(yōu)更新策略： 設(shè)備的役齡序列為：,更正：p134表5.27及更新策略、役齡序列,4.動(dòng)態(tài)規(guī)劃建模作業(yè)：P1362）_（2）,決策變量的允許集合：,5.N個(gè)頂點(diǎn)的容量網(wǎng)絡(luò)最多有多少個(gè)割集？,VS,Vt,N-2,假定

4、：網(wǎng)絡(luò)結(jié)構(gòu)可以保證沒(méi)有重復(fù)現(xiàn)象。,集合S構(gòu)成：,6.可以用枚舉法求最小割集？,（1）可以，但網(wǎng)絡(luò)規(guī)模很大時(shí)不好用； （2）原則：割容量最大流； （3）方法：包含在割集中的弧都飽和弧；,7.標(biāo)號(hào)過(guò)程中，不一定要對(duì)所有的頂點(diǎn)全部逐個(gè)順序標(biāo)記，只要找到增廣鏈就行。 8.可以同時(shí)在若干條增廣鏈上進(jìn)行流量調(diào)整，前提是保證：所得流仍然是可行流。 9.同一個(gè)問(wèn)題每一次標(biāo)號(hào)過(guò)程所尋找的增廣鏈不一定唯一。 10.最大流（XXij）不一定唯一，但最大流量唯一。 11.最小割集不一定唯一，可能在兩個(gè)或兩個(gè)以上的地方都是網(wǎng)絡(luò)的“瓶頸”。 12.最大流量和最小割容量相等，且唯一。 13.多發(fā)點(diǎn)和多收點(diǎn)的網(wǎng)絡(luò)可以虛設(shè)發(fā)點(diǎn)和收點(diǎn)。 14.