优化模型的三要素课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,优化模型的三要素,优化模型,于是，优化模型从数学上可以表述为,这里,opt,最优化的意思，可以是,min,（求极大，即,minamize,的缩写）或,max,（求极小，即,minamize,的缩写）的两者之一；,s.t.,（即,subject to,）,“受约束于”之意,。,（1）,（2）,（3）,优化模型基本类型,1.决策变量,x,的所有分量,x,i,均为连续数值,a）,f,h,i,g,i,都是线性函数，则为线性规划（LP）,b）,f,h,i,g,i,至少有一个是非线性，则为非线性规划（NLP）,c）,f 是二次函数,h,i,g,i,都是线性，则为二次规划（QP）,2.决策变量,x,的的一个或多个分量,x,i,取离散值,a）x的至少一个分量只取整数数值，则为整数规划（IP）,b）x的分量限定只取整数0或1，则为0-1规划（ZOP）,3.此外，为了解决实际问题的需要，还可以分为：单目标规划，多目标规划，动态规划，多层规划等。,（1）线性规划（LP）的一般形式,目标函数和所有的约束条件都是变量的线性函数。,常用的优化模型形式,（2）二次规划问题,目标函数为二次函数，约束条件为线性约束。,常用的优化模型形式,例-1,某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少需要50人，周五需要80人，周六和周日需要90人。现规定应聘者需连续工作5天，试确定聘用方案，即周一到周日每天聘用多少人，是5在满足需要的前况下聘用总人数最少？,优化模型,决策变量,：记周一到周日每天聘用的人数分别为,X,1,，,X,2,，,X,3,，,X,4,，,X,5,，,X,6,，,X,7,，这就是问题的决策变量。,目标函数,：目标函数即是聘用总人数，即,约束条件,：由每天需要的人数确定。由于每人连续工作五天，所以一周的雇员应该是周四到周一聘用的，按照需要至少,50,人，于是,线性规划模型,类似的，有,显然，人数应该是正整数，所以,问题归结为在以上约束条件下求解,min z,的整,数规划模型。由于目标函数和约束条件关于决策变量都是线性函数，所以这是一个整数向行规划模型。,线性规划模型,例-2,某班准备从5名游泳队员中选择4人组成接力队，参加学校的4*100混合泳接力比赛。5名队员4中泳姿的百米平均成绩如下表所示，问应该如何选拔队员组成接力队？,表一 ：5名队员4中泳姿百米平均成绩,队员,甲,乙,丙,丁,戊,蝶泳,106”8,57”2,118”,110”,107”4,仰泳,115”6,106”,107”8,114”2,111”,蛙泳,127”,106”4,124”6,109”6,123”8,自由泳,58”6,53”,59”4,57”2,102”4,线性规划模型,问题分析,：,问题要求从,5,名队员中选出,4,人组成接力队，每人一种泳姿，且四人的泳姿各不相同，使接力队成绩最好。容易想到穷举法，组成接力队的方案有,5,！,=120,中，逐一计算并做比较即可找出最优方案。显然这不是解决问题的最好方法，随着问题规模的变大，穷举法的计算量是无法接受的。,可以用,0-1,变量表示一个队员是否入选接力队，从而建立这个问题的,0-1规划模型.,线性规划模型,记,甲、乙、丙、丁、戊分别为队员,i,=1，2，3，4，5；记,蝶泳、仰泳、蛙泳、自由泳分别为泳姿,j,=1，2，3，4；记队员,i,的第,j,种泳姿的百米成绩为,c,ij,（s），,则表一可以表示成为：,表二 ：5名队员4中泳姿百米平均成绩,队员,甲,乙,丙,丁,戊,蝶泳,66.8,57.2,78,70,67.4,仰泳,75.6,66,67.8,74.2,71,蛙泳,87,66.4,84.6,69.6,83.8,自由泳,58.6,53,59.4,57.2,62.4,线性规划模型,目标函数,：当队员,队员,i,入选泳姿,j,的比赛时，,c,ij,x,ij,表示他的成绩，否则,c,ij,x,ij,=,0,。于是接力队的成绩可以表示为：,决策变量,：引入,0-1,变量,x,ij,若选择队员,i,参加泳姿,j,的比赛，记,x,ij,=,1,，否则记,x,ij,=,0.,这就是问题的决策变量，共,20,个。,每人最多只能入选,4,种泳姿之一，即对于,员,i,=1,，,2,，,3,，,4,，应该有：,约束条件,：,根据组成接力队的要求，,x,ij,应该满足下面两个约束条件：,每种泳姿有且只能有,1,人入选，即对于,员,j,=1,，,2,，,3,，,4,，,5,，应该有：,线性规划模型,综上所述，这个问题的优化模型可以写作：,这是一个线性0-1 规划模型，它是一个特殊的线性整数规划。,Lingo/Lindo软件介绍,这套软件包由美国芝加哥大学的,Linus,Scharge,教授于,1980,年前后开发，专门用于求解最优化问题，后经不断完善和扩充，并成立,LINDO,公司进行商业化运作，取得了巨大的成功。全球,财富,杂志,500,强的企业中，一半以上使用该公司产品，其中前,25,强企业中有,23,家使用该产品。,该软件包功能强大，版本也很多，而我们 使用的只是演示版（试用版），演示版与正式版功能基本上是 类似的，只是能够求解问题的规模受到限制，总变量数不超过,30,个，这在我们目前的使用过程中，基本上是足够。,Lingo/Lindo软件介绍,Lingo/Lindo软件求解的优化模型类型见下图：,优化模型,连续模型,整数模型,线性规划,二次规划,非线性规划,Lindo,Lingo,Lingo/Lindo软件介绍,Lindo,是英文,Linear Interactive and Discrete Optimizer,字首的缩写，即“交互式的线性和离散优化求解器”，可以用来求解线性规划（,LP,）和二次规划（,QP,）；,Lingo,是英文,Linear Interactive and General Optimizer,字首的缩写，即“交互式的线性和通用优化求解器”，它除了具有,Lindo,的全部功能外，还可以用来求解非线性规划。,Lingo,和,Lindo,的最大特色在于可以允许决策变量是整数，而且执行速度很快；,Lingo,实际上还是一种建模语言，即使对优化方面的专业知识了解不多的用户，也能方便的进行输入、求解，并能快速的得到复杂优化问题的高质量的解。,解决一个简单的线性规划（,LP,）问题,Lingo/Lindo软件介绍 -Lindo,其Lindo程序为：,例-3,Lingo/Lindo软件介绍 -Lindo,Lindo,程序以“,MAX”,（或“,MIN”,）表示目标是求最大化（最小化）问题，后面直接写目标函数的表达式和约束的表达式条件，目标函数和约束之间以“,ST”,分开；程序以“,END”,（也可以省略）结束；,输入格式与数学模型表达式几乎完全一样，连系数之间的乘号都一样省略了，而且,必须省略,；,在,Lindo,模型中的书写是相当灵活的；并且,Lindo,中已假定所有变量非负，也不区分大小写；约束条件中的“,=”,及“,”“”,代替；输入的多于空格和回车也会被忽略；,一行中“！”后面的文字将被认为是说明语句，不参与模型的建立，主要目的是增加程序的可读性。,我们从这段程序可以看出,Lindo,模型有以下特点：,现在我们用Lindo软件来求解这个模型，单击工具栏中的 图标，便得到以下运行状态窗口：,Lindo求解器运行状态窗口各项的含义,名称,含义,Status,显示当前求解状态：Optimal表示已经达到最优解；其他可能的显示：Feasible，Infeasible，Unbounded,Iterations,显示迭代次数,Infeasibility,约束不满足的量；0表示这个解是可行的,Objective,显示当前解的目标函数值,Best IP,显示整数规划当前解的最佳标函数值：N/A表示无答案或无意义,IP Bound,显示整数规划的界,Branches,显示分支定界算法已经计算的分支数：N/A表示无答案或无意义,Elapsed Time,显示计算所用时间：0：00说明计算太快，用时还不到0.05S,Update Time,显示控制和刷新本界面的时间间隔,Interrupt Solver,中断求解程序,Close,关闭该窗口,添加Lindo求解器,显示结果如下,单纯行法迭代两次得到最优解,最优目,标值,最优解各变量 的值,对偶价格,影子价格：,表示该非基变量增加一个单位而其他变量不变时目标函数减少的量（对,max,型问题）,松弛变量的值,【,紧约束,】,单纯行法进行两次迭代,Lingo/Lindo软件介绍 -Lindo,变量以字母开头、不区分大小写，变量名可不超过,8,个字符；,变量不能出现在约束条件的右端，右端只能是常数；变量与系数之间可以有空格，但,绝对不能有任何运算符,；,Lindo,中不接受”（）“和逗号,”,，“等任何运算符号（除非在注释语句中）；,模型中的表达式应当经过化，如不能出现（,X+1,）,2,+2X,2,+3Y,，而应该写成,3X,2,+2X+3Y+1,；,模型中已假定所有变量非负，可在模型的”,end“,语句后面用命令”,free“,取消变量的非负假定，其用法是在”,free“,后面跟变量名；,在模型的”,end“,语句后面可以用命令”,SUB“,设定变量的上界，用命令”,SLB“,设定变量的下界；,Lindo,中以“！”开始的是说明语句，说明语句也以“,;”,结束。,使用,Lindo,软件的一些注意事项：,Lingo/Lindo软件介绍 -Lindo,下面我们用一个例子来说明,Lindo,中三个变量范围限制命令（,FREE,、,SBU,、,SLB,）的作用和使用方法：,例-4,在这个模型中，对变量x没有非负限制，对y有上限限制，对z有下限限制；分别用,FREE、SBU、SLB三个命令可以实现这些功能。具体输入如下：,图a：例4的输入模型,图b：例4的输出结果,Lingo/Lindo软件介绍 -Lingo,Lingo9.0,软件比以前的版本有了很大的改进，功能大大增强，性能更加稳定，结果更加可靠；从基本更能上看，与,Lindo,相比，,Lingo,软件主要具备以下优点：,除具备,Lindo,饿全部功能外，还可以用于求解非线性规划问题；,Lingo,包含了内置的建模语言，允许以简练、直观的方式描述较大规模的优化问题，模型中所需的数据可以以一定的格式保存在独立的文件中。,事实上，Lindo公司目前已经将Lindo软件从其产品目录中删除，而将Lindo软件的所有功能都在Lingo中得到了支持，所以在不久的将来总有一天人们会废弃Lindo软件不再使用，但Lingo的生命力应该还是很顽强的！,Lingo/Lindo软件介绍,-Lingo,对前面的,线性规划模型,，编写,Lingo,程序如下：,点击图标,运行，屏幕上显示运行状态窗口如下：,对于Lingo运行状态窗口，我们给于以下解释：,变量数目：变量总数（,Total,）、非线型变量数（,Nonlinear,）、整数变量数（,Integer,）,约束变量：约束总数（,Total,）、非线性约束个数（,Nonlinear,）,非线性系数数量：总数（,Total,）、非线性项的系数个数（,Nonlinear,）,内存使用量：单位为千字节,求解花费时间：显示格式“时,:,分,:,秒,:”,Lingo状态窗口中关于,求解器,各项的含义,域名,含义,可能显示的值,Model Class,当前模型类型,LP、QP、ILP、IQP、PILP、PIQP、NLP、INLP、PINLP,State,当前解的状态,Global Optimum、Local Optimum、Feasible、Infeasible（