[理學(xué)]第三版運(yùn)籌學(xué)總復(fù)習(xí)-資料下載頁
2024-10-19 00:59本頁面
【正文】 代表的人只有一種任務(wù)可分派。然后，劃去該◎所在列的其他 0元素，記作 φ 表示該列所代表的任務(wù)已分派完，不必再考慮別人了。 b）給只有一個(gè) 0元素列的 0元素加圈 ,記作◎。然后，劃去該◎所在行的其他 0元素，記作 φ。 c）反復(fù)進(jìn)行 a）、 b）操作，直到所有 0元素都被圈出和劃掉為止。若每行每列均只有一個(gè)◎時(shí)（對應(yīng)的 xij=1，其余的 xij=0），即◎的個(gè)數(shù)等于方陣階數(shù)，得到最優(yōu)解，否則，轉(zhuǎn)到下一步。 第三步：◎的個(gè)數(shù)少于方陣的階數(shù)。 際 恩 陸 2021/11/10 30 a）若出現(xiàn) 0元素閉回路，則任選一個(gè) 0畫◎破閉回路，并劃去同行與同列其他 0元素，得到最優(yōu)解。 b）若無 0元素閉回路，則用覆蓋理論解決。 Ⅰ ）若無 0元素閉回路，則用直線覆蓋理論解決。 Ⅱ ）對未被直線覆蓋的一類區(qū)所有元素減去它們中的最小數(shù)；而對被直線交叉覆蓋的三類元素加上剛才的最小數(shù)，其余元素不變。轉(zhuǎn)第二步，循環(huán)執(zhí)行到◎的個(gè)數(shù)等于方陣階數(shù)為止。 ⑶ 非標(biāo)準(zhǔn)型的指派問題 略。 際 恩 陸 2021/11/10 31 第五章 復(fù)習(xí)思考題 整數(shù)規(guī)劃的意義，舉出整數(shù)規(guī)劃的例子。（略） 有人提出，求解整數(shù)規(guī)劃時(shí)，可先不考慮變量的整數(shù)約束，而去求解相應(yīng)的線性規(guī)劃問題，然后對求解結(jié)果為非整數(shù)的變量湊整。試問這種方法是否可行，為什么？ 這種方法對于整數(shù)規(guī)劃問題存在有有限個(gè)整數(shù)可行解時(shí)，是可行的。因?yàn)橹灰麛?shù)規(guī)劃問題中存在有有限個(gè)整數(shù)可行解，而又可求得相應(yīng)的線性規(guī)劃問題的最優(yōu)解，就一定可以用湊整和比較的辦法求得整數(shù)規(guī)劃問題的最優(yōu)解，其實(shí)，隱枚舉法和分支定解法就是根據(jù)這一原理來求解的。 際 恩 陸 2021/11/10 32 試述用分支定支定界法求解整數(shù)規(guī)劃問題的主要思想及主要步驟及此種方法的優(yōu)缺點(diǎn)。 見教材 P137— P141。 01變量的作用和舉例。 略。 試述用割平面法求解整數(shù)規(guī)劃問題的主要思想，在構(gòu)造割平面時(shí)如何做到從原可行域中只切去變量的非整數(shù)解。 見教材 P133— P137。 什么是隱枚舉法？為什么說分支定界法也是一種隱枚舉法？ 際 恩 陸 2021/11/10 33 把一個(gè)整數(shù)規(guī)劃問題的所有整數(shù)可行解都一一列出，然后比較它們的目標(biāo)函數(shù)值，從中選出目標(biāo)函數(shù)值最優(yōu)的整數(shù)解的方法叫完全枚舉法。而去掉部分不可能是最優(yōu)解的整數(shù)可行解，只在有限個(gè)整數(shù)可行解中求解最優(yōu)整數(shù)解的方法叫隱枚舉法。分支定界法正是應(yīng)用這一原理，利用分支和定界去掉部分非整數(shù)解，而使求解過程得以簡化。 ⑴ 整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問題的解的目標(biāo)函數(shù)值； 判斷下列說法是否正確 ⑵ 用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問題時(shí)，任何一個(gè)可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的下界。 √ 際 恩 陸 2021/11/10 34 ⑶ 用分支定界法求解一個(gè)極大化的整數(shù)規(guī)劃問題時(shí)，當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解，通常可任取其中一個(gè)為下界值，再進(jìn)行比較剪支； ⑷ 用割平面法求解整數(shù)規(guī)劃時(shí)，構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)解； ⑸ 用割平面法求解純整數(shù)規(guī)劃時(shí)，要求包括松弛變量在內(nèi)的全部變量必須取整數(shù)值； ⑹ 指派問題效率矩陣的每個(gè)元素都乘以同一常數(shù) k，將不影響最優(yōu)指派方案； ⑺ 指派問題數(shù)學(xué)模型的形式同運(yùn)輸問題十分相似，故也可以用表上作業(yè)法求解； √ √ 際 恩 陸 2021/11/10 35 ⑻ 求解 01規(guī)劃的隱枚舉法是分支定界法的物例。 ⑼ 分支定界法在需要分支時(shí)必須滿足：一是分支后的各子問題必須容易求解；二是各子問題解的集合必須覆蓋原問題的解。 √ √ 際 恩 陸 2021/11/10 36 際 恩 陸 2021/11/10 37 際 恩 陸 2021/11/10 38 際 恩 陸 2021/11/10 39 際 恩 陸 2021/11/10 40 際 恩 陸 2021/11/10 4
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1