理学数学规划模型.pptx

第四章第四章 数学规划模型数学规划模型 教学目的：使学生掌握一般数学规划的模型建立和求解教学重点：数学模型的建立和求解教学难点：数学模型的建立教学内容：4.1奶制品的生产与销售4.2自来水输送与货机装运4.3汽车生产与原油采购4.4接力队选拔和选课策略4.5饮料厂的生产与检修4.6钢管和易拉罐下料y主讲:潘东云凯 里 学 院 理 学 院 数 学与应用数学专业数学建模课件第1页/共124页数学规划模型实际问题中的优化模型x决策变量f(x)目标函数gi(x)0约束条件多元函数条件极值决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析第2页/共124页企业生产计划4.1奶制品的生产与销售空间层次工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划。时间层次若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划。本节课题第3页/共124页例1加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到30元/公斤，应否改变生产计划？每天：第4页/共124页1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1x2桶牛奶生产A2获利243x1获利164 x2原料供应 劳动时间 加工能力 决策变量目标函数每天获利约束条件非负约束 线性规划模型(LP)时间480小时 至多加工100公斤A150桶牛奶每天第5页/共124页模型分析与假设比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型第6页/共124页模型求解图解法x1x20ABCDl1l2l3l4l5约束条件目标函数 Z=0Z=2400Z=3600z=c(常数)等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。第7页/共124页本教材使用软件是LINDO6.1forWindows试用版安装过程中，用户只需要按照程序给出的提示，一步一步走下去，直到安装成功为止。第一次运行刚安装的LINDO软件时，系统会弹出一个对话框，要求你输入密码（Password）。如果你买的是正版软件，请在密码框中输入LINDO公司给你提供的密码，然后按“OK”按钮即可。否则，你只能使用演示版(即试用版)，按下“DemoVersion(演示版)”按钮即可。软件实现模型求解LINDO6.1第8页/共124页本题模型为在空白的模型窗口中输入这个LP模型：max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end第9页/共124页如图：第10页/共124页LINDO程序有以下特点：程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写出目标函数表达式和约束表达式；目标函数和约束之间用“ST”分开；（或用“s.t.”，“sunjectto”）程序以“END”结束（“END”也可以省略）。系数与变量之间的乘号必须省略。系统对目标函数所在行自动生成行名“1）”,对约束默认的行名分别是“2)”“3)”，用户也可以自己输入行名；行名放在对应的约束之前。书写相当灵活，不必对齐，不区分字符的大小写。默认所有的变量都是非负的,所以不必输入非负约束。约束条件中的“=”可分别用“”代替。一行中感叹号“！”后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。第11页/共124页模型求解：用鼠标点击工具栏中的图标，或从菜单中选择Solve|Solve（Ctrl+S）命令LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所示的LINDO“求解器运行状态窗口”。第12页/共124页求解器运行状态窗口显示的相应信息及含义：名称名称含义含义Status（当前状态）显示当前求解状态：显示当前求解状态：“Optimal”表示已经达到最优表示已经达到最优解；其他可能的显示还有三个：解；其他可能的显示还有三个：Feasible(可行解可行解),Infeasible(不可行不可行),Unbounded(最优值无界最优值无界)。Iterations（迭代次数）显示迭代次数：显示迭代次数：“2”表示经过了表示经过了2次迭代。次迭代。Infeasibility（不可行性）约束不满足的量约束不满足的量(即各个约束条件不满足的即各个约束条件不满足的“数量数量”的的和；特别注意不是和；特别注意不是“不满足的约束个数不满足的约束个数”)：“0”表表示这个解是可行的。示这个解是可行的。Objective（当前的目标值）显示目标函数当前的值：显示目标函数当前的值：7.45455。Best IP（整数规划当前的最佳目标值）显示整数规划当前的最佳目标值：显示整数规划当前的最佳目标值：“N/A”（No Answer或或Not Applicable）表示无答案或无意义，因）表示无答案或无意义，因为这个模型中没有整数变量，不是整数规划（为这个模型中没有整数变量，不是整数规划（IP）。）。第13页/共124页名称名称含义含义IPBound（整数规划的界）显示整数规划的界（对最大化问题显示上界；对最小化显示整数规划的界（对最大化问题显示上界；对最小化问题，显示下界）：问题，显示下界）：“N/A”含义同上。含义同上。Branches（分枝数）显示分枝定界算法已经计算的分枝数：显示分枝定界算法已经计算的分枝数：“N/A”含义同含义同上。上。ElapsedTime（所用时间）显示计算所用时间（秒）：显示计算所用时间（秒）：“0.00”说明计算太快了，说明计算太快了，用时还不到用时还不到0.005秒。秒。UpdateInterval（刷新本界面的时间间隔）显示和控制刷新本界面的时间间隔：显示和控制刷新本界面的时间间隔：“1”表示表示1秒；用秒；用户可以直接在界面上修改这个时间间隔。户可以直接在界面上修改这个时间间隔。InterruptSolver（中断求解程序）当模型规模比较大时（尤其对整数规划），可能求解时当模型规模比较大时（尤其对整数规划），可能求解时间会很长，如果不想再等待下去时，可以在程序运行过间会很长，如果不想再等待下去时，可以在程序运行过程中用鼠标点击该按钮终止计算。求解结束后这个按钮程中用鼠标点击该按钮终止计算。求解结束后这个按钮变成了灰色，再点击就不起作用了。变成了灰色，再点击就不起作用了。Close（关闭）该按钮只是关闭状态窗口，并不终止计算。如果你关闭该按钮只是关闭状态窗口，并不终止计算。如果你关闭了状态窗口，将来随时可以选择了状态窗口，将来随时可以选择WINDOW|OPENSTATUSWINDOW菜单命令来再次打开这个窗口。菜单命令来再次打开这个窗口。第14页/共124页紧接着弹出一对话框，询问你是否需要做灵敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。第15页/共124页报告窗口 用鼠标选择“Window|ReportsWindow”（报告窗口），就可以查看该窗口的内容第16页/共124页输出结果表示的意思是：“LPOPTIMUMFOUNDATSTEP1”表示单纯形法在1次迭代（旋转）后得到最优解。“VALUE”给出最优解中各变量(VARIABLE)的值:X=20,Y=30.“OBJECTIVEFUNCTIONVALUE1)3360.000”表示最优目标值为3360.（注意：在LINDO中目标函数所在的行总是被认为是第1行，这就是这里“1）”的含义）。20桶牛奶生产A1,30桶生产A2，利润3360元。第17页/共124页结果解释OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40三种资源“资源”剩余为零的约束为紧约束（有效约束）检验数REDUCEDCOST基变量的值为0非基变量增加一个单位时目标函数减少的量第18页/共124页结果解释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元！第19页/共124页保存文件选择File|Save（F5）命令把“结果报告”保存在一个文件中（缺省的后缀名为LTX,即LINDO文本文件）类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的文件将来可以用File|Open（F3）和File|View（F4）重新打开，用前者打开的程序可以进行修改，而后者只能浏览。如果模型有错误,运行时会弹出出错信息报告窗口(LINDOErrorMessage)，则需要修改模型。运筹与优化第20页/共124页RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEF INCREASE DECREASEX1 72.000000 24.000000 8.000000X2 64.000000 8.000000 16.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHS INCREASE DECREASE2 50.000000 10.000000 6.6666673 480.000000 53.333332 80.0000004100.000000INFINITY40.000000最优解不变时目标函数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围(64,96)x2系数范围(48,72)A1获利增加到30元/千克，应否改变生产计划x1系数由24 3=72增加为30 3=90，在允许范围内不变！(约束条件不变)第21页/共124页结果解释RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHS INCREASE DECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围原料最多增加10时间最多增加5335元可买到1桶牛奶，每天最多买多少？最多买10桶!(目标函数不变)第22页/共124页例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%的波动，对计划有无影响？第23页/共124页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附加约束 第24页/共124页模型求解软件实现 LINDO6.1OBJECTIVEFUNCTIONVALUE1)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=2DORANGE(SENSITIVITY)ANALYSIS?No第25页/共124页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结果解释每天销售168千克A2和19.2千克B1，利润3460.8（元）8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1除加工能力外均为紧约束第26页/共124页结果解释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元。（大于增加时间的利润增长）第27页/共124页结果解释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计算，会发现结果有很大变化。第28页/共124页4.2自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；运输问题各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少。第29页/共124页其他费用:450元/千吨 应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？元/千吨甲乙丙丁A160130220170B140130190150C190200230/引水管理费例1自来水输送收入：900元/千吨支出A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40水库供水量(千吨)小区基本用水量(千吨)小区额外用水量(千吨)（以天计）第30页/共124页总供水量：160确定送水方案使利润最大问题分析A：50B：60C：50甲：30；50乙：70；70丙：10；20丁：10；40=30!基本需求约束6)x12+x22+x32=707)x13+x23+x33=108)x14+x24=109)x11+x21+x31=80!基本+额外需求约束10)x12+x22+x32=14011)x13+x23+x33=3012)x14+x24总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润=收入(900)其它费用(450)引水管理费利润(元/千吨)甲乙丙丁A290320230280B310320260300C260250220/供应限制B,C类似处理问题讨论确定送水方案使利润最大需求约束可以不变第35页/共124页title自来水输送问题2max290 x11+320 x12+230 x13+280 x14+310 x21+320 x22+260 x23+300 x24+260 x31+250 x32+220 x33!引水管理费subjectto2)x11+x12+x13+x14=100!供应约束3)x21+x22+x23+x24=1204)x31+x32+x33=30!基本需求约束6)x12+x22+x32=707)x13+x23+x33=108)x14+x24=109)x11+x21+x31=80!基本+额外需求约束10)x12+x22+x32=14011)x13+x23+x33=3012)x14+x24=50end模型程序第36页/共124页OBJECTIVEFUNCTIONVALUE1)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【问题求解】第37页/共124页如何装运，使本次飞行获利最大？三个货舱最大载重(吨),),最大容积(米3 3)例2 货机装运重量（吨）空间(米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡第38页/共124页决策变量xij-第i 种货物装入第j 个货舱的重量(吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓)模型假设 每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；模型建立 第39页/共124页货舱容积 目标函数(利润)约束条件货机装运模型建立 货舱重量 10；680016；87008；5300 xij-第i 种货物装入第j 个货舱的重量第40页/共124页约束条件平衡要求 货物供应 货机装运模型建立 10；680016；87008；5300 xij-第i 种货物装入第j 个货舱的重量第41页/共124页title货机装运问题max3100 x11+3100 x12+3100 x13+3800 x21+3800 x22+3800 x23+3500 x31+3500 x32+3500 x33+2850 x41+2850 x42+2850 x43subjectto2)x11+x21+x31+x41=10!货舱重量约束3)x12+x22+x32+x42=164)x13+x23+x33+x43=85)480 x11+650 x21+580 x31+390 x41=6800!货舱容积约束6)480 x12+650 x22+580 x32+390 x42=87007)480 x13+650 x23+580 x33+390 x43=53008)8x11+8x21+8x31+8x41-5x12-5x22-5x32-5x42=0!平衡要求约束9)4x11+4x21+4x31+4x41-5x13-5x23-5x33-5x43=010)x11+x12+x13=18!货物供应约束11)x21+x22+x23=1512)x31+x32+x33=2311)x41+x42+x43=12end模型程序第42页/共124页OBJECTIVEFUNCTIONVALUE1)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元货物供应点货舱需求点平衡要求运输问题运输问题的扩展第43页/共124页4.3汽车生产与原油采购例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量【问题】制订月生产计划，使工厂的利润最大。如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？小型中型大型现有量钢材（吨）1.5 35600劳动时间（小时）28025040060000利润（万元）234第44页/共124页设每月生产小、中、大型汽车的数量分别为x1,x2,x3汽车厂生产计划 模型建立小型中型大型现有量钢材1.535600时间28025040060000利润234线性规划模型(LP)第45页/共124页title汽车厂生产计划问题1max2x1+3x2+4x3!目标函数subjectto2)1.5x1+3x2+5x3600!钢材约束3)280 x1+250 x2+400 x360000!劳动时间约束end模型程序第46页/共124页模型求解3）模型中增加条件：x1,x2,x3均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.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，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？第47页/共124页IP可用LINDO直接求解整数规划(IntegerProgramming,简记IP)“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3IP的最优解x1=64，x2=168，x3=0，最优值z=632title汽车厂生产(整数规划)问题max2x1+3x2+4x3!目标函数 st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.000000-3.000000X30.000000-4.000000模型求解IP结果输出第48页/共124页其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划 若生产某类汽车，则至少生产8080辆，求生产计划。x1,x2,x3=0或 80 第49页/共124页!汽车厂生产计划问题(子模型1)max2x1+3x2+4x3subjectto2)1.5x1+3x2+5x3600!钢材约束3)280 x1+250 x2+400 x3=80endgin3!汽车厂生产计划问题(子模型2)max2x1+3x2+4x3subjectto2)1.5x1+3x2+5x3600!钢材约束3)280 x1+250 x2+400 x3=80endgin3!汽车厂生产计划问题(子模型4)max2x1+3x2+4x3subjectto2)1.5x1+3x2+5x3600!钢材约束3)280 x1+250 x2+400 x3=80!子模型4附加约束5)x3=06)x2=0endgin3!汽车厂生产计划问题(子模型5)max2x1+3x2+4x3subjectto2)1.5x1+3x2+5x3600!钢材约束3)280 x1+250 x2+400 x3=80!子模型5附加约束5)x3=06)x2=80endgin3x1=80，x2=150，x3=0，最优值z=610 x1=0，x2=0，x3=120，最优值z=480 x1=0，x2=200，x3=0，最优值z=600 x1=214，x2=0，x3=0，最优值z=428第50页/共124页!汽车厂生产计划问题(子模型5)max2x1+3x2+4x3subjectto2)1.5x1+3x2+5x3600!钢材约束3)280 x1+250 x2+400 x3=80!子模型5附加约束5)x2=06)x3=80endgin3x1=80，x2=0，x3=96，最优值z=536x1=80，x2=150，x3=0，最优值z=610其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：第51页/共124页方法2：引入0-1变量，化为整数规划M为大的正数，可取1000 若生产某类汽车，则至少生产8080辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第52页/共124页!汽车厂生产计划问题（解法2）max2x1+3x2+4x3subjectto2)1.5x1+3x2+5x3600!钢材约束3)280 x1+250 x2+400 x360000!劳动时间约束4)x1-1000y1=05)x2-1000y2=06)x3-1000y3=08)x2-80y2=07)x3-80y3=0endgin3inty1!LINDO中对0-1变量的限定inty2inty3x1=80，x2=150，x3=0，最优值z=610OBJECTIVEFUNCTIONVALUE1)610.0000VARIABLEVALUEREDUCEDCOSTX180.000000-2.000000X2150.000000-3.000000X30.000000-4.000000Y11.0000000.000000Y21.0000000.000000Y30.0000000.000000最优解为第53页/共124页NLP虽然可用现成的数学软件求解(如LINGO,MATLAB)，但是其结果常依赖于初值的选择。方法3：化为非线性规划非线性规划（Non-LinearProgramming，简记NLP）实践表明，本例仅当初值非常接近上面方法算出的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产8080辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或 80第54页/共124页应如何安排原油的采购和加工？例2 原油采购与加工 市场上可买到不超过1500吨的原油A：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，超过500吨的 部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨。售价4800元/吨售价5600元/吨库存500吨库存1000吨汽油甲(A 50%)原油A原油B汽油乙(A 60%)第55页/共124页决策变量问题分析 利润：销售汽油的收入 -购买原油A的支出 难点：原油A的购价与购买量的关系较复杂甲(A 50%)AB乙(A 60%)购买xx11x12x21x224.8千元/吨5.6千元/吨原油A的购买量,原油A,B生产汽油甲,乙的数量(1)(1)c(x)为采购的支出为采购的支出模型建立模型建立第56页/共124页设原油设原油A A的购买量为的购买量为x x（吨），根据题目所给数据，（吨），根据题目所给数据，采购的支出采购的支出c(x)c(x)可表为如下的分段线性函数（以下价格以可表为如下的分段线性函数（以下价格以千元千元/吨为单位）：吨为单位）：(1)(1)总的收入为总的收入为4.8(4.8(x x1111+x x2121)+5.6()+5.6(x x1212+x x2222)（千元）。（千元）。于是本例的目标函数（利润）为于是本例的目标函数（利润）为(2)(2)模型建立模型建立第57页/共124页包括加工两种汽油用的原油包括加工两种汽油用的原油A A、原油、原油B B库存量的限制，库存量的限制，和原油和原油A A购买量的限制，以及两种汽油含原油购买量的限制，以及两种汽油含原油A A的比的比例限制，它们表示为例限制，它们表示为（3）（4）（5）（6）（7）（8）约束条件模型建立模型建立第58页/共124页目标函数中c(x)不是线性函数，是非线性规划；对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解；想办法将模型化简，用现成的软件求解。汽油含原油A的比例限制约束条件甲(A 50%)AB乙(A 60%)x11x12x21x22（6）（7）第59页/共124页x1,x2,x3以价格10,8,6(千元/吨)采购A的吨数目标函数只有当以10千元/吨的价格购买x1=500(吨)时，才能以8千元/吨的价格购买x2方法1 由于有非线性约束(11),(12)，(3)(13)构成非线性规划模型，可以用LINGO求解模型求解c(x)=10 x1+8x2+6x3x=x1+x2+x3500吨 x 1000吨，超过500吨的8千元/吨增加约束3 3种解法种解法(9)(10)（11）(12)(13)第60页/共124页方法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.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00LINGO得到的是局部最优解，还能得到更好的解吗？用库存的500吨原油A、500吨原油B生产汽油甲，不购买新的原油A，利润为4,800千元。第61页/共124页但是此时LINGOLINGO得到的结果只是一个局部最优解可以用菜单命令“LINGO|Options”LINGO|Options”在“Global Solver”Global Solver”选项卡上启动全局优化（Use Global SolverUse Global Solver）选项，然后重新执行菜单命令“LINGO|Solve”,LINGO|Solve”,得到：Global optimal solution found.Global optimal solution found.Objective value:5000.002 Objective value:5000.002 Extended solver steps:3 Extended solver steps:3 Total solver iterations:187 Total solver iterations:187Variable Value Reduced CostX11 0.000000 0.000000X21 0.000000 0.000000X12 1500.000 0.000000X22 1000.000 0.000000X1 500.0000 0.000000X2 499.9990 0.000000X3 0.9536707E-03 0.000000X 1000.000 0.000000此时LINGOLINGO得到的结果是一个全局最优解（Global Global optimal solutionoptimal solution）：购买