《運籌學(xué)（第3版）》 課件 第5章 整數(shù)規(guī)劃

實用運籌學(xué)

－－運用Excel建模和求解（第3版）第5章整數(shù)規(guī)劃IntegerProgramming本章內(nèi)容要點整數(shù)規(guī)劃的基本概念一般整數(shù)規(guī)劃的建模與應(yīng)用背包問題排班問題0-1規(guī)劃的建模與應(yīng)用本章主要內(nèi)容框架圖5.1整數(shù)規(guī)劃的基本概念在許多實際問題中，決策變量必須為整數(shù)。例如，當(dāng)決策變量是指派的人數(shù)、購買的設(shè)備數(shù)、投入的車輛數(shù)、是否投資等的時候，它們一般必須為非負整數(shù)才有意義。在這種情況下，常常需要應(yīng)用整數(shù)規(guī)劃進行優(yōu)化。整數(shù)規(guī)劃是要求全部或部分決策變量為整數(shù)的規(guī)劃。整數(shù)規(guī)劃分為線性整數(shù)規(guī)劃和非線性整數(shù)規(guī)劃。本章只介紹線性整數(shù)規(guī)劃，簡稱為整數(shù)規(guī)劃。整數(shù)規(guī)劃分為兩大類：一般整數(shù)規(guī)劃與0-1整數(shù)規(guī)劃。整數(shù)規(guī)劃與一般規(guī)劃相比，其可行解不再是連續(xù)的，而是離散的。5.2一般整數(shù)規(guī)劃例5-1

某航空公司是一家使用小型飛機經(jīng)營短途航線的小型區(qū)域性企業(yè)。該航空公司已經(jīng)經(jīng)營得不錯，管理層決定拓展其經(jīng)營領(lǐng)域。管理層面臨的基本問題是：是采購更多小型飛機來開辟一些新的短途航線，還是開始通過為一些跨地區(qū)航線購買大型飛機來進軍全國市場（或雙管齊下）？哪種戰(zhàn)略最有可能獲得最大收益？表5-1提供了購買兩種飛機的年利潤估計值；給出了每架飛機的采購成本，以及可用于飛機采購的總可用資金；并表明了管理層希望小型飛機的采購量不超過2架。需要做的決策是：小型飛機和大型飛機各采購多少架，才能獲得最大利潤？小型飛機大型飛機每架飛機的年利潤（百萬元）15每架飛機的采購成本（百萬元）550最多購買數(shù)量（架）2沒有限制總可用資金（百萬元）1005.2一般整數(shù)規(guī)劃【解】（1）決策變量設(shè)小型飛機與大型飛機的購買數(shù)量分別為x1(架)和x2

(架)。（2）目標(biāo)函數(shù)總利潤最大。（3）約束條件①資金限制②小型飛機數(shù)量限制（最多購買2架）③變量非負，且均為整數(shù)5.2一般整數(shù)規(guī)劃（1）為了進行比較，暫不考慮“整數(shù)”約束，看作一般的線性規(guī)劃問題，用圖解法求出的最優(yōu)解x1＝2，x2＝1.8

如何進行“取、舍”？（2）由于離散問題比連續(xù)問題更難處理，因此，整數(shù)規(guī)劃要比一般線性規(guī)劃難解得多，而且至今尚無一種像求解線性規(guī)劃那樣較成熟的算法。目前常用的基本算法有分支定界法、割平面法等。Excel”規(guī)劃求解”功能采用分支定界法來求解整數(shù)規(guī)劃問題。5.2一般整數(shù)規(guī)劃用Excel求解整數(shù)規(guī)劃問題的基本步驟與求解一般線性規(guī)劃問題相同，只是在約束條件中多添加一個“整數(shù)”約束。在Excel規(guī)劃求解的“添加約束”對話框中，用“int”表示整數(shù)。因此，只要在該對話框中添加一個約束條件，在左邊輸入要求取整的決策變量的單元格（或區(qū)域），然后選擇“int”。5.2一般整數(shù)規(guī)劃例5-1的電子表格模型5.3背包問題背包問題可以抽象為這樣一類問題：設(shè)有n種物品，已知每種物品的重量及價值；同時有一個背包，最大承重為C，現(xiàn)從n種物品中選取若干件（同一種物品可以選多件），使其總重量不超過C，而且總價值最大。背包問題等同于車、船、人造衛(wèi)星等工具的最優(yōu)裝載問題，有廣泛的實際意義。5.3.1一維背包問題例5-2

