1、第六章 整數(shù)線性規(guī)劃,6.1 常用整數(shù)線性規(guī)劃模型,6.1.1下料問題,例題1：制造某種產(chǎn)品，需要A，B，C 三種軸 件，其規(guī)格與數(shù)量如下表所示。各類軸件都用 55m 長的同一種圓鋼下料。若計劃生產(chǎn)100 臺機(jī)床，最少要用多少根圓鋼？,依據(jù)問題，若直接以要用的圓鋼數(shù)作為決策 變量,則建模變得很困難. 所以避免直接由題 意建模，先進(jìn)行分析，實際問題抽象成線性 規(guī)劃的數(shù)學(xué)模型經(jīng)常要求進(jìn)行轉(zhuǎn)化。,首先考慮一根長5.5m 的圓鋼截成 A，B,C 三種軸的毛坯有哪些具體下料方式。為此， 只需找出全部省料截法，如下表所示余料 的各種截法，其中1.2m 是各類軸件 長度中最短者。,一根圓鋼所截各類軸件數(shù),現(xiàn)

2、在問題歸結(jié)為：采用上述五種截法用 多少根圓鋼，才能配成100 套軸件，且 使 總下料根數(shù)最少？,設(shè)按第j 種截法下料 根。這樣 就可以建立該問題的LP 模型為:,6.1.2工作人員調(diào)度的問題,例題2：某個百貨商場對售貨人員的需求 經(jīng)過統(tǒng)計分析如表所示. 每個銷售人員每 周連續(xù)工作5 天，然后休息2 天，每個 銷售人員的周工資為100 元, 問應(yīng)該如何 安排, 使聘用售貨人員所需花費(fèi)最少？,解 (一): 設(shè) 為星期一開始工作的人數(shù)， 為 星期二開始工作的人數(shù)， 為星期六開始 工作的人數(shù)， 為星期日開始工作的人數(shù)。 于是目標(biāo)函數(shù)為：,按照每天所需售貨員的人數(shù)寫出約束條件，由 于除了周二和周三開始工

3、作的之外，其余都會 在周一工作，所以周一應(yīng)有 個人工作, 相應(yīng)的約束為,類似可得其它約束, 于是約束條件為:,從而數(shù)學(xué)模型為:,解 (二): 設(shè) 為星期一開始休息的人數(shù)， 為星期二開始休息的人數(shù)， 為星期六開 始休息的人數(shù)， 為星期日開始休息的人數(shù)。 于是目標(biāo)函數(shù)為：,由于除了周日和周一開始休息的之外，其余 都會在周一工作，周一有 個人工作, 相應(yīng)的約束為,類似可得其它約束, 于是約束條件為:,從而數(shù)學(xué)模型為:,6.1.3背包問題,例題 某公司正在考慮4個投資項目。投資 項目1將產(chǎn)生16，000元的凈利潤（NPV）， 項目2將產(chǎn)生22000元的凈利潤，項目3將產(chǎn) 生12000元的凈利潤， 項目

4、4將產(chǎn)生8000元 的凈利潤。每個投資項目現(xiàn)在都需要一定的 現(xiàn)金流出量：投資項目1需5000元；項目2需 7000元； 項目3需4000元；項目4需3000元。 目前可用于投資的現(xiàn)金為14000元。表述一 個IP， 它的解將告訴該公司如何最大化由投 資項目14獲得的凈利潤。,解：如同LP表述那樣，我們首先針對該公司必 須做出的每個決策定義一個變量。這時我們將 定義一個0-1型變量：,公司獲得的總凈利潤(單位為千元)是:,因此公司的目標(biāo)函數(shù)是:,由于最多只能投資14 000元，所以 必須滿足,把目標(biāo)函數(shù)和約束條件組合以后，將 得到下列0-1型IP：,像這樣只有一個約束條件的IP稱為背包 問題。假

