第四章第四章 数学规划模型数学规划模型 4.0数学规划模型数学规划模型4.1奶制品的生产与销售奶制品的生产与销售4.2 自来水输送与货机装运自来水输送与货机装运4.3 汽车生产与原油采购汽车生产与原油采购4.4 接力队选拔和选课策略接力队选拔和选课策略4.5 投资的收益和风险投资的收益和风险4.6供应与选址供应与选址y4.0数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x) 0约束条约束条件件多元函数多元函数条件极值条件极值决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域的边界上取得的边界上取得数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析一一 线性规划线性规划案例案例4.1，4.2引例引例生产组织计划问题生产组织计划问题某厂若只限生产甲乙两种产品，已知生产甲产品每单某厂若只限生产甲乙两种产品，已知生产甲产品每单位可获利位可获利10元，生产乙产品每单位可获利元，生产乙产品每单位可获利12元，甲乙元，甲乙两种产品的生产都必须经过厂里的三个车间，每单位两种产品的生产都必须经过厂里的三个车间，每单位产品在每个车间里所需要的工时数和每个车间可以用产品在每个车间里所需要的工时数和每个车间可以用来加工的总时数如下表，问应如何安排生产，才能使来加工的总时数如下表，问应如何安排生产，才能使厂方获得最大利润？厂方获得最大利润？单位产品需工时数单位产品需工时数一车间一车间二车间二车间三车间三车间甲（甲（10元）元）231乙（乙（12元）元）321本月总时数本月总时数15001500600单位产品需工时数单位产品需工时数一车间一车间二车间二车间三车间三车间甲（甲（10元）元）231乙（乙（12元）元）321本月总时数本月总时数15001500600设一月中生产甲产品设一月中生产甲产品x1个单位，乙产品个单位，乙产品x2个单位个单位厂方本月所获利润为厂方本月所获利润为F模模型型表示利润表示利润F最大最大一车间可用工时数限制一车间可用工时数限制二车间可用工时数限制二车间可用工时数限制三车间可用工时数限制三车间可用工时数限制两种产品非负约束两种产品非负约束线性规划问题的标准型线性规划问题的标准型目标函数目标函数约束条件约束条件若记若记则则矩阵形式矩阵形式(LP)(LinearProgramming)非标准型化标准型非标准型化标准型1）若求）若求minF =cx可化为可化为max(-F)=-cx2）若）若的第的第i行行则引入则引入松弛变量松弛变量即可化为等式约束即可化为等式约束时同理时同理3）若某）若某xk无非负要求，无非负要求，xk自由变量自由变量令令思考：思考：自由变量自由变量线性规划的求解线性规划的求解1）若只有两个变量时可以用图解法，见）若只有两个变量时可以用图解法，见4.12）单纯形法（略）有兴趣可参阅运筹学方面的教材）单纯形法（略）有兴趣可参阅运筹学方面的教材3）Matlab软件求解软件求解4）LindoLingo软件求解软件求解计算机软件计算机软件直接求解直接求解用用MATLAB优化工具箱解线性规划优化工具箱解线性规划命令：命令：x=linprog（c，A，b）2、模型、模型：min z=cX 命令：命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：注意：若没有不等式：存在，则令存在，则令A=，b=.min z=cX 1、模型：、模型：3、模型、模型：min z=cX lbXub命令：命令：1 x=linprog（c，A，b，Aeq,beq,lb，ub）2x=linprog（c，A，b，Aeq,beq,lb，ub,X0） 注意：注意：1若没有等式约束若没有等式约束:,则令则令Aeq=,beq=.2其中其中X0表示初始点表示初始点4、命令：、命令：x,fval=linprog()返回最优解及处的目标函数值返回最优解及处的目标函数值fval.c=-10-12;A=23;32;11;b=15001500600;Aeq=;beq=;lb=0;0;ub=;x,fval=linprog(c,A,b,Aeq,beq,lb,ub)用用MATLAB求解引例求解引例Optimizationterminatedsuccessfully.x=300.0000300.0000fval=-6.6000e+003用用Lingo软件解软件解线性规划线性规划max=10*x1+12*x2;2*x1+3*x21500;3*x1+2*x21500;x1+x2600;Globaloptimalsolutionfoundatiteration:2Objectivevalue:6600.000VariableValueReducedCostX1300.00000.000000X2300.00000.000000RowSlackorSurplusDualPrice16600.0001.00000020.0000003.20000030.0000001.20000040.0000000.000000问题问题1某厂利用甲某厂利用甲,乙乙,丙丙,丁四种设备生产丁四种设备生产A,B,C三种产品三种产品,相关数据如表所示相关数据如表所示.已知这三种产品的已知这三种产品的单件利润分别是单件利润分别是4.5,5,7（百元）（百元）,试问该厂应如何安试问该厂应如何安排生产可获得最大利润排生产可获得最大利润?ABC总工时总工时甲甲224800乙乙123650丙丙423850丁丁242700分析分析：该问题的关键所在是确定每种产品的产量该问题的关键所在是确定每种产品的产量,为此以为此以表示三种产品的产量表示三种产品的产量,则目标则目标为为在一个生产周期中在一个生产周期中,每种设备所提供的工时为有限每种设备所提供的工时为有限的的,故对四种设备而言还应该满足下列条件故对四种设备而言还应该满足下列条件:非负性非负性用用Lingo软件可以得到相应问题的解软件可以得到相应问题的解.启动启动Lingo,在窗在窗口下中输入下列程序口下中输入下列程序:保存完之后执行保存完之后执行Lingo菜单下的菜单下的Solve命令命令,得到相应的解得到相应的解.VariableValueReducedCostX185.714290.000000X271.428570.000000X3121.42860.000000RowSlackorSurplusDualPrice11592.8571.00000020.0000001.357143357.142860.00000040.0000000.214285750.0000000.4642857问题问题2某车间要制造某车间要制造100套钢筋架套钢筋架,每套需要长为每套需要长为2.9m,2.1m,1.5m的钢筋各一根的钢筋各一根.已知原料钢筋长度已知原料钢筋长度为为7.4m,问如何切割钢筋问如何切割钢筋,使得钢筋的利用率为最高使得钢筋的利用率为最高?分析分析该问题的要点是如何切割钢筋该问题的要点是如何切割钢筋,使得每次切割使得每次切割之后之后,剩下的余料为最少剩下的余料为最少?假设在切割过程中假设在切割过程中,我们不考虑钢筋的损耗我们不考虑钢筋的损耗,并考并考虑各种切割方案虑各种切割方案:方案方案2.92.11.5余料余料1103022010.130220.241200.350130.8从分析中可以看出从分析中可以看出,此问题的关键是确定每此问题的关键是确定每种方案下的余料数种方案下的余料数.设设表示第表示第种方案中使用的原料钢种方案中使用的原料钢筋数筋数,则余料数为则余料数为而相应的限制条件为而相应的限制条件为非负性非负性在在Lingo下得到该问题的解为下得到该问题的解为运行后得到该问题的解为运行后得到该问题的解为X210.000000.000000X30.0000000.3666667X450.000000.000000X50.0000001.283333X130.000000.000000问题问题3要从甲地调出物资要从甲地调出物资2000吨吨,从乙地调出物资从乙地调出物资1100吨吨,分别供给分别供给A地地1700吨吨,B地地1100吨吨,C地地200吨吨和和D地地100吨吨,已知每吨运费如表所示已知每吨运费如表所示,试建立一个使试建立一个使运费达到最小的调拨计划运费达到最小的调拨计划.单位路程运费表单位路程运费表销地销地15375151乙乙1572521甲甲DCBA产地产地分析分析设从第设从第个产地到第个产地到第个销地的运输量为个销地的运输量为运输成本为运输成本为则问题的目标函数为则问题的目标函数为由于从第一个产地调出的物资的总和为第一个产地由于从第一个产地调出的物资的总和为第一个产地的产量的产量,即有即有同理同理,有有对称地对称地,对销地而言对销地而言,有关系有关系由此得到该问题的数学模型由此得到该问题的数学模型注注该问题又称为运输问题该问题又称为运输问题.运输问题的一般形式运输问题的一般形式可写成可写成其中其中是第是第个产地的产量个产地的产量,是第是第个销地的个销地的需求量需求量.在上面的关系中在上面的关系中,有有相应的运输问题称为相应的运输问题称为产销平衡产销平衡的运输问题的运输问题.若产销若产销不平衡不平衡,应该如何处理应该如何处理?为什么总是假定产销是平衡为什么总是假定产销是平衡的的.二二 整数规划整数规划案例案例4.3，4.4整数规划的求解整数规划的求解1）分支定界法和割平面法（略）分支定界法和割平面法（略）有兴趣可参阅运筹学方面的教材有兴趣可参阅运筹学方面的教材2）LindoLingo软件求解软件求解（后面讲）（后面讲）IPIntegerProgramming0-1规划规划整数规划的求解整数规划的求解1）隐枚举法（略）有兴趣可参阅运筹学方面的教材）隐枚举法（略）有兴趣可参阅运筹学方面的教材3）LindoLingo软件求解软件求解（后面讲）（后面讲）2）Matlab软件求解软件求解（7.0版本以上）版本以上）x,fval=bintprog（c,A,b,Aeq,beq）三三 多目标规划多目标规划4.4，4.5四四 非线性规划非线性规划4.3，4.6求解求解方法多样化，技巧性强方法多样化，技巧性强企业生产计划企业生产计划4.1奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。用参数等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划。，否则应制订多阶段生产计划。本节课题本节课题例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3600z=c (常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。 模型求解模型求解 软件实现软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？ 2元！元！RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/千克，应否改变生产计划千克，应否改变生产计划x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内不变！不变！(约束条件不变约束条件不变)结果解释结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最多买多少？ 最多买最多买10桶桶!(目标函数不变目标函数不变)例例2奶制品的生产销售计划奶制品的生产销售计划 在例在例1基础上深加工基础上深加工1桶桶牛奶牛奶3千克千克A112小时小时8小时小时4公斤公斤A2或或获利获利24元元/公斤公斤获利获利16元元/公斤公斤0.8千克千克B12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投小时时间，应否投资？现投资资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480小时小时至多至多100公斤公斤A1B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？1桶桶牛奶牛奶3千克千克A112小时小时8小时小时4千克千克A2或或获利获利24元元/千克千克获利获利16元元/kg0.8千克千克 B12小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克出售出售x1千克千克A1,x2千克千克A2，X3千克千克B1,x4千克千克B2原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 x5千克千克A1加工加工B1，x6千克千克A2加工加工B2附加约束附加约束 OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2模型求解模型求解 软件实现软件实现 LINDO6.1DORANGE(SENSITIVITY)ANALYSIS? NoOBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2结果解释结果解释每天销售每天销售168千克千克A2和和19.2千克千克B1，利润利润3460.8（元）（元）8桶牛奶加工成桶牛奶加工成A1，42桶桶牛奶加工成牛奶加工成A2，将得到的将得到的24千克千克A1全部全部加工成加工成B1除加工能力外均除加工能力外均为紧约束为紧约束结果解释结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000增加增加1桶牛奶使利润增桶牛奶使利润增长长3.1612=37.92增加增加1小时时间使利小时时间使利润增长润增长3.2630元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，小时时间，应否投资？现投资应否投资？现投资150元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶，桶牛奶，可赚回可赚回189.6元。（大于元。（大于增加时间的利润增长）增加时间的利润增长）结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITYDORANGE(SENSITIVITY)ANALYSIS? YesB1获利下降获利下降10%，超，超出出X3系数允许范围系数允许范围B2获利上升获利上升10%，超，超出出X4系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6计算，会发现结果有很大变化。计算，会发现结果有很大变化。4.2 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；怎样安排输送方案使运费最小，或利润最大；运输问题运输问题各种类型的货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。如何搭配装载，使获利最高，或装箱数量最少。其他费用其他费用: :450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？ 若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？ 元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量(千千吨吨)小小区区基基本本用用水水量量(千千吨吨)小小区区额额外外用用水水量量(千千吨吨)（以天计）（以天计）总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润=收入收入(900)其它费用其它费用( (450) 引水管理费引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变或按教材需求约束可以不变或按教材p97中简化中简化求解求解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这类问题一般称为这类问题一般称为“运输问题运输问题”(TransportationProblem)总利润总利润 88700（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重( (吨吨),),最大容积最大容积( (米米3 3) )例例2货机装运货机装运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡决策决策变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量( (吨）吨）i=1,2,3,4, j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙； 模型建立模型建立 货舱货舱容积容积 目标目标函数函数( (利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量约束约束条件条件平衡平衡要求要求 货物货物供应供应 货机装运货机装运模型建立模型建立 10；680016；87008；5300xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量Objectivevalue:121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000货物货物2：前仓：前仓10, ,后仓后仓5；货物货物3: : 中仓中仓13,后仓后仓3；货物货物4: : 中仓中仓3。货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元货物货物供应点供应点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题的扩展运输问题的扩展货物货物2：前仓：前仓10, ,后仓后仓5；货物货物3: : 中仓中仓13,后仓后仓3；货物货物4: : 中仓中仓3。X21=10,X23=5；X32=13,X33=3；X42=3。注意：取整后不满足约束条件注意：取整后不满足约束条件22）要得到整数解，可以在模型中加人整数约束，要得到整数解，可以在模型中加人整数约束，于是问题变为整数规划模型（于是问题变为整数规划模型（IP），再求解！），再求解！思考思考Globaloptimalsolutionfoundatiteration:11Objectivevalue:121400.0VariableValueX110.000000X122.000000X130.000000X217.000000X220.000000X238.000000X313.000000X3212.00000X330.000000X410.000000X422.000000X430.000000121515.80.0000000.0000000.00000010.0000000.0000005.0000000.00000012.9473693.0000000.0000003.0526320.000000结果对比结果对比LingoLingo求解求解 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆， 那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1汽车厂生产计划汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。材、劳动时间的需求，利润及工厂每月的现有量。小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。4.3 汽车生产与原油采购汽车生产与原油采购设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1, x2, x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)模型模型求解求解 3）模型中增加条件：模型中增加条件：x1, x2, x3均为整数，重新求解。均为整数，重新求解。OBJECTIVEVALUE632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280.000000X30.0000000.946237ROWSLACKORSURPLUSDUALPRICES2)0.0000000.7311833)0.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=632model: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);endOBJECTIVEVALUE632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解模型求解 IP结果输出结果输出其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1, ,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610LINGO中中对对0-1变量的限定：变量的限定：biny1biny2biny3方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数，为大的正数，可取可取1000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80x2=0 或 80x3=0 或 80最优解最优解同前同前OBJECTIVEVALUE610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000NLP虽虽然然可可用用现现成成的的数数学学软软件件求求解解( (如如LINGO, , MATLAB) )，但是其结果常依赖于初值的选择。，但是其结果常依赖于初值的选择。 方法方法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记，简记NLP）用用LINGO求求解解本本例例，得得到到的的最最优优解解刚刚好好和和前前面面两两种种方方法法计计算算结结果果相相同同。即即本本例例中中结结果果为为全全局局最最优优，但要注意但要注意不是所有不是所有NLP问题都能得到全局最优解！问题都能得到全局最优解！ 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。 x1=0 或 80x2=0 或 80x3=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%)AB乙乙(A 60%)购买购买xx11x12x21x224.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 ABx11x12x21x22库存库存500吨吨库存库存1000吨吨目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划； 对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软，一般的非线性规划软件也难以输入和求解；件也难以输入和求解； 想办法将模型化简，用现成的软件求解。想办法将模型化简，用现成的软件求解。汽油含原油汽油含原油A的比例限制的比例限制约束约束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22x1,x2,x3以价格以价格10,8,6(千元千元/ /吨吨) )采购采购A的吨数的吨数目标目标函数函数 只有当以只有当以10千元千元/吨的价格购买吨的价格购买x1=500( (吨吨) )时，才能以时，才能以8千元千元/吨的价格购买吨的价格购买x2方法方法1 非线性规划模型非线性规划模型，可以用，可以用LINGO求解求解模型求解模型求解x=x1+x2+x3, c(x)=10x1+8x2+6x3 500吨吨 x 1000吨，超过吨，超过500吨的吨的8千千元元/ /吨吨增加约束增加约束同理同理方法方法1：LINGO求解求解Model:max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x11+x12x+500;x21+x220;2*x12-3*x220;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x30;x110;x120;x210;x220;x10;x20;x30;endObjectivevalue:4800.000VariableValueReducedCostX11500.00000.000000X21500.00000.000000X120.0000000.000000X220.0000000.000000X10.0000000.000000X20.0000000.000000X30.0000000.000000X0.0000000.000000LINGO得到的是局部最优得到的是局部最优解，还能得到更好的解吗？解，还能得到更好的解吗？用库存的用库存的500吨原油吨原油A、500吨原油吨原油B生产汽油甲，不购买新的原油生产汽油甲，不购买新的原油A，利润为利润为4,800千千元。元。 求全求全局最局最优解优解y1,y2,y3=1以价格以价格10,8,6(千元千元/ /吨吨) )采购采购A增增加加约约束束方法方法2 0-1线性规划模型线性规划模型，可用，可用LINGO求解求解y1, ,y2, ,y3=0或或1OBJECTIVEVALUE5000.000VARIABLEVALUEREDUCEDCOSTX110.0000000.000000X210.0000001.400000X121500.0000.000000X221000.0000.000000X1500.00000.000000X2500.00000.000000X30.0000000.000000X1000.0000.000000Y11.0000000.000000Y21.0000002000.000Y31.0000001000.000购买购买1000吨原油吨原油A，与，与库存的库存的500吨原油吨原油A和和1000吨原油吨原油B一起，生一起，生产汽油乙，利润为产汽油乙，利润为5,000千元千元。x1,x2,x3以价格以价格10,8,6(千元千元/ /吨吨) )采购采购A的吨数的吨数yi=0xi=0xi0yi=1优于方法优于方法1的局部最优解的局部最优解b1b2b3b4方法方法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)IP模型，模型，LINDG求求解解，得到的结果与，得到的结果与方法方法2相同相同. .处理分段线性函数，方法处理分段线性函数，方法3更具一般性更具一般性P106bk x bk+1yk=1, ,否则否则, ,yk=0方法方法3 bk x bk+1, ,x= zkbk+z k+1bk+1zk+zk+1=1，zk,zk+1 0,c(x)= zkc(bk)+zk+1c(bk+1).c(x)x1200090005000050010001500b1b2b3b4对于对于k=1,2,3分派问题分派问题4.4 接力队选拔和选课策略接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源都不同，如何分完成每项任务取得的效益或需要的资源都不同，如何分派任务使获得的总效益最大，或付出的总资源最少。派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。足一定条件下作出决择，使得收益最大或成本最小。丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进步到步到57”5,组成接力队的方案是否应该调整组成接力队的方案是否应该调整？如何选拔队员组成如何选拔队员组成4 4 100100米混合泳接力队米混合泳接力队? ?例例1混合泳接力队的选拔混合泳接力队的选拔甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”45名候选人的名候选人的百米成绩百米成绩组成接力队的方案共有组成接力队的方案共有5!=120种种。穷举法：穷举法：目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1, , 否则记否则记xij=0 0-1规划模型规划模型 cij( (秒秒) )队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩约束约束条件条件每人最多入选泳姿之一每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有每种泳姿有且只有1 1人人 模型求解模型求解 最最优优解解：x14=x21=x32=x43=1,其它变量为其它变量为0;成成绩绩为为253.2( (秒秒) )=413”2model:Min=66.8*x11+75.6*x12+87*x13+58.6*x14+67.4*x51+71*x52+83.8*x53+62.4*x54x11+x12+x13+x141x41+x42+x43+x441c=-0.05-0.27-0.19-0.185-0.185;Aeq=11.011.021.0451.065;beq=1;A=00.025000;000.01500;0000.0550;00000.026;b=a;a;a;a;vlb=0,0,0,0,0;vub=;x,val=linprog(c,A,b,Aeq,beq,vlb,vub);a,x=xQ=-valplot(a,Q,.)，axis(00.100.5)，holdona=a+0.001;endxlabel(a),ylabel(Q)To Matlab（invest.m）计计算算结结果果a=0.0030x=0.49490.12000.20000.05450.1154Q=0.1266a=0.0060x=00.24000.40000.10910.2212Q=0.2019a=0.0080x=0.00000.32000.53330.12710.0000Q=0.2112a=0.0100x=00.40000.584300Q=0.2190a=0.0200x=00.80000.188200Q=0.2518a=0.0400x=0.00000.99010.000000Q=0.2673五、结果分析五、结果分析4.4.在在a=0.006a=0.006附近有一个转折点，在这一点左边，风险增加很附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是应该选择曲线的拐点作为最优投资组合，大约是a a* *=0.6%=0.6%，Q Q* *=20%=20%3.曲线上的任一点都表示该风险水平的最大可能收益和该收益曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险水平要求的最小风险。对于不同风险的承受能力，选择该风险水平下的最优投资组合。下的最优投资组合。2.当投资越分散时，投资者承担的风险越小，这与题意一致。当投资越分散时，投资者承担的风险越小，这与题意一致。即即: :冒险的投资者会出现集中投资的情况，保守的投资者则尽冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。量分散投资。1.风险大，收益也大。风险大，收益也大。所对应投资方案为所对应投资方案为: : 风险度风险度收益收益x0x1x2x3x40.00600.201900.24000.40000.10910.2212某公司有某公司有6个建筑工地要开工，每个工地的位置（用平面坐标系个建筑工地要开工，每个工地的位置（用平面坐标系a，b表示，距离单位：千米表示，距离单位：千米）及水泥日用量）及水泥日用量d(吨吨)由下表给出。目由下表给出。目前有两个临时料场位于前有两个临时料场位于A(5,1)，B(2,7)，日储量各有，日储量各有20吨。假设从吨。假设从料场到工地之间均有直线道路相连。料场到工地之间均有直线道路相连。（1）试制定每天的供应计划，即从）试制定每天的供应计划，即从A，B两料场分别向各工地运两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。送多少吨水泥，使总的吨千米数最小。（2）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两）为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为个新的，日储量各为20吨，问应建在何处，节省的吨千米数有多大吨，问应建在何处，节省的吨千米数有多大？4.6 供应与选址供应与选址（一）、建立模型（一）、建立模型 记工地的位置为记工地的位置为(ai，bi)，水泥日用量为，水泥日用量为di，i=1,6;料场位置为料场位置为(xj，yj)，日储量为，日储量为ej，j=1,2；从料场；从料场j向工地向工地i的运送量为的运送量为Xij。当用临时料场时决策变量为：当用临时料场时决策变量为：Xij，当不用临时料场时决策变量为：当不用临时料场时决策变量为：Xij，xj，yj。（二）使用临时料场的情形（二）使用临时料场的情形使用两个临时料场使用两个临时料场A(5,1)，B(2,7).求从料场求从料场j向工地向工地i的运送量的运送量为为Xij，在各工地用量必须满足和各料场运送量不超过日储量的，在各工地用量必须满足和各料场运送量不超过日储量的条件下，使总的吨千米数最小，这是线性规划问题条件下，使总的吨千米数最小，这是线性规划问题.线性规划模线性规划模型为：型为：设设X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,X61=X6X12=X7,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12a=1.258.750.55.7537.25;b=1.250.754.7556.57.75;d=3547611;x=52;y=17;e=2020;fori=1:6forj=1:2aa(i,j)=sqrt(x(j)-a(i)2+(y(j)-b(i)2);endendCC=aa(:,1);aa(:,2);A=111111000000;000000111111;B=20;20;Aeq=100000100000010000010000001000001000000100000100000010000010000001000001;beq=d(1);d(2);d(3);d(4);d(5);d(6);VLB=000000000000;VUB=;xx,fval=linprog(CC,A,B,Aeq,beq,VLB,VUB)Matlab求解：编写程序求解：编写程序gying1.m计算结果为：计算结果为：x = 3.0000 5.0000 0.0000 7.0000 0.0000 1.0000 0.0000 0.0000 4.0000 0.0000 6.0000 10.0000fval = 136.2275（三）改建两个新料场的情形（三）改建两个新料场的情形 改建两个新料场，要同时确定料场的位置改建两个新料场，要同时确定料场的位置( (xj,yj) )和运送量和运送量Xij，在同样条件下使总吨千米数最小。这是非线性规划问题。，在同样条件下使总吨千米数最小。这是非线性规划问题。非线性规划模型为：非线性规划模型为：设设X11=X1,X21=X2,X31=X3,X41=X4,X51=X5,X61=X6X12=X7,X22=X8,X32=X9,X42=X10,X52=X11,X62=X12 x1=X13,y1=X14,x2=X15,y2=X16(1)先编写先编写M文件文件liaoch.m定义目标函数。定义目标函数。(2)取初值为线性规划的计算结果及临时料场的坐标取初值为线性规划的计算结果及临时料场的坐标:x0=35070100406105127;编写主程序编写主程序gying2.m.Matlab求解：编写函数求解：编写函数liaoch.mfunctionf=liaoch(x)a=1.258.750.55.7537.25;b=1.250.754.7556.57.75;d=3547611;e=2020;f1=0;fori=1:6s(i)=sqrt(x(13)-a(i)2+(x(14)-b(i)2);f1=s(i)*x(i)+f1;endf2=0;fori=7:12s(i)=sqrt(x(15)-a(i-6)2+(x(16)-b(i-6)2);f2=s(i)*x(i)+f2;endf=f1+f2;Matlab求解：编写程序求解：编写程序gying2.mx0=35070100406105127;%x0=35471000005115.63484.86877.24797.7499;A=11111100000000000000001111110000;B=20;20;Aeq=100000100000000001000001000000000010000010000000000100000100000000001000001000000000010000010000;beq=3547611;vlb=zeros(12,1);-inf;-inf;-inf;-inf;vub=;x,fval,exitflag=fmincon(liaoch,x0,A,B,Aeq,beq,vlb,vub)(3)计算结果为：计算结果为：x=3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867fval=105.4626exitflag=1(4)若修改主程序若修改主程序gying2.m,取初值为上面的计算结果取初值为上面的计算结果:x0=3.00005.00000.07077.000000.9293003.929306.000010.07076.38754.39435.75117.1867得结果为得结果为:x=3.00005.00000.30947.00000.01080.6798003.690605.989210.32025.53694.91945.82917.2852fval=103.4760exitflag=1总的吨千米数比上面结果略优总的吨千米数比上面结果略优.(5)若再取刚得出的结果为初值若再取刚得出的结果为初值,却计算不出最优解却计算不出最优解.(6)若取初值为若取初值为:x0=35471000005115.63484.86877.24797.7499,则计算结果为则计算结果为:x=3.00005.00004.00007.00001.0000000005.000011.00005.69594.92857.25007.7500fval=89.8835exitflag=1总的吨千米数总的吨千米数89.8835比上面结果更好比上面结果更好.通过此例可看出通过此例可看出fmincon函数在选取初值上的重要性函数在选取初值上的重要性.思考：还有更好的解吗？（思考：还有更好的解吗？（Lingo求解）求解）