[建筑]垃圾運(yùn)輸問題的模型及其求解-資料下載頁
2025-01-08 20:56本頁面
【正文】 tij，并根據(jù)各工序之間的加工次序的限制條件畫出 D 中的一條主要路徑 P： 4— 7— 1l— 一 3— 8— 一 14 一 l2 一 l3，所謂主要路徑就是加工所有工件時，必須符合其先后次序而不能調(diào)換或改變 這種次序的路徑．但主要路徑中間可以插人別的在主要路徑中未出現(xiàn)的工序．于是問題就變成在滿足主要路 徑 P的條件下，在 D中尋找最佳 H路．由表可知：工序 lO 應(yīng)在工序 5之前，工序 9應(yīng)在工序3之前 工序 4 之 后，工序 1應(yīng)在工序 3 之后工序 l4之前，工序 6應(yīng)在工序 8之后工序 l4 之前，故可將 P分成兩段： Pl： 4— 7 一 ll— 一 3， P2： 3— 8— 2一 l4 一 l2 一 l3．將工序 lO與 9插人 Pl中可得如下圖 2： 圖 2 部分工件加工順序圖 圖 2中共有 l9條不同的 H路，其中的最短 H路可用窮舉法，也可用下面的近似方法：先用 Dijkstra算法求出 4— 3的最短有向路為 Pl 4— 7— 247。9 — — 3，總權(quán)值為 39．再將工序 lO 和 11插 人到 Pl 中，由于弧 (10， 9)和弧 (11， 10)的權(quán)都 是 2，用子路 7— 11一 lO一 9 替代路 Pl沖的弧 (7， 9)，得最短有向路為 Pl，． 4— 7一 l 1一 lO一 9 — 一 3，總權(quán)值為 45．這恰好就是這 l9條 H路 中的最短 H路．下面考慮將工序 1與 6插入 P2 中，共有 8條不同的路，其中最短有向路為 P2 8 一 1一 l4 一 l2一 l3，總權(quán)值為 29．因此， 所求加工順序為 Pl P2，． 4 — ll一 1O 一 5— 3— 8 一 2一 l— l4一 l2一 l3，機(jī)床花費(fèi)總的準(zhǔn)備時間為 ll4． 又如 1998年全國大學(xué)生數(shù)學(xué)建模競賽題 B題《災(zāi)情巡視路線》，可將一般網(wǎng)絡(luò)上多組最優(yōu)巡視問題轉(zhuǎn) 化為賦權(quán)完全圖上的多個 TsP 問題 ，詳細(xì)請參見文獻(xiàn) [1]． 參考文獻(xiàn)： [1】趙肝，但琦．?dāng)?shù)學(xué)建模與數(shù)學(xué)實驗 [M】．北京：高等教育出版社， 2022． 11． 149— 160． [2] 李尚志．?dāng)?shù)學(xué)建模競賽教程 [M】．南京：江蘇教育出版社。 1996． 308— 312．
試題試卷相關(guān)推薦
鄂ICP備17016276號-1