湖北工業(yè)大學(xué)運(yùn)籌學(xué)-整數(shù)規(guī)劃

1、3.1 整數(shù)規(guī)劃及其數(shù)學(xué)模型,例：某工廠用集裝箱托運(yùn)甲、乙兩種貨物，每箱的體積、重量、可獲得的利潤(rùn) 及托運(yùn)所受限制如表所示：,問：兩種貨物各托運(yùn)多少箱，可使利潤(rùn)最大？,解：設(shè)甲乙兩種貨物托運(yùn)的箱數(shù)分別為 ，則,為整數(shù),這是一個(gè)整數(shù)線性規(guī)劃問題。 不考慮（4）時(shí)，其最優(yōu)解為：,將 取整,是可行解，但不是最優(yōu)解。,不是可行解；,3.1 整數(shù)規(guī)劃及其數(shù)學(xué)模型,3.1.1 整數(shù)規(guī)劃的類型 連續(xù)規(guī)劃：線性規(guī)劃問題中決策變量是連續(xù)變量。 整數(shù)規(guī)劃：部分或全部決策變量取整數(shù)值的數(shù)學(xué)規(guī)劃問題，屬于離散規(guī)劃。 整數(shù)規(guī)劃問題分為以下幾類： 1. 純整數(shù)規(guī)劃：全部決策變量取整數(shù)值的整數(shù)規(guī)劃。 2. 混合整數(shù)規(guī)劃：決

2、策變量中有一部分必須取整數(shù)值的整數(shù)規(guī)劃。 3. 0-1型整數(shù)規(guī)劃：決策變量只能取值0或1的整數(shù)規(guī)劃。 按照目標(biāo)函數(shù)和約束條件中是否包含非線性，將整數(shù)規(guī)劃分成整數(shù)線性規(guī)劃和 整數(shù)非線性規(guī)劃。本章的整數(shù)規(guī)劃都是整數(shù)線性規(guī)劃。,3.1.2 整數(shù)規(guī)劃的數(shù)學(xué)模型及其特點(diǎn),1. 整數(shù)線性規(guī)劃的數(shù)學(xué)模型一般形式為：,3.1 整數(shù)規(guī)劃及其數(shù)學(xué)模型,3.1.2 整數(shù)規(guī)劃的數(shù)學(xué)模型及其特點(diǎn),2. 整數(shù)線性規(guī)劃的特點(diǎn) 不考慮整數(shù)條件，由余下的約束條件和目標(biāo)函數(shù)構(gòu)成的規(guī)劃問題為該整數(shù)規(guī) 劃問題的松弛問題。 整數(shù)規(guī)劃問題的可行解一定是其松弛問題的可行解，但松弛問題的最優(yōu)解取 整所得到的解不一定是整數(shù)規(guī)劃的最優(yōu)解，甚至也

3、不一定是整數(shù)規(guī)劃的可行解。,例：背包問題 設(shè)一個(gè)背包的容積為 ，現(xiàn)有 種物品可裝，物品 的重量為 ，體積為 ， 問如何配裝物品，不超過(guò)背包體積，并且使裝物品的總重量最大？,解：設(shè),數(shù)學(xué)模型為：,3.2 分枝定界法,對(duì)于整數(shù)規(guī)劃問題，當(dāng)可行域有界，可用窮舉法（枚舉法）。窮舉變量所有可行的整數(shù)組合，再比較其目標(biāo)函數(shù)值以找到最優(yōu)解。對(duì)于小型問題，變量少，該方法可行；對(duì)于大型問題，可行的整數(shù)組合很多，窮舉法不可取。 分枝定界法僅檢查可行的整數(shù)組合的一部分，找到最優(yōu)整數(shù)解。 3.2.1 分枝與定界 1.分枝 若整數(shù)規(guī)劃的松弛問題的最優(yōu)解不符合整數(shù)要求，設(shè) ，不符合整數(shù) 要求， 是不超過(guò) 的最大整數(shù)，則構(gòu)

