第四章数学规划ppt课件

1、第四章第四章 数学规划数学规划 (Lindo )(Lindo )优化模型优化模型 数学规划数学规划Lindo Matlab LingoLindo Matlab Lingo实践问题中实践问题中的优化模型的优化模型mixgtsxxxxfzMaxMiniTn, 2 , 1, 0)(. .),(),()(1或x决策变量决策变量f(x)目的函数目的函数gi(x)0约束条约束条件件数学规划数学规划线性规划线性规划(LP)二次规划二次规划(QP)非线性规划非线性规划(NLP)纯整数规划纯整数规划(PIP)混合整数规划混合整数规划(MIP)整数规划整数规划(IP)0-1整数规划整数规划普通整数规划普通整数规划

2、延续规划延续规划LINDO LINDO 公司软件产品简要引见公司软件产品简要引见 美国芝加哥美国芝加哥(Chicago)大学的大学的Linus Schrage教授于教授于1980年前后开发年前后开发, 后来成立后来成立 LINDO系统公司系统公司LINDO Systems Inc.， lindo LINDO: Linear INteractive and Discrete Optimizer (V6.1)LINGO: Linear INteractive General Optimizer (V8.0)LINDO API: LINDO Application Programming Inter

3、face (V2.0)Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0)演示演示(试用试用)版、学生版、高级版、超级版、工业版、版、学生版、高级版、超级版、工业版、扩展版扩展版 求解问题规模和选件不同求解问题规模和选件不同LINDOLINDO和和LINGOLINGO软件能求解的优化模型软件能求解的优化模型 LINGO LINDO优化模型优化模型线性规划线性规划(LP)非线性规划非线性规划(NLP)二次规划二次规划(QP)延续优化延续优化整数规划整数规划(IP) LP QP NLP IP 全局优化全局优化(选选) ILP IQP INLP LINDO/LIN

4、GO软件的求解过程 LINDO/LINGO预处置程序预处置程序线性优化求解程序线性优化求解程序非线性优化求解程序非线性优化求解程序分枝定界管理程序分枝定界管理程序1. 确定常数确定常数2. 识别类型识别类型1. 单纯形算法单纯形算法2. 内点算法内点算法(选选)1、顺序线性规划法、顺序线性规划法(SLP) 2、广义既约梯度法、广义既约梯度法(GRG) (选选) 3、多点搜索、多点搜索(Multistart) (选选) 建模时需求留意的几个根本问题建模时需求留意的几个根本问题 1、尽量运用实数优化，减少整数约束和整数变量、尽量运用实数优化，减少整数约束和整数变量2、尽量运用光滑优化，减少非光滑约

5、束的个数、尽量运用光滑优化，减少非光滑约束的个数 如：尽量少运用绝对值、符号函数、多个变量求如：尽量少运用绝对值、符号函数、多个变量求最大最大/最小值、四舍五入、取整函数等最小值、四舍五入、取整函数等3、尽量运用线性模型，减少非线性约束和非线性变、尽量运用线性模型，减少非线性约束和非线性变量的个数量的个数 如如x/y 5 改为改为x5y4、合理设定变量上下界，尽能够给出变量初始值、合理设定变量上下界，尽能够给出变量初始值 5、模型中运用的参数数量级要适当、模型中运用的参数数量级要适当 (如小于如小于103)需求掌握的几个重要方面需求掌握的几个重要方面1、LINDO: 正确阅读求解报告尤其要掌握

6、敏感性分析正确阅读求解报告尤其要掌握敏感性分析2、LINGO： 掌握集合掌握集合(SETS)的运用；的运用；正确阅读求解报告；正确阅读求解报告；正确了解求解形状窗口；正确了解求解形状窗口； 学会设置根本的求解选项学会设置根本的求解选项(OPTIONS) ； 掌握与外部文件的根本接口方法掌握与外部文件的根本接口方法企业消费方案企业消费方案4.1 奶制品的消费与销售奶制品的消费与销售 空间层次空间层次工厂级：根据外部需求和内部设备、人力、原料等工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目的制定产品消费方案；条件，以最大利润为目的制定产品消费方案；车间级：根据消费方案、工艺流程、

