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

1、第四講第四講 整數(shù)規(guī)劃整數(shù)規(guī)劃 在求解線性規(guī)劃問(wèn)題時(shí)，得到的最優(yōu)解可能在求解線性規(guī)劃問(wèn)題時(shí)，得到的最優(yōu)解可能 是分?jǐn)?shù)或小數(shù)，但許多實(shí)際問(wèn)題要求得到的解為是分?jǐn)?shù)或小數(shù)，但許多實(shí)際問(wèn)題要求得到的解為 整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問(wèn)題整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問(wèn)題,稱稱 為為整數(shù)規(guī)劃整數(shù)規(guī)劃(integer programming)或簡(jiǎn)稱或簡(jiǎn)稱ip。 第一節(jié)第一節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)規(guī)劃的數(shù)學(xué)模型 njx mibxa ts xcxf j n j ijij n j jj , 2 , 1,0 , 2 , 1,),( . .

2、)(max(min) 1 1 且為整數(shù) 第二節(jié)第二節(jié) 0-1 整數(shù)規(guī)劃整數(shù)規(guī)劃 0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊 形式，它的變量形式，它的變量xj僅取值僅取值0或或1。這種只能取。這種只能取 0或或1的變量稱為的變量稱為0-1變量變量或或二進(jìn)制變量。二進(jìn)制變量。 下面通過(guò)過(guò)以下幾個(gè)例子說(shuō)明一下：下面通過(guò)過(guò)以下幾個(gè)例子說(shuō)明一下： 籃球隊(duì)要選擇籃球隊(duì)要選擇5名隊(duì)員組成上場(chǎng)陣容，名隊(duì)員組成上場(chǎng)陣容，8名隊(duì)員的身高及擅長(zhǎng)名隊(duì)員的身高及擅長(zhǎng) 位置見(jiàn)下表：位置見(jiàn)下表： 上場(chǎng)陣容應(yīng)滿足以下條件：上場(chǎng)陣容應(yīng)滿足以下條件： (1)只能有一名中鋒上場(chǎng)只能有一名中鋒上場(chǎng) (2)至少

3、有一名后衛(wèi)至少有一名后衛(wèi) (3)如一號(hào)和如一號(hào)和4號(hào)均上場(chǎng)，則號(hào)均上場(chǎng)，則6號(hào)不出場(chǎng)號(hào)不出場(chǎng) (4)2號(hào)和號(hào)和8號(hào)至少有一個(gè)不出場(chǎng)號(hào)至少有一個(gè)不出場(chǎng) 問(wèn)應(yīng)如何選擇問(wèn)應(yīng)如何選擇5名上場(chǎng)隊(duì)員，才能使出場(chǎng)隊(duì)員平均名上場(chǎng)隊(duì)員，才能使出場(chǎng)隊(duì)員平均 身高最高，試建立其模型。身高最高，試建立其模型。 1 2 8 9 10 7 3 4 6 5 11 1 2 3 4 變量為10 143 14 142 1421 141 131 13 131 11 121 121 4321min i x xx x xx xxx xx xx x xx x xx xx xxxxz 監(jiān)視攝像頭安裝監(jiān)視攝像頭安裝 2 1 3 10 45

4、6 7 9 8 12 11 13 二二.解解01規(guī)劃的過(guò)濾隱枚舉法規(guī)劃的過(guò)濾隱枚舉法 01規(guī)劃若有規(guī)劃若有n個(gè)變量，則產(chǎn)生個(gè)變量，則產(chǎn)生2n個(gè)可能個(gè)可能 的組合，當(dāng)?shù)慕M合，當(dāng)n較大則完全枚舉不可能。較大則完全枚舉不可能。 最優(yōu)解為目標(biāo)函數(shù)值最大的可行解。最優(yōu)解為目標(biāo)函數(shù)值最大的可行解。 可行解為滿足所有約束條件的解?？尚薪鉃闈M足所有約束條件的解。 1.找出任意一可行解，目標(biāo)函數(shù)值為找出任意一可行解，目標(biāo)函數(shù)值為z0； 2. 原問(wèn)題求最大值時(shí)，則增加一個(gè)過(guò)濾條件原問(wèn)題求最大值時(shí)，則增加一個(gè)過(guò)濾條件 3. 列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式（列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式（*），若滿足再檢

