1、,3.1 整數(shù)規(guī)劃數(shù)學模型 Mathematical Model of IP 3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming 3.3 01規(guī)劃的求解 Solving Binary Integer Programming,Chapter 3 整數(shù)規(guī)劃 Integer Programming,運籌學 Operations Research,3.1 整數(shù)規(guī)劃數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,一個規(guī)劃問題中要求部分或全部決策變量是整數(shù)，則這個規(guī)劃稱為整數(shù)規(guī)劃。當要求全部變量取整數(shù)值的，稱為純整數(shù)規(guī)劃；只要求

2、一部分變量取整數(shù)值的，稱為混合整數(shù)規(guī)劃。如果模型是線性的，稱為整數(shù)線性規(guī)劃。本章只討論整數(shù)線性規(guī)劃。,很多實際規(guī)劃問題都屬于整數(shù)規(guī)劃問題,1. 變量是人數(shù)、機器設(shè)備臺數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù) 2. 對某一個項目要不要投資的決策問題，可選用一個邏輯變量 x，當x=1表示投資，x=0表示不投資； 3. 人員的合理安排問題，當變量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。邏輯變量也是只允許取整數(shù)值的一類變量。,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,【例3-1 】某人有一背包可以裝10公斤重、0.025

3、m3的物品。他準備用來裝甲、乙兩種物品，每件物品的重量、體積和價值如表3-1所示。問兩種物品各裝多少件，所裝物品的總價值最大？,表3-1,【解】設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學模型為：,(3-1),3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,如果不考慮x1、x2取整數(shù)的約束（稱為（3-1）的松弛問題），線性規(guī)劃的可行域如圖3-1中的陰影部分所示。,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,圖3-1,2020年9月5日星期六,用圖解法求得點B為最優(yōu)解：X(3.57，7.14)，Z35.7。由于

4、x1，x2必須取整數(shù)值，實際上整數(shù)規(guī)劃問題的可行解集只是圖中可行域內(nèi)的那些整數(shù)點。用湊整法來解時需要比較四種組合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）雖屬可行解，但代入目標函數(shù)得Z=33,并非最優(yōu)。實際上問題的最優(yōu)解是（5，5），Z=35。即兩種物品各裝5件，總價值35元。,由圖31知，點（5，5）不是可行域的頂點，直接用圖解法或單純形法都無法求出整數(shù)規(guī)劃問題的最優(yōu)解，因此求解整數(shù)規(guī)劃問題的最優(yōu)解需要采用其它特殊方法。,還有些問題用線性規(guī)劃數(shù)學模型無法描述，但可以通過設(shè)置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學模型。,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model

5、of IP,2020年9月5日星期六,【例3-2 】在例3-1中，假設(shè)此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其一，建立下列幾種情形的數(shù)學模型，使所裝物品價值最大。 （1）所裝物品不變； （2）如果選擇旅行箱，則只能裝載丙和丁兩種物品，價值分別是4和3，載重量和體積的約束為,【解】此問題可以建立兩個整數(shù)規(guī)劃模型，但用一個模型描述更簡單。引入01變量（或稱邏輯變量）yi，令,i=1,2分別是采用背包及旅行箱裝載。,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,（1） 由于所裝物品不變，式(3-1

6、)約束左邊不變，整數(shù)規(guī)劃數(shù)學模型為,（2） 由于不同載體所裝物品不一樣，數(shù)學模型為,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,式中M為充分大的正數(shù)。從上式可知，當使用背包時(y1=1，y2=0)，式(b)和(d)是多余的；當使用旅行箱時(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：,同樣可以討論對于有m個條件互相排斥、有m（m、m）個條件起作用的情形。,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,（1)右端常數(shù)是k個值中的一個時，類似式(3-2)的約束條件

7、為,（2)對于m組條件中有k（m）組起作用時，類似式(3-3)的約束條件寫成,這里yi=1表示第i組約束不起作用（如y1=1式(3-3b)、(3-3d)不起作用），yi=0表示第i個約束起作用。當約束條件是“”符號時右端常數(shù)項應(yīng)為,（3) 對于m個條件中有k（m）個起作用時，約束條件寫成,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,【例3-3】試引入01變量將下列各題分別表達為一般線性約束條件 （1）x1+x26或4x1+6x210或2x1+4x220 （2）若x15，則x20，否則x28 （3）x取值0，1，3，5，7,【解】 （1

8、）3個約束只有1個起作用,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,或,2020年9月5日星期六,（3）右端常數(shù)是5個值中的1個,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,（2）兩組約束只有一組起作用,2020年9月5日星期六,【例3-4】企業(yè)計劃生產(chǎn)4000件某種產(chǎn)品，該產(chǎn)品可自己加工、外協(xié)加工任意一種形式生產(chǎn)已知每種生產(chǎn)的固定費用、生產(chǎn)該產(chǎn)品的單件成本以及每種生產(chǎn)形式的最大加工數(shù)量（件）限制如表32所示，怎樣安排產(chǎn)品的加工使總成本最小,表32,【解】設(shè)xj為采用第j（j=1,2,3）種方式生產(chǎn)的產(chǎn)品數(shù)量，生產(chǎn)費用為,3

9、.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,2020年9月5日星期六,式中kj是固定成本，cj是單位產(chǎn)品成本設(shè)01變量yj，令,數(shù)學模型為,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,（3-4）,式（3-4）中 是處理xj與yj一對變量之間邏輯關(guān)系的特殊約束，當xj0時yj=1, 當xj0時，為使Z最小化，有yj=0。 例3-4是混合整數(shù)規(guī)劃問題用WinQSB軟件求解得到： X(0，2000，2000)T，Y(0，1，1)T，Z=25400.,2020年9月5日星期六,作業(yè)：教材習題 3.13.7,1.線性整數(shù)規(guī)劃模型的特征 2

