数学建模教程——模型.pptx

《数学建模教程——模型.pptx》由会员分享，可在线阅读，更多相关《数学建模教程——模型.pptx（85页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函目标函数数gi(x)0约束条约束条件件多元函数多元函数条件极值条件极值决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域的边界上取得的边界上取得数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析第1页/共85页企业生产计划企业生产计划4.1奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件

2、，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。用参数等，以最小成本为目标制订生产批量计划。时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划。，否则应制订多阶段生产计划。本节课题本节课题第2页/共85页例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤

3、 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：第3页/共85页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利

4、243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天第4页/共85页模型分析与假设模型分析与假设 比比例例性性可可加加性性连续性连续性xi对目标函数的对目标函数的“贡献贡献”与与xi取值成取值成正比正比xi对约束条件的对约束条件的“贡献贡献”与与xi取值成取值成正比正比xi对目标函数的对目标函数的“贡献贡献”与与xj取值无取值无关关xi对约束条件的对约束条件的“贡献

5、贡献”与与xj取值无取值无关关xi取值连续取值连续A1,A2每公斤的获利是与各自产量无每公斤的获利是与各自产量无关的常数关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时间是与的数量和时间是与各自产量无关的常数各自产量无关的常数A1,A2每公斤的获利是与相互产量无每公斤的获利是与相互产量无关的常数关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量和时间是与的数量和时间是与相互产量无关的常数相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数线性规划模型线性规划模型第5页/共85页模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目

6、标函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。第6页/共85页模型求解模型求解 软件实现软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOST

7、ROWSLACKORSURPLUSDUALPRICESNO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。第7页/共85页结果解释结果解释 OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICESNO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三

8、种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）第8页/共85页结果解释结果解释 OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICES2)0.0000003)0.0000004)40.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位单位时时“效益效益”的增量的增量原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格35元可

9、买到元可买到1桶牛奶，要买吗桶牛奶，要买吗？3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元？2元！元！第9页/共85页RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEF INCREASE DECREASERIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHS INCREASE DECREASE最优解不变时目标函数系数最优解不变时目标函数系数允许变化范围允许变化范围DOR

10、ANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/千克，应否改变生产计划千克，应否改变生产计划x1系数由系数由24 3=72增加增加为为30 3=90，在，在允许范允许范围内围内不变！不变！(约束条件不变约束条件不变)第10页/共85页结果解释结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASERIGHTHANDSID

11、ERANGESROWCURRENTALLOWABLEALLOWABLERHS INCREASE DECREASE影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶，每天最多买多少桶牛奶，每天最多买多少？最多买最多买10桶桶!(目标函数不变目标函数不变)第11页/共85页例例2奶制品的生产销售计划奶制品的生产销售计划 在例在例1基础上深加工基础上深加工1桶牛桶牛奶奶3千克千克A112小时小时8小时小时4公斤公斤A2或或获利获利24元元/公斤公斤获利获利16元元/公斤公斤0.8千克千克B1

12、2小时小时,3元元1千克千克获利获利44元元/千克千克0.75千克千克B22小时小时,3元元1千克千克获利获利32元元/千克千克制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投小时时间，应否投资？现投资资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480小小时时至多至多100公斤公斤A1B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？第12页/共85页1桶牛桶牛奶奶3千克千克A112小时小时8小时小时4千克千克A2或或获利获利24元元/千克千克获利

13、获利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附加约束附加约束 第13页/共85页模型求解模型求解 软件实现软件实现 LINDO6.1OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDU

14、CEDCOSTROWSLACKORSURPLUSDUALPRICESNO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No第14页/共85页OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICESNO.ITERATIONS=2结果解释结果解释每天销售每天销售168千克千克A2和和19.2千克千克B1，利润（元）利润（元）8桶牛奶加工成桶牛奶加工成A1，42桶牛奶加桶牛奶加工成工成A2，将得到的将得到的24千克千克A1全部加工成全部加工成B1除加工能力外均为紧除加工能力

15、外均为紧约束约束第15页/共85页结果解释结果解释OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICES2)0.0000003)0.000000增加增加1桶牛奶使利润增长桶牛奶使利润增长增加增加1小时时间使利润增长小时时间使利润增长3.2630元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，应否投资？现小时时间，应否投资？现投资投资150元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶，可赚回桶牛奶，可赚回元。（大于增加时间的利润增长）元。（大于增加时间的利润增长）第1

16、6页/共85页结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX6-3.0000001.520000INFINITYDORAN

