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

第四講 整數(shù)規(guī)劃,在求解線性規(guī)劃問題時(shí)，得到的最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但許多實(shí)際問題要求得到的解為整數(shù)才行。這種要求線性規(guī)劃有整數(shù)解的問題,稱為整數(shù)規(guī)劃(integer programming)或簡稱ip。,第一節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn),整數(shù)規(guī)劃的數(shù)學(xué)模型,第二節(jié) 0-1 整數(shù)規(guī)劃,0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量xj僅取值0或1。這種只能取0或1的變量稱為0-1變量或二進(jìn)制變量。 下面通過過以下幾個(gè)例子說明一下：,籃球隊(duì)要選擇5名隊(duì)員組成上場陣容，8名隊(duì)員的身高及擅長位置見下表：,上場陣容應(yīng)滿足以下條件： (1)只能有一名中鋒上場 (2)至少有一名后衛(wèi) (3)如一號(hào)和4號(hào)均上場，則6號(hào)不出場 (4)2號(hào)和8號(hào)至少有一個(gè)不出場 問應(yīng)如何選擇5名上場隊(duì)員，才能使出場隊(duì)員平均身高最高，試建立其模型。,1,2,8,9,10,7,3,4,6,5,11,1,2,3,4,監(jiān)視攝像頭安裝,2,1,3,10,4,5,6,7,9,8,12,11,13,二.解01規(guī)劃的過濾隱枚舉法 01規(guī)劃若有n個(gè)變量，則產(chǎn)生2n個(gè)可能的組合，當(dāng)n較大則完全枚舉不可能。 最優(yōu)解為目標(biāo)函數(shù)值最大的可行解。 可行解為滿足所有約束條件的解。,1.找出任意一可行解，目標(biāo)函數(shù)值為z0；,2. 原問題求最大值時(shí)，則增加一個(gè)過濾條件,3. 列出所有可能解，對(duì)每個(gè)可能解先檢驗(yàn)式（*），若滿足再檢驗(yàn)其它約束，若不滿足式（*），則過濾掉，若所有約束都滿足，求出目標(biāo)值，判斷此時(shí)目標(biāo)函數(shù)值是否大于過濾條件，若是，用當(dāng)前的目標(biāo)函數(shù)值代替過濾條件值，否則過濾條件不變。,4. 目標(biāo)函數(shù)值最大（最?。┑慕饩褪亲顑?yōu)解。,（*）,第三節(jié) 指派問題,指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型 匈牙利解法求解指派問題 一般的指派問題,有n項(xiàng)任務(wù)，恰好n個(gè)人承擔(dān)，第i 人完成第j 項(xiàng)任務(wù)的花費(fèi)(時(shí)間或費(fèi)用等)為cij，如何指派使總花費(fèi)最??？,一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型,100自由泳 皮特-范登霍根邦德 荷蘭 47.84 2000年9月19日 100米仰泳 蘭尼-克雷澤爾伯格 美國 53.60 1999年8月24日 100蛙泳 北島康介 日本 59.78 2003年7月21日 100蝶泳 伊安-克羅克爾 美國 50.98 2003年7月26日 100米自由泳 50.51沈堅(jiān)強(qiáng)上 海1989年全國游泳冠軍賽 100米仰泳 55.11歐陽鯤鵬上 海2002年國家游泳隊(duì)測驗(yàn)賽 100米蛙泳 1:01.66曾啟亮廣 東第8屆全運(yùn)會(huì) 100米蝶泳 53.20蔣丞稷上 海第26屆奧運(yùn)會(huì),指派問題的系數(shù)矩陣如下：,cij的含義可以不同，如費(fèi)用、成本、時(shí)間等。 系數(shù)矩陣c中，第 i 行中各元素表示第 i 人做各事的費(fèi)用；第j 列各元素表示第 j 事由各人做的費(fèi)用。,為建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入nn個(gè)01變量：,指派問題的數(shù)學(xué)模型可寫成如下頁形式：,若派第i人做第j事 0 若不派第i人做第j事 （ij=1，2,，n）,第j項(xiàng)工作由一個(gè)人做,第i人做一項(xiàng)工作,指派問題的每個(gè)可行解，可用矩陣表示如下：,矩陣x中，每行各元素中只有1個(gè)元素為1,其余各元素等0；每列各元素中也只有1個(gè)元素為1,其余各元素等0 。 指派問題有n！個(gè)可行解。,匈牙利解法的關(guān)鍵是利用了指派問題最優(yōu)解的如下性質(zhì)： 若從指派問題的系數(shù)矩陣c的某行（或某列）各元素分別減去一個(gè)常數(shù)k，得到一個(gè)新的矩陣c，則以c和c 為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解。,二、匈牙利法解題步驟,1955年，庫恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，稱為匈牙利解法。,-2 -4 -9 -7,若某行(列)已有0元素，那就不必再減了。例1的計(jì)算為：,1. 使系數(shù)矩陣各行、各列出現(xiàn)零元素 作法：系數(shù)矩陣各行元素減去所在行的最小元素，再從所得矩陣的各列減去所在列最小元素。(因一行中xij 取值一個(gè)1，其余為0，cij 同時(shí)減去一常數(shù)不影響xij取值)。,匈牙利法解題步驟如下：,-4 -2,這就保證每行每列至少有一個(gè)0元素，同時(shí)不出現(xiàn)負(fù)元素。,2. 試求最優(yōu)解。如能找出n個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的xij= 1，其余xij = 0，得最優(yōu)解，結(jié)束；否則下一步。,例2求表中所示效率矩陣的指派問題的最小解。,經(jīng)行運(yùn)算即可得每行每列都有0元素的系數(shù)矩陣。,再按上述步驟運(yùn)算，得到：,3. 作能覆蓋所有0元素的最少直線數(shù)的直線集合 (1) 對(duì)沒有 的行打 號(hào)； (2) 對(duì)已打 號(hào)的行中所有0元素的所在列打 號(hào)； (3) 再對(duì)打有 號(hào)的列中 0 元素的所在行打 號(hào)； (4)重復(fù)(2),(3)直到得不出新的打 號(hào)的行(列)為止； (5) 對(duì)沒有打 號(hào)的行畫一橫線，對(duì)打 號(hào)的列畫一 縱線，這就得到覆蓋所有0元素的最少直線數(shù),4.未被直線覆蓋的最小元素為cij,在未被直線覆蓋處減去cij,在直線交叉處加上cij。,cij=2,解為,從系數(shù)矩陣c 中，找出最大元素m，用m減去矩陣c中所有元素得以系數(shù)矩陣b，則以b為系數(shù)矩陣的最小化指派問題和以c為系數(shù)矩陣的原最大化指派問題有相同最優(yōu)解。,1.最大化指派問題,三、一般的指派問題,例4 有盈利矩陣c如下，求如何分配盈利最大。,解：1. 先找出最大元素m, 即m=16，減去c中所有元素得,2. 用求目標(biāo)函數(shù)最小值的方法求解（略）,若人數(shù)少事件多，添上虛擬的人，費(fèi)用系數(shù)值為 0。 若事件少人數(shù)多，添上