運(yùn)籌學(xué)-整數(shù)規(guī)劃指派問題.ppt

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

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

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

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

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

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

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

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