運(yùn)籌學(xué)實(shí)驗(yàn)報(bào)告

.運(yùn)籌與優(yōu)化課內(nèi)實(shí)驗(yàn) 檢測(cè)實(shí)驗(yàn)一：線性規(guī)劃問(wèn)題與對(duì)偶問(wèn)題的建模與求解一．線性規(guī)劃：滿足以下三個(gè)條件的稱之為線性規(guī)劃問(wèn)題：（1）決策變量的取值是連續(xù)的，既可以為整數(shù)，也可以喂分?jǐn)?shù)、小數(shù)或?qū)崝?shù)。（2）目標(biāo)函數(shù)是決策變量的線性函數(shù)。（3）結(jié)束條件是含決策變量的線性等式或者不等式。二．線性規(guī)劃模型的形式：2.1．一般形式nmaxminzcixii1ns.t.aijxj,bii1,2,mj1xj（）j1,2,n0xj0(2.1)矩陣形式maxminzcTXs.t.AX,b(2.2)X0（X0)其中XTc1,c2,cnTx1,x2,xn為決策向量，c為目標(biāo)函數(shù)的系數(shù)向量，精品文本.bb1,b2,bmT為常數(shù)向量，Aaijmn為系數(shù)矩陣。2.2．標(biāo)準(zhǔn)形式所謂線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式，是指目標(biāo)函數(shù)要求min所有約束條件都是等式約束，且所有決策定量都是非負(fù)的，即，，，，minf(x1x2xn)c1x1c2x2cnxna11x1a12x2a1nxnb1，a21x1a22x2a2nxnb2，s.t.am1x1am2x2amnxnbm，，，，，x1x2xn0三．原問(wèn)題與對(duì)偶問(wèn)題的表達(dá)形式和關(guān)系在線性規(guī)劃的對(duì)偶理論中，把如下線性規(guī)劃形式稱為原問(wèn)題的標(biāo)準(zhǔn)形式minf(X)c1x1c2x2cnxn，a11x1a12x2a1nxnb1，axax2a2nxb，21122n2s..tam1x1am2x2amnxnbm，x1，x2，，xn 0．而把如下線性規(guī)劃形式稱為對(duì)偶問(wèn)題的標(biāo)準(zhǔn)形式maxg(Y) b1y1 b2y2 bnyn，a11y1 a12y2 am1ym c1，a21y1 a22y2 am2ymc2，st..a1ny1 a2ny2 amnym cn，y1，y2，，ym 0．若用矩陣形式表示，則原問(wèn)題和對(duì)偶問(wèn)題分別可寫成如下形式：原問(wèn)題minf(X) CX，st..對(duì)偶問(wèn)題

AX b，X 0．maxg(Y) Y'b,YA C,s.t.Y 0.原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系見表原問(wèn)題（對(duì)偶問(wèn)題） 對(duì)偶問(wèn)題（原問(wèn)題）精品文本.min目標(biāo)函數(shù)系數(shù)右邊常數(shù)約束條件系數(shù)矩陣第i個(gè)約束條件為“≥”型第i個(gè)約束條件為“=”型第i個(gè)約束條件為“≤”型第j個(gè)變量≥0第j個(gè)變量無(wú)限制第j個(gè)變量≤0

