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

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