數(shù)學(xué)建模指派問(wèn)題論文

..目錄一問(wèn)題重述2二模型假設(shè)2三匈牙利法述2四問(wèn)題分析3五問(wèn)題實(shí)現(xiàn)31問(wèn)題重述32問(wèn)題求解32.1由匈牙利法構(gòu)造目標(biāo)函數(shù)32.2模型建立33模型解析34程序?qū)崿F(xiàn)3六結(jié)果顯示及min求解3七模型深入31模型建立32進(jìn)展求解33程序分析3八模型檢驗(yàn)3九整體總結(jié)3十參考文獻(xiàn)3一問(wèn)題重述指派問(wèn)題亦稱平衡指派問(wèn)題僅研究人數(shù)與事數(shù)相等、一人一事及一事一人的情形。現(xiàn)有的不平衡指派問(wèn)題將研究圍擴(kuò)大到人數(shù)與事數(shù)可以不等、一人一事或一人多事及一事一人的情形。日?；顒?dòng)中也不乏人數(shù)與事數(shù)可以不等、一人多事及一事多人的情形，這類事務(wù)呈現(xiàn)了廣義指派問(wèn)題的實(shí)際背景。平衡指派問(wèn)題是特殊形式的平衡運(yùn)輸問(wèn)題，可運(yùn)用匈亞利法、削高排除法和縮陣分析法等特殊方法求解。另一方面，正是平衡指派問(wèn)題的這種特殊性，使得不平衡指派問(wèn)題不能按常規(guī)技術(shù)轉(zhuǎn)化為平衡指派問(wèn)題。因此，各種不平衡指派問(wèn)題需要確立相應(yīng)的有效解法１問(wèn)題的提出及其數(shù)學(xué)模型廣義指派問(wèn)題并非奇特和抽象的設(shè)想，相反，該問(wèn)題可以從司空見(jiàn)慣的日常事務(wù)中引出。現(xiàn)在我們就運(yùn)用匈牙利法，去實(shí)現(xiàn)n個(gè)人，n件工作的指派問(wèn)題。二模型假設(shè)1假設(shè)一共有n個(gè)人，n件工作，即人數(shù)與工作數(shù)相等。2假設(shè)每個(gè)人的都能從事某項(xiàng)工作，但是付出的代價(jià)不同。3假設(shè)求解代價(jià)最小的解。4甲乙丙丁四個(gè)人，ABCD四項(xiàng)工作，要求每人只能做一項(xiàng)工作，每項(xiàng)工作只由一人完成，問(wèn)如何指派總時(shí)間最短？三匈牙利法述第一步：找出矩陣每行的最小元素，分別從每行中減去這個(gè)最小元素；第二步：再找去矩陣每列的最小元素，分別從各列減去這個(gè)最小元素；第三步：經(jīng)過(guò)這兩步變換后，矩陣的每行每列至少都有了一個(gè)零元素，接著根據(jù)以下準(zhǔn)那么進(jìn)展試指派，找出覆蓋上面矩陣中所有零元素至少需要多少條直線；〔1〕從第一行開(kāi)場(chǎng)，假設(shè)該行只有一個(gè)零元素打上〔〕號(hào)。對(duì)打〔〕號(hào)零元素所在列劃一條直線。假設(shè)該行沒(méi)有零元素或有兩個(gè)以上零元素〔已劃去的不計(jì)在〕，那么轉(zhuǎn)下一行，一直到最后一行為止；〔2〕從第一列開(kāi)場(chǎng)，假設(shè)該列只有一個(gè)零元素就對(duì)這個(gè)零元素打上〔〕號(hào)〔同樣不考慮已劃去的零元素〕，對(duì)打〔〕號(hào)零元素所在行劃一條直線。假設(shè)該列沒(méi)有零元素或還有兩個(gè)以上零元素，那么轉(zhuǎn)下一列，并進(jìn)展到最后一列；〔3〕重復(fù)〔1〕、〔2〕兩個(gè)步驟，可能出現(xiàn)三種情況：矩陣每行都有一個(gè)打〔〕號(hào)零元素，很顯然，按照上述步驟得到的打〔〕的零元素都位于不同行不同列，因此就找到了問(wèn)題的答案；有多于兩行或兩列存在兩個(gè)以上零元素，即出現(xiàn)了零元素的閉回路，這個(gè)時(shí)候可順著閉回路的走向，對(duì)每個(gè)間隔的零元素打上〔〕號(hào)，然后對(duì)所有打〔〕號(hào)零元素或所有列或所在行劃一條直線。矩陣中所有零元素或打上〔〕號(hào)，或被劃去，但打〔〕號(hào)零元素個(gè)數(shù)小于m。第四步：為了設(shè)法使每行都有一個(gè)打〔〕的零元素，就要繼續(xù)對(duì)矩陣進(jìn)展變換；〔1〕從矩陣未被直線覆蓋的元素找出最小元素k；〔2〕對(duì)矩陣的每行，當(dāng)該行有直線覆蓋時(shí)，令=0，無(wú)直線覆蓋的，令=k；〔3〕對(duì)矩陣的每列，當(dāng)該列有直線覆蓋時(shí)，令=-k，無(wú)直線覆蓋的，令=0；〔4〕得列一個(gè)變換后的矩陣，其中每個(gè)元素=--。第五步：回到第三步，反復(fù)進(jìn)展，一直到矩陣中每一行都有一個(gè)打〔〕的零元素為止，即找到最優(yōu)分配方案為止。四問(wèn)題分析指派問(wèn)題的標(biāo)準(zhǔn)形式〔以人和事為例〕如下。有n個(gè)人和n項(xiàng)任務(wù)，第i個(gè)人做第j件事的費(fèi)用為，要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使完成這n項(xiàng)任務(wù)的費(fèi)用最少。一般把目標(biāo)函數(shù)的系數(shù)寫為矩陣形式，稱矩陣為系數(shù)矩陣〔CoefficientMatrix〕，也稱為效益矩陣或價(jià)值矩陣。矩陣的元素〔i,j=1,2,…n〕表示分配第i個(gè)人去完成第j項(xiàng)任務(wù)時(shí)的效益。一般地，以表示給定的資源分配用于給定活動(dòng)時(shí)的有關(guān)效益〔時(shí)間，費(fèi)用，價(jià)值等〕，且然后我們求解最小〔最大〔這里不再討論〕〕代價(jià)和模型，當(dāng)然，作為可行解，矩陣的每列元素中都有且只有一個(gè)1，以滿足約束條件式〔3〕。每行元素中也有且只有一個(gè)1，以滿足約束條件〔2〕。指派問(wèn)題n!個(gè)可行解。如果要求解最大值時(shí)，我們將構(gòu)造一個(gè)新的矩陣，使，其中是一個(gè)足夠大的常數(shù)。一般取中最大的元素作為，求解，所得的解就是原問(wèn)題的解。事實(shí)上，由可的此結(jié)論。五問(wèn)題實(shí)現(xiàn)1問(wèn)題重述問(wèn)題甲乙丙丁四個(gè)人，ABCD四項(xiàng)工作，要求每人只能做一項(xiàng)工作，每項(xiàng)工作只由一人完成，問(wèn)如何指派總時(shí)間最短？每個(gè)人的對(duì)每項(xiàng)工作的代價(jià)如下：2問(wèn)題求解開(kāi)場(chǎng)求解2.1由匈牙利法構(gòu)造目標(biāo)函數(shù)引入0-1變量xij，xij=1：第i人做第j項(xiàng)工作xij=0：第i人不做第j項(xiàng)工作約束條件：(i=1,2,…,92j=1,2,…,20)2.2模型建立即一項(xiàng)任務(wù)只由一個(gè)人完成一人只能完成一項(xiàng)任務(wù)求出目標(biāo)函數(shù)3模型解析根據(jù)指派問(wèn)題的最優(yōu)性定理，求最優(yōu)解的問(wèn)題可以轉(zhuǎn)換為求效益矩陣的大1元素組的問(wèn)題。匈牙利法的一般計(jì)算步驟為：步驟1：對(duì)效益矩陣進(jìn)展初等變換，使每行每列都出現(xiàn)0元素。1.

