第四章整數(shù)規(guī)劃與分配問題(第1講)

2023/2/11運籌學

OPERATIONSRESEARCH

2023/2/12第四章整數(shù)規(guī)劃與分配問題

（IntegerProgramming,IP)整數(shù)規(guī)劃的有關(guān)概念及特點整數(shù)規(guī)劃的求解方法：分枝定界法、割平面法指派問題及匈牙利解法整數(shù)規(guī)劃的應(yīng)用4.1整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)規(guī)劃（簡稱：IP）

要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃數(shù)學模型的一般形式：整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)線性規(guī)劃問題的種類：

純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃?；旌险麛?shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。

0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。一般形式依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0－1整數(shù)規(guī)劃。4.1.1整數(shù)規(guī)劃問題的數(shù)學模型2023/2/16純整數(shù)規(guī)劃：在整數(shù)規(guī)劃中，如果所有的變量都為非負整數(shù)，則稱為純整數(shù)規(guī)劃問題；混合整數(shù)規(guī)劃：如果有一部分變量為非負整數(shù)，則稱之為

混合整數(shù)規(guī)劃問題。0-1變量：在整數(shù)規(guī)劃中，如果變量的取值只限于0和1，這樣的變量我們稱之為0-1變量。0-1規(guī)劃：在整數(shù)規(guī)劃問題中，如果所有的變量都為0-1變量，則稱之為0-1規(guī)劃?！?整數(shù)規(guī)劃的有關(guān)概念及特點

一、概念整數(shù)規(guī)劃：要求決策變量取整數(shù)值的規(guī)劃問題。（線性整數(shù)規(guī)劃、非線性整數(shù)規(guī)劃等）2023/2/17求整數(shù)解的線性規(guī)劃問題，不是用四舍五入法或去尾法對性規(guī)劃的非整數(shù)解加以處理就能解決的，用枚舉法又往往會計算量太大，所以要用整數(shù)規(guī)劃的特定方法加以解決。例：求解下列整數(shù)規(guī)劃：二、整數(shù)規(guī)劃的求解特點2023/2/18分析：

若當作一般線性規(guī)劃求解，圖解法的結(jié)果如下。1、非整數(shù)規(guī)劃最優(yōu)解顯然不是整數(shù)規(guī)劃的可行解。2、四舍五入后的結(jié)果也不是整數(shù)規(guī)劃的可行解。3、可行解是陰影區(qū)域交叉點，可比較這些點對應(yīng)的函數(shù)值，找出最優(yōu)。2023/2/19分析：

