運(yùn)籌學(xué)08-整數(shù)規(guī)劃

1、第八章 整數(shù)規(guī)劃,8.1 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型8.2 圖解法8.3 整數(shù)規(guī)劃的應(yīng)用8.4 分支定界法8.5 指派問題與匈牙利算法,一、整數(shù)規(guī)劃問題的特征： 變量取值范圍是離散的，經(jīng)典連續(xù)數(shù)學(xué)中的理論和方法一般無法直接用來求解整數(shù)規(guī)劃問題。二、整數(shù)規(guī)劃問題的定義：規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃（Integer Programming）。簡稱IP。線性規(guī)劃中的變量（部分或全部）限制為整數(shù)

2、時(shí)，稱為整數(shù)線性規(guī)劃。,8.1 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型,8.1 整數(shù)規(guī)劃問題及其數(shù)學(xué)模型,三、建模中常用的處理方法： 1、資本預(yù)算問題： 設(shè)有n個(gè)投資方案，cj為第j個(gè)投資方案的收益。投資過程共分為m個(gè)階段，bi為第i個(gè)階段的投資總量，aij為第i階段第j項(xiàng)投資方案所需要的資金。目標(biāo)是在各階段資金限制下使整個(gè)投資的總收益最大。,2、指示變量：指示不同情況的出現(xiàn) 例.有m個(gè)倉庫，要決定動(dòng)用哪些倉庫，滿足n個(gè)顧客對貨物

3、的需要，并決定從各倉庫分別向不同顧客運(yùn)送多少貨物？ 費(fèi)用： fi:動(dòng)用i倉庫的固定運(yùn)營費(fèi)（租金等） cij:從倉庫i到j(luò)顧客運(yùn)送單位貨物運(yùn)費(fèi),約束條件：i)每個(gè)顧客的需要量dj必須得到滿足； ii)只能從動(dòng)用的倉庫運(yùn)出貨物。,四、整數(shù)規(guī)劃的數(shù)學(xué)模型純整數(shù)規(guī)劃：所有決策變量為非負(fù)整數(shù)；全整數(shù)規(guī)劃：所有變量、系數(shù)和常數(shù)均為整數(shù)；混合整數(shù)規(guī)劃：只有一部分決

4、策變量為非負(fù)整數(shù)，其余變量可 為非負(fù)實(shí)數(shù)；0-1整數(shù)規(guī)劃：所有決策變量只能取0獲1兩個(gè)整數(shù)。,,8.2 整數(shù)規(guī)劃的圖解法,例1. 某公司擬用集裝箱托運(yùn)甲、乙兩種貨物，這兩種貨物每件的體積、重量、可獲利潤以及托運(yùn)所受限制如表所示。甲種貨物至多托運(yùn)4件，問兩種貨物各托運(yùn)多少件，可使獲得利潤最大。,,8.2 整數(shù)規(guī)劃的圖解法,解：設(shè)x1 、 x2分別為甲、乙兩種貨物托運(yùn)的件數(shù)，

5、建立模型 目標(biāo)函數(shù)： Max z = 2x1 +3 x2 約束條件： s.t. 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1

6、 ≤4 x1，x2 ≥ 0 為整數(shù)。如果去掉最后一個(gè)約束，就是一個(gè)線性規(guī)劃問題。,,8.2 整數(shù)規(guī)劃的圖解法,由圖解法得到線性規(guī)劃的最優(yōu)解為x1=2.44, x2=3.26,目標(biāo)函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4, x2=2,目標(biāo)函數(shù)值為14。,,8.2 整數(shù)規(guī)劃的圖解法,例2： Max z = 3x1 + x2 + 3

7、x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x1,x2,x3 ≥ 0 為整數(shù),例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 ≤ 4 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x3 ≤1 x1,x2,x3 ≥ 0