10、.什么是純（混合）整數(shù)規(guī)劃 3.01規(guī)劃模型的應(yīng)用,3.1 整數(shù)規(guī)劃的數(shù)學模型 Mathematical Model of IP,下一節(jié)：純整數(shù)規(guī)劃的求解,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,分枝定界法的步驟：,1. 求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 2.若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步； 3.任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束xixi及xixi+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時

11、，目標值是分枝問題的下界； 4. 檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算,若還存在非整數(shù)解并且目標值大于（max）整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。,3.2.1求解純整數(shù)規(guī)劃的分枝定界法,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,【例3-5 】用分枝定界法求解例5.1,【解】先求對應(yīng)的松弛問題（記為LP0）：,用圖解法得到最優(yōu)解X（3.57,7.14）,Z0=35.7,如下圖所示。,3.2 純整數(shù)規(guī)劃的求解 Solv

12、ing Pure Integer Programming,2020年9月5日星期六,8.33,10,松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7,x1,x2,o,A,B,C,10,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,10,10,x1,x2,o,A,B,C,LP1,LP2,3,4,LP1:X=(3,7.6),Z1=34.8,LP2:X=(4,6.5),Z2=35.5,10,10,x1,x2,o,A,B,C,LP1,LP3,3,4,LP3:X=(4.33,6),Z3=35.33,6,LP1:X=(3,7.6),Z1=34.

13、8,10,10,x1,x2,o,A,C,LP1,3,4,6,LP4:X=(4,6),Z4=34,LP5:X=(5,5),Z5=35,5,LP1:X=(3,7.6),Z1=34.8,LP3,LP5,盡管LP1的解中x1不為整數(shù)，但Z5Z因此LP5的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解。,上述分枝過程可用下圖表示,LP0:X=(3.57,7.14),Z0=35.7,LP1:X=(3,7.6) Z1=34.8,LP2:X=(4,6.5) Z2=35.5,x13,x14,LP3:X=(4.33,6) Z3=35.33,x26,LP4:X=(4,6) Z4=34,LP5:X=(5,5) Z5=35,x14,x1

14、5,無可行解,x27,2020年9月5日星期六,設(shè)純整數(shù)規(guī)劃,松弛問題,的最優(yōu)解,設(shè)xi不為整數(shù)，,3.2.2 求解IP的割平面法,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,將 分離成一個整數(shù)與一個非負真分數(shù)之和：,則有,等式兩邊都為整數(shù)并且有,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,加入松弛變量si得,此式稱為以xi行為源行（來源行）的割平面，或分數(shù)切割式，或R.E.Gomory(高莫雷)約束方程。,將Gomory約束加入到松弛問題的最優(yōu)表

15、中，用對偶單純形法計算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部為整數(shù)解。,則,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,例如，,x1行：,移項：,令,加入松弛變量s1得,同理，對于x2行有：,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,【例3-6】 用割平面法求解下列IP問題,【解】 放寬變量約束，對應(yīng)的松弛問題是,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,加入松弛

16、變量x3及x4后，用單純形法求解，得到最優(yōu)表3-3。,最優(yōu)解X(0)(5/2，15/4),不是IP的最優(yōu)解。選擇表3-3的第一行(也可以選第二行)為源行,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,表3-3,2020年9月5日星期六,分離系數(shù)后改寫成,加入松弛變量x5得到高莫雷約束方程,將式(3-8)作為約束條件添加到表33中，用對偶單純形法計算，如表34所示,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,2020年9月5日星期六,最優(yōu)解X(1)(3，3)，最優(yōu)值Z21。所有變量為整數(shù)，X(1)就是I

17、P的最優(yōu)解。如果不是整數(shù)解，需要繼續(xù)切割，重復上述計算過程。,3.2 純整數(shù)規(guī)劃的求解 Solving Pure Integer Programming,表34,如果在對偶單純形法中原切割方程的松弛變量仍為基變量，則此松弛變量所在列化為單位向量后就可以去掉該行該列，再切割。,2020年9月5日星期六,作業(yè)：教材習題 3.8，3.9,1.理解分枝與定界的含義 2.選擇合適的“ 枝”生“ 枝” 3.掌握何時停止生“ 枝” 4.領(lǐng)會割平面法的基本原理 5.分離源行，求出Gomory約束 6.在最優(yōu)表中增加Gomory約束，用 對偶單純形法迭代,3.2 純整數(shù)規(guī)劃的求解 Solving Pure In

18、teger Programming,下一節(jié)： 01規(guī)劃的求解,3.3 01規(guī)劃的求解 Solving BIP,2020年9月5日星期六,3.3.1 求解01整數(shù)規(guī)劃的隱枚舉法,隱枚舉法的步驟：,1.找出任意一可行解，目標函數(shù)值為Z0,2. 原問題求最大值時，則增加一個約束,當求最小值時，上式改為小于等于約束,3. 列出所有可能解，對每個可能解先檢驗式（*），若滿足再檢驗其它約束，若不滿足式（*），則認為不可行，若所有約束都滿足，則認為此解是可行解，求出目標值,4. 目標函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解,3.3 01規(guī)劃的求解 Solving BIP,2020年9月5日星期六,【例3-7】用隱枚舉法求解下列BIP問題,【解】（1）不難看出，當所有變量等于0或1的任意組合時