若當作一般線性規(guī)劃求解，圖解法的結(jié)果如下。1、非整數(shù)規(guī)劃最優(yōu)解顯然不是整數(shù)規(guī)劃的可行解。2、四舍五入后的結(jié)果也不是整數(shù)規(guī)劃的可行解。3、可行解是陰影區(qū)域交叉點，可比較這些點對應(yīng)的函數(shù)值，找出最優(yōu)。整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)規(guī)劃的典型例子例1工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個。這種物資的需求地有B1,B2,B3,B4四個。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運費cij，見下表：B1B2B3B4年生產(chǎn)能力A12934400A28357600A37612200A44525200年需求量350400300150工廠A3或A4開工后，每年的生產(chǎn)費用估計分別為1200萬或1500萬元。現(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費用最少。整數(shù)規(guī)劃的特點及應(yīng)用解：這是一個物資運輸問題，特點是事先不能確定應(yīng)該建A3還是A4中哪一個，因而不知道新廠投產(chǎn)后的實際生產(chǎn)物資。為此，引入0-1變量：再設(shè)xij為由Ai運往Bj的物資數(shù)量，單位為千噸；z表示總費用，單位萬元。則該規(guī)劃問題的數(shù)學模型可以表示為：整數(shù)規(guī)劃的特點及應(yīng)用混合整數(shù)規(guī)劃問題整數(shù)規(guī)劃的特點及應(yīng)用例2現(xiàn)有資金總額為B?？晒┻x擇的投資項目有n個，項目j所需投資額和預期收益分別為aj和cj（j＝1,2,..,n），此外由于種種原因，有三個附加條件：若選擇項目1，就必須同時選擇項目2。反之不一定項目3和4中至少選擇一個；項目5,6,7中恰好選擇2個。應(yīng)該怎樣選擇投資項目，才能使總預期收益最大。整數(shù)規(guī)劃的特點及應(yīng)用解：對每個投資項目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個項目的決策選擇，記為：投資問題可以表示為：整數(shù)規(guī)劃的特點及應(yīng)用例4.3指派問題或分配問題。人事部門欲安排四人到四個不同崗位工作，每個崗位一個人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。

工作人員ABCD甲85927390乙95877895丙82837990丁86908088整數(shù)規(guī)劃的特點及應(yīng)用設(shè)數(shù)學模型如下：要求每人做一項工作，約束條件為：整數(shù)規(guī)劃的特點及應(yīng)用每項工作只能安排一人，約束條件為：變量約束：例

某人有一個背包可以裝5公斤重、0.02m3

的物品。他準備用來裝A、B兩種物品，每件物品的重量、體積和價值如表3-2所示。問兩種物品各裝多少件才能使所裝物品的總價值最大？表解：設(shè)A、B兩種物品的裝載件數(shù)分別為x1，x2，則該問題的數(shù)學模型為假設(shè)此人還有一只旅行箱，最大載重量為10公斤，其體積是0.018m3。背包和行李箱只能選擇其一，如果所需攜帶物品不變，問該如何裝載物品，使所裝物品價值最大？解：引入0-1變量（或稱邏輯變量）yi，令則該整數(shù)規(guī)劃數(shù)學模型為2023/2/121§2

應(yīng)用舉例

一、邏輯變量在數(shù)學模型中的應(yīng)用1、m個約束條件中只有k個起作用設(shè)有m個約束條件定義0-1整型變量：M是任意大正數(shù)。第i個約束起作用第i個約束不起作用則原約束中只有k個真正起作用的情況可表示為：2023/2/1222、約束條件右端項是r個可能值中的一個則通過定義約束條件右端項不是bi約束條件右端項是bi可將上述條件表示為2023/2/1233、兩組條件中滿足其中一組例如表示條件：若，則；否則時則通過定義第i組條件起作用，i=1，2第i組條件不起作用可將上述條件表示為又：M是任意大正數(shù)，2023/2/124定義4、表示含有固定費用的函數(shù)例如：表示產(chǎn)品j的生產(chǎn)數(shù)量，其生產(chǎn)費用函數(shù)為：目標函數(shù)：其中是與產(chǎn)量無關(guān)的生產(chǎn)準備費用則原問題可表示為整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)規(guī)劃問題解的特征：

整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個子集，任意兩個可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。整數(shù)規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標函數(shù)值不會優(yōu)于后者最優(yōu)解的目標函數(shù)值。整數(shù)規(guī)劃的特點及應(yīng)用例4.3設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。整數(shù)規(guī)劃的特點及應(yīng)用用圖解法求出最優(yōu)解為：x1＝3/2,x2=10/3，且有Z=29/6≈4.83

現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個點即(1，3),(2，3),(1，4),(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3)

按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如右圖所示。其中(2,2),(3,1)點的目標函數(shù)值最大，即為Z=4。整數(shù)規(guī)劃的特點及應(yīng)用整數(shù)規(guī)劃問題的求解方法：

分支定界法和割平面法匈牙利法（指派問題）思考:應(yīng)如何求解整數(shù)線性規(guī)劃問題(IP)?枚舉法2023/2/129§4

分枝定界法

分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問題，又能解決混合整數(shù)規(guī)劃的問題。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法編制而成的。下面舉例來說明分枝定界法的思想和步驟。2023/2/130性質(zhì)

