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

實(shí)用運(yùn)籌學(xué)

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

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

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

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

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

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

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

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

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

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

需要啟動(dòng)資金（固定成本）的例1-1。假設(shè)將例1-1的問題做如下變形：變化一：生產(chǎn)新產(chǎn)品（門和窗）各需要一筆啟動(dòng)資金，分別為700元和1300元，門和窗的單位利潤(rùn)還是原來的300元和500元。變化二：一個(gè)生產(chǎn)批次在一個(gè)星期后即終止，因此門和窗的產(chǎn)量需要取整。5.6.1固定成本問題【解】（1）決策變量由于涉及啟動(dòng)資金（固定成本），本問題的決策變量有兩類：第一類是所需要生產(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)品的總利潤(rùn)最大5.6.1固定成本問題（3）約束條件

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

在實(shí)際生產(chǎn)過程中，為了防止產(chǎn)品的過度多元化，有時(shí)需要限制產(chǎn)品生產(chǎn)的種類，這就是產(chǎn)品互斥問題。求解產(chǎn)品互斥問題時(shí)，采用求解固定成本問題的方法，引入隱性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)品門和窗具有相同的用戶，是互相競(jìng)爭(zhēng)的。因此，管理層決定不同時(shí)生產(chǎn)兩種產(chǎn)品，而是只選擇其中的一種進(jìn)行生產(chǎn)?！窘狻浚?）決策變量

本問題的決策變量有兩類：第一類是門和窗的每周產(chǎn)量；第二類是門和窗是否生產(chǎn)。①?zèng)Q策變量：設(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)品的總利潤(rùn)最大（3）約束條件

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

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

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

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

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

引入一個(gè)隱性0-1變量。（1