5、設(shè)小王打算進(jìn)行夜間徒步旅行， 小王考慮在旅途中攜帶 4樣物品。下表 給出了每樣物品的重量以及小王覺得能 夠從每樣物品得到的利益。,背包中物品的重量和利益,設(shè)小王的背包最多能攜帶14公斤的物品， 對 ，定義：,同樣得到上面的模型。,例題4：修改上例的表述，把下列每個要求 考慮在內(nèi)： （1）公司最多可以投資 2個投資項目。 （2)如果公司對投資項目2進(jìn)行投資，那么 還必須對投資項目 1進(jìn)行投資。 （3）如果公司對投資項目 2進(jìn)行投資，那 么就不能對投資項目 4進(jìn)行投資。,解：對（1），只需增加約束條件,（2）就 和 而言，這個要求規(guī)定， 如 ，那么 也必須等于1。 如果我們增加約束條件 那么我們考

6、慮到了第2個要求。,(3) 此時投資項目2和投資項目4只能 出現(xiàn)一個或者兩個都不出現(xiàn)，因此只 需增加約束條件,6.1.4固定費(fèi)用問題,例題5：固定費(fèi)用IP G服裝公司能夠生產(chǎn)3種 服裝：襯衣、短褲和長褲。每種服裝的生產(chǎn) 都要求G公司具有適當(dāng)類型的機(jī)器。 生產(chǎn)每 種服裝所需要的機(jī)器將按照下列費(fèi)用租用： 襯衣機(jī)器，每周200元；短褲機(jī)器，每周150 元；長褲機(jī)器，每周100元。 每種服裝的生產(chǎn) 還需要表 2 所示數(shù)量的布料和勞動時間。每周 可以使用的勞動時間為150個小時，布料為160 平方米。 下表給出了每種服裝的單位成本和 售價。表述一個可以使G公司每周利潤最大的IP.,解: 如同LP表述那樣

7、，我們將針對G公司 必須做出的每個決策定義一個決策變量。 顯然，G公司必須決定每周應(yīng)當(dāng)生產(chǎn)多少 每種類型的服裝， 因此我們定義,注意，租用機(jī)器的費(fèi)用只取決于所生產(chǎn)服 裝的類型，而與每種服裝的產(chǎn)量無關(guān)。因 此我們就能夠使用下列變量表示租用機(jī)器 的費(fèi)用：,從而建立模型如下：,可依次取為：,6.1.5集合覆蓋問題,(1),集合 的打包問題可表示為：,(2),集合 的劃分問題可表示為：,實際問題中許多問題可表示上述三類問題。 下面看一個具體的集合覆蓋問題。,例題6:設(shè)施位置集合覆蓋問題 K市有6個城區(qū)（城區(qū)16）。這個市必須確 定在什么地方修建消防站。在保證至少有一 個消防站在每個城區(qū)的15分鐘（行駛

8、時間） 路程內(nèi)的情況下，這個市希望修建的消防站 最少。下表給出了在K市的城區(qū)之間行駛時需 要的時間（單位為分鐘）。 表述一個IP，告 訴K市應(yīng)當(dāng)修建多少消防站以及它們所在的 位置。,解： 對城區(qū)16， 定義,于是目標(biāo)函數(shù)是極小化：,下表給出了每個位置在15分鐘內(nèi)可到達(dá)的城區(qū)。,因此對每個位置，有約束條件：,從而整個模型為：,6.1.6二選一約束條件（either or）,下列情況通常出現(xiàn)在數(shù)學(xué)規(guī)劃問題中?，F(xiàn)在 提供了兩個下列形式的約束條件,希望保證至少滿足上述兩個約束條件中的一 個約束條件，這經(jīng)常稱做二選一約束條件。 在表述中加人如下兩個約束條件以后， 將保 證至少滿足一個約束條件成立：,例題

9、7:二選一約束條件,D汽車公司正在考慮生產(chǎn)3種類型的汽車： 微型、中型和大型汽車。表6給出了生產(chǎn) 每種汽車需要的資源以及產(chǎn)生的利潤。目 前有 6000噸鋼材和 60000小時的勞動時 間。要生產(chǎn)一種在經(jīng)濟(jì)效益上可行的汽車， 這種類型的汽車至少必須生產(chǎn)1000輛。 表述一個可以使該公司利潤最大的IP。,解: 由于D公司必須確定每種汽車應(yīng)當(dāng)生產(chǎn) 多少輛，所以我們定義 分別是微 型、中型和大型汽車的產(chǎn)量，因此利潤 （單位為千元）就是 ， D公司的目標(biāo)函數(shù)是,我們知道，如果要生產(chǎn)某種類型的汽車， 那么至少必須生產(chǎn) 1000輛。因此，對于 ，必須有 或 ， 于是可表示為：,由于鋼材和勞動時間有限，因此必

