指派問題(含非標(biāo)準(zhǔn)指派問題)-展示頁
2025-07-23 21:42本頁面
【正文】 min(Zt)=minZt而新問題的約束方程同原指派問題。但其最優(yōu)解比原最優(yōu)解之減少t.證明：設(shè)式（）～（）為原指派問題。1955年，庫恩（）提出了匈牙利法。二． 匈牙利解法原理：雖然指派問題是一類特殊的整數(shù)規(guī)劃問題，又是特殊的01規(guī)劃問題和特殊的運(yùn)輸問題，因此，它可以用多種相應(yīng)的解法來求解。但一般情況下沒有這么好。商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分派建筑任務(wù)，才能使總的建筑費(fèi)用最少？表59B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：這是一標(biāo)準(zhǔn)的指派問題。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。其總的費(fèi)用 z =C⊙X 這里的⊙表示兩矩陣對應(yīng)元素的積，然后相加。每一種情況為指派問題的一個可行解。()的特征是它有n個1，其它都是0。并稱矩陣 C= = （）為效率矩陣（或價(jià)值系數(shù)矩陣）。注： 指派問題是產(chǎn)量（）、銷量（）相等，且==1，i，j=1,2,…n的運(yùn)輸問題。指派問題的標(biāo)準(zhǔn)形式（以人和事為例）是：有n個人和n件事，已知第i個人作第j件事的費(fèi)用為，要求確定人和事之間的一一對應(yīng)的指派方案，是完成這n件事的總費(fèi)用最少。諸如此類的問題，它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。5 指 派 問 題一． 指派問題的標(biāo)準(zhǔn)形式及數(shù)學(xué)模型在現(xiàn)實(shí)生活中，有各種性質(zhì)的指派問題。其模型為： Max(或min)z=中部分或全部取整數(shù) 若要求決策變量只能取值0或1的整數(shù)規(guī)劃稱為01型整數(shù)線性規(guī)劃。第五章 整數(shù)規(guī)劃167。1 整數(shù)規(guī)劃的數(shù)學(xué)模型及特點(diǎn)要求一部分或全部決策變量必須取整數(shù)值得規(guī)劃問題稱為整數(shù)規(guī)劃。 167。例如，有若干項(xiàng)工作需要分配給若干人（或部門）來完成；有若干項(xiàng)合同需要選擇若干個投標(biāo)者來承包；有若干班級需要安排在各教室上課等等。由于指派問題的多樣性，有必要定義指派問題的標(biāo)準(zhǔn)形式。為了建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入個01變量：若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,…n 這樣，問題的數(shù)學(xué)模型可寫成 （）（）（） （）其中，（）表示每件事必優(yōu)且只有一個人去做，（）表示每個人必做且只做一件事。 有時(shí)也稱為第i個人完成第j件工作所需的資源數(shù)，稱之為效率系數(shù)（或價(jià)值系數(shù)）。并稱決策變量排成的nn矩陣X== （）為決策變量矩陣。這n個1位于不同行、不同列。共n!個解。問題是：把這n個1放到X的個位置的什么地方可使耗費(fèi)的總資源最少？（解最優(yōu)）例1 已知效率矩陣 C= 則 X（1）= ， X（2）= 都是指派問題的最優(yōu)解例12/P149：某商業(yè)公司計(jì)劃開辦五家新商店。已知建筑公司Ai（i=1，2，…5）對新商店Bj（1，2，…5）的建造費(fèi)用的報(bào)價(jià)（萬元）為（i，j=1,2,…5）,見表59。若設(shè)01變量i,j=1,2,…5當(dāng)Ai不承建Bj時(shí)當(dāng)Ai承建Bj時(shí)=則問題的數(shù)學(xué)模型為 Min z=4+8+…+10+6 若看成運(yùn)輸問題，且如上所述，則表59為商店公司B1B2B3B4B5任務(wù)A
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1