數(shù)學建模 下料問題.ppt

1、2020/10/7,整數(shù)規(guī)劃的數(shù)學模型,Max(Min)(c1 x1+ c2 x2 + cn xn ) a11 x1+ a12 x2 + a1n xn (=,) b1 a21 x1+ a22 x2 + a2n xn (=,) b2 . am1 x1+ am2 x2 + amn xn (=,) bm x1n 0 且取整數(shù) 純整數(shù)規(guī)劃: 所有變量都有取整約束 混合整數(shù)規(guī)劃: 只有部分變量有取整約束 ,生產(chǎn)中通過切割、剪裁、沖壓等手段，將原材料加工成所需大小,鋼管和易拉罐下料,原料下料問題,按照工藝要求，確定下料方案，使所用材料最省，或利潤最大,問題1. 如何下料最節(jié)省 ?,例1 鋼管下料,問題2.

2、 客戶增加需求：,節(jié)省的標準是什么？,由于采用不同切割模式太多，會增加生產(chǎn)和管理成本，規(guī)定切割模式不能超過3種。如何下料最節(jié)?。?按照客戶需要在一根原料鋼管上安排切割的一種組合。,切割模式,合理切割模式的余料應(yīng)小于客戶需要鋼管的最小尺寸,鋼管下料,為滿足客戶需要，按照哪些種合理模式，每種模式切割多少根原料鋼管，最為節(jié)??？,合理切割模式,2. 所用原料鋼管總根數(shù)最少,鋼管下料問題1,兩種標準,1. 原料鋼管剩余總余量最小,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,7),約束,滿足需求,決策變量,目標1（總余量）,按模式2切割12根,按模式5切割15根，余料27米,最優(yōu)解：x2=12,

3、x5=15, 其余為0； 最優(yōu)值：27。,整數(shù)約束： xi 為整數(shù),當余料沒有用處時，通常以總根數(shù)最少為目標,目標2（總根數(shù)）,鋼管下料問題1,約束條件不變,最優(yōu)解：x2=15, x5=5, x7=5, 其余為0； 最優(yōu)值：25。,xi 為整數(shù),按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,雖余料增加8米，但減少了2根,與目標1的結(jié)果“共切割27根，余料27米” 相比,鋼管下料問題2,對大規(guī)模問題，用模型的約束條件界定合理模式,增加一種需求：5米10根；切割模式不超過3種。,現(xiàn)有4種需求：4米50根，5米10根，6米20根，8米15根，用枚舉法確定合理切割模式，

4、過于復(fù)雜。,決策變量,xi 按第i 種模式切割的原料鋼管根數(shù)(i=1,2,3),r1i, r2i, r3i, r4i 第i 種切割模式下，每根原料鋼管生產(chǎn)4米、5米、6米和8米長的鋼管的數(shù)量,滿足需求,模式合理：每根余料不超過3米,整數(shù)非線性規(guī)劃模型,鋼管下料問題2,目標函數(shù)（總根數(shù)）,約束條件,整數(shù)約束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)為整數(shù),增加約束，縮小可行域，便于求解,原料鋼管總根數(shù)下界：,特殊生產(chǎn)計劃：對每根原料鋼管 模式1：切割成4根4米鋼管，需13根； 模式2：切割成1根5米和2根6米鋼管，需10根； 模式3：切割成2根8米鋼管，需8根。 原料鋼

5、管總根數(shù)上界：13+10+8=31,模式排列順序可任定,鋼管下料問題2,需求：4米50根，5米10根，6米20根，8米15根,每根原料鋼管長19米,LINGO求解整數(shù)非線性規(guī)劃模型,Local optimal solution found at iteration: 12211 Objective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000

6、 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.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：每根原料鋼管切割成3根4米和1根6米鋼管，共10根； 模式2：每根原料鋼管切割成2根4米、1根5米和1根6米鋼管，共10根； 模式3：每根原料鋼管切割

7、成2根8米鋼管，共8根。 原料鋼管總根數(shù)為28根。,板材規(guī)格2： 長方形， 3228cm， 2萬張。,例2 易拉罐下料,每周工作40小時，每只易拉罐利潤0.10元，原料余料損失0.001元 / cm2（不能裝配的罐身、蓋、底也是余料）,罐身高10cm，上蓋、下底直徑均5cm。,板材規(guī)格1： 正方形，邊長24cm，5萬張。,如何安排每周生產(chǎn)？,模式1: 正方形 邊長24cm,問題分析,計算各種模式下的余料損失,上、下底直徑d=5cm，罐身高h=10cm。,模式1 余料損失 242-10d2/4 - dh=222.6 cm2,問題分析,目標:易拉罐利潤扣除原料余料損失后的凈利潤最大,約束：每周工作

8、時間不超過40小時； 原料數(shù)量：規(guī)格1（模式1 3）5萬張， 規(guī)格2（模式4）2萬張； 罐身和底、蓋的配套組裝 。,注意：不能裝配的罐身、上下底也是余料,決策變量,xi 按照第i 種模式的生產(chǎn)張數(shù)(i=1,2,3,4)； y1 一周生產(chǎn)的易拉罐個數(shù)； y2 不配套的罐身個數(shù)； y3 不配套的底、蓋個數(shù)。,模型建立,目標,約束條件,時間約束,原料約束,模型建立,y1 易拉罐個數(shù)；y2 不配套的罐身； y3 不配套的底、蓋。,每只易拉罐利潤0.10元，余料損失0.001元 / cm2,罐身面積dh=157.1 cm2 底蓋面積d2/4=19.6 cm2,(40小時),約束條件,配套約束,y1 易拉

9、罐個數(shù)；y2 不配套的罐身； y3 不配套的底、蓋。,雖然xi和y1，y2，y3應(yīng)是整數(shù)，但是因生產(chǎn)量很大，可以把它們看成實數(shù)，從而用線性規(guī)劃模型處理 。,將所有決策變量擴大10000倍（xi 萬張，yi 萬件）,LINDO發(fā)出警告信息：“數(shù)據(jù)之間的數(shù)量級差別太大，建議進行預(yù)處理，縮小數(shù)據(jù)之間的差別”,模式2生產(chǎn)40125張， 模式3生產(chǎn)3750張， 模式4生產(chǎn)20000張， 共產(chǎn)易拉罐160250個 (罐身和底、蓋無剩余)， 凈利潤為4298元,模型求解,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.00