某貨運公司使用一種最大承載能力為10噸的卡車來裝載三種貨物，每種貨物的單位重量和單位價值如表5-2所示。應(yīng)當(dāng)如何裝載貨物才能使總價值最大？貨物編號123單位重量（噸）345單位價值（萬元）4565.3.1一維背包問題【解】本問題是典型的一維背包問題。（1）決策變量設(shè)卡車裝載的編號為i的貨物有xi件（i=1,2,3）。（2）目標(biāo)函數(shù)總價值最大。（3）約束條件①卡車最大承載能力限制②變量非負，且均為整數(shù)5.3.1一維背包問題例5-2的電子表格模型5.3.2多維背包問題當(dāng)約束條件不僅有貨物的重量，還有體積等限制時，構(gòu)成了多維背包問題。例5-3

現(xiàn)有一輛載重為5噸、裝載體積為8立方米的卡車，可裝載三種貨物，已知每種貨物各有8件，其他有關(guān)信息如表5-3所示，求攜帶貨物價值最大的裝載方案。貨物品種單位重量（噸）單位體積（立方米）單位價值（萬元）10.20.3320.40.57.530.30.465.3.2多維背包問題【解】本問題是典型的多維背包問題。（1）決策變量設(shè)卡車裝載的第i種貨物的數(shù)量為xi件（i=1,2,3）。（2）目標(biāo)函數(shù)總價值最大。（3）約束條件①卡車載重限制②卡車裝載體積限制③每種貨物最多8件④變量非負，且均為整數(shù)5.3.2多維背包問題例5-3的電子表格模型5.4排班問題例5-4

某航空公司正準備增加其中心機場的往來航班，因此需要雇用更多的服務(wù)人員。不同時段有最少需求人數(shù)，有5種排班方式（連續(xù)工作8個小時）。時段排班1排班2排班3排班4排班5最少需求人數(shù)06:00～08:00√4808:00～10:00√√7910:00～12:00√√6512:00～14:00√√√8714:00～16:00√√6416:00～18:00√√7318:00～20:00√√8220:00～22:00√4322:00～24:00√√5200:00～6:00√15每人每天工資（元）1701601751801955.4排班問題【解】本問題是排班問題。（1）決策變量確定不同排班的上班人數(shù)。設(shè)：xi為排班i的上班人數(shù)(i＝1,2,

,5)（2）目標(biāo)函數(shù)每天的總成本最小。（3）約束條件①每個時段的在崗人數(shù)必須不少于最少需求人數(shù)②變量非負，且均為整數(shù)5.4排班問題例5-4的線性規(guī)劃模型5.4排班問題例5-4的電子表格模型5.5顯性0-1變量的整數(shù)規(guī)劃0-1規(guī)劃是整數(shù)規(guī)劃的特殊情況，也是應(yīng)用最廣泛的一類整數(shù)規(guī)劃。在0-1規(guī)劃中，其整數(shù)變量只能取0或1，通常用這些0-1變量表示某種邏輯關(guān)系。例如：用“1”表示“是”，用“0”表示“非（否）”。0-1規(guī)劃模型的建立和求解方法與一般線性規(guī)劃模型相同，只是增加了一個“變量取值必須是0或1”的約束條件。為反映這一約束條件，在求解時應(yīng)在Excel規(guī)劃求解的“添加約束”對話框中添加關(guān)于變量取值為1或0的約束條件。在“添加約束”對話框中，用“bin”（Binary）表示“0”和“1”兩者取一。因此，只需在約束條件左邊輸入要求取“0”或“1”的變量的單元格（或區(qū)域），然后選擇“bin”。5.5顯性0-1變量的整數(shù)規(guī)劃請體會以下不同情況下決策變量的邏輯關(guān)系區(qū)別。例如，兩個０-1變量x1和x2分別表示兩個決策的指令狀態(tài)，則：（1）x1＋x1＝0，表示兩者皆非；（2）x1＋x1＝1，表示兩者中有且只有一個許可；（3）x1＋x1＝2，表示兩者必須同時許可；（4）x1＋x1≤1，表示兩者至多一個許可，但不排除兩者皆非的情況；（5）x1＋x1≥1，表示兩者至少一個許可，但不排除兩者皆可的情況；（6）x1＋x1≤2，表示兩者可以以上述任何情況出現(xiàn)，實際上是同時放棄了對這兩個邏輯變量的約束。5.5顯性0-1變量的整數(shù)規(guī)劃例5-5分公司選址問題。某銷售公司打算在長春或武漢設(shè)立分公司（也可以在兩個城市都設(shè)立分公司）以增加市場份額，同時管理層也在考慮建一個配送中心（也可以不建配送中心），但配送中心的地點限制在新設(shè)立分公司的城市。經(jīng)過計算，每種選擇可使公司獲得的利潤和所需資金如表5-6所示?？傤A(yù)算不得超過1000萬元。目標(biāo)是在滿足以上約束的條件下使總利潤最大。利潤所需資金在長春設(shè)立分公司800600在武漢設(shè)立分公司500300在長春建配送中心600500在武漢建配送中心4002005.5顯性0-1變量的整數(shù)規(guī)劃【解】（1）決策變量本問題的決策變量是“是非決策”的（顯性）0-1變量，每個決策只有兩種選擇--“是”或者“否”，“1”表示對于這個決策選擇“是”，“0”表示對于這個決策選擇“否”。是非決策問題決策變量可能取值在長春設(shè)立分公司？x10或1在武漢設(shè)立分公司？x20或1在長春建配送中心？x30或1在武漢建配送中心？x40或15.5顯性0-1變量的整數(shù)規(guī)劃（2）目標(biāo)函數(shù)總利潤最大。（3）約束條件①總預(yù)算約束②公司最多只建一個新配送中心（互斥）③公司只在新設(shè)立分公司的城市建配送中心（相依）④0－1變量5.5顯性0-1變量的整數(shù)規(guī)劃例5-5的電子表格模型5.5顯性0-1變量的整數(shù)規(guī)劃由于可用資金沒有用完（只用了可用資金1000萬元中的900萬元），并且沒有建配送中心，所以可以對可用資金進行敏感性分析?？捎觅Y金（萬元）實際使用（萬元）是否建配送中心是否設(shè)立分公司總利潤

