优化模型的三要素.ppt

优化模型的三要素 优化模型 于是 优化模型从数学上可以表述为 这里opt最优化的意思 可以是min 求极大 即minamize的缩写 或max 求极小 即minamize的缩写 的两者之一 s t 即subjectto 受约束于 之意 1 2 3 优化模型基本类型 1 决策变量x的所有分量xi均为连续数值a f hi gi都是线性函数 则为线性规划 LP b f hi gi至少有一个是非线性 则为非线性规划 NLP c f是二次函数 hi gi都是线性 则为二次规划 QP 2 决策变量x的的一个或多个分量xi取离散值a x的至少一个分量只取整数数值 则为整数规划 IP b x的分量限定只取整数0或1 则为0 1规划 ZOP 3 此外 为了解决实际问题的需要 还可以分为 单目标规划 多目标规划 动态规划 多层规划等 1 线性规划 LP 的一般形式目标函数和所有的约束条件都是变量的线性函数 常用的优化模型形式 2 二次规划问题目标函数为二次函数 约束条件为线性约束 常用的优化模型形式 例 1某服务部门一周中每天需要不同数目的雇员 周一到周四每天至少需要50人 周五需要80人 周六和周日需要90人 现规定应聘者需连续工作5天 试确定聘用方案 即周一到周日每天聘用多少人 是5在满足需要的前况下聘用总人数最少 优化模型 决策变量 记周一到周日每天聘用的人数分别为X1 X2 X3 X4 X5 X6 X7 这就是问题的决策变量 目标函数 目标函数即是聘用总人数 即 约束条件 由每天需要的人数确定 由于每人连续工作五天 所以一周的雇员应该是周四到周一聘用的 按照需要至少50人 于是 线性规划模型 类似的 有 显然 人数应该是正整数 所以 问题归结为在以上约束条件下求解minz的整数规划模型 由于目标函数和约束条件关于决策变量都是线性函数 所以这是一个整数向行规划模型 线性规划模型 例 2某班准备从5名游泳队员中选择4人组成接力队 参加学校的4 100混合泳接力比赛 5名队员4中泳姿的百米平均成绩如下表所示 问应该如何选拔队员组成接力队 线性规划模型 问题分析 问题要求从5名队员中选出4人组成接力队 每人一种泳姿 且四人的泳姿各不相同 使接力队成绩最好 容易想到穷举法 组成接力队的方案有5 120中 逐一计算并做比较即可找出最优方案 显然这不是解决问题的最好方法 随着问题规模的变大 穷举法的计算量是无法接受的 可以用0 1变量表示一个队员是否入选接力队 从而建立这个问题的0 1规划模型 线性规划模型 记甲 乙 丙 丁 戊分别为队员i 1 2 3 4 5 记蝶泳 仰泳 蛙泳 自由泳分别为泳姿j 1 2 3 4 记队员i的第j种泳姿的百米成绩为cij s 则表一可以表示成为 线性规划模型 目标函数 当队员队员i入选泳姿j的比赛时 cijxij表示他的成绩 否则cijxij 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软件介绍 这套软件包由美国芝加哥大学的LinusScharge教授于1980年前后开发 专门用于求解最优化问题 后经不断完善和扩充 并成立LINDO公司进行商业化运作 取得了巨大的成功 全球 财富 杂志500强的企业中 一半以上使用该公司产品 其中前25强企业中有23家使用该产品 该软件包功能强大 版本也很多 而我们使用的只是演示版 试用版 演示版与正式版功能基本上是类似的 只是能够求解问题的规模受到限制 总变量数不超过30个 这在我们目前的使用过程中 基本上是足够 Lingo Lindo软件介绍 Lingo Lindo软件求解的优化模型类型见下图 优化模型 连续模型 整数模型 线性规划 二次规划 非线性规划 Lindo Lingo Lingo Lindo软件介绍 Lindo是英文LinearInteractiveandDiscreteOptimizer字首的缩写 即 交互式的线性和离散优化求解器 可以用来求解线性规划 LP 和二次规划 QP Lingo是英文LinearInteractiveandGeneralOptimizer字首的缩写 即 交互式的线性和通用优化求解器 它除了具有Lindo的全部功能外 还可以用来求解非线性规划 Lingo和Lindo的最大特色在于可以允许决策变量是整数 而且执行速度很快 Lingo实际上还是一种建模语言 即使对优化方面的专业知识了解不多的用户 也能方便的进行输入 求解 并能快速的得到复杂优化问题的高质量的解 解决一个简单的线性规划 LP 问题 Lingo Lindo软件介绍 Lindo 其Lindo程序为 例 3 Lingo Lindo软件介绍 Lindo Lindo程序以 MAX 或 MIN 表示目标是求最大化 最小化 问题 后面直接写目标函数的表达式和约束的表达式条件 目标函数和约束之间以 ST 分开 程序以 END 也可以省略 结束 输入格式与数学模型表达式几乎完全一样 连系数之间的乘号都一样省略了 而且必须省略 在Lindo模型中的书写是相当灵活的 并且Lindo中已假定所有变量非负 也不区分大小写 约束条件中的 及 代替 输入的多于空格和回车也会被忽略 一行中 后面的文字将被认为是说明语句 不参与模型的建立 主要目的是增加程序的可读性 我们从这段程序可以看出Lindo模型有以下特点 现在我们用Lindo软件来求解这个模型 单击工具栏中的图标 便得到以下运行状态窗口 添加Lindo求解器 显示结果如下 单纯行法迭代两次得到最优解 最优目标值 最优解各变量的值 对偶价格 影子价格 表示该非基变量增加一个单位而其他变量不变时目标函数减少的量 对max型问题 松弛变量的值 紧约束 单纯行法进行两次迭代 Lingo Lindo软件介绍 Lindo 变量以字母开头 不区分大小写 变量名可不超过8个字符 变量不能出现在约束条件的右端 右端只能是常数 变量与系数之间可以有空格 但绝对不能有任何运算符 Lindo中不接受 和逗号 等任何运算符号 除非在注释语句中 模型中的表达式应当经过化 如不能出现 X 1 2 2X2 3Y 而应该写成3X2 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 Lindo软件介绍 Lingo 关闭求解状态窗口 得到结果如下 Lingo Lindo软件介绍 Lingo Lingo中变量不区分大小写 变量名可以超过8个 不能超过32个 需以字母开头 用Lingo解优化模型时已假定所有变量非负 除非用限定变量范围的函数 free或 bnd另行说明 变量可以放在约束条件右端 同时数字也可以放在约束条件左边 Lingo模型语句由一系列语句组成 每一个语句都必须以 结尾 Lingo中以 开始的是说明语句 说明语句也以 结束 关于Lingo的基本用法的几点注意事项 Lingo Lindo软件介绍 Lingo ABS X 绝对值函数 返回X的绝对值 EXP X 指数函数 以自然对数e为底 返回eX的值 LOG X 自然对数函数 返回X的自然对数值 POW X Y 指数函数 返回XY的值 SQR X 平方函数 返回X 的值 SQRT X 平方根函数 返回X的平方根 FLOOR X 取整函数 返回X的整数部分 向靠近0的方向取 SMAX X 取最大值 返回一列数 LIST 的最大值 SMIN X 取最大小值 返回一列数 LIST 的最小值 三角函数 COS X SIN X TAN X 在Lingo中建立的优化模型可以引用大量的内部函数这些函数都以 符号打头 其用法比较简单 我们一一列出 基本数学函数 Lingo Lindo软件介绍 Lingo 变量定界函数对变量的取值范围附加限制 共有以下四种 变量定界函数 BND L X U 限制L X U 注意 Lingo中没有与Lindo命令SLB SUB类似的函数 SLB SUB BIN X 限制X为0或1 注意Lindo中的命令是INT 但Lingo中这个函数却不是 INT FREE X 取消对X的符号限制 即可取负数 0或正数 GIN X 限制X为整数 添加Lindo截图添加Lingo截图 Lindo模型与Lingo模型的区别与联系 Lindo中目标函数 Max 开头 在Lingo中则以 Max 开头 ST 在Lingo模型中中不再需要 Lindo中系数和变量之间不能含有运算符 而Lingo中每个系数和变量之间均增加了运算符 并且绝对不可以省略 Lingo中每行后面均增加了一个分号 英文状态下输入 Lingo中模型以 MODEL 开始 以 END 结束 对于简单的模型 这两个语句都可以省略