線性規(guī)劃整數(shù)規(guī)劃教學PPT

1、第四講第四講 整數(shù)規(guī)劃整數(shù)規(guī)劃 在求解線性規(guī)劃問題時，得到的最優(yōu)解可能在求解線性規(guī)劃問題時，得到的最優(yōu)解可能是分數(shù)或小數(shù)，但許多實際問題要求得到的解為是分數(shù)或小數(shù)，但許多實際問題要求得到的解為整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問題整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問題,稱稱為為整數(shù)規(guī)劃整數(shù)規(guī)劃(integer programming)或簡稱或簡稱ip。第一節(jié)第一節(jié) 整數(shù)規(guī)劃的數(shù)學模型及解的特點整數(shù)規(guī)劃的數(shù)學模型及解的特點整數(shù)規(guī)劃的數(shù)學模型整數(shù)規(guī)劃的數(shù)學模型njxmibxatsxcxfjnjijijnjjj, 2 , 1,0, 2 , 1,),(. .)(max(min)11且為整數(shù)第二節(jié)第

2、二節(jié) 0-1 整數(shù)規(guī)劃整數(shù)規(guī)劃 0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量形式，它的變量xj僅取值僅取值0或或1。這種只能取。這種只能取0或或1的變量稱為的變量稱為0-1變量變量或或二進制變量。二進制變量。 下面通過過以下幾個例子說明一下：下面通過過以下幾個例子說明一下： 籃球隊要選擇籃球隊要選擇5名隊員組成上場陣容，名隊員組成上場陣容，8名隊員的身高及擅長名隊員的身高及擅長位置見下表：位置見下表： 上場陣容應滿足以下條件：上場陣容應滿足以下條件：(1)只能有一名中鋒上場只能有一名中鋒上場(2)至少有一名后衛(wèi)至少有一名后衛(wèi)(3)如一號和如一號和4號均上場，

3、則號均上場，則6號不出場號不出場(4)2號和號和8號至少有一個不出場號至少有一個不出場 問應如何選擇問應如何選擇5名上場隊員，才能使出場隊員平均名上場隊員，才能使出場隊員平均身高最高，試建立其模型。身高最高，試建立其模型。 12891073465111234變量為1014314142142114113113131111211214321minixxxxxxxxxxxxxxxxxxxxxxxxxz監(jiān)視攝像頭安裝監(jiān)視攝像頭安裝21310456798121113二二.解解01規(guī)劃的過濾隱枚舉法規(guī)劃的過濾隱枚舉法 01規(guī)劃若有規(guī)劃若有n個變量，則產生個變量，則產生2n個可能個可能的組合，當?shù)慕M合，當n

4、較大則完全枚舉不可能。較大則完全枚舉不可能。最優(yōu)解為目標函數(shù)值最大的可行解。最優(yōu)解為目標函數(shù)值最大的可行解?？尚薪鉃闈M足所有約束條件的解?？尚薪鉃闈M足所有約束條件的解。1.找出任意一可行解，目標函數(shù)值為找出任意一可行解，目標函數(shù)值為z0； 2. 原問題求最大值時，則增加一個過濾條件原問題求最大值時，則增加一個過濾條件3. 列出所有可能解，對每個可能解先檢驗式（列出所有可能解，對每個可能解先檢驗式（*），若滿足再檢），若滿足再檢驗其它約束，若不滿足式（驗其它約束，若不滿足式（*），則過濾掉，若所有約束都滿足，），則過濾掉，若所有約束都滿足，求出目標值，判斷此時目標函數(shù)值是否大于過濾條件，若是，求

5、出目標值，判斷此時目標函數(shù)值是否大于過濾條件，若是，用當前的目標函數(shù)值代替過濾條件值，否則過濾條件不變。用當前的目標函數(shù)值代替過濾條件值，否則過濾條件不變。4. 目標函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。目標函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。 02211zxcxcxcnn（*）第三節(jié)第三節(jié) 指派問題指派問題n指派問題的標準形式指派問題的標準形式及其數(shù)學模型及其數(shù)學模型n匈牙利解法求解指派問題匈牙利解法求解指派問題 n一般的指派問題一般的指派問題 有有n項任務，恰好項任務，恰好n個人承擔，第個人承擔，第i 人完成第人完成第j 項任務的花費項任務的花費(時間或費用時間或費用等等)為為cij，如何指派使