7、资源约束及费车间级：根据消费方案、工艺流程、资源约束及费用参数等，以最小本钱为目的制定消费批量方案。用参数等，以最小本钱为目的制定消费批量方案。时间层次时间层次假设短时间内外部需求和内部资源等不随时间变化，假设短时间内外部需求和内部资源等不随时间变化，可制定单阶段消费方案，否那么应制定多阶段消费方可制定单阶段消费方案，否那么应制定多阶段消费方案。案。本节课题本节课题例例1 加工奶制品的消费方案加工奶制品的消费方案1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制定消费方案，使

8、每天获利最大制定消费方案，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？假设买，每天最多买多桶牛奶，买吗？假设买，每天最多买多少少? 可聘用暂时工人，付出的工资最多是每小时几元可聘用暂时工人，付出的工资最多是每小时几元? A1的获利添加到的获利添加到 30元元/公斤，应否改动消费方案？公斤，应否改动消费方案？ 每天：每天：1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 x1桶牛奶消费桶牛奶消费A1 x2桶牛奶消费桶牛奶消费A2 获利获利 243x1 获利获利 164 x2 原料供应原料供应 5021 xx劳动时间劳动时间 48081221 xx加

9、工才干加工才干 10031x决策变量决策变量 目的函数目的函数 216472xxzMax每天获利每天获利约束条件约束条件非负约束非负约束 0,21xx线性线性规划规划模型模型(LP)时间时间480小时小时 至多加工至多加工100公斤公斤A1 50桶牛奶桶牛奶 每天每天模型分析与假设模型分析与假设 比比例例性性 可可加加性性 延续性延续性 xi对目的函数的对目的函数的“奉献与奉献与xi取值取值成正比成正比 xi对约束条件的对约束条件的“奉献与奉献与xi取值取值成正比成正比 xi对目的函数的对目的函数的“奉献与奉献与xj取值取值无关无关 xi对约束条件的对约束条件的“奉献与奉献与xj取值取值无关无

10、关 xi取值延续取值延续 A1,A2每公斤的获利是与各每公斤的获利是与各自产量无关的常数自产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量的数量和时间是与各自产量无关的常和时间是与各自产量无关的常数数A1,A2每公斤的获利是与相每公斤的获利是与相互产量无关的常数互产量无关的常数每桶牛奶加工出每桶牛奶加工出A1,A2的数量的数量和时间是与相互产量无关的常和时间是与相互产量无关的常数数加工加工A1,A2的牛奶桶数是实的牛奶桶数是实数数 线性规划模型线性规划模型模型求解模型求解 图解法图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx

11、约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目的目的函数函数 Z=0Z=2400Z=3600z=c (常数常数) 等值线等值线c在在B(20,30)点得到最优解点得到最优解目的函数和约束条件是线性函数目的函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目的函数的等值线为直线目的函数的等值线为直线 最优解一定在凸多边最优解一定在凸多边形的某个顶点获得。形的某个顶点获得。 模型求解模型求解 软件实现软件实现 LINDO 6.1 max 72x1+64x2st2x1+x250

12、312x1+8x248043x1100end OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2DO RANGE (SENSITIVITY) ANALYSIS? No20桶牛奶消费桶牛奶消费A1, 30

13、桶消费桶消费A2，利润，利润3360元。元。 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料无剩余原料无剩余时间无剩余时间无剩余加工才干剩余加工才干剩余40max 72x1+6

14、4x2st2x1+x250312x1+8x248043x1100end三三种种资资源源“资源资源 剩余为零的约束为紧约束有效约束剩余为零的约束为紧约束有效约束 模型求解模型求解 reduced cost值表值表示当该非基变量示当该非基变量添加一个单位时添加一个单位时其他非基变量其他非基变量坚持不变目的坚持不变目的函数减少的量函数减少的量(对对max型问题型问题) OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLAC

15、K OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2也可了解为：也可了解为：为了使该非基变为了使该非基变量变成基变量，量变成基变量，目的函数中对应目的函数中对应系数应添加的量系数应添加的量结果解释结果解释 OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLA

16、CK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最优解下最优解下“资源添加资源添加1单位时单位时“效益的增量效益的增量 原料添加原料添加1单位单位, 利润增长利润增长48 时间添加时间添加1单位单位, 利润增长利润增长2 加工才干增长不影响利润加工才干增长不影响利润影子价钱影子价钱 35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？35 或或“=或或“=功能一样功能一样变量与系数间可有空格变量与系数间可有空格(甚至回车甚至回

17、车), 但无运算符但无运算符变量名以字母开头，不能超越变量名以字母开头，不能超越8个字符个字符变量名不区分大小写包括变量名不区分大小写包括LINDO中的关键字中的关键字目的函数所在行是第一行，第二行起为约束条件目的函数所在行是第一行，第二行起为约束条件行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“终终了了行中注有行中注有“!符号的后面部分为注释。如符号的后面部分为注释。如: ! Its Comment.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE 对模型命名对模型命名最多最多72个字符，如：个字符，如： TITLE This Model is onl

