運(yùn)籌學(xué)OperationsResearch1.整數(shù)規(guī)劃數(shù)學(xué)模型MathematicalModelof

IP2.分枝定界法BranchandBoundMethod3.割平面法cutting-plane

Method4.0－1規(guī)劃

BinaryIntegerProgramming5.指派問(wèn)題AssignmentProblemChapter5整數(shù)規(guī)劃IntegerProgramming4/8/2025一個(gè)規(guī)劃問(wèn)題中要求部分或全部決策變量是整數(shù)，則這個(gè)規(guī)劃稱為整數(shù)規(guī)劃。當(dāng)要求全部變量取整數(shù)值的，稱為純整數(shù)規(guī)劃；只要求一部分變量取整數(shù)值的，稱為混合整數(shù)規(guī)劃。如果模型是線性的，稱為整數(shù)線性規(guī)劃。本章只討論整數(shù)線性規(guī)劃。很多實(shí)際規(guī)劃問(wèn)題都屬于整數(shù)規(guī)劃問(wèn)題.例如1.變量是人數(shù)、機(jī)器設(shè)備臺(tái)數(shù)或產(chǎn)品件數(shù)等都要求是整數(shù)2.對(duì)某一個(gè)項(xiàng)目要不要投資的決策問(wèn)題，可選用一個(gè)邏輯變量x，當(dāng)x=1表示投資，x=0表示不投資；3.人員的合理安排問(wèn)題，當(dāng)變量xij=1表示安排第i人去做j工作，xij=0表示不安排第i人去做j工作。邏輯變量也是只允許取整數(shù)值的一類變量。4/8/2025【例5.1】某人有一背包可以裝10公斤重、0.025m3的物品。他準(zhǔn)備用來(lái)裝甲、乙兩種物品，每件物品的重量、體積和價(jià)值如表5－1所示。問(wèn)兩種物品各裝多少件，所裝物品的總價(jià)值最大？表5—1物品重量（公斤/每件）體積（m3/每件）價(jià)值(元/每件)甲乙1.20.80.0020.002543【解】設(shè)甲、乙兩種物品各裝x1、x2件，則數(shù)學(xué)模型為：(5.1)4/8/2025如果不考慮x1、x2取整數(shù)的約束（稱為（5.1）的松弛問(wèn)題），線性規(guī)劃的可行域如圖5—1中的陰影部分所示。圖5－14/8/2025用圖解法求得點(diǎn)B為最優(yōu)解：X＝(3.57，7.14)，Z＝35.7。由于x1，x2必須取整數(shù)值，實(shí)際上整數(shù)規(guī)劃問(wèn)題的可行解集只是圖中可行域內(nèi)的那些整數(shù)點(diǎn)。用湊整法來(lái)解時(shí)需要比較四種組合，但（4，7）、（4，8）（3，8）都不是可行解，（3，7）雖屬可行解，但代入目標(biāo)函數(shù)得Z=33,并非最優(yōu)。實(shí)際上問(wèn)題的最優(yōu)解是（5，5），Z=35。即兩種物品各裝5件，總價(jià)值35元。由圖5－1知，點(diǎn)（5，5）不是可行域的頂點(diǎn)，直接用圖解法或單純形法都無(wú)法求出整數(shù)規(guī)劃問(wèn)題的最優(yōu)解，因此求解整數(shù)規(guī)劃問(wèn)題的最優(yōu)解需要采用其它特殊方法。還有些問(wèn)題用線性規(guī)劃數(shù)學(xué)模型無(wú)法描述，但可以通過(guò)設(shè)置邏輯變量建立起整數(shù)規(guī)劃的數(shù)學(xué)模型。4/8/2025【例5.2】在例5.1中，假設(shè)此人還有一只旅行箱，最大載重量為12公斤，其體積是0.02m3。背包和旅行箱只能選擇其一，建立下列幾種情形的數(shù)學(xué)模型，使所裝物品價(jià)值最大。（1）

所裝物品不變；（2）

如果選擇旅行箱，載重量和體積的約束為解：此問(wèn)題可以建立兩個(gè)整數(shù)規(guī)劃模型，但用一個(gè)模型描述更簡(jiǎn)單。引入0－1變量（或稱邏輯變量）yi，令i=1,2分別是采用背包及旅行箱裝載。4/8/2025（1）

由于所裝物品不變，式(8.1)約束左邊不變，整數(shù)規(guī)劃數(shù)學(xué)模型為（2）

由于不同載體所裝物品不一樣，數(shù)學(xué)模型為4/8/2025式中M為充分大的正數(shù)。從上式可知，當(dāng)使用背包時(shí)(y1=1，y2=0)，式(b)和(d)是多余的；當(dāng)使用旅行箱時(shí)(y1=0，y2=1)，式(a)和(c)是多余的。上式也可以令：同樣可以討論對(duì)于有m個(gè)條件互相排斥、有m（≤m、≥m）個(gè)條件起作用的情形。4/8/2025【例5.3】企業(yè)計(jì)劃生產(chǎn)2000件某種產(chǎn)品，該種產(chǎn)品可利用Ａ、Ｂ、Ｃ設(shè)備中的任意一種加工。已知每種設(shè)備的生產(chǎn)準(zhǔn)備結(jié)束費(fèi)用、生產(chǎn)該產(chǎn)品時(shí)的單件成本以及每種設(shè)備限定的最大加工數(shù)量（件）如下表所示，試建立總成本最小的數(shù)學(xué)模型。設(shè)備生產(chǎn)準(zhǔn)備結(jié)束費(fèi)（元）生產(chǎn)成本（元／件）限定最大加工數(shù)（件）Ａ１００１０６００Ｂ３００２８００Ｃ２００５１２００4/8/2025【解】設(shè)xj表示在第j（j=1,2,3）種設(shè)備上加工的產(chǎn)品數(shù)量，其生產(chǎn)費(fèi)用為：式中Kj是同產(chǎn)量無(wú)關(guān)的生產(chǎn)準(zhǔn)備費(fèi)用（即固定費(fèi)用），cj是單位產(chǎn)品成本。設(shè)0－1變量yj，令目標(biāo)函數(shù)為4/8/2025式中是一個(gè)特殊的約束條件，顯然當(dāng)xj>0時(shí)，yj=1,當(dāng)xj＝0時(shí)，為使Z極小化，只有yj=0才有意義。用QSB軟件求解得到：X＝（0，800，1200），Y＝（0，1，1），Z=8100.如果問(wèn)題的所有變量取0或1，此問(wèn)題稱為0－1整數(shù)規(guī)劃問(wèn)題，簡(jiǎn)稱0－1規(guī)劃。4/8/2025【例5.4】指派問(wèn)題或分配問(wèn)題。人事部門欲安排四人到四個(gè)不同崗位工作，每個(gè)崗位一個(gè)人。經(jīng)考核四人在不同崗位的成績(jī)（百分制）如表5－3所示，如何安排他們的工作使總成績(jī)最好。表5－3工作人員ABCD甲85927390乙95877895丙82837990丁869080884/8/2025【解】此工作分配問(wèn)題可以采用枚舉法求解，即將所有分配方案求出，總分最大的方案就是最優(yōu)解。本例的方案有4！＝4×3×2×1＝24種，當(dāng)人數(shù)和工作數(shù)較多時(shí)，方案數(shù)是人數(shù)的階乘，計(jì)算量非常大。用0－1規(guī)劃模型求解此類分配問(wèn)題顯得非常簡(jiǎn)單。設(shè)數(shù)學(xué)模型如下：目標(biāo)函數(shù)為要求每人做一項(xiàng)工作，約束條件為4/8/202