4、造兩個(gè)約束條件：,分別將其并入上述松弛問題中，形成兩個(gè)分枝后繼問題，兩個(gè)后繼問題中的 可行域包含原整數(shù)規(guī)劃問題的所有可行解。 根據(jù)需要，各個(gè)后繼問題可以類似產(chǎn)生自己的分枝后繼問題，如此不斷，直 到獲得整數(shù)規(guī)劃問題的最優(yōu)解，就是所謂的“分枝”。,3.2 分枝定界法,3.2.1 分枝與定界 2.定界 在分枝過(guò)程中，某個(gè)后繼問題獲得一個(gè)整數(shù)可行解，則其目標(biāo)函數(shù)值為 一個(gè)“界限”，可作為衡量其他分枝的一個(gè)依據(jù)。對(duì)于對(duì)應(yīng)松弛問題最優(yōu)解 目標(biāo)函數(shù)值小于上述“界限”值的后繼問題，可刪除不予以考慮。當(dāng)以后的 分枝出現(xiàn)更好的“界限”，就以它來(lái)取代原來(lái)的界限。 3.分枝與定界的作用 將可行域分成子區(qū)域（分枝），逐

5、步減小松弛問題的目標(biāo)函數(shù)值（上界） 增大整數(shù)規(guī)劃問題的目標(biāo)函數(shù)值（下界）。 分枝：為整數(shù)規(guī)劃最優(yōu)解出現(xiàn)創(chuàng)造新條件。 定界：提高搜索的效率。,3.2 分枝定界法,3.2.1 分枝與定界,例：,解：記整數(shù)規(guī)劃問題為IP，松弛問題為L(zhǎng)P,不考慮條件(4)，求解LP問題的最優(yōu)解為：,不符合整數(shù)要求,（1）任選一變量如 進(jìn)行分枝，構(gòu)造兩個(gè)約束條件：,加入到LP問題中，得到后繼問題LP1、LP2。,LP1最優(yōu)解為：,不符合整數(shù)要求,LP2最優(yōu)解為：,不符合整數(shù)要求,3.2 分枝定界法,3.2.1 分枝與定界,LP11無(wú)可行解,不符合整數(shù)要求,LP12最優(yōu)解為：,構(gòu)造兩個(gè)約束條件：,加入到LP1中，得到兩個(gè)

6、分枝LP11、LP12。,構(gòu)造兩個(gè)約束條件：,加入到LP12中，得到兩個(gè)分枝LP121、LP122。,LP121最優(yōu)解為：,LP122最優(yōu)解為：,這兩個(gè)解為IP問題的可行解且目標(biāo)函數(shù)值 相等，是IP最優(yōu)解目標(biāo)函數(shù)值的一個(gè)下界。,3.2 分枝定界法,3.2.1 分枝與定界,該IP問題的兩個(gè)最優(yōu)解為：,LP,3.2 分枝定界法,3.2.2 分枝定界法的基本步驟 1.求解原整數(shù)規(guī)劃問題的松弛問題： （1）若松弛問題沒有可行解，原問題也沒有可行解，則停止。 （2）若松弛問題有最優(yōu)解，且滿足原問題中的取整要求，則該最優(yōu)解為原整 數(shù)規(guī)劃問題的最優(yōu)解。 若松弛問題有最優(yōu)解，但不滿足原問題的取整要求，則轉(zhuǎn)下一

7、步，對(duì)松弛問 題進(jìn)行分枝。 2.分枝：任選一個(gè)不符合取整要求的變量 ，其值為 ，構(gòu)造兩個(gè)約束條件：,分別加入到松弛問題，得到兩個(gè)后繼問題，對(duì)此后繼問題求最優(yōu)解。,3.定界：若分枝后繼問題中存在滿足原問題中取整要求的最優(yōu)解，求出其目標(biāo) 函數(shù)值為最大者，作為整數(shù)規(guī)劃問題最優(yōu)解目標(biāo)函數(shù)值的下界限 。 4.比較與剪枝 各分枝后繼問題中無(wú)可行解或最優(yōu)目標(biāo)函數(shù)值小于 ，不需要再考慮分枝。,3.2 分枝定界法,3.2.2 分枝定界法的基本步驟,5.若所有分枝后繼問題都無(wú)需繼續(xù)分枝，即得到整數(shù)規(guī)劃問題的最優(yōu)解。,分枝定界法適用于純整數(shù)規(guī)劃和混合型整數(shù)規(guī)劃問題，它僅在一部分可行解的 整數(shù)解中尋求最優(yōu)解。,3.3

