[理學]第三版運籌學總復習(參考版)
2024-10-22 00:59本頁面
【正文】 √ √ 際 恩 陸 2021/11/10 36 際 恩 陸 2021/11/10 37 際 恩 陸 2021/11/10 38 際 恩 陸 2021/11/10 39 際 恩 陸 2021/11/10 40 際 恩 陸 2021/11/10 41 。 √ 際 恩 陸 2021/11/10 34 ⑶ 用分支定界法求解一個極大化的整數(shù)規(guī)劃問題時，當?shù)玫蕉嘤谝粋€可行解，通常可任取其中一個為下界值，再進行比較剪支； ⑷ 用割平面法求解整數(shù)規(guī)劃時，構造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)解； ⑸ 用割平面法求解純整數(shù)規(guī)劃時，要求包括松弛變量在內的全部變量必須取整數(shù)值； ⑹ 指派問題效率矩陣的每個元素都乘以同一常數(shù) k，將不影響最優(yōu)指派方案； ⑺ 指派問題數(shù)學模型的形式同運輸問題十分相似，故也可以用表上作業(yè)法求解； √ √ 際 恩 陸 2021/11/10 35 ⑻ 求解 01規(guī)劃的隱枚舉法是分支定界法的物例。分支定界法正是應用這一原理，利用分支和定界去掉部分非整數(shù)解，而使求解過程得以簡化。 什么是隱枚舉法？為什么說分支定界法也是一種隱枚舉法？ 際 恩 陸 2021/11/10 33 把一個整數(shù)規(guī)劃問題的所有整數(shù)可行解都一一列出，然后比較它們的目標函數(shù)值，從中選出目標函數(shù)值最優(yōu)的整數(shù)解的方法叫完全枚舉法。 試述用割平面法求解整數(shù)規(guī)劃問題的主要思想，在構造割平面時如何做到從原可行域中只切去變量的非整數(shù)解。 01變量的作用和舉例。 際 恩 陸 2021/11/10 32 試述用分支定支定界法求解整數(shù)規(guī)劃問題的主要思想及主要步驟及此種方法的優(yōu)缺點。試問這種方法是否可行，為什么？ 這種方法對于整數(shù)規(guī)劃問題存在有有限個整數(shù)可行解時，是可行的。 際 恩 陸 2021/11/10 31 第五章 復習思考題 整數(shù)規(guī)劃的意義，舉出整數(shù)規(guī)劃的例子。轉第二步，循環(huán)執(zhí)行到◎的個數(shù)等于方陣階數(shù)為止。 Ⅰ ）若無 0元素閉回路，則用直線覆蓋理論解決。 際 恩 陸 2021/11/10 30 a）若出現(xiàn) 0元素閉回路，則任選一個 0畫◎破閉回路，并劃去同行與同列其他 0元素，得到最優(yōu)解。若每行每列均只有一個◎時（對應的 xij=1，其余的 xij=0），即◎的個數(shù)等于方陣階數(shù)，得到最優(yōu)解，否則，轉到下一步。然后，劃去該◎所在行的其他 0元素，記作 φ。然后，劃去該◎所在列的其他 0元素，記作 φ 表示該列所代表的任務已分派完，不必再考慮別人了。則以 C’ 求得的最優(yōu)解和以 C求得的最優(yōu)解相同。 首先：每行減該行中的最小數(shù)，再每列減去該列中的最小數(shù)。 際 恩 陸 2021/11/10 28 標準型指派問題的求解 ① 求解原理：找出一組位于系數(shù)矩陣中不同行、不同列的零元素，對其畫圈，對應的 xij=1，未畫圈的元素，對應的 xij=0，此時，目標函數(shù)最優(yōu)。 指派問題的標準型 目標函數(shù)為求 min；系數(shù)矩陣為方陣（即每項工作只能有一人來做，每個人只能做一項工作），且其所有元素均為非負。這是一類特殊的 0— 1規(guī)劃問題。 以 z的最大值為上界逐步向上搜索，直至獲得可行解，此即為最優(yōu)解。如本章的例 11。用隱枚舉法求解 0— 1規(guī)劃的步驟如下： 第一步：變換目標函數(shù)和約束方程組。 0— 1規(guī)劃與隱枚舉法 ⑴ 0— 1規(guī)劃的概念 決策變量只取 0， 1兩個數(shù)的整數(shù)規(guī)劃， 1， 0表示方案的取舍。即： 0??? ? kikbi xff方程右邊際 恩 陸 2021/11/10 25 上述就是所求的割平面方程。以上方程左邊為整數(shù)，右邊的內是正數(shù)。 ? ? bibikikiki fNxfNx ????? ? ③ 將整數(shù)項寫于方程左邊，真分數(shù)項寫于右邊。 際 恩 陸 2021/11/10 24 ikiki bxax ?? ? 其中 bi是基變量 xi的非整數(shù)解。步驟如下：
教學課件相關推薦
鄂ICP備17016276號-1