物流運籌學-整數(shù)規(guī)劃課件

1、第三章 整數(shù)規(guī)劃 一般整數(shù)規(guī)劃問題 整數(shù)規(guī)劃的解法 01規(guī)劃 指派問題 物流資源分配問題1可編輯ppt第三章 整數(shù)規(guī)劃 一般整數(shù)規(guī)劃問題1可編輯ppt知識目標掌握整數(shù)規(guī)劃的基本形式；掌握分枝定界法計算過程；理解割平面法；掌握01規(guī)劃的標準形式；了解01變量的應用；掌握01規(guī)劃的匈牙利解法。技能目標能夠結合實際情況建立整數(shù)規(guī)劃模型，并可利用分枝 定界法求解；能夠應用01規(guī)劃建模并求解，安排人員工作。2可編輯ppt知識目標2可編輯ppt第一節(jié) 一般整數(shù)規(guī)劃問題什么是整數(shù)規(guī)劃問題？整數(shù)規(guī)劃的一般形式：3可編輯ppt第一節(jié) 一般整數(shù)規(guī)劃問題什么是整數(shù)規(guī)劃問題？3可編輯pp第二節(jié) 整數(shù)規(guī)劃的解法 割平面

2、法分枝定界法4可編輯ppt第二節(jié) 整數(shù)規(guī)劃的解法 割平面法4可編輯ppt例3-5 5可編輯ppt例3-5 5可編輯ppt割平面法基本思想：求原問題對應松弛問題最優(yōu)解，如果不是原問題的可行解，則通過引入線性約束條件（即割平面），使松弛問題的可行域逐步縮小（即切掉一部分），每次切割掉的是松弛問題的非整數(shù)解的一部分，但不切掉任何整數(shù)解，直到最后使目標函數(shù)達到最優(yōu)的整數(shù)解成為可行域的一個頂點時，即為原問題的最優(yōu)解。其本質是利用線性規(guī)劃的求解方法逐步縮小可行域，最后找到整數(shù)規(guī)劃的最優(yōu)解。 6可編輯ppt割平面法基本思想：求原問題對應松弛問題最優(yōu)解，如果不是原問題例3-6 7可編輯ppt例3-6 7可編輯

3、ppt8可編輯ppt8可編輯ppt9可編輯ppt9可編輯ppt其最優(yōu)解為=（1,1）最優(yōu)值為=1 10可編輯ppt其最優(yōu)解為=（1,1）最優(yōu)值為=1 10可編輯ppt割平面法的求解步驟 步驟1：求解原問題的松弛問題，得最優(yōu)解，若滿足整數(shù)約束，則即為最優(yōu)解，否則進入下一步；步驟2：分解其中一個非整分量，構造一個新的線性約束條件，加入原松弛問題中，形成新的線性規(guī)劃；步驟3：求解新線性規(guī)劃問題，得，若為整數(shù)則為原問題的最優(yōu)解，否則進入步驟2。按某非整分量構造的約束條件需滿足以下兩個條件：（1）當前最優(yōu)解不滿足該約束，即使得該最優(yōu)解不會再出現(xiàn)在松弛問題可行解中；（2）所有整數(shù)可行解均滿足該約束，即新增

4、約束條件后，仍保留了原松弛問題的所有整數(shù)解。11可編輯ppt割平面法的求解步驟 步驟1：求解原問題的松弛問題，得最優(yōu)解，分枝定界法 基本思想：求原問題的對應的松弛問題，其最優(yōu)解若不是原問題的可行解，則通過附加線性不等式約束（整型），將松弛問題分枝變?yōu)槿舾勺訂栴}，即對每一個非整變量附加兩個互相排斥（不交叉）的整型約束，即得兩個子問題，繼續(xù)求解定界，重復下去，直到得到最優(yōu)解為止。12可編輯ppt分枝定界法 基本思想：求原問題的對應的松弛問題，其最優(yōu)解若不例3-7 用分枝定界法求解：13可編輯ppt例3-7 用分枝定界法求解：13可編輯ppt14可編輯ppt14可編輯ppt分枝定界法求解步驟步驟1：

5、求解原問題的松弛問題（用LP表示），得最優(yōu)解，若滿足整數(shù)約束，則即為最優(yōu)解，否則進入下步。步驟2：分枝。任選的一個不為整的分量，設為（其中為整數(shù)部分，為小數(shù)部分），據(jù)此得兩個約束條件，這樣就將LP的可行域分割成兩個不相交的子集。將這兩個約束分別加入LP得兩個新問題，即兩個分枝LP1和LP2。步驟3：定界。設LP的最優(yōu)值為，則它是IP最優(yōu)值的上界，任取IP的一個可行解，對應目標值記為，它是的下界（初次下界可以取“”），即有：15可編輯ppt分枝定界法求解步驟步驟1：求解原問題的松弛問題（用LP表示）分枝定界法求解步驟步驟4：解每一分枝，并根據(jù)不同情況采取以下步驟：（1）若無可行解，則將該分枝剪掉

