优化模型的三要素

《优化模型的三要素》由会员分享，可在线阅读，更多相关《优化模型的三要素（30页珍藏版）》请在金锄头文库上搜索。

1、F优化模型的三要素优化模型于是，优化模型从数学上可以表述为这里opt 最优化的意思，可以是min（求极大 ，即minamize的缩写）或max （求极小，即 minamize的缩写）的两者之一；s.t. （即subject to） “受约束于”之意。（1）（2）（3）F优化模型基本类型1.决策变量x的所有分量xi均为连续数值a）f ,hi ,gi都是线性函数，则为线性规划（LP）b）f ,hi ,gi至少有一个是非线性，则为非线性规划（NLP）c） f 是二次函数,hi ,gi 都是线性，则为二次规划（QP）2.决策变量x的的一个或多个分量xi取离散值a） x的至少一个分量只取整数数值，则为整

2、数规划（IP）b） x的分量限定只取整数0或1，则为0-1规划（ZOP）3.此外，为了解决实际问题的需要，还可以分为：单 目标规划，多目标规划，动态规划，多层规划等。（1）线性规划（LP）的一般形式 目标函数和所有的约束条件都是变量的线性 函数。常用的优化模型形式（2）二次规划问题 目标函数为二次函数，约束条件为线性约束。常用的优化模型形式例-1 某服务部门一周中每天需要不同数目的 雇员：周一到周四每天至少需要50人，周五 需要80人，周六和周日需要90人。现规定应 聘者需连续工作5天，试确定聘用方案，即周 一到周日每天聘用多少人，是5在满足需要的 前况下聘用总人数最少？ 优化模型 决策变量：

3、记周一到周日每天聘用的人数分别为X1，X2 ，X3，X4，X5，X6 ，X7，这就是问题的决策变量。 目标函数：目标函数即是聘用总人数，即 约束条件：由每天需要的人数确定。由于每人连续工 作五天，所以一周的雇员应该是周四到周一聘用的，按 照需要至少50人，于是线性规划模型线性规划模型类似的，有显然，人数应该是正整数，所以问题归结为在以上约束条件下求解min z的 整数规划模型。由于目标函数和约束条件关于 决策变量都是线性函数，所以这是一个整数向 行规划模型。线性规划模型线性规划模型例-2 某班准备从5名游泳队员中选择4人组成 接力队，参加学校的4*100混合泳接力比赛。 5名队员4中泳姿的百米

4、平均成绩如下表所示 ，问应该如何选拔队员组成接力队？表一 ：5名队员4中泳姿百米平均成绩队员甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4线性规划模型线性规划模型问题分析：问题要求从5名队员中选出4人组成接力 队，每人一种泳姿，且四人的泳姿各不相同，使接 力队成绩最好。容易想到穷举法，组成接力队的方 案有5！=120中，逐一计算并做比较即可找出最优方 案。显然这不是解决问题的最好方法，随着问题规 模的变大，穷举法的计算量是无法接受的。可

5、以用0-1变量表示一个队员是否入选接力队， 从而建立这个问题的0-1规划模型.线性规划模型线性规划模型记甲、乙、丙、丁、戊分别为队员 i=1，2，3，4，5 ；记蝶泳、仰泳、蛙泳、自由泳分别为泳姿 j=1，2，3 ，4；记队员 i 的第 j 种泳姿的百米成绩为 cij（s），则 表一可以表示成为：表二 ：5名队员4中泳姿百米平均成绩队员甲乙丙丁戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4线性规划模型线性规划模型 目标函数：当队员队员 i 入选泳姿 j 的比赛时， cij xij表示他

6、的成绩，否则cij xij=0。于是接力队的成绩可 以表示为： 决策变量：引入0-1变量xij 若选择队员 i 参加泳姿 j 的 比赛，记 xij=1，否则记 xij=0.这就是问题的决策变量， 共20个。每人最多只能入选4种泳姿之一，即对于员 i=1，2，3 ，4，应该有： 约束条件：根据组成接力队的要求， xij 应该满足下面两 个约束条件：每种泳姿有且只能有1人入选，即对于员 j=1，2，3，4 ，5，应该有：线性规划模型线性规划模型综上所述，这个问题的优化模型可以写作：这是一个线性0-1 规划模型，它是一个特 殊的线性整数规划。Lingo/Lindo软件介绍 这套软件包由美国芝加哥大学

7、的Linus Scharge教授 于1980年前后开发，专门用于求解最优化问题，后经 不断完善和扩充，并成立LINDO公司进行商业化运作 ，取得了巨大的成功。全球财富杂志500强的企业 中，一半以上使用该公司产品，其中前25强企业中有 23家使用该产品。 该软件包功能强大，版本也很多，而我们 使用的只是 演示版（试用版），演示版与正式版功能基本上是 类 似的，只是能够求解问题的规模受到限制，总变量数不 超过30个，这在我们目前的使用过程中，基本上是足 够。Lingo/Lindo软件介绍Lingo/Lindo软件求解的优化模型类型见下图：优化模型连续模型整数模型线性规划二次规划非线性规划Lind