17、GE(SENSITIVITY)ANALYSIS?YesB1获利下降获利下降10%，超出，超出X3系数允许范围系数允许范围B2获利上升获利上升10%，超出，超出X4系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为计算，会发现结果有的系数改为计算，会发现结果有很大变化。很大变化。第17页/共85页 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；怎样安排输送方案使运费最小，或利润最大；运输问题运输问题各种类型的

18、货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。如何搭配装载，使获利最高，或装箱数量最少。第18页/共85页其他费用其他费用:450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60

19、C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量(千千吨吨)小小区区基基本本用用水水量量(千千吨吨)小小区区额额外外用用水水量量(千千吨吨)（以天计）（以天计）第19页/共85页总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润=收入收入(900)其它费用其它费用(450)引水管理引水管理费费利润利润(元元/千吨千吨)甲甲乙

20、乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变需求约束可以不变第23页/共85页求解求解OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTX21X22X23X24X31X330.000000这类问题一般称为这类问题一般称为“运输问题运输问题”(TransportationProblem)总利润总利润 88700（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(1

21、0;20)丁丁(10;40)4010050305030第24页/共85页如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例2 货机装货机装运运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡第25页/共

22、85页决策决策变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后分别代表前、中、后仓仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙；模型建立模型建立 第26页/共85页货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；53

23、00 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第27页/共85页约束约束条件条件平衡平衡要求要求 货物货物供应供应 货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量第28页/共85页OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTX32X33X430.000000650.000000货物货物2：前仓：前仓10,后仓后仓5；货物货物3:中仓中仓13,后仓后仓3；货物货物4:中仓中仓3。货机装运货机装运模型求解模型求解 最大利润约最

24、大利润约121516元元货物货物供应点供应点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题的扩展运输问题的扩展第29页/共85页 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1 汽车厂生产计汽车厂生产计划划 汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。材、劳动时间的需求，利润及工厂每月的现有量。小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时

25、间（小时）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。汽车生产与原油采购汽车生产与原油采购第30页/共85页设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有现有量量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)第31页/共85页模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。

26、OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTROWSLACKORSURPLUSDUALPRICES结果为小数，结果为小数，怎么办？怎么办？1）舍去小数：取）舍去小数：取x1=64，x2=167，算出目标函数值，算出目标函数值z=629，与，与LP最优值相差不最优值相差不大。大。2）试试探探：如如取取x1=65，x2=167；x1=64，x2=168等等，计计算算函函数数值值z，通通过过比比较较可可能得到更优的解。能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。为什么？第32页/共85页IP可用可用LINDO

27、直接求解直接求解整数规划整数规划(IntegerProgramming,简记简记IP)“gin3”表示表示“前前3个变量为整数个变量为整数”，等价于：，等价于：ginx1ginx2ginx3IP的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin3OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTX30.000000-4.000000模型求解模型求解 IP结果输出结果输出第33页/共85页其中其中3个个子

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

29、OBJECTIVEFUNCTIONVALUEVARIABLEVALUEREDUCEDCOSTY30.0000000.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前第35页/共85页NLP虽虽然然可可用用现现成成的的数数学学软软件件求求解解(如如LINGO,MATLAB)，但是其结果常依赖于初值的选择。，但是其结果常依赖于初值的选择。方法方法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记，简记NLP）实

30、实践践表表明明，本本例例仅仅当当初初值值非非常常接接近近上上面面方方法法算算出出的最优解时，才能得到正确的结果。的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第36页/共85页应如何安排原油的采购和加工应如何安排原油的采购和加工？例例2 原油采购与加原油采购与加工工 市场上可买到不超过市场上可买到不超过1500吨的原油吨的原油A：购买量不超过购买量不超过500吨时的单价为吨时的单价为10000元元/吨；吨；购买量超过购买量超过500吨但不超过吨但不超过1000

31、吨时，超过吨时，超过500吨的吨的 部分部分8000元元/吨；吨；购买量超过购买量超过1000吨时，超过吨时，超过1000吨的部分吨的部分6000元元/吨。吨。售价售价4800元元/吨吨售价售价5600元元/吨吨库存库存500吨吨库存库存1000吨吨汽油甲汽油甲(A 50%)原油原油A原油原油B汽油乙汽油乙(A 60%)第37页/共85页决策决策变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油的收入利润：销售汽油的收入 -购买原油购买原油A的支出的支出 难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂甲甲(A 50%)AB乙乙(A 60%)购买购买xx11x

