《数学模型(第四版)课件-第四章.ppt》由会员分享，可在线阅读，更多相关《数学模型(第四版)课件-第四章.ppt（122页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 数学规划模型数学规划模型 4.1奶制品的生产与销售奶制品的生产与销售4.2自来水输送与货机装运自来水输送与货机装运4.3汽车生产与原油采购汽车生产与原油采购4.4接力队选拔和选课策略接力队选拔和选课策略4.5饮料厂的生产与检修饮料厂的生产与检修4.6钢管和易拉罐下料钢管和易拉罐下料数学规划模型数学规划模型 实际问题中实际问题中的优化模型的优化模型x决策变量决策变量f(x)目标函数目标函数gi(x)0约束条约束条件件多元函数多元函数条件极值条件极值决策变量个数决策变量个数n和和约束条件个数约束条件个数m较大较大最优解在可行域最优解在可行域的边界上取得的边界上取得数数学学规规划划线性
2、规划线性规划非线性规划非线性规划整数规划整数规划重点在模型的建立和结果的分析重点在模型的建立和结果的分析优化模型与优化软件的重要意义(最最)优化优化:在一定条件下在一定条件下,寻求使目标最大寻求使目标最大(小小)的决策的决策 最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:结构设计 资源分配 生产计划 运输方案解决优化问题的手段解决优化问题的手段 经验积累，主观判断 作试验，比优劣 建立数学模型(优化模型)，求最优策略(决策)(最最)优化优化:在一定条件下在一定条件下,寻求使目标最大寻求使目标最大(小小)的决策的决策CUMCM赛题：约一半以上与优化有关，需用软件求解。(最)
3、优化理论是运筹学的基本内容运筹学(OR:Operations/OperationalResearch)管理科学(MS:ManagementScience)决策科学(DS:DecisionScience)优化(Optimization),规划(Programming)无无约约束束优优化化线线性性规规划划非非线线性性规规划划网网络络优优化化组组合合优优化化整整数数规规划划不不确确定定规规划划多多目目标标规规划划目目标标规规划划动动态态规规划划OR/MS/DS优化问题的一般形式优化问题三要素：决策变量；目标函数；约束决策变量；目标函数；约束条件条件可行解（满足约束）与可行域（可行解的集合）最优解（取
4、到最小大值的可行解）约约束束条条件件目标函数目标函数决策变量决策变量给定一个函数给定一个函数 f(x),),寻找寻找 x*使得使得 f(x*)最小，即最小，即其中其中局部最优解局部最优解全局最优解全局最优解必要条件必要条件x*f(x)xlxgo充分条件充分条件Hessian阵阵最优解在可行域边界上取得时不能用无约束优化方法求解最优解在可行域边界上取得时不能用无约束优化方法求解无约束优化:最优解的分类和条件约束优化的简单分类线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)
5、目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全部或部分全部或部分)为整数为整数整数线性规划整数线性规划(ILP)，整数非线性规划，整数非线性规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划数学规划数学规划连连续续优优化化离离散散优优化化常用优化软件1.LINDO/LINGO软件软件2.MATLAB优化工具箱优化工具箱3.EXCEL软件的优化功能软件的优化功能4.SAS(统计分析统计分析)软件的优化功能软件的优化功能5.其他其他MATLAB优化工具箱能求解
6、的优化模型The toolbox includes routines for many types of optimization including:Unconstrained nonlinear minimization Constrained nonlinear minimization,including goal attainment problems,minimax problems,and semi-infinite minimization problems Quadratic and linear programmingNonlinear least squares and
7、curve-fitting Nonlinear system of equation solving Constrained linear least squares Sparse and structured large-scale problemsMATLAB优化工具箱能求解的优化模型优化工具箱优化工具箱3.0(MATLAB7.0R14)连续优化连续优化离散优化离散优化无约束优化无约束优化非线性非线性极小极小fminunc非光滑非光滑(不可不可微微)优化优化fminsearch非线性非线性方方程程(组组)fzerofsolve全局全局优化优化暂缺暂缺非线性非线性最小二乘最小二乘lsqnon
8、linlsqcurvefit线性规划线性规划linprog纯纯0-1规划规划bintprog一般一般IP(暂缺暂缺)非线性规划非线性规划fminconfminimaxfgoalattainfseminf上下界约束上下界约束fminbndfminconlsqnonlinlsqcurvefit约束线性约束线性最小二乘最小二乘lsqnonneglsqlin约束优化约束优化二次规划二次规划quadprogLINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发,后来成立LINDO系统公司（LINDO Systems Inc.）网址：LIND
9、O:Linear INteractive and Discrete Optimizer(V6.1)LINGO:Linear INteractive General Optimizer(V9.0)LINDO API:LINDO Application Programming Interface(V2.0)Whats Best!:(SpreadSheet e.g.EXCEL)(V7.0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版求解问题规模和选件不同LINDO API使用LINDO API可以建立求最佳解的应用程序。LINDO API允许你将强大的线性、整数或非线性求解引擎挂入你已写好
10、的应用程序中。迅速、容易的应用程序开发迅速、容易的应用程序开发LINDO API 可以使你容易地将最佳化的功能整合到你自己开发的应用程序中。LINDO API 附有完整的文件和范例帮助您迅速上手。强大的求解引擎强大的求解引擎LINDO API 提供的强大求解引擎包括针对线性、非线性(convex和nonconvex)，二次和整数的最佳化。完整的求解程序完整的求解程序LINDO API 提供了你需要的弹性和功能，不管你的应用程序是大或小，简单或复杂。它包含了数十个程序(routine)来公式化、求解、查询和修改你的问题。分析不可实行和无边际模型分析不可实行和无边际模型(Infeasible an
11、d Unbounded Models)LINDO API 内含工具可以找出导致模型无合理解或无边际模型的原因。建立因特网和企业内部网络的应用程序建立因特网和企业内部网络的应用程序LINDO API 允许你建立因特网和企业内部网络的应用程序可同时供多人使用LINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)连续优化连续优化整数规划整数规划(IP)LINDO/LINGO软件的求解过程LPQPNLPIP全局优化全局优化(选选)ILPIQPINLPLINDO/LINGO预处理程序预处理程序线性优化求
12、解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1.确定常数确定常数2.识别类型识别类型1.单纯形算法单纯形算法2.内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP)2、广义既约梯度法、广义既约梯度法(GRG)(选选)3、多点搜索、多点搜索(Multistart)(选选)建模时需要注意的几个基本问题1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y 5改为x5
13、y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103)需要掌握的几个重要方面1、LINDO:正确阅读求解报告（尤其要掌握敏感性分析）2、LINGO：掌握集合(SETS)的应用；正确阅读求解报告；正确理解求解状态窗口；学会设置基本的求解选项(OPTIONS)；掌握与外部文件的基本接口方法DIFFERENCE BETWEEN LINGO AND LINDOLINDO 用于求解线性规划和二次规划LINGO 还可用于非线性规划求解，一些线性和非线性方程组的求解。LINDO不提供数组或类似的数据结构。LINGO包含内置的建模语言，允许以简练、直观的方式描述较大规
14、模的优化问题，模型中所需要的数据可以以一定格式保存在独立的文件中。文件类型描述.lg4 LINGO格式的模型文件 二进制格式文件.lng 文本格式的模型文件（不保存字体、颜色、嵌入对象）.ldt LINGO数据文件.ltf LINGO命令脚本文件.lgr LINGO报告文件.ltx LINDO格式的模型文件.mps 数学规划系统格式的模型文件状态窗口Model Class:LP,QP,ILP,IQ,PILP,PIQP,NLP,INLP,PINLPState:Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupte
15、d UndeterminedSolver Type:B-and-B 分支定界 Global 全局最优 Multistart 多个初始点LINGO软件简介LINGO模型的优点模型的优点 包含了LINDO的全部功能 提供了灵活的编程语言（矩阵生成器）LINGO模型的构成：模型的构成：5个段个段 目标与约束段 集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）计算段(CALCENDCALC)-LINGO9.0企业生产计划企业生产计划4.1奶制品的生产与销售奶制品的生产与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求
16、和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划用参数等，以最小成本为目标制订生产批量计划.时间层次时间层次若短时间内外部需求和内部资源等不随时间变化，可若短时间内外部需求和内部资源等不随时间变化，可制订制订单阶段生产计划单阶段生产计划，否则应制订多阶段生产计划，否则应制订多阶段生产计划.本节课题本节课题例例1加工奶制品的生产计划加工奶制品的生产计划1桶桶牛奶牛奶 3公斤公斤A1 12小时小时 8小时小时 4公
17、斤公斤A2 或或获利获利24元元/公斤公斤获利获利16元元/公斤公斤50桶牛奶桶牛奶时间时间480小时小时 至多加工至多加工100公斤公斤A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/公斤，应否改变生产计划？公斤，应否改变生产计划？每天：每天：问问题题1桶桶牛奶牛奶3公斤公斤A112小时小时8小时小时4公斤公斤A2或或获利获利24元元/公斤公斤获利获利16元元/公斤
18、公斤x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2获利获利243x1获利获利164 x2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A150桶牛奶桶牛奶每天每天基本基本模型模型模型分析与假设模型分析与假设 比比例例性性可可加加性性连续性连续性xi对目标函数的对目标函数的“贡贡献献”与与xi取值成正比取值成正比xi对约束条件的对约束条件的“贡贡献献”与与xi取值成正比取值成正比xi对目标函数的对目标函数的“
19、贡贡献献”与与xj取值无关取值无关xi对约束条件的对约束条件的“贡贡献献”与与xj取值无关取值无关xi取值连续取值连续A1,A2每公斤的获利是与各自每公斤的获利是与各自产量无关的常数产量无关的常数每桶牛奶加工每桶牛奶加工A1,A2的数量的数量,时时间是与各自产量无关的常数间是与各自产量无关的常数A1,A2每公斤的获利是与相互每公斤的获利是与相互产量无关的常数产量无关的常数每桶牛奶加工每桶牛奶加工A1,A2的数量的数量,时时间是与相互产量无关的常数间是与相互产量无关的常数加工加工A1,A2的牛奶桶数是实数的牛奶桶数是实数线性规划模型线性规划模型模型求解模型求解 图解法图解法 x1x20ABCDl
20、1l2l3l4l5约约束束条条件件目标目标函数函数 Z=0Z=2400Z=3600z=c(常数常数)等值线等值线c在在B(20,30)点得到最优解点得到最优解目标函数和约束条件是线性函数目标函数和约束条件是线性函数可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形目标函数的等值线为直线目标函数的等值线为直线最优解一定在凸多边最优解一定在凸多边形的某个顶点取得。形的某个顶点取得。模型求解模型求解 软件实现软件实现 LINGOmodel:max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct3*x1100;end Globaloptimalsol
21、utionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCost X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000 20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。结果解释结果解释 Globaloptimalsolutionfound.Obj
22、ectivevalue: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三三种种资资源源“资源资源”剩余为零的约束为紧约束（
23、有效约束）剩余为零的约束为紧约束（有效约束）原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40结果解释结果解释 Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2VariableValueReducedCostX120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.00000
24、0最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量影子价格影子价格35元可买到元可买到1桶牛奶，要买吗桶牛奶，要买吗?3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元聘用临时工人付出的工资最多每小时几元?2元！元！原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientI
25、ncreaseDecreaseX172.0000024.000008.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000 最优解不变时目标函最优解不变时目标函数系数允许变化范围数系数允许变化范围Options-GeneralSolver-DualComputations敏感性分析敏感性
26、分析(“LINGO|Ranges”)x1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/公斤，应否改变生产计划公斤，应否改变生产计划?x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内不变！不变！(约束条件不变约束条件不变)结果解释结果解释 Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX172.0000024.000008
27、.000000X264.000008.00000016.00000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseMILK50.0000010.000006.666667TIME480.000053.3333380.00000CPCT100.0000INFINITY40.00000影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶桶牛奶,每天最多买多少每天最多买多少?最多买最多买10桶桶!(目标函数不变
28、目标函数不变)充分条件充分条件!例例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桶牛奶
29、桶牛奶,480小时小时至多至多100公斤公斤A1B1，B2的获利经常有的获利经常有10%的波动，对计划有无影响？的波动，对计划有无影响？每天销售每天销售10公斤公斤A1的合同必须满足，对利润有什么影响？的合同必须满足，对利润有什么影响？1桶桶牛奶牛奶3kgA112小时小时8小时小时4kgA2或或获利获利24元元/kg获利获利16元元/kg0.8kg B12小时小时,3元元1kg获利获利44元元/kg0.75kg B22小时小时,3元元1kg获利获利32元元/kg出售出售x1kgA1,x2kgA2，x3kgB1,x4kgB2原料原料供应供应 劳动劳动时间时间 加工能力加工能力 决策决策变量变量
30、目标目标函数函数 利润利润约束约束条件条件非负约束非负约束 x5kgA1加工加工B1，x6kgA2加工加工B2附加约束附加约束 基本模型基本模型模型求解模型求解 软件实现软件实现 LINGO Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.52000
31、0RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000
32、.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除加工能力外除加工能力
33、外均为紧约束均为紧约束结果解释结果解释Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003
34、.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000增加增加1桶牛奶使利润桶牛奶使利润增长增长3.1612=37.92增加增加1小时时间使小时时间使利润增长利润增长3.2630元可增加元可增加1桶牛奶，桶牛奶，3元可增加元可增加1小时时间，小时时间，应否投资？现投资应否投资？现投资150元，可赚回多少？元，可赚回多少？投资投资150元增加元增加5桶牛奶桶牛奶,可赚回可赚回189.6元。元。(大于大于增加时间的利润增长增加时间的利润增长)结果解释结果解释B1,B2的获利有的获利有10%的波动，对计划有无影响的波动，对计划有无影
35、响Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY敏感性分析敏感性分析 B1获利下
36、降获利下降10%，超，超出出X3系数允许范围系数允许范围B2获利上升获利上升10%，超，超出出X4系数允许范围系数允许范围波动对计划有影响波动对计划有影响生产计划应重新制订：如将生产计划应重新制订：如将x3的系数改为的系数改为39.6计算，计算，会发现结果有很大变化。会发现结果有很大变化。Globaloptimalsolutionfound.Objectivevalue:3460.800Totalsolveriterations:2VariableValueReducedCostX10.0000001.680000X2168.00000.000000X319.200000.000000X40.
37、0000000.000000X524.000000.000000X60.0000001.520000RowSlackorSurplusDualPrice13460.8001.000000MILK0.0000003.160000TIME0.0000003.260000CPCT76.000000.00000050.00000044.0000060.00000032.00000结果解释结果解释x1从从0开始增加一个单开始增加一个单位时，最优目标函数位时，最优目标函数值将减少值将减少1.68ReducedCost有意义有意义也是有条件的也是有条件的(LINGO没有给出没有给出)每天销售每天销售10公斤
38、公斤A1的合同必须满足，的合同必须满足，对利润有什么影响？对利润有什么影响？公司利润减少公司利润减少1.6810=16.8（元）（元）最优利润为最优利润为3460.816.8=3444 奶制品的生产与销售奶制品的生产与销售 由于产品利润、加工时间等均为常数，可由于产品利润、加工时间等均为常数，可建立建立线性规划线性规划模型模型.线性规划模型的三要素：线性规划模型的三要素：决策变量、目标决策变量、目标函数、约束条件函数、约束条件.用用LINGO求解，输出丰富，利用求解，输出丰富，利用影子价格影子价格和和灵敏性分析灵敏性分析可对结果做进一步研究可对结果做进一步研究.建模时尽可能利用原始的数据信息，
39、把尽量建模时尽可能利用原始的数据信息，把尽量多的计算留给计算机去做（分析例多的计算留给计算机去做（分析例2的建模）的建模）.4.2 自来水输送与货机装运自来水输送与货机装运生产、生活物资从若干供应点运送到一些需求点，生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费最小，或利润最大怎样安排输送方案使运费最小，或利润最大?运输问题运输问题各种类型的货物装箱，由于受体积、重量等限制，各种类型的货物装箱，由于受体积、重量等限制，如何搭配装载，使获利最高，或装箱数量最少如何搭配装载，使获利最高，或装箱数量最少?其他费用其他费用:450元元/千吨千吨 应如何分配水库供水量，公司才能获利最
40、多？应如何分配水库供水量，公司才能获利最多？若水库供水量都提高一倍，公司利润可增加到多少？若水库供水量都提高一倍，公司利润可增加到多少？元元/千吨千吨甲甲乙乙丙丙丁丁A160130220170B140130190150C190200230/引水管理费引水管理费例例1 自来水输送自来水输送收入：收入：900元元/千吨千吨支出支出A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40水水库库供供水水量量(千千吨吨)小小区区基基本本用用水水量量(千千吨吨)小小区区额额外外用用水水量量(千千吨吨)（以天计）（以天计）总供水量：总供水量：160确定送水方案确定送
41、水方案使利润最大使利润最大问题问题分析分析A：50B：60C：50甲：甲：30；50乙：乙：70；70丙：丙：10；20丁：丁：10；40总需求量总需求量(300)每个水库最大供水量都提高一倍每个水库最大供水量都提高一倍利润利润=收入收入(900)其它费用其它费用(450)引水管理费引水管理费利润利润(元元/千吨千吨)甲甲乙乙丙丙丁丁A290320230280B310320260300C260250220/供应供应限制限制B,C类似处理类似处理问题讨论问题讨论 确定送水方案确定送水方案使利润最大使利润最大需求约束可以不变需求约束可以不变求解求解部分结果：部分结果：ObjectiveValue:
42、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)甲甲(
43、30;50)乙乙(70;70)丙丙(10;20)丁丁(10;40)4010050305030供应点供应点需求点需求点物资物资供需平衡或不平衡供需平衡或不平衡如何如何装运，装运，使本次飞行使本次飞行获利最大？获利最大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)例例2货机装运货机装运重量重量（吨）（吨）空间空间(米米3/吨）吨）利润利润（元（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成比例重成比例.前仓：前仓：10；6
44、800中仓：中仓：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 个货舱的重量个货舱的重
45、量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物可以分割到任意小；每种货物可以分割到任意小；货机装运货机装运每种货物可以在一个或多个货舱中任意分布；每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误差所给出的数据都是精确的，没有误差.模型建立模型建立 货舱货舱容积容积 目标目标函数函数(利润利润)约束约束条件条件货机装运货机装运模型建立模型建立 货舱货舱重量重量 10；680016；87008；5300 xij-第第i 种货物装入第种货物装
46、入第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,35
47、00,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程序程序 Globaloptimalso
48、lutionfound.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.0
49、000X(4,2)3.0526320.000000X(4,3)0.000000650.0000货物货物2：前仓：前仓7,后仓后仓8；货物货物3:前仓前仓3,中仓中仓1 13；货物货物4:中仓中仓3。货机装运货机装运模型求解模型求解 最大利润约最大利润约121516元元货物货物供应点供应点货舱货舱需求点需求点装载平衡要求装载平衡要求运输运输问题问题运输问题的扩展运输问题的扩展 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆，那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例1汽车厂生产计划汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对
50、汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量钢材、劳动时间的需求，利润及工厂每月的现有量.小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234制订月生产计划，使工厂的利润最大制订月生产计划，使工厂的利润最大.4.3 汽车生产与原油采购汽车生产与原油采购设每月生产小、中、大型设每月生产小、中、大型汽车的数量分别为汽车的数量分别为x1,x2,x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535