《整數(shù)規(guī)劃(整數(shù)規(guī)劃)ppt課件.ppt》由會員分享，可在線閱讀，更多相關《整數(shù)規(guī)劃(整數(shù)規(guī)劃)ppt課件.ppt（71頁珍藏版）》請在匯文網(wǎng)上搜索。

1、想一想：,在生產(chǎn)管理和經(jīng)營活動中若要求解：,安排上班的人數(shù),運輸車輛臺數(shù),第八章 整數(shù)規(guī)劃（IP）(Integer Programming),1 整數(shù)規(guī)劃的模型（掌握）,3 整數(shù)規(guī)劃的應用（掌握） （補充指派問題的匈牙利解法）,2 整數(shù)規(guī)劃的計算機求解（掌握）,主要內(nèi)容：,一、整數(shù)規(guī)劃的模型,（一）整數(shù)規(guī)劃實例例1：某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤以及托運所受限制如表所示：甲種貨物至多托運4件。問：兩種貨物各托運多少件，可使獲得利潤最大？,規(guī)劃模型：,（二）整數(shù)規(guī)劃的一般數(shù)學模型,一般形式,依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃

2、、混合整數(shù)規(guī)劃、01整數(shù)規(guī)劃。,純整數(shù)規(guī)劃：所有決策變量要求取非負整數(shù)。,全整數(shù)規(guī)劃：除了所有決策變量要求取非負整數(shù)外，技術系數(shù)aij和常數(shù)bi也要求取整數(shù)。,混合整數(shù)規(guī)劃：只有一部分的決策變量要求取非負整數(shù)，另一部分可以取非負實數(shù)。,01整數(shù)規(guī)劃：所有決策變量只能取 0 或 1 兩個整數(shù)。,對整數(shù)規(guī)劃問題，先按線性規(guī)劃問題（不受整數(shù)約束）求解，然后“舍入化整”，就可得到整數(shù)最優(yōu)解，可以嗎？,想一想：,（三）整數(shù)規(guī)劃與線性規(guī)劃的關系,從數(shù)學模型上看整數(shù)規(guī)劃似乎是線性規(guī)劃的一種特殊形式，求解只需在線性規(guī)劃的基礎上，通過舍入取整，尋求滿足整數(shù)要求的解即可。但實際上兩者卻有很大的不同，通過舍入得到的