6、，不再考慮。（2）若是整數(shù)解且其最優(yōu)值，則該分枝的解就是原整數(shù)規(guī)劃問題的最優(yōu)解，結束。（3）若是整數(shù)解，但最優(yōu)值，則取為新的下界，該枝關閉。（4）若是非整數(shù)解且，則該分枝中不包含原問題的最優(yōu)解，該枝關閉。（5）若是非整數(shù)解，且又是平行各分枝中的最大目標函數(shù)值，則取為新的上界，同時將該枝視為新的LP，回到步驟2。步驟5：各分枝均已查清，對應最優(yōu)目標值的解即是原問題的最優(yōu)解。16可編輯ppt分枝定界法求解步驟步驟4：解每一分枝，并根據(jù)不同情況采取以下第三節(jié) 01規(guī)劃如果整數(shù)規(guī)劃問題中的所有決策變量僅限于取0或者1兩個值，則稱此問題為01整數(shù)規(guī)劃，簡稱01規(guī)劃，其變量稱為01變量。如果整數(shù)規(guī)劃問題中

7、的部分決策變量為01變量，則稱為01混合整數(shù)規(guī)劃。 17可編輯ppt第三節(jié) 01規(guī)劃如果整數(shù)規(guī)劃問題中的所有決策變量僅限于01規(guī)劃的求解列舉法隱枚舉法18可編輯ppt01規(guī)劃的求解列舉法18可編輯ppt隱枚舉法19可編輯ppt隱枚舉法19可編輯ppt第四節(jié) 指派問題 指派問題的標準形式20可編輯ppt第四節(jié) 指派問題 指派問題的標準形式20可編輯ppt價值系數(shù) 效率矩陣 決策變量 21可編輯ppt價值系數(shù) 效率矩陣 決策變量 21可編輯ppt指派問題求解匈牙利法推論：若將指派問題的效率矩陣每一行及每一列分別減去各行及各列的最小元素，則得到的新指派問題與原指派問題有相同的最優(yōu)解。定義：在效率矩陣

8、C中，有一組在不同行不同列的零元素，稱為獨立零元素組，此時每個元素稱為獨立零元素。定理1 設指派問題的效率矩陣為 ，若將該矩陣的某一行（或某一列）的各個元素都減去同一常數(shù) （ 可正可負），得到新的效率矩陣 ，則以 為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。但其最優(yōu)解比原最優(yōu)值減少 。 22可編輯ppt指派問題求解匈牙利法推論：若將指派問題的效率矩陣每一行及每行減掉其所在行最小值，然后每列再減其所在列最小值 指派指派方案最優(yōu)值為5665=22 23可編輯ppt每行減掉其所在行最小值，然后每列再減其所在列最小值 指派指派例3-12 24可編輯ppt例3-12 24可編輯ppt（1）對中所有

9、不含元素的行打，如第3行。（2）對打的行中，所有打零元素所在的列打，如第1列。（3）對所有打列中元素所在行打，如第2行。（4）重復上述（2）、（3）步，直到不能進一步打為止。（5）對未打的每一行劃一直線，如第1、3、5行。對已打的每一列劃一縱線，如第1列，既得到覆蓋當前0元素的最少直線數(shù)。 25可編輯ppt（1）對中所有不含元素的行打，如第3行。25可編輯ppt在未被直線覆蓋過的元素中找最小元素，將打行的各元素減去這個最小元素，將打列的各元素加上這個最小元素（以避免打行中出現(xiàn)負元素），這樣就增加了零元素的個數(shù)。26可編輯ppt在未被直線覆蓋過的元素中找最小元素，將打行的各元素減去這個最優(yōu)指派方

10、案是：讓小組1完成任務3；小組2完成任務2；小組3完成任務1；小組4完成任務4；小組5完成任務5 總成本 79666=34 27可編輯ppt最優(yōu)指派方案是：讓小組1完成任務3；小組2完成任務2；小組3非標準形式的指派問題 最大化指派問題人數(shù)和工作數(shù)不等 某事一定不能由某人來做 一個人可做幾件事 28可編輯ppt非標準形式的指派問題 最大化指派問題28可編輯ppt第五節(jié) 物流資源分配問題29可編輯ppt第五節(jié) 物流資源分配問題29可編輯ppt本章小結本章在線性規(guī)劃的基礎上，結合物流問題實際，提出了決策變量部分或者全部限制為整數(shù)時的一般線性整數(shù)規(guī)劃問題，通過與相應的線性規(guī)劃進行比較，說明了整數(shù)規(guī)劃問題需要探求新的求解方法，接著重點闡述了求解整數(shù)規(guī)劃問題的兩類基本方法：割平面法與分枝定界法。作為整數(shù)規(guī)劃的特例，專門討論了決策變量僅取0、1兩個值時相應整數(shù)規(guī)劃及其求解方法。最后介紹了整數(shù)規(guī)劃在物流資源分配中的應用。本章重點和難點是求解一般整數(shù)規(guī)劃的分枝定界法、割平面法原理與具體計算方法；標準指派問題及其匈牙利解法；整數(shù)規(guī)劃在物流領域中的有效運用。 30可編輯ppt本章小結本章在線性規(guī)劃的基礎上，結合物流問題實際，提出了決策案例分析（1）現(xiàn)代配送中心規(guī)劃時考慮的因素、目標和約束條件的限制主要有哪些？（2）案例中建模的過程及模型的含義？（3）整數(shù)規(guī)劃可以應用在哪些實際問題中？31可編輯