從效益矩陣A中每一行減去該行的最小元素；2.

再在所得矩陣中每一列減去該列的最小元素，得矩陣D；步驟2：將矩陣D中0元素置為1元素，非0元素置為0元素，得矩陣E。步驟3：確定獨(dú)立1元素組。1.

在矩陣E中含有1元素的各行中選擇1元素最少的行，比擬該行中各1元素所在的列中1元素的個(gè)數(shù)，選擇1元素的個(gè)數(shù)最少的那一列中的1元素；2.

將所選的1元素所在的行和列的元素置為0；3.

重復(fù)第2步和第3步，直到?jīng)]有1元素為止，即得到一個(gè)獨(dú)立1元素組。步驟4：判斷是否為最大獨(dú)立1元素組。1.

如果所得獨(dú)立1元素組為原效益矩陣的最大獨(dú)立1元素組〔即1元素的個(gè)數(shù)等于矩陣的階數(shù)〕，那么已得到最優(yōu)解，停頓計(jì)算；2.

如果所得獨(dú)立1元素組還不是原效益矩陣的最大獨(dú)立1元素組，那么繼續(xù)尋找可擴(kuò)路的方法對(duì)其進(jìn)展擴(kuò)，進(jìn)展下一步；步驟5：利用尋找可擴(kuò)路方法確定最大獨(dú)立1元素組。1.

