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

1、1,01變量： 在整數(shù)規(guī)劃問題中，有一類特殊的整數(shù)規(guī)劃，不僅要求解為整數(shù)，而且要求只能取得0和1兩個整數(shù)值，這類整數(shù)規(guī)劃稱之為01型整數(shù)規(guī)劃，該類解稱為01變量,第三節(jié) 01型整數(shù)規(guī)劃,2,一 指派問題,由n項不同的工作或任務(wù)，需要n個人去完成（每人只能完成一項工作）。由于每人的知識、能力、經(jīng)驗等不同，故各人完成不同任務(wù)所需的時間（或其它資源）不同。 問應(yīng)指派哪個人完成何項工作所消耗的總資源最少,指派問題的數(shù)學(xué)模型,引進(jìn)0-1變量,表示安排第i個人完成第j項工作,表示不安排第i個人完成第j項工作,3,決策變量矩陣可表示為,用 表示第i個人完成第j項工作所需的資源數(shù)，稱之為效率 系數(shù)（或價值系數(shù)

2、）。表示為,4,則指派問題的數(shù)學(xué)模型為,或1,注：指派問題是一種特殊的LP問題，是一種特殊的運輸問題,目前認(rèn)為最簡潔的方法匈牙利法,5,例 某商業(yè)公司計劃開辦五家新商店。為了盡早建成 營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑 公司 對新商店 的建造 報價（萬元）為 ，商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分配建筑任務(wù)，才能使總的建筑費用最少,6,這是一個標(biāo)準(zhǔn)的指派問題。若設(shè)0-1變量,當(dāng) 承建 時,當(dāng) 不承建 時,則問題的數(shù)學(xué)模型為,或1,7,如何分派工作,8,4,6,7,6,7,從而導(dǎo)出匈牙利解法的思想,9,1955年,由庫恩（W.W.Kuhn）根據(jù)匈牙利數(shù)學(xué)家狄考尼格（d.konig)關(guān)

