数学规划与(Lingo) .ppt

第四章 数学规划（Lingo） 最短路问题 下料问题 露天矿的运输问题 钢管运输问题 二次规划(QP)问题 LINDO可求解二次规划(QP)问题，但输入方式较复杂，因为在LINDO中不许出现非线性表达式 需要为每一个实际约束增加一个对偶变量（LAGRANGE乘子），在实际约束前增加有关变量的一阶最优条件，转化为互补问题 “END”后面使用QCP命令指明实际约束开始的行号，然后才能求解 建议总是用LINGO解QP [注意]对QP和IP: 敏感性分析意义不大 状态窗口（LINDO Solver Status） 当前状态：已达最优解 迭代次数：18次 约束不满足的“量”(不是“约束个数”)：0 当前的目标值：94 最好的整数解：94 整数规划的界：93.5 分枝数：1 所用时间：0.00秒（太快了，还不到0.005秒） 刷新本界面的间隔:1(秒) 选项设置 Report/Statistics LINDO行命令、命令脚本文件 LINGO模型 — 例：选址问题 选址问题：NLP 边界 状态窗口 平面示意图 模型假设 卡车在一个班次中不应发生等待或熄火后再启动的情况； 在铲位或卸点处由两条路线以上造成的冲突问题面前，我们认为只要平均时间能完成任务，就认为不冲突。我们不排时地进行讨论； 空载与重载的速度都是28km/h，耗油相差很大； 卡车可提前退出系统，等等。 符号 xij ：从i铲位到j号卸点的石料运量 （车） 单位： 吨； cij ：从i号铲位到j号卸点的距离 公里； Tij :从i号铲位到号j卸点路线上运行一个周期平均时间 分； Aij ：从号铲位到号卸点最多能同时运行的卡车数 辆； Bij ：从号铲位到号卸点路线上一辆车最多可运行的次数 次； pi：i号铲位的矿石铁含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j号卸点任务需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 吨 cki ：i号铲位的铁矿石储量 万吨 cyi ：i号铲位的岩石储量 万吨 fi :描述第i号铲位是否使用的0-1变量，取1为使用；0为关闭。 优化模型 计算结果（LINGO软件） 计算结果（派车） 最大化产量 常用解法: 二次规划 先计算最小运费矩阵 两种运输方式（铁路／公路）混合最短路问题 是普通最短路问题的变种，需要自己设计算法 fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量 yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量 其他优化赛题 增加约束，缩小可行域，便于求解 原料钢管总根数下界： 特殊生产计划：对每根原料钢管 模式1：切割成4根4米钢管，需13根； 模式2：切割成1根5米和2根6米钢管，需10根； 模式3：切割成2根8米钢管，需8根。 原料钢管总根数上界：31 模式排列顺序可任定 钢管下料问题2 需求：4米50根，5米10根，6米20根，8米15根 每根原料钢管长19米 LINGO求解整数非线性规划模型 Local optimal solution found at iteration: 12211 Objective value: 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 R11 3.000000 0.000000 R12 2.000000 0.000000 R13 0.000000 0.000000 R21 0.000000 0.000000 R22 1.000000 0.000000 R23 0.000000 0.000000 R31