数学模型汽车厂生产计划精.ppt

《数学模型汽车厂生产计划精.ppt》由会员分享，可在线阅读，更多相关《数学模型汽车厂生产计划精.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学模型汽车厂生产计划第1页，本讲稿共15页模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3 均为整数，重新求解。均为整数，重新求解。OBJECTIVE FUNCTION VALUE 1)632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 0.731183 3)0.000000 0.003226结果为小数，怎结果为小数，怎么办？么办？1

2、）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最最优值优值632.2581相差不大。相差不大。2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，通过比较可能得到更优的解。通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？第2页，本讲稿共15页IP可用可用LINDO直接求解直接求解整数规划整数规划(Integer Programming,简记简记IP)“gin 3”表示表示“前前3个变量为个变量为整数整数”，等价于：，等价于：gi

3、n x1gin x2gin x3 IP 的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632 max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3 OBJECTIVE FUNCTION VALUE 1)632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000 模型求解模型求解 IP 结果输出结果输出第3页，本讲稿共15页其中其中3个个子模型应

4、子模型应去掉，然后逐一去掉，然后逐一求解，比较目标函数值，再加上求解，比较目标函数值，再加上整数约束，得最优解：整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型 汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0 或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610第4页，本讲稿共15页LINDO中中 对对 0-1变量的限定：变量的限定：int y1int y2int y3 方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划 M为大的正数，为大的正数，

5、可取可取1000 OBJECTIVE FUNCTION VALUE 1)610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前 第5页，本讲稿共15

6、页NLP虽虽然然可可用用现现成成的的数数学学软软件件求求解解(如如LINGO,MATLAB)，但是其结果常依赖于初值的选择。，但是其结果常依赖于初值的选择。方法方法3：化为非线性规划化为非线性规划 非线性规划（非线性规划（Non-Linear Programming，简记，简记NLP）实实践践表表明明，本本例例仅仅当当初初值值非非常常接接近近上上面面方方法法算算出出的的最最优解时，才能得到正确的结果。优解时，才能得到正确的结果。若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第6页，本讲稿共1

7、5页应如何安排原油的采购和加工应如何安排原油的采购和加工？例例2 原油采购与加工原油采购与加工 市场上可买到不超过市场上可买到不超过1500吨的原油吨的原油A：购买量不超过购买量不超过500吨时的单价为吨时的单价为10000元元/吨；吨；购买量超过购买量超过500吨但不超过吨但不超过1000吨时，超过吨时，超过500吨的吨的 部部分分8000元元/吨；吨；购买量超过购买量超过1000吨时，超过吨时，超过1000吨的部分吨的部分6000元元/吨。吨。售价售价4800元元/吨吨 售价售价5600元元/吨吨库存库存500吨吨 库存库存1000吨吨 汽油甲汽油甲(A 50%)原油原油A 原油原油B 汽

8、油乙汽油乙(A 60%)第7页，本讲稿共15页决策决策变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油的收入利润：销售汽油的收入-购买原油购买原油A的支出的支出 难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂甲甲(A 50%)A B 乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/吨吨 5.6千元千元/吨吨原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？第8页，本讲稿共15页原油供应原油供应 约束约束条件条件 x 500

9、吨单价为吨单价为10千千元元/吨；吨；500吨吨 x 1000吨，超过吨，超过500吨的吨的8千千元元/吨；吨；1000吨吨 x 1500吨，超过吨，超过1000吨的吨的6千千元元/吨。吨。目标目标函数函数购买购买x A B x11x12x21x22库存库存500吨吨 库存库存1000吨吨 第9页，本讲稿共15页 目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软件也，一般的非线性规划软件也难以输入和求解；难以输入和求解；想办法将模型化简，用现成的软件求解。想办法将模型化简，用现成的软件求解。

10、汽油含原油汽油含原油A的比例限制的比例限制 约束约束条件条件甲甲(A 50%)A B 乙乙(A 60%)x11x12x21x22第10页，本讲稿共15页x1,x2,x3 以价格以价格10,8,6(千元千元/吨吨)采购采购A的吨数的吨数目标目标函数函数 只有当以只有当以10千元千元/吨的价格购买吨的价格购买x1=500(吨吨)时，才能以时，才能以8千千元元/吨的价格购买吨的价格购买x2方法方法1 非线性规划模型非线性规划模型，可以用，可以用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500吨吨 x 1000吨，超过吨，超过500吨的吨的8千千元元

11、/吨吨增加约束增加约束x=x1+x2+x3,c(x)=10 x1+8x2+6x3 第11页，本讲稿共15页方法方法1：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 0;2*x12-3*x22 0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1 500;x2 500;x3 0;x11 0;x12 0;x21 0;x22 0;x1 0;x2 0;x3 0;end Objective value:4800.000Variable Va

12、lue Reduced CostX11 500.0000 0.0000000E+00X21 500.0000 0.0000000E+00X12 0.0000000E+00 0.0000000E+00X22 0.0000000E+00 0.0000000E+00 X1 0.1021405E-13 10.00000 X2 0.0000000E+00 8.000000 X3 0.0000000E+00 6.000000 X 0.0000000E+00 0.0000000E+00 LINGO得到的是局部最优解，还能得得到的是局部最优解，还能得到更好的解吗？到更好的解吗？用库存的用库存的500吨原油吨原

13、油A、500吨原油吨原油B生生产汽油甲，不购买新的原油产汽油甲，不购买新的原油A，利润为，利润为4,800千千元。元。第12页，本讲稿共15页y1,y2,y3=1 以价格以价格10,8,6(千元千元/吨吨)采购采购A增增加加约约束束方法方法2 0-1线性规划模型线性规划模型，可用，可用LINDO求解求解y1,y2,y3=0或或1 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 X

14、11 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 购买购买1000吨原油吨原油A，与库，与库存的存的500吨原油吨原油A和和1000吨吨原油原油B一起，生产汽油乙，一起，生产汽油乙，利润为利润为5,000千元千元。x1,x2,x3 以价格以价格10,8,6(千元千元/吨吨)采购采购A

15、的吨数的吨数y=0 x=0 x0 y=1优于方法优于方法1的结果的结果第13页，本讲稿共15页b1 b2 b3 b4方法方法3 b1 x b2，x=z1b1+z2b2，z1+z2=1，z1,z2 0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000050010001500b2 x b3，x=z2b2+z3b3，z2+z3=1，z2,z3 0,c(x)=z2c(b2)+z3c(b3).b3 x b4，x=z3b3+z4b4，z3+z4=1，z3,z4 0,c(x)=z3c(b3)+z4c(b4).直接处理处理分段线性函数直接处理处理分段线性函数c(x)第14页，本讲稿共15页IP模型，模型，LINDO求解，求解，得到的结果与方法得到的结果与方法2相相同同.处理分段线性函数，方法处理分段线性函数，方法3更具一般性更具一般性bk x bk+1yk=1,否则否则,yk=0方法方法3 bk x bk+1,x=zkbk+z k+1 bk+1zk+zk+1=1，zk,zk+1 0,c(x)=zkc(bk)+zk+1 c(bk+1).c(x)x1200090005000050010001500b1 b2 b3 b4对于对于k=1,2,3第15页，本讲稿共15页