生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題概述_第1頁
生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題概述_第2頁
生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題概述_第3頁
生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題概述_第4頁
生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題概述_第5頁
已閱讀5頁,還剩156頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題優(yōu)化建模與LINDO/LINGO軟件第5章內(nèi)容提要§5.1生產(chǎn)與銷售計劃問題§5.2有瓶頸設(shè)備的多級生產(chǎn)計劃問題§5.3下料問題§5.4面試順序與消防車調(diào)度問題§5.5飛機定位和飛行計劃問題§5.1生產(chǎn)與銷售計劃問題§5.1.1問題實例例5.1某公司用兩種原油(A和B)混合加工成兩種汽油(甲和乙)。甲、乙兩種汽油含原油A的最低比例分別為50%和60%,每噸售價分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫存量分別為500噸和1000噸,還可以從市場上買到不超過1500噸的原油A。原油A的市場價為:購買量不超過500噸時的單價為10000元/噸;購買量超過500噸但不超過1000噸時,超過500噸的部分8000元/噸;購買量超過1000噸時,超過1000噸的部分6000元/噸。該公司應(yīng)如何安排原油的采購和加工?!?.1.2建立模型問題分析安排原油采購、加工的目標(biāo)是利潤最大,題目中給出的是兩種汽油的售價和原油A的采購價,利潤為銷售汽油的收入與購買原油A的支出之差。這里的難點在于原油A的采購價與購買量的關(guān)系比較復(fù)雜,是分段函數(shù)關(guān)系,能否及如何用線性規(guī)劃、整數(shù)規(guī)劃模型加以處理是關(guān)鍵所在。模型建立設(shè)原油A的購買量為x(噸),根據(jù)題目所給數(shù)據(jù),采購的支出c(x)可表為如下的分段線性函數(shù)(以下價格以千元/噸為單位):(1)設(shè)原油A用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為x11和x12(噸),原油B用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為x21和x22(噸),則總的收入為4.8(x11+x21)+5.6(x12+x22)(千元)。于是本例的目標(biāo)函數(shù)(利潤)為(2)約束條件包括加工兩種汽油用的原油A、原油B庫存量的限制,和原油A購買量的限制,以及兩種汽油含原油A的比例限制,它們表示為(3)(4)(5)(6)(7)(8)由于(1)式中的c(x)不是線性函數(shù),(1)~(8)給出的是一個非線性規(guī)劃。而且,對于這樣用分段函數(shù)定義的c(x),一般的非線性規(guī)劃軟件也難以輸入和求解。能不能想辦法將該模型化簡,從而用現(xiàn)成的軟件求解呢?§5.1.3求解模型3種解法第1種解法將原油A的采購量x分解為三個量,即用x1,x2,x3分別表示以價格10、8、6千元/噸采購的原油A的噸數(shù),總支出為c(x)=10x1+8x2+6x3,且(9)這時目標(biāo)函數(shù)(2)變?yōu)榫€性函數(shù):(10)應(yīng)該注意到,只有當(dāng)以10千元/噸的價格購買x1=500(噸)時,才能以8千元/噸的價格購買x2(>0),這個條件可以表示為 (11)同理,只有當(dāng)以8千元/噸的價格購買x2=500(噸)時,才能以6千元/噸的價格購買x3(>0),于是(12)此外,x1,x2,x3的取值范圍是(13)由于有非線性約束(11),(12),(3)~(13)構(gòu)成非線性規(guī)劃模型。LINGO程序:Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12<x+500;x21+x22<1000;0.5*x11-0.5*x21>0;0.4*x12-0.6*x22>0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;@bnd(0,x1,500);@bnd(0,x2,500);@bnd(0,x3,500);end將文件存儲儲并命名為為exam0501a.lg4,執(zhí)行菜單命命令“LINGO|Solve”,運運行該程序序得到:Localoptimalsolutionfound.Objectivevalue:4800.000Totalsolveriterations:26VariableValueReducedCostX11500.00000.000000X21500.00000.000000X120.0000000.000000X220.0000000.000000X10.0000000.000000X20.0000000.000000X30.0000000.000000X0.0000000.000000最優(yōu)解:用用庫存的的500噸噸原油A、、500噸噸原油B生生產(chǎn)1000噸汽油油甲,不購購買新的原原油A,利利潤為4800(千千元)但是此時LINGO得到的結(jié)結(jié)果只是一一個局部最優(yōu)解解可以用菜單單命令“LINGO|Options”在“GlobalSolver”選項卡卡上啟動全全局優(yōu)化((UseGlobalSolver)選項項,然后重重新執(zhí)行菜菜單命令““LINGO|Solve””,得得到:Globaloptimalsolutionfound.Objectivevalue:5000.002Extendedsolversteps:3Totalsolveriterations:187VariableValueReducedCostX110.0000000.000000X210.0000000.000000X121500.0000.000000X221000.0000.000000X1500.00000.000000X2499.99900.000000X30.9536707E-030.000000X1000.0000.000000此時LINGO得到到的結(jié)果是是一個全局最優(yōu)解解(Globaloptimalsolution):購買1000噸噸原油A,,與庫存的的500噸噸原油A和和1000噸原油B一起,共共生產(chǎn)2500噸汽汽油乙,利利潤為5000(千千元),高高于剛剛得得到的局部部最優(yōu)解對對應(yīng)的利潤潤4800(千元))。第2種解法法:引入0-1變量將((11)和和(12))轉(zhuǎn)化為線線性約束令y1=1,y2=1,y3=1分別表表示以10千元/噸噸、8千元元/噸、6千元/噸噸的價格采采購原油A,則約束束(11))和(12)可以替替換為(14)(15)(16)y1,y2,y3=0或1(17)(3)~((10),,(13))~(17)構(gòu)成混混合整數(shù)線線性規(guī)劃模模型,將它它輸入LINDO軟軟件:Max4.8x11+4.8x21+5.6x12+5.6x22-10x1-8x2-6x3stx-x1-x2-x3=0x11+x12-x<500x21+x22<10000.5x11-0.5x21>00.4x12-0.6x22>0x1-500y1<0x2-500y2<0x3-500y3<0x1-500y2>0x2-500y3>0endinty1inty2inty3運行行該該程程序序得得到到:OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLEVALUEREDUCEDCOSTY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.0000000.400000X1000.0000000.000000這個個結(jié)結(jié)果果與與前前面面非非線線性性規(guī)規(guī)劃劃模模型型用用全全局局優(yōu)優(yōu)化化得得到到的的結(jié)結(jié)果果相相同同。。第3種種解解法法直接接處處理理分分段段線線性性函函數(shù)數(shù)c(x)。。(1))式式表表示示的的函函數(shù)數(shù)c(x)如如圖圖5-1。。c(x)x1200090005000050010001500圖5-1分段線性函數(shù)c(x)圖形記x軸上上的的分分點點為為b1=0,b2=500,b3=1000,b4=1500。。當(dāng)當(dāng)x在第第1個個小小區(qū)區(qū)間間[b1,b2]時時,,記記x=z1b1+z2b2,z1+z2=1,,z1,z2≥0,因為為c(x)在在[b1,b2]是是線線性性的的,,所所以以c(x)=z1c(b1)+z2c(b2)。。同同樣樣,,當(dāng)當(dāng)x在第第2個個小小區(qū)區(qū)間間[b2,b3]時時,,x=z2b2+z3b3,z2+z3=1,,z2,z3≥0,c(x)=z2c(b2)+z3c(b3)。。當(dāng)當(dāng)x在第第3個個小小區(qū)區(qū)間間[b3,b4]時時,,x=z3b3+z4b4,z3+z4=1,,z3,z4≥0,c(x)=z3c(b3)+z4c(b4)。。為為了了表表示示x在哪哪個個小小區(qū)區(qū)間間,,引引入入0-1變變量量yk(k=1,2,3),,當(dāng)當(dāng)x在第第k個小小區(qū)區(qū)間間時時,,yk=1,,否否則則,,yk=0。。這這樣樣,z1,z2,z3,z4,y1,y2,y3應(yīng)滿滿足足(18)(19)(20)此時時x和c(x)可可以以統(tǒng)統(tǒng)一一地地表表示示為為(2))~((10)),,((18))~((22))也也構(gòu)構(gòu)成成一一個個混混合合整整數(shù)數(shù)線線性性規(guī)規(guī)劃劃模模型型,,可可以以用用LINDO求求解解。。不不過過,,我我們們還還是是將將它它輸輸入入LINGO軟軟件件,,因因為為其其擴擴展展性性更更好好((即即當(dāng)當(dāng)分分段段函函數(shù)數(shù)的的分分段段數(shù)數(shù)更更多多時時,,只只需需要要對對下下面面程程序序作作很很小小的的改改動動))。。輸輸入入的的LINGO模模型型如如下下::(22)輸入入的的LINGO模模型型如如下下::Model:SETS:Points/1..4/:b,c,y,z;!端端點點數(shù)數(shù)為為4,,即即分分段段數(shù)數(shù)為為3;ENDSETSDATA:b=050010001500;c=05000900012000;y=,,,0;!增增加加的的虛虛擬擬變變量量y(4)=0;ENDDATAMax=4.8*x11+4.8*x21+5.6*x12+5.6*x22-@sum(Points:c*z);x11+x12<x+500;x21+x22<1000;0.5*x11-0.5*x21>0;0.4*x12-0.6*x22>0;@sum(Points:b*z)=x;@for(Points(i)|i#eq#1:z(i)<=y(i));@for(Points(i)|i#ne#1:z(i)<=y(i-1)+y(i));@sum(Points:y)=1;@sum(Points:z)=1;@for(Points:@bin(y));end求解,得到的的結(jié)果如下((略去已知參參數(shù)b和c的的顯示結(jié)果)):Globaloptimalsolutionfound.Objectivevalue:5000.000Extendedsolversteps:0Totalsolveriterations:28VariableValueReducedCostX110.0000000.000000X210.0000001.600000X121500.0000.000000X221000.0000.000000X1000.0000.000000Y(1)0.000000-4600.000Y(2)0.000000-1200.000Y(3)1.0000000.000000Y(4)0.0000000.000000Z(1)0.0000000.000000Z(2)0.0000000.000000Z(3)1.0000000.000000Z(4)0.000000200.0000可見,得到的的最優(yōu)解和最最優(yōu)值與第2種解法相同同。備注這個個問題的關(guān)鍵鍵是處理分段段線性函數(shù),,我們推薦化化為整數(shù)線性性規(guī)劃模型的的第2,3種解解法,第3種種解法更具一一般性,其做做法如下。設(shè)一個n段線性函數(shù)f(x)的分點為引入zk將x和f(x)表示為(23)(24)zk和0-1變量量yk滿足(25)(26)(27)§5.2有有瓶頸設(shè)備的的多級生產(chǎn)計計劃問題§5.2.1問題實例例在給定的外部部需求和生產(chǎn)產(chǎn)能力等限制制條件下,按按照生產(chǎn)總費費用最小編制制未來若干個個生產(chǎn)周期的的最優(yōu)生產(chǎn)計計劃,這種問問題在文獻上上一般稱為批批量問題(LotsizingProblems)。我們通過下面面的具體例子子來說明這種種多級生產(chǎn)計計劃問題的優(yōu)優(yōu)化模型。這這里“多級””的意思是需需要考慮產(chǎn)品品是通過多個個生產(chǎn)階段((工藝過程))生產(chǎn)出來的的。例5.2某某工廠的主主要任務(wù)是通通過組裝生產(chǎn)產(chǎn)產(chǎn)品A,用用于滿足外部部市場需求。。A產(chǎn)品的產(chǎn)品品構(gòu)成與組裝裝過程見圖5-2:即D、E、F、、G是從外部部采購的零件件,先將零件件D、E組裝裝成部件B,,零件F、G組裝成部件件C,然后將將部件B、C組裝成產(chǎn)品品A出售。圖中弧上的數(shù)數(shù)字表示的是是組裝時部件件(或產(chǎn)品))中包含的零零件(或部件件)的數(shù)量((可以稱為消消耗系數(shù)),,例如DB弧弧上的數(shù)字““9”表示組組裝1個部件件B需要用到到9個零件D;BA弧上上的數(shù)字“5”表示組裝裝1件產(chǎn)品A需要用到5個部件B;;依此類推。瓶頸設(shè)備加工ABCDEFG579111315圖5-2產(chǎn)產(chǎn)品構(gòu)成與組組裝過程圖表5-1生生產(chǎn)計劃的原原始數(shù)據(jù)周次123456A的外部需求40010009010瓶頸能力

1000005000500010001000零部件編號ABCDEFG生產(chǎn)準備費用4005001000300200400100單件庫存費用120.61.00.040.030.040.04假設(shè)該工廠每每次生產(chǎn)計劃劃的計劃期為為6周(即每每次制定未來來6周的生產(chǎn)產(chǎn)計劃),只只有最終產(chǎn)品品A有外部需需求,目前收收到的訂單的的需求件數(shù)按按周的分布如如表5-1第第2行所示。。部件B、C是在該工廠廠最關(guān)鍵的設(shè)設(shè)備(可以稱稱為瓶頸設(shè)備備)上組裝出出來的,瓶頸頸設(shè)備的生產(chǎn)產(chǎn)能力非常緊緊張,具體可可供能力如表表5-1第3行所示(第第2周設(shè)備檢檢修,不能使使用)。B、、C的能力消消耗系數(shù)分別別為5和8,,即生產(chǎn)1件件B需要占用用5個單位的的能力,即生生產(chǎn)1件C需需要占用8個個單位的能力力。對于每種零部部件或產(chǎn)品,,如果工廠在在某一周訂購購或者生產(chǎn)該該零部件或產(chǎn)產(chǎn)品,工廠需需要付出一個個與訂購或生生產(chǎn)數(shù)量無關(guān)關(guān)的固定成本本(稱為生產(chǎn)產(chǎn)準備費用));如果某一一周結(jié)束時該該零部件或產(chǎn)產(chǎn)品有庫存存存在,則工廠廠必須付出一一定的庫存費費用(與庫存存數(shù)量成正比比)。這些數(shù)數(shù)據(jù)在表5-1第5、6行給出。按照工廠的信信譽要求,目目前接收的所所有訂單到期期必須全部交交貨,不能有有缺貨發(fā)生;;此外,不妨妨簡單地假設(shè)設(shè)目前該企業(yè)業(yè)沒有任何零零部件或產(chǎn)品品庫存,也不不希望第6周周結(jié)束后留下下沒有任何零零部件或產(chǎn)品品庫存。最后后,假設(shè)不考考慮生產(chǎn)提前前期,即假設(shè)設(shè)當(dāng)周采購的的零件馬上就就可用于組裝裝,組裝出來來的部件也可可以馬上用于于當(dāng)周組裝成成品A。在上述假設(shè)和和所給數(shù)據(jù)下下,如何制定定未來6周的的生產(chǎn)計劃??§5.2.2建立模型型問題分析這這個例子考慮慮的是在有限限的計劃期內(nèi)內(nèi),給定產(chǎn)產(chǎn)品結(jié)構(gòu)、生生產(chǎn)能力和相相關(guān)費用及零零部件或成品品(以下統(tǒng)稱稱為生產(chǎn)項目目)在離散的的時間段上((這里是周,,也可以是天天、月等)的的外部需求之之后,確定定每一生產(chǎn)項項目在每一時時間段上的生生產(chǎn)量(即即批量),使使總費用最最小.由于每每一生產(chǎn)項目目在每一時間間段上生產(chǎn)時時必須經(jīng)過生生產(chǎn)準備(Setup),所以以通常的討論論中總費用至至少應(yīng)考慮生生產(chǎn)準備費用用和庫存費用用.其實,細心的的讀者一定會會問:是否需需要考慮生產(chǎn)產(chǎn)的直接成本本(如原材料料成本、人力力成本、電力力成本等)??符號說明為了建立這類類問題的一般般模型,我們們定義如下數(shù)數(shù)學(xué)符號:N--------生生產(chǎn)項目總總數(shù)(本例中中N=7);T--------計計劃期長度度(本例中T=6);K--------瓶瓶頸資源種種類數(shù)(本例例中K=1));M--------一一個充分大大的正數(shù),在在模型中起到到使模型線性性化的作用;-----項項目i在t時段的外部需需求(本例中只有有產(chǎn)品A有外外部需求);-----項項目i在t時段的生產(chǎn)批批量;-----項項目i在t時段的庫存量量;-----項項目i在t時段是否生產(chǎn)產(chǎn)的標(biāo)志(0:不生產(chǎn)產(chǎn),1:生生產(chǎn));-----產(chǎn)產(chǎn)品結(jié)構(gòu)中中項目j對項目i的消耗系數(shù);S(i)-----產(chǎn)品結(jié)構(gòu)構(gòu)中項目i的直接后繼項項目集合;-----項項目i在t時段生產(chǎn)時的的生產(chǎn)準備費費用;-----項項目i在t時段的單件庫庫存費用;-----資資源k在t時段的能力上上限;---項目目i在t時段生產(chǎn)時,生產(chǎn)單個個產(chǎn)品占用資資源k的能力;δ(x)----這這個函數(shù)當(dāng)且且僅當(dāng)x>0時取值1,否則取取值0.在上述數(shù)學(xué)符號中,只有為決策變量;其余均為已知知的計劃參數(shù)數(shù)。目標(biāo)函數(shù)這個問題的目目標(biāo)是使生產(chǎn)產(chǎn)準備費用和和庫存費用的的總和最小。。因此,目標(biāo)標(biāo)函數(shù)應(yīng)該是是每個項目在在每個時段上上的生產(chǎn)準備備費用和庫存存費用的總和和,即(28)約束條件這個問題中的的約束有這么么幾類:每個個項目的物流流應(yīng)該守恒、、資源能力限限制應(yīng)該滿足足、每時段生生產(chǎn)某項目前前必須經(jīng)過生生產(chǎn)準備和非非負約束((對Yi,j是0-1約束束)。(29)資源能力限制制比較容易理理解,即(30)所謂物流守恒恒(假設(shè)Ii,0=0)(31)每時段生產(chǎn)某某項目前必須須經(jīng)過生產(chǎn)準準備,也就是是說當(dāng)Xit=0時Yit=0;Xit>0時Yit=1。這本來來是一個非線線性約束,但但是通過引入入?yún)?shù)M(很大的正數(shù)數(shù),表示每個個項目每個時時段的最大產(chǎn)產(chǎn)量)可以化化成線性約束束,即:總結(jié):這這個問題的優(yōu)優(yōu)化模型就是是在約束(29)(30)(31))下使目標(biāo)函函數(shù)(28))達到最小。?!?.2.3求解模型型本例生產(chǎn)項目目總數(shù)N=7(A、B、C、D、、E、F、G),計劃劃期長度T=6(周),,瓶頸資源種種類數(shù)K=1。只有A有外部需求求,所以di,t中只有d1,t可以取非非零需求求,即表表5-1中的第第2行的的數(shù)據(jù),,其他全全部為零零。參參數(shù)si,t、hi,t只與項目目i有關(guān),而而不隨時時段t變化,所所以可以以略去下下標(biāo)t,其數(shù)值值就是表表5-1中的最最后兩行行數(shù)據(jù)。。由于只有有一種資資源,參參數(shù)Ck,t可以略去去下標(biāo)k,其數(shù)值值就是表表5-1中的第第3行的的數(shù)據(jù);;而ak,I,t只與項目目i有關(guān),而而不隨時時段t變化,所所以可以以同時略略去下標(biāo)標(biāo)k和t,即a2=5,a3=8(其其他ai為0)。。從圖6-2中中容易得得到項目目i的直接后后繼項目目集合S(i)和消耗耗系數(shù)。。準備以下下的數(shù)據(jù)據(jù)文件((文本文文件exam0502.LDT,可可以看到到其中也也可以含含有注釋釋語句)):!項目目集合;A BCD EFG~!計劃劃期集合合;1 234 56~!需求求;400 1000 90 10000000000000000000000000000000000000~!能力力;100000 500050001000 1000~!生產(chǎn)產(chǎn)準備費費;400500 1000300 200400100~!庫存存費;120.61.0 0.040.030.04 0.04~!對能能力的消消耗系數(shù)數(shù);0 580 000~!項目目間的消消耗系數(shù)數(shù):req(i,j)表示示j用到到多少i;0000000500000070000000900000011000000013000000150000!數(shù)據(jù)據(jù)結(jié)束;對本例,,A的外外部總需需求為240,,所以任任何項目目的產(chǎn)量量不會超超過240×7×15<25000(從圖圖6-2可以知知道,這這里7××15已已經(jīng)是每每件產(chǎn)品品A對任任意一個個項目的的最大的的消耗系系數(shù)了)),所以以取M=25000就就已經(jīng)足足夠了。。本例中的的具體模模型可以以如下輸輸入LINGO軟件::MODEL:TITLE瓶瓶頸設(shè)備備的多級級生產(chǎn)計計劃;!從文文本文件件exam0502.LDT中讀取取數(shù)據(jù);SETS:!PART=項項目集合合,Setup=生產(chǎn)產(chǎn)準備費費,Hold=單單件庫存存成本,,A=對對瓶頸頸資源的的消耗系系數(shù);PART/@FILE('exam0502.LDT')/:Setup,Hold,A;!TIME=計計劃期集集合,Capacity=瓶頸頸設(shè)備的的能力;TIME/@FILE('exam0502.LDT')/:Capacity;!USES=項項目結(jié)構(gòu)構(gòu)關(guān)系,,Req=項項目之之間的消消耗系數(shù)數(shù);USES(PART,PART):Req;!PXT=項目目與時間間的派生生集合,,Demand=外外部需需求,X=產(chǎn)產(chǎn)量((批量)),Y=0/1變量,,INV=庫庫存;PXT(PART,TIME):Demand,X,Y,Inv;ENDSETS!目標(biāo)標(biāo)函數(shù);[OBJ]Min=@sum(PXT(i,t):setup(i)*Y(i,t)+hold(i)*Inv(i,t));!物流平衡衡方程;@FOR(PXT(i,t)|t#NE#1:[Bal]Inv(i,t-1)+X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t)));@FOR(PXT(i,t)|t#eq#1:[Ba0]X(i,t)-Inv(i,t)=Demand(i,t)+@SUM(USES(i,j):Req(i,j)*X(j,t)));!能力力約束;@FOR(TIME(t):[Cap]@SUM(PART(i):A(i)*X(i,t))<Capacity(t));!其他他約束;M=25000;@FOR(PXT(i,t):X(i,t)<=M*Y(i,t));@FOR(PXT:@BIN(Y));DATA:Demand=@FILE('exam0502.LDT');Capacity=@FILE('exam0502.LDT');Setup=@FILE('exam0502.LDT');Hold=@FILE('exam0502.LDT');A=@FILE('exam0502.LDT');Req=@FILE('exam0502.LDT');ENDDATAEND注意:由由于本例例有42個0-1變量量,LINGO演示版版是無法法求解的的表5-2生產(chǎn)計劃劃的最后后結(jié)果周次123456A的產(chǎn)量40100100B的產(chǎn)量2001000C的產(chǎn)量1055625D的產(chǎn)量18009000E的產(chǎn)量220011000F的產(chǎn)量137158125G的產(chǎn)量158259375LINDO求解解:得得到最優(yōu)優(yōu)目標(biāo)函函數(shù)值為為9245,結(jié)結(jié)果如如下:§5.3下料料問題§5.3下料料問題生產(chǎn)中常常會遇到到通過切切割、剪剪裁、沖沖壓等手手段,將將原材料料加工成成所需大大小這種種工藝過過程,稱稱為原料料下料((cuttingstock)問問題。按按照進一一步的工工藝要求求,確定定下料方方案,使使用料最最省,或或利潤最最大,是是典型的的優(yōu)化問問題。本本節(jié)通過過兩個實實例討論論用數(shù)學(xué)學(xué)規(guī)劃模模型解決決這類問問題的方方法。§5.3.1鋼鋼管下料料問題例5.3某某鋼管零零售商從從鋼管廠廠進貨,,將鋼管管按照顧顧客的要要求切割割后售出出。從鋼鋼管廠進進貨時得得到的原原料鋼管管都是19米長長。1)現(xiàn)現(xiàn)有一客客戶需要要50根根4米長長、20根6米米長和15根8米長的的鋼管。。應(yīng)如何何下料最最節(jié)????2)零零售商如如果采用用的不同同切割模模式太多多,將會會導(dǎo)致生生產(chǎn)過程程的復(fù)雜雜化,從從而增加加生產(chǎn)和和管理成成本,所所以該零零售商規(guī)規(guī)定采用用的不同同切割模模式不能能超過3種。此此外,該該客戶除除需要1)中的的三種鋼鋼管外,,還需要要10根根5米長長的鋼管管。應(yīng)如如何下料料最節(jié)省???問題1)的的求解問題分析首先,應(yīng)當(dāng)當(dāng)確定哪些些切割模式式是可行的的。所謂一一個切割模模式,是指指按照客戶戶需要在原原料鋼管上上安排切割割的一種組組合。例如如,我們可可以將19米長的鋼鋼管切割成成3根4米米長的鋼管管,余料為為7米顯然然,可行的的切割模式式是很多的的。其次,應(yīng)當(dāng)當(dāng)確定哪些些切割模式式是合理的的。通常假假設(shè)一個合合理的切割割模式的余余料不應(yīng)該該大于或等等于客戶需需要的鋼管管的最小尺尺寸。在這這種合理性性假設(shè)下,,切割模式式一共有7種,如表表5-3所所示。表5-3鋼鋼管下下料的合理理切割模式式4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料(米)模式14003模式23101模式32013模式41203模式51111模式60301模式70023問題化為在在滿足客戶戶需要的條條件下,按按照哪些種種合理的模模式,切割割多少根原原料鋼管,,最為節(jié)省省。而所謂謂節(jié)省,可可以有兩種種標(biāo)準,一一是切割后后剩余的總總余料量最最小,二是是切割原料料鋼管的總總根數(shù)最少少。下面將將對這兩個個目標(biāo)分別別討論。模型建立決策變量用xi表示按照第第i種模式(i=1,2,…,7)切切割的原料料鋼管的根根數(shù),顯然然它們應(yīng)當(dāng)當(dāng)是非負整整數(shù)。決策目標(biāo)以切割后剩剩余的總余余料量最小小為目標(biāo),,則由表1可得(32)以切割原料料鋼管的總總根數(shù)最少少為目標(biāo),,則有(33)下面分別在在這兩種目目標(biāo)下求解解。約束條件為滿足客戶戶的需求,,按照表1應(yīng)有模型求解1.將((32),,(34))~(36)構(gòu)成的的整數(shù)線性性規(guī)劃模型型(加上整整數(shù)約束))輸入LINDO如如下:Title鋼管下下料-最最小化余余量Min3x1+x2+3x3+3x4+x5+x6+3x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20x3+x5+2x7>=15endgin7求解可以得得到最優(yōu)解解如下:OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000即按照模式式2切割12根原料料鋼管,按按照模式5切割15根原料鋼鋼管,共27根,總總余料量為為27米。。顯然,在在總余料量量最小的目目標(biāo)下,最最優(yōu)解將是是使用余料料盡可能小小的切割模模式(模式式2和5的的余料為1米),這這會導(dǎo)致切切割原料鋼鋼管的總根根數(shù)較多。。2.將((33)~(36))構(gòu)成的整整數(shù)線性規(guī)規(guī)劃模型((加上整數(shù)數(shù)約束)輸輸入LINDO:Title鋼管下下料-最最小化鋼鋼管根數(shù)Minx1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5>=50x2+2x4+x5+3x6>=20x3+x5+2x7>=15endgin7求解,可以以得到最優(yōu)優(yōu)解如下::OBJECTIVEFUNCTIONVALUE1)25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000即按照模式式2切割15根原料料鋼管,按按模式5切切割5根,,按模式7切割5根根,共27根,可算算出總余料料量為35米。與上上面得到的的結(jié)果相比比,總余料料量增加了了8米,但但是所用的的原料鋼管管的總根數(shù)數(shù)減少了2根。在余余料沒有什什么用途的的情況下,,通常選擇擇總根數(shù)最最少為目標(biāo)標(biāo)。問題2)的的求解問題分析按按照解解問題1))的思路,,可以通過過枚舉法首首先確定哪哪些切割模模式是可行行的。但由由于需求的的鋼管規(guī)格格增加到4種,所以以枚舉法的的工作量較較大。下面面介紹的整整數(shù)非線性性規(guī)劃模型型,可以同同時確定切切割模式和和切割計劃劃,是帶有有普遍性的的方法。同1)類似似,一個合合理的切割割模式的余余料不應(yīng)該該大于或等等于客戶需需要的鋼管管的最小尺尺寸(本題題中為4米米),切割割計劃中只只使用合理理的切割模模式,而由由于本題中中參數(shù)都是是整數(shù),所所以合理的的切割模式式的余量不不能大于3米。此外外,這里我我們僅選擇擇總根數(shù)最最少為目標(biāo)標(biāo)進行求解解。模型建立決策變量由由于不不同切割模模式不能超超過3種,,可以用xi表示按照第第i種模式(i=1,2,3))切割的原原料鋼管的的根數(shù),顯顯然它們應(yīng)應(yīng)當(dāng)是非負負整數(shù)。設(shè)所使用的第第i種切割模式式下每根原原料鋼管生生產(chǎn)4米長長、5米長長、6米長長和8米長長的鋼管數(shù)數(shù)量分別為為r1i,r2i,r3i,r4i(非負整數(shù))。決策目標(biāo)以以切割割原料鋼管管的總根數(shù)數(shù)最少為目目標(biāo),即目目標(biāo)為(37)約束條件為為滿足足客戶的需需求,應(yīng)有有(38)(39)(40)(41)每一種切割割模式必須須可行、合合理,所以以每根原料料鋼管的成成品量不能能超過19米,也不不能少于16米(余余量不能大大于3米)),于是(42)(43)(44)模型求解(37)~(44))構(gòu)成這個個問題的優(yōu)優(yōu)化模型。。由于在((38)~(41))式中出現(xiàn)現(xiàn)了決策變變量的乘積積,所以這這是一個整整數(shù)非線性性規(guī)劃模型型,雖然用用LINGO軟件可可以直接求求解,但我我們發(fā)現(xiàn)在在較低版本本的LINGO軟件件中需要運運行很長時時間也難以以得到最優(yōu)優(yōu)解。為了了減少運行行時間,可可以增加一一些顯然的的約束條件件,從而縮縮小可行解解的搜索范范圍。例如,由于于3種切割割模式的排排列順序是是無關(guān)緊要要的,所以以不妨增加加以下約束束:(45)又例如,我我們注意到到所需原料料鋼管的總總根數(shù)有著著明顯的上上界和下界界。首先,,無論如何何,原料鋼鋼管的總根根數(shù)不可能能少于(根)其次,考慮慮一種非常常特殊的生生產(chǎn)計劃::第一種切切割模式下下只生產(chǎn)4米鋼管,,一根原料料鋼管切割割成4根4米鋼管,,為滿足50根4米米鋼管的需需求,需要要13根原原料鋼管;;第二種切切割模式下下只生產(chǎn)5米、6米米鋼管,一一根原料鋼鋼管切割成成1根5米米鋼管和2根6米鋼鋼管,為滿滿足10根根5米和20根6米米鋼管的需需求,需要要10根原原料鋼管;;第三種切割割模式下只只生產(chǎn)8米米鋼管,一一根原料鋼鋼管切割成成2根8米米鋼管,為為滿足15根8米鋼鋼管的需求求,需要8根原料鋼鋼管。于是是滿足要求求的這種生生產(chǎn)計劃共共需13+10+8=31根根原料鋼管管,這就得得到了最優(yōu)優(yōu)解的一個個上界。所所以可增加加以下約束束:(46)將(37))~(46)構(gòu)成的的模型輸入入LINGO如下::將(37))~(46)構(gòu)成的的模型輸入入LINGO如下::model:Title鋼管下下料-最最小化鋼鋼管根數(shù)的的LINGO模型;min=x1+x2+x3;x1*r11+x2*r12+x3*r13>=50;x1*r21+x2*r22+x3*r23>=10;x1*r31+x2*r32+x3*r33>=20;x1*r41+x2*r42+x3*r43>=15;4*r11+5*r21+6*r31+8*r41<=19;4*r12+5*r22+6*r32+8*r42<=19;4*r13+5*r23+6*r33+8*r43<=19;4*r11+5*r21+6*r31+8*r41>=16;4*r12+5*r22+6*r32+8*r42>=16;4*r13+5*r23+6*r33+8*r43>=16;x1+x2+x3>=26;x1+x2+x3<=31;x1>=x2;x2>=x3;@gin(x1);@gin(x2);@gin(x3);@gin(r11);@gin(r12);@gin(r13);@gin(r21);@gin(r22);@gin(r23);@gin(r31);@gin(r32);@gin(r33);@gin(r41);@gin(r42);@gin(r43);end經(jīng)過LINGO求解解,得到輸輸出如下::Localoptimalsolutionfound.Objectivevalue:28.00000Extendedsolversteps:72Totalsolveriterations:3404ModelTitle:鋼鋼管下料料-最小化化鋼管根數(shù)數(shù)的LINGO模型型VariableValueReducedCostX110.000001.000000X210.000001.000000X38.0000001.000000R112.0000000.000000R123.0000000.000000R130.0000000.000000R211.0000000.000000R220.0000000.000000R230.0000000.000000R311.0000000.000000R321.0000000.000000R330.0000000.000000R410.0000000.000000R420.0000000.000000R432.0000000.000000即按照模式式1、2、、3分別切切割10、、10、8根原料鋼鋼管,使用用原料鋼管管總根數(shù)為為28根。。第一種切切割模式下下一根原料料鋼管切割割成3根4米鋼管和和1根6米米鋼管;第第二種切割割模式下一一根原料鋼鋼管切割成成2根4米米鋼管、1根5米鋼鋼管和1根根6米鋼管管;第三種種切割模式式下一根原原料鋼管切切割成2根根8米鋼管管。如果充分利利用LINGO建模模語言的能能力,使用用集合和屬屬性的概念念,可以編編寫以下LINGO程序,這這種方法更更具有一般般的通用性性,并有利利于輸入更更大規(guī)模的的下料問題題的優(yōu)化模模型:model:Title鋼管下料-最小化鋼管管根數(shù)的LINGO模型;SETS:NEEDS/1..4/:LENGTH,NUM;!定義基本集集合NEEDS及其屬性LENGTH,NUM;CUTS/1..3/:X;!定義基本集集合CUTS及其屬性X;PATTERNS(NEEDS,CUTS):R;!定義派生集集合PATTERNS(這是一個個稠密集合合)及其屬屬性R;ENDSETSDATA:LENGTH=4568;NUM=50102015;CAPACITY=19;ENDDATAmin=@SUM(CUTS(I):X(I));!目標(biāo)函數(shù);@FOR(NEEDS(I):@SUM(CUTS(J):X(J)*R(I,J))>NUM(I));!滿足需求約約束;@FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))<CAPACITY);!合理切割模模式約束;@FOR(CUTS(J):@SUM(NEEDS(I):LENGTH(I)*R(I,J))>CAPACITY-@MIN(NEEDS(I):LENGTH(I)));!合理切割模模式約束;@SUM(CUTS(I):X(I))>26;@SUM(CUTS(I):X(I))<31;!人為增加約約束;@FOR(CUTS(I)|I#LT#@SIZE(CUTS):X(I)>X(I+1));!人為增加約約束;@FOR(CUTS(J):@GIN(X(J)));@FOR(PATTERNS(I,J):@GIN(R(I,J)));end求解這個模模型,得到到的結(jié)果與與前面的結(jié)結(jié)果完全相相同?!?.3.2易拉罐罐下料問題題例5.4某某公司司采用一套套沖壓設(shè)備備生產(chǎn)一種種罐裝飲料料的易拉罐罐,這種易易拉罐是用用鍍錫板沖沖壓制成的的(參見圖圖5-3))。易拉罐罐為圓柱形形,包括罐罐身、上蓋蓋和下底,,罐身高10厘米,,上蓋和下下底的直徑徑均為5厘厘米。該公公司使用兩兩種不同規(guī)規(guī)格的鍍錫錫板原料,,規(guī)格1的的鍍錫板為為正方形,,邊長24厘米;規(guī)規(guī)格2的鍍鍍錫板為長長方形,長長、寬分別別為32和和28厘米米。由于生生產(chǎn)設(shè)備和和生產(chǎn)工藝藝的限制,,對于規(guī)格格1的鍍鍍鍍錫板原料料,只可以以按照圖2中的模式式1、2或或3進行沖沖壓;對于于規(guī)格2的的鍍錫板原原料只能按按照模式4進行沖壓壓。使用模模式1、2、3、4進行每次次沖壓所需需要的時間間分別為1.5、2、1、3(秒)。。模式1模式2模式3模式4上蓋下底罐身圖5-3易易拉罐罐下料模式式該工廠每周周工作40小時,每每周可供使使用的規(guī)格格1、2的的鍍錫板原原料分別為為5萬張和和2萬張。。目前每只只易拉罐的的利潤為0.10元元,原料余余料損失為為0.001元/厘米2(如果周周末有罐身身、上蓋或或下底不能能配套組裝裝成易拉罐罐出售,也也看作是原原料余料損損失)。工工廠應(yīng)如何何安排每周周的生產(chǎn)??已知上蓋和和下底的直直徑d=5厘米,,可得其面面積為19.6厘米2表5-44種沖沖壓模式的的特征罐身個數(shù)底、蓋個數(shù)余料損失(厘米2)沖壓時間(秒)模式1110222.61.5模式224183.32模式3016261.81模式445169.53問題的目標(biāo)標(biāo)顯然應(yīng)是是易拉罐的的利潤扣除除原料余料料損失后的的凈利潤最最大,約束束條件除每每周工作時時間和原料料數(shù)量外,,還要考慮慮罐身和底底、蓋的配配套組裝。。模型建立決策變量用用xi表示按照第第i種模式的沖沖壓次數(shù)((i=1,2,3,4),,y1表示一周生生產(chǎn)的易拉拉罐個數(shù)。。為計算不不能配套組組裝的罐身身和底、蓋蓋造成的原原料損失,,用y2表示不配套套的罐身個個數(shù),y3表示不配套套的底、蓋蓋個數(shù)。雖雖然實際上上xi和y1,y2,y3應(yīng)該是整數(shù)數(shù)。但是由由于生產(chǎn)量量相當(dāng)大,,可以把它它們看成是是實數(shù),從從而用線性性規(guī)劃模型型處理。決策目標(biāo)假假設(shè)每每周生產(chǎn)的的易拉罐能能夠全部售售出,公司司每周的銷銷售利潤是是0.1y1。原料余余料損失包包括兩部分分:4種沖沖壓模式下下的余料損損失,和不不配套的罐罐身和底、、蓋造成的的原料損失失。按照前前面的計算算及表2的的結(jié)果,總總損失為0.001(222.6x1+183.3x2+261.8x3+169.5x4+157.1y2+19.6y3)。于是,決策策目標(biāo)為(47)約束條件時間約束::每周工作作時間不超超過40小小時=144000(秒),,由表2最最后一列得得(48)原料約束::每周可供使使用的規(guī)格格1、2的的鍍錫板原原料分別為為50000張和20000張,即(49)(50)配套約束::由表2一周生產(chǎn)產(chǎn)的罐身個個數(shù)為x1+2x2+4x4,一周生生產(chǎn)的底、、蓋個數(shù)為為10x1+4x2+16x3+5x4,因為應(yīng)盡盡可能將它它們配套組組裝成易拉拉罐銷售。。所以y1滿足(51)這時不配套套的罐身個個數(shù)y2,和不配套套的底、蓋蓋個數(shù)y3應(yīng)為(52)(53)(47)~(53))就是我們們得到的模模型,其中中(51))是一個非非線性關(guān)系系,不易直直接處理,,但是它可以以等價為以以下兩個線線性不等式式:(54)(55)模型求解將模型(47)~((50)和和(52))~(55)直接輸輸入LINDO(輸輸入LINGO也可可以),求求解時LINDO發(fā)發(fā)出警告信信息(程序序和警告信信息參見圖圖5-4))。圖中中錯誤編號號“66””的含義((參見第4章的錯誤誤代碼表))是:模型型中數(shù)據(jù)不不平衡,所所以發(fā)出警警告信息((注意,只只是警告信信息,所以以仍然可以以繼續(xù)求解解)。求解解結(jié)果是::OBJECTIVEFUNCTIONVALUE1)4298.337VARIABLEVALUEREDUCEDCOSTY1160250.0000000.000000X10.0000000.000050X240125.0000000.000000X33750.0000000.000000X420000.0000000.000000Y20.0000000.223331Y30.0000000.036484圖5-4模模型中中數(shù)據(jù)不平平衡的警告告信息這個結(jié)果可可靠嗎?由由于LINDO警告告模型中數(shù)數(shù)據(jù)之間的的數(shù)量級差差別太大,,所以我們們可以進行行預(yù)處理,,縮小數(shù)據(jù)據(jù)之間的差差別。實際際上,約束束(48))~(50)中右端端項的數(shù)值值過大(與與左端的系系數(shù)相比較較),LINDO在在計算中容容易產(chǎn)生比比較大的誤誤差,所以以出現(xiàn)此警警告信息。。為了了解解決決這這一一問問題題,,可可以以將將所所有有決決策策變變量量擴擴大大10000倍倍((相相當(dāng)當(dāng)于于xi以萬萬次次為為單單位位,,yi以萬萬件件為為單單位位))。。此此時時,,目目標(biāo)標(biāo)((47))可可以以保保持持不不變變((記記住住得得到到的的結(jié)結(jié)果果單單位位為為萬萬元元就就可可以以了了)),,而而約約束束((48))~((50))改改為為(56)(57)(58)將模型型(47))和((52)~(58))輸入入LINDO:!易易拉罐罐下料料:均均衡數(shù)數(shù)據(jù)Max0.100y1-0.2226x1-0.1833x2-0.2618x3-0.1695x4-0.1571y2-0.0196y3s.t.1.5x1+2.0x2+1.0x3+3.0x4<=14.4x1+x2+x3<=5x4<=2x1+2x2+4x4-y1>=010x1+4x2+16x3+5x4-2y1>=0x1+2x2+4x4-y1-y2=010x1+4x2+16x3+5x4-2y1-y3=0end求解得得到:OBJECTIVEFUNCTIONVALUE1)0.4298337VARIABLEVALUEREDUCEDCOSTY116.0250000.000000X10.0000000.000050X24.0125000.000000X30.3750000.000000X42.0000000.000000Y20.0000000.223331Y30.0000000.036484即模式式1不不使用用,模模式2使用用40125次次,模模式3使用用3750次,,模式式4使使用20000次,,可生生產(chǎn)易易拉罐罐160250個,,罐身身和底底、蓋蓋均無無剩余余,凈凈利潤潤為4298元元。5.4面試順順序與與消防防車調(diào)調(diào)度問問題面試順順序問問題例5.5有有4名同同學(xué)到到一家家公司司參加加三個個階段段的面面試::公司司要求求每個個同學(xué)學(xué)都必必須首首先找找公司司秘書書初試試,然然后到到部門門主管管處復(fù)復(fù)試,,最后后到經(jīng)經(jīng)理處處參加加面試試,并并且不不允許許插隊隊(即即在任任何一一個階階段4名同同學(xué)的的順序序是一一樣的的)。。由于于4名名同學(xué)學(xué)的專專業(yè)背背景不不同,,所以以每人人在三三個階階段的的面試試時間間也不不同,,如表表5-5所所示((單位位:分分鐘))。這這4名名同學(xué)學(xué)約定定他們們?nèi)坎棵嬖囋囃暌砸院笠灰黄痣x離開公公司。。假定定現(xiàn)在在時間間是早早晨8:00,,請問問他們們最早早何時時能離離開公公司??表5-5面面試試時間間要求求秘書初試主管復(fù)試經(jīng)理面試同學(xué)甲131520同學(xué)乙102018同學(xué)丙201010同學(xué)丁81015建立模模型實際上上,這這個問問題就就是要要安排排4名名同學(xué)學(xué)的面面試順順序,,使完完成全全部面面試所所花費費的時時間最最少。。記tij為第i名同學(xué)學(xué)參加加第j階段面面試需需要的的時間間(已已知),令令xij表示第第i名同學(xué)學(xué)參加加第j階段面面試的的開始始時刻刻(不不妨記記早上上8::00面試試開始始為0時刻刻)(i=1,2,3,4;j=1,2,3),T為完成成全部部面試試所花花費的的最少少時間間。優(yōu)化目目標(biāo)為為a.時時間間先后后次序序約束束(每每人只只有參參加完完前一一個階階段的的面試試后才才能進進入下下一個個階段段)::xij+tijxi,j+1(i=1,2,3,4;j=1,2)b.每每個階階段j同一時時間只只能面面試1名同同學(xué)::用0-1變量量yik表示第第k名同學(xué)學(xué)是否否排在在第i名同學(xué)學(xué)前面面(1表示示是,,0表表示否否),,則xij+tij–xkjTyik(i,k=1,2,3,4;j=1,2,3;i<k)xkj+tkj–xijT(1–yik)(i,k=1,2,3,4;j=1,2,3;i<k)約束條條件::可以將將非線線性的的優(yōu)化化目標(biāo)標(biāo)改寫寫為如如下線線性優(yōu)優(yōu)化目目標(biāo)::MinTs.t.Tx13+t13Tx23+t23Tx33+t33Tx43+t43MinTs.t.xij+tijxi,j+1(i=1,2,3,4;j=1,2)xij+tij–xkjTyik(i,k=1,2,3,4;j=1,2,3;i<k)xkj+tkj–xijT(1–yik)(i,k=1,2,3,4;j=1,2,3;i<k)xi3+ti3T(i=1,2,3,4)這個個問問題題的的0-1非非線線性性規(guī)規(guī)劃劃模模型型(當(dāng)當(dāng)然然所所有有變變量量還還有有非非負負約約束束,,變變量量yik還有有0-1約約束束):Model:min=T;T>=x13+t13;T>=x23+t23;T>=x33+t33;T>=x43+t43;x11+t11<=x12;x12+t12<=x13;x21+t21<=x22;x22+t22<=x23;x31+t31<=x32;x32+t32<=x33;x41+t41<=x42;x42+t42<=x43;求解解模模型型這個個模模型型可可以以如如下下輸輸入入LINGO:x11+t11-x21<=T*y12;x21+t21-x11<=T*(1-y12);x12+t12-x22<=T*y12;x22+t22-x12<=T*(1-y12);x13+t13-x23<=T*y12;x23+t23-x13<=T*(1-y12);x11+t11-x31<=T*y13;x31+t31-x11<=T*(1-y13);x12+t12-x32<=T*y12;x32+t32-x12<=T*(1-y13);x13+t13-x33<=T*y13;x33+t33-x13<=T*(1-y13);x11+t11-x41<=T*y14;x41+t41-x11<=T*(1-y14);x12+t12-x42<=T*y14;x42+t42-x12<=T*(1-y14);x13+t13-x43<=T*y14;x43+t43-x13<=T*(1-y14);x21+t21-x31<=T*y23;x31+t31-x21<=T*(1-y23);x22+t22-x32<=T*y23;x32+t32-x32<=T*(1-y23);x23+t23-x33<=T*y23;x33+t33-x23<=T*(1-y23);x21+t21-x41<=T*y24;x41+t41-x21<=T*(1-y24);x22+t22-x42<=T*y24;x42+t42-x22<=T*(1-y24);x23+t23-x43<=T*y24;x43+t43-x23<=T*(1-y24);x31+t31-x41<=T*y34;x41+t41-x31<=T*(1-y34);x32+t32-x42<=T*y34;x42+t42-x32<=T*(1-y34);x33+t33-x43<=T*y34;x43+t43-x33<=T*(1-y34);t11=13;t12=15;t13=20;t21=10;t22=20;t23=18;t31=20;t32=16;t33=10;t41=8;t42=10;t43=15;@bin(y12);@bin(y13);@bin(y14);@bin(y23);@bin(y24);@bin(y34);End用LINGO求求解解得得到到:Localoptimalsolutionfoundatiteration:4357Objectivevalue:84.00000VariableValueReducedCostT84.000000.000000X1336.000000.000000T1320.000000.000000X2356.000000.000000T2318.000000.000000X3374.000000.000000T3310.000000.000000X4321.000000.000000T4315.000000.000000X118.0000000.000000T1113.000000.000000X1221.000000.000000T1215.000000.000000VariableValueReducedCostX2121.000000.000000T2110.000000.000000X2236.000000.000000T2220.000000.000000X3137.500000.000000T3120.000000.000000X3257.750000.000000T3216.000000.000000X410.0000000.9999970T418.0000000.000000X4211.000000.000000T4210.000000.000000Y120.000000-83.99950Y130.0000000.000000Y141.00000083.99950Y230.000000-83.99950Y241.0000000.000000Y341.0000000.000000即所有面面試完成成至少需需要84分鐘,,面試順順序為4-1-2-3(即即丁-甲甲-乙-丙)。。早上8:00面試開開始,最最早9:24面面試可以以全部結(jié)結(jié)束。同樣,如如果利用用LINGO的建模語語言,可可以編寫寫一個更更一般的的LINGO模型。先先準備一一個數(shù)據(jù)據(jù)文件(文本文文件exam0505.txt),其中中的內(nèi)容容如下::!被面面試者集集合;1234~!面試試階段的的集合;123~!已知的面面試所需需要的時時間;1315201020182016108 10 15!數(shù)據(jù)據(jù)結(jié)束;LINGO模型型如下::Model:Title面面試問題題;SETS:!Person=被面面試者集集合,Stage=面試試階段的的集合;Person/@FILE(exam0505.txt)/;Stage/@FILE(exam0505.txt)/;!T=已已知的面面試所需需要的時時間,X=面面試開開始時間間;PXS(Person,Stage):T,X;!Y(i,k)=1:k排排在i前前,0::否則;PXP(Person,Person)|&1#LT#&2:Y;ENDSETSDATA:T=@FILE(exam0505.txt);ENDDATA[obj]min=MAXT;!MAXT是是面試的的最后結(jié)結(jié)束時間間;MAXT>=@max(PXS(i,j)|j#EQ#@size(stage):x(i,j)+t(i,j));!只有參加加完前一一個階段段的面試試后才能能進入下下一個階階段;@for(PXS(i,j)|j#LT#@size(stage):[ORDER]x(i,j)+t(i,j)<x(i,j+1));!同一一時間只只能面試試1名同同學(xué);@for(Stage(j):@for(PXP(i,k):[SORT1]x(i,j)+

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論