,整數規劃 制作：傅明睿,Mathematical modeling,整數規劃是什么?,規劃中的變量（部分或全部）限制為整數時，稱為整數規劃。若在線性規劃模型中，變量限制為整數，則稱為整數線性規劃。目前所流行的求解整數規劃的方法，往往只適用于整數線性規劃。目前還沒有一種方法能有效地求解一切整數規劃。,Mathematical modeling,整數規劃的分類,變量全限制為整數時，稱純（完全）整數規劃。 變量部分限制為整數的，稱混合整數規劃。 變量只能取0或1時，稱之為0-1整數規劃。,Mathematical modeling,整數規劃模型的建立 整數規劃模型的求解 完全枚舉法 分支定界法 割平面法 0-1數規劃模整型,Mathematical modeling,例1 集裝箱運貨問題： 已知甲乙兩種貨物的裝運和獲利情況如下表所示，問：甲乙兩貨物各托運多少箱，可使獲得利潤最大？,Mathematical modeling,解：設 為甲乙兩貨物各托運箱數,Mathematical modeling,(1) 原線性規劃有最優解，當自變量限制為整數后，其整數規劃解出現下述情況： a原線性規劃最優解全是整數，則整數規劃最優解與線性規劃最優解一致。 b原線性規劃最優解不全是整數，則整數規劃最優解小于原線性規劃最優解（max）或整數規劃最優解大于原線性規劃最優解（min）。,Mathematical modeling,例2 今有一臺機器將一周生產的兩種型號的冷飲杯存儲在150立方米的儲藏室 里,并同時進行出售.已知這臺機器能在6小時內生產一百箱號杯,5小時內生產一百箱號杯,生產以百箱為單位計算,預計每周生產60小時.如果號杯每百箱占體積10立方米,每百箱可獲利潤500元,每周售出數量不會超過800箱;號杯每百箱占體積20立方米, 每百箱可獲利潤450元,每周售出數量不受限制.為保證總收益為最大,每周應安排生產、號杯各多少百箱？,Mathematical modeling,解: 設每周生產、號杯各 百箱,則有如下數學模型,返回,Mathematical modeling,例3：設整數規劃問題如下,完全枚舉法,Mathematical modeling,現求整數解（最優解）：如用“舍入取整法”可得到4個點即(1，3) (2，3)(1，4)(2，4)。顯然，它們都不可能是整數規劃的最優解。 故按整數規劃約束條件，其可行解肯定在線性規劃問題的可行域內且為整數點。故整數規劃問題的可行解集是一個有限集，如圖所示。,求得（2，2）（3，1）點為最大值，。 在求解整數規劃問題時，可將集合內的整數點一一找出，其最大目標函數的值為最優解，此法為完全枚舉法。,返回,Mathematical modeling,對有約束條件的最優化問題（其可行解為有限數）的所有可行解空間恰當地進行系 統搜索，這就是分枝與定界內容。通常，把全部可行解空間反復地分割為越來越小的子 集，稱為分枝；并且對每個子集內的解集計算一個目標下界（對于最小值問題），這稱 為定界。在每次分枝后，凡是界限超出已知可行解集目標值的那些子集不再進一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。,分支定界法,Mathematical modeling,例4 用分支定界法求以下整數規劃,Mathematical modeling,Mathematical modeling,開始,V0 X1=2.25,X2=3.75;Z0=41.25,X23,X24,V1 X1=3,X2=3,Z2=39,V2 X1=1.8,X2=4,Z1=41,X12,X11,V3 X1=1,X2=4.44, Z4=40.56,V6 X1=0,X2=5,Z6=40,V5 X1=1,X2=4,Z5=37,V4 不可行,X24,X25,Mathematical modeling,0-1整數規劃,1.什么是0-1整數規劃？ 2.什么時候采用0-1整數規劃法？,0-1 整數規劃是一種特殊形式的整數規劃，這時的決策變量xi 只取兩個值0或1，一般的解法為隱枚舉法。,正如計算機只懂得0,1兩個數，1代表是，0代表否。同樣的，在0-1整數規劃中的0和1并不是真真意義上的數，而是一個衡量事件是否發生的標準。一般來說，我們在從多個事物中選出其中一部分，在一定的條件下求解最優情況時可以采用0-1整數規劃法。,Mathematical modeling,例5一個旅行者要到某地作兩周的帶包旅行,裝背包時,他發現除了已裝的必需物件外,他還能再裝5公斤重的東西.他打算從下列4種東西中選取,使增加的重量不超過5公斤又能使使用價值最大.這4種東西的重量和使用價值(這里用打分數的辦法表示價值)如下表所示,問旅行者應該選取哪些物件為好？,Mathematical modeling,解：建立模型為,Mathematical modeling,Mathematical modeling,由上表可知，問題的最優解為 X*=( x1 =1 x2=0 x3=1 ) 但此法太繁瑣，工作量相當大。而隱枚舉法就是在此基礎上，通過加入一定的條件，就能較快的求得最優解： 找到x1 =0 x2=0 x3=1 是一個可行解，為盡快找到最優解，可將3 x12 x25 x3 5 作為一個約束，凡是目標函數值小于5 的組合不必討論，如下表。,Mathematical modeling,例6 求解下列0-1規劃問題,Mathematical modeling,解：對于0-1 規劃問題，由于每個變量只取0，1兩個值，一般會用窮舉法來解，即將所有的0，1 組合找出，使目標函數達到極值要求就可求得最優解。,Mathematical modeling,例7(指派問題) 有5個工人，要分派他們分別