8、 割平面法,1.思路：在整數(shù)規(guī)劃的松弛問題中逐次增加一個(gè)新約束條件（即割平面）， 它能割去松弛問題可行域中不含整數(shù)解的區(qū)域，逐次割下去，直到最 終得到松弛問題可行域的一個(gè)最優(yōu)極點(diǎn)即最優(yōu)整數(shù)解為止。,2.基本原理,整數(shù)規(guī)劃問題：,松弛問題：,3.3 割平面法,2.基本原理,在松弛問題對(duì)應(yīng)的最終單純形表中，設(shè) 為 個(gè)基變量的下標(biāo)集合， 為 個(gè)非基變量的下標(biāo)集合，則 個(gè)約束方程可表示為：,方法：從 中選取一個(gè)非整分量（分?jǐn)?shù)部分最大），構(gòu)造一個(gè)線性約束條 件，將其加入松弛問題中，形成一個(gè)新的線性規(guī)劃，求解。若新的最 優(yōu)解滿足取整要求則它為整數(shù)規(guī)劃的最優(yōu)解，否則重復(fù)上述步驟，直 到獲得整數(shù)最優(yōu)解為止。,

9、3.3 割平面法,3.求解步驟,（1）求松弛問題的最優(yōu)解，若最優(yōu)解 不滿足取整約束條件，則,將兩式代入上式得：,（3）為滿足取整約束條件，等式左邊為整數(shù)，右邊為小于1的數(shù)，則,即,為切割方程（割平面方程）,切割方程可由最終單純形表中的任意一個(gè)含有非整數(shù)基變量的等式約束演變而來(lái)，切割方程并不唯一。,3.3 割平面法,3.求解步驟,切割方程：,割掉原問題部分非整數(shù)最優(yōu)解。, 沒有割掉原問題任一個(gè)整數(shù)可行解，任一整數(shù)可行解均滿足上式。,（4）將上述切割方程加入松弛問題中，構(gòu)成一個(gè)新的線性規(guī)劃，求最優(yōu)解。 隨著“切割”不斷繼續(xù)，整數(shù)規(guī)劃最優(yōu)解最終成為某個(gè)線性規(guī)劃可行域 的一個(gè)頂點(diǎn)，并作為該線性規(guī)劃的最

10、優(yōu)解。 從幾何角度分析：R為原松弛問題的可行域，R為加入切割方程后新的線性 規(guī)劃的可行域。對(duì)R作切割，在剩下的R中保留了整數(shù)規(guī)劃的所有整數(shù)可行 解，不符合取整要求的部分被割掉了。,3.3 割平面法,例：,解：松弛問題標(biāo)準(zhǔn)形式為：,松弛問題對(duì)應(yīng)的單純形表為：,松弛問題的最優(yōu)解為：,3.3 割平面法,（1）由最終單純形表可知：,考慮取整的約束條件 ： 且均為整數(shù),即 為切割方程,（2）切割方程作為新的約束條件加入松弛問題中,3.3 割平面法,（2）用單純形法求解,，b列中為非可行解，用對(duì)偶單純形法計(jì)算，則 為換出變量，,為換入變量,3.3 割平面法,（3）用 換,最優(yōu)解為,為整數(shù)，該整數(shù)規(guī)劃問題的

11、最優(yōu)解為,3.4 0-1型整數(shù)規(guī)劃的典型應(yīng)用,1.邏輯變量：表示系統(tǒng)是否處于某個(gè)特定狀態(tài)或決策，是否取某個(gè)特定方案。,0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的特殊情形，其變量只能取值0或1，變量 稱為0-1 變量或二進(jìn)制變量。,2.投資場(chǎng)所的選定 例：某公司打算在東、西、南三區(qū)建門市部，擬定7個(gè)位置（ ）選 擇，規(guī)定：在東區(qū)，在 中至多選兩個(gè)；在西區(qū)，在 中 至少選一個(gè)；在南區(qū)，在 中至少選一個(gè)。如選用 點(diǎn)，設(shè)備投 資估計(jì)為 元，每年獲利 元，但投資總額不超過(guò) 元。問應(yīng)選擇 哪幾個(gè)點(diǎn)可使年利潤(rùn)最大？,3.4 0-1型整數(shù)規(guī)劃的典型應(yīng)用,2.投資場(chǎng)所的選定,則該問題的表示為：,3.特殊約束的處理,例：在產(chǎn)品