8、o LingoLingo/Lindo软件介绍Lindo是英文Linear Interactive and Discrete Optimizer字首的缩写，即“交互式的线性和离散优化 求解器”，可以用来求解线性规划（LP）和二次规划（ QP）；Lingo是英文Linear Interactive and General Optimizer字首的缩写，即“交互式的线性和通用优化 求解器”，它除了具有Lindo的全部功能外，还可以用 来求解非线性规划。Lingo和Lindo的最大特色在于可以允许决策变量是整 数，而且执行速度很快；Lingo实际上还是一种建模语 言，即使对优化方面的专业知识了解不多的

9、用户，也 能方便的进行输入、求解，并能快速的得到复杂优化 问题的高质量的解。 解决一个简单的线性规划（LP）问题Lingo/Lindo软件介绍-Lindo其Lindo程序为：例-3Lingo/Lindo软件介绍-LindoLindo程序以“MAX”（ 或“MIN”）表示目标是求最大化 （最小化）问题，后面直接写目标函数的表达式和约束 的表达式条件，目标函数和约束之间以“ST”分开；程序 以“END” （也可以省略）结束； 输入格式与数学模型表达式几乎完全一样，连系数之间 的乘号都一样省略了，而且必须省略； 在Lindo模型中的书写是相当灵活的；并且Lindo中已假 定所有变量非负，也不区分大小

10、写；约束条件中的“=” 及“”“”代替；输入的多于空格和回车也会 被忽略； 一行中“！”后面的文字将被认为是说明语句，不参与模 型的建立，主要目的是增加程序的可读性。 我们从这段程序可以看出Lindo模型有以下特点：现在我们用Lindo软件来求解这个模型，单击工具栏中的 图标，便得到以下运行状态窗口：Lindo求解器运行状态窗口各项的含义名称含义Status显示当前求解状态：Optimal表示已经达到 最优解；其他可能的显示：Feasible， Infeasible，UnboundedIterations显示迭代次数Infeasibility 约束不满足的量；0表示这个解是可行的Objecti

11、ve显示当前解的目标函数值Best IP显示整数规划当前解的最佳标函数值： N/A表示无答案或无意义IP Bound显示整数规划的界Branches显示分支定界算法已经计 算的分支数： N/A表示无答案或无意义Elapsed Time显示计算所用时间 ：0：00说明计算太快 ，用时还 不到0.05SUpdate Time显示控制和刷新本界面的时间间 隔Interrupt Solver中断求解程序Close关闭该 窗口添加Lindo求解器显示结果如下单纯行法迭代两次得到最优解最优目标值最优解 各变量 的值对偶价格影子价格：表示该非基变量增 加一个单位而其他 变量不变时目标函 数减少的量（对 ma

12、x型问题）松弛变量的值【 紧约束】单纯行法进 行两次迭代Lingo/Lindo软件介绍-Lindo变量以字母开头、不区分大小写，变量名可不超过8个字符；变量不能出现在约束条件的右端，右端只能是常数；变量与系 数之间可以有空格，但绝对不能有任何运算符； Lindo中不接受”（）“和逗号 ”，“等任何运算符号（除非在注释 语句中）； 模型中的表达式应当经过化，如不能出现 （X+1）2 + 2X2 + 3Y，而应该写成3X2+2X+3Y+1； 模型中已假定所有变量非负，可在模型的 ”end“语句后面用命 令”free“取消变量的非负假定，其用法是在”free“后面跟变量 名； 在模型的 ”end“语

13、句后面可以用命令”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软件比以前的版本有

14、了很大的改进，功能大大增强 ，性能更加稳定，结果更加可靠；从基本更能上看，与Lindo相 比，Lingo软件主要具备以下优点：除具备Lindo饿全部功能外，还可以用于求解非线性规划问题；Lingo包含了内置的建模语言，允许以简练、直观的方式描述较大规 模的优化问题，模型中所需的数据可以以一定的格式保存在独立的 文件中。事实上，Lindo公司目前已经将Lindo软件从其产品目 录中删除，而将Lindo软件的所有功能都在Lingo中得到了 支持，所以在不久的将来总有一天人们会废弃Lindo软件不 再使用，但Lingo的生命力应该还是很顽强的！Lingo/Lindo软件介绍-Lingo 对前面的线性

15、规划模型，编写Lingo程序如下：点击图标 运行，屏幕上显示运行状态窗口如下：对于Lingo运行状态窗口， 我们给于以下解释：u变量数目：变量总数（ Total）、非线型变量数 （Nonlinear）、整数变 量数（Integer）u约束变量：约束总数（ Total ）、非线性约束个 数（Nonlinear）u非线性系数数量：总数 （ Total ）、非线性项的 系数个数（Nonlinear）u内存使用量：单位为千字节u求解花费时间：显示 格式“时:分:秒:”Lingo状态窗口中关于求解器各项的含义域名含义可能显示的值Model Class 当前模型类型LP、QP、ILP、IQP、PILP、P

16、IQP、NLP、 INLP、PINLPState当前解的状态Global Optimum、Local Optimum、Feasible、 Infeasible（不可行）、Unbounded（无界）、 Interrupted（中断）、undetermined（未确定 ）Objective当前解的目标 函数值实数Infeasibility当前约束不满 足的量实数Iterations目前为止迭代 的次数非负实数Lingo状态窗口中关于扩展的求解器各项的含义域名含义可能显示的值Solver Type使用的特殊求解程 序B-and-B（分支定界法） Global（全局最优求解程序） Multistart（用多个初始点求解的程序） Best Obj到目前为止找到的 可行解最佳目标函 数实数Steps特殊求解程序当前 运行步数非负实数Active有效步数非负实数Lin