18、y an Example变量不能出如今一个约束条件的右端变量不能出如今一个约束条件的右端表达式中不接受括号表达式中不接受括号“( )和逗号和逗号“,等任何符号等任何符号, 例例: 400(X1+X2)需写为需写为400X1+400X2表达式应化简，如表达式应化简，如2X1+3X2- 4X1应写成应写成 -2X1+3X2缺省假定一切变量非负；可在模型的缺省假定一切变量非负；可在模型的“END语句语句后用后用“FREE name将变量将变量name的非负假定取消的非负假定取消可在可在 “END后用后用“SUB 或或“SLB 设定变量上设定变量上下界下界 例如：例如： “sub x1 10的作用等价

19、于的作用等价于“x1ui 交易费 = piui xiui而题目所给定的定值 ui(单位:元)相对总投资 M 很小, piui更小,可以忽略不计,这样购买 Si的净收益为(ri-pi)xi 3要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型: 目标函数 MAXniiiixpr0)( MINmax qixi 约束条件 niiixp0)1 (=M xi0 i=0,1,n4. 模型简化：c投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合。因此对风险、收益赋予权重 s（0s1)，s 称为投资偏好系数.模模型型 3 目标函数：min smaxqixi -（1-s）nii

20、iixpr0)( 约束条件 niiixp0)1 (=M， xi0 i=0,1,2,nb若投资者希望总盈利至少达到水平k 以上，在风险最小的情况下寻找相应的投资组合。模模型型2 固定盈利水平，极小化风险 目标函数： R= minmax qixi 约束条件：niiiixpr0)(k， Mxpii)1 ( ， xi 0 i=0，1，na 在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限 a，使最大的一个风险 qixi/Ma，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。模型模型 1 1 固定风险水平，优化收益 目标函数： Q=MAX11)(niiiixpr 约束条件： M

21、xqiia Mxpii)1 (， xi 0 i=0，1，n四、模型四、模型1 1的求解的求解 模型1为: minf = (-0.05, -0.27, -0.19, -0.185, -0.185) (x0 x1 x2 x3 x 4 ) T x0 + 1.01x1 + 1.02x2 +1.045x3 +1.065x4 =1s.t. 0.025x1 a 0.015x2 a 0.055x3 a 0.026x4a xi 0 (i = 0,1,.4) 由于a是恣意给定的风险度，究竟怎样给定没有一个准那么，不同的投资者有不同的风险度。我们从a=0开场，以步长a=0.001进展循环搜索，编制程序如下：a=0;

22、while(1.1-a)1 c=-0.05 -0.27 -0.19 -0.185 -0.185; Aeq=1 1.01 1.02 1.045 1.065; beq=1; A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026; b=a;a;a;a; vlb=0,0,0,0,0;vub=; x,val=linprog(c,A,b,Aeq,beq,vlb,vub); a x=x Q=-val plot(a,Q,.)，axis(0 0.1 0 0.5)，hold on a=a+0.001;end xlabel(a),ylabel(Q)To

23、Matlabxxgh5a = 0.0030 x = 0.4949 0.1200 0.2000 0.0545 0.1154 Q = 0.1266a = 0.0060 x = 0 0.2400 0.4000 0.1091 0.2212 Q = 0.2019a = 0.0080 x = 0.0000 0.3200 0.5333 0.1271 0.0000 Q = 0.2112a = 0.0100 x = 0 0.4000 0.5843 0 0 Q =0.2190a = 0.0200 x = 0 0.8000 0.1882 0 0 Q =0.2518 a = 0.0400 x = 0.0000 0.9901 0.0000 0 0 Q =0.2673计算结果：计算结果：五、五、 结果分析结果分析返 回4.4.在在a=0.006a=0.006附近有一个转机点，在这一点左边，风险添加很少时，利润增长附近有一个转机点，在这一点左边，风险添加很少时，利润增长 很快。在这一点右边，风险添加很大时，利润增长很缓慢，