（萬元）長春武漢長春武漢7005000101900800500010190090090000111300100090000111300110011000111170012001100011117001300110001111700140014001011190015001400101119005.6隱性0-1變量的整數(shù)規(guī)劃在例5-5中，每個0-1變量表示一個“是非決策”，這些變量也稱為0-1決策變量或顯性0-1變量。除了這些0-1決策變量，有時還引入其他一些0-1變量以幫助建立模型。隱性0-1變量（也稱為輔助0-1變量），是引入模型的附加0-1變量，目的是方便建立純的或混合的0-1規(guī)劃模型。介紹隱性0-1變量的5種使用方法，在這些方法中，隱性0-1變量在使問題標(biāo)準化以便于求解方面發(fā)揮了重要作用。固定成本問題產(chǎn)品互斥問題最少產(chǎn)量問題兩個約束中選一個約束的問題N個約束中選K個約束的問題5.6.1固定成本問題

在一般情況下，產(chǎn)品的成本由固定成本和可變成本兩部分組成。固定成本是指在固定投入要素上的支出，它不受產(chǎn)量影響，例如廠房和設(shè)備的租金、貸款利息、管理費用等；可變成本是指在可變投入要素上的支出，它是隨著產(chǎn)量變化而變化的成本，例如原材料費用、生產(chǎn)工人的工資、銷售傭金等。通常，可變成本和產(chǎn)量成正比，所以可以用下面的表達式來表示某一產(chǎn)品的總成本5.6.1固定成本問題對于有n種產(chǎn)品生產(chǎn)問題的一般模型可以表示如下：引入yi：是否生產(chǎn)第i種產(chǎn)品

轉(zhuǎn)化為：5.6.1固定成本問題例5-6

需要啟動資金（固定成本）的例1-1。假設(shè)將例1-1的問題做如下變形：變化一：生產(chǎn)新產(chǎn)品（門和窗）各需要一筆啟動資金，分別為700元和1300元，門和窗的單位利潤還是原來的300元和500元。變化二：一個生產(chǎn)批次在一個星期后即終止，因此門和窗的產(chǎn)量需要取整。5.6.1固定成本問題【解】（1）決策變量由于涉及啟動資金（固定成本），本問題的決策變量有兩類：第一類是所需要生產(chǎn)的門和窗的數(shù)量；第二類是決定是否生產(chǎn)門和窗，這種邏輯關(guān)系可用隱性0-1變量來表示。①整數(shù)決策變量：設(shè)x1、x2分別表示門和窗的每周產(chǎn)量。②隱性0-1變量：設(shè)y1、y2分別表示是否生產(chǎn)門和窗（1表示生產(chǎn)，0表示不生產(chǎn)）。（2）目標(biāo)函數(shù)兩種新產(chǎn)品的總利潤最大5.6.1固定成本問題（3）約束條件

①原有的三個車間每周可用工時限制②變化一，新產(chǎn)品需要啟動資金，即產(chǎn)量xi與是否生產(chǎn)yi之間的關(guān)系③產(chǎn)量xi非負且為整數(shù)（變化二）、是否生產(chǎn)yi為0-1變量5.6.1固定成本問題例5-6的電子表格模型在Excel中，相對極大值M需要數(shù)值化，從車間1和車間2的約束中可以看出，x1的最大取值為4，x2的最大取值為6，因此，M的取值只需不小于6即可，這里取99（需要說明的是：為了區(qū)別其他數(shù)據(jù)，相對極大值M一般取9，99，999，9999等）5.6.2產(chǎn)品互斥問題

