運籌學08-整數(shù)規(guī)劃

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

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

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

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

5、建立模型 目標函數(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ù)。如果去掉最后一個約束，就是一個線性規(guī)劃問題。,,8.2 整數(shù)規(guī)劃的圖解法,由圖解法得到線性規(guī)劃的最優(yōu)解為x1=2.44, x2=3.26,目標函數(shù)值為14.66。由圖表可看出，整數(shù)規(guī)劃的最優(yōu)解為x1=4, x2=2,目標函數(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變量,用《管理運籌學》軟件求解得： x1 = 5 x2 = 2 x3 = 2,用《管理運籌學》軟件求解得： x1 = 4 x2 = 1.25 x3 = 1,,8.3 整數(shù)規(guī)劃的應用,一、投資場所的選擇例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市，擬議中有10個位置 Aj (j＝1，2，3，…，10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度

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

10、示 (單位：萬元)。但投資總額不能超過720萬元，問應選擇哪幾個銷售點，可使年利潤為最大?,,8.3 整數(shù)規(guī)劃的應用,解：設：0--1變量 xi = 1 (Ai 點被選用）或 0 (Ai 點沒被選用）。 這樣我們可建立如下的數(shù)學模型：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ī)劃的應用,二、固定成本問題 例5．高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板

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

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

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

16、整數(shù)規(guī)劃的應用,解：引入0—1變量 xij，并令xij = 1(當指派第 i人去完成第j項工作時)或0（當不指派第 i人去完成第j項工作時)．這可以表示為一個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 (甲只能干一項工作) x21+ x22+ x23+ x24= 1 (乙只能干一項工作) x31+ x32+ x33+ x34= 1 (丙只能干一項工作) x41+ x42+ x43+ x44= 1 (丁只能干一項工作) 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ī)劃的應用,四、投資問題 例8．某公司在今后五年內考慮給以下的項目投資。已知：項目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%， 但要求第一年投資最

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

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

21、投資C項目4萬元時，取值2；第2年投資C項目2萬元時，取值1；第2年不投資C項目時，取值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ī)劃的上下界，用增加約束條件的辦法，把相應的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。,,8.4 分支定界法,,分支定界法示意圖,8.5 指派問題與匈牙利法,1、指派問題的形式表述給定了一系列所要完成的任務（tasks）以及一系列完成任務的被指派者（assignees），所需要解決的問題就是要確定出哪一個人被指派進行哪一項任務,2、指派問題的假

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

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

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

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