数学模型与lindo软件[西南交大]

数学模型与lindo软件 西南交通大学数学建模 需要掌握的几个重要方面需要掌握的几个重要方面 正确阅读求解报告 尤其要掌握敏感性 分析 应用举例 对lindo软件窗口参数的认识 LINDO公司软件产品简要介绍 美国芝加哥 Chicago 大学的Linus Schrage教授于1980 年前后开发 后来成立 LINDO系统公司 LINDO Systems Inc 网址 LINDO Linear Interactive and Discrete Optimizer V6 1 LINGO Linear Interactive General Optimizer V8 0 LINDO API LINDO Application Programming Interface V2 0 What s Best SpreadSheet e g EXCEL V7 0 学生版 演示版和发行版的主要区别在于对优化问题 的规模 变量和约束个数 有不同的限制 LINDO和LINGO软件能求解的优化模型 LINDO LINGO软件的求解过程 LINDO LINGO预处理程序 1 确定常数 2 识别类型 LP NLP IP 全局优化 选 INLP ILP IQP 分枝定界管理程序 线性优化求解程序非线性优化求解程序 1 顺序线性规划法 SLP 2 广义既约梯度 GRG 选 3 多点搜索 Multistart 选 1 单纯形算法 2 内点算法 选 用LINDO 求解线性规划 LP 问题 求解机制 采用单纯形法 一般是首先寻求一个 可行解 在有可行解情况下再寻求最 优解 最优解 Optimal Solution 可行解 所得结果 解无界 Unbounded Solution 不可行解 max 2x 3y ST 4x 3y 10 3x 5y 12 end 假设所有的变量都是非负的 max23 4310 3512 0 zxy stxy xy x y 当前状态 已经达 到最优解 迭代次数 2次 多余或错误的约束 条件 0 当前的目标值 145 最好的整数解 整数规划的界 分枝数 所用时间 刷新本界面的时间 间隔 1 秒 不区分变量中的大小写字符 变量名不 能超过 个字符 目标函数及各约束条件 之间一定要有 Subject to ST 分开 可用 代替 状态窗口 LINDO Solver Status 1 表示单纯形法在两次迭代 旋转 后得到最优解 2 表示最优目标值 3 给出最优解中各变量的值 4 给出松驰变量的值 第2 3 行松驰变量均为0 说明对于最 优解来讲 两个约束 第2 3 行 均取等号 7 表示用单纯形法进行了两次迭代 5 列出最优单纯形 表中判别数所在行的 变量的系数 表示当 变量有微小变动时 目标函数的变化率 其中基变量的 reduced cost值应 为0 对于非基变量 Xj 相应的 reduced cost值表 示当某个变量Xj 增 加一个单位时目标函 数减少的量 max型 问题 6 对偶价格 表示当对应约束 有微小变动时 目标函数的变 化率 输出结果中对应于每一 个约束有一个对偶价格 若其 数值为p 表示对应约束中不 等式右端项若增加1 个单位 目标函数将增加p 个单位 max 型问题 一种汽油的特性可用两个指标描述 其点火性用 辛烷数 描述 其挥发性用 蒸汽压力 描述 某炼油厂有四种标准汽油 设其标 号分别为 其特性及库存量列于下表 中 将上 述标准汽油适量混合 可得两种飞机汽油 某标号为 这 两种飞机汽油的性能指标及产量需求列于表 中 问应如何根据库存情况适量混合各种标准汽油 使既满足飞机汽 油的性能指标 而产量又为最高 选自张莹 运筹学基础 灵敏度分析 系统报告当目标函数的系数和约束右端项在什么范围 变化 此时假定其他系数保持不变 时 最优基保持不变 1 目标函数中 的 变量系数为 当它在 1 1 154137 1 0 0 154137 1 变化时 最 优基保持不变 2 当它在 250000 234752 984375 250000 18 6222 0625 15247 015625 436222 06 25 范围变化时 最优基 保持不变 若想获得灵敏度分析 可用 Reports 的 Rang 选项 若需显示单纯形表 可执行 Reports 的 Tab lean 选项 选项设置 IP Objective Hurdle IP目 标函数的障碍值 即只寻 找比这个值更优最优解 如知道某个整数可行解 时 就可以设置这个值 IP Var Fixing Tol 固定一 个整数变量取值所依据的 一个上限 如果一个整数 变量判别数的值很大 超 过该上限 则以后把该整 数变量固定 Nonzero Limit 非零系 数的个数上限 Iteration Limit 最大迭 代步数 Initial Contraint Tol 约束的初始误差上限 Final Contraint Tol 约 束的最后误差上限 Entering Var Tol 进基 变量的REDUCED COST 的误差限 Pivot Size Tol 旋转元 的误差限 Preprocess 预处理 生成割平面 Preferred Branch 优先的分枝方式 Default 缺省方式 Up 向上取整优先 Down 向下取整优先 IP Optimality Tol IP最优值允许的误差上限 如5 即0 05 LINDO的一些注意事项 1 变量与系数间可有空格 但不能有任何运算符号如 乘号 等 2 一般LINDO 中不能接受括号 和逗号 例 400 X1 X2 需写成400X1 400X2 10 000 需写成10000 3 LINDO 文件中常有注释间杂于各命令 COMMANDS 之中 前面 注有 符号 例如 This is a comment 4 LINDO中已假定所有变量非负 可在模型的 END 语句后面用 FREE name 语句将变量name 的非负假定取消 5 变量不能出现在一个约束条件的右端 6 表达式应化简 如2X1 3X2 4X1应写成 2X1 3X2 量纲分析与一般错误的避免 1 简单的印刷错误 2 表达式的原理错误 3 近似误差 印刷错误 PICTURE 命令 量纲分析 整数规划 IP LINDO 可用于求解整数规划 IP 模型的输入与LP 问 题类似 但在END标志后需定 义整型变量 0 1 型的变量可由INTEGER 可简写为INT 命令来标识 INT vname 或INT n 前者只将变量vname 标识为 0 1 型 后者将当前模型中 前n 个变量标识为0 1 型 一般的整数变量可用命令GIN 是GENERAL INTEGER 的 意思 其使用方式及格式与 INT 命令相似 MIN X1 X2 X3 X4 X5 X6 X7 SUBJECT TO X1 X4 X5 X6 X7 50 X1 X2 X5 X6 X7 50 X1 X2 X3 X6 X7 50 X1 X2 X3 X4 X7 50 X1 X2 X3 X4 X5 80 X2 X3 X4 X5 X6 90 X3 X4 X5 X6 X7 90 END GIN 7 LINDO 求解用的是分枝定界法 紧接着 几行显示的是分枝定界的信息 在第1 个分枝中设定x2 4 并在该分枝中找到了 整数解 而且就是全局整数最优解 所以 算法停止 最优解 x 0 4 32 12 32 10 4 松弛和剩余变量 SLACK OR SURPLUS 仍然可以表示约束的松紧程度 在22次迭代后找到对应 的线性规划 LP 问题 的最优解 最优值 93 3333359 目前IP 尚无相应完善的敏感性分析理论 因此REDUCED COST 和DUAL PRICES 结果在整数规划中意义不大 0 1 规划规划 MIN 2X1 X2 X3 ST X1 3X2 X3 2 4X2 X3 5 X1 2X2 X3 2 X1 4X2 X3 98 4X2 0 3X1 LAG1 2LAG2 277 2 X1 X2 100 X1 2X2 0 END QCP 4 3 GIN 2 4 最好直接用后面介绍的 LINGO 求解QP 目标函数 1 目标函数只用于给出模型 中相应变量的出现顺序 X1 x2 lag1 lag2用加号连接 2 在实际约束前增加刚刚得 到的有关变量的一阶最优条件 3 QCP n语句说明这是一 个二次规划 同时指出实际约 束是从第n 行开始的 4 规定整数变量 File菜单包括了LINDO 通过文件与外部设备交换信息的命令 File Open 打开文件 可对文件进行编辑 保存 等 而File View只用于文件浏览 可求解 不能编辑 由于LINDO 对文件大小有限制 File View 对浏览大规模的模型文件是有用的 File LOG OUTPUT要求你指定一个文件名后 所有输出都被送到这个日志文件中保存下来 File Take Commands该命令用于打开一个 LINDO 命令脚本文件 File Basis Save 将单纯形算法当前的基 解 以 指定的文件名和文件格式保存下来 可以用 File Basis Read 读出这个基 解 并从这个 基 解 开始继续运行单纯形算法 File Title显示当前模型的名称 如果该模型被 命名过 Date显示当前日 期和时间 Elapsed Time本 次启动已用时间 Edit 编辑 菜单包括了在当前窗口下编辑文本的命令 用鼠标双击其中某个符号 则该符号进入缓冲 区 Paste Buffer 也可以直接编辑缓 冲区的内容 点击 Paste 按钮时 缓冲区的 内容将被插入模型中 点击 Clear 按 钮将清除缓冲区的内容 点击 Close 按钮 将关闭该对话框 用于模型中当前 光标后插入符号 可选符号是三类 1 LINDO 系统的 保留字 2 当前模型的决 策变量 3 约束的行号 EDIT OPTIONS 已讲 Solve 求解 菜单包括了求解模型的命令 SOLVE COMPILE MODELSOLVE COMPILE MODEL 编译当前模型 使SOLVE SOLVE 命令时自然也是先调用该命令 如果当前模型输入有语法错误 将报告错误 SOLVE PIVOTSOLVE PIVOT进行一次迭代 即一次旋转 由此你可以 跟踪整个单纯形算法的运行 SOLVE DEBUGSOLVE DEBUG分析LP 无解 或无界的原因 建议如何修 改 仅对LP 有效 对IP 和 QP 无意义 SOLVE Preemptive GoalSOLVE Preemptive Goal 按字典序对目标进行优化 先 优化第1 个目标 然后把这个 目标的值固定在最优值 对第 2 个目标进行优化 依此类推 仅对LP 和IP 有效 对QP 无意义 REPORTS 报告 菜单包括了生成解答结果报告的命令 RangeRange 显示当前解的敏感性分析结果 在 此之前求解过当前模型 SolutionSolution 显示 当前的解 全部解 或非零解 ParametricsParametrics 对约束的右端项 RHS 进 行参数分析 也就是研究某个约束的右端项 发生变化时 最优值何变化 PerusePeruse 可有选 择地显示列或行 的有关信息 PicturePicture 按照图形或文本方式显示模型中 的非零系数 而Basis PictureBasis Picture 只显 示当前基 Basis 的非零系数 TableauTableau显示单纯形表 Formulation显示当前模型 Show Column显示模型中你选定的列 的信息 Positive Definite判断二次规划的目标函数的二次型是否正 定 Report Statistics显示当前模型的统计信息 举QP例 ROWS 5 VARS 4 INTEGER VARS 2 0 0 1 QCP 4 NONZEROS 19 CONSTRAINT NONZ 12 6 1 DENSITY 0 760 SMALLEST AND LARGEST ELEMENTS IN ABSOLUTE VALUE 0 300000 277 000 OBJ MIN NO 2 0 2 GUBS 1 SINGLE COLS 0 REDUNDANT COLS 0 第一行第一行 模型只有5 行 约束只有4 行 4 个变量 其中两个 整数变量 无0 1 变量 从第4 行开始是二次规划的实际约束 第二行第二行 非零系数共有19 个 约束中非零系数共有12 个 其中6 个为1 或 1 模型密度为0 760 密度定义为非零系数 行 数 变量数 第三行第三行 模型中系 数的最小值和最大 值 绝对值 为 0 3 和277 min X1 X2 LAG1 LAG2 S T 2X1 0 3X2 LAG1 LAG2 98 4X2 0 3X1 LAG1 2LAG2 277 X1 X2 100 X1 2X2 0 END QCP 4 GIN 2 版面局限 第四行第四行 模型目标为极小化 小于等于 等于 大于等于约束分别 有 个 广义上界约束 GUBS 不超过 个 变量上界 约束 VUBS 不少于1个 GUBS 是指一组不含有相同变量的约束 所谓VUBS 是指一个 蕴涵变量上界的约束 如从约束X1 X2 X3 0 可以看出 若X3 0 则X1 0 X2 0 因为有非负限制 因此X1 X2 X3 0