数学建模规划问题的经典案例(32页).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,建立优化模型的一般步骤,1.,确定决策变量,2.,确定目标函数的表达式,3.,寻找约束条件,例,1,：,设某厂生产电脑和手机两种产品，这两种产品的生产需要逐次经过两条装配线进行装配。电脑在第一条装配线每台需要,2,小时，在第二条装配线每台需要,3,小时；手机在第一条装配线每台需要,4,小时，在第二条装配线每台需要,1,小时。第一条装配线每天有,80,个可用工时，第一条装配线每天有,60,个可用工时，电脑和手机每台的利润分别为,100,元和,80,元。问怎样制定生产计划？,分析：,目标是利润,L,；而利润是由电脑的产量,x,和手机的产量,y,决定,2.4,案例,假设：,1,、两种产品的销量不受限制,2,、原材料供应不受限制,约束条件：,装配线,1,的工时限制,装配线,2,的工时限制,变量约束,建立模型,模型求解：,1,2,4,3,6,5,7,例,2,：,最短路线问题的数学建模实例,14,15,12,10,13,20,9,12,8,8,10,1,2,4,3,6,5,7,9,8,10,例,3,：,最短路线问题算例,100,150,200,175,125,400,250,300,200,275,175,275,200,350,150,100,9-10,100,8-10,150,6-9-10,300,5-8-10,400,7-8-10,275,2-6-10,600,4-6-10,500,3-5-10,600,1-4-10,650,最短路线为,:1-4-6-9-10,，长度：,650,1,2,4,3,6,5,7,14,15,12,10,13,20,9,12,8,8,10,例,4,：,最小费用流问题,例,5,：,最大流量问题,1,2,4,3,6,5,7,14,15,12,10,13,20,9,12,8,8,10,工厂定期订购原料，存入仓库供生产之用；,车间一次加工出一批零件，供装配线每天生产之用；,商店成批购进各种商品，放在货柜里以备零售；,水库在雨季蓄水，用于旱季的灌溉和发电。,存贮模型,存贮量多少合适？,存贮量过大，存贮费用太高；存贮量太小，会导致一,次性订购费用增加，或不能及时满足需求。,问题,1,不允许缺货的存贮模型,配件厂为装配线生产若干种部件，轮换生产不同的部件时因更换设备要付生产准备费（与生产数量无关），同一部件的产量大于需求时因积压资金、占用仓库要付存贮费。今已知某一部件的日需求量,100,件，生产准备费,5000,元，存贮费每日每件,1,元。如果生产能力远大于需求，并且不允许出现缺货，试安排该产品的生产计划，即多少天生产一次（称为生产周期），每次产量多少，可使总费用最小。,问题分析,若每天生产一次，每次,100,件，无存贮费，生产准备费,5000,元，每天费用,5000,元；,若,10,天生产一次，每次,1000,件，存贮费,900+800+100=4500,元，生产准备费,5000,元，总计,9500,元，平均每天费用,950,元；,若,50,天生产一次，每次,5000,件，存贮费,4900+4800+100=122500,元，生产准备费,5000,元，总计,127500,元，平均每天费用,2550,元；,寻找生产周期、产量、需求量、生产准备费和存贮费之间的关系，使每天的费用最少。,模型假设,1,连续化，即设生产周期,T,和产量,Q,均为连续量；,2,产品每日的需求量为常数,r,；,3,每次生产准备费,C,1,，每日每件产品存贮费,C,2,；,4,生产能力为无限大（相对于需求量），当存贮量,降到零时，,Q,件产品立即生产出来供给需求，即,不允许缺货。,模型建立,总费用与变量的关系,总费用,=,生产准备费,+,存贮费,存贮费,=,存贮单价,*,存贮量,存贮量,=,？,设,t,时刻的存贮量为,q,(,t,),，,t,=0,时生产,Q,件，存贮量,q,(0)=,Q,q,(,t,),以需求速率,r,线性递减，直至,q,(,T,)=0,，如图。,q,(,t,)=,Q-r t,，,Q=r T,。,o,t,q,Q,T,r,A,不允许缺货模型的存贮量,q,(,t,),存贮量的计算,卡盟排行榜,卡盟,Microsoft Office PowerPoint,，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用,Microsoft Office PowerPoint,不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。,Microsoft Office PowerPoint,做出来的东西叫演示文稿，其格式后缀名为：,ppt,、,pptx,；或者也可以保存为：,pdf,、图片格式等,一个周期内存贮量,一个周期内存贮费,(A,的面积,),一个周期的总费用,每天平均费用,模型求解,用微分法,每天平均最小费用,思考,建模中未考虑生产费用（这应是最大一笔费,用），在什么情况下才可以不考虑它？,建模时作了“生产能力无限大”的简化假设，如 果生产能力有限，是大于需求量的一个常数，如何建模？,结果解释,当准备费,c,1,增加时，生产周期和产量都变大；,当存贮费,c,2,增加时，生产周期和产量都变小；,当日需求费,r,增加时，生产周期变小而产量变大。,这些定性结果符合常识，而定量关系（平方根，系数,2,等）凭常识是无法得出的，只能由数学建模得到。,这里得到的费用,C,与前面计算得,950,元有微小差别，你能解释吗？,在本例中,敏感性分析,讨论参数,有微小变化时对生产周期,T,影响。,由相对变化量衡量对参数的敏感程度。,T,对,c,1,的敏感程度记为,意义是当准备费增加,1%,时，生产周期增加,0.5%,；,而存贮费增加,1%,时，生产周期减少,0.5%,；,日需求量增加,1%,时，生产周期减少,0.5%,。,当,有微小变化对生产周期影响不太大。,模型假设,1,连续化，即设生产周期,T,和产量,Q,均为连续量；,2,产品每日的需求量为常数,r,；,3,每次生产准备费,C,1,，每日每件产品存贮费,C,2,；,4,生产能力为无限大（相对于需求量），允许缺,货，每天每件产品缺货损失费,C,3,，但缺货数量需,在下次生产（订货）时补足。,问题,2,允许缺货的存贮模型,模型建立,总费用,=,生产准备费,+,存贮费,+,缺货损失费,存贮费,存贮单价,*,存贮量,缺货损失费,=,缺货单价,*,缺货量,存贮量,=,？，缺货量,=,？,因存贮量不足造成缺货，因此,q,(,t,),可取负值，,q,(,t,),以需求速率,r,线性递减，直至,q,(,T,1,)=0,，如图。,q,(,t,)=,Q-r t,，,Q,=,r,T,1,。,o,t,q,Q,T,r,A,允许缺货模型的存贮量,q,(,t,),R,T,1,B,一个周期内缺货损失费,一个周期内存贮费,一个周期的总费用,每天平均费用,模型求解,用微分法 令,每天平均最小费用,每个周期的供货量,与不允许缺货模型相比较，有,结果解释,即允许缺货时，,周期和供货量增加，周期初的存贮量减少。,2,）缺货损失费愈大，愈小，愈接近 ，,愈接近 。,1,）,3,）,不允许缺货模型可视为允许缺货模型的特例。,企业生产计划,奶制品的生产与销售,空间层次,工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；,车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。,时间层次,若短时间内外部需求和内部资源等不随时间变化，可制订,单阶段生产计划,，否则应制订多阶段生产计划。,本节课题,一奶制品加工厂用牛奶生产,A1,、,A2,两种奶制品，一桶牛奶可以在甲类设备上用,12,小时加工成,3,公斤,A1,，或者在乙类设备上用,8,个小时加工成,4,公斤,A2,。根据市场需求，生产的,A1,，,A2,全部都能售出，且每公斤,A1,获利,24,元，每公斤,A2,获利,16,元。现在加工厂每天能得到,50,桶牛奶的供应，每天正式工人总的劳动时间为,480,小时，并且甲类设备每天之多能加工,100,公斤,A1,，乙类设备没有加工能力限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论一以下,3,个附加问题：,例,1,加工奶制品的生产计划,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,例,1,加工奶制品的生产计划,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,50,桶牛奶,时间,480,小时,至多加工,100,公斤,A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,公斤，应否改变生产计划？,每天：,1,桶牛奶,3,公斤,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,获利,243x,1,获利,164,x,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),时间,480,小时,至多加工,100,公斤,A,1,50,桶牛奶,每天,模型分析与假设,比例性,可加性,连续性,x,i,对目标函数的“贡献”与,x,i,取值成正比,x,i,对约束条件的“贡献”与,x,i,取值成正比,x,i,对目标函数的“贡献”与,x,j,取值无关,x,i,对约束条件的“贡献”与,x,j,取值无关,x,i,取值连续,A,1,A,2,每公斤的获利是与各自产量无关的常数,每桶牛奶加工出,A,1,A,2,的数量和时间是与各自产量无关的常数,A,1,A2,每公斤的获利是与相互产量无关的常数,每桶牛奶加工出,A,1,A,2,的数量和时间是与相互产量无关的常数,加工,A,1,A,2,的牛奶桶数是实数,线性规划模型,模型求解,图解法,x,1,x,2,0,A,B,C,D,l,1,l,2,l,3,l,4,l,5,约束条件,目标函数,Z,=0,Z,=2400,Z,=3600,z,=,c,(,常数,),等值线,c,在,B,(20,30),点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 48.000000,3)0.000000 2.000000,4)40.000000 0.000000,NO.ITERATIONS=2,模型求解,软件实现,LINDO 6.1,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,DO RANGE(SENSITIVITY)ANALYSIS?,No,20,桶牛奶生产A,1,30,桶生产,A,2,，利润,3360,元。,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE,REDUCED COST,X1 20.000000,0.000000,X2 30.000000,0.000000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 48.000000,3)0.000000 2.000000,4)40.000000 0.000000,NO.ITERATIONS=2,：,结果解释,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW,SLACK OR SURPLUS,DUAL PRICES,2)0.000000,48.000000,3)0.000000,2.000000,4)40.000000,0.000000,NO.ITERATIONS=2,原料无剩余,时间无剩余,加工能力剩余,40,max 72x1+64x2,st,2,）,x1+x250,3,）,12x1+8x2480,4,）,3x1100,end,三种资源,“,资源”剩余为零的约束为紧约束（有效约束）,结果解释,OBJECTIVE FUNCTION VALUE,1)3360.000,VARIABLE VALUE REDUCED COST,X1 20.000000 0.000000,X2 30.000000 0.000000,ROW SLACK OR SURPLUS,DUAL PRICES,2),0.000000,48.000000,3),0.000000,2.000000,4),40.000000,0.000000,NO.ITERATIONS=2,最优解下“资源”增加,1,单位时“效益”的增量,原料增加,1,单位,利润增长,48,时间增加,1,单位,利润增长,2,加工能力增长不影响利润,影子价格,35,元可买到,1,桶牛奶，要买吗？,35 48,应该买！,聘用临时工人付出的工资最多每小时几元？,2,元！,RANGES IN WHICH THE BASIS IS UNCHANGED:,OBJ COEFFICIENT RANGES,VARIABLE CURRENT ALLOWABLE ALLOWABLE,COEF INCREASE DECREASE,X1 72.000000 24.000000 8.000000,X2 64.000000 8.000000 16.000000,RIGHTHAND SIDE RANGES,ROW CURRENT ALLOWABLE ALLOWABLE,RHS INCREASE DECREASE,2 50.000000 10.000000 6.666667,3 480.000000 53.333332 80.000000,4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY)ANALYSIS?,Yes,x,1,系数范围,(64,96),x,2,系数范围,(48,72),A,1,获利增加到,30,元,/,千克，应否改变生产计划,x,1,系数由,24,3=72,增加,为,30,3=90,，在,允许范围内,不变！,(,约束条件不变,),结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED:,OBJ COEFFICIENT RANGES,VARIABLE CURRENT ALLOWABLE ALLOWABLE,COEF INCREASE DECREASE,X1 72.000000 24.000000 8.000000,X2 64.000000 8.000000 16.000000,RIGHTHAND SIDE RANGES,ROW CURRENT ALLOWABLE ALLOWABLE,RHS INCREASE DECREASE,2 50.000000 10.000000 6.666667,3 480.000000 53.333332 80.000000,4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加,10,时间最多增加,53,35,元可买到,1,桶牛奶，每天最多买多少？,最多买,10,桶,!,(,目标函数不变,),例,2,奶制品的生产销售计划,例,1,给出的,A1,、,A2,两种奶制品的生产条件、利润、及工厂的“资源”限制都不变，为增加工厂的获利，开发了奶制品的深加工技术：用,2,小时和,3,元加工费可将,1,公斤,A1,加工成,0.8,公斤的高级奶制品,B1,，也可将,1,公斤,A2,加工成,0.75,公斤的高级奶制品,B2,，每公斤,B1,能获利,44,元，每公斤,B2,能获利,32,元。试为该厂制定一个生产销售计划，使每天的净利润最大，并讨论以下问题：,若投资,30,元可增加,1,桶牛奶，投资,3,元可增加,1,小时劳动时间，应否应做这些投资？现每天投资,150,元，可赚回多少？,B,1,，,B,2,的获利经常有,10%,的波动，对定制的计划有无影响？若每公斤,B1,的获利下降,10,，计划应该变化吗？,例,2,奶制品的生产销售计划,在例,1,基础上深加工,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,公斤,A,2,或,获利,24,元,/,公斤,获利,16,元,/,公斤,0.8,千克,B,1,2,小时,3,元,1,千克,获利,44,元,/,千克,0.75,千克,B,2,2,小时,3,元,1,千克,获利,32,元,/,千克,制订生产计划，使每天净利润最大,50,桶牛奶,480,小时,至多,100,公斤,A,1,若投资,30,元可增加,1,桶牛奶，投资,3,元可增加,1,小时劳动时间，应否应做这些投资？现每天投资,150,元，可赚回多少？,B,1,，,B,2,的获利经常有,10%,的波动，对定制的计划有无影响？若每公斤,B1,的获利下降,10,，计划应该变化吗？,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,千克,A,2,或,获利,24,元,/,千克,获利,16,元,/,kg,0.8,千克,B,1,2,小时,3,元,1,千克获利,44,元,/,千克,0.75,千克,B,2,2,小时,3,元,1,千克,获利,32,元,/,千克,出售,x,1,千克,A,1,x,2,千克,A,2,，,X,3,千克,B,1,x,4,千克,B,2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x,5,千克,A,1,加工,B,1,，,x,6,千克,A,2,加工,B,2,附加约束,模型求解,软件实现,LINDO 6.1,OBJECTIVE FUNCTION VALUE,1)3460.800,VARIABLE VALUE REDUCED COST,X1 0.000000 1.680000,X2 168.000000 0.000000,X3 19.200001 0.000000,X4 0.000000 0.000000,X5 24.000000 0.000000,X6 0.000000 1.520000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 3.160000,3)0.000000 3.260000,4)76.000000 0.000000,5)0.000000 44.000000,6)0.000000 32.000000,NO.ITERATIONS=2,DO RANGE(SENSITIVITY)ANALYSIS?,No,OBJECTIVE FUNCTION VALUE,1)3460.800,VARIABLE VALUE,REDUCED COST,X1 0.000000,1.680000,X2 168.000000,0.000000,X3 19.200001,0.000000,X4 0.000000,0.000000,X5 24.000000,0.000000,X6 0.000000,1.520000,ROW SLACK OR SURPLUS DUAL PRICES,2)0.000000 3.160000,3)0.000000 3.260000,4)76.000000 0.000000,5)0.000000 44.000000,6)0.000000 32.000000,NO.ITERATIONS=2,结果解释,每天销售,168,千克,A,2,和,19.2,千克,B,1,，,利润,3460.8,（元）,8,桶牛奶加工成,A,1,，,42,桶牛奶加工成,A,2,，,将得到的,24,千克,A,1,全部加工成,B,1,除加工能力外均为紧约束,结果解释,OBJECTIVE FUNCTION VALUE,1)3460.800,VARIABLE VALUE REDUCED COST,X1 0.000000 1.680000,X2 168.000000 0.000000,X3 19.200001 0.000000,X4 0.000000 0.000000,X5 24.000000 0.000000,X6 0.000000 1.520000,ROW SLACK OR SURPLUS,DUAL PRICES,2)0.000000,3.160000,3)0.000000,3.260000,4)76.000000 0.000000,5)0.000000 44.000000,6)0.000000 32.000000,增加,1,桶牛奶使利润增长,3.16,12=37.92,增加,1,小时时间使利润增长,3.26,30,元可增加,1,桶牛奶，,3,元可增加,1,小时时间，应否投资？现投资,150,元，可赚回多少？,投资,150,元增加,5,桶牛奶，可赚回,189.6,元。（大于增加时间的利润增长）,结果解释,B,1,B,2,的获利有,10%,的波动，对计划有无影响,RANGES IN WHICH THE BASIS IS UNCHANGED:,OBJ COEFFICIENT RANGES,VARIABLE CURRENT ALLOWABLE ALLOWABLE,COEF INCREASE DECREASE,X1 24.000000 1.680000 INFINITY,X2 16.000000 8.150000 2.100000,X3 44.000000 19.750002 3.166667,X4 32.000000 2.026667 INFINITY,X5 -3.000000 15.800000 2.533334,X6 -3.000000 1.520000 INFINITY,DO RANGE(SENSITIVITY)ANALYSIS?,Yes,B,1,获利下降,10%,，超出,X3,系数允许范围,B,2,获利上升,10%,，超出,X4,系数允许范围,波动对计划有影响,生产计划应重新制订：如将,x,3,的系数改为,39.6,计算，会发现结果有很大变化。,自来水输送与货机装运,生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；,运输问题,各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。,其他费用,:450,元,/,千吨,应如何分配水库供水量，公司才能获利最多？,若水库供水量都提高一倍，公司利润可增加到多少？,元,/,千吨,甲,乙,丙,丁,A,160,130,220,170,B,140,130,190,150,C,190,200,230,/,引水管理费,例,1,自来水输送,收入：,900,元,/,千吨,支出,A,：,50,B,：,60,C,：,50,甲：,30,；,50,乙：,70,；,70,丙：,10,；,20,丁：,10,；,40,水库供水量,(,千吨,),小区基本用水量,(,千吨,),小区额外用水量,(,千吨,),（以天计）,总供水量：,160确定送水方案使利润最大,问题分析,A,：,50,B,：,60,C,：,50,甲：,30,；,50,乙：,70,；,70,丙：,10,；,20,丁：,10,；,40,总需求量,(300),每个水库最大供水量都提高一倍,利润,=,收入,(900),其它费用,(450),引水管理费,利润,(,元,/,千吨,),甲,乙,丙,丁,A,290,320,230,280,B,310,320,260,300,C,260,250,220,/,供应限制,B,C,类似处理,问题讨论,确定送水方案使利润最大,需求约束可以不变,求解,OBJECTIVE FUNCTION VALUE,1)88700.00,VARIABLE VALUE REDUCED COST,X11 0.000000 20.000000,X12 100.000000 0.000000,X13 0.000000 40.000000,X14 0.000000 20.000000,X21,30.000000,0.000000,X22,40.000000,0.000000,X23,0.000000 10.000000,X24,50.000000,0.000000,X31,50.000000,0.000000,X32 0.000000 20.000000,X33,30.000000,0.000000,这类问题一般称为,“运输问题”,(Transportation Problem),总利润,88700,（元）,A(100),B(,120,),C(,100,),甲,(30;,50),乙,(70;,70),丙,(10;,20),丁,(10;,40),40,100,50,30,50,30,如何装运，使本次飞行获利最大？,三个货舱,最大,载,重,(,吨,),最大容积,(,米,3,),例,2,货机装运,重量（吨）,空间,(,米,3,/,吨）,利润（元,/,吨）,货物,1,18,480,3100,货物,2,15,650,3800,货物,3,23,580,3500,货物,4,12,390,2850,三个货舱中实际载重必须与其最大载重成比例,前仓：,10,6800,中仓：,16,；,8700,后仓：,8,；,5300,飞机平衡,决策变量,x,ij,-,第,i,种货物装入第,j,个货舱的重量,(,吨）,i,=1,2,3,4,j,=1,2,3(,分别代表前、中、后仓,),模型假设,每种货物可以分割到任意小；,货机装运,每种货物可以在一个或多个货舱中任意分布；,多种货物可以混装，并保证不留空隙；,模型建立,货舱容积,目标函数,(,利润,),约束条件,货机装运,模型建立,货舱重量,10,；,6800,16,；,8700,8,；,5300,x,ij,-,第,i,种货物装入第,j,个货舱的重量,约束条件,平衡要求,货物供应,货机装运,模型建立,10,；6800,16,；,8700,8,；,5300,x,ij,-,第,i,种货物装入第,j,个货舱的重量,OBJECTIVE FUNCTION VALUE,1)121515.8,VARIABLE VALUE REDUCED COST,X11 0.000000 400.000000,X12 0.000000 57.894737,X13 0.000000 400.000000,X21 10.000000 0.000000,X22 0.000000 239.473679,X23 5.000000 0.000000,X31 0.000000 0.000000,X32,12.947369,0.000000X33,3.000000,0.000000,X41 0.000000 650.000000,X42 3.052632,0.000000,X43 0.000000 650.000000,货物,2,：前仓,10,后仓,5,；,货物,3:,中仓,13,后仓,3,；,货物,4:,中仓,3,。,货机装运,模型求解,最大利润约,121516,元,货物,供应点,货舱,需求点,平衡要求,运输问题,运输问题的扩展,设每月生产小、中、大型汽车的数量分别为,x,1,x,2,x,3,汽车厂生产计划,模型建立,小型 中型 大型 现有量,钢材,1.5 3 5 600,时间,280 250 400 60000,利润,2 3 4,线性规划模型,(LP),模型求解,3,）模型中增加条件：,x,1,x,2,x,3,均为整数，重新求解。,OBJECTIVE FUNCTION VALUE,1)632.2581,VARIABLE 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,）舍去小数：取,x,1,=64,，,x,2,=167,，算出目标函数值,z,=629,，与,LP,最优值,632.2581,相差不大。,2,）试探：如取,x,1,=65,，,x,2,=167,；,x,1,=64,，,x,2,=168,等，计算函数值,z,，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,IP,可用,LINDO,直接求解,整数规划,(Integer Programming,简记,IP),“gin 3”,表示“前,3,个变量为整数”，等价于：,gin x1,gin x2,gin x3,IP,的最优解,x,1,=64,，,x,2,=168,，,x,3,=0,，最优值,z,=632,max 2x1+3x2+4x3,st1.5x1+3x2+5x3600,280 x1+250 x2+400 x360000,end,gin 3,OBJECTIVE FUNCTION VALUE,1)632.0000,VARIABLE VALUE REDUCED COST,X1 64.000000 -2.000000,X2 168.000000 -3.000000,X3 0.000000 -4.000000,模型求解,IP,结果输出,其中,3,个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：,方法,1,：分解为,8,个,LP,子模型,汽车厂生产计划,若生产某类汽车，则至少生产,80,辆，求生产计划。,x,1x,2,x,3,=0,或,80,x,1,=80,，,x,2,=150,，,x,3,=0,，最优值,z,=610,LINDO,中对,0-1,变量的限定：,int,y1,int,y2,int,y3,方法,2,：引入,0-1,变量，化为整数规划,M,为大的正数，可取,1000,OBJECTIVE FUNCTION VALUE,1)610.0000,VARIABLE 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,若生产某类汽车，则至少生产,80,辆，求生产计划。,x,1,=0,或,80,x,2,=0,或,80,x,3,=0,或,80,最优解同前,NLP,虽然可用现成的数学软件求解,(,如,LINGO,MATLAB),，但是其结果常依赖于初值的选择。,方法,3,：化为非线性规划,非线性规划（,Non-Linear Programming,，简记,NLP,）,实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。,若生产某类汽车，则至少生产,80,辆，求生产计划。,x,1,=0,或,80,x,2,=0,或,80,x,3,0,或,80,应如何安排原油的采购和加工？,例,2,原油采购与加工,市场上可买到不超过,1500,吨的原油,A,：,购买量不超过,500,吨时的单价为,10000,元,/,吨；,购买量超过,500,吨但不超过,1000,吨时，超过,500,吨的 部分,8000,元,/,吨；,购买量超过,1000,吨时，超过,1000,吨的部分,6000,元,/,吨。,售价,4800,元,/,吨,售价,5600,元,/,吨,库存,500,吨,库存,1000,吨,汽油甲,(A,50%),原油,A,原油,B,汽油乙,(A,60%),决策变量,目标函数,问题分析,利润：销售汽油的收入,-,购买原油,A,的支出,难点原油,A,的购价与购买量的关系较复杂,甲,(A,50%),A,B,乙,(A,60%),购买,x,x,11,x,12,x,21,x,22,4.8,千元,/,吨,5.6,千元,/,吨,原油,A,的购买量,原油,A,B,生产汽油甲,乙的数量,c,(,x,),购买原油,A,的支出,利润,(,千元,),c,(,x,),如何表述？,原油供应,约束条件,x,500,吨单价为,10,千元,/,吨；,500,吨,x,1000,吨，超过,500,吨的,8,千元,/,吨；,1000,吨,x,1500,吨，超过,1000,吨的,6,千元,/,吨。,目标函数,购买,x,A,B,x,11,x,12,x,21,x,22,库存,500,吨,库存,1000,吨,目标函数中,c,(,x,),不是线性函数，是非线性规划；,对于用分段函数定义的,c,(,x,),，一般的非线性规划软件也难以输入和求解；,想办法将模型化简，用现成的软件求解。,汽油含原油,A,的比例限制,约束条件,甲,(A,50%),A,B,乙,(A,60%),x,11,x,12,x,21,x,22,x,1,x,2,x,3,以价格,10,8,6(,千元,/,吨,),采购,A,的吨数,目标函数,只有当以,10,千元,/,吨的价格购买,x,1,=500(,吨,),时，才能以,8,千元,/,吨的价格购买,x,2,方法,1,非线性规划模型，可以用,LINGO,求解模型求解,x,=,x,1,+x,2,+x,3,c,(,x,)=10,x,1,+8,x,2,+6,x,3,500,吨,x,1000,吨，超过,500,吨的,8,千元,/,吨,增加约束,x,=,x,1,+x,2,+x,3,c,(,x,)=10,x,1,+8,x,2,+6,x,3,方法,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.000,Variable Value Reduced Cost,X11 500.0000,0.0000000E+00,X21 500.0000,0.0000000E+00,X12 0.0000000E+00 0.0000000E+00,X22 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,吨原油,A,、,500,吨原油,B,生产汽油甲，不购买新的原油,A,，利润为,4,800,千元。,y,1,y,2,y,3,=1,以价格,10,8,6(,千元,/,吨,),采购,A,增加约束,方法,2,0-1,线性规划模型，可用,LINDO,求解,y,1,y,2,y,3,=0,或,1,OBJECTIVE FUNCTION VALUE,1)5000.000,VARIABLE VALUE REDUCED COST,Y1 1.0000