求MAX的問題：整數(shù)規(guī)劃的最優(yōu)目標函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最優(yōu)目標函數(shù)值；

求MIN的問題：整數(shù)規(guī)劃的最優(yōu)目標函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最優(yōu)目標函數(shù)值。1、求解整數(shù)規(guī)劃相應(yīng)的一般線性規(guī)劃問題（即先去掉整數(shù)約束）。易知：整數(shù)規(guī)劃的可行域（?。┌诰€性規(guī)劃的可行域(大）。若線性規(guī)劃的最優(yōu)解恰是整數(shù)解，則其就是整數(shù)規(guī)劃的最優(yōu)解。否則該最優(yōu)解，是整數(shù)規(guī)劃最優(yōu)解的上界或下界。2023/2/131例：求解下列整數(shù)規(guī)劃：解：1、解對應(yīng)的線性規(guī)劃：其最優(yōu)解為，顯然不是整數(shù)規(guī)劃的可行解。L0：2023/2/1322、分枝與定界：將對應(yīng)的線性規(guī)劃問題分解成幾個子問題，每個子問題就是一分枝，而所有子問題的解集之和要包含原整數(shù)規(guī)劃的解集。

求解每一分枝子問題：若其最優(yōu)解滿足整數(shù)約束，則它就是原問題的一個可行解（不一定是最優(yōu)）；否則，就是該枝的上界或下界。

若所有分支的最優(yōu)解都不滿足整數(shù)條件（即不是原問題的可行解），則選取一個邊界值最優(yōu)的分支繼續(xù)分解，直至找到一個原問題的可行解。若在同一級分枝中同時出現(xiàn)兩個以上的原問題可行解，則保留目標值最優(yōu)的一個，其余不再考慮。從各分枝中找原問題可行解的目的是為下一步的比較與剪枝。2023/2/133將上述線性規(guī)劃問題分為兩枝，并求解。解得解得L1：L2：顯然兩個分枝均非整數(shù)可行解，選邊界值較大的L1繼續(xù)分枝。2023/2/134將L1分為兩枝，并求解。解得解得L11：L12：兩個分枝均是整數(shù)可行解，保留目標值較大的L12。2023/2/1353、比較與剪枝將各子問題的邊界值與保留下的整數(shù)可行解對應(yīng)的目標值比較，將邊界值劣于可行行解的分支減剪去。

若比較剪枝后，只剩下所保留的整數(shù)可行解，則該解就是原整數(shù)規(guī)劃的最優(yōu)解；否則選取邊界值最大的一個分枝繼續(xù)分解，在其后的過程中出現(xiàn)新的整數(shù)可行解時，則與原可行解比較，保留較優(yōu)的一個，重復第三步。2023/2/136L0：X2≤2X2≥3X1≤3X1≥4用圖表示上例的求解過程與求解結(jié)果2023/2/137§5

割平面法

一、基本思想在整數(shù)規(guī)劃的松弛問題中，依次引進新的約束條件（割平面），使問題的可行域逐步減小，但每次割去的只是部分非整數(shù)解，直到使問題的目標函數(shù)值達到最優(yōu)的整數(shù)點成為縮小后的可行域的一個頂點，這樣就可以用線性規(guī)劃的方法求得整數(shù)最優(yōu)解。2023/2/138例：求解下列整數(shù)規(guī)劃：解：1、解對應(yīng)的線性規(guī)劃（松弛問題），并將約束條件的系數(shù)均化為整數(shù)：2023/2/139加入松弛變量后求解，得最終單純形表：25/2011/2-1/2313/410-1/43/400-1/4-5/4如果上述求解結(jié)果是整數(shù)解，則結(jié)束；否則轉(zhuǎn)下一步；2、找出非整數(shù)解中分數(shù)部分最大的一個基變量，并將該行對應(yīng)的約束方程所有常數(shù)（系數(shù)及常數(shù)項）分解成一個整數(shù)與一個正分數(shù)之和；將所有分式項移到等式右端。例如上例，取第一行約束2023/2/140易知，左端為整數(shù)，要是等式成立，右端也必為整數(shù)，且將代入上式，得2023/2/141這就是一個割平面。將其添加到原約束中，得到新的可行域如圖所示。割去的只是部分非整數(shù)解。2023/2/1423、將新的約束添加到原問題中，得到一個新的線性規(guī)劃問題，求解此問題，可用靈敏度分析的方法。4、重復上述的1-3步，直至求出整數(shù)最優(yōu)解。25/2011/2-1/20313/410-1/43/400-1/200-1/2-1/2100-1/4-5/40將反應(yīng)到最終表中，得2023/2/143運用對偶單純形法，解得22010-11/231001-1/2010011-2000-1-1/2此解仍非整數(shù)解，將基變量對應(yīng)的約束分解為：得到新的約束2023/2/14422010-11/2031001-1/20010011-200-1/20000-1/21000-1-1/2021010-1023410010-10300110-40100001-2000-10-1此時已得整數(shù)最優(yōu)解。2023/2/145約束即為分支定界法1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界： 任意選一個非整數(shù)解的變量xi，在松弛問題中加上約束：xi≤[xi]和xi≥[xi]+1組成兩個新的松弛問題，稱為分枝。新的松弛問題具有特征：當原問題是求最大值時，目標值是分枝問題的上界；當原問題是求最小值時，目標值是分枝問題的下界。3

)剪枝 檢查所有分枝的解及目標函數(shù)值，若某分枝的解是整數(shù)并且目標函數(shù)值大于（max）等于其它分枝的目標值，則將其它分枝剪去不再計算，若還存在非整數(shù)解并且目標值大于(max)整數(shù)解的目標值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：分支定界法例