10、須有：,（鋼材約束條件）,（勞動時間約束條件）,注意到 為非負(fù)整數(shù)，這樣便得到如下IP：,這個IP最優(yōu)解是 ， ， 其它為0。因此，D公司應(yīng)當(dāng)生產(chǎn) 2000輛 中型汽車。如果不要求 D公司每種汽車至 少生產(chǎn)1000輛，那么最優(yōu)解將是生產(chǎn)570 輛微型汽車和 1715輛中型汽車。,6.1.7 If-then約束條件,在許多應(yīng)用中將出現(xiàn)下列情況：我們希望 保證，如果滿足約束條件，,那么必須滿足約束條件,如果沒有滿足,那么可以滿足也可以不滿足,簡而言之，我們希望保證,意味著,為了確保這一點，我們將在表述中加人下 列約束條件：,6.2整數(shù)規(guī)劃的基本性質(zhì),整數(shù)規(guī)劃(Integer Programming

11、, 簡稱 IP) 的一般模型為：,其中 。 若 ，則稱之為 純整數(shù)規(guī)劃問，否則稱為混合整數(shù)規(guī)劃問題。,上述問題也通常簡記為：,其中,（1）,若去掉整數(shù)約束，上述問題就是一個連續(xù) 規(guī)劃問題, 相應(yīng)的數(shù)學(xué)模型為：,（2）,稱之為對應(yīng)IP 問題的松弛問題。 對問題(1)， 若目標(biāo)與約束函數(shù)均為線性函數(shù)， 則稱之為 整數(shù)線性規(guī)劃。,求解一般整數(shù)規(guī)劃問題 的主要方法有分枝 定界方法和割平面方法。這兩個方法都基 于下面的觀察： 如果在求解一個IP 的松弛 問題時得到了恰好是整數(shù)值的解, 那么這個 松弛問題的最優(yōu)解也是這個IP 的最優(yōu)解。 這是因為IP 的可行域是其LP 松弛問題可行 域的子集。因此，這個I

12、P 的最優(yōu)值不會小于 (對min 問題) 或大于(對max 問題)松弛問題 的最優(yōu)值。因此我們有如下定理：,定理 1. 1、若松弛問題(2)的解為IP問題(1)的可行解， 則該解也是原問題(1)的最優(yōu)解。 2、松弛問題(2)的解對應(yīng)的目標(biāo)值是原問題(1) 目標(biāo)值的一個下界（對max問題為一個上界）。,本章將在線性規(guī)劃基礎(chǔ)上考慮整數(shù)線性規(guī)劃 問題。和線性規(guī)劃一樣可定義整數(shù)線性規(guī)劃 的標(biāo)準(zhǔn)形式如下：,（3）,其中 表示所有n維非負(fù)整數(shù)向量構(gòu)成的 集合，即：,則問題(3)也可寫作 或：,整數(shù)線性規(guī)劃通常要比線性規(guī)劃困難得多， 將其相應(yīng)的LP 松弛問題的最優(yōu) 解“圓整” 來解原整數(shù)規(guī)劃，雖是最容易想到

13、的， 但 常常得不到整數(shù)規(guī)劃的最優(yōu)解，甚至根本 不是可行解。,例題 1: 計算：,下面介紹一個代數(shù)學(xué)的基本定理，它 與整數(shù)線性規(guī)劃密切相關(guān)。,證明： 必要性是顯然的。下面證明 充分性， 不妨設(shè)矩陣 行滿秩，,設(shè),證明： 設(shè)無界多面體P的頂點集合為 ，極方向集合為 。 因為極方向的任何正數(shù)倍仍是極方向， 故不妨可設(shè)所有的 都是非負(fù)整數(shù)向 量。根據(jù)線性規(guī)劃的 表示定理，可得：,以 記所有n維非負(fù)整數(shù)向量構(gòu)成的集合，設(shè),其中 表示不超過 的最大整數(shù)，且,由此就可推得,證畢,由于 的每一點均可寫成集合 中若 干個點的凸組合，因此 的極點必屬 于集合 。 而線性規(guī)劃問題的最優(yōu)解 必 可在極點（即基本可行