6、總花費最??？如何指派使總花費最??？一、指派問題的標準形式一、指派問題的標準形式及其數(shù)學模型及其數(shù)學模型 自由仰泳蛙泳蝶泳趙47.84 53.6059.7850.98錢48.3255.6762.6552.83孫53.5460.6470.3256.43李50.5155.1161.6653.20100自由泳自由泳 皮特皮特-范登霍根邦德范登霍根邦德 荷蘭荷蘭 47.84 2000年年9月月19日日 100米仰泳米仰泳 蘭尼蘭尼-克雷澤爾伯格克雷澤爾伯格 美國美國 53.60 1999年年8月月24日日 100蛙泳蛙泳 北島康介北島康介 日本日本 59.78 2003年年7月月21日日 100蝶泳蝶泳

7、 伊安伊安-克羅克爾克羅克爾 美國美國 50.98 2003年年7月月26日日100米自由泳米自由泳 50.51沈堅強上沈堅強上 海海1989年全國游泳冠軍賽年全國游泳冠軍賽100米仰泳米仰泳 55.11歐陽鯤鵬上歐陽鯤鵬上 海海2002年國家游泳隊測驗賽年國家游泳隊測驗賽100米蛙泳米蛙泳 1:01.66曾啟亮廣曾啟亮廣 東第東第8屆全運會屆全運會100米蝶泳米蝶泳 53.20蔣丞稷上蔣丞稷上 海第海第26屆奧運會屆奧運會指派問題的系數(shù)矩陣如下：指派問題的系數(shù)矩陣如下：nnnnnnnnjiccccccccccc212222111211)(cij的含義可以不同，如費用、成本、時間等。的含義可以

8、不同，如費用、成本、時間等。系數(shù)矩陣系數(shù)矩陣c中，第中，第 i 行中各元素表示第行中各元素表示第 i 人做各事的費人做各事的費用；第用；第j 列各元素表示第列各元素表示第 j 事由各人做的費用。事由各人做的費用。 為建立標準指派問題的數(shù)學模型，引入為建立標準指派問題的數(shù)學模型，引入nn個個01變量：變量：jix指派問題的數(shù)學模型可寫成如下頁形式：指派問題的數(shù)學模型可寫成如下頁形式：1若派第若派第i人做第人做第j事事0 若不派第若不派第i人做第人做第j事事 （ij=1，2,，n） ninjijijxczmin11 n),1,jn;,1,(i101 1n), 1( 111 或或ijnjijniij

9、x)n,i(xjx 第第j項工作由項工作由一個人做一個人做第第i人做人做一項工作一項工作指派問題的每個可行解，可用矩陣表示如下：指派問題的每個可行解，可用矩陣表示如下：nnnnnnnnjixxxxxxxxxxx212222111211)(矩陣矩陣x中，每行各元素中只有中，每行各元素中只有1個元素為個元素為1,其余各元素等其余各元素等0；每列各元素中也只有每列各元素中也只有1個元素為個元素為1,其余各元素等其余各元素等0 。指派問題有指派問題有n！個可行解。個可行解。 匈牙利解法的關鍵是利用了指派問題最優(yōu)解的如下性質：匈牙利解法的關鍵是利用了指派問題最優(yōu)解的如下性質： 若從指派問題的系數(shù)矩陣若從

10、指派問題的系數(shù)矩陣c的某行（或某列）各元素分別減去的某行（或某列）各元素分別減去一個常數(shù)一個常數(shù)k，得到一個新的矩陣得到一個新的矩陣c，則以則以c和和c 為系數(shù)矩陣的兩個為系數(shù)矩陣的兩個指派問題有相同的最優(yōu)解。指派問題有相同的最優(yōu)解。 二、匈牙利法解題步驟二、匈牙利法解題步驟 1955年，庫恩利用匈牙利數(shù)學家康尼格的關于矩陣中獨立零元年，庫恩利用匈牙利數(shù)學家康尼格的關于矩陣中獨立零元素的定理，提出了解指派問題的一種算法，稱為匈牙利解法。素的定理，提出了解指派問題的一種算法，稱為匈牙利解法。-2-4-9-7 若某行若某行(列列)已有已有0元素，那就不必再減了。例元素，那就不必再減了。例1的計算為

11、：的計算為： 9 11 8 7 13 16 14 9 15 14 4 104 13 15 2)c(ij 2 4 1 04 7 0 011 10 0 62 11 13 01. 使系數(shù)矩陣各行、各列出現(xiàn)零元素使系數(shù)矩陣各行、各列出現(xiàn)零元素 作法：系數(shù)矩陣各行元素減去所在行的最小元素，再從所作法：系數(shù)矩陣各行元素減去所在行的最小元素，再從所得矩陣的各列減去所在列最小元素。得矩陣的各列減去所在列最小元素。(因一行中因一行中xij 取值一個取值一個1，其，其余為余為0，cij 同時減去一常數(shù)不影響同時減去一常數(shù)不影響xij取值取值)。匈牙利法解題步驟如下：匈牙利法解題步驟如下：)(0 0 1 02 3

12、5 09 6 0 60 7 13 0ijb 2 4 1 04 7 0 011 10 0 62 11 13 0-4 -2 這就保證每行每列至少有一個這就保證每行每列至少有一個0元素，同時元素，同時不出現(xiàn)不出現(xiàn)負元素負元素。 2. 試求最優(yōu)解。如能找出試求最優(yōu)解。如能找出n個位于不同行不同列個位于不同行不同列的零元素，令對應的的零元素，令對應的xij= 1，其余其余xij = 0，得最優(yōu)解，得最優(yōu)解，結束；否則下一步。結束；否則下一步。 0 0 1 0 2 3 5 0 9 6 0 6 0 7 13 0 作法：由獨立作法：由獨立0元素的行（列）開始，獨立元素的行（列）開始，獨立0元素處元素處畫畫 標

13、記標記 ，在有，在有 的行列中劃去其它的行列中劃去其它0元素；元素；再在剩余的再在剩余的0元素中重復此做法，直至不能標記元素中重復此做法，直至不能標記 為為止。止。 9 10 7 10 4 10 6 6 14 159 14 12 17 7 6 6 6 9 8 9 7 9 7 12 5 6 3 6 04 0 0 8 92 7 5 10 00 0 0 3 22 0 2 0 5 7 6 7 6 4 例例2求表中所示效率矩陣的指派問題的最小解。求表中所示效率矩陣的指派問題的最小解。 任務任務人人abcde甲甲127979乙乙89666丙71712149丁15146610戊4107109經行運算即可得每

14、行每列都有經行運算即可得每行每列都有0元素的系數(shù)矩陣。元素的系數(shù)矩陣。 5 6 3 6 04 0 0 8 92 7 5 10 00 0 0 3 22 0 2 0 5再按上述步驟運算，得到：再按上述步驟運算，得到：所畫所畫 0元素少于元素少于n，未得到最優(yōu)解。未得到最優(yōu)解。 563604008927510000032202053. 作能覆蓋所有作能覆蓋所有0元素的最少直線數(shù)的直線集合元素的最少直線數(shù)的直線集合 (1) 對沒有對沒有 的行打的行打 號；號； (2) 對已打對已打 號的行中所有號的行中所有0元素的所在列打元素的所在列打 號；號； (3) 再對打有再對打有 號的列中號的列中 0 元素的

15、所在行打元素的所在行打 號；號； (4)重復重復(2),(3)直到得不出新的打直到得不出新的打 號的行號的行(列列)為止；為止； (5) 對沒有打對沒有打 號的行畫一橫線，對打號的行畫一橫線，對打 號的列畫一號的列畫一 縱線，這就得到覆蓋所有縱線，這就得到覆蓋所有0元素的最少直線數(shù)元素的最少直線數(shù) 3 4 1 4 0 4 0 0 8 110 5 3 8 0 0 0 0 3 4 2 0 2 0 7 56360400892751000003220205 4.未被直線覆蓋的最小元素為未被直線覆蓋的最小元素為cij,在未被直線覆在未被直線覆蓋處減去蓋處減去cij,在直線交叉處加上在直線交叉處加上cij

16、。cij=2 解為解為 3 4 1 4 0 4 0 0 8 110 5 3 8 0 0 0 0 3 4 2 0 2 0 7 從系數(shù)矩陣從系數(shù)矩陣c 中，找出最大元素中，找出最大元素m，用用m減去矩陣減去矩陣c中中所有元素得以系數(shù)矩陣所有元素得以系數(shù)矩陣b，則以則以b為系數(shù)矩陣的最小化指派為系數(shù)矩陣的最小化指派問題和以問題和以c為系數(shù)矩陣的原最大化指派問題有相同最優(yōu)解為系數(shù)矩陣的原最大化指派問題有相同最優(yōu)解。 9 11 8 7 13 16 14 9 15 14 4 104 13 15 2)c(ij1.最大化指派問題最大化指派問題三、一般的指派問題三、一般的指派問題例例4 有盈利矩陣有盈利矩陣c如下，求如何分配盈利最大。如下，求如何分配盈利最大。7 5 8 9 3 0 2 7 1 2 12 6 12 3 1 41)(ijb解：解：1. 先找出最大元素先找出最大元素m, 即即m=16，減去減去c中所有元素中所有元素得得 9 11 8 7 13 16 14 9 15 14 4 104 13 15 2)c(ij2. 用求目標函數(shù)最小值的方法求解（略）用求目標函數(shù)最小值的方法求解（略）若人數(shù)少事件多，添上若人數(shù)少事件多