优化模型与lindolingo软件.ppt

《优化模型与lindolingo软件.ppt》由会员分享，可在线阅读，更多相关《优化模型与lindolingo软件.ppt（58页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、优化模型与优化模型与lindolingo软件软件最优化问题简介最优化问题简介引例引例:生产计划问题生产计划问题常用优化软件常用优化软件LindoLindoLindoLindo软件应用软件应用软件应用软件应用范例范例范例范例加工奶制品的生产计划加工奶制品的生产计划加工奶制品的生产计划加工奶制品的生产计划主要内容LingoLingoLingoLingo软件应用软件应用软件应用软件应用范例范例范例范例原油采购与加工原油采购与加工原油采购与加工原油采购与加工2特点：从若干可能的计划（方案）中寻求某种意义下的最优方案，数学上将这种问题称为最优化问题（optimization).静态问题(没有考虑时间t的

2、变化)1、生产计划问题；2、运输问题；最优化问题简介3单耗 甲 乙 丙 x1 x2 x3限额材料工时工人 2 3 1 3 2 1.5 3 2 5343640利润(元/件)4 3 2在一定的条件下，问生产数量xi=？使利润达到最大？数据表生产计划问题生产计划问题规划模型利润材料工时人力4运输问题A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6

3、A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450 里程（km）目标：运费达到最小网络图5 某种原材料有M个产地，现在需要将原材料从产地运往N个工地，假定M个产地的产量为ai和N个工地的需求量为bj，单位产品的运费cij已知，那么如何安排运输方案可以使总运费最低？数学模型：cij 单位运费；xij 运输量；ai 第i 地产量；bj 第j 地需要量；状态变量返 回运输问题6建立最优化的数学模型应具备三个基本要素1、决策变量（decision variables);2、约束条件（constraints);3、目标函数（objecti

4、ve function)最优化问题分类：线性、非线性静态、动态整数、非整数随机、非随机等 返 回7优化，规划的类型 无约束优化 线性规划(LP)目标和约束均为线性函数 非线性规划(NLP)目标和约束均为非线性函数 整数规划(IP)决策变量为整数 组合优化 不确定规划 多目标规划 目标函数至少两个以上 网络优化 动态规划 研究随时间变化的决策问题 返 回8典型的工程应用问题返 回线性规划(LP)运输问题配料问题投资计划综合生产中转调用生产率比较整数规划(IP)投资选择生产计划指派问题下料问题50个决策变量以上的优化问题称为大规模的.9生产计划问题生产计划问题min cTxs.t.Axb x0归纳

5、：规划模型利润材料工时人力10数学规划中的几个概念1、可行解（可行点）2、可行域3、最优解例：Max z=3x1+x2s.t.-x1+x22 L1 x1-2x22 L2 3x1+2x214 L3 x1，x20图解图解:起作用约束：L2，L3最优解（4，1）最优值 zmax=13L3L2L111多峰函数，存在局部最大和整体最大等值线图函数曲面图形4.局部最优解5.整体最优解12建模时需要注意的几个基本问题1.尽量使用实数优化，减少整数约束和整数变量2.尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小、四舍五入、取整函数等3.尽量使用线性模型，减少非线性约

6、束和非线性变量的个数 4.合理设定变量的上下界，尽可能给出变量初始值5.模型中使用的参数数量级要恰当（小于103）返 回13常用优化软件1.LINDO/LINGO软件2.MATLAB优化工具箱3.EXCELL软件的优化功能4.SAS(统计分析）软件的优化功能14常用优化软件1.LINDO/LINGO软件2.MATLAB优化工具箱3.EXCELL软件的优化功能4.SAS(统计分析）软件的优化功能15LINDO和LINGO软件能求解的优化模型优化模型连续优化整数规划(IP)线性规划二次规划非线性规划规划LINDOLINGO16例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12

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

8、 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天18模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数

9、和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。19模型求解模型求解 软件实现软件实现 LINDO6.1max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000

10、0048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。20结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000

11、004)40.0000000.000000NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2）x1+x2503）12x1+8x24804）3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）21结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0

12、.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增量的增量原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元？2元！元！22RANGESINWHICHTHEBASISISUNCHANGED:O

13、BJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函最优解不变时目标函数系数允

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

15、2.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶，每天最多买多少桶牛奶，每天最多买

16、多少？最多买最多买10桶桶!(目标函数不变目标函数不变)24例例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元，可赚回多少

17、？元，可赚回多少？50桶牛奶桶牛奶,480小时小时至多至多100公斤公斤A1B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？251桶桶牛奶牛奶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原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量 目标目标函数函数

18、利润利润约束约束条件条件非负约束非负约束 x5千克千克A1加工加工B1，x6千克千克A2加工加工B2附加约束附加约束 26模型求解模型求解 软件实现软件实现 LINDO6.1OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.160000

19、3)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No27 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大；怎样安排输送方案使运费最小，或利润最大；运输问题运输问题各种类型的货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少

