




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
整數(shù)規(guī)劃整數(shù)規(guī)劃的數(shù)學(xué)模型設(shè)置邏輯變量建立整數(shù)規(guī)劃模型分配問題與匈牙利法分支定界法、割平面法應(yīng)用舉例整數(shù)規(guī)劃整數(shù)規(guī)劃的數(shù)學(xué)模型分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型分配問題也稱指派問題(assignmentproblem),在我們現(xiàn)實(shí)生活中,常有各種性質(zhì)的分配問題.例如:應(yīng)如何分配若干項(xiàng)工作給若干個(gè)人(或部門)來完成,以達(dá)到總體的最佳效果等等.由于分配問題的多樣性,我們有必要定義分配問題的標(biāo)準(zhǔn)形式.匈牙利解法一般的分配問題3分配問題與匈牙利法分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型3分配問題與匈牙利法分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型分配問題的標(biāo)準(zhǔn)形式(以人和任務(wù)為例)假定有n項(xiàng)任務(wù)分配給n個(gè)人去完成,并指定每人完成其中一項(xiàng),每項(xiàng)只交給其中一人去完成,設(shè)第i人完成第j項(xiàng)任務(wù)費(fèi)用為Cij(i,j=1,2,……,n),應(yīng)如何分配使總費(fèi)用最少。
因此,我們可得分配問題的系數(shù)矩陣效率矩陣分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型分配問題的標(biāo)準(zhǔn)形式(以人和任分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型為了建立標(biāo)準(zhǔn)分配問題的數(shù)學(xué)模型,我們引入n2個(gè)
0-1變量,并且得到該問題的數(shù)學(xué)模型.分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型為了建立標(biāo)準(zhǔn)分配問題的數(shù)學(xué)模例1.四個(gè)外語學(xué)院學(xué)生組成翻譯公司,接到一項(xiàng)業(yè)務(wù):把一個(gè)產(chǎn)品說明書翻譯成A、B、C、D四種語言,應(yīng)指派何人做何種工作,能使總的時(shí)間最少?
ABCD11494152117910313610541791513分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型需時(shí)(h)語種學(xué)生例1.四個(gè)外語學(xué)院學(xué)生組成翻譯公司,接到一項(xiàng)業(yè)務(wù):把一個(gè)產(chǎn)品解:這是一個(gè)標(biāo)準(zhǔn)的分配問題.若設(shè)0-1變量分配問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型可用表上作業(yè)法求解解:這是一個(gè)標(biāo)準(zhǔn)的分配問題.若設(shè)0-1變量分配問題的標(biāo)準(zhǔn)形匈牙利法匈牙利法的基本思想如果效率矩陣C中存在n
個(gè)位于不同行不同列的零元素,則只要令對(duì)應(yīng)于這些零元素位置的決策變量xij=1,其余的決策變量xij=0,則可取到最小值0,即該分配方案最優(yōu).
如:匈牙利法匈牙利法的基本思想匈牙利法匈牙利法的計(jì)算步驟第一步:找出效率矩陣每行的最小元素,并分別從每行中減去;如例1中效率矩陣為u1=4u2=7u3=5u4=9定理1如果從分配問題效率矩陣C每一行元素中分別減去(或加上)常數(shù)ui,從每一列分別減去(或加上)常數(shù)vj,得到新的效率矩陣C’,C’與C具有相同的最優(yōu)解.匈牙利法匈牙利法的計(jì)算步驟u1=4定理1如果從分配問題效匈牙利法匈牙利法的計(jì)算步驟第二步:找出效率矩陣每列的最小元素,再分別從每列中減去;接上,例1中效率矩陣轉(zhuǎn)換為C與C〞具有相同的最優(yōu)解v1=4v2=0v3=0v4=0匈牙利法匈牙利法的計(jì)算步驟C與C〞具有相同的最優(yōu)解v1匈牙利法匈牙利法的計(jì)算步驟第三步:確定能否找出n個(gè)位于不同行不同列的零元素集合來.根據(jù)定理2,該問題轉(zhuǎn)化為:要覆蓋上面矩陣中的所有零元素,至少需要多少條直線;怎么得到覆蓋零元素的最少直線數(shù)?從第一行開始,若該行只有一個(gè)零元素,就對(duì)這個(gè)零元素打上()號(hào),將打()號(hào)零元素所在列畫一條直線.若該行沒有零元素或有兩個(gè)以上零元素(已劃去的不計(jì)在內(nèi)),則轉(zhuǎn)下一行,依次進(jìn)行到最后一行;從第一列開始,若該列只有一個(gè)零元素就對(duì)這個(gè)零元素打上()號(hào)(同樣不考慮已劃去的零元素),再對(duì)打()號(hào)零元素所在行畫一條直線.若該列沒有零元素或有兩個(gè)以上零元素,則轉(zhuǎn)下一列,依次進(jìn)行到最后一列;重復(fù)1和2兩個(gè)步驟,可能出現(xiàn)三種情況:
定理2若矩陣A的元素可分成“0”和非“0”兩部分,則覆蓋“0”元素的最少直線數(shù)等于位于不同行不同列的“0”元素的最大個(gè)數(shù).匈牙利法匈牙利法的計(jì)算步驟定理2若矩陣A的元素可分成“0匈牙利法第一種情況覆蓋零元素的最少直線數(shù)(或打()號(hào)的零元素個(gè)數(shù))等于nZ=4+11+5+9=29h
1234A149415B117910C136105D1791513匈牙利法第一種情況Z=4+11+5+9=29h匈牙利法第二種情況打()號(hào)的零元素個(gè)數(shù)小于n,但未被劃去的零元素之間存在閉回路,這時(shí)可順著閉回路的走向,對(duì)每個(gè)間隔的零元素打一()號(hào),然后對(duì)所有打()號(hào)的零元素,或所在行,或所在列畫一條直線.匈牙利法第二種情況此問題有多個(gè)最優(yōu)解此問題有多個(gè)最優(yōu)解匈牙利法第三種情況矩陣中所有零元素或被劃去,或打上()號(hào),但打()號(hào)的零元素個(gè)數(shù)仍小于n.匈牙利法第三種情況匈牙利法匈牙利法的計(jì)算步驟第四步:為設(shè)法使每一行都有一個(gè)打()號(hào)零元素,需繼續(xù)按定理1對(duì)矩陣進(jìn)行變換:從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù)k;
對(duì)矩陣的每行,當(dāng)該行有直線覆蓋時(shí),令ui=0,無直線覆蓋時(shí),令ui=k;每行元素減去ui;對(duì)矩陣中有直線覆蓋的列,令vj=-k,對(duì)無直線覆蓋的列,令vj=0;每列元素減去vj;得到一個(gè)新矩陣;第五步:回到第三步,反復(fù)進(jìn)行,一直到矩陣的每一行都有一個(gè)打()號(hào)零元素為止,即找到了最優(yōu)分配方案.匈牙利法匈牙利法的計(jì)算步驟匈牙利法上述例子完成一、二、三步之后如右:轉(zhuǎn)向第四步:回到第三步:k=2u1=2u2=2u3=0u4=2v1=-2v2=-2v3=0v4=0匈牙利法上述例子完成一、二、三步之后如右:k=2u1=2v匈牙利法匈牙利法匈牙利法第四步:最優(yōu)解所對(duì)應(yīng)的最小值Z=3+2+4+3+9=21.匈牙利法第四步:最優(yōu)解所對(duì)應(yīng)的一般分配問題1、人數(shù)和工作任務(wù)不相等的分配問題(不平衡的分配問題)(1)人少任務(wù)多(2)人多任務(wù)少類似產(chǎn)銷不平衡問題(虛設(shè)假想的人,增添假想任務(wù))2、某項(xiàng)任務(wù)一定不能由某人做的分配問題
將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M3、一個(gè)人可做幾項(xiàng)任務(wù)的分配問題4、目標(biāo)函數(shù)為求最大值(最大化的分配問題) 效率矩陣中元素全為負(fù)數(shù),根據(jù)定理1,讓效率矩陣中所有元素變成非負(fù)數(shù),再利用匈牙利法求解.一般分配問題1、人數(shù)和工作任務(wù)不相等的分配問題(不平衡的分配例1.已知下列五名運(yùn)動(dòng)員各種姿勢(shì)的游泳成績(各為50m)如下表.試問如何從中選拔一個(gè)4×50m混合泳的接力隊(duì),使預(yù)期的比賽成績?yōu)樽詈茫?/p>
趙錢張王周仰泳37.732.938.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1需時(shí)(s)隊(duì)員項(xiàng)目不平衡的分配問題例1.已知下列五名運(yùn)動(dòng)員各種姿勢(shì)的游泳成績(各為50m)如下解:非標(biāo)準(zhǔn)的分配問題,先轉(zhuǎn)化成標(biāo)準(zhǔn)分配問題.一般分配問題
趙錢張王周仰泳37.732.938.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1E00000需時(shí)(s)隊(duì)員項(xiàng)目解:非標(biāo)準(zhǔn)的分配問題,先轉(zhuǎn)化成標(biāo)準(zhǔn)分配問題.一般分配問題不平衡的分配問題不平衡的分配問題不平衡的分配問題不平衡的分配問題不平衡的分配問題不平衡的分配問題某任務(wù)一定不能由某人做的分配問題例2.分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù),考慮任務(wù)E必須完成,其它4項(xiàng)可任選3項(xiàng)完成。試確定最優(yōu)分配方案,使完成任務(wù)的總時(shí)間最少。
ABCDE甲2529314237乙3938262033丙3427284032丁2442362345某任務(wù)一定不能由某人做的分配問題例2.分配甲、乙、丙、某任務(wù)一定不能由某人做的分配問題解:1)這是不平衡的分配問題,首先轉(zhuǎn)換為標(biāo)準(zhǔn)型,再用匈牙利法求解。2)由于任務(wù)數(shù)多于人數(shù),所以假定一名虛擬人,設(shè)為戊。因?yàn)楣ぷ鱁必須完成,故設(shè)戊完成E的時(shí)間為M(M是非常大的數(shù)),其余效率系數(shù)為0,則標(biāo)準(zhǔn)型效率矩陣表為:
ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M某任務(wù)一定不能由某人做的分配問題解:1)這是不平衡的分某任務(wù)一定不能由某人做的分配問題解續(xù):用匈牙利法求出最優(yōu)分配方案為:即甲-B,乙-D,丙-E,丁-A,任務(wù)C放棄,最少時(shí)間為105h。某任務(wù)一定不能由某人做的分配問題解續(xù):用匈牙利法求出最優(yōu)一個(gè)人可做幾項(xiàng)任務(wù)的分配問題若某人可同時(shí)做幾項(xiàng)任務(wù),則將該人化作相同的
幾個(gè)“人”來接受分配,且費(fèi)用系數(shù)取值相同.例如:丙可以同時(shí)任職A和C工作,求最優(yōu)分配方案。
ABCD甲37.732.938.837.0乙43.433.142.234.7丙33.328.538.930.4
ABCD甲37.732.938.837.0乙43.433.142.234.7丙33.328.538.930.4丙33.328.538.930.4一個(gè)人可做幾項(xiàng)任務(wù)的分配問題若某人可同時(shí)做幾項(xiàng)任務(wù),則將該一個(gè)人可做幾項(xiàng)任務(wù)的分配問題例2.分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù),考慮其中一人完成兩項(xiàng),其他每人完成一項(xiàng)。試確定最優(yōu)分配方案,使完成任務(wù)的總時(shí)間最少。
ABCDE甲2529314237乙3938262033丙3427284032丁2442362345一個(gè)人可做幾項(xiàng)任務(wù)的分配問題例2.分配甲、乙、丙、丁四個(gè)一個(gè)人可做幾項(xiàng)任務(wù)的分配問題解:虛擬戊,它完成任務(wù)的效率由每列最小效率構(gòu)成,則標(biāo)準(zhǔn)型效率矩陣表為:
ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊2427262032一個(gè)人可做幾項(xiàng)任務(wù)的分配問題解:虛擬戊,它完成任務(wù)的效率由例2續(xù)分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。每個(gè)人呢完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù),考慮任務(wù)A由甲或丙完成,任務(wù)C由丙或丁完成,任務(wù)E由甲、乙或丁完成,且規(guī)定4人中丙或丁完成兩項(xiàng)任務(wù),其他每人完成一項(xiàng)。試確定最優(yōu)分配方案,使完成任務(wù)的總時(shí)間最少。
ABCDE甲2529314237乙393826
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年語文考查項(xiàng)目與實(shí)施計(jì)劃試題及答案
- 小學(xué)一年級(jí)語文技能提升試題及答案
- 浙江省浙北G2聯(lián)盟2022-2023學(xué)年高一下學(xué)期4月期中聯(lián)考生物學(xué)試題(含答案)
- 2024年統(tǒng)計(jì)學(xué)考試學(xué)習(xí)難點(diǎn)闡述試題及答案
- 2024年汽車維修工輪胎與懸掛試題及答案
- 小學(xué)一年級(jí)語文試題及答案全面展示
- 二手車評(píng)估的心理因素分析試題及答案
- 2024年市場(chǎng)營銷領(lǐng)域的案例分析能力試題及答案
- 2024年計(jì)算機(jī)基礎(chǔ)知識(shí)測(cè)驗(yàn)試題及答案
- 2024年小學(xué)六年級(jí)語文考試的試題及答案總結(jié)
- 創(chuàng)意AI時(shí)代人工智能ppt模板課件
- 工程項(xiàng)目管理(第五版)第三章
- 《設(shè)計(jì)色彩——色彩的基礎(chǔ)知識(shí)》PPT課件(完整版)
- 客戶受電工程竣工檢驗(yàn)意見書(南網(wǎng))
- 基于單片機(jī)控制的異步電動(dòng)機(jī)變頻調(diào)速系統(tǒng)的設(shè)計(jì)
- 泛光照明施工方案(DOC)
- 土地使用權(quán)(住宅用地)市場(chǎng)比較法評(píng)估測(cè)算表
- DFMEA全解(完整版)
- (最新整理)世界水利發(fā)展史
- 超市新員工進(jìn)職[新版]ppt課件
- (完整版)護(hù)士延續(xù)注冊(cè)體檢表(總2頁)
評(píng)論
0/150
提交評(píng)論