32、12x21x224.8千元千元/吨吨5.6千元千元/吨吨原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支的支出出利润利润(千元千元)c(x)如何表述？如何表述？第38页/共85页原油供应原油供应 约束约束条件条件 x 500吨单价为吨单价为10千千元元/吨；吨；500吨吨 x 1000吨，超过吨，超过500吨的吨的8千千元元/吨；吨；1000吨吨 x 1500吨，超过吨，超过1000吨的吨的6千千元元/吨。吨。目标目标函数函数购买购买x ABx11x12x21x22库存库存500吨吨库存库存1000吨吨第39页/共85页目标函数中目

33、标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软，一般的非线性规划软件也难以输入和求解；件也难以输入和求解；想办法将模型化简，用现成的软件求解。想办法将模型化简，用现成的软件求解。汽油含原油汽油含原油A的比例限制的比例限制约束约束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22第40页/共85页x1,x2,x3以价格以价格10,8,6(千元千元/吨吨)采购采购A的吨的吨数数目标目标函数函数 只有当以只有当以10千元千元/吨的价格购买吨的价格购买x1=500(吨吨)时，才能以时，才

34、能以8千元千元/吨的价格购买吨的价格购买x2方法方法1 非线性规划模型非线性规划模型，可以用，可以用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500吨吨 x 1000吨，超过吨，超过500吨的吨的8千千元元/吨吨增加约束增加约束x=x1+x2+x3,c(x)=10 x1+8x2+6x3 第41页/共85页方法方法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;(x

35、1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x30;x110;x120;x210;x220;x10;x20;x30;endVariableValueReducedCost0.0000000E+000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X0.0000000E+000.0000000E+00LINGO得到的是局部最优解，还能得到更好得到的是局部最优解，还能得到更好的解吗？的解吗？用库存的用库存的500吨原油吨原油A、500吨原油吨原油B生产汽油甲生产汽油甲，不购买

36、新的原油，不购买新的原油A，利润为，利润为4,800千千元。元。第42页/共85页y1,y2,y3=1以价格以价格10,8,6(千元千元/吨吨)采购采购A增增加加约约束束方法方法2 0-1线性规划模型线性规划模型，可用，可用LINDO求解求解y1,y2,y3=0或或1OBJECTIVEFUNCTIONVALUEVARIABLE VALUE REDUCEDCOSTX1X2X0.000000购买购买1000吨原油吨原油A，与库存的，与库存的500吨原油吨原油A和和1000吨原油吨原油B一一起，生产汽油乙，利润为起，生产汽油乙，利润为5,000千元千元。x1,x2,x3以价格以价格10,8,6(千元

37、千元/吨吨)采购采购A的吨的吨数数y=0 x=0 x0y=1优于方法优于方法1的结果的结果第43页/共85页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)第44

38、页/共85页IP模型，模型，LINDO求解，得求解，得到的结果与方法到的结果与方法2相同相同.处理分段线性函数，方法处理分段线性函数，方法3更具一般性更具一般性bk 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第45页/共85页分派问题分派问题 接力队选拔和选课策略接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同，若干项任务分给一些

39、候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。足一定条件下作出决择，使得收益最大或成本最小。第46页/共85页丁的蛙泳成绩退步到丁的蛙泳成绩退步到115”2；戊的自由泳成绩进；戊的自由泳成绩进步到步

40、到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种种。第47页/共85页目标目标函数函数若选择队员若选择队员i参

41、加泳姿参加泳姿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人人 第48页/共85页模型求解模型求解 最最优优解解：x14=x21=x32=x43=1,其它变量为其它变量为0;成绩为成绩为(秒秒)=413”

42、2+SUBJECTTOx11+x12+x13+x14=1x41+x42+x43+x44=1x11+x21+x31+x41+x51=1x14+x24+x34+x44+x54=1ENDINT20输入输入LINDO求解求解 甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳106”857”2118”110”107”4仰泳仰泳115”6106”107”8114”2111”蛙泳蛙泳127”106”4124”6109”6123”8自由泳自由泳58”653”59”457”2102”4甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.第49页/共85页丁蛙泳丁蛙泳c43=，戊自由泳，戊自由泳c54=62.4,方案方

