第4章-数学规划模型

第四章数学规划模型4.1奶制品的生产与销售4.2自来水输送与货机装运4.3汽车生产与原油采购4.4接力队选拔和选课策略4.5饮料厂的生产与检修4.6钢管和易拉罐下料数学规划模型实际问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 中的优化模型x~决策变量f(x)~目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 gi(x)0~约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析企业生产计划4.1奶制品的生产与销售空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划.时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划.例1加工奶制品的生产计划50桶牛奶时间480h至多加工100kgA1制订生产计划，使每天获利最大35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/kg，应否改变生产计划？每天：问题x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应劳动时间加工能力决策变量目标函数每天获利约束条件非负约束线性规划模型(LP)时间480h至多加工100kgA1基本模型模型分析与假设比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每千克的获利是与各自产量无关的常数每桶牛奶加工A1,A2的数量,时间是与各自产量无关的常数A1,A2每千克的获利是与相互产量无关的常数每桶牛奶加工A1,A2的数量,时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型模型求解图解法目标函数z=c(常数)~等值线在B(20,30)点得到最优解.目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得.模型求解软件实现LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;endGlobaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.00000020桶牛奶生产A1,30桶生产A2，利润3360元.结果解释Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000model:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end三种资源“资源”剩余为零的约束为紧约束（有效约束）结果解释Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最优解下“资源”增加1单位时“效益”的增量影子价格35元可买到1桶牛奶，要买吗?35<48,应该买！聘用临时工人付出的工资最多每小时几元?2元！Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000最优解不变时目标函数系数允许变化范围敏感性分析(“LINGO|Ranges”)x1系数范围(64,96)x2系数范围(48,72)A1获利增加到30元/kg，应否改变生产计划?x1系数由243=72增加为303=90，在允许范围内不变！(约束条件不变)结果解释Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶,每天最多买多少?最多买10桶!(目标函数不变)充分条件!例2奶制品的生产销售计划在例1基础上深加工制订生产计划，使每天净利润最大30元可增加1桶牛奶，3元可增加1h时间，应否投资？现投资150元，可赚回多少？50桶牛奶,480h至多100kgA1B1，B2的获利经常有10%的波动，对计划有无影响？每天销售10kgA1的 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 必须满足，对利润有什么影响？出售x1kgA1,x2kgA2，x3kgB1,x4kgB2原料供应劳动时间加工能力决策变量目标函数利润约束条件非负约束x5kgA1加工B1，x6kgA2加工B2附加约束基本模型模型求解软件实现LINGOGlobaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000结果解释每天销售168kgA2和19.2kgB1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24kgA1全部加工成B1除加工能力外均为紧约束结果解释Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000增加1桶牛奶使利润增长3.16×12=37.92增加1h时间使利润增长3.2630元可增加1桶牛奶，3元可增加1h时间，应否投资？现投资150元，可赚回多少？投资150元增加5桶牛奶,可赚回189.6元(大于增加时间的利润增长).结果解释B1,B2的获利有10%的波动，对计划有无影响Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY…………B1获利下降10%，超出X3系数允许范围B2获利上升10%，超出X4系数允许范围波动对计划有影响生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化.Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000结果解释x1从0开始增加一个单位时，最优目标函数值将减少1.68ReducedCost有意义也是有条件的(LINGO没有给出)每天销售10kgA1的合同必须满足，对利润有什么影响？公司利润减少1.68×10=16.8（元）最优利润为3460.8–16.8=3444奶制品的生产与销售由于产品利润、加工时间等均为常数，可建立线性规划模型.线性规划模型的三要素：决策变量、目标函数、约束条件.用LINGO求解，输出丰富，利用影子价格和灵敏性分析可对结果做进一步研究.建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做（分析例2的建模）.4.2自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 使运费最小，或利润最大?运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少?其他费用:450元/103t应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？例1自来水输送收入：900元/103t支出总供水量：160确定送水方案使利润最大问题分析<总需求量：120+180=300总收入900160=144000(元)收入：900元/103t其他费用:450元/103t支出引水管理费其他支出450160=72000(元)供应限制约束条件需求限制线性规划模型(LP)目标函数水库i向j区的日供水量为xij（x34=0）决策变量模型建立确定3个水库向4个小区的供水量模型求解部分结果：ObjectiveValue:24400.00VariableValueReducedCostX110.00000030.000000X1250.0000000.000000X130.00000050.000000X140.00000020.000000X210.00000010.000000X2250.0000000.000000X230.00000020.000000X2410.0000000.000000X3140.0000000.000000X320.00000010.000000X3310.0000000.000000利润=总收入-其他费用-引水管理费=144000-72000-24400=47600（元）引水管理费24400(元)目标函数总供水量(320)>总需求量(300)每个水库最大供水量都提高一倍利润=收入(900)–其他费用(450)–引水管理费供应限制B,C类似处理问题讨论确定送水方案使利润最大需求约束可以不变求解部分结果：ObjectiveValue:88700.00VariableValueReducedCostX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000X2130.0000000.000000X2240.0000000.000000X230.00000010.000000X2450.0000000.000000X3150.0000000.000000X320.00000020.000000X3330.0000000.000000运输问题总利润88700（元）供需平衡或不平衡如何装运，使本次飞行获利最大？三个货舱最大载重(t),最大容积(m3)例2货机装运三个货舱中实际载重必须与其最大载重成比例.飞机平衡WET=(10,16,8),VOL=(6800,8700,5300);w=(18,15,23,12),v=(480,650,580,390),p=(3100,3800,3500,2850).已知参数i=1,2,3,4（货物）j=1,2,3(分别代表前、中、后仓)货舱j的重量限制WETj体积限制VOLj第i种货物的重量wi，体积vi，利润pi货机装运决策变量xij--第i种货物装入第j个货舱的重量(t）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误差.模型建立货舱容积目标函数(利润)约束条件货机装运模型建立货舱重量xij--第i种货物装入第j个货舱的重量约束条件平衡要求货物供应货机装运模型建立xij--第i种货物装入第j个货舱的重量!定义集合及变量;sets:cang/1..3/:WET,VOL;wu/1..4/:w,v,p;link(wu,cang):x;endsets!对已知变量赋值;data:WET=10,16,8;VOL=6800,8700,5300;w=18,15,23,12;v=480,650,580,390;p=3100,3800,3500,2850;enddatamax=@sum(wu(i):p(i)*@sum(cang(j):x(i,j)));@for(wu(i):@sum(cang(j):x(i,j))0;x2*(x2-80)>0;x3*(x3-80)>0;@gin(x1);@gin(x2);@gin(x3);方法3：化为非线性规划非线性规划（Non-LinearProgramming，简记NLP）若生产某类汽车，则至少生产80辆，求生产计划.x1=0或80最优解同前.一般地，整数规划和非线性规划的求解比线性规划困难得多，特别是问题规模较大或者要求得到全局最优解时.汽车厂生产计划决策变量为整数,建立整数规划模型.求解整数规划和非线性规划比线性规划困难得多(即便用数学软件).当整数变量取值很大时,可作为连续变量处理,问题简化为线性规划.对于类似于“x=0或80”这样的条件，通常引入0-1变量处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）.应如何安排原油的采购和加工？例2原油采购与加工市场上可买到不超过1500t的原油A：购买量不超过500t时的单价为10000元/t；购买量超过500t但不超过1000t时，超过500t的部分8000元/t；购买量超过1000t时，超过1000t的部分6000元/t.决策变量目标函数问题分析利润：销售汽油的收入购买原油A的支出.难点：原油A的购价与购买量的关系较复杂.原油A的购买量,原油A,B生产汽油甲,乙的数量c(x)~购买原油A的支出利润(千元)c(x)如何表述？原油供应约束条件x500t单价为10千元/t；500tx1000t，超过500t的8千元/t；1000tx1500t，超过1000t的6千元/t.目标函数目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解.汽油含原油A的比例限制约束条件x1,x2,x3~以价格10,8,6(千元/t)采购A的吨数目标函数只有当以10千元/t的价格购买x1=500(t)时，才能以8千元/t的价格购买x2方法1非线性规划模型，可以用LINGO求解模型求解x=x1+x2+x3,c(x)=10x1+8x2+6x3500tx1000t，超过500t的8千元/tx=x1+x2+x3,c(x)=10x1+8x2+6x3方法1：LINGO求解Model:Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x120;2*x12-3*x22>0;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1<500;x2<500;x3<500;endLocaloptimalsolutionfound.Objectivevalue:4800.000Totalsolveriterations:14VariableValueReducedCostX11500.00000.000000X21500.00000.000000X120.0000000.2666667X220.0000000.000000X10.0000000.4000000X20.0000000.000000X30.0000000.000000X0.0000000.000000LINGO得到的是局部最优解,还能得到更好的解吗？用库存的500t原油A、500t原油B生产汽油甲，不购买新的原油A，利润为4800千元.方法1：LINGO求解计算全局最优解：选LINGO|Options菜单；在弹出的选项卡中选择“GeneralSolver”；然后找到选项“UseGlobalSolver”将其选中；应用或保存；重新求解。Globaloptimalsolutionfound.Objectivevalue:5000.000Extendedsolversteps:1Totalsolveriterations:43VariableValueReducedCostX110.0000000.000000X210.0000000.900000X121500.0000.000000X221000.0000.000000X1500.00000.000000X2500.00000.000000X30.0000000.000000X1000.0000.000000还有其他建模和求解方法吗？购买1000t原油A，与库存的500t原油A和1000t原油B一起，共生产2500t汽油乙，利润为5000千元.y1,y2,y3=1~以价格10,8,6(千元/t)采购A增加约束方法20-1线性规划模型,可用LINGO求解.y1,y2,y3=0或1购买1000t原油A，与库存的500t原油A和1000t原油B一起，生产汽油乙，利润为5000千元.x1,x2,x3~以价格10,8,6(千元/t)采购A的吨数与方法1（全局最优解）的结果相同引入0-1变量模型求解b1b2b3b4方法3b1xb2，x=z1b1+z2b2，z1+z2=1，z1,z20,c(x)=z1c(b1)+z2c(b2).b2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)IP模型，LINGO求解，得到的结果与方法2相同.bkxbk+1yk=1,否则,yk=0方法3bkxbk+1,x=zkbk+zk+1bk+1zk+zk+1=1，zk,zk+10,c(x)=zkc(bk)+zk+1c(bk+1).对于k=1,2,3方法3:直接处理分段线性函数，方法更具一般性.分段函数无法直接用非线性规划方法或软件求解.原油采购与加工方法1:增加约束化为非线性规划,可以用LINGO求解,但可能得到的是局部最优解.方法2:引入0-1变量,化为线性规划模型,可用LINGO求解.分派问题4.4接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同,完成每项任务取得的效益或需要的资源不同，如何分派任务使获得的总效益最大，或付出的总资源最少?若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出抉择，使得收益最大或成本最小?如何选拔队员组成4100m混合泳接力队?例1混合泳接力队的选拔5名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种.甲乙丙丁戊蝶泳仰泳蛙泳自由泳目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=00-1规划模型cij(s)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一每种泳姿有且只有1人模型求解MODEL:sets:person/1..5/;position/1..4/;link(person,position):c,x;endsetsdata:c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;enddata输入LINGO求解min=@sum(link:c*x);@for(person(i):@sum(position(j):x(i,j))<=1;);@for(position(i):@sum(person(j):x(j,i))=1;);@for(link:@bin(x));END模型求解最优解：x14=x21=x32=x43=1,其他变量为0;输入LINGO求解甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.甲乙丙丁戊蝶泳仰泳蛙泳自由泳丁蛙泳c43=69.675.2(s)，戊自由泳c54=62.457.5(s),方案是否调整？敏感性分析？新方案:乙~蝶泳、丙~仰泳、丁~蛙泳、戊~自由泳IP一般没有与LP相类似的理论，LINGO输出的敏感性分析结果通常是没有意义的.c43,c54的新数据重新输入模型，用LINGO求解原分配方案:甲~自由泳、乙~蝶泳、丙~仰泳、丁~蛙泳.讨论混合泳接力队的选拔指派(Assignment)问题：有若干项任务,每项任务必有且只能有一人承担，每人只能承担一项，不同人员承担不同任务的效益(或成本)不同，怎样分派各项任务使总效益最大(或总成本最小)?人员数量与任务数量相等人员数量大于任务数量(本例)人员数量小于任务数量?建立0-1规划模型是常用方法为了选修课程门数最少，应学习哪些课程？例2选课策略要求至少选两门数学课、三门运筹学课和两门计算机课选修课程最少，且学分尽量多，应学习哪些课程？0-1规划模型决策变量目标函数xi=1~选修课号i的课程（xi=0~不选）选修课程总数最少约束条件最少2门数学课，3门运筹学课，2门计算机课.先修课程要求最优解：x1=x2=x3=x6=x7=x9=1,其他为0；6门课程，总学分21.0-1规划模型约束条件x3=1必有x1=x2=1模型求解（LINGO）学分最多多目标优化的处理方法：化成单目标优化.两目标(多目标)规划讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少以学分最多为目标,不管课程多少.以课程最少为目标,不管学分多少.多目标规划在课程最少的前提下以学分最多为目标.最优解：x1=x2=x3=x5=x7=x9=1,其他为0；总学分由21增至22.注意：最优解不唯一！LINGO不能告诉优化问题的解是否唯一.可将x9=1易为x6=1多目标规划对学分数和课程数加权形成一个目标，如三七开.最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其他为0；总学分28.讨论与思考最优解与1=0，2=1的结果相同——学分最多.多目标规划最优解与1=1，2=0的结果相同——课程最少.选课策略用0-1变量表示策略选择是常用的方法“要选甲(x1)必选乙(x2)”可用x1x2描述.“要选甲(x1)必不选乙(x2)”怎样描述?“甲乙二人至多选一人”怎样描述?“甲乙二人至少选一人”怎样描述?双(多)目标规划的处理方法加权组合成一个新目标,化为单目标规划.一个目标作为约束,解另一个目标的规划.问题1公司应该与哪些候选企业建立代理关系？例3销售代理的开发与中断公司未来5年的业务量分别为400，500，600，700和800问题2若目前全部建立了代理关系，应如何进行调整？候选代理1候选代理2候选代理3候选代理4年最大业务量350250300200一次性费用(万元)100809070年运行费用(万元)7.54.06.53.0代理1代理2代理3代理4临时中断费用(万元)5342重新恢复费用(万元)5419问题１的建模决策变量目标函数xit=1~在第t年初(首次)与代理i建立代理关系xit=0~否总费用（建立代理＋运行费用）最小公司可在任一年开始与代理建立代理关系.代理关系一旦建立，将长期保持.假设~建立代理运行费用问题１的建模约束条件公司每年的业务量必须能够由足够的代理承担第1年第2年第3年第4年第5年问题１的求解LINGO求解结果x11=x21=x44=1(其他变量为0)，最小总费用313.5万元公司应在第1年初与代理1、2建立代理关系;在第4年初与代理4建立代理关系.假定公司一旦与候选代理建立代理关系，则这一关系将长期保持问题2的建模决策变量目标函数xit=1~第t年代理i从事代理业务；xit=0~否总费用（运行费+中断费＋恢复费）最小公司目前已与所有代理建立代理关系.公司每年初可中断或恢复代理关系.假设yit=1~第t年与代理i中断代理关系；yit=0~否zit=1~第t年与代理i恢复代理关系；zit=0~否yit=1~第t年与代理i中断代理关系；yit=0~否zit=1~第t年与代理i恢复代理关系；zit=0~否问题2的建模约束条件业务量约束、业务中断约束、业务恢复约束业务量约束：每年公司的业务量由足够的代理承担业务中断约束：某年运行，下一年不运行，则需中断如果xit=1而xi,t+1=0，则yi,t+1=1业务恢复约束：某年不运行，下一年运行，则需恢复如果xit=0而xi,t+1=1，则zi,t+1=1问题2的求解模型分析xit的值：x11=x12=x13=x14=x15=x23=x24=x25=x41=x42=x43=x44=x45=1(其他为0);最小总费用86.5万元.公司应在第1年初临时中断与代理2、3的代理关系，而在第3年初重新恢复与代理2的代理关系.LINGO求解结果可只要求xit为0-1变量，最优解中yit(zit)自然是0-1变量设法减少整数变量数目4.5饮料厂的生产与检修单阶段生产计划多阶段生产计划生产批量问题企业生产计划考虑与产量无关的固定费用.给优化模型求解带来新的困难.安排生产计划,满足每周的需求,使4周总费用最小.存贮费:每周每千箱饮料0.2(千元).例1饮料厂的生产与检修计划在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?某种饮料4周的需求量、生产能力和成本问题分析除第4周外每周的生产能力超过每周的需求；生产成本逐周上升；前几周应多生产一些.饮料厂在第1周开始时没有库存；从费用最小考虑,第4周末不能有库存；周末有库存时需支出一周的存贮费；每周末的库存量等于下周初的库存量.模型假设目标函数约束条件产量、库存与需求平衡决策变量能力限制非负限制模型建立x1~x4：第1~4周的生产量y1~y3：第1~3周末库存量存贮费:0.2(千元/周•千箱)模型求解4周生产计划的总费用为528(千元)最优解：x1~x4：15，40，25，20；y1~y3：0，15，5.LINGO求解讨论增加库存量(y1~y3)为决策变量使模型清晰并便于检查.检修计划0-1变量wt：wt=1~检修安排在第t周(t=1,2,3,4）在4周内安排一次设备检修,占用当周15千箱生产能力,能使检修后每周增产5千箱，检修应排在哪一周?检修安排在任一周均可约束条件能力限制产量、库存与需求平衡条件不变增加约束条件：检修1次检修计划目标函数不变0-1变量wt=1~检修安排在第t周LINGO求解总费用由528降为527(千元)检修所导致的生产能力提高的作用,需要更长的时间才能得到充分体现.最优解：w1=1,w2,w3,w4=0;x1~x4：15,45,15,25；y1~y3：0,20,0.讨论引入0-1变量表示检修例2饮料的生产批量问题安排生产计划,满足每周的需求,使4周总费用最小.存贮费:每周每千箱饮料0.2(千元)(与例1同).饮料厂使用同一条生产线轮流生产多种饮料.若某周开工生产某种饮料,需支出生产准备费8千元.某种饮料4周的需求量、生产能力和成本(与例1同)ct~时段t生产费用(元/件);ht~时段t(末)存贮费(元/件)st~时段t生产准备费(元)；dt~时段t市场需求(件)；Mt~时段t生产能力(件).假设初始库存为0.制订生产计划,满足需求并使T个时段的总费用最小.决策变量xt~时段t生产量；yt~时段t(末)存贮量；问题分析与例1的主要差别:需考虑与生产数量无关的费用——生产准备费模型建立wt=1~时段t开工生产(wt=0~不开工).混合0-1规划模型目标函数约束条件模型建立ct~生产费,ht~存贮费,st~准备费,dt~需求量,Mt~生产能力,xt~生产量,yt~存贮量,wt~开工生产0-1变量.~满足需求既含可变费用(生产成本、存贮费)又含固定费用(生产准备费)的多阶段生产计划问题.最优解：x1~x4：15，40，45，0；总费用：554.0(千元)将所给参数代入模型，用LINGO求解模型求解与例1的最优解：x1~x4：15,45,15,25的区别!生产批量(Lot-sizing)问题关键是引入0-1变量wt表示时段t是否开工生产.生产中通过切割、剪裁、冲压等手段，将原材料加工成规定大小的成材.4.6钢管和易拉罐下料原料下料问题优化问题:按照工艺要求，确定下料方案，使所用材料最省，或利润最大.问题1.如何下料最节省?例1钢管下料问题2.客户增加需求：节省的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 是什么？由于采用不同切割模式太多,会增加生产和管理成本,规定切割模式不能超过3种.如何下料最节省？按照客户需要在一根原料钢管上安排切割的一种组合,如:切割模式合理切割模式的余料应小于客户需要钢管的最小尺寸.钢管下料为满足客户需要，按照哪些种合理模式切割，每种模式切割多少根原料钢管，最为节省？合理切割模式2.所用原料钢管总根数最少.钢管下料问题1节省的两种标准1.原料钢管剩余总余量最小.xi~按第i种模式切割的原料钢管根数(i=1,…,7)约束满足需求决策变量目标1（总余量）按模式2切割12根,按模式5切割15根,共27根,余料27m.最优解：x2=12,x5=15,其余为0；最优值：27.整数约束：xi为整数目标2（总根数）钢管下料问题1约束条件不变最优解：x2=15,x5=5,x7=5,其余为0；最优值：25.按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35m.目标2切割减少了2根,但余料增加8m,为什么?与目标1的结果“共切割27根，余料27m”相比.若余料没有用处,通常以总根数最少为目标.钢管下料问题1目标1(总余量)~x2=12,x5=15,共27根,余27m目标2(总根数)~x2=15,x5=5,x7=5,共25根,余35m按照目标1比需求多生产1根4m、7根6m,共46m,正好等于2根原料(38m)再加8m.原料钢管:每根19m若多生产的也视为余料,则总余量最小等价于总根数最少.钢管下料问题2对大规模问题，用模型的约束条件界定合理模式.增加一种需求：10根5m；切割模式不超过3种.现有4种需求：50根4m,10根5m,20根6m,15根8m，用枚举法确定合理切割模式，过于复杂.决策变量xi~按第i种模式切割的原料钢管根数(i=1,2,3).r1i,r2i,r3i,r4i~第i种切割模式下，每根原料钢管生产4m、5m、6m和8m长的钢管的数量.满足需求模式合理：每根余料不超过3m整数非线性规划模型钢管下料问题2目标函数（总根数）约束条件整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数增加约束，缩小可行域，便于求解.原料钢管总根数下界：特殊生产计划：对每根原料钢管模式1：切割成4根4m钢管，需13根；模式2：切割成1根5m和2根6m钢管，需10根；模式3：切割成2根8m钢管，需8根.原料钢管总根数上界：13+10+8=31模式排列顺序可任定钢管下料问题2需求：50根4m，10根5m，20根6m，15根8m每根原料钢管长19mLINGO求解整数非线性规划模型Localoptimalsolutionfound.Objectivevalue:28.00000VariableValueReducedCostX(1)10.000001.000000X(2)10.000001.000000X(3)8.0000001.000000R(1,1)3.0000000.000000R(1,2)2.0000000.000000R(1,3)0.0000000.000000R(2,1)0.0000000.000000R(2,2)1.0000000.000000R(2,3)0.0000000.000000R(3,1)1.0000000.000000R(3,2)1.0000000.000000R(3,3)0.0000000.000000R(4,1)0.0000000.000000R(4,2)0.0000000.000000R(4,3)2.0000000.000000(也是全局最优解)模式1：每根原料钢管切割成3根4m和1根6m钢管,共10根;模式2：每根原料钢管切割成2根4m、1根5m和1根6m钢管，共10根；模式3：每根原料钢管切割成2根8m钢管，共8根.原料钢管总根数为28根.板材规格2：长方形，3228cm，2万张.例2易拉罐下料每周工作40h，每只易拉罐利润0.10元，原料余料损失0.001元/cm2(不能装配的罐身、盖、底也是余料).罐身高10cm，上盖、下底直径均5cm.板材规格1：正方形，边长24cm，5万张.如何安排每周生产？模式1:正方形边长24cm问题分析计算各种模式下的余料损失上、下底直径d=5cm，罐身高h=10cm.模式1余料损失:242-10d2/4-dh=222.6cm2问题分析目标:易拉罐利润扣除原料余料损失后的净利润最大.约束：每周工作时间不超过40h；原料数量：规格1（模式1~3）5万张，规格2（模式4）2万张；罐身和底、盖的配套组装.注意：不能装配的罐身、上下底也是余料.决策变量xi~按照第i种模式的生产张数(i=1,2,3,4)；y1~一周生产的易拉罐个数；y2~不配套的罐身个数；y3~不配套的底、盖个数.模型建立目标约束条件时间约束原料约束模型建立y1~易拉罐个数；y2~不配套的罐身；y3~不配套的底、盖.每只易拉罐利润0.10元，余料损失0.001元/cm2罐身面积dh=157.1cm2底盖面积d2/4=19.6cm2(40h)约束条件配套约束y1~易拉罐个数；y2~不配套的罐身；y3~不配套的底、盖.虽然xi和y1，y2，y3应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理.将所有决策变量扩大10000倍（xi~万张，yi~万件）数据之间的数量级差别太大，可以进行预处理，缩小数据之间的差别，便于减少计算误差.模式2生产40125张，模式3生产3750张，模式4生产20000张，共产易拉罐160250个(罐身和底、盖无剩余)，净利润为4298元.模型求解Objectivevalue:0.4298337VariableValueReducedCostY116.025000.000000X10.0000000.000050X24.0125000.000000X30.37500000.000000X42.0000000.000000Y20.0000000.2233312Y30.0000000.0364844下料问题的建模确定下料模式构造优化模型规格不太多，可枚举下料模式，建立整数线性规划模型，否则要构造整数非线性规划模型，求解困难，可用缩小可行域的方法进行化简，但要保证最优解的存在.一维问题（如钢管下料）二维问题（如易拉罐下料）具体问题具体分析（比较复杂）