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

1、3.1 整數(shù)規(guī)劃及其數(shù)學(xué)模型,例：某工廠用集裝箱托運甲、乙兩種貨物，每箱的體積、重量、可獲得的利潤 及托運所受限制如表所示：,問：兩種貨物各托運多少箱，可使利潤最大？,解：設(shè)甲乙兩種貨物托運的箱數(shù)分別為 ，則,為整數(shù),這是一個整數(shù)線性規(guī)劃問題。 不考慮（4）時，其最優(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ī)劃。 按照目標函數(shù)和約束條件中是否包含非線性，將整數(shù)規(guī)劃分成整數(shù)線性規(guī)劃和 整數(shù)非線性規(guī)劃。本章的整數(shù)規(guī)劃都是整數(shù)線性規(guī)劃。,3.1.2 整數(shù)規(guī)劃的數(shù)學(xué)模型及其特點,1. 整數(shù)線性規(guī)劃的數(shù)學(xué)模型一般形式為：,3.1 整數(shù)規(guī)劃及其數(shù)學(xué)模型,3.1.2 整數(shù)規(guī)劃的數(shù)學(xué)模型及其特點,2. 整數(shù)線性規(guī)劃的特點 不考慮整數(shù)條件，由余下的約束條件和目標函數(shù)構(gòu)成的規(guī)劃問題為該整數(shù)規(guī) 劃問題的松弛問題。 整數(shù)規(guī)劃問題的可行解一定是其松弛問題的可行解，但松弛問題的最優(yōu)解取 整所得到的解不一定是整數(shù)規(guī)劃的最優(yōu)解，甚至也

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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