20、。如何搭配装载，使获利最高，或装箱数量最少。28其他费用其他费用:450元元/千吨千吨 应如何分配水库供水量，公司才能获利最多？应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量(千千吨吨)小小区区基基本本用用

21、水水量量(千千吨吨)小小区区额额外外用用水水量量(千千吨吨)（以天计）（以天计）29总供水量：总供水量：160确定送水方案确定送水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润=收入收入(900)其它费用其它费用(450)引水管理费引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C类似处理类似处理问题讨论问题讨论 确定送

22、水方案确定送水方案使利润最大使利润最大需求约束可以不变需求约束可以不变33求解求解OBJECTIVEFUNCTIONVALUE1)88700.00VARIABLEVALUEREDUCEDCOSTX110.00000020.000000X12100.0000000.000000X130.00000040.000000X140.00000020.000000X2130.0000000.000000X2240.0000000.000000X230.00000010.000000X2450.0000000.000000X3150.0000000.000000X320.00000020.000000X3

23、330.0000000.000000这类问题一般称为这类问题一般称为“运输问题运输问题”(TransportationProblem)总利润总利润 88700（元）（元）A(100)B(120)C(100)甲甲(30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)401005030503034如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例2货机装运货机装运重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货

24、物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例前仓：前仓：10；6800中仓：中仓：16；8700后仓：后仓：8；5300飞机平衡飞机平衡35决策决策变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；

25、多种货物可以混装，并保证不留空隙；模型建立模型建立 36货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量37约束约束条件条件平衡平衡要求要求 货物货物供应供应 货机装运货机装运模型建立模型建立 10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱的重量个货舱的重量38OBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX1

26、10.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。货机装运货机装运模型

27、求解模型求解 最大利润约最大利润约121516元元货物货物供应点供应点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题的扩展运输问题的扩展39OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.000000

28、3.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除加工能力外均除加工能力外均为紧约束为紧约束40结果解释结果解释OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.68000

29、0X2168.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元可增加元

30、可增加1小时时间，小时时间，应否投资？现投资应否投资？现投资150元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶，桶牛奶，可赚回可赚回189.6元。（大于元。（大于增加时间的利润增长）增加时间的利润增长）41结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影响RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.00

31、00008.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计算，会发现结果有很大变化。计算

32、，会发现结果有很大变化。42设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)43模型模型求解求解 3）模型中增加条件：模型中增加条件：x1,x2,x3均为整数，重新求解。均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.5161290.000000X2167.7419280

33、.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，通过比较可能得到更优的解。，通过比较可能得到更优的解。但必须检验它们是否满足约束条件。为什么？但必须检验它们是否满足约束条件。

34、为什么？44IP可用可用LINDO直接求解直接求解整数规划整数规划(IntegerProgramming,简记简记IP)“gin3”表示表示“前前3个变量个变量为整数为整数”，等价于：，等价于：ginx1ginx2ginx3IP的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin3OBJECTIVEFUNCTIONVALUE1)632.0000VARIABLEVALUEREDUCEDCOSTX164.000000-2.000000X2168.00

35、0000-3.000000X30.000000-4.000000模型求解模型求解 IP结果输出结果输出45其中其中3个个子模型应子模型应去掉，然后去掉，然后逐一求解，比较目标函数值，逐一求解，比较目标函数值，再加上整数约束，得最优解：再加上整数约束，得最优解：方法方法1：分解为：分解为8个个LP子模型子模型汽车厂生产计划汽车厂生产计划 若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1,x2,x3=0或或 80 x1=80，x2=150，x3=0，最优值，最优值z=61046LINDO中中 对对 0-1变量的限定：变量的限定：inty1inty2i

36、nty3方法方法2：引入引入0-1变量，化为整数规划变量，化为整数规划M为大的正数，为大的正数，可取可取1000OBJECTIVEFUNCTIONVALUE1)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 或