在實際生產(chǎn)過程中，為了防止產(chǎn)品的過度多元化，有時需要限制產(chǎn)品生產(chǎn)的種類，這就是產(chǎn)品互斥問題。求解產(chǎn)品互斥問題時，采用求解固定成本問題的方法，引入隱性0-1變量：第i種產(chǎn)品是否生產(chǎn)yi。因此，在n種產(chǎn)品中，最多只能生產(chǎn)k種的約束為：以及產(chǎn)量xi與是否生產(chǎn)yi之間的關(guān)系：5.6.2產(chǎn)品互斥問題例5-7

包含互斥產(chǎn)品的例1-1。假設(shè)將例1-1的問題做如下的變形：兩種新產(chǎn)品門和窗具有相同的用戶，是互相競爭的。因此，管理層決定不同時生產(chǎn)兩種產(chǎn)品，而是只選擇其中的一種進行生產(chǎn)?！窘狻浚?）決策變量

本問題的決策變量有兩類：第一類是門和窗的每周產(chǎn)量；第二類是門和窗是否生產(chǎn)。①決策變量：設(shè)x1、x2分別表示門和窗的每周產(chǎn)量。②隱性0-1變量：設(shè)y1、y2分別表示是否生產(chǎn)門和窗（1表示生產(chǎn)，0表示不生產(chǎn)）。5.6.2產(chǎn)品互斥問題（2）目標(biāo)函數(shù)

兩種新產(chǎn)品的總利潤最大（3）約束條件

①原有的三個車間每周可用工時限制②只能生產(chǎn)一種產(chǎn)品（產(chǎn)品互斥）③產(chǎn)量xi非負、是否生產(chǎn)yi為0-1變量5.6.2產(chǎn)品互斥問題例5-7的電子表格模型5.6.3最少產(chǎn)量問題

在實際生產(chǎn)生活中，經(jīng)常會碰到最少產(chǎn)量、最少訂購量問題。求解最少產(chǎn)量問題時，采用求解固定成本問題的方法，引入隱性0-1變量：第i種產(chǎn)品是否生產(chǎn)yi。因此，對于第i種產(chǎn)品，如果生產(chǎn)，最少生產(chǎn)Si的約束為：以及產(chǎn)量xi與是否生產(chǎn)yi之間的關(guān)系為：5.6.3最少產(chǎn)量問題例5-8某公司需要購買5000個燈泡。公司已經(jīng)收到三家供應(yīng)商的投標(biāo)，供應(yīng)商1提供的燈泡每個3元，一次最少訂購2000個，最多3000個；供應(yīng)商2提供的燈泡每個5元，一次最少訂購1000個，多購不限；供應(yīng)商3可供應(yīng)3000個以內(nèi)任意數(shù)量的燈泡，每個1元，另加固定費用5000元。公司決定從一家或兩家購買。該公司正在考慮采取什么樣的訂購方案，可以使其所花的總費用最少?！窘狻浚?）決策變量本問題的決策變量有兩類：第一類是從各供應(yīng)商購買燈泡的數(shù)量；第二類是是否從各供應(yīng)商購買燈泡。5.6.3最少產(chǎn)量問題例5-8的混合0-1規(guī)劃模型5.6.3最少產(chǎn)量問題例5-8的電子表格模型5.6.4從兩個約束中選一個約束的問題

管理決策時經(jīng)常會遇到在兩個約束中選一個的問題。舉例來說，某個投資方案有兩個約束，但只要其中有一個約束成立就可以了，另外一個約束則不做要求。可以把這種問題轉(zhuǎn)化為有0-1變量的混合整數(shù)規(guī)劃問題。這樣，需要引入一個0-1變量來決定滿足兩個約束條件中的哪一個，這樣的問題也是隱性0-1變量問題，用y表示：5.6.4從兩個約束中選一個約束的問題例5-9

加入二選一約束的例1-1。假設(shè)將例1-1的問題做如下變形：工廠最近建了一個與車間3類似的新車間（車間4），因此，新車間也可以參與兩種新產(chǎn)品的生產(chǎn)。但是，由于管理上的原因，管理層決定只允許車間3和車間4中的一個車間參與新產(chǎn)品的生產(chǎn)，同時要選取能獲得產(chǎn)品組合總利潤最大的那個車間。每個產(chǎn)品所需時間每周可用工時（小時）門窗車間1104車間20212車間33218車間42428單位利潤（元）3005005.6.4從兩個約束中選一個約束的問題【解】

該問題有兩種求解方法。方法1：分別建立模型求解（P173--174）。方法2：建立一個模型求解，這時就需要

引入一個隱性0-1變量。（1