8、 x1，x3 為整數(shù) x3 為0-1變量,用《管理運(yùn)籌學(xué)》軟件求解得： x1 = 5 x2 = 2 x3 = 2,用《管理運(yùn)籌學(xué)》軟件求解得： x1 = 4 x2 = 1.25 x3 = 1,,8.3 整數(shù)規(guī)劃的應(yīng)用,一、投資場所的選擇例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市，擬議中有10個(gè)位置 Aj (j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集度

9、，規(guī)定： 在東區(qū)由A1 ， A2 ，A3 三個(gè)點(diǎn)至多選擇兩個(gè)； 在西區(qū)由A4 ， A5 兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)由A6 ， A7 兩個(gè)點(diǎn)中至少選一個(gè)； 在北區(qū)由A8 ， A9 ， A10 三個(gè)點(diǎn)中至少選兩個(gè)。 Aj 各點(diǎn)的設(shè)備投資及每年可獲利潤由于地點(diǎn)不同都是不一樣的，預(yù)測情況見表所

10、示 (單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個(gè)銷售點(diǎn)，可使年利潤為最大?,,8.3 整數(shù)規(guī)劃的應(yīng)用,解：設(shè)：0--1變量 xi = 1 (Ai 點(diǎn)被選用）或 0 (Ai 點(diǎn)沒被選用）。 這樣我們可建立如下的數(shù)學(xué)模型：Max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t. 100x1+120x2+150x3+80x4+70x5+9

11、0x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xj ≥ 0 且xj 為0--1變量，i = 1,2,3,……,10,,8.3 整數(shù)規(guī)劃的應(yīng)用,二、固定成本問題 例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板

12、、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。不考慮固定費(fèi)用，每種容器售出一只所得的利潤分別為 4萬元、5萬元、6萬元，可使用的金屬板有500噸，勞動(dòng)力有300人/月，機(jī)器有100臺(tái)/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬元，中號(hào)為 150 萬元，大號(hào)為200萬元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤為最大。,,8.3 整數(shù)規(guī)劃的應(yīng)用,解：這是一個(gè)整數(shù)規(guī)劃的問題。 設(shè)

13、x1，x2， x3 分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時(shí)才投入，為了說明固定費(fèi)用的這種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第 i種容器, 即 xi ＞ 0 時(shí)) 或0（當(dāng)不生產(chǎn)第 i種容器即 xi = 0 時(shí)）。 引入約束 xi ≤ M yi ，i =1，2，3，M充分大，以保證當(dāng) yi = 0 時(shí)，xi = 0 。 這樣我們可建立如下的數(shù)學(xué)模型：

14、Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 為0--1變量，i = 1,2,3

15、,,三、指派問題 有 n 項(xiàng)不同的任務(wù)，恰好 n 個(gè)人可分別承擔(dān)這些任務(wù)，但由于每人特長不同，完成各項(xiàng)任務(wù)的效率等情況也不同?，F(xiàn)假設(shè)必須指派每個(gè)人去完成一項(xiàng)任務(wù)，怎樣把 n 項(xiàng)任務(wù)指派給 n 個(gè)人，使得完成 n 項(xiàng)任務(wù)的總的效率最高，這就是指派問題。 例6．有四個(gè)工人，要分別指派他們完成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表所示，問應(yīng)如何指派工作，才能使總的消耗時(shí)間為最少。,8.3 整數(shù)規(guī)劃的應(yīng)用,,8.3

16、整數(shù)規(guī)劃的應(yīng)用,解：引入0—1變量 xij，并令xij = 1(當(dāng)指派第 i人去完成第j項(xiàng)工作時(shí))或0（當(dāng)不指派第 i人去完成第j項(xiàng)工作時(shí))．這可以表示為一個(gè)0--1整數(shù)規(guī)劃問題：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44s.t. x11+ x12+ x13+ x14=

17、1 (甲只能干一項(xiàng)工作) x21+ x22+ x23+ x24= 1 (乙只能干一項(xiàng)工作) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只

18、能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 為0--1變量，i,j = 1,2,3,4,,8.3 整數(shù)規(guī)劃的應(yīng)用,四、投資問題 例8．某公司在今后五年內(nèi)考慮給以下的項(xiàng)目投資。已知：項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%， 但要求第一年投資最

19、低金額為4萬元，第二、三、四年不限；項(xiàng)目B：第三年初需要投資，到第五年末能回收本利128％，但規(guī)定最低投資金額為3萬元，最高金額為5萬元； 項(xiàng)目 C：第二年初需要投資，到第五年末能回收本利140%，但規(guī)定其投資額或?yàn)?萬元或?yàn)?萬元或?yàn)?萬元或?yàn)?萬元。 項(xiàng)目 D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。 該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有