5、），若滿足再檢 驗(yàn)其它約束，若不滿足式（驗(yàn)其它約束，若不滿足式（*），則過(guò)濾掉，若所有約束都滿足，），則過(guò)濾掉，若所有約束都滿足， 求出目標(biāo)值，判斷此時(shí)目標(biāo)函數(shù)值是否大于過(guò)濾條件，若是，求出目標(biāo)值，判斷此時(shí)目標(biāo)函數(shù)值是否大于過(guò)濾條件，若是， 用當(dāng)前的目標(biāo)函數(shù)值代替過(guò)濾條件值，否則過(guò)濾條件不變。用當(dāng)前的目標(biāo)函數(shù)值代替過(guò)濾條件值，否則過(guò)濾條件不變。 4. 目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。 02211 zxcxcxc nn （*） 第三節(jié)第三節(jié) 指派問(wèn)題指派問(wèn)題 n指派問(wèn)題的標(biāo)準(zhǔn)形式指派問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型及其數(shù)學(xué)模型 n匈牙利解法求解指派問(wèn)題匈牙利

6、解法求解指派問(wèn)題 n一般的指派問(wèn)題一般的指派問(wèn)題 有有n項(xiàng)任務(wù)，恰好項(xiàng)任務(wù)，恰好n個(gè)人承擔(dān)，第個(gè)人承擔(dān)，第i 人完成第人完成第j 項(xiàng)任務(wù)的花費(fèi)項(xiàng)任務(wù)的花費(fèi)(時(shí)間或費(fèi)用時(shí)間或費(fèi)用 等等)為為cij，如何指派使總花費(fèi)最?。咳绾沃概墒箍偦ㄙM(fèi)最?。?一、指派問(wèn)題的標(biāo)準(zhǔn)形式一、指派問(wèn)題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型及其數(shù)學(xué)模型 自由仰泳蛙泳蝶泳 趙47.84 53.6059.7850.98 錢(qián)48.3 2 55.6762.6552.83 孫53.5 4 60.6470.3256.43 李50.5 1 55.1161.6653.20 100自由泳自由泳 皮特皮特-范登霍根邦德范登霍根邦德 荷蘭荷蘭 47.84 2

7、000年年9月月19日日 100米仰泳米仰泳 蘭尼蘭尼-克雷澤爾伯格克雷澤爾伯格 美國(guó)美國(guó) 53.60 1999年年8月月24日日 100蛙泳蛙泳 北島康介北島康介 日本日本 59.78 2003年年7月月21日日 100蝶泳蝶泳 伊安伊安-克羅克爾克羅克爾 美國(guó)美國(guó) 50.98 2003年年7月月26日日 100米自由泳米自由泳 50.51沈堅(jiān)強(qiáng)上沈堅(jiān)強(qiáng)上 海海1989年全國(guó)游泳冠軍賽年全國(guó)游泳冠軍賽 100米仰泳米仰泳 55.11歐陽(yáng)鯤鵬上歐陽(yáng)鯤鵬上 海海2002年國(guó)家游泳隊(duì)測(cè)驗(yàn)賽年國(guó)家游泳隊(duì)測(cè)驗(yàn)賽 100米蛙泳米蛙泳 1:01.66曾啟亮廣曾啟亮廣 東第東第8屆全運(yùn)會(huì)屆全運(yùn)會(huì) 100米蝶

