運籌學整數(shù)規(guī)劃指派問題PPT精品文檔

1、.101變量：變量： 在整數(shù)規(guī)劃問題中，有一類特殊的整數(shù)規(guī)在整數(shù)規(guī)劃問題中，有一類特殊的整數(shù)規(guī)劃，不僅要求解為整數(shù)，而且要求只能取得劃，不僅要求解為整數(shù)，而且要求只能取得0和和1兩個整數(shù)值，這類整數(shù)規(guī)劃稱之為兩個整數(shù)值，這類整數(shù)規(guī)劃稱之為01型型整數(shù)規(guī)劃，該類解稱為整數(shù)規(guī)劃，該類解稱為01變量。變量。第三節(jié)第三節(jié)01型整數(shù)規(guī)劃型整數(shù)規(guī)劃.2一 指派問題由由n項不同的工作或任務，需要項不同的工作或任務，需要n個人去完成（每人只個人去完成（每人只能完成一項工作）。由于每人的知識、能力、經(jīng)驗等能完成一項工作）。由于每人的知識、能力、經(jīng)驗等不同，故各人完成不同任務所需的時間（或其它資源）不同，故各人完

2、成不同任務所需的時間（或其它資源）不同。不同。問應指派哪個人完成何項工作所消耗的總資源最少？問應指派哪個人完成何項工作所消耗的總資源最少？指派問題的數(shù)學模型指派問題的數(shù)學模型引進0-1變量01ijx表示安排第i個人完成第j項工作表示不安排第i個人完成第j項工作.3決策變量矩陣可表示為：nnnnnnxxxxxxxxxx212222111211用 表示第i個人完成第j項工作所需的資源數(shù)，稱之為效率系數(shù)（或價值系數(shù)）。表示為nnnnnncccccccccc212222111211ijc.4則指派問題的數(shù)學模型為ninjijijxcz11minnjxnixtsniijnjij, 2 , 11, 2 ,

