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

生產(chǎn)與服務(wù)運(yùn)作管理中的優(yōu)化問題,優(yōu)化建模與LINDO/LINGO軟件,第5章,內(nèi)容提要,5.1 生產(chǎn)與銷售計(jì)劃問題 5.2 有瓶頸設(shè)備的多級(jí)生產(chǎn)計(jì)劃問題 5.3 下料問題 5.4 面試順序與消防車調(diào)度問題 5.5 飛機(jī)定位和飛行計(jì)劃問題,5.1 生產(chǎn)與銷售計(jì)劃問題,5.1.1問題實(shí)例,例5.1某公司用兩種原油（A和B）混合加工成兩種汽油（甲和乙）。甲、乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價(jià)分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫(kù)存量分別為500噸和1000噸，還可以從市場(chǎng)上買到不超過1500噸的原油A。原油A的市場(chǎng)價(jià)為：購(gòu)買量不超過500噸時(shí)的單價(jià)為10000元/噸；購(gòu)買量超過500噸但不超過1000噸時(shí)，超過500噸的部分8000元/噸；購(gòu)買量超過1000噸時(shí)，超過1000噸的部分6000元/噸。該公司應(yīng)如何安排原油的采購(gòu)和加工。,5.1.2建立模型,問題分析 安排原油采購(gòu)、加工的目標(biāo)是利潤(rùn)最大，題目中給出的是兩種汽油的售價(jià)和原油A的采購(gòu)價(jià)，利潤(rùn)為銷售汽油的收入與購(gòu)買原油A的支出之差。這里的難點(diǎn)在于原油A的采購(gòu)價(jià)與購(gòu)買量的關(guān)系比較復(fù)雜，是分段函數(shù)關(guān)系，能否及如何用線性規(guī)劃、整數(shù)規(guī)劃模型加以處理是關(guān)鍵所在。,模型建立設(shè)原油A的購(gòu)買量為x（噸），根據(jù)題目所給數(shù)據(jù)， 采購(gòu)的支出c(x)可表為如下的分段線性函數(shù)（以下價(jià)格以 千元/噸為單位）：,(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ù)（利潤(rùn)）為,(2),約束條件包括加工兩種汽油用的原油A、原油B庫(kù)存量的限制， 和原油A購(gòu)買量的限制，以及兩種汽油含原油A的比例限制， 它們表示為,（3）,（4）,（5）,（6）,（7）,（8）,由于（1）式中的c(x)不是線性函數(shù)，（1）（8）給出的是 一個(gè)非線性規(guī)劃。而且，對(duì)于這樣用分段函數(shù)定義的c(x)， 一般的非線性規(guī)劃軟件也難以輸入和求解。能不能想辦法 將該模型化簡(jiǎn)，從而用現(xiàn)成的軟件求解呢？,5.1.3 求解模型,3種解法,第1種解法 將原油A的采購(gòu)量x分解為三個(gè)量，即用x1，x2，x3分別表示以價(jià)格10、8、6千元/噸采購(gòu)的原油A的噸數(shù)，總支出為c(x) = 10x1+8x2+6x3，且,(9),這時(shí)目標(biāo)函數(shù)（2）變?yōu)榫€性函數(shù)：,(10),應(yīng)該注意到，只有當(dāng)以10千元/噸的價(jià)格購(gòu)買x1=500（噸）時(shí)，才能以8千元/噸的價(jià)格購(gòu)買x2（0），這個(gè)條件可以表示為,(11),同理，只有當(dāng)以8千元/噸的價(jià)格購(gòu)買x2=500（噸）時(shí)， 才能以6千元/噸的價(jià)格購(gòu)買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,將文件存儲(chǔ)并命名為exam0501a.lg4， 執(zhí)行菜單命令“LINGO|Solve”，運(yùn)行該程序得到：,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)解: 用庫(kù)存的500噸原油A、500噸原油B生產(chǎn)1000噸汽油甲，不購(gòu)買新的原油A，利潤(rùn)為4800（千元）,但是此時(shí)LINGO得到的結(jié)果只是一個(gè)局部最優(yōu)解,可以用菜單命令“LINGO|Options”在“Global Solver”選項(xiàng)卡上啟動(dòng)全局優(yōu)化（Use Global Solver）選項(xiàng)，然后重新執(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,此時(shí)LINGO得到的結(jié)果是一個(gè)全局最優(yōu)解（Global optimal solution）：購(gòu)買1000噸原油A，與庫(kù)存的500噸原油A和1000噸原油B一起，共生產(chǎn)2500噸汽油乙，利潤(rùn)為5000（千元），高于剛剛得到的局部最優(yōu)解對(duì)應(yīng)的利潤(rùn)4800（千元）。,第2種解法: 引入0-1變量將（11）和（12）轉(zhuǎn)化為線性約束,令y1=1，y2=1，y3=1分別表示以10千元/噸、8千元/噸、6千元/噸的價(jià)格采購(gòu)原油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,運(yùn)行該程序得到： 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,這個(gè)結(jié)果與前面非線性規(guī)劃模型用全局優(yōu)化得到的結(jié)果相同。,第3種解法 直接處理分段線性函數(shù)c(x)。 （1）式表示的函數(shù)c(x)如圖5-1。,記x軸上的分點(diǎn)為b1=0, b2=500, b3=1000, b4=1500。當(dāng)x在第1個(gè)小區(qū)間 b1, b2時(shí)，記x= z1b1+z2b2，z1+z2=1，z1, z20, 因?yàn)閏(x)在b1, b2是線性的，所以c(x)= z1c(b1)+z2c(b2)。同樣，當(dāng)x在第2個(gè)小區(qū)間 b2, b3時(shí)，x= z2b2+z3b3，z2+z3=1，z2, z30, c(x)= z2c(b2)+z3c(b3)。當(dāng)x在第3個(gè)小區(qū)間 b3, b4時(shí)，x= z3b3+z4b4，z3+z4=1，z3, z40, c(x)= z3c(b3)+z4c(b4)。為了表示x在哪個(gè)小區(qū)間，引入0-1變量yk(k=1,2,3)，當(dāng)x在第k個(gè)小區(qū)間時(shí)，yk=1，否則，yk=0。這樣, z1, z2, z3, z4, y1, y2, y3應(yīng)滿足,(18),(19),(20),此時(shí)x和c(x)可以統(tǒng)一地表示為,（2）（10），（18）（22）也構(gòu)成一個(gè)混合整數(shù)線性規(guī)劃模型，可以用LINDO求解。不過，我們還是將它輸入LINGO軟件，因?yàn)槠鋽U(kuò)展性更好（即當(dāng)分段函數(shù)的分段數(shù)更多時(shí)，只需要對(duì)下面程序作很小的改動(dòng)）。輸入的LINGO模型如下：,(22),輸入的LINGO模型如下：,Model: SETS: Points/14/: b, c, y, z; ! 端點(diǎn)數(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種解法相同。,備注 這個(gè)問題的關(guān)鍵是處理分段線性函數(shù)，我們推薦化為整數(shù)線性規(guī)劃模型的第2, 3種解法，第3種解法更具一般性，其做法如下。,設(shè)一個(gè)n段線性函數(shù)f(x)的分點(diǎn)為,引入zk 將x和f(x)表示為,(23),(24),zk 和0-1變量yk滿足,(25),(26),(27),5.2 有瓶頸設(shè)備的多級(jí)生產(chǎn)計(jì)劃問題,5.2.1 問題實(shí)例,在給定的外部需求和生產(chǎn)能力等限制條件下，按照生產(chǎn)總費(fèi)用最小編制未來若干個(gè)生產(chǎn)周期的最優(yōu)生產(chǎn)計(jì)劃，這種問題在文獻(xiàn)上一般稱為批量問題（Lotsizing Problems）。 我們通過下面的具體例子來說明這種多級(jí)生產(chǎn)計(jì)劃問題的優(yōu)化模型。這里“多級(jí)”的意思是需要考慮產(chǎn)品是通過多個(gè)生產(chǎn)階段（工藝過程）生產(chǎn)出來的。,例5.2 某工廠的主要任務(wù)是通過組裝生產(chǎn)產(chǎn)品A，用于滿足外部市場(chǎng)需求。,A產(chǎn)品的產(chǎn)品構(gòu)成與組裝過程見圖5-2：即D、E、F、G是從外部采購(gòu)的零件，先將零件D、E組裝成部件B，零件F、G組裝成部件C，然后將部件B、C組裝成產(chǎn)品A出售。,圖中弧上的數(shù)字表示的是組裝時(shí)部件（或產(chǎn)品）中包含的零件（或部件）的數(shù)量（可以稱為消耗系數(shù)），例如DB弧上的數(shù)字“9”表示組裝1個(gè)部件B需要用到9個(gè)零件D；BA弧上的數(shù)字“5”表示組裝1件產(chǎn)品A需要用到5個(gè)部件B；,依此類推。,圖5-2 產(chǎn)品構(gòu)成與組裝過程圖,表5-1 生產(chǎn)計(jì)劃的原始數(shù)據(jù),假設(shè)該工廠每次生產(chǎn)計(jì)劃的計(jì)劃期為6周（即每次制定未來6周的生產(chǎn)計(jì)劃），只有最終產(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個(gè)單位的能力，即生產(chǎn)1件C需要占用8個(gè)單位的能力。,對(duì)于每種零部件或產(chǎn)品，如果工廠在某一周訂購(gòu)或者生產(chǎn)該零部件或產(chǎn)品，工廠需要付出一個(gè)與訂購(gòu)或生產(chǎn)數(shù)量無關(guān)的固定成本（稱為生產(chǎn)準(zhǔn)備費(fèi)用）；如果某一周結(jié)束時(shí)該零部件或產(chǎn)品有庫(kù)存存在，則工廠必須付出一定的庫(kù)存費(fèi)用（與庫(kù)存數(shù)量成正比）。這些數(shù)據(jù)在表5-1第5、6行給出。,按照工廠的信譽(yù)要求，目前接收的所有訂單到期必須全部交貨，不能有缺貨發(fā)生；此外，不妨簡(jiǎn)單地假設(shè)目前該企業(yè)沒有任何零部件或產(chǎn)品庫(kù)存，也不希望第6周結(jié)束后留下沒有任何零部件或產(chǎn)品庫(kù)存。最后，假設(shè)不考慮生產(chǎn)提前期，即假設(shè)當(dāng)周采購(gòu)的零件馬上就可用于組裝，組裝出來的部件也可以馬上用于當(dāng)周組裝成品A。 在上述假設(shè)和所給數(shù)據(jù)下，如何制定未來6周的生產(chǎn)計(jì)劃？,5.2.2 建立模型 問題分析 這個(gè)例子考慮的是在有限的計(jì)劃期內(nèi), 給定產(chǎn)品結(jié)構(gòu)、生產(chǎn)能力和相關(guān)費(fèi)用及零部件或成品（以下統(tǒng)稱為生產(chǎn)項(xiàng)目）在離散的時(shí)間段上（這里是周，也可以是天、月等）的外部需求之后, 確定每一生產(chǎn)項(xiàng)目在每一時(shí)間段上的生產(chǎn)量 (即批量), 使總費(fèi)用最小.由于每一生產(chǎn)項(xiàng)目在每一時(shí)間段上生產(chǎn)時(shí)必須經(jīng)過生產(chǎn)準(zhǔn)備 (Setup), 所以通常的討論中總費(fèi)用至少應(yīng)考慮生產(chǎn)準(zhǔn)備費(fèi)用和庫(kù)存費(fèi)用. 其實(shí)，細(xì)心的讀者一定會(huì)問：是否需要考慮生產(chǎn)的直接成本（如原材料成本、人力成本、電力成本等）？,符號(hào)說明 為了建立這類問題的一般模型，我們定義如下數(shù)學(xué)符號(hào)： N - 生產(chǎn)項(xiàng)目總數(shù)（本例中N=7）; T - 計(jì)劃期長(zhǎng)度（本例中T=6）; K - 瓶頸資源種類數(shù)（本例中K=1）; M - 一個(gè)充分大的正數(shù)，在模型中起到使模型線性化的作用;,- 項(xiàng)目i在t時(shí)段的外部需求 （本例中只有產(chǎn)品A有外部需求）;,- 項(xiàng)目i在t時(shí)段的生產(chǎn)批量;,- 項(xiàng)目i在t時(shí)段的庫(kù)存量;,- 項(xiàng)目i在t時(shí)段是否生產(chǎn)的標(biāo)志 (0：不生產(chǎn), 1：生產(chǎn));,- 產(chǎn)品結(jié)構(gòu)中項(xiàng)目j對(duì)項(xiàng)目i的消耗系數(shù);,S(i) - 產(chǎn)品結(jié)構(gòu)中項(xiàng)目i的直接后繼項(xiàng)目集合;,- 項(xiàng)目i在t時(shí)段生產(chǎn)時(shí)的生產(chǎn)準(zhǔn)備費(fèi)用;,- 項(xiàng)目i在t時(shí)段的單件庫(kù)存費(fèi)用;,- 資源k在t時(shí)段的能力上限;,- 項(xiàng)目i在t時(shí)段生產(chǎn)時(shí), 生產(chǎn)單個(gè)產(chǎn)品占用資源k 的能力;,(x) - 這個(gè)函數(shù)當(dāng)且僅當(dāng)x0時(shí)取值1, 否則取值0.,其余均為已知的計(jì)劃參數(shù)。,目標(biāo)函數(shù),這個(gè)問題的目標(biāo)是使生產(chǎn)準(zhǔn)備費(fèi)用和庫(kù)存費(fèi)用的總和最小。因此，目標(biāo)函數(shù)應(yīng)該是每個(gè)項(xiàng)目在每個(gè)時(shí)段上的生產(chǎn)準(zhǔn)備費(fèi)用和庫(kù)存費(fèi)用的總和，即,(28),約束條件,這個(gè)問題中的約束有這么幾類：每個(gè)項(xiàng)目的物流應(yīng)該守恒、資源能力限制應(yīng)該滿足、每時(shí)段生產(chǎn)某項(xiàng)目前必須經(jīng)過生產(chǎn)準(zhǔn)備和非負(fù)約束 （對(duì)Yi,j是0-1約束）。,(29),資源能力限制比較容易理解，即,(30),所謂物流守恒（假設(shè)Ii,0 =0）,(31),每時(shí)段生產(chǎn)某項(xiàng)目前必須經(jīng)過生產(chǎn)準(zhǔn)備，也就是說當(dāng)Xit=0時(shí)Yit=0；Xit0時(shí)Yit=1。這本來是一個(gè)非線性約束，但是通過引入?yún)?shù)M（很大的正數(shù)，表示每個(gè)項(xiàng)目每個(gè)時(shí)段的最大產(chǎn)量）可以化成線性約束，即：,總結(jié): 這個(gè)問題的優(yōu)化模型就是在約束（29）（30）（31）下使目標(biāo)函數(shù)（28）達(dá)到最小。,5.2.3 求解模型,本例生產(chǎn)項(xiàng)目總數(shù)N=7(A、B、C、D、E、F、G) ，計(jì)劃期長(zhǎng)度T=6（周），瓶頸資源種類數(shù)K=1。只有A有外部需求，所以di,t中只有d1,t可以取非零需求，即表5-1中的第2行的數(shù)據(jù)，其他全部為零。 參數(shù)si,t 、 hi,t只與項(xiàng)目i有關(guān)，而不隨時(shí)段t變化，所以可以略去下標(biāo)t，其數(shù)值就是表5-1中的最后兩行數(shù)據(jù)。,由于只有一種資源，參數(shù)Ck,t可以略去下標(biāo)k，其數(shù)值就是表5-1中的第3行的數(shù)據(jù)；而ak,I,t只與項(xiàng)目i有關(guān)，而不隨時(shí)段t變化，所以可以同時(shí)略去下標(biāo)k和t，即a2=5，a3=8（其他ai為0）。從圖6-2中容易得到項(xiàng)目i的直接后繼項(xiàng)目集合S(i)和消耗系數(shù)。,準(zhǔn)備以下的數(shù)據(jù)文件（文本文件exam0502.LDT，可以看到其中也可以含有注釋語(yǔ)句）：,! 項(xiàng)目集合; A B C D E F G ! 計(jì)劃期集合; 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)準(zhǔn)備費(fèi); 400 500 1000 300 200 400 100 ! 庫(kù)存費(fèi); 12 0.6 1.0 0.04 0.03 0.04 0.04 ! 對(duì)能力的消耗系數(shù)； 0 5 8 0 0 0 0,! 項(xiàng)目間的消耗系數(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é)束;,對(duì)本例，A的外部總需求為240，所以任何項(xiàng)目的產(chǎn)量不會(huì)超過24071525000（從圖6-2可以知道，這里715已經(jīng)是每件產(chǎn)品A對(duì)任意一個(gè)項(xiàng)目的最大的消耗系數(shù)了），所以取M=25000就已經(jīng)足夠了。 本例中的具體模型可以如下輸入LINGO軟件：,MODEL: TITLE 瓶頸設(shè)備的多級(jí)生產(chǎn)計(jì)劃; ! 從文本文件exam0502.LDT中讀取數(shù)據(jù);,SETS: ! PART = 項(xiàng)目集合, Setup = 生產(chǎn)準(zhǔn)備費(fèi)，Hold = 單件庫(kù)存成本， A = 對(duì)瓶頸資源的消耗系數(shù); PART/ FILE( exam0502.LDT)/ : Setup, Hold, A; ! TIME = 計(jì)劃期集合，Capacity = 瓶頸設(shè)備的能力; TIME / FILE( exam0502.LDT)/ : Capacity; ! USES = 項(xiàng)目結(jié)構(gòu)關(guān)系，Req = 項(xiàng)目之間的消耗系數(shù); USES( PART, PART) : Req; ! PXT = 項(xiàng)目與時(shí)間的派生集合，Demand = 外部需求, X = 產(chǎn)量（批量）, Y = 0/1變量，INV = 庫(kù)存; 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個(gè)0-1變量，LINGO演示版是無法求解的,表5-2 生產(chǎn)計(jì)劃的最后結(jié)果,LINDO求解: 得到最優(yōu)目標(biāo)函數(shù)值為9245, 結(jié)果如下：,5.3 下料問題,5.3 下料問題,生產(chǎn)中常會(huì)遇到通過切割、剪裁、沖壓等手段，將原材料加工成所需大小這種工藝過程，稱為原料下料（cutting stock）問題。按照進(jìn)一步的工藝要求，確定下料方案，使用料最省，或利潤(rùn)最大，是典型的優(yōu)化問題。本節(jié)通過兩個(gè)實(shí)例討論用數(shù)學(xué)規(guī)劃模型解決這類問題的方法。,5.3.1鋼管下料問題,例5.3 某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出。從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19米長(zhǎng)。 1) 現(xiàn)有一客戶需要50根4米長(zhǎng)、20根6米長(zhǎng)和15根8米長(zhǎng)的鋼管。應(yīng)如何下料最節(jié)??？ 2) 零售商如果采用的不同切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要1）中的三種鋼管外，還需要10根5米長(zhǎng)的鋼管。應(yīng)如何下料最節(jié)省？,問題1）的求解,問題分析 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個(gè)切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。例如，我們可以將19米長(zhǎng)的鋼管切割成3根4米長(zhǎng)的鋼管，余料為7米顯然，可行的切割模式是很多的。,其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。在這種合理性假設(shè)下，切割模式一共有7種，如表5-3所示。,表5-3 鋼管下料的合理切割模式,問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)，一是切割后剩余的總余料量最小，二是切割原料鋼管的總根數(shù)最少。下面將對(duì)這兩個(gè)目標(biāo)分別討論。,模型建立 決策變量 用xi 表示按照第i種模式（i=1, 2, , 7）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(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米），這會(huì)導(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ī)劃模型，可以同時(shí)確定切割模式和切割計(jì)劃，是帶有普遍性的方法。,同1）類似，一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4米），切割計(jì)劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3米。此外，這里我們僅選擇總根數(shù)最少為目標(biāo)進(jìn)行求解。,模型建立,決策變量 由于不同切割模式不能超過3種，可以用xi 表示按照第i種模式（i=1, 2, 3）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4米長(zhǎng)、5米長(zhǎng)、6米長(zhǎng)和8米長(zhǎng)的鋼管數(shù)量分別為r1i, r2i, r3i, r4i（非負(fù)整數(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)成這個(gè)問題的優(yōu)化模型。由于在（38）（41）式中出現(xiàn)了決策變量的乘積，所以這是一個(gè)整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)在較低版本的LINGO軟件中需要運(yùn)行很長(zhǎng)時(shí)間也難以得到最優(yōu)解。為了減少運(yùn)行時(shí)間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。,例如，由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束：,（45）,又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。首先，無論如何，原料鋼管的總根數(shù)不可能少于,（根）,其次，考慮一種非常特殊的生產(chǎn)計(jì)劃：第一種切割模式下只生產(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)計(jì)劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個(gè)上界。所以可增加以下約束：,(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建模語(yǔ)言的能力，使用集合和屬性的概念，可以編寫以下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（這是一個(gè)稠密集合）及其屬性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 求解這個(gè)模型，得到的結(jié)果與前面的結(jié)果完全相同。,5.3.2易拉罐下料問題,例5.4 某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用鍍錫板沖壓制成的（參見圖5-3）。易拉罐為圓柱形，包括罐身、上蓋和下底，罐身高10厘米，上蓋和下底的直徑均為5厘米。該公司使用兩種不同規(guī)格的鍍錫板原料，規(guī)格1的鍍錫板為正方形，邊長(zhǎng)24厘米；規(guī)格2的鍍錫板為長(zhǎng)方形，長(zhǎng)、寬分別為32和28厘米。由于生產(chǎn)設(shè)備和生產(chǎn)工藝的限制，對(duì)于規(guī)格1的鍍鍍錫板原料，只可以按照?qǐng)D2中的模式1、2或3進(jìn)行沖壓；對(duì)于規(guī)格2的鍍錫板原料只能按照模式4進(jìn)行沖壓。使用模式1、2、3、4進(jìn)行每次沖壓所需要的時(shí)間分別為1.5、2、1、3（秒）。,模式4,圖5-3 易拉罐下料模式,該工廠每周工作40小時(shí)，每周可供使用的規(guī)格1、2的鍍錫板原料分別為5萬張和2萬張。目前每只易拉罐的利潤(rùn)為0.10元，原料余料損失為0.001元 / 厘米2（如果周末有罐身、上蓋或下底不能配套組裝成易拉罐出售，也看作是原料余料損失）。工廠應(yīng)如何安排每周的生產(chǎn)？,已知上蓋和下底的直徑d=5厘米，可得其面積為,19.6厘米2,表5-4 4種沖壓模式的特征,問題的目標(biāo)顯然應(yīng)是易拉罐的利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大，約束條件除每周工作時(shí)間和原料數(shù)量外，還要考慮罐身和底、蓋的配套組裝。,模型建立,決策變量 用xi 表示按照第i種模式的沖壓次數(shù)（i=1, 2, 3, 4），y1表示一周生產(chǎn)的易拉罐個(gè)數(shù)。為計(jì)算不能配套組裝的罐身和底、蓋造成的原料損失，用y2表示不配套的罐身個(gè)數(shù)，y3表示不配套的底、蓋個(gè)數(shù)。雖然實(shí)際上xi和y1，y2，y3應(yīng)該是整數(shù)。但是由于生產(chǎn)量相當(dāng)大，可以把它們看成是實(shí)數(shù)，從而用線性規(guī)劃模型處理。,決策目標(biāo) 假設(shè)每周生產(chǎn)的易拉罐能夠全部售出，公司每周的銷售利潤(rùn)是0.1y1。原料余料損失包括兩部分：4種沖壓模式下的余料損失，和不配套的罐身和底、蓋造成的原料損失。按照前面的計(jì)算及表2的結(jié)果，總損失為0.001(222.6x1 + 183.3x2 + 261.8x3 + 169.5x4 + 157.1y2 +19.6y3)。,于是，決策目標(biāo)為,(47),約束條件,時(shí)間約束：每周工作時(shí)間不超過40小時(shí)=144000（秒），由表2最后一列得,(48),原料約束： 每周可供使用的規(guī)格1、2的鍍錫板原料分別為50000張和20000張，即,(49),(50),配套約束： 由表2一周生產(chǎn)的罐身個(gè)數(shù)為x1 + 2x2 + 4x4, 一周生產(chǎn)的底、蓋個(gè)數(shù)為10x1 + 4x2 + 16x3+ 5x4，因?yàn)閼?yīng)盡可能將它們配套組裝成易拉罐銷售。所以y1滿足,(51),這時(shí)不配套的罐身個(gè)數(shù)y2，和不配套的底、蓋個(gè)數(shù)y3應(yīng)為,(52),(53),（47）（53）就是我們得到的模型，其中（51）是一個(gè)非線性關(guān)系，不易直接處理，,但是它可以等價(jià)為以下兩個(gè)線性不等式：,(54),(55),模型求解,將模型（47）（50）和（52）（55）直接輸入LINDO（輸入LINGO也可以），求解時(shí)LINDO發(fā)出警告信息（程序和警告信息參見圖5-4）。 圖中錯(cuò)誤編號(hào)“66”的含義（參見第4章的錯(cuò)誤代碼表）是：模型中數(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ù)不平衡的警告信息,這個(gè)結(jié)果可靠嗎？由于LINDO警告模型中數(shù)據(jù)之間的數(shù)量級(jí)差別太大，所以我們可以進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別。實(shí)際上，約束（48）（50）中右端項(xiàng)的數(shù)值過大（與左端的系數(shù)相比較），LINDO在計(jì)算中容易產(chǎn)生比較大的誤差，所以出現(xiàn)此警告信息。,為了解決這一問題，可以將所有決策變量擴(kuò)大10000倍（相當(dāng)于xi以萬次為單位，yi以萬件為單位）。此時(shí)，目標(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個(gè)，罐身和底、蓋均無剩余，凈利潤(rùn)為4298元。,5.4 面試順序與消防車調(diào)度問題,面試順序問題,例5.5 有4名同學(xué)到一家公司參加三個(gè)階段的面試：公司要求每個(gè)同學(xué)都必須首先找公司秘書初試，然后到部門主管處復(fù)試，最后到經(jīng)理處參加面試，并且不允許插隊(duì)（即在任何一個(gè)階段4名同學(xué)的順序是一樣的）。由于4名同學(xué)的專業(yè)背景不同，所以每人在三個(gè)階段的面試時(shí)間也不同，如表5-5所示（單位：分鐘）。這4名同學(xué)約定他們?nèi)棵嬖囃暌院笠黄痣x開公司。假定現(xiàn)在時(shí)間是早晨8：00，請(qǐng)問他們最早何時(shí)能離開公司？,表5-5 面試時(shí)間要求,建立模型,實(shí)際上，這個(gè)問題就是要安排4名同學(xué)的面試順序，使完成全部面試所花費(fèi)的時(shí)間最少。,記tij為第i名同學(xué)參加第j階段面試需要的時(shí)間(已知)，令xij表示第i名同學(xué)參加第j階段面試的開始時(shí)刻(不妨記早上8：00面試開始為0時(shí)刻)(i=1, 2, 3, 4；j=1, 2, 3)，T為完成全部面試所花費(fèi)的最少時(shí)間。,優(yōu)化目標(biāo)為,a. 時(shí)間先后次序約束(每人只有參加完前一個(gè)階段的面試后才能進(jìn)入下一個(gè)階段)： xij+ tij xi，j+1 (i=1, 2, 3, 4；j=1, 2) b.每個(gè)階段j同一時(shí)間只能面試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),這個(gè)問題的0-1非線性規(guī)劃模型(當(dāng)然所有變量還有非負(fù)約束，變量yik還有0-1約束) :,Model: min =T; T = x1