数学模型姜启源-第四章(第五版).ppt
- 文档编号:14863619
- 上传时间:2023-06-28
- 格式:PPT
- 页数:111
- 大小:2.57MB
数学模型姜启源-第四章(第五版).ppt
《数学模型姜启源-第四章(第五版).ppt》由会员分享,可在线阅读,更多相关《数学模型姜启源-第四章(第五版).ppt(111页珍藏版)》请在冰点文库上搜索。
实际问题中的优化模型,x决策变量,f(x)目标函数,gi(x)0约束条件,多元函数条件极值,决策变量个数n和约束条件个数m较大,最优解在可行域的边界上取得,数学规划,线性规划非线性规划整数规划,重点在模型的建立和结果的分析,第四章数学规划模型,第四章数学规划模型,4.1奶制品的生产与销售4.2自来水输送与货机装运4.3汽车生产与原油采购4.4接力队选拔和选课策略4.5饮料厂的生产与检修4.6钢管和易拉罐下料4.7广告投入与升级调薪4.8投资的风险与收益,企业生产计划,4.1奶制品的生产与销售,空间层次,工厂级:
根据外部需求和内部设备、人力、原料等条件,以最大利润为目标制订产品生产计划;,车间级:
根据生产计划、工艺流程、资源约束及费用参数等,以最小成本为目标制订生产批量计划.,时间层次,若短时间内外部需求和内部资源等不随时间变化,可制订单阶段生产计划,否则应制订多阶段生产计划.,例1加工奶制品的生产计划,50桶牛奶,时间480h,至多加工100kgA1,制订生产计划,使每天获利最大,35元可买到1桶牛奶,买吗?
若买,每天最多买多少?
可聘用临时工人,付出的工资最多是每小时几元?
A1的获利增加到30元/kg,应否改变生产计划?
每天:
问题,x1桶牛奶生产A1,x2桶牛奶生产A2,获利243x1,获利164x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(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)点得到最优解.,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得.,模型求解,软件实现,LINGO,model:
max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end,Globaloptimalsolutionfound.Objectivevalue:
3360.000Totalsolveriterations:
2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000,20桶牛奶生产A1,30桶生产A2,利润3360元.,结果解释,Globaloptimalsolutionfound.Objectivevalue:
3360.000Totalsolveriterations:
2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000,model:
max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end,三种资源,“资源”剩余为零的约束为紧约束(有效约束),结果解释,Globaloptimalsolutionfound.Objectivevalue:
3360.000Totalsolveriterations:
2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000,最优解下“资源”增加1单位“效益”的增量,35元可买到1桶牛奶,要买吗?
3548,应该买!
聘用临时工人付出的工资最多每小时几元?
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系数由243=72增加为303=90,在允许范围内,不变!
(约束条件不变),结果解释,Rangesinwhichthebasisisunchanged:
ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶,每天最多买多少?
最多买10桶!
目标函数不变,充分条件!
例2奶制品的生产销售计划,在例1基础上深加工,制订生产计划,使每天净利润最大,30元可增加1桶牛奶,3元可增加1h时间,应否投资?
现投资150元,可赚回多少?
50桶牛奶,480h,至多100kgA1,B1,B2的获利经常有10%的波动,对计划有无影响?
每天销售10kgA1的合同必须满足,对利润有什么影响?
出售x1kgA1,x2kgA2,,x3kgB1,x4kgB2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5kgA1加工B1,x6kgA2加工B2,附加约束,基本模型,模型求解,软件实现,LINGO,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,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,结果解释,每天销售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.1612=37.92,增加1h时间使利润增长3.26,30元可增加1桶牛奶,3元可增加1h时间,应否投资?
现投资150元,可赚回多少?
投资150元增加5桶牛奶,可赚回189.6元(大于增加时间的利润增长).,结果解释,B1,B2的获利有10%的波动,对计划有无影响,Rangesinwhichthebasisisunchanged:
ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX124.000001.68000INFINITYX216.000008.150002.10000X344.0000019.750003.166667X432.000002.026667INFINITYX5-3.0000015.800002.533333X6-3.000001.52000INFINITY,B1获利下降10%,超出X3系数允许范围,B2获利上升10%,超出X4系数允许范围,波动对计划有影响,生产计划应重新制订:
如将x3的系数改为39.6计算,会发现结果有很大变化.,敏感性分析,结果解释,x1从0开始增加一个单位时,最优目标函数值将减少1.68,ReducedCost是有意义、有条件的(LINGO没有给出),每天销售10kgA1的合同必须满足,对利润有什么影响?
公司利润减少1.6810=16.8(元),最优利润为3460.816.8=3444,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,小结与评注,由于产品利润、加工时间等均为常数,可建立线性规划模型.,线性规划模型的三要素:
决策变量、目标函数、约束条件.,用LINGO求解,输出丰富,利用影子价格和灵敏性分析可对结果做进一步研究.,建模时尽可能利用原始的数据信息,把尽量多的计算留给计算机去做(分析例2的建模).,4.2自来水输送与货机装运,生产、生活物资从若干供应点运送到一些需求点,怎样安排输送方案使运费最小,或利润最大?
运输问题,各种类型的货物装箱,由于受体积、重量等限制,如何搭配装载,使获利最高,或装箱数量最少?
其他费用:
450元/103t,应如何分配水库供水量,公司才能获利最多?
若水库供水量都提高一倍,公司利润可增加到多少?
例1自来水输送,收入:
900元/103t,支出,总供水量:
160,确定送水方案使利润最大,问题分析,总需求量:
120+180=300,总收入900160=144000(元),收入:
900元/103t,其他费用:
450元/103t,支出,引水管理费,其他支出450160=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货机装运,三个货舱中实际载重必须与其最大载重成比例.,飞机平衡,模型假设,每种货物可以分割到任意小;,每种货物可以在一个或多个货舱中任意分布;,多种货物可以混装,并保证不留空隙;,所给出的数据都是精确的,没有误差.,第i种货物的重量wi,体积vi,利润pi(i=1,2,3,4),已知参数,货舱j的重量限制WETj,体积限制VOLj,(j=1,2,3分别代表前、中、后仓),货舱容积,目标函数(利润),约束条件,模型建立,货舱重量,xij-第i种货物装入第j个货舱的重量i=1,2,3,4,j=1,2,3,决策变量,约束条件,平衡要求,货物供应,模型建立,xij-第i种货物装入第j个货舱的重量,j,k=1,2,3;jk,Globaloptimalsolutionfound.Objectivevalue:
121515.8Totalsolveriterations:
12VariableValueReducedCostX(1,1)0.000000400.0000X(1,2)0.00000057.89474X(1,3)0.000000400.0000X(2,1)7.0000000.000000X(2,2)0.000000239.4737X(2,3)8.0000000.000000X(3,1)3.0000000.000000X(3,2)12.947370.000000X(3,3)0.0000000.000000X(4,1)0.000000650.0000X(4,2)3.0526320.000000X(4,3)0.000000650.0000,货物2:
前仓7,后仓8;货物3:
前仓3,中仓13;货物4:
中仓3.,模型求解,最大利润约121516元,货物供应点货舱需求点,装载平衡要求,如果生产某一类型汽车,则至少要生产80辆,那么最优的生产计划应作何改变?
例1汽车厂生产计划,汽车厂生产三种类型的汽车,已知各类型每辆车对钢材、劳动时间的需求,利润及工厂每月的现有量.,制订月生产计划,使工厂的利润最大.,4.3汽车生产与原油采购,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,模型建立,线性规划模型(LP),模型求解,3)模型中增加条件:
x1,x2,x3均为整数,重新求解.,ObjectiveValue:
632.2581VariableValueReducedCostX164.5161290.000000X2167.7419280.000000X30.0000000.946237RowSlackorSurplusDualPrice20.0000000.73118330.0000000.003226,结果为小数,怎么办?
1)舍去小数:
取x1=64,x2=167,算出目标函数值z=629,与LP最优值632.2581相差不大.,2)试探:
如取x1=65,x2=167;x1=64,x2=168等,计算函数值z,通过比较可能得到更优的解.,但必须检验它们是否满足约束条件.为什么?
IP可用LINGO直接求解,整数规划(IntegerProgramming,简记IP),IP的最优解x1=64,x2=168,x3=0,最优值z=632,max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;gin(x1);gin(x2);gin(x3);,Globaloptimalsolutionfound.Objectivevalue:
632.0000Extendedsolversteps:
0Totalsolveriterations:
3VariableValueReducedCostX164.00000-2.000000X2168.0000-3.000000X30.000000-4.000000,模型求解,IP结果输出,其中3个子模型应去掉,然后逐一求解,比较目标函数值,再加上整数约束,得最优解:
方法1:
分解为8个LP子模型,若生产某类汽车,则至少生产80辆,求生产计划.,x1,x2,x3=0或80,x1=80,x2=150,x3=0,最优值z=610,LINGO中对0-1变量的限定:
bin(y1);bin(y2);bin(y3);,方法2:
引入0-1变量,化为整数规划,M为大的正数,本例可取1000,ObjectiveValue:
610.0000VariableValueReducedCostX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000,若生产某类汽车,则至少生产80辆,求生产计划.,x1=0或80,最优解同前,max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x30;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变量处理,尽量不用非线性规划(特别是引入的整数变量个数较少时).,小结与评注,应如何安排原油的采购和加工?
市场上可买到不超过1500t的原油A:
购买量不超过500t时的单价为10000元/t;购买量超过500t但不超过1000t时,超过500t的部分8000元/t;购买量超过1000t时,超过1000t的部分6000元/t.,例2原油采购与加工,决策变量,目标函数,问题分析,利润:
销售汽油的收入购买原油A的支出.难点:
原油A的购价与购买量的关系较复杂.,原油A的购买量,原油A,B生产汽油甲,乙的数量,c(x)购买原油A的支出,利润(千元),c(x)如何表述?
原油供应,约束条件,x500,单价为10千元/t;500x1000,超过500t的8千元/t;1000x1500,超过1000t的6千元/t.,目标函数,汽油含原油A的比例限制,约束条件,目标函数中c(x)不是线性函数,是非线性规划;,对于用分段函数定义的c(x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学模型 姜启源 第四 第五