做最少的直線覆蓋矩陣D的所有0元素；2.

在沒(méi)有被直線覆蓋的局部找出最小元素，在沒(méi)有被直線覆蓋的各行減去此最小元素，在沒(méi)有被直線覆蓋的各列上加上此最小元素，得到一個(gè)新的矩陣，返回第二步。4程序?qū)崿F(xiàn)這里我們運(yùn)用c++語(yǔ)言進(jìn)展編程進(jìn)展求解/************************************************************************//*zhipai2.cppAuthor:路遙Date:2012-12-1Description:需要在同樣的目錄下建立一個(gè)input.txt的文件夾在里面寫入每個(gè)人從事不同的工作代價(jià)，首行要寫入幾階方程，然后是每個(gè)人的不同工作代價(jià)，用空格隔開(kāi)。每人一行，見(jiàn)下面數(shù)字形式。用匈牙利法，實(shí)現(xiàn)n個(gè)人，n件工作的指派問(wèn)題。Input:input.txt格式為代價(jià)矩陣維度n，和矩陣容，例如：43584685425859252Output:控制臺(tái)輸出指派矩陣，例如0001001010000100*//************************************************************************/#include<iostream>#include<fstream>usingnamespacestd;#defineMAX_N100intnn;//輸入矩陣的維度nnvoidprintMatrix(inta[MAX_N][MAX_N]){ inti,j; for(i=0;i<nn;i++) { for(j=0;j<nn;j++) cout<<a[i][j]<<""; cout<<endl; }}intmain(){ intc[MAX_N][MAX_N],b[MAX_N][MAX_N]; intquan[MAX_N][MAX_N],cha[MAX_N][MAX_N]; introwZero[MAX_N],colZero[MAX_N]; introwCheck[MAX_N],colCheck[MAX_N]; inti,j,k; ifstreaminput("input.txt"); if(!input) { cout<<"Openinputfilefailed."<<endl; system("pause"); exit(1); }//讀取輸入文件input>>nn; for(i=0;i<nn;i++) { for(j=0;j<nn;j++) { input>>c[i][j]; b[i][j]=c[i][j]; } } input.close();//每行減去該行最小for(i=0;i<nn;i++) { intmin=b[i][0]; for(j=1;j<nn;j++) { if(b[i][j]<min) min=b[i][j]; } for(j=0;j<nn;j++) b[i][j]-=min; }//每列減去該列最小for(j=0;j<nn;j++) { intmin=b[0][j]; for(i=1;i<nn;i++) { if(b[i][j]<min) min=b[i][j]; } for(i=0;i<nn;i++) b[i][j]-=min; }//開(kāi)場(chǎng)嘗試進(jìn)展試指派assign://初始化標(biāo)記數(shù)組和計(jì)數(shù)數(shù)組for(i=0;i<nn;i++) { rowZero[i]=colZero[i]=0; rowCheck[i]=colCheck[i]=0; for(j=0;j<nn;j++) quan[i][j]=cha[i][j]=0; }//計(jì)算每行每列0元素個(gè)數(shù)for(i=0;i<nn;i++) for(j=0;j<nn;j++) if(b[i][j]==0) { rowZero[i]++; colZero[j]++; } boolflag;//直到盡可能多的0元素都被圈出和劃掉為止do { flag=false;//尋找只有一個(gè)0元素的行，加圈劃叉for(i=0;i<nn;i++) {if(rowZero[i]==1)//該行只有一個(gè)0元素 {//cout<<"rowZerofound:"<<i<<endl; flag=true;//找到0元素,加圈劃叉for(j=0;j<nn;j++) { if(b[i][j]==0&&quan[i][j]==0&&cha[i][j]==0) { quan[i][j]=1; rowZero[i]--; colZero[j]--; for(k=0;k<nn;k++) { if(b[k][j]==0&&quan[k][j]==0&&cha[k][j]==0) { cha[k][j]=1; rowZero[k]--; colZero[j]--; } } break; } } //break; } }//尋找只有一個(gè)0元素的列，加圈劃叉for(j=0;j<nn;j++) {if(colZero[j]==1)//該列只有一個(gè)0元素 {flag=true;//找到0元素,加圈劃叉for(i=0;i<nn;i++) { if(b[i][j]==0&&quan[i][j]==0&&cha[i][j]==0) { quan[i][j]=1; rowZero[i]--; colZero[j]--; for(k=0;k<nn;k++) { if(b[i][k]==0&&quan[i][k]==0&&cha[i][k]==0) { cha[i][k]=1; rowZero[i]--; colZero[k]--; } } break; } } //break; } } }while(flag);//判斷是否還有0元素未被標(biāo)記intzeroNotMarked=0; for(i=0;i<nn;i++) zeroNotMarked+=rowZero[i]; while(zeroNotMarked!=0) { /*從剩有0元素最少的行(列)開(kāi)場(chǎng)，比擬這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要"禮讓〞選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)展，直到所有0元素都已圈出和劃掉為止。*/ intleastZeroRow=0; while(rowZero[leastZeroRow]==0) leastZeroRow++; for(i=leastZeroRow+1;i<nn;i++) { if(rowZero[i]!=0&&rowZero[i]<rowZero[leastZeroRow]) leastZeroRow=i; }i=leastZeroRow;//得到0元素最少的行標(biāo)intleastZeroCol=0; while(colZero[leastZeroCol]==0) leastZeroCol++; for(j=0;j<nn;j++) { if(b[i][j]==0&&quan[i][j]==0&&cha[i][j]==0&&colZero[j]<colZero[leastZeroCol]) leastZeroCol=j; }j=leastZeroCol;//得到0元素最少的列標(biāo)//圈出b[i][j],劃掉i行和j列其余0元素quan[i][j]=1; rowZero[i]--; colZero[j]--; zeroNotMarked--; for(k=0;k<nn;k++) { if(b[i][k]==0&&quan[i][k]==0&&cha[i][k]==0) { cha[i][k]=1; rowZero[i]--; colZero[k]--; zeroNotMarked--; } } for(k=0;k<nn;k++) { if(b[k][j]==0&&quan[k][j]==0&&cha[k][j]==0) { cha[k][j]=1; rowZero[k]--; colZero[j]--; zeroNotMarked--; } } } //printMatrix(quan);//假設(shè)quan元素的數(shù)目countQuan等于矩陣的階數(shù)nn,那么得出最優(yōu)解，否那么畫線intcountQuan=0; for(i=0;i<nn;i++) for(j=0;j<nn;j++) countQuan+=quan[i][j];if(countQuan<nn)//需要作直線覆蓋0元素 {//對(duì)沒(méi)有quan的行打勾for(i=0;i<nn;i++) { inttemp=0; for(k=0;k<nn;k++) temp+=quan[i][k]; if(temp==0) { rowCheck[i]=1; } } /*重復(fù)執(zhí)行(1)(2)，直到打不出新的勾為止：(1)對(duì)已打勾的行中含cha的元素的列打勾(2)對(duì)已打勾的列中含quan的元素的行打勾*/ intnewCheck=0; intcheck; do { check=newCheck; //(1) for(i=0;i<nn;i++) { if(rowCheck[i]==1) { for(j=0;j<nn;j++) { if(cha[i][j]==1&&colCheck[j]==0) { colCheck[j]=1; newCheck++; } } } } //(2) for(j=0;j<nn;j++) { if(colCheck[j]==1) { for(i=0;i<nn;i++) { if(quan[i][j]==1&&rowCheck[i]==0) { rowCheck[i]=1; newCheck++; } } } } }while(check!=newCheck);//(5)對(duì)rowCheck[]==0的行畫橫線，colCheck[]==1的列畫縱線//這就得到覆蓋所有0元素的最少直線數(shù)numLinesintnumLines=0; for(i=0;i<nn;i++) { if(rowCheck[i]==0) numLines++; } for(j=0;j<nn;j++) { if(colCheck[j]==1) numLines++; } if(numLines!=countQuan) {cout<<"直線個(gè)數(shù)不等于畫圈0元素個(gè)數(shù)，試指派有誤"<<endl; }//假設(shè)numLines=countQuan<nn，須再變換當(dāng)前的系數(shù)矩陣，以找到nn個(gè)獨(dú)立的0元素if(numLines==countQuan&&numLines<nn) { /*變換矩陣b[i][j]以增加0元素：設(shè)沒(méi)有被直線覆蓋(rowCheck[i]==1&&colCheck[j]==0)的有所有元素中的最小元素為min2，然后打勾各行都減去min2；打勾各列都加上min2，將得到的矩陣重新進(jìn)展試指派*/i=0; while(rowCheck[i]==0)i++; j=0; while(colCheck[j]==1)j++; intmin2=b[i][j]; for(i=0;i<nn;i++) for(j=0;j<nn;j++) { if(b[i][j]<min2&&rowCheck[i]==1&&colCheck[j]==0) min2=b[i][j]; } for(i=0;i<nn;i++) { if(rowCheck[i]==1) { for(j=0;j<nn;j++) { b[i][j]-=min2; } } } for(j=0;j<nn;j++) { if(colCheck[j]==1) { for(i=0;i<nn;i++) { b[i][j]+=min2; } } }//將變換后的矩陣b[i][j]重新試指派gotoassign; } }//此時(shí)countQuan==nn,輸出指派結(jié)果cout<<"指派結(jié)果如下："<<endl;printMatrix(quan); system("pause"); return0;}六結(jié)果顯示及min求解Min〔z〕=4+5+2+2=13即求出最小代價(jià)。完成假設(shè)要求七模型深入將約束條件由整數(shù)數(shù)據(jù)變?yōu)樾?shù)數(shù)據(jù)且目標(biāo)函數(shù)由最小值化為最大值問(wèn)題的求解。假設(shè)有4件工作分派給4個(gè)人來(lái)做，每項(xiàng)工作只能由一人來(lái)做，每個(gè)人只能做一項(xiàng)工作。下表為各人對(duì)各項(xiàng)工作所具有的工作效率。問(wèn)應(yīng)該如何安排人選，及發(fā)揮個(gè)人特長(zhǎng)又能使總的效率最大。每個(gè)人完成各項(xiàng)任務(wù)需要的時(shí)間工人人ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.41模型建立數(shù)學(xué)模型為s.t.或1，i，j=1，2，3，42進(jìn)展求解本次我們使用matlab求解具體程序如下：function[y,fval]=maxzp(M,C)%M為C中元素的最大值[m,n]=size(C);C=M+zeros(n)-C;%將求極小值的目標(biāo)函數(shù)系數(shù)矩陣轉(zhuǎn)換成求極大值的系數(shù)矩陣M=1.0;C=C';f=C(:);Aeq=zeros(2*n,n*n);fori=1:nAeq(1:n,1+(i-1)*n:i*n)=eye(n,n);endfori=1:nAeq(n+i,1+(i-1)*n:i*n)=ones(1,n);endbeq=ones(2*n,1);lb=zeros(n*n,1);ub=ones(n*n,1);x=linprog(f,[],[],Aeq,beq,lb,ub);y=reshape(x,n,n);y=y';y=round(y);sol=zeros(n,n);fori=1:nforj=1:nify(i,j)==1sol(i,j)=C(j,i);endendendfval=sum(sol(:));fval=M*n-fval;%求出極大值的目標(biāo)函數(shù)值其中，C=[0.60.20.30.