8、泳米蝶泳 53.20蔣丞稷上蔣丞稷上 海第海第26屆奧運(yùn)會(huì)屆奧運(yùn)會(huì) 指派問(wèn)題的系數(shù)矩陣如下：指派問(wèn)題的系數(shù)矩陣如下： nnnn n n nnji ccc ccc ccc cc 21 22221 11211 )( cij的含義可以不同，如費(fèi)用、成本、時(shí)間等。的含義可以不同，如費(fèi)用、成本、時(shí)間等。 系數(shù)矩陣系數(shù)矩陣c中，第中，第 i 行中各元素表示第行中各元素表示第 i 人做各事的費(fèi)人做各事的費(fèi) 用；第用；第j 列各元素表示第列各元素表示第 j 事由各人做的費(fèi)用。事由各人做的費(fèi)用。 為建立標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型，引入為建立標(biāo)準(zhǔn)指派問(wèn)題的數(shù)學(xué)模型，引入 nn個(gè)個(gè)01變量：變量： ji x 指派問(wèn)題的

9、數(shù)學(xué)模型可寫(xiě)成如下頁(yè)形式：指派問(wèn)題的數(shù)學(xué)模型可寫(xiě)成如下頁(yè)形式： 1若派第若派第i人做第人做第j事事 0 若不派第若不派第i人做第人做第j事事 （ij=1，2,，n） n i n j ijij xczmin 11 n),1,jn;,1,(i10 1 1 n), 1( 1 1 1 或或 ij n j ij n i ij x )n,i(x jx 第第j項(xiàng)工作由項(xiàng)工作由 一個(gè)人做一個(gè)人做 第第i人做人做 一項(xiàng)工作一項(xiàng)工作 指派問(wèn)題的每個(gè)可行解，可用矩陣表示如下：指派問(wèn)題的每個(gè)可行解，可用矩陣表示如下： nnnn n n nnji xxx xxx xxx xx 21 22221 11211 )( 矩陣矩

10、陣x中，每行各元素中只有中，每行各元素中只有1個(gè)元素為個(gè)元素為1,其余各元素等其余各元素等0； 每列各元素中也只有每列各元素中也只有1個(gè)元素為個(gè)元素為1,其余各元素等其余各元素等0 。 指派問(wèn)題有指派問(wèn)題有n！個(gè)可行解。個(gè)可行解。 匈牙利解法的關(guān)鍵是利用了指派問(wèn)題最優(yōu)解的如下性質(zhì)：匈牙利解法的關(guān)鍵是利用了指派問(wèn)題最優(yōu)解的如下性質(zhì)： 若從指派問(wèn)題的系數(shù)矩陣若從指派問(wèn)題的系數(shù)矩陣c的某行（或某列）各元素分別減去的某行（或某列）各元素分別減去 一個(gè)常數(shù)一個(gè)常數(shù)k，得到一個(gè)新的矩陣得到一個(gè)新的矩陣c，則以則以c和和c 為系數(shù)矩陣的兩個(gè)為系數(shù)矩陣的兩個(gè) 指派問(wèn)題有相同的最優(yōu)解。指派問(wèn)題有相同的最優(yōu)解。

11、二、匈牙利法解題步驟二、匈牙利法解題步驟 1955年，庫(kù)恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元年，庫(kù)恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元 素的定理，提出了解指派問(wèn)題的一種算法，稱為匈牙利解法。素的定理，提出了解指派問(wèn)題的一種算法，稱為匈牙利解法。 -2 -4 -9 -7 若某行若某行(列列)已有已有0元素，那就不必再減了。例元素，那就不必再減了。例1的計(jì)算為：的計(jì)算為： 9 11 8 7 13 16 14 9 15 14 4 10 4 13 15 2 )c( ij 2 4 1 0 4 7 0 0 11 10 0 6 2 11 13 0 1. 使系數(shù)矩陣各行、各列出現(xiàn)零元素使系數(shù)矩

12、陣各行、各列出現(xiàn)零元素 作法：系數(shù)矩陣各行元素減去所在行的最小元素，再?gòu)乃鞣ǎ合禂?shù)矩陣各行元素減去所在行的最小元素，再?gòu)乃?得矩陣的各列減去所在列最小元素。得矩陣的各列減去所在列最小元素。(因一行中因一行中xij 取值一個(gè)取值一個(gè)1，其，其 余為余為0，cij 同時(shí)減去一常數(shù)不影響同時(shí)減去一常數(shù)不影響xij取值取值)。 匈牙利法解題步驟如下：匈牙利法解題步驟如下： )( 0 0 1 0 2 3 5 0 9 6 0 6 0 7 13 0 ij b 2 4 1 0 4 7 0 0 11 10 0 6 2 11 13 0 -4 -2 這就保證每行每列至少有一個(gè)這就保證每行每列至少有一個(gè)0元素，同時(shí)

13、元素，同時(shí) 不出現(xiàn)不出現(xiàn)負(fù)元素負(fù)元素。 2. 試求最優(yōu)解。如能找出試求最優(yōu)解。如能找出n個(gè)位于不同行不同列個(gè)位于不同行不同列 的零元素，令對(duì)應(yīng)的的零元素，令對(duì)應(yīng)的xij= 1，其余其余xij = 0，得最優(yōu)解，得最優(yōu)解， 結(jié)束；否則下一步。結(jié)束；否則下一步。 0 0 1 0 2 3 5 0 9 6 0 6 0 7 13 0 作法：由獨(dú)立作法：由獨(dú)立0元素的行（列）開(kāi)始，獨(dú)立元素的行（列）開(kāi)始，獨(dú)立0元素處元素處 畫(huà)畫(huà) 標(biāo)記標(biāo)記 ，在有，在有 的行列中劃去其它的行列中劃去其它0元素；元素； 再在剩余的再在剩余的0元素中重復(fù)此做法，直至不能標(biāo)記元素中重復(fù)此做法，直至不能標(biāo)記 為為 止。止。 9 1

14、0 7 10 4 10 6 6 14 15 9 14 12 17 7 6 6 6 9 8 9 7 9 7 12 5 6 3 6 0 4 0 0 8 9 2 7 5 10 0 0 0 0 3 2 2 0 2 0 5 7 6 7 6 4 例例2求表中所示效率矩陣的指派問(wèn)題的最小解。求表中所示效率矩陣的指派問(wèn)題的最小解。 任務(wù)任務(wù) 人人 abcde 甲甲127979 乙乙89666 丙71712149 丁15146610 戊4107109 經(jīng)行運(yùn)算即可得每行每列都有經(jīng)行運(yùn)算即可得每行每列都有0元素的系數(shù)矩陣。元素的系數(shù)矩陣。 5 6 3 6 0 4 0 0 8 9 2 7 5 10 0 0 0 0

15、3 2 2 0 2 0 5 再按上述步驟運(yùn)算，得到：再按上述步驟運(yùn)算，得到： 所畫(huà)所畫(huà) 0元素少于元素少于n，未得到最優(yōu)解。未得到最優(yōu)解。 56360 40089 275100 00032 20205 3. 作能覆蓋所有作能覆蓋所有0元素的最少直線數(shù)的直線集合元素的最少直線數(shù)的直線集合 (1) 對(duì)沒(méi)有對(duì)沒(méi)有 的行打的行打 號(hào)；號(hào)； (2) 對(duì)已打?qū)σ汛?號(hào)的行中所有號(hào)的行中所有0元素的所在列打元素的所在列打 號(hào)；號(hào)； (3) 再對(duì)打有再對(duì)打有 號(hào)的列中號(hào)的列中 0 元素的所在行打元素的所在行打 號(hào)；號(hào)； (4)重復(fù)重復(fù)(2),(3)直到得不出新的打直到得不出新的打 號(hào)的行號(hào)的行(列列)為止；為

16、止； (5) 對(duì)沒(méi)有打?qū)](méi)有打 號(hào)的行畫(huà)一橫線，對(duì)打號(hào)的行畫(huà)一橫線，對(duì)打 號(hào)的列畫(huà)一號(hào)的列畫(huà)一 縱線，這就得到覆蓋所有縱線，這就得到覆蓋所有0元素的最少直線數(shù)元素的最少直線數(shù) 3 4 1 4 0 4 0 0 8 11 0 5 3 8 0 0 0 0 3 4 2 0 2 0 7 56360 40089 275100 00032 20205 4.未被直線覆蓋的最小元素為未被直線覆蓋的最小元素為cij,在未被直線覆在未被直線覆 蓋處減去蓋處減去cij,在直線交叉處加上在直線交叉處加上cij。 cij=2 解為解為 3 4 1 4 0 4 0 0 8 11 0 5 3 8 0 0 0 0 3 4 2

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