1、第三章第三章 整數(shù)規(guī)劃整數(shù)規(guī)劃 普通整數(shù)規(guī)劃問題普通整數(shù)規(guī)劃問題 整數(shù)規(guī)劃的解法整數(shù)規(guī)劃的解法 01規(guī)劃規(guī)劃 指派問題指派問題 物流資源分配問題物流資源分配問題知識目的知識目的掌握整數(shù)規(guī)劃的根本方式；掌握整數(shù)規(guī)劃的根本方式；掌握分枝定界法計算過程；掌握分枝定界法計算過程；了解割平面法；了解割平面法；掌握掌握01規(guī)劃的規(guī)范方式；規(guī)劃的規(guī)范方式；了解了解01變量的運(yùn)用；變量的運(yùn)用；掌握掌握01規(guī)劃的匈牙利解法。規(guī)劃的匈牙利解法。技藝目的技藝目的可以結(jié)合實踐情況建立整數(shù)規(guī)劃模型，并可利用分可以結(jié)合實踐情況建立整數(shù)規(guī)劃模型，并可利用分枝枝 定界法求解；定界法求解；可以運(yùn)用可以運(yùn)用01規(guī)劃建模并求解，安

2、排人員任務(wù)。規(guī)劃建模并求解，安排人員任務(wù)。第一節(jié) 普通整數(shù)規(guī)劃問題 什么是整數(shù)規(guī)劃問題？ 整數(shù)規(guī)劃的普通方式：max z（ 或min z） =1njjjc x 112( , )1,2,. .01,2,nijjijjna xbims txjnxxx 取整數(shù) 第二節(jié) 整數(shù)規(guī)劃的解法 割平面法 分枝定界法例3-5 12121212maxz129452028,0 xxxxxxx x割平面法 根本思想：求原問題對應(yīng)松弛問題最優(yōu)解，假設(shè)不是原問題的可行解，那么經(jīng)過引入線性約束條件即割平面，使松弛問題的可行域逐漸減少即切掉一部分，每次切割掉的是松弛問題的非整數(shù)解的一部分，但不切掉任何整數(shù)解，直到最后使目的函

3、數(shù)到達(dá)最優(yōu)的整數(shù)解成為可行域的一個頂點(diǎn)時，即為原問題的最優(yōu)解。其本質(zhì)是利用線性規(guī)劃的求解方法逐漸減少可行域，最后找到整數(shù)規(guī)劃的最優(yōu)解。 例3-6 2121212max 326320,0zxxxxxx x且為整數(shù)234113442xxx234111(0)(0)1442xxx 2341111244xxx 341110244xx341111442xxs jjjczjjjcz412222333xss 2121212max 326320,0zxxxxxx x且為整數(shù)割平面法的求解步驟 步驟1：求解原問題的松弛問題，得最優(yōu)解，假設(shè)滿足整數(shù)約束，那么即為最優(yōu)解，否那么進(jìn)入下一步；步驟2：分解其中一個非整分量

4、，構(gòu)造一個新的線性約束條件，參與原松弛問題中，構(gòu)成新的線性規(guī)劃；步驟3：求解新線性規(guī)劃問題，得，假設(shè)為整數(shù)那么為原問題的最優(yōu)解，否那么進(jìn)入步驟2。按某非整分量構(gòu)造的約束條件需滿足以下兩個條件：1當(dāng)前最優(yōu)解不滿足該約束，即使得該最優(yōu)解不會再出如今松弛問題可行解中；2一切整數(shù)可行解均滿足該約束，即新增約束條件后，仍保管了原松弛問題的一切整數(shù)解。分枝定界法 根本思想：求原問題的對應(yīng)的松弛問題，其最優(yōu)解假設(shè)不是原問題的可行解，那么經(jīng)過附加線性不等式約束整型，將松弛問題分枝變?yōu)榧僭O(shè)干子問題，即對每一個非整變量附加兩個相互排斥不交叉的整型約束，即得兩個子問題，繼續(xù)求解定界，反復(fù)下去，直到得到最優(yōu)解為止。例

5、3-7 用分枝定界法求解：12121212max43410. . 238,0zxxxxstxxx x且均為整數(shù)011 6(, )5 5x 0625z 12121212max43410. . 238,0zxxxxstxxx x且均為整數(shù)011 6(, )5 5x 0625z 分枝定界法求解步驟步驟1：求解原問題的松弛問題用LP表示，得最優(yōu)解，假設(shè)滿足整數(shù)約束，那么即為最優(yōu)解，否那么進(jìn)入下步。步驟2：分枝。任選的一個不為整的分量，設(shè)為其中為整數(shù)部分，為小數(shù)部分，據(jù)此得兩個約束條件，這樣就將LP的可行域分割成兩個不相交的子集。將這兩個約束分別參與LP得兩個新問題，即兩個分枝LP1和LP2。步驟3：定