12、加工時(shí)，可能一種產(chǎn)品可用幾種方式加工，但一次只能選擇一種 或幾種加工方式，加工方式之間存在排斥關(guān)系。,從 個(gè)約束 中選擇 個(gè)約束條件,（1）相互排斥的約束,3.4 0-1型整數(shù)規(guī)劃的典型應(yīng)用,（1）相互排斥的約束 可用如下約束條件組表示：,為足夠大的正數(shù),（2）多中選一的約束,在下列 個(gè)約束中，只有1個(gè)約束有效：,引入 個(gè)0-1整數(shù)變量,該問題可表示為：,若有 個(gè)約束有效，則,3.4 0-1型整數(shù)規(guī)劃的典型應(yīng)用,由于事先不知道某種產(chǎn)品是否生產(chǎn)，不能確定相應(yīng)的固定費(fèi)用是否發(fā)生， 借助0-1整型解決此問題。,4.與生產(chǎn)方式有關(guān)的固定費(fèi)用問題,例：某工廠生產(chǎn)某種產(chǎn)品，有幾種不同生產(chǎn)方式可供選擇。生產(chǎn)

13、的固定成本 與所選擇的生產(chǎn)方式有關(guān)。如果生產(chǎn)方式投資高（設(shè)備自動(dòng)化程度高）， 固定成本高，由于產(chǎn)量大，分配到每件產(chǎn)品的變動(dòng)成本降低。如果生產(chǎn) 方式投資低（設(shè)備自動(dòng)化程度低），固定成本低，分配到每件產(chǎn)品的變 動(dòng)成本可能增加。如何選擇生產(chǎn)方式使生產(chǎn)成本最低？,設(shè) 表示采用第 種生產(chǎn)方式時(shí)的產(chǎn)量， 表示采用第 種生產(chǎn)方式時(shí) 每件產(chǎn)品的變動(dòng)成本， 表示采用第 種生產(chǎn)方式時(shí)的固定成本。,3.4 0-1型整數(shù)規(guī)劃的典型應(yīng)用,4.與生產(chǎn)方式有關(guān)的固定費(fèi)用問題,設(shè) 表示采用第 種生產(chǎn)方式時(shí)的產(chǎn)量， 表示采用第 種生產(chǎn)方式時(shí) 每件產(chǎn)品的變動(dòng)成本， 表示采用第 種生產(chǎn)方式時(shí)的固定成本。,解：總成本為,3.4 0-

14、1型整數(shù)規(guī)劃的典型應(yīng)用,例：籃球隊(duì)要選擇5名隊(duì)員組成上場(chǎng)陣容，8名隊(duì)員的身高及擅長(zhǎng)位置如表所示，上場(chǎng)陣 容應(yīng)滿足以下條件： （1）只能有一名中鋒上場(chǎng)； （2）至少要有一名后衛(wèi)； （3）如果1號(hào)或4號(hào)上場(chǎng)，則6號(hào)不能上場(chǎng)，反過(guò)來(lái)也一樣； （4）2號(hào)和8號(hào)至少有一個(gè)不出場(chǎng)。 問應(yīng)如何選擇5名上場(chǎng)隊(duì)員，才能使出場(chǎng)隊(duì)員平均身高最高？,3.5 0-1型整數(shù)規(guī)劃的求解（隱枚舉法）,例：,解：將所有決策變量可能的情況全部列出，組成 組合。在所有組合情況下， 根據(jù)過(guò)濾條件找到最優(yōu)解。 過(guò)濾條件： 某個(gè)變量組合不滿足其中一個(gè)約束條件，不必檢查其他約束條件。 目標(biāo)函數(shù)值：對(duì)于目標(biāo)函數(shù)值比它差的變量組合，不必檢查可

15、行性， 只有發(fā)現(xiàn)更好的可行解，才替換原來(lái)的。 最優(yōu)解：,3.6 分配問題及匈牙利法,分配問題（指派問題）是一種0-1型整數(shù)規(guī)劃問題。 3.6.1 分配問題的數(shù)學(xué)模型 分配問題：在滿足特定的分配要求下，使分配方案總體效果最佳。 分配問題標(biāo)準(zhǔn)形式：設(shè) n 個(gè)人和 n 件事，第 i 個(gè)人做第 j 件事的費(fèi)用為cij， 確定人和事之間一一對(duì)應(yīng)關(guān)系，使完成 n 件事費(fèi)用最少。,標(biāo)準(zhǔn)分配問題的數(shù)學(xué)模型為：,一件事只能由一人完成,一個(gè)人只能做一件事,3.6 分配問題及匈牙利法,分配問題的系數(shù)矩陣：,解矩陣：,分配問題的可行解由解矩陣表示： 每列元素：只有一個(gè)為1，其余均為0。（滿足第1個(gè)約束條件） 每行元素