20、的資金本利總額為最大?,,8.3 整數(shù)規(guī)劃的應(yīng)用,解：1) 設(shè)xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分別表示第 i 年年初給項(xiàng)目A，B，C，D的投資額； 設(shè)yiA， yiB，是0—1變量，并規(guī)定取 1 時(shí)分別表示第 i 年給A、B投資，否則取 0（ i = 1, 2, 3, 4, 5）。設(shè)yiC 是非負(fù)整數(shù)變量，并規(guī)定：第2年投資C項(xiàng)目8萬元時(shí)，取值為4；第 2年投資C項(xiàng)目6萬元時(shí)，取值3；第2年

21、投資C項(xiàng)目4萬元時(shí)，取值2；第2年投資C項(xiàng)目2萬元時(shí)，取值1；第2年不投資C項(xiàng)目時(shí)，取值0； 這樣我們建立如下的決策變量： 第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C

22、 x2C=20000y2C D x1D x2D x3D x4D x5D,,8.4 分支定界法,分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問題，又能解決混合整數(shù)規(guī)劃的問題。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法而編制成的。 分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件，則求出

23、整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應(yīng)的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。,,8.4 分支定界法,,分支定界法示意圖,8.5 指派問題與匈牙利法,1、指派問題的形式表述給定了一系列所要完成的任務(wù)（tasks）以及一系列完成任務(wù)的被指派者（assignees），所需要解決的問題就是要確定出哪一個(gè)人被指派進(jìn)行哪一項(xiàng)任務(wù),2、指派問題的假

24、設(shè)被指派者的數(shù)量和任務(wù)的數(shù)量是相同的每一個(gè)被指派者只完成一項(xiàng)任務(wù) 每一項(xiàng)任務(wù)只能由一個(gè)被指派者來完成 每個(gè)被指派者和每項(xiàng)任務(wù)的組合有一個(gè)相關(guān)成本 目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小,典型問題,例1：有甲、乙、丙、丁四個(gè)工人，要分別派他們完成四鄉(xiāng)不同的任務(wù)，分別記作A、B、C、D。他們完成各項(xiàng)任務(wù)所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？,,,,第1步，變換系數(shù)矩陣：,-5,第2步，確定獨(dú)立零元素,找到 3 個(gè)

25、獨(dú)立零元素， 但 m = 3 < n = 4,,,,,第3步，作最少的直線覆蓋所有零元素：,(5)對沒有打√號(hào)的行畫橫線，有打√號(hào)的列畫縱線，這就得到覆蓋所有零元素的最少直線數(shù),(1)對沒有獨(dú)立零元素的行打√號(hào)；,√,(2)對已打√號(hào)的行中所有含劃掉零元素的列打√號(hào)；,√,(3)再對打有√號(hào)的列中含獨(dú)立零元素的行打√號(hào)；,(4)重復(fù)(2)，(3)直到得不出新的打√號(hào)的行、列為止；,,,,√,,,,第4步：在沒有被直線覆蓋的所有元素

26、中找出最小元素，然后將所在行（或列）都減去這最小元素；,,,,,,,,,,,,,,在出現(xiàn)負(fù)數(shù)的列（或行）都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。,,,,,-5,,,,,√,√,,,,,,,,,,,,,√,,5、指派問題的變形 Variants of Assignment Problem,任務(wù)比被指派者多被指派者比要完成的任務(wù)多有一些被指派者并不能進(jìn)行某一些的任務(wù) 每個(gè)被指派

27、者可以同時(shí)被指派給多個(gè)的任務(wù),（1）人數(shù)與工作數(shù)不等的處理,當(dāng)人數(shù)>工作數(shù)時(shí)：假想工作數(shù)，使得與人數(shù)能夠匹配, 對應(yīng)的效率設(shè)定為0值。,當(dāng)工作數(shù)>人數(shù)時(shí)：假想人數(shù)，使得與工作數(shù)能夠匹配, 對應(yīng)的效率設(shè)定為0值。,人數(shù)和工作數(shù)不等的指派問題,,（2）一個(gè)人可做幾項(xiàng)工作的指派問題,A1可同時(shí)做三項(xiàng)工作,,（3）某項(xiàng)工作一定不能由某人做的指派問題,A1不能做B4;A3不能做B3,,,,,,,,,,（4）若目標(biāo)函數(shù)為求max