《线性整数规划模型ppt课件》由会员分享，可在线阅读，更多相关《线性整数规划模型ppt课件（91页珍藏版）》请在金锄头文库上搜索。
1、优化建模与计算 许顺维 参考书 优化建模与LINDO LINGO软件 谢金星 薛毅编著 清华大学出版社 2005年7月第1版 内容提要 1 优化模型的基本概念2 优化问题的建模实例3 LINDO LINGO软件简介 1 优化模型的基本概念 最优化是工程技术 经济管理 科学研究 社会生活中经常遇到的问题 如 优化模型和算法的重要意义 结构设计 资源分配 生产计划 运输方案 解决优化问题的手段 经验积累 主观判断 作试验 比优劣 建立数学模型 求解最优策略 最优化 在一定条件下 寻求使目标最大 小 的决策 优化问题三要素 决策变量 目标函数 约束条件 优化问题的一般形式 无约束优化 没有约束 与约
2、束优化 有约束 可行解 只满足约束 与最优解 取到最优值 局部最优解与整体最优解 局部最优解 LocalOptimalSolution 如x1 整体最优解 GlobalOptimalSolution 如x2 优化模型的简单分类 线性规划 LP 目标和约束均为线性函数非线性规划 NLP 目标或约束中存在非线性函数二次规划 QP 目标为二次函数 约束为线性整数规划 IP 决策变量 全部或部分 为整数整数线性规划 ILP 整数非线性规划 INLP 纯整数规划 PIP 混合整数规划 MIP 一般整数规划 0 1 整数 规划 连续优化 离散优化 数学规划 优化模型的简单分类和求解难度 优化 线性规划 非
3、线性规划 二次规划 连续优化 整数规划 问题求解的难度增加 2 优化模型实例 目标函数 约束条件 例2 1线性规划模型 LP 模型求解 图解法 约束条件 目标函数 z c 常数 等值线 在B 20 30 点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边形的某个顶点取得 求解LP的基本思想 思路 从可行域的某一顶点开始 只需在有限多个顶点中一个一个找下去 一定能得到最优解 LP的约束和目标函数均为线性函数 2维 可行域线段组成的凸多边形 目标函数等值线为直线 最优解凸多边形的某个顶点 n维 超平面组成的凸多面体 等值线是超平面
4、凸多面体的某个顶点 LP的通常解法是单纯形法 G B Dantzig 1947 线性规划模型的解的几种情况 目标 98x1 277x2 x12 0 3x1x2 2x22 约束 x1 x2 100 x1 2x2x1 x2 0 二次规划模型 QP 若还要求变量为整数 则是整数二次规划模型 IQP 二次规划模型 QP 例1 2 决策变量 cij xj yj 16维 非线性规划模型 NLP 非线性规划模型 NLP 例1 3 整数规划问题一般形式 整数线性规划 ILP 目标和约束均为线性函数整数非线性规划 NLP 目标或约束中存在非线性函数 整数规划问题的分类 纯 全 整数规划 PIP 决策变量均为整数
5、混合整数规划 MIP 决策变量有整数 也有实数 0 1规划决策变量只取0或1 取消整数规划中决策变量为整数的限制 松弛 对应的连续优化问题称为原问题的松弛问题 整数规划问题对应的松弛问题 基本思想 隐式地枚举一切可行解 分而治之 所谓分枝 就是逐次对解空间 可行域 进行划分 而所谓定界 是指对于每个分枝 或称子域 要计算原问题的最优解的下界 对极小化问题 这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分 也就是尽可能去掉一些明显的非最优点 避免完全枚举 分枝定界法 B B BranchandBound 整数线性规划的分枝定界算法 无约束优化 更多的优化问题 线性规划 非线性规划 网络
6、优化 组合优化 整数规划 不确定规划 多目标规划 目标规划 动态规划 连续优化 离散优化 从其他角度分类 应用广泛 生产和运作管理 经济与金融 图论和网络优化 目标规划问题 对策论 排队论 存储论 以及更加综合 更加复杂的决策问题等实际问题规模往往较大 用软件求解比较方便 3 LINDO LINGO软件简介 常用优化软件 1 LINDO LINGO软件2 MATLAB优化工具箱 Mathematic的优化功能3 SAS 统计分析 软件的优化功能4 EXCEL软件的优化功能5 其他 如CPLEX等 MATLAB优化工具箱能求解的优化模型 优化工具箱3 0 MATLAB7 0R14 连续优化 离散
7、优化 无约束优化 非线性极小fminunc 非光滑 不可微 优化fminsearch 非线性方程 组 fzerofsolve 全局优化暂缺 非线性最小二乘lsqnonlinlsqcurvefit 线性规划linprog 纯0 1规划bintprog一般IP 暂缺 非线性规划fminconfminimaxfgoalattainfseminf 上下界约束fminbndfminconlsqnonlinlsqcurvefit 约束线性最小二乘lsqnonneglsqlin 约束优化 二次规划quadprog LINDO公司软件产品简要介绍 美国芝加哥 Chicago 大学的LinusSchrage教授
8、于1980年前后开发 后来成立LINDO系统公司 LINDOSystemsInc 网址 LINDO LinearINteractiveandDiscreteOptimizer V6 1 LINDOAPI LINDOApplicationProgrammingInterface V4 1 LINGO LinearINteractiveGeneralOptimizer V10 0 What sBest SpreadSheete g EXCEL V8 0 演示 试用 版 高级版 超级版 工业版 扩展版 求解问题规模和选件不同 LINGO除了能用于求解线性规划和二次规划外 还可以用于非线性规划求解以及
9、一些线性和非线性方程 组 的求解等 LINGO软件的最大特色在于它允许优化模型中的决策变量为整数 而且执行速度快 LINGO内置了一种建立最优化模型的语言 可以简便地表达大规模问题 利用LINGO高效的求解器可快速求解并分析结果 LINGO可以求解 线性规划 二次规划 非线性规划 整数规划 图论及网络优化和排队论模型中的最优化问题等 LINDO LINGO软件能求解的模型 优化 线性规划 非线性规划 二次规划 连续优化 整数规划 LINDO LINGO 建模时需要注意的几个基本问题 1 尽量使用实数优化 减少整数约束和整数变量2 尽量使用光滑优化 减少非光滑约束的个数如 尽量少使用绝对值 符号
10、函数 多个变量求最大 最小值 四舍五入 取整函数等3 尽量使用线性模型 减少非线性约束和非线性变量的个数 如x y 5改为x 5y 4 合理设定变量上下界 尽可能给出变量初始值5 模型中使用的参数数量级要适当 如小于103 需要掌握的几个重要方面 LINGO 正确阅读求解报告 掌握集合 SETS 的应用 正确理解求解状态窗口 学会设置基本的求解选项 OPTIONS 掌握与外部文件的基本接口方法 1 2了解LINGO的菜单 新建 打开 保存 打印 剪切 复制 粘贴 取消 重做 查找 定位 匹配括号 求解 显示答案 模型图示 选项设置 窗口后置 关闭所有窗口 平铺窗口 在线帮助 上下文相关帮助 文
11、件菜单 编辑菜单 LINGO菜单 窗口菜单 帮助菜单 变量 约束 非零系数 内存使用量 已运行时间 求解器状态 扩展求解器状态 例1加工奶制品的生产计划 50桶牛奶 时间480h 至多加工100kgA1 制订生产计划 使每天获利最大 35元可买到1桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到30元 kg 应否改变生产计划 每天 问题 x1桶牛奶生产A1 x2桶牛奶生产A2 获利24 3x1 获利16 4x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利 约束条件 非负约束 线性规划模型 LP 时间480h 至多加工100kgA1
12、 基本模型 模型求解 软件实现 LINGO model max 72 x1 64 x2 milk x1 x2 50 time 12 x1 8 x2 480 cpct 3 x1 100 end Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplusDualPrice13360 0001 000000MILK0 00000048 00000TIME0 00
13、00002 000000CPCT40 000000 000000 20桶牛奶生产A1 30桶生产A2 利润3360元 LINGO的语法规定 1 求目标函数的最大值或最小值分别用MAX 或MIN 来表示 2 每个语句必须以分号 结束 每行可以有许多语句 语句可以跨行 3 变量名称必须以字母 A Z 开头 由字母 数字 0 9 和下划线所组成 长度不超过32个字符 不区分大小写 4 可以给语句加上标号 例如 OBJ MAX 200 X1 300 X2 LINGO的语法规定 5 以惊叹号 开头 以分号 结束的语句是注释语句 6 如果对变量的取值范围没有作特殊说明 则默认所有决策变量都非负 7 乘号
14、必须输入 不能省略 8 LINGO模型以语句 MODEL 开头 以 END 结束 对于比较简单的模型 这两个语句可以省略 模型求解 软件实现 LINGO model max 72 x1 64 x2 milk x1 x2 50 time 12 x1 8 x2 480 cpct 3 x1 100 end Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplu
15、sDualPrice13360 0001 000000MILK0 00000048 00000TIME0 0000002 000000CPCT40 000000 000000 20桶牛奶生产A1 30桶生产A2 利润3360元 模型求解 reducedcost值表示当该非基变量增加一个单位时 其他非基变量保持不变 目标函数减少的量 对max型问题 OBJECTIVEFUNCTIONVALUE1 3360 000VARIABLEVALUEREDUCEDCOSTX120 0000000 000000X230 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0
16、00000048 0000003 0 0000002 0000004 40 0000000 000000NO ITERATIONS 2 也可理解为 为了使该非基变量变成基变量 目标函数中对应系数应增加的量 结果解释 Globaloptimalsolutionfound Objectivevalue 3360 000Totalsolveriterations 2VariableValueReducedCostX120 000000 000000X230 000000 000000RowSlackorSurplusDualPrice13360 0001 000000MILK0 00000048 00000TIME0 0000002 000000CPCT40 000000 000000 model max 72 x1 64 x2 milk x1 x2 50 time 12 x1 8 x2 480 cpct 3 x1 100 end 三种资源 资源 剩余为零的约束为紧约束 有效约束 结果解释 Globaloptimalsolutionfound Objectivevalue 3360 000T
