数学建模线性规划课件

第四章第四章 数学规划模型数学规划模型 4.1奶制品的生产与销售奶制品的生产与销售4.2自来水输送与货机装运自来水输送与货机装运4.3汽车生产与原油采购汽车生产与原油采购4.4接力队选拔和选课策略接力队选拔和选课策略4.5饮料厂的生产与检修饮料厂的生产与检修4.6钢管和易拉罐下料钢管和易拉罐下料数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条约束条件件多元函数多元函数条件极值条件极值决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域的边界上取得的边界上取得数数学学规规划划线性规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析企业生产计划企业生产计划4.1奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划用参数等，以最小成本为目标制订生产批量计划.时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划，否则应制订多阶段生产计划.本节课题本节课题例例1加工奶制品的生产计划加工奶制品的生产计划1桶桶牛奶牛奶 3kgA1 12h 8h 4kgA2 或或获利获利24元元/kg获利获利16元元/kg50桶牛奶桶牛奶时间时间480h至多加工至多加工100kgA1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/kg，应否改变生产计划？，应否改变生产计划？每天：每天：问问题题1桶桶牛奶牛奶3kgA112h8h4kgA2或或获利获利24元元/kg获利获利16元元/kgx1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480h至多加工至多加工100kgA150桶牛奶桶牛奶每天每天基本基本模型模型模型分析与假设模型分析与假设 比比例例性性可可加加性性连续性连续性xi对目标函数的对目标函数的“贡贡献献”与与xi取值成正比取值成正比xi对约束条件的对约束条件的“贡贡献献”与与xi取值成正比取值成正比xi对目标函数的对目标函数的“贡贡献献”与与xj取值无关取值无关xi对约束条件的对约束条件的“贡贡献献”与与xj取值无关取值无关xi取值连续取值连续A1,A2每千克的获利是与各自每千克的获利是与各自产量无关的常数产量无关的常数每桶牛奶加工每桶牛奶加工A1,A2的数量的数量,时时间是与各自产量无关的常数间是与各自产量无关的常数A1,A2每千克的获利是与相互每千克的获利是与相互产量无关的常数产量无关的常数每桶牛奶加工每桶牛奶加工A1,A2的数量的数量,时时间是与相互产量无关的常数间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数线性规划模型线性规划模型模型求解模型求解 图解法图解法 x1x2OABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 z=0z=2400z=3360z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解.目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得形的某个顶点取得.模型求解模型求解 软件实现软件实现 LINGOmodel:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCost X120.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三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40结果解释结果解释 Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量影子价格影子价格35元可买到元可买到1桶牛奶，要买吗桶牛奶，要买吗?3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元?2元！元！原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长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基础上深加工基础上深加工1桶桶牛奶牛奶3kgA112h8h4kgA2或或获利获利24元元/kg获利获利16元元/kg0.8kgB12h,3元元1kg获利获利44元元/kg0.75kgB22h,3元元1kg获利获利32元元/kg制订生产计划，使每天净利润最大制订生产计划，使每天净利润最大 30元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1h时间，应否投资？现投资时间，应否投资？现投资150元，可赚回多少？元，可赚回多少？50桶牛奶桶牛奶,480h至多至多100kgA1B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？每天销售每天销售10kgA1的合同必须满足，对利润有什么影响？的合同必须满足，对利润有什么影响？1桶桶牛奶牛奶3kgA112h8h4kgA2或或获利获利24元元/kg获利获利16元元/kg0.8kgB12h,3元元1kg获利获利44元元/kg0.75kg B22h,3元元1kg获利获利32元元/kg出售出售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.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.1612=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.6810=16.8（元）（元）最优利润为最优利润为3460.816.8=3444 奶制品的生产与销售奶制品的生产与销售 由于产品利润、加工时间等均为常数，可由于产品利润、加工时间等均为常数，可建立建立线性规划线性规划模型模型.线性规划模型的三要素：线性规划模型的三要素：决策变量、目标决策变量、目标函数、约束条件函数、约束条件.用用LINGO求解，输出丰富，利用求解，输出丰富，利用影子价格影子价格和和灵敏性分析灵敏性分析可对结果做进一步研究可对结果做进一步研究.建模时尽可能利用原始的数据信息，把尽量建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做（分析例多的计算留给计算机去做（分析例2的建模）的建模）.4.2 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大怎样安排输送方案使运费最小，或利润最大?运输问题运输问题各种类型的货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少如何搭配装载，使获利最高，或装箱数量最少?其他费用其他费用:450元元/103t 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？元元/103t甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/103t支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量小小区区基基本本用用水水量量小小区区额额外外用用水水量量（以天计）（以天计）(103t)(103t)(103t)总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润=收入收入(900)其他费用其他费用(450)引水管理费引水管理费利润利润(元元/103t)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制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（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030供应点供应点需求点需求点物资物资供需平衡或不平衡供需平衡或不平衡如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(t),(t),最大容积最大容积(m(m3 3)例例2货机装运货机装运重量重量（t）空间空间(m3/t）利润利润（元（元/t）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例.前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡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(t）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误差所给出的数据都是精确的，没有误差.模型建立模型建立 货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量约束约束条件条件平衡平衡要求要求 货物货物供应供应 货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量j,k=1,2,3;jk!定义集合及变量定义集合及变量;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)w(i);for(cang(j):sum(wu(i):x(i,j)WET(j);for(cang(j):sum(wu(i):v(i)*x(i,j)VOL(j);for(cang(j):for(cang(k)|k#GT#j:!#GT#是大于等于的含义是大于等于的含义;sum(wu(i):x(i,j)/WET(j)=sum(wu(i):x(i,k)/WET(k););END货机装运货机装运LINGO程序程序 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,中仓中仓1 13；货物货物4:中仓中仓3.货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元货物货物供应点供应点货舱货舱需求点需求点装载平衡要求装载平衡要求运输运输问题问题运输问题的扩展运输问题的扩展 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1汽车厂生产计划汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量钢材、劳动时间的需求，利润及工厂每月的现有量.小型小型中型中型大型大型现有量现有量钢材（钢材（t）1.535600劳动时间（劳动时间（h）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂的利润最大制订月生产计划，使工厂的利润最大.4.3 汽车生产与原油采购汽车生产与原油采购设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性规划线性规划模型模型(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=632max=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子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=610LINGO中中对对0-1变量的限定：变量的限定：bin(y1);bin(y2);bin(y3);方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数为大的正数,本例可取本例可取1000ObjectiveValue:610.0000VariableValueReducedCostX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);方法方法3：化为非线性规划化为非线性规划非线性规划非线性规划（Non-LinearProgramming，简记简记NLP）若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划辆，求生产计划.x1=0 或 80 x2=0 或 80 x3=0 或 80最优解同前最优解同前.一般地，整数规划和非一般地，整数规划和非线性规划的求解比线性线性规划的求解比线性规划困难得多，特别是规划困难得多，特别是问题规模较大或者要求问题规模较大或者要求得到全局最优解时得到全局最优解时.汽车厂生产计划汽车厂生产计划 决策变量为整数决策变量为整数,建立建立整数规划模型整数规划模型.求解整数规划和非线性规划比线性规划求解整数规划和非线性规划比线性规划困难得多困难得多(即便用数学软件即便用数学软件).当整数变量取值很大时当整数变量取值很大时,可作为连续变量可作为连续变量处理处理,问题问题简化为线性规划简化为线性规划.对于类似于对于类似于“x=0或或 80”这样的条件，通常这样的条件，通常引入引入0-1变量变量处理，尽量不用非线性规划（特处理，尽量不用非线性规划（特别是引入的整数变量个数较少时）别是引入的整数变量个数较少时）.应如何安排原油的采购和加工应如何安排原油的采购和加工？例例2原油采购与加工原油采购与加工市场上可买到不超过市场上可买到不超过1500t t的原油的原油A：购买量不超过购买量不超过500t t时的单价为时的单价为10000元元/t/t；购买量超过购买量超过500t t但不超过但不超过1000t t时，超过时，超过500t t的的 部分部分8000元元/t/t；购买量超过购买量超过1000t t时，超过时，超过1000t t的部分的部分6000元元/t./t.售价售价4800元元/t售价售价5600元元/t库存库存500t库存库存1000t汽油甲汽油甲(A 50%)原油原油A原油原油B汽油乙汽油乙(A 60%)决策决策变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油的收入利润：销售汽油的收入 购买原油购买原油A的支出的支出.难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂.甲甲(A 50%)AB乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/t5.6千元千元/t原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？原油供应原油供应 约束约束条件条件 x 500t t单价为单价为10千千元元/t/t；500t t x 1000t t，超过，超过500t t的的8千千元元/t/t；1000t t x 1500t t，超过，超过1000t t的的6千千元元/t./t.目标目标函数函数购买购买x ABx11x12x21x22库存库存500t库存库存1000t目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软，一般的非线性规划软件也难以输入和求解；件也难以输入和求解；想办法将模型化简，用现成的软件求解想办法将模型化简，用现成的软件求解.汽油含原油汽油含原油A的比例限制的比例限制约束约束条件条件甲甲(A 50%)AB乙乙(A 60%)x11x12x21x22x1,x2,x3以价格以价格10,8,6(千元千元/t)t)采购采购A的吨数的吨数目标目标函数函数 只有当以只有当以10千元千元/t t的价格购买的价格购买x1=500(t)(t)时，才能以时，才能以8千元千元/t t的价格购买的价格购买x2方法方法1 非线性规划模型非线性规划模型，可以用，可以用LINGO求解求解模型求解模型求解x=x1+x2+x3,c(x)=10 x1+8x2+6x3 500t t x 1000t t，超过，超过500t t的的8千千元元/t/t增加约束增加约束x=x1+x2+x3,c(x)=10 x1+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+x12x+500;x21+x220;2*x12-3*x220;x=x1+x2+x3;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x30y=1与方法与方法1（全局最优解）的结果相同（全局最优解）的结果相同引入引入0-1变量变量模型求解模型求解b1b2b3b4方法方法3 b1 x b2，x=z1b1+z2b2，z1+z2=1，z1,z2 0,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000O50010001500b2 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+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)x1200090005000O50010001500b1b2b3b4对于对于k=1,2,3方法方法3:直接处理分段线性函数，方法更具一般性直接处理分段线性函数，方法更具一般性.分段函数分段函数无法直接用非线性规划方法或软件求无法直接用非线性规划方法或软件求解解.原油采购与加工原油采购与加工 方法方法1:增加约束化为增加约束化为非线性规划非线性规划,可以用可以用LINGO求解求解,但可能但可能得到的是局部最优解得到的是局部最优解.方法方法2:引入引入0-1变量变量,化为化为线性规划模型线性规划模型,可用可用LINGO求解求解.分派问题分派问题4.4 接力队选拔和选课策略接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同若干项任务分给一些候选人来完成，每人的专长不同,完成每项任务取得的效益或需要的资源不同，如何分派完成每项任务取得的效益或需要的资源不同，如何分派任务使获得的总效益最大，或付出的总资源最少任务使获得的总效益最大，或付出的总资源最少?若干种策略供选择，不同的策略得到的收益或付出的若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出抉择，使得收益最大或成本最小足一定条件下作出抉择，使得收益最大或成本最小?如何选拔队员组成如何选拔队员组成4 4 100100m混合泳接力队混合泳接力队?例例1混合泳接力队的选拔混合泳接力队的选拔5名候选人的名候选人的百米成绩百米成绩穷举法穷举法：组成接力队的方案共有组成接力队的方案共有5!=120种种.甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳讨论讨论:丁的蛙泳成绩退步到丁的蛙泳成绩退步到 ；戊的自由泳成；戊的自由泳成绩进步到绩进步到 ,组成接力队的方案是否应该调整组成接力队的方案是否应该调整？目标目标函数函数若选择队员若选择队员i参加泳姿参加泳姿j 的比赛，记的比赛，记xij=1,否则记否则记xij=0 0-1规划模型规划模型 cij(s)队员队员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人人 模型求解模型求解 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求解求解 甲甲自由泳、乙自由泳、乙蝶泳、丙蝶泳、丙仰泳、丁仰泳、丁蛙泳蛙泳.成绩为成绩为253.2(s)=甲甲乙乙丙丙丁丁戊戊蝶泳蝶泳仰泳仰泳蛙泳蛙泳自由泳自由泳丁蛙泳丁蛙泳c43=69.675.2(s)，戊自由泳，戊自由泳c54=62.457.5(s),方案是否调整？方案是否调整？敏感性分析？敏感性分析？新方案新方案:乙乙蝶泳、丙蝶泳、丙仰泳、丁仰泳、丁蛙泳、戊蛙泳、戊自由泳自由泳IP一般没有与一般没有与LP相类似的理论，相类似的理论，LINGO输出的输出的敏感性分析结果通常是没有意义的敏感性分析结果通常是没有意义的.c43,c54 的新数据重新输入模型，用的新数据重新输入模型，用LINGO求解求解 原分配方案原分配方案:甲甲自由泳、乙自由泳、乙蝶泳、丙蝶泳、丙仰泳、丁仰泳、丁蛙泳蛙泳.讨论讨论最优解：最优解：x21=x32=x43=x51=1,成绩为成绩为混合泳接力队的选拔混合泳接力队的选拔指派指派(Assignment)问题问题：有若干项任务有若干项任务,每项任务必每项任务必有且只能有一人承担，每人只能承担一项有且只能有一人承担，每人只能承担一项，不同人员，不同人员承担不同任务的效益承担不同任务的效益(或成本或成本)不同，怎样分派各项任不同，怎样分派各项任务使总效益最大务使总效益最大(或总成本最小或总成本最小)?人员数量与任务数量相等人员数量与任务数量相等人员数量大于任务数量人员数量大于任务数量(本例本例)人员数量小于任务数量人员数量小于任务数量?建立建立0-1规划模型是常用方法规划模型是常用方法为了选修课程门数最少，应学习哪些课程为了选修课程门数最少，应学习哪些课程？例例2选课策略选课策略要求至少选两门数学课、三门运筹学课和两门计算机课要求至少选两门数学课、三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求1微积分微积分5数学数学2线性代数线性代数4数学数学3最优化方法最优化方法4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数4数据结构数据结构3数学；计算机数学；计算机计算机编程计算机编程5应用统计应用统计4数学；运筹学数学；运筹学微积分；线性代数微积分；线性代数6计算机模拟计算机模拟3计算机；运筹学计算机；运筹学计算机编程计算机编程7计算机编程计算机编程2计算机计算机8预测理论预测理论2运筹学运筹学应用统计应用统计9数学实验数学实验3运筹学；计算机运筹学；计算机微积分；线性代数微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程选修课程最少，且学分尽量多，应学习哪些课程？0-1规划模型规划模型 决策变量决策变量 目标函数目标函数 xi=1选修课号选修课号i 的的课程（课程（xi=0不选）不选）选修课程总数最少选修课程总数最少约束条件约束条件最少最少2门数学课，门数学课，3门运筹学课，门运筹学课，2门计算机课门计算机课.课号课号课名课名所属类别所属类别1微积分微积分数学数学2线性代数线性代数数学数学3最优化方法最优化方法数学；运筹学数学；运筹学4数据结构数据结构数学；计算机数学；计算机5应用统计应用统计数学；运筹学数学；运筹学6计算机模拟计算机模拟计算机；运筹学计算机；运筹学7计算机编程计算机编程计算机计算机8预测理论预测理论运筹学运筹学9数学实验数学实验运筹学；计算机运筹学；计算机先修课程要求先修课程要求最优解：最优解：x1=x2=x3=x6=x7=x9=1,其他为其他为0；6门课程，总学分门课程，总学分21.0-1规划模型规划模型 约束条件约束条件x3=1必有必有x1=x2=1模型求解（模型求解（LINGO）课号课号课名课名先修课要求先修课要求1微积分微积分2线性代数线性代数3最优化方法最优化方法微积分；线性代数微积分；线性代数4数据结构数据结构计算机编程计算机编程5应用统计应用统计微积分；线性代数微积分；线性代数6计算机模拟计算机模拟计算机编程计算机编程7计算机编程计算机编程8预测理论预测理论应用统计应用统计9数学实验数学实验微积分；线性代数微积分；线性代数学分最多学分最多多目标优化的处理方法：化成单目标优化多目标优化的处理方法：化成单目标优化.两目标两目标(多目标多目标)规划规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？讨论：选修课程最少，学分尽量多，应学习哪些课程？课程最少课程最少以以学分最多为目标学分最多为目标,不管课程多少不管课程多少.以课程最少以课程最少为目标为目标,不管学分多少不管学分多少.最优解如上，最优解如上，6门门课程，总学分课程，总学分21.最优解显然是选修最优解显然是选修所有所有9门课程门课程.多目标规划多目标规划 在在课程最少的前提下课程最少的前提下以以学分最多为目标学分最多为目标.最优解：最优解：x1=x2=x3=x5=x7=x9=1,其他为其他为0；总总学分由学分由21增至增至22.注意：最优解不唯一！注意：最优解不唯一！课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 LINGO不能告诉优化不能告诉优化问题的解是否唯一问题的解是否唯一.可将可将x9=1易为易为x6=1增加约束增加约束 ，以学分最多为目标求解以学分最多为目标求解.多目标规划多目标规划 对学分数和课程数加权形成一个目标，如三七开对学分数和课程数加权形成一个目标，如三七开.最优解：最优解：x1=x2=x3=x4=x5=x6=x7=x9=1，其他为其他为0；总学分总学分28.课号课号课名课名学分学分1微积分微积分52线性代数线性代数43最优化方法最优化方法44数据结构数据结构35应用统计应用统计46计算机模拟计算机模拟37计算机编程计算机编程28预测理论预测理论29数学实验数学实验3 讨论与思考讨论与思考最优解最优解与与 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建立代理关系建立代理关系.假定公司一旦与候选代理建立代理关系，则这一假定公司一旦与候选代理建立代理关系，则这一关系将长期保持关系将长期保持 i=1,2,3,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的建模的建模约束条件约束条件业务量约束、业务中断约束、业务恢复约束业务量约束、业务中