Lingo生產(chǎn)與服務(wù)運作管理中的優(yōu)化問題.ppt

生產(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)如何安排原油的采購和加工。,5.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 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”，運行該程序得到：,Local optimal solution found. Objective value: 4800.000 Total solver iterations: 26,Variable Value Reduced Cost X11 500.0000 0.000000 X21 500.0000 0.000000 X12 0.000000 0.000000 X22 0.000000 0.000000 X1 0.000000 0.000000 X2 0.000000 0.000000 X3 0.000000 0.000000 X 0.000000 0.000000,最優(yōu)解: 用庫存的500噸原油A、500噸原油B生產(chǎn)1000噸汽油甲，不購買新的原油A，利潤為4800（千元）,但是此時LINGO得到的結(jié)果只是一個局部最優(yōu)解,可以用菜單命令“LINGO|Options”在“Global Solver”選項卡上啟動全局優(yōu)化（Use Global Solver）選項，然后重新執(zhí)行菜單命令“LINGO|Solve” , 得到：,Global optimal solution found. Objective value: 5000.002 Extended solver steps: 3 Total solver iterations: 187,Variable Value Reduced Cost X11 0.000000 0.000000 X21 0.000000 0.000000 X12 1500.000 0.000000 X22 1000.000 0.000000 X1 500.0000 0.000000 X2 499.9990 0.000000 X3 0.9536707E-03 0.000000 X 1000.000 0.000000,此時LINGO得到的結(jié)果是一個全局最優(yōu)解（Global optimal solution）：購買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軟件：,Max 4.8x11+4.8x21+5.6x12+5.6x22-10x1-8x2-6x3 st x-x1-x2-x3=0 x11+x12-x0 0.4x12-0.6x220 x1-500y10 x2-500y30 end int y1 int y2 int y3,運行該程序得到： OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 1000.000000 0.000000,這個結(jié)果與前面非線性規(guī)劃模型用全局優(yōu)化得到的結(jié)果相同。,第3種解法 直接處理分段線性函數(shù)c(x)。 （1）式表示的函數(shù)c(x)如圖5-1。,記x軸上的分點為b1=0, b2=500, b3=1000, b4=1500。當(dāng)x在第1個小區(qū)間 b1, b2時，記x= z1b1+z2b2，z1+z2=1，z1, z20, 因為c(x)在b1, b2是線性的，所以c(x)= z1c(b1)+z2c(b2)。同樣，當(dāng)x在第2個小區(qū)間 b2, b3時，x= z2b2+z3b3，z2+z3=1，z2, z30, c(x)= z2c(b2)+z3c(b3)。當(dāng)x在第3個小區(qū)間 b3, b4時，x= z3b3+z4b4，z3+z4=1，z3, z40, c(x)= z3c(b3)+z4c(b4)。為了表示x在哪個小區(qū)間，引入0-1變量yk(k=1,2,3)，當(dāng)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ī)劃模型，可以用LINDO求解。不過，我們還是將它輸入LINGO軟件，因為其擴展性更好（即當(dāng)分段函數(shù)的分段數(shù)更多時，只需要對下面程序作很小的改動）。輸入的LINGO模型如下：,(22),輸入的LINGO模型如下：,Model: SETS: Points/14/: b, c, y, z; ! 端點數(shù)為4，即分段數(shù)為3; ENDSETS DATA: b=0 500 1000 1500; c=0 5000 9000 12000; y=,0; ! 增加的虛擬變量y(4)=0; ENDDATA,Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - sum(Points: c*z); x11+x12 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é)果）： Global optimal solution found. Objective value: 5000.000 Extended solver steps: 0 Total solver iterations: 28,Variable Value Reduced Cost X11 0.000000 0.000000 X21 0.000000 1.600000 X12 1500.000 0.000000 X22 1000.000 0.000000 X 1000.000 0.000000 Y( 1) 0.000000 -4600.000 Y( 2) 0.000000 -1200.000 Y( 3) 1.000000 0.000000 Y( 4) 0.000000 0.000000 Z( 1) 0.000000 0.000000 Z( 2) 0.000000 0.000000 Z( 3) 1.000000 0.000000 Z( 4) 0.000000 200.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)周期的最優(yōu)生產(chǎn)計劃，這種問題在文獻上一般稱為批量問題（Lotsizing Problems）。 我們通過下面的具體例子來說明這種多級生產(chǎn)計劃問題的優(yōu)化模型。這里“多級”的意思是需要考慮產(chǎn)品是通過多個生產(chǎn)階段（工藝過程）生產(chǎn)出來的。,例5.2 某工廠的主要任務(wù)是通過組裝生產(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ù)字表示的是組裝時部件（或產(chǎn)品）中包含的零件（或部件）的數(shù)量（可以稱為消耗系數(shù)），例如DB弧上的數(shù)字“9”表示組裝1個部件B需要用到9個零件D；BA弧上的數(shù)字“5”表示組裝1件產(chǎn)品A需要用到5個部件B；,依此類推。,圖5-2 產(chǎn)品構(gòu)成與組裝過程圖,表5-1 生產(chǎn)計劃的原始數(shù)據(jù),假設(shè)該工廠每次生產(chǎn)計劃的計劃期為6周（即每次制定未來6周的生產(chǎn)計劃），只有最終產(chǎn)品A有外部需求，目前收到的訂單的需求件數(shù)按周的分布如表5-1第2行所示。部件B、C是在該工廠最關(guān)鍵的設(shè)備（可以稱為瓶頸設(shè)備）上組裝出來的，瓶頸設(shè)備的生產(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)數(shù)量無關(guān)的固定成本（稱為生產(chǎn)準備費用）；如果某一周結(jié)束時該零部件或產(chǎn)品有庫存存在，則工廠必須付出一定的庫存費用（與庫存數(shù)量成正比）。這些數(shù)據(jù)在表5-1第5、6行給出。,按照工廠的信譽要求，目前接收的所有訂單到期必須全部交貨，不能有缺貨發(fā)生；此外，不妨簡單地假設(shè)目前該企業(yè)沒有任何零部件或產(chǎn)品庫存，也不希望第6周結(jié)束后留下沒有任何零部件或產(chǎn)品庫存。最后，假設(shè)不考慮生產(chǎn)提前期，即假設(shè)當(dāng)周采購的零件馬上就可用于組裝，組裝出來的部件也可以馬上用于當(dāng)周組裝成品A。 在上述假設(shè)和所給數(shù)據(jù)下，如何制定未來6周的生產(chǎn)計劃？,5.2.2 建立模型 問題分析 這個例子考慮的是在有限的計劃期內(nèi), 給定產(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)的直接成本（如原材料成本、人力成本、電力成本等）？,符號說明 為了建立這類問題的一般模型，我們定義如下數(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)的標(biāo)志 (0：不生產(chǎn), 1：生產(chǎn));,- 產(chǎn)品結(jié)構(gòu)中項目j對項目i的消耗系數(shù);,S(i) - 產(chǎn)品結(jié)構(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)x0時取值1, 否則取值0.,其余均為已知的計劃參數(shù)。,目標(biāo)函數(shù),這個問題的目標(biāo)是使生產(chǎn)準備費用和庫存費用的總和最小。因此，目標(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；Xit0時Yit=1。這本來是一個非線性約束，但是通過引入?yún)?shù)M（很大的正數(shù)，表示每個項目每個時段的最大產(chǎn)量）可以化成線性約束，即：,總結(jié): 這個問題的優(yōu)化模型就是在約束（29）（30）（31）下使目標(biāo)函數(shù)（28）達到最小。,5.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)k和t，即a2=5，a3=8（其他ai為0）。從圖6-2中容易得到項目i的直接后繼項目集合S(i)和消耗系數(shù)。,準備以下的數(shù)據(jù)文件（文本文件exam0502.LDT，可以看到其中也可以含有注釋語句）：,! 項目集合; A B C D E F G ! 計劃期集合; 1 2 3 4 5 6 ! 需求; 40 0 100 0 90 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,! 能力; 10000 0 5000 5000 1000 1000 ! 生產(chǎn)準備費; 400 500 1000 300 200 400 100 ! 庫存費; 12 0.6 1.0 0.04 0.03 0.04 0.04 ! 對能力的消耗系數(shù)； 0 5 8 0 0 0 0,! 項目間的消耗系數(shù): req(i,j)表示j用到多少i; 0 0 0 0 0 0 0 5 0 0 0 0 0 0 7 0 0 0 0 0 0 0 9 0 0 0 0 0 0 11 0 0 0 0 0 0 0 13 0 0 0 0 0 0 15 0 0 0 0 ! 數(shù)據(jù)結(jié)束;,對本例，A的外部總需求為240，所以任何項目的產(chǎn)量不會超過24071525000（從圖6-2可以知道，這里715已經(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)準備費，Hold = 單件庫存成本， A = 對瓶頸資源的消耗系數(shù); PART/ FILE( exam0502.LDT)/ : Setup, Hold, A; ! TIME = 計劃期集合，Capacity = 瓶頸設(shè)備的能力; TIME / FILE( exam0502.LDT)/ : Capacity; ! USES = 項目結(jié)構(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,! 目標(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); ENDDATA END,注意：由于本例有42個0-1變量，LINGO演示版是無法求解的,表5-2 生產(chǎn)計劃的最后結(jié)果,LINDO求解: 得到最優(yōu)目標(biāo)函數(shù)值為9245, 結(jié)果如下：,5.3 下料問題,5.3 下料問題,生產(chǎn)中常會遇到通過切割、剪裁、沖壓等手段，將原材料加工成所需大小這種工藝過程，稱為原料下料（cutting stock）問題。按照進一步的工藝要求，確定下料方案，使用料最省，或利潤最大，是典型的優(yōu)化問題。本節(jié)通過兩個實例討論用數(shù)學(xué)規(guī)劃模型解決這類問題的方法。,5.3.1鋼管下料問題,例5.3 某鋼管零售商從鋼管廠進貨，將鋼管按照顧客的要求切割后售出。從鋼管廠進貨時得到的原料鋼管都是19米長。 1) 現(xiàn)有一客戶需要50根4米長、20根6米長和15根8米長的鋼管。應(yīng)如何下料最節(jié)省？ 2) 零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要1）中的三種鋼管外，還需要10根5米長的鋼管。應(yīng)如何下料最節(jié)?。?問題1）的求解,問題分析 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如，我們可以將19米長的鋼管切割成3根4米長的鋼管，余料為7米顯然，可行的切割模式是很多的。,其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。在這種合理性假設(shè)下，切割模式一共有7種，如表5-3所示。,表5-3 鋼管下料的合理切割模式,問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對這兩個目標(biāo)分別討論。,模型建立 決策變量 用xi 表示按照第i種模式（i=1, 2, , 7）切割的原料鋼管的根數(shù)，顯然它們應(yī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 鋼管下料 - 最小化余量,Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7,求解可以得到最優(yōu)解如下：,OBJECTIVE FUNCTION VALUE 1) 27.00000 VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000,即按照模式2切割12根原料鋼管，按照模式5切割15根原料鋼管，共27根，總余料量為27米。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和5的余料為1米），這會導(dǎo)致切割原料鋼管的總根數(shù)較多。,2. 將（33）（36）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO：,Title 鋼管下料 - 最小化鋼管根數(shù) Min x1 + x2 + x3 + x4 + x5 + x6 + x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7,求解，可以得到最優(yōu)解如下：,OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000,即按照模式2切割15根原料鋼管，按模式5切割5根，按模式7切割5根，共27根，可算出總余料量為35米。與上面得到的結(jié)果相比，總余料量增加了8米，但是所用的原料鋼管的總根數(shù)減少了2根。在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標(biāo)。,問題2）的求解,問題分析 按照解問題1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。下面介紹的整數(shù)非線性規(guī)劃模型，可以同時確定切割模式和切割計劃，是帶有普遍性的方法。,同1）類似，一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4米），切割計劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3米。此外，這里我們僅選擇總根數(shù)最少為目標(biāo)進行求解。,模型建立,決策變量 由于不同切割模式不能超過3種，可以用xi 表示按照第i種模式（i=1, 2, 3）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負整數(shù)。設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4米長、5米長、6米長和8米長的鋼管數(shù)量分別為r1i, r2i, r3i, r4i（非負整數(shù)）。,決策目標(biāo) 以切割原料鋼管的總根數(shù)最少為目標(biāo)，即目標(biāo)為,（37）,約束條件 為滿足客戶的需求，應(yīng)有,(38),(39),(40),(41),每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19米，也不能少于16米（余量不能大于3米），于是,(42),(43),(44),模型求解,（37）（44）構(gòu)成這個問題的優(yōu)化模型。由于在（38）（41）式中出現(xiàn)了決策變量的乘積，所以這是一個整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)在較低版本的LINGO軟件中需要運行很長時間也難以得到最優(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)解的一個上界。所以可增加以下約束：,(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 =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 =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求解，得到輸出如下： Local optimal solution found. Objective value: 28.00000 Extended solver steps: 72 Total solver iterations: 3404 Model Title: 鋼管下料-最小化鋼管根數(shù)的LINGO模型,Variable Value Reduced Cost X1 10.00000 1.000000 X2 10.00000 1.000000 X3 8.000000 1.000000 R11 2.000000 0.000000 R12 3.000000 0.000000 R13 0.000000 0.000000 R21 1.000000 0.000000 R22 0.000000 0.000000 R23 0.000000 0.000000 R31 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.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/14/:LENGTH,NUM; ! 定義基本集合NEEDS及其屬性LENGTH,NUM; CUTS/13/:X; ! 定義基本集合CUTS及其屬性X; PATTERNS(NEEDS,CUTS):R; ! 定義派生集合PATTERNS（這是一個稠密集合）及其屬性R; ENDSETS DATA: LENGTH=4 5 6 8; NUM=50 10 20 15; CAPACITY=19; ENDDATA min=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 -MIN(NEEDS(I):LENGTH(I) ); !合理切割模式約束; SUM(CUTS(I): X(I) ) 26; SUM(CUTS(I): X(I) ) X(I+1) ); !人為增加約束; FOR(CUTS(J): GIN(X(J) ) ; FOR(PATTERNS(I,J): GIN(R(I,J) ); end 求解這個模型，得到的結(jié)果與前面的結(jié)果完全相同。,5.3.2易拉罐下料問題,例5.4 某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用鍍錫板沖壓制成的（參見圖5-3）。易拉罐為圓柱形，包括罐身、上蓋和下底，罐身高10厘米，上蓋和下底的直徑均為5厘米。該公司使用兩種不同規(guī)格的鍍錫板原料，規(guī)格1的鍍錫板為正方形，邊長24厘米；規(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（秒）。,模式4,圖5-3 易拉罐下料模式,該工廠每周工作40小時，每周可供使用的規(guī)格1、2的鍍錫板原料分別為5萬張和2萬張。目前每只易拉罐的利潤為0.10元，原料余料損失為0.001元 / 厘米2（如果周末有罐身、上蓋或下底不能配套組裝成易拉罐出售，也看作是原料余料損失）。工廠應(yīng)如何安排每周的生產(chǎn)？,已知上蓋和下底的直徑d=5厘米，可得其面積為,19.6厘米2,表5-4 4種沖壓模式的特征,問題的目標(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ù)。但是由于生產(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)的罐身個數(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ā)出警告信息（程序和警告信息參見圖5-4）。 圖中錯誤編號“66”的含義（參見第4章的錯誤代碼表）是：模型中數(shù)據(jù)不平衡，所以發(fā)出警告信息（注意，只是警告信息，所以仍然可以繼續(xù)求解）。求解結(jié)果是：,OBJECTIVE FUNCTION VALUE 1) 4298.337 VARIABLE VALUE REDUCED COST Y1 160250.000000 0.000000 X1 0.000000 0.000050 X2 40125.000000 0.000000 X3 3750.000000 0.000000 X4 20000.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484,圖5-4 模型中數(shù)據(jù)不平衡的警告信息,這個結(jié)果可靠嗎？由于LINDO警告模型中數(shù)據(jù)之間的數(shù)量級差別太大，所以我們可以進行預(yù)處理，縮小數(shù)據(jù)之間的差別。實際上，約束（48）（50）中右端項的數(shù)值過大（與左端的系數(shù)相比較），LINDO在計算中容易產(chǎn)生比較大的誤差，所以出現(xiàn)此警告信息。,為了解決這一問題，可以將所有決策變量擴大10000倍（相當(dāng)于xi以萬次為單位，yi以萬件為單位）。此時，目標(biāo)（47）可以保持不變（記住得到的結(jié)果單位為萬元就可以了），而約束（48）（50）改為,(56),(57),(58),將模型（47）和（52）（58）輸入LINDO:,! 易拉罐下料：均衡數(shù)據(jù),Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x4 - 0.1571y2 - 0.0196y3 s.t. 1.5x1 + 2.0x2 + 1.0x3 +3.0x4 =0 10x1 + 4x2 + 16x3+ 5x4 - 2y1 =0 x1 + 2x2 + 4x4 - y1 - y2 =0 10x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0 end,求解得到：,OBJECTIVE FUNCTION VALUE,1) 0.4298337,VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484,即模式1不使用，模式2使用40125次，模式3使用3750次，模式4使用20000次，可生產(chǎn)易拉罐160250個，罐身和底、蓋均無剩余，凈利潤為4298元。,5.4 面試順序與消防車調(diào)度問題,面試順序問題,例5.5 有4名同學(xué)到一家公司參加三個階段的面試：公司要求每個同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊（即在任何一個階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以每人在三個階段的面試時間也不同，如表5-5所示（單位：分鐘）。這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在時間是早晨8：00，請問他們最早何時能離開公司？,表5-5 面試時間要求,建立模型,實際上，這個問題就是要安排4名同學(xué)的面試順序，使完成全部面試所花費的時間最少。,記tij為第i名同學(xué)參加第j階段面試需要的時間(已知)，令xij表示第i名同學(xué)參加第j階段面試的開始時刻(不妨記早上8：00面試開始為0時刻)(i=1, 2, 3, 4；j=1, 2, 3)，T為完成全部面試所花費的最少時間。,優(yōu)化目標(biāo)為,a. 時間先后次序約束(每人只有參加完前一個階段的面試后才能進入下一個階段)： xij+ tij xi，j+1 (i=1, 2, 3, 4；j=1, 2) b.每個階段j同一時間只能面試1名同學(xué)：用0-1變量yik表示第k名同學(xué)是否排在第i名同學(xué)前面(1表示是，0表示否)，則 xij+ tijxkjTyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxijT(1yik) (i, k=1, 2, 3, 4; j=1, 2, 3; ik),約束條件：,可以將非線性的優(yōu)化目標(biāo)改寫為如下線性優(yōu)化目標(biāo)： Min T s.t. T x13+ t13 T x23+ t23 T x33+ t33 T x43+ t43,Min T s.t. xij+ tij xi, j+1 (i=1, 2, 3, 4；j=1, 2) xij+ tijxkjTyik (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xkj+ tkjxijT(1yik) (i, k=1, 2, 3, 4; j=1, 2, 3; ik) xi3+ ti3T (i=1, 2, 3, 4),這個問題的0-1非線性規(guī)劃模型(當(dāng)然所有變量還有非負約束，變量yik還有0-1約束) :,Model: min =T; T = x1