3、解（整數(shù)）也不一定就是最優(yōu)解，有時甚至不能保證所得的解是整數(shù)可行解。舉例說明。,例：設整數(shù)規(guī)劃問題如下,首先不考慮整數(shù)約束，得到線性規(guī)劃問題。,用 解法求出最優(yōu)解x13/2, x2 = 10/3且有MaxZ = 29/6,x1,x2,3,3,(3/2,10/3),現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個點即(1，3) (2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。,按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，如圖所示。,圖,1. 整數(shù)規(guī)劃的解是可數(shù)個的，最 優(yōu)解不一定發(fā)生在頂點。2. 整數(shù)規(guī)劃的最優(yōu)

4、解不會優(yōu)于其對應線性規(guī)劃問題的最優(yōu)解。（定理）,重點,因此，可將集合內(nèi)的整數(shù)點一一找出，其最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。 如上例：其中（2，2）（3，1）點為最大值，MaxZ=4。,目前，常用的求解整數(shù)規(guī)劃的方法有： 分支定界法和割平面法（不作為課堂授課內(nèi)容）； 對于特別的01規(guī)劃問題采用隱枚舉法和匈牙利法。,在實際中經(jīng)常會遇到這樣的問題，有n 項不同的任務，需要n 個人分別完成其中的一項，但由于任務的性質(zhì)和各人的專長不同，因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問題，應指派哪個人去完成哪項任務，使完成 n 項任務的總效率最高（或所需時間最少）

5、，這類問題稱為指派問題或分派問題。,二、指派問題（匈牙利法）,指派問題是01規(guī)劃的特例。庫恩（ww.kuhn）于1955年提出了指派問題的解法。他引用了匈牙利數(shù)學家康尼格一個關于矩陣中0元素的定理，所以把這解法稱為匈牙利法。以后在方法上雖有不斷改進，但仍沿用這名稱。,四、整數(shù)規(guī)劃問題計算機求解(P165),例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1,x2,x3 0 為整數(shù),用管理運籌學軟件求解得： x1 = 5 x2 = 2 x3 = 2,四、整數(shù)規(guī)劃問題計算機求解(P165),例

6、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 x1，x3 為整數(shù) x3 為0-1變量,用管理運籌學軟件求解得： x1 = 4 x2 = 1.25 x3 = 1 z = 16.25,8.3 整數(shù)規(guī)劃的應用,投資場所的選擇。例4固定成本問題。例5指派問題（分配問題）。例6分布系統(tǒng)設計。例7投資問題。例8,例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置 Aj (j1，2，3，10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密

7、集度，規(guī)定： 在東區(qū)由A1 ， A2 ，A3 三個點至多選擇兩個； 在西區(qū)由A4 ， A5 兩個點中至少選一個； 在南區(qū)由A6 ， A7 兩個點中至少選一個； 在北區(qū)由A8 ， A9 ， A10 三個點中至少選兩個。 Aj 各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，預測情況見表所示 (單位：萬元)。但投資總額不能超過720萬元，問應選擇哪幾個銷售點，可使年利潤為最大?,五、投資場所的選擇。例4(P166),解：設：0-1變量 xi = 1 (Ai 點被選用）或 0 (Ai 點沒被選用）。 這樣我們可建立如下的數(shù)學模型：Max z =36x1+40 x2+50 x3+22x4+20

8、x5+30 x6+25x7+48x8+58x9+61x10s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0 且xi 為0-1變量，i = 1,2,3,10,例4、京成畜產(chǎn)品公司計劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個位置 Aj (j1，2，3，10)可供選擇，考慮到各地區(qū)居民的消費水平及居民居住密集度，規(guī)定： 在東區(qū)由A1 ， A2 ，A3 三個點至多選擇兩個；

9、在西區(qū)由A4 ， A5 兩個點中至少選一個； 在南區(qū)由A6 ， A7 兩個點中至少選一個； 在北區(qū)由A8 ， A9 ， A10 三個點中至少選兩個。 Aj 各點的設備投資及每年可獲利潤由于地點不同都是不一樣的，預測情況見表所示 (單位：萬元)。但投資總額不能超過720萬元，問應選擇哪幾個銷售點，可使年利潤為最大?在西區(qū)由A4 ， A5 兩個點或者都選，或者都不選。,五、投資場所的選擇。例4(P166),在實際中經(jīng)常會遇到這樣的問題，有n 項不同的任務，需要n 個人分別完成其中的一項，但由于任務的性質(zhì)和各人的專長不同，因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問

10、題，應指派哪個人去完成哪項任務，使完成 n 項任務的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。,（一）、指派問題的數(shù)學模型 設n 個人被分配去做n 件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第i 個人去做第j 件工作的的效率（ 時間或費用）為Cij(i=1.2n;j=1.2n)并假設Cij 0。問應如何分配才能使總效率（ 時間或費用）最高？,六、指派問題,指派問題是01規(guī)劃的特例。庫恩（ww.kuhn）于1955年提出了指派問題的解法。他引用了匈牙利數(shù)學家康尼格一個關于矩陣中0元素的定理，所以把這解法稱為匈牙利法。以后在方法上雖有不斷改進，但仍沿用這名稱。

11、,【例】下表為某一個分配問題的效率矩陣，其中aij表示 第i個人完成第j項工作需要的時間。要求：1.將此分配問題的求解轉化為一個網(wǎng)絡圖中求始點 與終點之間的最短路問題，畫出該網(wǎng)絡圖，注明 節(jié)點和邊的含義，并標明每一條邊的aij值； 2.以上述網(wǎng)絡圖為基礎，利用01變量建立該最短 路問題的01整數(shù)規(guī)劃模型，列出該模型的數(shù)學 表達式。,例6有四個工人，要分別指派他們完成四項不同的工作，每人做各項工作所消耗的時間如下表所示，問應如何指派工作，才能使總的消耗時間為最少。,解：引入01變量 xij，并令 xij = 1(當指派第 i人去完成第j項工作時)或0（當不指派第 i人去完成第j項工作時)這可以表

12、示為一個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= 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+

13、 x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 為0-1變量，i,j = 1,2,3,4 * * * 求解可用管理運籌學軟件中整數(shù)規(guī)劃方法。,設決策變量 1 分配第i 個人去做第j 件工作 xij = 0 相反 ( I,j=1.2. n ),其數(shù)學模型為：,（二）匈牙利法解題步驟（補充，重點）,指派問題是0-1 規(guī)劃的特例，也是運輸問題的特例，當然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運輸問題的解法去求解，這就如同用單純型法求解運輸問題一樣是不合算的。利用指派問題的特點

14、可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨立 0 元素的最多個數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。,第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 (1) 從（cij）的每行元素都減去該行的最小元素； (2) 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。,第二步：進行試指派，以尋求最優(yōu)解。 在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為： (1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作 。然后劃

15、去 所在列(行)的其它0元素，記作 ；這表示這列所代表的任務已指派完，不必再考慮別人了。 (2)給只有一個0元素的列(行)中的0元素加圈，記作；然后劃去 所在行的0元素，記作 (3)反復進行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。,(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸瓦M行，直到所有0元素都已圈出和劃掉為止。 （5）若 元素的數(shù)目m 等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)

16、解已得到。若m n, 則轉入下一步。 第三步：作最少的直線覆蓋所有0元素。 (1)對沒有的行打號； (2)對已打號的行中所有含元素的列打號； (3)再對打有號的列中含 元素的行打號；,(4)重復(2)，(3)直到得不出新的打號的行、列為止； (5)對沒有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù) l 。l 應等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若 lm n，須再變換當前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打各行都減去這最小元素；打各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉回第二步。,指派問題,例：有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R。有甲、乙、丙、丁四人。他們將中文說明書譯成不同語種的說明書所需的時間如表所示。問應指派何人去完成何工作，使所需總時間最少？,例一：,2,4,9,7,4,2,甲、乙、丙、丁四個人加工A、B、C、D四種工件所需時間（單位：m