3、 11. .110ijx或1注：指派問題是一種特殊的lp問題，是一種特殊的運輸問題。目前認為最簡潔的方法匈牙利法。.5例 某商業(yè)公司計劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司 對新商店 的建造報價（萬元）為 ，商業(yè)公司應當對5家建筑公司怎樣分配建筑任務，才能使總的建筑費用最少？)5 , 2 , 1(iai)5 , 2 , 1(jbj)5 , 2 , 1,(jicijc54321aaaaa54321bbbbb8106961081476106129671417971215784.6這是一個標準的指派問題。若設0-1變量01ijx當 承建 時iajb當 不

4、承建 時iajb則問題的數(shù)學模型為5554121161084minxxxxz5, 2 , 115, 2 , 11. .5151jxixtsiijjij0ijx或1.7c810696108147610612967141797121578454321aaaaa54321bbbbb0010000010010001000000001*x如何分派工作?.8c810696108147610612967141797121578454321aaaaa54321bbbbb-414022328023062208112359110-6-7 -6-70010000010010001000000001*x從而導出匈牙利

5、解法的思想：.91955年,由庫恩（w.w.kuhn）根據(jù)匈牙利數(shù)學家狄考尼格（d.konig)關(guān)于矩陣中獨立零元素的定理發(fā)明的。匈牙利法的基本原理：定理1 將效率矩陣的某一行（或某一列）的各個元素都減去同一個常數(shù)t (t可正可負），得到新的矩陣，則以新矩陣為效率矩陣的指派問題與原指派問題的最優(yōu)解相同。但其最優(yōu)值比原最優(yōu)值減少t 。解：設效率矩陣c為二匈牙利解法.10nnnnknkknnccccccccccccc21212222111211nnnnknkknnccctctctcccccccc21212222111211記新指派問題的目標函數(shù)為 ，zninjnkiinjnjkjkjijijiji

6、jxcxcxcz11111njkjnkiinjnkiinjnjkjkjijijnjkjkjijijxtxcxcxtcxc1111111)(.11ninjijijtztxc111 .注意到njijx11所以原式因此有tztzzmin)min(min推論推論 若將指派問題的效率矩陣每一行及每一列分別減去各若將指派問題的效率矩陣每一行及每一列分別減去各行各列的最小元素，則得到的新的指派問題與原指派問題有行各列的最小元素，則得到的新的指派問題與原指派問題有相同的最優(yōu)解。相同的最優(yōu)解。注：當 cij=0 時，從第i行看，它表示第i人去干第j項工作效率（相對）最好，而從第j列來看，它表示第j項工作讓第i人

7、來干效率（相對）最高。njkjnkiinjnkiinjnjkjkjijijnjkjkjijijxtxcxcxtcxc1111111)(.12問題是：能否找到位于不同行、不同列的問題是：能否找到位于不同行、不同列的n個個0元素？元素？定義 在效率矩陣c中，有一組處于不同行、不同列的零元素，稱為獨立零元素組，此時其中每個元素稱為獨立零元素。例 已知0084765000320205c則0, 0, 0, 043312412cccc是一個獨立零元素組，.130, 0, 0, 043312412cccc分別稱為獨立零元素。0084765000320205c也是一個獨立零元素組。00847650003202

8、05c不是一個獨立零元素組。.14定理定理 效率矩陣效率矩陣c中獨立零元素的最多個數(shù)等于能覆蓋所中獨立零元素的最多個數(shù)等于能覆蓋所有零元素的最少直線數(shù)。有零元素的最少直線數(shù)。本定理由匈牙利數(shù)學家狄考尼格證明的。例 已知矩陣0084765000320205c3084065070320205c.15例 現(xiàn)有一個44的指派問題，其效率矩陣為：9118713161491514410413152c求解該指派問題。步驟1：變換系數(shù)矩陣，使得每行及每列至少產(chǎn)生一個零元素。.169118713161491514410413152c-2-4-9-724104750111006211130-4-210010235

9、0960607130c步驟步驟2：用圈：用圈0法確定法確定 中的獨立中的獨立0元素元素。若獨立零元素個素有n個，則已得最優(yōu)解。若 獨立零元素的個數(shù) n, 則轉(zhuǎn)入步驟3。1c1, 1, 1, 143312214xxxx其余全為0。.17在在只有一個只有一個0元素的行元素的行（或列）加圈，表示此人只能做該事（或列）加圈，表示此人只能做該事（或此事只能由該人來做），每圈一個（或此事只能由該人來做），每圈一個“0”，同時把，同時把位于位于同同列列同行的其他同行的其他零元素劃去零元素劃去。表示此時已不能再由他人來做。表示此時已不能再由他人來做（或此人已不能做其它事）。如此反復，直到矩陣中所有（或此人已不

10、能做其它事）。如此反復，直到矩陣中所有零元素都被圈去或劃去為至。零元素都被圈去或劃去為至。在遇到所有行和列中，在遇到所有行和列中，零元素都不止一個零元素都不止一個時，可時，可任選任選其中其中一個加圈，然后劃去一個加圈，然后劃去同行、同列同行、同列其他未被標記的零元素。其他未被標記的零元素。例0080760000320205c.18步驟步驟3： 若矩陣所有零元素都被標記的，但圈零的個數(shù)若矩陣所有零元素都被標記的，但圈零的個數(shù)m nm n ，作最少直線覆蓋當前零元素。作最少直線覆蓋當前零元素。已知5家建筑公司承建5家商店系數(shù)矩陣8106961081476106129671417971215784c

11、-4-7-6-6-6046304081012630371020811340-1 -3變換系數(shù)矩陣.19043204050012320377108110301c 確定獨立零元素. 作最少直線覆蓋當前所有零元素。由于獨立零元素個數(shù)4 5. 對沒有圈0的行打“”。 在已打“”的行中，對零元素所在的列打“”。 在已打“”的列中，對圈0元素所在的行打“”。.20043204050012320377108110301c 重復和，直到再也找不到可以打“”的行或列為止 對沒有打“”的行畫一橫線，對已打“”的列畫一縱線，即得覆蓋當前0元素的最少直線數(shù)目的集合。04320405001232037710811030

12、2c 繼續(xù)變換系數(shù)矩陣，以增加0元素。在未被直線覆蓋的元素中找出一個最小的元素。對未被直.21043204050012320377108110301c043204050012320377108110302c線覆蓋的元素所在的行（或列）中各元素都減去這一元素。這樣，在未被直線覆蓋的元素中勢必會出現(xiàn)0元素，但同時卻又使已覆蓋的元素中出現(xiàn)負元素。為了消除負元素，只要對它們所在的列（或行）中各元素都加上這一最小元素。返回。.22043204050012320377108110302c-1-104320405000121126601811030+1304321405010121026600811031c

13、 中已有5個獨立0元素，故可確定指派問題的最優(yōu)方案。3c, 1, 1, 1, 1,xxxx其余全為0。.23也就是說，最優(yōu)指派方案是：讓a1承建b3 ,a2承建b2,讓a3承建b1,讓a4承建b4,讓a5承建b5. 這樣安排能使總的建造費用最少，總的建造費用為7+9+6+6+6=34（萬元）。.24三 非標準形式的指派問題處理方法：化成標準形式，再按匈牙利方法求解。 目標函數(shù)最大化指派問題例 有4名工人a1,a2,a3,a4分別操作4臺機床b1,b2,b3,b4。每人操作每臺機床的單位產(chǎn)量見下表。求產(chǎn)值最大的指派方案。 機床工人b1 b2 b3 b4a1a2a3a41

14、0 9 8 7 3 4 5 6 2 1 1 2 4 3 5 6.25 人數(shù)和事數(shù)不等的指派問題人少事多，添上虛擬的“人”。這些虛擬的“人”做各事的費用系數(shù)可取0，理解為這些費用實際上不會發(fā)生。 工作工人b1 b2 b3 b4 b5a1a2a3a410 11 4 2 8 7 11 10 14 12 5 6 9 12 14 13 15 11 10 7.26 人數(shù)和事數(shù)不等的指派問題人多事少，則添上一些虛擬的“事”。這些虛擬的“事”被各人做的費用系數(shù)同樣也取0。 工作工人b1 b2 b3 b4a1a2a3a4a57 5 1311 6 1510 9 1114 12 108 12 14 7.27例 5家

15、建筑公司承建5家商店的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司 a4和a5，而讓技術(shù)力量較強的建筑公司a1，a2和a3來承建。根據(jù)實際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費用最少的指派方案。3 一個人可以做幾件事的指派問題.287812961014179712157841a2a3a1b2b3b4b5b由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作相同的兩家建筑公司（ 和這樣，系數(shù)矩陣變?yōu)椋篿a)3 , 2 , 1, iai7812967812961014179710141797121578412157841b2b3b4b5b1a1a2a2a3a3a上

16、面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，.29引入一件虛事b6，使之成為標準指派問題的系數(shù)矩陣：078129607812960101417970101417970121578401215784c1a1a2a2a3a3a1b2b3b4b5b6b再利用匈牙利法求解。.30078129607812960101417970101417970121578401215784c列變換00051200051203610130361013057000057000圈000051200051203610130361013057000057000-1-1+1再變換打覆蓋.311005121005120

17、25902025902157000157000圈0010000001000100000000010000100000001x最優(yōu)解1a2a3a1b2b3b4b5b6b a1承建b1和b3 ,a2承建b2,a3承建b4和b5 總建筑費用為.32最優(yōu)解 總建筑費用為010000001000100000000010000100000001x1a2a3a1b2b3b4b5b6b781296781296101417971014179712157841215784c3578974z（萬元） a1承建b1和b3 ,a2承建b2,a3承建b4和b5.33例 分配甲、乙、丙、丁四個人去完成a、b、c、d、e五項任務，每人完成各項任務的時間如下表。由于任務重，人數(shù)少，考慮