max右邊常數(shù)目標(biāo)函數(shù)系數(shù)系數(shù)矩陣的轉(zhuǎn)置第i個(gè)變量≥0第i個(gè)變量無(wú)限制第i個(gè)變量≤0第j個(gè)約束條件為“≤”型第j個(gè)約束條件為“=”型第j個(gè)約束條件為“≥”型四．實(shí)際問(wèn)題與 lingo求解計(jì)算例（原問(wèn)題）：設(shè)某種植物每天至少需要 2g水，4g礦物質(zhì)，5g維生素。已知三種肥料A，B，C；其中A種肥料含有1g水，3g維生素；B種肥料含有3g水，2g礦物質(zhì)，1g維生素；C種肥料含有1g水，2g礦物質(zhì)，2g維生素。其中A種肥料6元每克，B種肥料4元每克，C種肥料7元每克，要求確定既要滿足植物生長(zhǎng)的營(yíng)養(yǎng)需求，又要費(fèi)用最省的選用肥料的方案。該問(wèn)題的模型為:minz=6*x1+4*x2+7*x3;x13*x32;3*x12*x2x34;x12*x22*x35;s.t.0;x1x20;x30;用lingo求解代碼如下：model:min=6*x1+4*x2+7*x3;x1+3*x3>=2;3*x1+2*x2+x3>=4;精品文本.x1+2*x2+2*x3>=5;x1>=0;x2>=0;x3>=0;end求解得：Globaloptimalsolutionfoundatiteration:0Objectivevalue:12.00000VariableValueReducedCostX10.0000003.000000X21.8333330.000000X30.66666670.000000RowSlackorSurplusDualPrice112.00000-1.00000020.000000-1.00000030.33333330.00000040.000000-2.00000050.0000000.00000061.8333330.00000070.66666670.000000通過(guò)上面結(jié)果可以知道，最佳費(fèi)用為12元，此時(shí)，需要A,B,C三種肥料為精品文本.0,1.833,0.667克。例（對(duì)偶形式）：設(shè)某公司生產(chǎn)A，B，C三種肥料，已知生產(chǎn)A種肥料贏利2元，生產(chǎn)B種肥料贏利4元，生產(chǎn)C種肥料贏利5元。而生產(chǎn)A需要1小時(shí)設(shè)備1，3小時(shí)設(shè)備2，1小時(shí)設(shè)備3；生產(chǎn)B需要2小時(shí)設(shè)備2，2小時(shí)設(shè)備3；需要3小時(shí)設(shè)備1，1小時(shí)設(shè)備2，2小時(shí)設(shè)備3；而設(shè)備1每天可用6小時(shí)，設(shè)備2每天可用4小時(shí)，設(shè)備3每天可用7小時(shí)，求怎樣安排生產(chǎn)才能使公司的贏利最大。該問(wèn)題的模型為：maxz=2*y1+4*y2+7*y3;y13*y2y36;2*y22*y34;3*y1y22*y37;s.t.0;y1y20;y30;用lingo求解model:max=2*y1+4*y2+5*y3;y1+3*y2+y3<=6;2*y2+2*y3<=4;3*y1+y2+2*y3<=7;y1>=0;y2>=0;y3>=0;end求解得：精品文本.Globaloptimalsolutionfoundatiteration:0Objectivevalue:12.00000VariableValueReducedCostY11.0000000.000000Y20.0000000.3333333Y32.0000000.000000RowSlackorSurplusDualPrice112.000001.00000023.0000000.00000030.0000001.83333340.0000000.666666751.0000000.00000060.0000000.00000072.0000000.000000例4.2.1（原問(wèn)題）：某企業(yè)利用3種原料B1，B2，B3生產(chǎn)2種產(chǎn)品A1，A2。3種原料的月供應(yīng)量和生產(chǎn)1噸產(chǎn)品A1，A2均可在市場(chǎng)銷售，企業(yè)應(yīng)如何安排月生產(chǎn)計(jì)劃，使總收益最大？單位產(chǎn)品消耗A1A2原料月供應(yīng)量原料（t）精品文本.B111150B223240B332300單位產(chǎn)品價(jià)格（萬(wàn)元2.41.8/t）設(shè)計(jì)劃生產(chǎn)產(chǎn)品 Ai的數(shù)量為xi（t/月），i=1，2，則所討論的原問(wèn)題的數(shù)學(xué)模型為：maxz=2.4*x1+1.8*x2;x1x21502*x13*x2240s.t.3*x12*x2300x10;x20;用lingo求解model:max=2.4*x1+1.8*x2;x1+x2<=150;2*x1+3*x2<=240;3*x1+2*x2<=300;x1>=0;x2>=0;end求解得：Globaloptimalsolutionfoundatiteration:0Objectivevalue:244.8000精品文本.VariableValueReducedCostX184.000000.000000X224.000000.000000RowSlackorSurplusDualPrice1244.80001.000000242.000000.00000030.0000000.120000040.0000000.7200000584.000000.000000624.000000.000000（對(duì)偶問(wèn)題）：設(shè)原料 B1，B2，B3的價(jià)格為 y1,y2,y3(萬(wàn)元/t)，顯然，應(yīng)有yi>=0,I=1,2,3.由原問(wèn)題的條件，生產(chǎn) 1t產(chǎn)品A1需消耗1t原料B1，2t原料B2,3t原料B3，可獲得收益為2.4萬(wàn)元。因此，若將生產(chǎn) 1t產(chǎn)品A1的這些原料賣出所得的收益為y1+2*y2+3*y3(萬(wàn)元)它必須不少于生產(chǎn) 1t產(chǎn)品A1所得的收益，對(duì)于該企業(yè)才是合算的。所以應(yīng)有 y1+2*y2+3*y3>=2.對(duì)于產(chǎn)品 A2，可類似得到y(tǒng)1+2*y2+3*y3>=1.8。同時(shí)，若買方（公司）欲購(gòu)買該工廠的全部原料，則應(yīng)付出150*y1+240*y2+300*y3萬(wàn)元（這也是該工廠賣出全部原料的總收益）。從買方角度應(yīng)使總支出金可能地少。因此，可得到線性規(guī)劃問(wèn)題。該問(wèn)題的模型為:精品文本.minf=150*y1+240*y2+300*y3y12*y23*y32.4y13*y22*y31.8s.t.y10;y20;y30;用lingo求解model:min=150*y1+240*y2+300*y3；y1+2*y2+3*y3>=2.4y1+3*y2+2*y3>=1.8;y1>=0;y2>=0;y3>=0;求解得：Globaloptimalsolutionfoundatiteration:4Objectivevalue:244.8000VariableValueReducedCostY10.00000042.00000Y20.12000000.000000Y30.72000000.000000Row SlackorSurplus DualPrice1 244.8000 -1.000000精品文本.20.000000-84.0000030.000000-24.0000040.0000000.00000050.12000000.00000060.72000000.000000五．實(shí)驗(yàn)分析1.針對(duì)上面的線性規(guī)劃問(wèn)題，每個(gè)問(wèn)題都相應(yīng)的給出了具體的對(duì)偶問(wèn)題，方便的比較。2.利用lingo軟件求解，速度快，精度高。實(shí)驗(yàn)二：基于匈牙利解法的指派問(wèn)題建模與求解一、指派問(wèn)題與匈牙利解法指派問(wèn)題又稱分配問(wèn)題，其用途非常廣泛，比如某公司指派 n個(gè)人去做 n件事，各人做不同的一件事，如何安排人員使得總費(fèi)用最少？若考慮每個(gè)職工對(duì)工作的效率（如熟練程度等），怎樣安排會(huì)使總效率達(dá)到最大？這些都是一個(gè)企業(yè)經(jīng)營(yíng)管理者必須考慮的問(wèn)題，所以該問(wèn)題有重要的應(yīng)用價(jià)值 .雖然指派問(wèn)題可以用 0-1規(guī)劃問(wèn)題來(lái)解，設(shè) X(I,J)是0-1變量, 用X(I,J)=1表示第I個(gè)人做第J件事,X(I,J)=0表示第I個(gè)人不做第J件事.設(shè)非負(fù)矩陣C（I，J）表示第I個(gè)人做第J件事的費(fèi)用， 則問(wèn)題可以寫成LINGO程序SETS:PERSON/1..N/;精品文本.WORK/1..N/;WEIGHT(PERSON,WORK):C,X;ENDSETSDATA:W=?ENDDATAMIN=@SUM(WEIGHT:C*X);@FOR(PERSON(I):@SUM(WORK(J):X(I,J))=1);@FOR(WORK(J):@SUM(PERSONM(I):X(I,J))=1);@FOR(WEIGHT:@BIN(X));其中2*N個(gè)約束條件是線性相關(guān)的 ,可以去掉任意一個(gè)而得到線性無(wú)關(guān)條件.但是由于有N^2個(gè)0-1變量,當(dāng)N很大時(shí)，用完全枚舉法解題幾乎是不可能的.而已有的0-1規(guī)劃都是用隱枚舉法做的，計(jì)算量較大 .對(duì)于指派問(wèn)題這種特殊的0-1規(guī)劃，有一個(gè)有效的方法——匈牙利算法，是 1955年W.W.Kuhn利用匈牙利數(shù)學(xué)家D.K?nig的二部圖G的最大匹配的大小等于 G的最小頂點(diǎn)覆蓋的大小的定理提出的一種算法，這種算法是多項(xiàng)式算法，計(jì)算量為 O(N3).匈牙利算法的基本原理是基于以下兩個(gè)定理 .定理1 設(shè)C=(Cij)n×n是指派問(wèn)題的效益矩陣，若將 C中的任一行（或任一列）減去該行（或該列）中的最小元素，得到新的效率矩陣 C’，則C’對(duì)應(yīng)的新的指派問(wèn)題與原指派問(wèn)題有相同的最優(yōu)解 .定理2 效率矩陣C中獨(dú)立的0元素的最多個(gè)數(shù)等于覆蓋所有 0元素的最少精品文本.直線數(shù).當(dāng)獨(dú)立零元素的個(gè)數(shù)等于矩陣的階數(shù)時(shí)就得到最優(yōu)解 .二．模型擴(kuò)展1、目標(biāo)函數(shù)最大化的指派問(wèn)題模型對(duì)于最大化的指派問(wèn)題nmaxfcijxiji,j1ni1xij1(j1,2,n)ns.t.xij1(i1,2,n)j1xij0或i,j1,2,n1不能將目標(biāo)函數(shù)改為nminzf(cij)xiji,j1來(lái)實(shí)現(xiàn)求解，因?yàn)樾傺览惴ㄒ恳粋€(gè)系數(shù)都為非負(fù) .因此，對(duì)于最大化的指派問(wèn)題，只能在效率矩陣 C=(cij)n×n找出最大的數(shù)M，然后進(jìn)行矩陣變換，即可以討論矩陣 B=M – C,其中 M=max(max(C))*ones(size(C))，將原指派問(wèn)題模型轉(zhuǎn)化為同解指派問(wèn)題模型：n nminz(Mcij)xijbijxiji,j1i,j1nxij1(j1,2,n)i1s.t.nxij1(i1,2,n)j1xij或1i,j1,2,n0再用匈牙利算法求解即可 .2、效率矩陣不是方陣的指派問(wèn)題模型精品文本.⑴若人多事少,可以添上一些虛擬的事,這些事被各人做的費(fèi)用可取為零 .⑵若人少事多,可以添上一些虛擬的人,他們做各事的費(fèi)用可取為零 .⑶若一個(gè)人可同時(shí)做幾件事 ,可以將這人化為相同的幾個(gè)人 ,費(fèi)用不變.⑷若規(guī)定某人不能做某事 ,求最小時(shí)則可令這人做這事的費(fèi)用為充分大的數(shù)(在MATLAB中可取為inf)；求最大時(shí)則可令這人做這事的費(fèi)用為 0，然后按目標(biāo)函數(shù)最大化的指派問(wèn)題數(shù)學(xué)模型的求解方式求解 .三．匈牙利解法的缺陷與改進(jìn)3.1、算法的不足之處指派問(wèn)題就是給定一個(gè) n階非負(fù)矩陣A={A(I,J)}, 求一個(gè)0-1矩陣X(I,J),使得f min AI,JXI,J眾所周知,求這個(gè)問(wèn)題的一個(gè)方法是 在1955年利用匈牙利數(shù)學(xué)家D.K?nig的關(guān)于矩陣中獨(dú)立0元素的定理(即矩陣中獨(dú)立零元素的最大個(gè)數(shù)等于覆蓋全部0元素的直線的最少條數(shù) )提出了解指派問(wèn)題的一種算法 .步驟一:將系數(shù)矩陣 A的各行元素分別減去本行中的最小元素 , 再將所得矩陣(仍記為A)的各列元素分別減去本列中的最小元素 .這樣所得矩陣 A的各行和各列中都有0元素.步驟二:求A的最大個(gè)數(shù)的獨(dú)立 0元素，如個(gè)數(shù)等于 n，則完成.不然進(jìn)行下一步.步驟三:求覆蓋矩陣A所有0元素的最少數(shù)目的直線,求A中所有未被直線覆蓋的元素中的最小數(shù) m，把未被直線覆蓋的行中各元素都減去 m，再把A的被直線覆蓋的各列中各元素都加上 m.轉(zhuǎn)步驟二.精品文本.這是一種正確的多項(xiàng)式算法，但是我們發(fā)現(xiàn)現(xiàn)有的文獻(xiàn)中具體實(shí)現(xiàn)步驟二的算法是有缺陷的，敘述如下：現(xiàn)有的求最大個(gè)數(shù)的獨(dú)立 0元素的算法是:步驟一:找只有一個(gè)沒有標(biāo)記的 0元素的行,如無(wú)轉(zhuǎn)步驟三步驟二:將該0元素標(biāo)記為獨(dú)立 0元素,并把該獨(dú)立0元素所在的列的其他 0元素標(biāo)記為非獨(dú)立 0元素,轉(zhuǎn)步驟一步驟三:找只有一個(gè)沒有標(biāo)記的 0元素的列,如無(wú)轉(zhuǎn)步驟五步驟四:將該0元素標(biāo)記為獨(dú)立 0元素,并把該獨(dú)立0元素所在的行的其他 0元素標(biāo)記為非獨(dú)立 0元素,轉(zhuǎn)步驟三步驟五:找沒有標(biāo)記的0元素,如無(wú),完成最大個(gè)數(shù)的獨(dú)立 0元素的尋求.步驟六:未標(biāo)記的0元素在每行及每列的個(gè)數(shù)都大于 1，按某種規(guī)則取某個(gè)0元素標(biāo)記為獨(dú)立 0元素,并把該獨(dú)立0元素所在的行和列的其他 0元素標(biāo)記為非獨(dú)立0元素,轉(zhuǎn)步驟一.對(duì)于已求出最大個(gè)數(shù)的獨(dú)立 0元素但個(gè)數(shù)小于n的矩陣A,一般文獻(xiàn)上介紹的求覆蓋全部零元素的方法是：步驟一:對(duì)所有無(wú)獨(dú)立0元素的行打?;步驟二:若無(wú)新打?的行,轉(zhuǎn)步驟六;步驟三:對(duì)新打?的行中的非獨(dú)立 0元素所在的列打 ?;步驟四:若無(wú)新打?的列,轉(zhuǎn)步驟六;步驟五:對(duì)新打? 的列中的獨(dú)立0元素所在的行打?.轉(zhuǎn)步驟二;步驟六:用直線覆蓋沒有打 ?的行與打?的列.3.2、算法漏洞分析精品文本.但是我們發(fā)現(xiàn),在求最大個(gè)數(shù)的獨(dú)立 0元素的方法中的步驟六有漏洞 .就是說(shuō)在當(dāng)行和列中未標(biāo)記的 0元素的個(gè)數(shù)都大于 1時(shí)在獨(dú)立0元素的確定上可能會(huì)把不應(yīng)當(dāng)是獨(dú)立 0元素的0元素錯(cuò)誤地確定為獨(dú)立 0元素，從而得不到最大個(gè)數(shù)的獨(dú)立0元素.一般文獻(xiàn)上介紹的求最大個(gè)數(shù)的獨(dú)立 0元素的方法中，當(dāng)矩陣中各行各列的無(wú)標(biāo)記的0元素的個(gè)數(shù)都大于 1時(shí)，求獨(dú)立0元素的規(guī)則有兩種:規(guī)則1: 可任選其中一個(gè)0元素為獨(dú)立0元素（本文用上標(biāo)加撇來(lái)標(biāo)記：0’），同時(shí)標(biāo)記同行和同列中其它 0元素為非獨(dú)立0元素（本文用加一橫線來(lái)標(biāo)記：0）.規(guī)則2: 若各行中無(wú)標(biāo)記的 0元素至少有兩個(gè)，?.從剩有0元素最少的行開始，比較這行各 0元素所在列中0元素的數(shù)目，選擇 0元素少的那列的這個(gè) 0元素為獨(dú)立0元素.然后標(biāo)記同行同列的其它 0元素為非獨(dú)立 0元素.現(xiàn)有的算法中的缺點(diǎn)在于在確定獨(dú)立零元素時(shí)不一定能得到最大個(gè)數(shù)的獨(dú)立零元素，從而算法會(huì)失敗.我們找到以下一個(gè)有 6個(gè)獨(dú)立0元素的6階矩陣A,其中每行每列都有二個(gè)或 2個(gè)以上的0元素，其中用 0’表示是獨(dú)立0元素，0表示劃線的0元素，1表示任意正數(shù)):0 1 1 0 1 10 0 1 1 1 11 0 0 1 1 1(1)1 1 1 0 0 01 1 1 1 0 01 0 0 1 1 1但是按照取第一行第一列的 0元素為獨(dú)立0元素時(shí)只能得到以下所示 5個(gè)獨(dú)立0元素，小于最大獨(dú)立0元素的個(gè)數(shù)6，而需要覆蓋全部零元素的直線的條數(shù)是6條豎線，導(dǎo)致算法失?。壕肺谋?0 1 1 0 1 10 0 1 1 1 11 0 0 1 1 1(2)1 1 1 0 0 01 1 1 1 0 01 0 0 1 1 1從以上例子可見文獻(xiàn)中敘述的獨(dú)立 0元素的求法不一定能得到最大數(shù)目的獨(dú)立零元素.我們可以用兩種方法構(gòu)造任意大于 6階的類似的例子，如以下 10階的兩個(gè)例子分別應(yīng)該有 10個(gè)獨(dú)立0元素，但按不當(dāng)?shù)剡x取獨(dú)立 0元素時(shí)只能得到 9個(gè)獨(dú)立0元素.01111110110110111111001111111100111111111001111111100111111111001111111110001111111001111111110011111111001111100111111111111001111111110111111111100011111110111111111000111111110111111001111111111110通過(guò)把這些矩陣作為對(duì)角塊，其余元素為正數(shù)的矩陣可以構(gòu)造更多的這種例子.3.3、算法的更正由于問(wèn)題出在求最大個(gè)數(shù)的獨(dú)立零元素上，我們?cè)谒惴ㄖ性黾恿死们?M-增廣路的方法[3]來(lái)保證能得到最大個(gè)數(shù)的獨(dú)立零元素 .我們提出的更正的完整的算法如下 :一、化約矩陣將系數(shù)矩陣A的各行元素分別減去本行中的最小元素 , 再將所得矩陣(仍記精品文本.為A)的各列元素分別減去本列中的最小元素.這樣所得矩陣A的各行和各列中都有0元素.二、標(biāo)記零元素找只有一個(gè)沒有標(biāo)記的0元素的行,將該0元素標(biāo)記為0’(獨(dú)立0元素),并把該0’所在的列的其他 0元素標(biāo)記為0(劃線零元素),轉(zhuǎn)1.如無(wú)轉(zhuǎn)2.⒉找只有一個(gè)沒有標(biāo)記的 0元素的列,將該0元素標(biāo)記為0’,并把該0’所在的行的其他 0元素標(biāo)記為0,轉(zhuǎn)2；如無(wú)轉(zhuǎn)3.⒊若未標(biāo)記的0元素在其所在的行及列的個(gè)數(shù)都大于 1，取未標(biāo)記的 0元素最少的行或列中取一個(gè)所在列或行上 0元素個(gè)數(shù)較少的零元素標(biāo)記為 0’,并把該0’所在的行和列的其他 0元素標(biāo)記為0,轉(zhuǎn)1；如無(wú),轉(zhuǎn)三.三、求最小點(diǎn)覆蓋(即最小直線覆蓋)⒈若0’的個(gè)數(shù)等于n，完成；否則，轉(zhuǎn) 2.⒉對(duì)所有沒有0’的行標(biāo)記為 S,對(duì)S行中的0所在列標(biāo)記為T,將T列上0’所在的行標(biāo)記為 TS，將S行T列上0標(biāo)記為0.⒊將S行和T列分別標(biāo)記為S'和T'，將TS改為S.如S行中的某行上的0位于未標(biāo)志的列上，標(biāo)記該列為T，如所有的T列上都有0’,將0’所在的行標(biāo)為TS.將S行T列上的0標(biāo)為為0,轉(zhuǎn)2.不然，若S行中的某行上的0位于未標(biāo)志某個(gè)列上，而該列上沒有0’，則存在M-增廣路，在增廣路上交換0和0’.取消行、列的標(biāo)記，轉(zhuǎn)三；若S行上不存在位于未標(biāo)志的列上的0,將S改為S'，轉(zhuǎn)四.四、進(jìn)一步化約矩陣用直線覆蓋標(biāo)記為 T'的列和沒有標(biāo)記為 S'的行.即最小點(diǎn)覆蓋是(X-S')?T',求矩陣中所有未被直線覆蓋的元素中的最小數(shù) m，把未被直線覆蓋的行中各元素都減去m，再把被直線覆蓋的各列中各元素都加上 m.去掉所有的標(biāo)記，轉(zhuǎn)二.四．實(shí)際問(wèn)題分析與求解4.1（基于匈牙利解法的問(wèn)題求解）：某出版社有A、B、C、D、E五名專業(yè)精品文本.翻譯，他們翻譯五種外文的速度（印刷字符 /小時(shí)）如表所示.若規(guī)定一名翻譯只能翻譯一種外文，問(wèn)：⑴若C翻譯不懂法語(yǔ)、D翻譯不懂英語(yǔ)（如表所示）如何安排效率最高？⑵若根據(jù)原文作者的要求， A翻譯必須翻譯德語(yǔ)，E翻譯必須翻譯日語(yǔ)，如何安排效率最高？語(yǔ)種英法俄德日翻譯A1000700800800600B80060010009001100C900/700900900D/1000700700800E700700700900900解析：⑴此問(wèn)題是一個(gè)有條件的指派問(wèn)題的求解，C翻譯不懂法語(yǔ)、D翻譯不懂英語(yǔ)，故設(shè)翻譯 C翻譯法語(yǔ)、翻譯 D翻譯英語(yǔ)的效率為零.于是，該有條件的指派問(wèn)題的效率矩陣 C為：100070080080060080060010009001100C90007009009001000700700800700700700900900目標(biāo)函數(shù)為：5maxz cijxij.i,j1將其化為求極小化問(wèn)題： bij=max{cij}-cij，于是精品文本.min1004003003005001000300200200400300500100200003005001002000B2001100400200200200090020000110010040040030010010000300300200400400400200200200200200200000010000min03001002004000300100200400300500020003005000200009001000009001000010000200300200100002003002002002001000020020010000所以，效率最高的最優(yōu)安排方案是 A翻譯英語(yǔ)、B翻譯俄語(yǔ)、C翻譯德語(yǔ)、D翻譯法語(yǔ)、E翻譯日語(yǔ).⑵若根據(jù)原文作者的要求， A翻譯必須翻譯俄語(yǔ)、E翻譯必須翻譯日語(yǔ)，可視為此時(shí)只有B、C、D三名翻譯需要安排任務(wù)，使之總的效率最高。語(yǔ)種英法俄翻譯B8006001000C900/700D/1000700于是，該指派問(wèn)題的效率矩陣 C為：8006001000C900070001000700目標(biāo)函數(shù)為：3maxz cijxij.i,j1精品文本.將其化為求極小化問(wèn)題： bij=max{cij}-cij，于是min2004000020040002004000B1001000300100090020009002001000030001000030010000300000min所以，在滿足A翻譯必須翻譯德語(yǔ)、E翻譯必須翻譯日語(yǔ)的前提下， B翻譯俄語(yǔ)、C翻譯英語(yǔ)、D翻譯法語(yǔ)，這樣分配時(shí)，效率最高 .4.2（標(biāo)準(zhǔn)指派問(wèn)題軟件求解） ：分配甲、乙、丙、丁、戊完成 A，B，C，D，E五項(xiàng)任務(wù)，每人完成一項(xiàng)，每項(xiàng)任務(wù)只能由一個(gè)人完成， 五個(gè)人完成任務(wù)所需時(shí)間如下表，做出合理安排，使總時(shí)間最少 .人ABCDE甲8610912乙9127119丙74358丁958118戊467511（1）Lingo程序求解代碼如下：model:sets:a/1..5/;time(a,a):t,n;endsetsdata:精品文本.t=8610912912711974358958118467511;enddatamin=@sum(time:t*n);@for(a(i):@sum(a(j):n(i,j))=1);@for(a(j):@sum(a(i):n(i,j))=1);end結(jié)果：Globaloptimalsolutionfoundatiteration:6Objectivevalue:30.00000VariableValueReducedCostT(1,1)8.0000000.000000T(1,2)6.0000000.000000T(1,3)10.000000.000000T(1,4)9.0000000.000000T(1,5)12.000000.000000T(2,1)9.0000000.000000T(2,2)12.000000.000000精品文本.T(2,3)7.0000000.000000T(2,4)11.000000.000000T(2,5)9.0000000.000000T(3,1)7.0000000.000000T(3,2)4.0000000.000000T(3,3)3.0000000.000000T(3,4)5.0000000.000000T(3,5)8.0000000.000000T(4,1)9.0000000.000000T(4,2)5.0000000.000000T(4,3)8.0000000.000000T(4,4)11.000000.000000T(4,5)8.0000000.000000T(5,1)4.0000000.000000T(5,2)6.0000000.000000T(5,3)7.0000000.000000T(5,4)5.0000000.000000T(5,5)11.000000.000000N(1,1)0.0000000.000000N(1,2)0.0000000.000000N(1,3)0.0000003.000000N(1,4)1.0000000.000000精品文本.N(1,5)0.0000003.000000N(2,1)0.0000001.000000N(2,2)0.0000006.000000N(2,3)0.0000000.000000N(2,4)0.0000002.000000N(2,5)1.0000000.000000N(3,1)0.0000003.000000N(3,2)0.0000002.000000N(3,3)1.0000000.000000N(3,4)0.0000000.000000N(3,5)0.0000003.000000N(4,1)0.0000002.000000N(4,2)1.0000000.000000N(4,3)0.0000002.000000N(4,4)0.0000003.000000N(4,5)0.0000000.000000N(5,1)1.0000000.000000N(5,2)0.0000004.000000N(5,3)0.0000004.000000N(5,4)0.0000000.000000N(5,5)0.0000006.000000RowSlackorSurplusDualPrice精品文本.130.00000-1.00000020.000000-9.00000030.000000-9.00000040.000000-5.00000050.000000-8.00000060.000000-5.00000070.0000001.00000080.0000003.00000090.0000002.000000100.0000000.000000110.0000000.000000（2）MATLAB求解此模型的代碼:C=[8610912;9127119;74358;958118;467511];n=size(C,1);C=C(:);A=[];B=[];Ae=zeros(2*n,n^2);fori=1:nforj=(i-1)*n+1:n*iAe(i,j)=1;end精品文本.fork=i:n:n^2Ae(n+i,k)=1;endendBe=ones(2*n,1);Xm=zeros(n^2,1);XM=ones(n^2,1);[x,z]=linprog(C,A,B,Ae,Be,Xm,XM);x=reshape(x,n,n);disp('×?ó??a???ó:');?aAssignment=round(x)disp('×?ó??a?a:');zOptimizationterminated.最優(yōu)解矩陣為:Assignment=00000000010010001000精品文本.1 0 0 0 0最優(yōu)解為:z=30.00003）基于改進(jìn)匈牙利算法的matlab程序代碼%主程序function[f,D,G]=assign(W)%指派問(wèn)題求最小費(fèi)用的主程序，如求最大效益，改 W=max(W(:))-W,f=max(W(:))*n-f即可輸入-W:指派問(wèn)題的系數(shù)矩陣,W(I,J)表示第I人做第j事的費(fèi)用輸出-D:行向量,第I人做第D(I)件事.-G:行向量，第J事讓第G(J)人做.-f:最小費(fèi)用null=min(W,[],2);f=sum(null);%null:各行最小元素;f:目標(biāo)函數(shù)值的改變.n=numel(null);%n權(quán)陣的階數(shù)W=W-repmat(null,1,n);%權(quán)陣各行減去本行最小元素null=min(W,[],1);f=f+sum(null);%null:權(quán)陣各列最小元素 ;f:目標(biāo)函數(shù)值的改變.W=W-repmat(null,n,1);%權(quán)陣各列減去本列最小元素，至此權(quán)陣各行各列至少有一個(gè)0while1精品文本.[D,G,E]=assignz(W,n);%調(diào)用標(biāo)記獨(dú)立0的程序assignz;S=find(D==0); %無(wú)獨(dú)立0的行標(biāo)ifisempty(S)return;end;%如有n個(gè)獨(dú)立0,完成指派工作[D,G,SP,TP]=assignln(D,G,E,S,n);%調(diào)用求最少劃線程序 assignlnnum=numel(SP)-numel(TP);%最少劃線數(shù)=n-numifnum %劃線數(shù)小于n時(shí),變換權(quán)陣null=setdiff(1:n,TP); %此null是沒有劃線的列標(biāo)m=min(min(W(SP,null))); %此m為未被直線覆蓋的元素中的最小數(shù)W(SP,null)=W(SP,null)-m;%未被直線覆蓋的元素都減去 mnull=setdiff(1:n,SP); %此add是劃過(guò)線的行標(biāo),標(biāo)記獨(dú)立0W(null,TP)=W(null,TP)+m;%余下的行和列加上 mf=f+m*num; %目標(biāo)函數(shù)值的改變.elsereturn; %劃線數(shù)=n時(shí)完成end;end;%子程序function[D,G,E]=assignz(W,n)%選獨(dú)立0的子程序C=zeros(n);C(find(W==0))=1;E=C;%C:未標(biāo)記的0;E:非獨(dú)立的0D=zeros(1,n);G=zeros(1,n);%第I人做第D(I)事.第J事讓第G(J)人做.u=sum(C,2);v=sum(C);%u(i)第i行中的未標(biāo)記的0的個(gè)數(shù),v(j)第j列中未標(biāo)記的0的個(gè)數(shù)whileany(u)精品文本.row=find(u==1,1);%行中只有一個(gè)未標(biāo)記的 0的第一個(gè)行標(biāo)whilerowcol=find(C(row,:)==1,1);%第row行0所在的列標(biāo)D(row)=col;G(col)=row;E(row,col)=0;u=u-C(:,col);v(col)=0;C(:,col)=0; %刪去第col列的0row=find(u==1,1); %為循環(huán)作預(yù)處理end; %這時(shí)行中不是只有一個(gè)未標(biāo)記的 0col=find(v==1,1); %求列中只有一個(gè)未標(biāo)記的 0的列標(biāo)whilecolrow=find(C(:,col)==1,1);%求零元素所在的行標(biāo) rowD(row)=col;G(col)=row;E(row,col)=0;%第row行第col列為獨(dú)立0v=v-C(row,:);u(row)=0;C(row,:)=0; %刪除第row行的0col=find(v==1,1); %為循環(huán)作預(yù)處理end;if any(u) %這時(shí)行列中未標(biāo)記的 0多于一個(gè)row=find(u,1);col=find(C(row,:),1);D(row)=col; G(col)=row;E(row,col)=0;u=u-C(:,col);u(row)=0;v=v-C(row,:);v(col)=0;C(:,col)=0;精品文本.C(row,:)=0;elsereturn;end;end;子程序function[D,G,SP,TP]=assignln(D,G,E,S,n)%劃線子程序un=S;SP=[];TP=[]; %記錄打勾的行標(biāo) SP及列標(biāo)TPF=zeros(n); %F用于追溯M-交替路while~isempty(S) %有新打勾的S行時(shí)[null,T]=find(E(S,:));%新打勾的S行中非獨(dú)立零元素所在的列 TT=setdiff(T,TP); %新打勾的列ifisempty(T)SP=union(SP,S);return;end%無(wú)新打勾的列時(shí)退出F(S,T)=E(S,T); %打勾的行列相交點(diǎn)的位置，用于追溯 M-交替路SP=union(SP,S);TP=union(TP,T);%已打勾的行標(biāo)SP及列標(biāo)TPStemp=G(T); %求新打勾的T列中獨(dú)立0所在的行P=find(Stemp==0); %新打勾的T列中不存在獨(dú)立 0，追溯M-增廣路if~isempty(P) %當(dāng)新打勾的某列上無(wú)獨(dú)立 0時(shí)Tun=T(P); %新打勾的T列中無(wú)獨(dú)立0的列標(biāo)[r,c]=find(E(S,Tun),1);%求S行Tun列中一個(gè)刪除0的位置row=S(r);col1=Tun(c); %刪除0位于row行,col1列while1精品文本.E(row,col1)=0;%刪除0改為獨(dú)立0col2=D(row);D(row)=col1; G(col1)=row;%改變指派的事和人ifismember(row,un)break;end; %當(dāng)追溯到row在un中時(shí)結(jié)束E(row,col2)=1;%獨(dú)立0改為刪除0row=find(F(:,col2),1);col1=col2;endS=find(D==0); un=S; SP=[];TP=[];F=zeros(n);%清除標(biāo)記,為循環(huán)作準(zhǔn)備elseS=Stemp;end;end;運(yùn)行結(jié)果;f=30D=1 5 3 2 4G=精品文本.1 4 3 5 24.3（非標(biāo)準(zhǔn)指派問(wèn)題 lingo解法）公司現(xiàn)有41個(gè)技術(shù)人員，其結(jié)構(gòu)和相應(yīng)的工資水平如下：工資情況 高級(jí)工程師 工程師 助理工程師 技術(shù)員人數(shù) 9 17 10 5日工資(元) 250 200 170 110公司承接4個(gè)工程項(xiàng)目，兩項(xiàng)是在 A地和B地現(xiàn)場(chǎng)施工監(jiān)理；另外兩項(xiàng)是 C和D地工程設(shè)計(jì)，主要工作在辦公室完成。各項(xiàng)目的合同對(duì)有關(guān)技術(shù)人員的收費(fèi)標(biāo)準(zhǔn)不同。收費(fèi)（元/天）高級(jí)工程師工程師助理工程師技術(shù)員A1000800600500B1500800700600C1300900700400D1000800700500各項(xiàng)目對(duì)專業(yè)技術(shù)人員結(jié)構(gòu)的要求工資情況項(xiàng)目ABCD高級(jí)工程師1～32～521～2工程師>=2>=2>=22～8助理工程師>=2>=2>=2>=1技術(shù)員>=1>=3>=1—總計(jì)<=10<=16<=11<=18精品文本.CD兩項(xiàng)目是在辦公室完成所以每人每天有 50元開支.如何合理地分配現(xiàn)有的技術(shù)力量，使公司每天的直接收益最大？Lingo求解代碼如下：model:sets:job/1..4/:e;worker/1..4/:a,b;link(job,worker):d,x;endsetsdata:a=917105;b=250200170110;d=1000800600500150080070060013009007004001000800700500;e=10161118;enddatamax=@sum(link(i,j):d(i,j)*x(i,j)-b(j)*x(i,j))-@sum(worker(j)|j#ge#3:50*@sum(job(i):x(i,j)));@for(worker(j):@sum(job(i):x(i,j))<=a(j));精品文本.@for(job(i):@sum(worker(j):x(i,j))<=e(i));x(1,1)>=1;x(1,1)<=3;x(2,1)>=2;x(2,1)<=5;x(3,1)>=2;x(3,1)<=2;x(4,1)>=1;x(4,1)<=2;x(1,2)>=2;x(2,2)>=2;x(3,2)>=2;x(4,2)>=2;x(4,2)<=8;x(1,3)>=2;x(2,3)>=2;x(3,3)>=2;x(4,3)>=1;x(1,4)>=1;x(2,4)>=3;x(3,4)>=1;@for(link:@gin(x));EndGlobaloptimalsolutionfound.Objectivevalue:30.00000Totalsolveriterations:10VariableValueReducedCostCAPACITY(W1)1.0000000.000000CAPACITY(W2)1.0000000.000000CAPACITY(W3)1.0000000.000000CAPACITY(W4)1.0000000.000000CAPACITY(W5)1.0000000.000000DEMAND(J1)1.0000000.000000DEMAND(J2)1.0000000.000000DEMAND(J3)1.0000000.000000DEMAND(J4)1.0000000.000000DEMAND(J5)1.0000000.000000精品文本.COST(W1,J1)8.0000000.000000COST(W1,J2)6.0000000.000000COST(W1,J3)10.000000.000000COST(W1,J4)9.0000000.000000COST(W1,J5)12.000000.000000COST(W2,J1)9.0000000.000000COST(W2,J2)12.000000.000000COST(W2,J3)7.0000000.000000CO