最優(yōu)截斷切割問題(編輯修改稿)
2025-04-22 01:22 本頁面
【文章內(nèi)容簡介】 一）的有向路決不通過情形（二）的公共點集，情形（二）的有向路也不通過情形（一）的公共點集。所以可判斷出這兩部分是獨立的、互補的。.如果我們在圖G中分別去掉點集{(1,2,z)|z=0,1,2}和{(2,1,z)|z=0,1,2}及與之相關(guān)聯(lián)的入弧，就形成兩個新的網(wǎng)絡(luò)圖，如圖Ｈ1和Ｈ2。這兩個網(wǎng)絡(luò)圖具有互補性。對于一個問題來說，最短路線必存在于它們中的某一個中。由于調(diào)整垂直刀具為3次時，總費用需增加3e，故我們先安排這種情況的權(quán)增加值e，每次轉(zhuǎn)刀時，給其待切弧上的權(quán)增加e。增加e的情況如下圖中所示。再來判斷是否滿足調(diào)整垂直刀具為二次、一次時的情況，我們發(fā)現(xiàn)所增加的權(quán)滿足另外兩類切割序列。綜合上述分析，我們將原網(wǎng)絡(luò)圖G分解為兩個網(wǎng)絡(luò)圖Ｈ1和Ｈ2，并在指定邊上的權(quán)增加e，然后分別求出圖和中從到的最短路，最短路的權(quán)分別為：d1,：，相應(yīng)的圖求出的最優(yōu)切割序列即為其對應(yīng)的最短路徑。圖圖Ⅲ、對“每次選擇一個加工費用最少的待切割面進行切割”這個準則的好壞進行評價評價的標準：最佳切割方式可以不唯一，可是最佳加工費用應(yīng)等于按照之前的模型求解出的最少加工費用。即：若準則精選出的不同切割方式有很多，而相應(yīng)的加工費卻不全相同，則其不具備優(yōu)化準則的基本屬性。同樣，即使精選出的切割方式唯一，但加工費卻非真正意義上的最小，則準則也無最優(yōu)性可言。根據(jù)實例中的數(shù)據(jù)，在局部最優(yōu)準則的前提下，假定時，求出的最佳加工費用為374元，這與用上面的模型求解出的結(jié)果相同。假定時，求出的最佳加工費用為490元，并且比上面的結(jié)果大。因此，“每次選擇一個加工費用最少的待切割面進行切割”不能作為最佳優(yōu)化準則使用，但當時可以采用這個準則，而當時不能采用這個準則。四、模型求解結(jié)果由題目所給的數(shù)據(jù)可以得出、、的值：61769A、r=1,e=0時弧1,21,41,102,32,52,113,63,124,5權(quán)值190145765857弧4,74,135,65,85,146,96,157,87,16權(quán)值190757630573820弧8,98,179,1810,1110,1310,1911,1211,1411,20權(quán)值38861451001451454058弧12,1512,2113,1413,1613,2214,1514,1714,2315,18權(quán)值30751007575403030弧15,2416,1716,2517,1817,2618,2719,2019,2220,21權(quán)值20202086584058弧20,2321,2422,2322,2523,2423,2624,2725,2626,27權(quán)值1612304030161288費用最少為374元。B、r=，e=0時弧1,21,41,102,32,52,113,63,124,5權(quán)值190768757弧4,74,135,65,85,146,96,157,87,16權(quán)值1907645573830弧8,98,179,18
試題試卷相關(guān)推薦
鄂ICP備17016276號-1