16、：只有一個(gè)為1，其余均為0。（滿足第2個(gè)約束條件） 則分配問題可行解有 n！個(gè),3.6 分配問題及匈牙利法,3.6.2 匈牙利法 1.分配問題的性質(zhì) 分配問題的系數(shù)矩陣 的某行（某列）各元素分別減去一個(gè)常數(shù)， 得到一個(gè)矩陣 ，則以C 和C 為系數(shù)矩陣的兩個(gè)分配問題有相同 的最優(yōu)解。,證：設(shè),則,當(dāng)z 達(dá)到最小值時(shí)，z也有最 小值，兩者解的情況完全相同。 根據(jù)該性質(zhì)提出求解分配問題 的一種方法，稱為匈牙利法。,在矩陣C中，能覆蓋0元素的最少直線數(shù)等于 不同行不同列的0元素的最大個(gè)數(shù)。（證明略）,3.6 分配問題及匈牙利法,3.6.2 匈牙利法 2.匈牙利法步驟 （1）變換系數(shù)矩陣 各行各列減去其

17、最小元素，使每行每列至少有1個(gè)零元素，且不出現(xiàn)負(fù)元素。 （2）分配（從上到下，從左到右） 從零元素最少的行開始，標(biāo)記一個(gè)零元素（劃圈），并刪去該行該列其余零 元素。 當(dāng)劃圈的個(gè)數(shù)等于 n 時(shí)，劃圈所在的變量取1，其余均為0，為所求最優(yōu)解。 當(dāng)劃圈的個(gè)數(shù)小于 n 時(shí)，轉(zhuǎn)入下一步。 （3）增加零元素 對(duì)無(wú)圈的行劃 對(duì)劃行中零元素所在列劃 對(duì)劃列中劃圈所在行劃 重復(fù)以上步驟，直到劃不出為止。,3.6 分配問題及匈牙利法,3.6.2 匈牙利法 2.匈牙利法步驟 （3）增加零元素 對(duì)沒有劃的行劃?rùn)M線 對(duì)有劃的列劃豎線 得到覆蓋所有零元素的最少直線集合。 取不被直線覆蓋的所有元素中的最小元素 劃行的各元素

18、中減去最小元素 劃列的各元素中加上最小元素 得到新的系數(shù)矩陣C 對(duì)新的系數(shù)矩陣C，重復(fù)步（2），得到問題的最優(yōu)解。,3.6 分配問題及匈牙利法,3.6.2 匈牙利法,例：已知分配問題的系數(shù)矩陣如下，用匈牙利法求最優(yōu)解。,解：（1）變換系數(shù)矩陣：各行各列減去最小元素,3.6 分配問題及匈牙利法,3.6.2 匈牙利法,例：已知分配問題的系數(shù)矩陣如下，用匈牙利法求最優(yōu)解。,（2）分配 確定獨(dú)立元素,獨(dú)立零元素有3個(gè)，34，不是最優(yōu)解。, 確定最少覆蓋所有0元素的直線集合,3.6 分配問題及匈牙利法,3.6.2 匈牙利法,例：已知分配問題的系數(shù)矩陣如下，用匈牙利法求最優(yōu)解。,（3）增加零元素 在不被直線覆蓋的所有元素中選擇最小元素,3.6 分配問題及匈牙利法,3.6.2 匈牙利法,例：已知分配問題的系數(shù)矩陣如下，用匈牙利法求最優(yōu)解。,（3）增加零元素 重復(fù)（2），確定獨(dú)立元素,有4個(gè)獨(dú)立零元素 最優(yōu)解為：,3.6 分配問題及匈牙利法,3.6.3 非標(biāo)準(zhǔn)分配問題的求解,1.目標(biāo)函數(shù)求最大值,設(shè),令,在求最大值的數(shù)學(xué)模型上， 構(gòu)造 為系數(shù)矩陣，求最 小值分配問題。,3.6 分配問題及匈牙利法,3.6.3 非標(biāo)準(zhǔn)分配問題的求解,例：已知分配問題：,3.6 分配問題及匈牙利