用分枝定界法求解整數(shù)規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題(原整數(shù)規(guī)劃問題的松馳問題)LPIP分支定界法用圖解法求松弛問題的最優(yōu)解，如圖所示。x1x2⑴⑵3(18/11,40/11)⑶21123x1＝18/11,x2=40/11Z=－218/11≈(－19.8)即Z也是IP最小值的下限。對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2≤3，x2≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2分支定界法分支：分別求出（LP1）和（LP2）的最優(yōu)解。分支定界法先求LP1,如圖所示。此時在B點取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計算。x1x2⑴⑵33(18/11,40/11)⑶11BAC同理求LP2,如圖所示。在C

點取得最優(yōu)解。即:x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z(2)<Z(1)＝－16∴原問題有比－16更小的最優(yōu)解，但x2不是整數(shù)，故繼續(xù)分支。分支定界法在IP2中分別再加入條件：x2≤3,x2≥4得下式兩支：分別求出LP21和LP22的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACD先求LP21,如圖所示。此時D在點取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(21)＝-87/5≈-17.4<Z(1)=-16但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。求LP22，如圖所示。無可行解，故不再分枝。分支定界法

在（LP21）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：分別求出（LP211）和（LP212）的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACDEF先求（LP211）,如圖所示。此時在E點取得最優(yōu)解。即x1＝2,x2=3,Z(211)＝－17找到整數(shù)解，問題已探明，此枝停止計算。求（LP212），如圖所示。此時F在點取得最優(yōu)解。即x1＝3,x2=2.5,Z(212)＝－31/2≈－15.5>Z(211)

如對LP212繼續(xù)分解，其最小值也不會低于－15.5，問題探明,剪枝。分支定界法原整數(shù)規(guī)劃問題的最優(yōu)解為:x1=2,x2=3,Z*=－17以上的求解過程可以用一個樹形圖表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP21x1=12/5,x2=3Z(21)

＝－17.4LP22無可行解LP211x1=2,x2=3Z(211)

＝－17LP212