6、界。設(shè)LP的最優(yōu)值為，那么它是IP最優(yōu)值的上界，任取IP的一個可行解，對應(yīng)目的值記為，它是的下界初次下界可以取“，即有：分枝定界法求解步驟步驟4：解每一分枝，并根據(jù)不同情況采取以下步驟：1假設(shè)無可行解，那么將該分枝剪掉，不再思索。2假設(shè)是整數(shù)解且其最優(yōu)值，那么該分枝的解就是原整數(shù)規(guī)劃問題的最優(yōu)解，終了。3假設(shè)是整數(shù)解，但最優(yōu)值，那么取為新的下界，該枝封鎖。4假設(shè)是非整數(shù)解且，那么該分枝中不包含原問題的最優(yōu)解，該枝封鎖。5假設(shè)是非整數(shù)解，且又是平行各分枝中的最大目的函數(shù)值，那么取為新的上界，同時將該枝視為新的LP，回到步驟2。步驟5：各分枝均已查清，對應(yīng)最優(yōu)目的值的解即是原問題的最優(yōu)解。第三節(jié)

7、01規(guī)劃 假設(shè)整數(shù)規(guī)劃問題中的一切決策變量僅限于取0或者1兩個值，那么稱此問題為01整數(shù)規(guī)劃，簡稱01規(guī)劃，其變量稱為01變量。假設(shè)整數(shù)規(guī)劃問題中的部分決策變量為01變量，那么稱為01混合整數(shù)規(guī)劃。 01規(guī)劃的求解規(guī)劃的求解 列舉法 隱枚舉法隱枚舉法1231231231223123(0)(1)(2)(3) (4) max32522 44 3 46 ,01zxxxxxxxxxxxxxx x x或第四節(jié) 指派問題 指派問題的規(guī)范方式 價值系數(shù) ,1,2,ijci jn 效率矩陣 決策變量 指派問題求解匈牙利法k定理定理1 設(shè)指派問題的效率矩陣為設(shè)指派問題的效率矩陣為 ，假設(shè)將該矩陣的某一，假設(shè)將該

8、矩陣的某一行行或某一列的各個元素都減去同一常數(shù)或某一列的各個元素都減去同一常數(shù) 可正可負(fù)，得到可正可負(fù)，得到新的效率矩陣新的效率矩陣 ，那么以，那么以 為效率矩陣的新的指派問題為效率矩陣的新的指派問題與原指派問題的最優(yōu)解一樣。但其最優(yōu)解比原最優(yōu)值減少與原指派問題的最優(yōu)解一樣。但其最優(yōu)解比原最優(yōu)值減少 。 ijn nCck()ijn nCcCk例3-12 61012961081476781296101417971215784C31181773232154234C 31181773232154234C 131180662121010541234130118006620121010504123406

9、1012961081476781296101417971215784C非規(guī)范方式的指派問題 最大化指派問題 人數(shù)和任務(wù)數(shù)不等 某事一定不能由某人來做 一個人可做幾件事 第五節(jié) 物流資源分配問題本章小結(jié) 本章在線性規(guī)劃的根底上，結(jié)合物流問題實踐，提出了決策變量部分或者全部限制為整數(shù)時的普通線性整數(shù)規(guī)劃問題，經(jīng)過與相應(yīng)的線性規(guī)劃進(jìn)展比較，闡明了整數(shù)規(guī)劃問題需求探求新的求解方法，接著重點(diǎn)論述了求解整數(shù)規(guī)劃問題的兩類根本方法：割平面法與分枝定界法。作為整數(shù)規(guī)劃的特例，專門討論了決策變量僅取0、1兩個值時相應(yīng)整數(shù)規(guī)劃及其求解方法。最后引見了整數(shù)規(guī)劃在物流資源分配中的運(yùn)用。 本章重點(diǎn)和難點(diǎn)是求解普通整數(shù)規(guī)劃的分枝定界法、割平面法原理與詳細(xì)計算方法；規(guī)范指派問題及其匈牙利解法；整數(shù)規(guī)劃在物流領(lǐng)域中的有效運(yùn)用。 案例分析1現(xiàn)代配送中心規(guī)劃時思索的要素、目的和約束條件的限制主