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

實用運籌學

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

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

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

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

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

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

某航空公司正準備增加其中心機場的往來航班，因此需要雇用更多的服務人員。不同時段有最少需求人數，有5種排班方式（連續(xù)工作8個小時）。時段排班1排班2排班3排班4排班5最少需求人數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）決策變量確定不同排班的上班人數。設：xi為排班i的上班人數(i＝1,2,

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

（萬元）長春武漢長春武漢7005000101900800500010190090090000111300100090000111300110011000111170012001100011117001300110001111700140014001011190015001400101119005.6隱性0-1變量的整數規(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變量在使問題標準化以便于求解方面發(fā)揮了重要作用。固定成本問題產品互斥問題最少產量問題兩個約束中選一個約束的問題N個約束中選K個約束的問題5.6.1固定成本問題

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

轉化為：5.6.1固定成本問題例5-6

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

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

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

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

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

兩種新產品的總利潤最大（3）約束條件

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

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

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

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

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

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