14、解）處達(dá)到，故問 題(3)的求解便可化為如下線性規(guī)劃問題：,（6）,這是整數(shù)線性規(guī)劃所要研究的一個 基本問題。后面的分枝定界方法和 割平面法都可看作是為解決這一基 本問題而提出的簡單而有效的方法。,6.3整數(shù)規(guī)劃的計算方法,整數(shù)規(guī)劃(Integer Programming, 簡稱 IP) 的一般模型為：,通常簡記為：,（7.1）,其中,為可行域,若去掉整數(shù)約束，上述問題就是一個連續(xù) 規(guī)劃問題, 相應(yīng)的數(shù)學(xué)模型為：,（7.2）,稱之為對應(yīng)IP 問題的松弛問題。 對問題 （7.1），若 ，則稱之為純 整數(shù)規(guī)劃問題；否則稱之為混合整數(shù)規(guī)劃 問題。若目標(biāo)與約束函數(shù)均為線性函數(shù)， 則稱之為整數(shù)線性規(guī)劃。

15、,整數(shù)規(guī)劃通常要比線性規(guī)劃困難得多，將其相應(yīng)的LP 松弛問題的最優(yōu) 解“化整” 來解原整數(shù)規(guī)劃，雖是最容易想到的， 但常常得不到整數(shù)規(guī)劃的最優(yōu)解，甚至根本不是可行解，因此有必要對整數(shù)規(guī)劃的解法進(jìn)行專門研究。 求解一般整數(shù)規(guī)劃問題 的主要方法是分枝定界方法， 此外還有割平面方法。,這兩個方法都基于下面基本而重要的觀察： 如果你在求解一個IP 的松弛問題時得到了恰好是整數(shù)值的解, 那么這個松弛問題的最優(yōu)解也是這個IP 的最優(yōu)解。因此，這個IP 的最優(yōu)值不會小于(對min 問題) 或大于(對max 問題)松弛問題的最優(yōu)值。因此我們有如下定理：,定理711： （1）若松弛問題的解為IP問題的可行解，則

16、 該解也是原問題的最優(yōu)解。 （2）松弛問題的解對應(yīng)的目標(biāo)值是原問題 目標(biāo)值的一個下界（對max問題為一個上界）。,6.3.1分枝定界方法,下面介紹求解一般整數(shù)規(guī)劃問題(IP)的主要 方法分枝定界方法。 在求解整數(shù)規(guī)劃時，如果可行域是有界的， 首先容易想到的方法就是窮舉變量的所有 可行的整數(shù)組合，然后比較它們的目標(biāo)函 數(shù)值以定出最優(yōu)解：對于小型的問題, 這個方 法是可行的，也是有效的。對于大 型的問題，可行的整數(shù) 組合數(shù)是很大的， 如設(shè)某個問題有50 個0-1 整型變量, 則其可 能的解有,即使是用每秒1 億次的計算機(jī), 也要算上130.31 天; 若有100 個0-1 整型變量, 則要算上46

17、.52 年! 解這樣的題，窮舉法是不可取的。所以我們的方法一般應(yīng)是僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解。分枝定界解法（Branch and Bound Method）就是其中的一個。,顯然 必是某個葉子節(jié)點的解，且是所有葉子節(jié)點的解中最小的。 因此分枝定界法實際上是一個窮舉的過程，有可能會遇到“組合爆炸”的問題，但通過分枝、剪枝和定界過程的靈活組合，常常能在規(guī)定時間里獲得滿意的結(jié)果，因此分枝定界法是目前求解整數(shù)規(guī)劃問題商業(yè)軟件的首選方法。在求解過程中首先要解決如下兩個問題：,1、在分枝的問題中先求解哪個問題？ 2、在多個 非整數(shù)的情形下，選擇哪一 個變量作為分枝變量？,對第一個問