37、80最优解同前最优解同前47NLP虽虽然然可可用用现现成成的的数数学学软软件件求求解解(如如LINGO,MATLAB)，但是其结果常依赖于初值的选择。，但是其结果常依赖于初值的选择。方法方法3：化为非线性规划化为非线性规划非线性规划（非线性规划（Non-LinearProgramming，简记，简记NLP）实实践践表表明明，本本例例仅仅当当初初值值非非常常接接近近上上面面方方法法算算出出的最优解时，才能得到正确的结果。的最优解时，才能得到正确的结果。若生产某类汽车，则至少生产若生产某类汽车，则至少生产8080辆，求生产计划。辆，求生产计划。x1=0 或 80 x2=0 或 80 x3=0 或

38、8048应如何安排原油的采购和加工应如何安排原油的采购和加工？例例2原油采购与加工原油采购与加工市场上可买到不超过市场上可买到不超过1500吨的原油吨的原油A：购买量不超过购买量不超过500吨时的单价为吨时的单价为10000元元/吨；吨；购买量超过购买量超过500吨但不超过吨但不超过1000吨时，超过吨时，超过500吨的吨的 部分部分8000元元/吨；吨；购买量超过购买量超过1000吨时，超过吨时，超过1000吨的部分吨的部分6000元元/吨。吨。售价售价4800元元/吨吨售价售价5600元元/吨吨库存库存500吨吨库存库存1000吨吨汽油甲汽油甲(A 50%)原油原油A原油原油B汽油乙汽油乙

39、(A 60%)49决策决策变量变量 目标目标函数函数问题问题分析分析 利润：销售汽油的收入利润：销售汽油的收入 -购买原油购买原油A的支出的支出 难点：原油难点：原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂甲甲(A 50%)AB乙乙(A 60%)购买购买xx11x12x21x224.8千元千元/吨吨5.6千元千元/吨吨原油原油A的购买量的购买量,原油原油A,B生产生产汽油汽油甲甲,乙的数量乙的数量c(x)购买原油购买原油A的支出的支出利润利润(千元千元)c(x)如何表述？如何表述？50原油供应原油供应 约束约束条件条件 x 500吨单价为吨单价为10千千元元/吨；吨；500吨吨

40、x 1000吨，超过吨，超过500吨的吨的8千千元元/吨；吨；1000吨吨 x 1500吨，超过吨，超过1000吨的吨的6千千元元/吨。吨。目标目标函数函数购买购买x ABx11x12x21x22库存库存500吨吨库存库存1000吨吨51目标函数中目标函数中c(x)不是线性函数，是非线性规划；不是线性函数，是非线性规划；对于用分段函数定义的对于用分段函数定义的c(x)，一般的非线性规划软一般的非线性规划软件也难以输入和求解；件也难以输入和求解；想办法将模型化简，用现成的软件求解。想办法将模型化简，用现成的软件求解。汽油含原油汽油含原油A的比例限制的比例限制约束约束条件条件甲甲(A 50%)AB

41、乙乙(A 60%)x11x12x21x2252x1,x2,x3以价格以价格10,8,6(千元千元/吨吨)采购采购A的吨数的吨数目标目标函数函数 只有当以只有当以10千元千元/吨的价格购买吨的价格购买x1=500(吨吨)时，才能以时，才能以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 53方法方法1：LINGO

42、求解求解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.

43、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千千元。元。54y1,y2,y3=1以价格以价格10,8,6(千元千元/吨吨)采购采购A增增加加约约束

44、束方法方法2 0-1线性规划模型线性规划模型，可用，可用LINDO求解求解y1,y2,y3=0或或1OBJECTIVEFUNCTIONVALUE1)5000.000VARIABLE VALUE REDUCEDCOSTY11.0000000.000000Y21.0000002200.000000Y31.0000001200.000000X110.0000000.800000X210.0000000.800000X121500.0000000.000000X221000.0000000.000000X1500.0000000.000000X2500.0000000.000000X30.000000

45、0.400000X1000.0000000.000000购买购买1000吨原油吨原油A，与，与库存的库存的500吨原油吨原油A和和1000吨原油吨原油B一起，生一起，生产汽油乙，利润为产汽油乙，利润为5,000千元千元。x1,x2,x3以价格以价格10,8,6(千元千元/吨吨)采购采购A的吨数的吨数y=0 x=0 x0y=1优于方法优于方法1的结果的结果55b1b2b3b4方法方法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

46、，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)56IP模型，模型，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,357参考资料参考资料 1.谢金星，薛毅 优化建模与 LINDO/LINGO软件，清华大学出版社,20052.谢金星，优化建模与 LINDO/LINGO软件讲稿，清华清华大学数学建模网站大学数学建模网站 http:/ 58