生產(chǎn)運作管理優(yōu)化

生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題優(yōu)化建模與LINDO/LINGO軟件內(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某公司用兩種原油（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)如何安排原油的采購和加工。§5.1.2建立模型問題分析安排原油采購、加工的目標是利潤最大，題目中給出的是兩種汽油的售價和原油A的采購價，利潤為銷售汽油的收入與購買原油A的支出之差。這里的難點在于原油A的采購價與購買量的關(guān)系比較復雜，是分段函數(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)（千元）。于是本例的目標函數(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)這時目標函數(shù)（2）變?yōu)榫€性函數(shù)：(10)應(yīng)該注意到，只有當以10千元/噸的價格購買x1=500（噸）時，才能以8千元/噸的價格購買x2（>0），這個條件可以表示為 (11)同理，只有當以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:26VariableValueReducedCost最優(yōu)解解:用庫存存的500噸原油油A、500噸原油油B生產(chǎn)1000噸汽油油甲，，不購購買新新的原原油A，利潤潤為4800（千元元）但是此此時LINGO得到的的結(jié)果果只是是一個個局部最最優(yōu)解解可以用用菜單單命令令“LINGO|Options”在“GlobalSolver”選項卡卡上啟啟動全全局優(yōu)優(yōu)化（（UseGlobalSolver）選項，然然后重新執(zhí)執(zhí)行菜單命命令“LINGO|Solve”,得到：Globaloptimalsolutionfound.Objectivevalue:5000.002Extendedsolversteps:3Totalsolveriterations:187VariableValueReducedCost此時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.000VARIABLEVALUEREDUCEDCOST這個結(jié)果與與前面非線線性規(guī)劃模模型用全局局優(yōu)化得到到的結(jié)果相相同。第3種解法直接處理分分段線性函函數(shù)c(x)。（1）式表示的的函數(shù)c(x)如圖5-1。c(x)x1200090005000050010001500圖5-1分段線性函數(shù)c(x)圖形記x軸上的分點點為b1=0,b2=500,b3=1000,b4=1500。當x在第1個小區(qū)間[b1,b2]時，記x=z1b1+z2b2，z1+z2=1，z1,z2≥0,因為c(x)在[b1,b2]是線性的，，所以c(x)=z1c(b1)+z2c(b2)。同樣，當當x在第2個小區(qū)間[b2,b3]時，x=z2b2+z3b3，z2+z3=1，z2,z3≥0,c(x)=z2c(b2)+z3c(b3)。當x在第3個小區(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)，當x在第k個小區(qū)間時時，yk=1，否則，yk=0。這樣,z1,z2,z3,z4,y1,y2,y3應(yīng)滿足(18)(19)(20)此時x和c(x)可以統(tǒng)一地地表示為（2）~（10），（18）~（22）也構(gòu)成一一個混合整整數(shù)線性規(guī)規(guī)劃模型，，可以用LINDO求解。不過過，我們還還是將它輸輸入LINGO軟件，因為為其擴展性性更好（即即當分段函函數(shù)的分段段數(shù)更多時時，只需要要對下面程程序作很小小的改動））。輸入的的LINGO模型如下：：(22)輸入的LINGO模型如下：：Model:SETS:Points/1..4/:b,c,y,z; !端點數(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é)結(jié)果果如如下下（（略略去去已已知知參參數(shù)數(shù)b和c的顯顯示示結(jié)結(jié)果果））：：Globaloptimalsolutionfound.Objectivevalue:5000.000Extendedsolversteps:0Totalsolveriterations:28VariableValueReducedCost可見見，，得得到到的的最最優(yōu)優(yōu)解解和和最最優(yōu)優(yōu)值值與與第第2種解解法法相相同同。。備注注這這個個問問題題的的關(guān)關(guān)鍵鍵是是處處理理分分段段線線性性函函數(shù)數(shù)，，我我們們推推薦薦化化為為整整數(shù)數(shù)線線性性規(guī)規(guī)劃劃模模型型的的第第2,3種解解法法，，第第3種解解法法更更具具一一般般性性，，其其做做法法如如下下。。設(shè)一一個個n段線線性性函函數(shù)數(shù)f(x)的分分點點為為引入入zk將x和f(x)表示示為為(23)(24)zk和0-1變量量yk滿足足(25)(26)(27)§5.2有瓶瓶頸頸設(shè)設(shè)備備的的多多級級生生產(chǎn)產(chǎn)計計劃劃問問題題§2.1問題題實實例例在給給定定的的外外部部需需求求和和生生產(chǎn)產(chǎn)能能力力等等限限制制條條件件下下，，按按照照生生產(chǎn)產(chǎn)總總費費用用最最小小編編制制未未來來若若干干個個生生產(chǎn)產(chǎn)周周期期的的最最優(yōu)優(yōu)生生產(chǎn)產(chǎn)計計劃劃，，這這種種問問題題在在文文獻獻上上一一般般稱稱為為批批量量問問題題（（LotsizingProblems）。。我們們通通過過下下面面的的具具體體例例子子來來說說明明這這種種多多級級生生產(chǎn)產(chǎn)計計劃劃問問題題的的優(yōu)優(yōu)化化模模型型。。這這里里““多多級級””的的意意思思是是需需要要考考慮慮產(chǎn)產(chǎn)品品是是通通過過多多個個生生產(chǎn)產(chǎn)階階段段（（工工藝藝過過程程））生生產(chǎn)產(chǎn)出出來來的的。。例5.2某工工廠廠的的主主要要任任務(wù)務(wù)是是通通過過組組裝裝生生產(chǎn)產(chǎn)產(chǎn)產(chǎn)品品A，用用于于滿滿足足外外部部市市場場需需求求。。A產(chǎn)品品的的產(chǎn)產(chǎn)品品構(gòu)構(gòu)成成與與組組裝裝過過程程見見圖圖2：即即D、E、F、G是從從外外部部采采購購的的零零件件，，先先將將零零件件D、E組裝裝成成部部件件B，零零件件F、G組裝成成部件件C，然后后將部部件B、C組裝成成產(chǎn)品品A出售。。圖中弧弧上的的數(shù)字字表示示的是是組裝裝時部部件（（或產(chǎn)產(chǎn)品））中包包含的的零件件（或或部件件）的的數(shù)量量（可可以稱稱為消消耗系系數(shù)）），例例如DB弧上的的數(shù)字字“9”表示組組裝1個部件件B需要用用到9個零件件D；BA弧上的的數(shù)字字“5”表示組組裝1件產(chǎn)品品A需要用用到5個部件件B；依此類類推。。瓶頸設(shè)備加工ABCDEFG579111315圖2產(chǎn)品構(gòu)構(gòu)成與與組裝裝過程程圖表1生產(chǎn)計計劃的的原始始數(shù)據(jù)據(jù)周次123456A的外部需求40010009010瓶頸能力 1000005000500010001000零部件編號ABCDEFG生產(chǎn)準備費用4005001000300200400100單件庫存費用120.61.00.040.030.040.04假設(shè)該該工廠廠每次次生產(chǎn)產(chǎn)計劃劃的計計劃期期為6周（即即每次次制定定未來來6周的生生產(chǎn)計計劃）），只只有最最終產(chǎn)產(chǎn)品A有外部部需求求，目目前收收到的的訂單單的需需求件件數(shù)按按周的的分布布如表表1第2行所示示。部部件B、C是在該該工廠廠最關(guān)關(guān)鍵的的設(shè)備備（可可以稱稱為瓶瓶頸設(shè)設(shè)備））上組組裝出出來的的，瓶瓶頸設(shè)設(shè)備的的生產(chǎn)產(chǎn)能力力非常常緊張張，具具體可可供能能力如如表1第3行所示示（第第2周設(shè)備備檢修修，不不能使使用））。B、C的能力力消耗耗系數(shù)數(shù)分別別為5和8，即生生產(chǎn)1件B需要占占用5個單位位的能能力，，即生生產(chǎn)1件C需要占占用8個單位位的能能力。。對于每每種零零部件件或產(chǎn)產(chǎn)品，，如果果工廠廠在某某一周周訂購購或者者生產(chǎn)產(chǎn)該零零部件件或產(chǎn)產(chǎn)品，，工廠廠需要要付出出一個個與訂訂購或或生產(chǎn)產(chǎn)數(shù)量量無關(guān)關(guān)的固固定成成本（（稱為為生產(chǎn)產(chǎn)準備備費用用）；；如果果某一一周結(jié)結(jié)束時時該零零部件件或產(chǎn)產(chǎn)品有有庫存存存在在，則則工廠廠必須須付出出一定定的庫庫存費費用（（與庫庫存數(shù)數(shù)量成成正比比）。。這些些數(shù)據(jù)據(jù)在表表1第5、6行給給出出。。按照照工工廠廠的的信信譽譽要要求求，，目目前前接接收收的的所所有有訂訂單單到到期期必必須須全全部部交交貨貨，，不不能能有有缺缺貨貨發(fā)發(fā)生生；；此此外外，，不不妨妨簡簡單單地地假假設(shè)設(shè)目目前前該該企企業(yè)業(yè)沒沒有有任任何何零零部部件件或或產(chǎn)產(chǎn)品品庫庫存存，，也也不不希希望望第第6周結(jié)結(jié)束束后后沒沒有有任任何何零零部部件件或或產(chǎn)產(chǎn)品品庫庫存存。。最最后后，，假假設(shè)設(shè)不不考考慮慮生生產(chǎn)產(chǎn)提提前前期期，，即即假假設(shè)設(shè)當當周周采采購購的的零零件件馬馬上上就就可可用用于于組組裝裝，，組組裝裝出出來來的的部部件件也也可可以以馬馬上上用用于于當當周周組組裝裝成成品品A。在上上述述假假設(shè)設(shè)和和所所給給數(shù)數(shù)據(jù)據(jù)下下，，如如何何制制定定未未來來6周的的生生產(chǎn)產(chǎn)計計劃劃？？§2.2建立立模模型型問題題分分析析這這個個例例子子考考慮慮的的是是在在有有限限的的計計劃劃期期內(nèi)內(nèi),給定定產(chǎn)產(chǎn)品品結(jié)結(jié)構(gòu)構(gòu)、、生生產(chǎn)產(chǎn)能能力力和和相相關(guān)關(guān)費費用用及及零零部部件件或或成成品品（（以以下下統(tǒng)統(tǒng)稱稱為為生生產(chǎn)產(chǎn)項項目目））在在離離散散的的時時間間段段上上（（這這里里是是周周，，也也可可以以是是天天、、月月等等））的的外外部部需需求求之之后后,確定定每每一一生生產(chǎn)產(chǎn)項項目目在在每每一一時時間間段段上上的的生生產(chǎn)產(chǎn)量量(即批批量量),使總總費費用用最最小小.由于于每每一一生生產(chǎn)產(chǎn)項項目目在在每每一一時時間間段段上上生生產(chǎn)產(chǎn)時時必必須須經(jīng)經(jīng)過過生生產(chǎn)產(chǎn)準準備備(Setup),所以以通通常常的的討討論論中中總總費費用用至至少少應(yīng)應(yīng)考考慮慮生生產(chǎn)產(chǎn)準準備備費費用用和和庫庫存存費費用用.其實實，，細細心心的的學學生生一一定定會會問問：：是是否否需需要要考考慮慮生生產(chǎn)產(chǎn)的的直直接接成成本本（（如如原原材材料料成成本本、、人人力力成成本本、、電電力力成成本本等等））？？符號號說說明明為了了建建立立這這類類問問題題的的一一般般模模型型，，我我們們定定義義如如下下數(shù)數(shù)學學符符號號：：N--------生產(chǎn)產(chǎn)項項目目總總數(shù)數(shù)（（本本例例中中N=7）;T--------計劃劃期期長長度度（（本本例例中中T=6）;K--------瓶頸頸資資源源種種類類數(shù)數(shù)（（本本例例中中K=1）;M--------一個個充充分分大大的的正正數(shù)數(shù)，，在在模模型型中中起起到到使使模模型型線線性性化化的的作作用用;-----項目目i在t時段段的的外外部部需需求求（本本例例中中只只有有產(chǎn)產(chǎn)品品A有外外部部需需求求））;-----項目目i在t時段段的的生生產(chǎn)產(chǎn)批批量量;-----項目目i在t時段段的的庫庫存存量量;-----項目目i在t時段段是是否否生生產(chǎn)產(chǎn)的的標標志志(0：不不生生產(chǎn)產(chǎn),1：生生產(chǎn)產(chǎn));-----產(chǎn)品品結(jié)結(jié)構(gòu)構(gòu)中中項項目目j對項項目目i的消消耗耗系系數(shù)數(shù);S(i)-----產(chǎn)品品結(jié)結(jié)構(gòu)構(gòu)中中項項目目i的直直接接后后繼繼項項目目集集合合;-----項目目i在t時段段生生產(chǎn)產(chǎn)時時的的生生產(chǎn)產(chǎn)準準備備費費用用;-----項目目i在t時段段的的單單件件庫庫存存費費用用;-----資源源k在t時段段的的能能力力上上限限;---項目目i在t時段段生生產(chǎn)產(chǎn)時時,生產(chǎn)產(chǎn)單單個個產(chǎn)產(chǎn)品品占占用用資資源源k的能能力力;δ(x)----這個個函函數(shù)數(shù)當當且且僅僅當當x>0時取取值值1,否則則取取值值0.在上述數(shù)學符號中，只有為決策變量;其余余均均為為已已知知的的計計劃劃參參數(shù)數(shù)。。目標標函函數(shù)數(shù)這個個問問題題的的目目標標是是使使生生產(chǎn)產(chǎn)準準備備費費用用和和庫庫存存費費用用的的總總和和最最小小。。因因此此，，目目標標函函數(shù)數(shù)應(yīng)應(yīng)該該是是每每個個項項目目在在每每個個時時段段上上的的生生產(chǎn)產(chǎn)準準備備費費用用和和庫庫存存費費用用的的總總和和，，即即(28)約束束條條件件這個個問問題題中中的的約約束束有有這這么么幾幾類類：：每每個個項項目目的的物物流流應(yīng)應(yīng)該該守守恒恒、、資資源源能能力力限限制制應(yīng)應(yīng)該該滿滿足足、、每每時時段段生生產(chǎn)產(chǎn)某某項項目目前前必必須須經(jīng)經(jīng)過過生生產(chǎn)產(chǎn)準準備備和和非非負負約約束束（（對對Yi,j是0-1約束束））。。(29)資源源能能力力限限制制比比較較容容易易理理解解，，即即(30)所謂謂物物流流守守恒恒（（假假設(shè)設(shè)Ii,0=0）(31)每時時段段生生產(chǎn)產(chǎn)某某項項目目前前必必須須經(jīng)經(jīng)過過生生產(chǎn)產(chǎn)準準備備，，也也就就是是說說當當Xit=0時Yit=0；Xit>0時Yit=1。這這本本來來是是一一個個非非線線性性約約束束，，但但是是通通過過引引入入?yún)?shù)數(shù)M（很很大大的的正正數(shù)數(shù)，，表表示示每每個個項項目目每每個個時時段段的的最最大大產(chǎn)產(chǎn)量量））可可以以化化成成線線性性約約束束，，即即：：總結(jié)結(jié):這個個問問題題的的優(yōu)優(yōu)化化模模型型就就是是在在約約束束（（29）（（30）（（31）下下使使目目標標函函數(shù)數(shù)（（28）達達到到最最小小。?！?.3求解解模模型型本例例生生產(chǎn)產(chǎn)項項目目總總數(shù)數(shù)N=7(A、B、C、D、E、F、G)，計計劃劃期期長長度度T=6（周周）），，瓶瓶頸頸資資源源種種類類數(shù)數(shù)K=1。只只有有A有外外部部需需求求，，所所以以di,t中只只有有d1,t可以以取取非非零零需需求求，，即即表表5-1中的的第第2行的的數(shù)數(shù)據(jù)據(jù)，，其其他他全全部部為為零零。。參參數(shù)數(shù)si,t、hi,t只與與項項目目i有關(guān)關(guān)，，而而不不隨隨時時段段t變化化，，所所以以可可以以略略去去下下標標t，其其數(shù)數(shù)值值就就是是表表1中的的最最后后兩兩行行數(shù)數(shù)據(jù)據(jù)。。由于于只只有有一一種種資資源源，，參參數(shù)數(shù)Ck,t可以以略略去去下下標標k，其其數(shù)數(shù)值值就就是是表表1中的的第第3行的的數(shù)數(shù)據(jù)據(jù)；；而而ak,I,t只與與項項目目i有關(guān)關(guān)，，而而不不隨隨時時段段t變化化，，所所以以可可以以同同時時略略去去下下標標k和t，即a2=5，a3=8（其他ai為0）。從圖圖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)準備備費;400500 1000300 200400100~!庫存費;120.61.0 0.040.030.04 0.04~!對能力的的消耗系系數(shù)；0 580 000~!項目間的的消耗系系數(shù):req(i,j)表示j用到多少少i;0000000500000070000000900000011000000013000000150000!數(shù)據(jù)結(jié)束束;對本例，，A的外部總總需求為為240，所以任任何項目目的產(chǎn)量量不會超超過240××7×15<25000（從圖2可以知道道，這里里7×15已經(jīng)是每每件產(chǎn)品品A對任意一一個項目目的最大大的消耗耗系數(shù)了了），所所以取M=25000就已經(jīng)足足夠了。。本例中的的具體模模型可以以如下輸輸入LINGO軟件：MODEL:TITLE瓶頸設(shè)備備的多級級生產(chǎn)計計劃;!從文本文文件exam0502.LDT中讀取數(shù)數(shù)據(jù);SETS:!PART=項目集合合,Setup=生產(chǎn)準備備費，Hold=單件庫存存成本，，A=對瓶頸資資源的消消耗系數(shù)數(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ù);USES(PART,PART):Req;!PXT=項目與時時間的派派生集合合，Demand=外部需求求,X=產(chǎn)量（批批量）,Y=0/1變量，INV=庫存;PXT(PART,TIME):Demand,X,Y,Inv;ENDSETS!目標函數(shù)數(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)目標函函數(shù)值為為9245,結(jié)果如下下：§5.3下料問題題§5.3下料問題題生產(chǎn)中常常會遇到到通過切切割、剪剪裁、沖沖壓等手手段，將將原材料料加工成成所需大大小這種種工藝過過程，稱稱為原料料下料（（cuttingstock）問題。。按照進進一步的的工藝要要求，確確定下料料方案，，使用料料最省，，或利潤潤最大，，是典型型的優(yōu)化化問題。。本節(jié)通通過兩個個實例討討論用數(shù)數(shù)學規(guī)劃劃模型解解決這類類問題的的方法。。鋼管下料料問題例5.3某鋼管零零售商從從鋼管廠廠進貨，，將鋼管管按照顧顧客的要要求切割割后售出出。從鋼鋼管廠進進貨時得得到的原原料鋼管管都是19米長。1)現(xiàn)有一客客戶需要要50根4米長、20根6米長和15根8米長的鋼鋼管。應(yīng)應(yīng)如何下下料最節(jié)節(jié)省？2)零售商如如果采用用的不同同切割模模式太多多，將會會導致生生產(chǎn)過程程的復雜雜化，從從而增加加生產(chǎn)和和管理成成本，所所以該零零售商規(guī)規(guī)定采用用的不同同切割模模式不能能超過3種。此外外，該客客戶除需需要1）中的三三種鋼管管外，還還需要10根5米長的鋼鋼管。應(yīng)應(yīng)如何下下料最節(jié)節(jié)??？問題1）的求解解問題分析析首先，應(yīng)應(yīng)當確定定哪些切切割模式式是可行行的。所所謂一個個切割模模式，是是指按照照客戶需需要在原原料鋼管管上安排排切割的的一種組組合。例例如，我我們可以以將19米長的鋼鋼管切割割成3根4米長的鋼鋼管，余余料為7米。。。。顯然，，可行的的切割模模式是很很多的。。其次，應(yīng)應(yīng)當確定定哪些切切割模式式是合理理的。通通常假設(shè)設(shè)一個合合理的切切割模式式的余料料不應(yīng)該該大于或或等于客客戶需要要的鋼管管的最小小尺寸。。在這種種合理性性假設(shè)下下，切割割模式一一共有7種，如表表5-3所示。表5-3鋼管下料料的合理理切割模模式4米鋼管根數(shù)6米鋼管根數(shù)8米鋼管根數(shù)余料（米）模式14003模式23101模式32013模式41203模式51111模式60301模式70023問題化為為在滿足足客戶需需要的條條件下，，按照哪哪些種合合理的模模式，切切割多少少根原料料鋼管，，最為節(jié)節(jié)省。而而所謂節(jié)節(jié)省，可可以有兩兩種標準準，一是是切割后后剩余的的總余料料量最小小，二是是切割原原料鋼管管的總根根數(shù)最少少。下面面將對這這兩個目目標分別別討論。。模型建建立決策變變量用xi表示按按照第第i種模式式（i=1,2,……,7）切割割的原原料鋼鋼管的的根數(shù)數(shù)，顯顯然它它們應(yīng)應(yīng)當是是非負負整數(shù)數(shù)。決策目目標以切割割后剩剩余的的總余余料量量最小小為目目標，，則由由表1可得(32)以切割割原料料鋼管管的總總根數(shù)數(shù)最少少為目目標，，則有有(33)下面分分別在在這兩兩種目目標下下求解解。約束條條件為滿足足客戶戶的需需求，，按照照表1應(yīng)有模型求求解1.將（32），（（34）~（36）構(gòu)成成的整整數(shù)線線性規(guī)規(guī)劃模模型（（加上上整數(shù)數(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.00000VARIABLEVALUEREDUCEDCOST即按照照模式式2切割12根原料料鋼管管，按按照模模式5切割15根原料料鋼管管，共共27根，總總余料料量為為27米。顯顯然，，在總總余料料量最最小的的目標標下，，最優(yōu)優(yōu)解將將是使使用余余料盡盡可能能小的的切割割模式式（模模式2和5的余料料為1米），，這會會導致致切割割原料料鋼管管的總總根數(shù)數(shù)較多多。2.將（33）~（36）構(gòu)成成的整整數(shù)線線性規(guī)規(guī)劃模模型（（加上上整數(shù)數(shù)約束束）輸輸入LINDO：Title鋼管下下料-最小化化鋼管管根數(shù)數(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.00000VARIABLEVALUEREDUCEDCOST即按照照模式式2切割15根原料料鋼管管，按按模式式5切割5根，按按模式式7切割5根，共共27根，可可算出出總余余料量量為35米。與與上面面得到到的結(jié)結(jié)果相相比，，總余余料量量增加加了8米，但但是所所用的的原料料鋼管管的總總根數(shù)數(shù)減少少了2根。在在余料料沒有有什么么用途途的情情況下下，通通常選選擇總總根數(shù)數(shù)最少少為目目標。。問題2）的求求解問題分分析按按照解解問題題1）的思思路，，可以以通過過枚舉舉法首首先確確定哪哪些切切割模模式是是可行行的。。但由由于需需求的的鋼管管規(guī)格格增加加到4種，所所以枚枚舉法法的工工作量量較大大。下下面介介紹的的整數(shù)數(shù)非線線性規(guī)規(guī)劃模模型，，可以以同時時確定定切割割模式式和切切割計計劃，，是帶帶有普普遍性性的方方法。。同1）類似似，一一個合合理的的切割割模式式的余余料不不應(yīng)該該大于于或等等于客客戶需需要的的鋼管管的最最小尺尺寸（（本題題中為為4米），，切割割計劃劃中只只使用用合理理的切切割模模式，，而由由于本本題中中參數(shù)數(shù)都是是整數(shù)數(shù)，所所以合合理的的切割割模式式的余余量不不能大大于3米。此此外，，這里里我們們僅選選擇總總根數(shù)數(shù)最少少為目目標進進行求求解。。模型建建立決策變變量由由于不不同切切割模模式不不能超超過3種，可可以用用xi表示按按照第第i種模式式（i=1,2,3）切割割的原原料鋼鋼管的的根數(shù)數(shù)，顯顯然它它們應(yīng)應(yīng)當是是非負負整數(shù)數(shù)。設(shè)所使用用的第第i種切割割模式式下每每根原原料鋼鋼管生生產(chǎn)4米長、、5米長、、6米長和和8米長的的鋼管管數(shù)量量分別別為r1i,r2i,r3i,r4i（非負整整數(shù)）。決策目目標以以切割割原料料鋼管管的總總根數(shù)數(shù)最少少為目目標，，即目目標為為（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ā)發(fā)現(xiàn)在在較低低版本本的LINGO軟件中中需要要運行行很長長時間間也難難以得得到最最優(yōu)解解。為為了減減少運運行時時間，，可以以增加加一些些顯然然的約約束條條件，，從而而縮小小可行行解的的搜索索范圍圍。例如，，由于于3種切割割模式式的排排列順順序是是無關(guān)關(guān)緊要要的，，所以以不妨妨增加加以下下約束束：（45）又例如如，我我們注注意到到所需需原料料鋼管管的總總根數(shù)數(shù)有著著明顯顯的上上界和和下界界。首首先，，無論論如何何，原原料鋼鋼管的的總根根數(shù)不不可能能少于于（根））其次，，考慮慮一種種非常常特殊殊的生生產(chǎn)計計劃：：第一一種切切割模模式下下只生生產(chǎn)4米鋼管管，一一根原原料鋼鋼管切切割成成4根4米鋼管管，為為滿足足50根4米鋼管管的需需求，，需要要13根原料料鋼管管；第第二種種切割割模式式下只只生產(chǎn)產(chǎn)5米、6米鋼管管，一一根原原料鋼鋼管切切割成成1根5米鋼管管和2根6米鋼管管，為為滿足足10根5米和20根6米鋼管管的需需求，，需要要10根原料料鋼管管；第三種種切割割模式式下只只生產(chǎn)產(chǎn)8米鋼管管，一一根原原料鋼鋼管切切割成成2根8米鋼管管，為為滿足足15根8米鋼管管的需需求，，需要要8根原料料鋼管管。于于是滿滿足要要求的的這種種生產(chǎn)產(chǎn)計劃劃共需需13+10+8=31根原料料鋼管管，這這就得得到了了最優(yōu)優(yōu)解的的一個個上界界。所所以可可增加加以下下約束束：(46)將（37）~（46）構(gòu)成成的模模型輸輸入LINGO如下：：將（37）~（46）構(gòu)成成的模模型輸輸入LINGO如下：：model:Title鋼管下下料-最小化化鋼管管根數(shù)數(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模型VariableValueReducedCost即按照照模式式1、2、3分別切切割10、10、8根原料料鋼管管，使使用原原料鋼鋼管總總根數(shù)數(shù)為28根。第第一種種切割割模式式下一一根原原料鋼鋼管切切割成成3根4米鋼管管和1根6米鋼管管；第第二種種切割割模式式下一一根原原料鋼鋼管切切割成成2根4米鋼管管、1根5米鋼管管和1根6米鋼管管；第第三種種切割割模式式下一一根原原料鋼鋼管切切割成成2根8米鋼管管。如果充充分利利用LINGO建模語語言的的能力力，使使用集集合和和屬性性的概概念，，可以以編寫寫以下下LINGO程序，，這種種方法法更具具有一一般的的通用用性，，并有有利于于輸入入更大大規(guī)模模的下下料問問題的的優(yōu)化化模型型：model:Title鋼管下下料-最小化化鋼管管根數(shù)數(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));!目標函函數(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é)結(jié)果完完全相相同。。易拉罐罐下料料問題題例5.4某公司司采用用一套套沖壓壓設(shè)備備生產(chǎn)產(chǎn)一種種罐裝裝飲料料的易易拉罐罐，這這種易易拉罐罐是用用鍍錫錫板沖沖壓制制成的的（參參見圖圖5-3）。易易拉罐罐為圓圓柱形形，包包括罐罐身、、上蓋蓋和下下底，，罐身身高10厘米，，上蓋蓋和下下底的的直徑徑均為為5厘米。。該公公司使使用兩兩種不不同規(guī)規(guī)格的的鍍錫錫板原原料，，規(guī)格格1的鍍錫錫板為為正方方形，，邊長長24厘米；；規(guī)格格2的鍍錫錫板為為長方方形，，長、、寬分分別為為32和28厘米。。由于于生產(chǎn)產(chǎn)設(shè)備備和生生產(chǎn)工工藝的的限制制，對對于規(guī)規(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ī)規(guī)格1、2的鍍錫錫板原原料分分別為為5萬張和和2萬張。。目前前每只只易拉拉罐的的利潤潤為0.10元，原原料余余料損損失為為0.001元/厘米2（如果果周末末有罐罐身、、上蓋蓋或下下底不不能配配套組組裝成成易拉拉罐出出售，，也看看作是是原料料余料料損失失）。。工廠廠應(yīng)如如何安安排每每周的的生產(chǎn)產(chǎn)？已知上上蓋和和下底底的直直徑d=5厘米，，可得得其面面積為為19.6厘米2表5-44種沖壓壓模式式的特特征罐身個數(shù)底、蓋個數(shù)余料損失（厘米2）沖壓時間（秒）模式1110222.61.5模式224183.32模式3016261.81模式445169.53問題的的目標標顯然然應(yīng)是是易拉拉罐的的利潤潤扣除除原料料余料料損失失后的的凈利利潤最最大，，約束束條件件除每每周工工作時時間和和原料料數(shù)量量外，，還要要考慮慮罐身身和底底、蓋蓋的配配套組組裝。。模型建建立決策變變量用用xi表示按按照第第i種模式式的沖沖壓次次數(shù)（（i=1,2,3,4），y1表示一一周生生產(chǎn)的的易拉拉罐個個數(shù)。。為計計算不不能配配套組組裝的的罐身身和底底、蓋蓋造成成的原原料損損失，，用y2表示不不配套套的罐罐身個個數(shù)，，y3表示不不配套套的底底、蓋蓋個數(shù)數(shù)。雖雖然實實際上上xi和y1，y2，y3應(yīng)該是整整數(shù)。但但是由于于生產(chǎn)量量相當大大，可以以把它們們看成是是實數(shù)，，從而用用線性規(guī)規(guī)劃模型型處理。。決策目標標假假設(shè)每周周生產(chǎn)的的易拉罐罐能夠全全部售出出，公司司每周的的銷售利利潤是0.1y1。原料余余料損失失包括兩兩部分：：4種沖壓模模式下的的余料損損失，和和不配套套的罐身身和底、、蓋造成成的原料料損失。。按照前前面的計計算及表表2的結(jié)果，，總損失失為0.001(222.6x1+183.3x2+261.8x3+169.5x4+157.1y2+19.6y3)。于是，決決策目標標為(47)約束條件件時間約束束：每周周工作時時間不超超過40小時=144000（秒），，由表2最后一列列得(48)原料約束束：每周可供供使用的的規(guī)格1、2的鍍錫板板原料分分別為50000張和20000張，即(49)(50)配套約束束：由由表2一周生產(chǎn)產(chǎn)的罐身身個數(shù)為為x1+2x2+4x4,一周生產(chǎn)產(chǎn)的底、、蓋個數(shù)數(shù)為10x1+4x2+16x3+5x4，因為應(yīng)應(yīng)盡可能能將它們們配套組組裝成易易拉罐銷銷售。所所以y1滿足(51)這時不配配套的罐罐身個數(shù)數(shù)y2，和不配配套的底底、蓋個個數(shù)y3應(yīng)為為(52)(53)（47）~（53）就就是是我我們們得得到到的的模模型型，，其其中中（（51）是是一一個個非非線線性性關(guān)關(guān)系系，，不不易易直直接接處處理理，，但是是它它可可以以等等價價為為以以下下兩兩個個線線性性不不等等式式：：(54)(55)模型型求求解解將模模型型（（47）~（50）和和（（52）~（55）直直接接輸輸入入LINDO（輸輸入入LINGO也可可以以）），，求求解解時時LINDO發(fā)出出警警告告信信息息（（程程序序和和警警告告信信息息參參見見圖圖5-4）。。圖圖中中錯錯誤誤編編號號““66””的含含義義（（參參見見第第4章的的錯錯誤誤代代碼碼表表））是是：：模模型型中中數(shù)數(shù)據(jù)據(jù)不不平平衡衡，，所所以以發(fā)發(fā)出出警警告告信信息息（（注注意意，，只只是是警警告告信信息息，，所所以以仍仍然然可可以以繼繼續(xù)續(xù)求求解解））。。求求解解結(jié)結(jié)果果是是：：OBJECTIVEFUNCTIONVALUE1)4298.337VARIABLEVALUEREDUCEDCOST圖5-4模型型中中數(shù)數(shù)據(jù)據(jù)不不平平衡衡的的警警告告信信息息這個個結(jié)結(jié)果果可可靠靠嗎嗎？？由由于于LINDO警告告模模型型中中數(shù)數(shù)據(jù)據(jù)之之間間的的數(shù)數(shù)量量級級差差別別太太大大，，所所以以我我們們可可以以進進行行預預處處理理，，縮縮小小數(shù)數(shù)據(jù)據(jù)之之間間的的差差別別。。實實際際上上，，約約束束（（48）~（50）中中右右端端項項的的數(shù)數(shù)值值過過大大（（與與左左端端的的系系數(shù)數(shù)相相比比較較）），，LINDO在計計算算中中容容易易產(chǎn)產(chǎn)生生比比較較大大的的誤誤差差，，所所以以出出現(xiàn)現(xiàn)此此警警告告信信息息。。為了了解解決決這這一一問問題題，，可可以以將將所所有有決決策策變變量量擴擴大大10000倍（（相相當當于于xi以萬萬次次為為單單位位，，yi以萬萬件件為為單單位位））。。此此時時，，目目標標（（47）可可以以保保持持不不變變（（記記住住得得到到的的結(jié)結(jié)果果單單位位為為萬萬元元就就可可以以了了）），，而而約約束束（（48）~（50）改改為為(56)(57)(58)將模模型型（（47）和和（（52）~（58）輸輸入入LINDO:!易拉拉罐罐下下料料：：均均衡衡數(shù)數(shù)據(jù)據(jù)s.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.4298337VARIABLEVALUEREDUCEDCOST即模模式式1不使使用用，，模模式式2使用用40125次，，模模式式3使用用3750次，，模模式式4使用用20000次，，可可生生產(chǎn)產(chǎn)易易拉拉罐罐160250個，，罐罐身身和和底底、、蓋蓋均均無無剩剩余余，，凈凈利利潤潤為為4298元。。5.4面試試順順序序與與消消防防車車調(diào)調(diào)度度問問題題面試試順順序序問問題題例5.5有4名同同學學到到一一家家公公司司參參加加三三個個階階段段的的面面試試：：公公司司要要求求每每個個同同學學都都必必須須首首先先找找公公司司秘秘書書初初試試，，然然后后到到部部門門主主管管處處復復試試，，最最后后到到經(jīng)經(jīng)理理處處參參加加面面試試，，并并且且不不允允許許插插隊隊（（即即在在任任何何一一個個階階段段4名同學的順序序是一樣的））。由于4名同學的專業(yè)業(yè)背景不同，，所以每人在在三個階段的的面試時間也也不同，如表表5-5所示（單位：：分鐘）。這這4名同學約定他他們?nèi)棵嬖囋囃暌院笠黄鹌痣x開公司。。假定現(xiàn)在時時間是早晨8：00，請問他們最最早何時能離離開公司？表5-5面試時間要求求秘書初試主管復試經(jīng)理面試同學甲131520同學乙102018同學丙201010同學丁81015建立模型實際上，這個個問題就是要要安排4名同學的面試試順序，使完完成全部面試試所花費的時時間最少。記tij為第i名同學參加第第j階段面試需要要的時間(已知)，令xij表示第i名同學參加第第j階段面試的開開始時刻(不妨記早上8：00面試開始為0時刻)(i=1,2,3,4；j=1,2,3)，T為完成全部面面試所花費的的最少時間。。優(yōu)化目標為a.時間先后次序序約束(每人只有參加加完前一個階階段的面試后后才能進入下下一個階段)：xij+tijxi，j+1(i=1,2,3,4；j=1,2)b.每個階段j同一時間只能