3、于矩陣中獨立零元素的定理發(fā)明的,匈牙利法的基本原理,定理1 將效率矩陣的某一行（或某一列）的各個元素都減去 同一個常數(shù)t (t可正可負(fù)），得到新的矩陣，則以新矩陣為 效率矩陣的指派問題與原指派問題的最優(yōu)解相同。但其最 優(yōu)值比原最優(yōu)值減少t,解：設(shè)效率矩陣C為,二匈牙利解法,10,記新指派問題的目標(biāo)函數(shù)為,11,注意到,所以原式,因此有,推論 若將指派問題的效率矩陣每一行及每一列分別減去各 行各列的最小元素，則得到的新的指派問題與原指派問題有 相同的最優(yōu)解,注：當(dāng) cij=0 時，從第i行看，它表示第i人去干第j項工作效率（相對）最好，而從第j列來看，它表示第j項工作讓第i人來干效率（相對）最高

4、,12,問題是：能否找到位于不同行、不同列的n個0元素,定義 在效率矩陣C中，有一組處于不同行、不同列的零元素， 稱為獨立零元素組，此時其中每個元素稱為獨立零元素,例 已知,則,是一個獨立零元素組,13,分別稱為獨立零元素,也是一個獨立零元素組,不是一個獨立零元素組,14,定理 效率矩陣C中獨立零元素的最多個數(shù)等于能覆蓋所 有零元素的最少直線數(shù),本定理由匈牙利數(shù)學(xué)家狄考尼格證明的,例 已知矩陣,15,例 現(xiàn)有一個44的指派問題，其效率矩陣為,求解該指派問題,步驟1：變換系數(shù)矩陣，使得每行及每列至少產(chǎn)生一個零元 素,16,2,4,9,7,4,2,步驟2：用圈0法確定 中的獨立0元素。若獨立零元素

5、個 素有n個，則已得最優(yōu)解。若 獨立零元素的個數(shù) n, 則轉(zhuǎn) 入步驟3,其余全為0,17,在只有一個0元素的行（或列）加圈，表示此人只能做該事 （或此事只能由該人來做），每圈一個“0”，同時把位于同 列同行的其他零元素劃去。表示此時已不能再由他人來做（或此人已不能做其它事）。如此反復(fù)，直到矩陣中所有零元素都被圈去或劃去為至,在遇到所有行和列中，零元素都不止一個時，可任選其中 一個加圈，然后劃去同行、同列其他未被標(biāo)記的零元素,例,18,步驟3： 若矩陣所有零元素都被標(biāo)記的，但圈零的個數(shù)m n ，作最少直線覆蓋當(dāng)前零元素,已知5家建筑公司承建5家商店系數(shù)矩陣,4,7,6,6,6,1,3,變換系數(shù)矩

6、陣,19,確定獨立零元素,作最少直線覆蓋當(dāng)前所有零元素,由于獨立零元素個數(shù)4 5,對沒有圈0的行打“,在已打“”的行中，對零元素所在的列打“,在已打“”的列中，對圈0元素所在的行打“,20,重復(fù)和，直到再也找不到可以打“”的行或列為止,對沒有打“”的行畫一橫線，對已打“”的列畫一縱線， 即得覆蓋當(dāng)前0元素的最少直線數(shù)目的集合,繼續(xù)變換系數(shù)矩陣，以增加0元素,在未被直線覆蓋的元素中找出一個最小的元素。對未被直,21,線覆蓋的元素所在的行（或列）中各元素都減去這一元素。這 樣，在未被直線覆蓋的元素中勢必會出現(xiàn)0元素，但同時卻又 使已覆蓋的元素中出現(xiàn)負(fù)元素。為了消除負(fù)元素，只要對它們 所在的列（或行

7、）中各元素都加上這一最小元素。返回,22,1,1,1,中已有5個獨立0元素，故可確 定指派問題的最優(yōu)方案,其余全為0,23,也就是說，最優(yōu)指派方案是：讓A1承建B3 ,A2承建B2,讓A3承建B1,讓A4承建B4,讓A5承建B5,這樣安排能使總的建造費用最少，總的建造費用為7+9+6+6+6=34（萬元,24,三 非標(biāo)準(zhǔn)形式的指派問題,處理方法：化成標(biāo)準(zhǔn)形式，再按匈牙利方法求解,目標(biāo)函數(shù)最大化指派問題,例 有4名工人A1,A2,A3,A4分別操作4臺機床B1,B2,B3,B4。每人操作每臺機床的單位產(chǎn)量見下表。求產(chǎn)值最大的指派方案,25,人數(shù)和事數(shù)不等的指派問題,人少事多，添上虛擬的“人”。這

8、些虛擬的“人”做各事的費用系數(shù)可取0，理解為這些費用實際上不會發(fā)生,26,人數(shù)和事數(shù)不等的指派問題,人多事少，則添上一些虛擬的“事”。這些虛擬的“事”被各人做的費用系數(shù)同樣也取0,27,例 5家建筑公司承建5家商店的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司 A4和A5，而讓技術(shù)力量較強的建筑公司A1，A2和A3來承建。根據(jù)實際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費用最少的指派方案,3 一個人可以做幾件事的指派問題,28,由于每家建筑公司最多可承建兩家新商店，因此，把每家 建筑公司化作相同的兩家建筑公司（ 和 這樣，系數(shù)矩陣變?yōu)?上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同,29,引入一件虛事B6，使之成為標(biāo)準(zhǔn)指派問題的系數(shù)矩陣,再利用匈牙利法求解,30,列變換,圈0,1,1,1,再變換,打,覆蓋,31,圈0,最優(yōu)解,A1承建B1和B3 ,A2承建B2,A3承建B4和B5,總建筑費用為,32,最優(yōu)解,總建筑費用為,萬元,A1承建B1和B3 ,A2承建B2,A3承建B4和B5,33,例 分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務(wù)，每人完成各項任務(wù)的時間如下表。由于任務(wù)重，人數(shù)少，考慮：