18、題，通常采用LIFO 規(guī)則，即 “后進(jìn)先出(即Last In, First Out)” 的規(guī)則 依次求解子問題。另一種常用的方法是 跳躍式跟蹤法。,對第二個問題，分枝經(jīng)濟(jì)重要性最大的 分?jǐn)?shù)值變量通常是最佳策略。,例7-1：生產(chǎn)桌子和椅子，已知生產(chǎn)一個這 桌子9個單位的木材和1個單位的工時，其 利潤為8元。生產(chǎn)一個椅子需要5個單位的 木材和1個單位的工時，其利潤為5元。木 材總數(shù)為45，工時總數(shù)為6，如下表所示。,問應(yīng)如何安排生產(chǎn)利潤最大？,解：設(shè)生產(chǎn)餐桌和椅子的數(shù)量分別是 和 ，則數(shù)學(xué)模型為：,用作圖法：,下面用“分枝定界”的方法：首先解由原問題 去掉整數(shù)約束后得到的松弛問題（稱之為子 問題1

19、），得解：,即若誤差不超過6%，則該解已可接受了。 由于已得到整數(shù)解，子問題2已不用分枝， 其最優(yōu)解可作為候選的最優(yōu)解。然后求解 子問題3，得解,這一過程如下圖所示。,再解子問題5不可行，舍去，此時已窮盡所有 分枝，因此最優(yōu)解就是 。 整個計算過程一共計算了七個線性規(guī)劃子問題。,在使用單純形法計算上述子問題時，可采用 前述靈敏度分析的方法。如對上述例題。 下面介紹求解背包問題的分枝定界方法。由 于背包問題只有一個約束，其松弛問題的解 可以直接得到，如對問題：,（7.5）,其中 是選擇物品j的利益， 是可使用資源的量， 物品j占用的資源。其松弛問題為：,對問題7.6， 可以解釋為物品j每使用 一

20、個單位資源可以獲得的利益，設(shè),(7.6),則問題(7.6)的解為,對相應(yīng)的min問題，解為,此對背包問題(7.5)，對變量 ，應(yīng)按 從 大到小的順序?qū)?從小到大編號，然后直接 按前述分枝定界方法（首先對編號最小的變 量進(jìn)行分枝，并采用LIFO規(guī)則）計算即可。,實際問題中的大多數(shù)背包問題是0-1背包問題， 其模型為：,(7.7),即每種物品最多只能取一個。由于每個變量 只能取值0或1，因此對變量 進(jìn)行分枝后 將直接得到兩個分枝，此時分枝過程也簡化 了。下面舉例說明。,例：計算0-1背包問題：,解：此時變量 已按 從大到小的順序 編好號，首先解由原問題去掉整數(shù)約束后 得到的松弛問題（稱之為子問題1

21、），容易 看出其解為：,對應(yīng)的目標(biāo)值為,6.3.2 0-1規(guī)劃的隱枚舉法,一般0-1規(guī)劃的數(shù)學(xué)模型為：,(7.8),對上述問題，由于變量只取0與1，因此 n個變量組合起來得到的所有可能解有 個，可用一個完全二叉樹來表示，如三 個只取0與1的變量的所有可能組合可由 下面的完全二叉樹來表示：,當(dāng)n 很小時，可直接用枚舉法解上述問題，當(dāng)n很大時，可結(jié)合分枝定界方法，通過對問題的觀察簡化上述枚舉過程，得到隱枚舉法。隱枚舉法經(jīng)常用于求解0l型IP。 它利用每個變量都必須等于0或1，簡化了分枝定界過程的分枝和定界。,在隱枚舉法中使用的樹中， 對于某個變量 ，樹的每個分枝將規(guī)定 或1。在每個節(jié)點處，一些變量的值已經(jīng)被確定，值已經(jīng)被確定的那些變量稱為固定變量， 在一個節(jié)點處值沒有被定的所有變量都稱為自由變量。對于一個節(jié)點來說，所有自由變量的取定的值稱為該節(jié)點的完備值。下面描述3個在隱枚舉法中使用的主要思想。,1、在一個節(jié)點處，對于固定變量在該節(jié)點的給 定值，是不是有一種容易的方法能夠求出該 節(jié)點在原始0l型IP 中可行的良好完備值呢？ 要回答這個問題，我們需要完備這個節(jié) 點， 把每個自由變量設(shè)置為能夠使目標(biāo)函數(shù)最大或 最小的值（0或1）。如果