43、案是否调整？是否调整？敏感性分析？敏感性分析？乙乙蝶泳、丙蝶泳、丙仰泳、仰泳、丁丁蛙泳、戊蛙泳、戊自由泳自由泳IP规划一般没有与规划一般没有与LP规划相类似的理论，规划相类似的理论，LINDO输输出的敏感性分析结果通常是没有意义的。出的敏感性分析结果通常是没有意义的。最优解：最优解：x21=x32=x43=x51=1,成绩为成绩为417”7c43,c54 的新数据重新输入模型，用的新数据重新输入模型，用LINDO求解求解 指派指派(Assignment)问题问题：每项任务有且只有一人承担，每项任务有且只有一人承担，每人只能承担一项每人只能承担一项，效益不同，怎样分派使总效益最大，效益不同，怎样

44、分派使总效益最大.讨论讨论甲甲自由泳、乙自由泳、乙蝶泳、蝶泳、丙丙仰泳、丁仰泳、丁蛙泳蛙泳.原原方方案案第50页/共85页为了选修课程门数最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程？例例2 选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分5数学数学2线性代数线性代数4数学数学3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；

45、运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程选修课程最少，且学分尽量多，应学习哪些课程？第51页/共85页0-1规划模型规划模型 决策变量决策变量 目标函数目标函数 xi=1选修课号选修课号i 的的课程（课程（xi=0不选）不选）选修课程总数最少选修课程总数最少约束条件约束条件最少最少2门数学课，门数学课，3门运筹

46、学课，门运筹学课，2门计算机课。门计算机课。课号课号课名课名所属类别所属类别1微积分微积分数学数学2线性代数线性代数数学数学3最优化方法最优化方法数学；运筹学数学；运筹学4数据结构数据结构数学；计算机数学；计算机5应用统计应用统计数学；运筹学数学；运筹学6计算机模拟计算机模拟计算机；运筹学计算机；运筹学7计算机编程计算机编程计算机计算机8预测理论预测理论运筹学运筹学9数学实验数学实验运筹学；计算机运筹学；计算机第52页/共85页先修课程要求先修课程要求最优解：最优解：x1=x2=x3=x6=x7=x9=1,其它为其它为0；6门课程，总学分门课程，总学分210-1规划模型规划模型 约束条件约束条

47、件x3=1必有必有x1=x2=1模型求解（模型求解（LINDO）课号课号课名课名先修课要求先修课要求1微积分微积分2线性代数线性代数3最优化方法最优化方法微积分；线性代数微积分；线性代数4数据结构数据结构计算机编程计算机编程5应用统计应用统计微积分；线性代数微积分；线性代数6计算机模拟计算机模拟计算机编程计算机编程7计算机编程计算机编程8预测理论预测理论应用统计应用统计9数学实验数学实验微积分；线性代数微积分；线性代数第53页/共85页学分最多学分最多多目标优化的处理方法：化成单目标优化。多目标优化的处理方法：化成单目标优化。两目标两目标(多目标多目标)规划规划 讨论：选修课程最少，学分尽量多

48、，应学习哪些课程？讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少课程最少以以学分最多为目标，不管课程学分最多为目标，不管课程多少。多少。以课程最少以课程最少为目标，不管学分为目标，不管学分多少。多少。最优解如上，最优解如上，6门课程，总门课程，总学分学分21。最优解显然是选修所有最优解显然是选修所有9门门课程课程。第54页/共85页多目标规划多目标规划 在在课程最少的前提下课程最少的前提下以以学分最多为目标。学分最多为目标。最优解：最优解：x1=x2=x3=x5=x7=x9=1,其它为其它为0；总学分由总学分由21增至增至22。注意：最优解不唯一！注意：最优解不唯一！课号课号课名课名

49、学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 LINDO无法告诉优化无法告诉优化问题的解是否唯一。问题的解是否唯一。可将可将x9=1易为易为x6=1增加约束增加约束 ，以学分最多为目标求解。以学分最多为目标求解。第55页/共85页多目标规划多目标规划 对学分数和课程数加权形成一个目标，如三七开。对学分数和课程数加权形成一个目标，如三七开。最优解：最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其它为其它为0；总学分总学分28。课号课

50、号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 第56页/共85页讨论与思考讨论与思考最优解最优解与与 1=0，2=1的结果相同的结果相同学分最多学分最多多目标规划多目标规划 最优解最优解与与 1=1，2=0的结果相同的结果相同课程最少课程最少第57页/共85页 饮料厂的生产与检修饮料厂的生产与检修单阶段生产计划单阶段生产计划多阶段生产计划多阶段生产计划生产批量问题生产批量问题企业生产计划企业生产计划考虑与产量无关的固定费用考虑与产量无