数学规划及软件2013.ppt

2020年2月21日星期五4时8分56秒 王文祥2013 7 数学规划模型 案例与软件求解 2020年2月21日星期五4时8分56秒 一 数学规划模型与优化软件简介 二 LINDO LINGO软件 Outline 四 LINGO建模语言 三 建模实例 2020年2月21日星期五4时8分56秒 数学规划是优化问题的一个分支 起始于20世纪30年代末 50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视 七八十年代是数学规划飞速发展时期 无论是从理论上还是算法方面都得到了进一步完善 时至今日数学规划仍然是运筹学领域中热点研究问题 从国内外的数学建模竞赛的试题中看 有一半以上的问题可用数学规划进行求解 一 数学规划模型与优化软件简介 2020年2月21日星期五4时8分56秒 数学规划模型的一般形式 可行域 三要素 决策变量 目标函数 约束条件 可行解 只满足约束 与最优解 取到最优值 受约束于 之意 2020年2月21日星期五4时8分56秒 数学规划类型 连续规划 全部决策变量取值均为连续数值 实数 离散规划 部分或全部决策变量只取离散数值 2020年2月21日星期五4时8分56秒 线性规划 LP 目标和约束均为线性函数非线性规划 NLP 目标或约束中存在非线性函数二次规划 QP 目标为二次函数 约束为线性整数规划 IP 决策变量 全部或部分 为整数整数线性规划 ILP 整数非线性规划 INLP 纯整数规划 PIP 混合整数规划 MIP 一般整数规划 0 1 整数 规划 连续规划 离散规划 数学规划 MathematicalProgramming 2020年2月21日星期五4时8分56秒 常用优化软件 LINDO LINGO软件MATLAB优化工具箱 mathematica优化程序包EXCEL软件的优化功能SAS 统计分析 软件的优化功能 2020年2月21日星期五4时8分56秒 LINDO公司软件产品简要介绍 美国芝加哥 Chicago 大学的LinusSchrage教授于1980年前后开发 后来成立LINDO系统公司 LINDOSystemsInc 网址 LINDO LinearInteractionandDiscreteOptimizerLINGO LinearInteractionGeneralOptimizer 2020年2月21日星期五4时8分56秒 LINDO和LINGO能求解的数学规划模型 LINGO LINDO 数学规划模型 线性规划 LP 非线性规划 NLP 二次规划 QP 连续规划 整数规划 IP 2020年2月21日星期五4时8分56秒 LINDO是专门用于求解数学规划的软件包 LINDO执行速度很快 易于方便输入 因此在数学 科研和工业界得到广泛应用 LINDO主要用于解线性规划 二次规划 也可以用于线性方程组的求解以及代数方程求根等 LINDO中包含了建模语言和许多常用的数学函数 包括大量概论函数 可供使用者建立规划问题时调用 一般用LINDO LinearInteractiveandDiscreteOptimizer 解决线性规划 二 LINDO LINGO软件简介 2020年2月21日星期五4时8分56秒 最大规模的模型的非零系数可以达到1 000 000个最大变量个数可以达到100 000个 最大目标函数和约束条件个数可以达到32000个最大整数变量个数可以达到100 000个LINDO6 1学生版至多可求解多达300个变量和150个约束的规划问题 2020年2月21日星期五4时8分56秒 1 求解线性规划和非线性规划问题2 模型输入简练直观3 运行速度快计算能力强4 内置建模语言提供内部函数较少语句直观描述大规模优化模型5 引入集合容易建模6 数据交换方便 与EXCEL和数据库 LINGO软件的主要功能和特点 2020年2月21日星期五4时8分56秒 例1简单的线性规划 LP 问题 在空白的模型窗口中输入这个LP模型 max2x 3yst4x 3y 103x 5y 12end 2020年2月21日星期五4时8分56秒 如图 2020年2月21日星期五4时8分56秒 LINDO程序有以下特点 程序以 MAX 或 MIN 开始 表示目标最大化 或最小化 问题 后面直接写目标函数表达式和约束表达式 目标函数和约束之间用 ST 分开 或用 s t 程序以 END 结束 END 也可以省略 系数与变量之间的乘号必须省略 系统对目标函数所在行自动生成行名 1 对约束默认的行名分别是 2 3 用户也可以自己输入行名 行名放在对应的约束之前 书写相当灵活 不必对齐 不区分字符的大小写 默认所有的变量都是非负的 所以不必输入非负约束 约束条件中的 可分别用 代替 一行中感叹号 后面的文字为是注释语句 可增强程序的可读性 不参与模型的建立 2020年2月21日星期五4时8分56秒 模型求解 用鼠标点击工具栏中的图标 或从菜单中选择Solve Solve Ctrl S 命令 LINDO首先开始编译这个模型 编译没有错误则开始求解 求解时会首先显示如右图所示的LINDO 求解器运行状态窗口 2020年2月21日星期五4时8分56秒 求解器运行状态窗口显示的相应信息及含义 2020年2月21日星期五4时8分56秒 2020年2月21日星期五4时8分56秒 紧接着弹出一对话框 询问你是否需要做灵敏性分析 DORANGE SENSITIVITY ANALYSIS 先选择 否 N 按钮 这个窗口就会关闭 然后 再把状态窗口也关闭 2020年2月21日星期五4时8分56秒 报告窗口 用鼠标选择 Window ReportsWindow 报告窗口 就可以查看该窗口的内容 2020年2月21日星期五4时8分56秒 输出结果表示的意思是 LPOPTIMUMFOUNDATSTEP2 表示单纯形法在两次迭代 旋转 后得到最优解 OBJECTIVEFUNCTIONVALUE1 7 454545 表示最优目标值为7 454545 注意 在LINDO中目标函数所在的行总是被认为是第1行 这就是这里 1 的含义 2020年2月21日星期五4时8分56秒 VALUE 给出最优解中各变量 VARIABLE 的值 X 1 272727 Y 1 636364 REDUCEDCOST 给出最优的单纯形表中目标函数行 第1行 中变量对应的系数 SLACKORSURPLUS 松驰或剩余 给出约束对应的松驰变量的值 第2 3行松驰变量均为0 说明对于最优解来讲 两个约束 第2 3行 均取等号 即都是紧约束 2020年2月21日星期五4时8分56秒 DUALPRICES 给出对偶价格 或影子价格 的值 表示最优解下 资源 增加1单位时 效益 的增量 第2 3行对偶价格分别为 090909 545455 NO ITERATIONS 2 表示用单纯形法进行了两次迭代 2020年2月21日星期五4时8分56秒 使用LINDO的一些注意事项 或 或 功能相同变量与系数间可有空格 甚至回车 但无运算符变量名以字母开头 不能超过8个字符变量名不区分大小写 包括LINDO中的关键字 目标函数所在行是第一行 第二行起为约束条件行号 行名 自动产生或人为定义 行名以 结束行中注有 符号的后面部分为注释 如 It sComment 在模型的任何地方都可以用 TITLE 对模型命名 最多72个字符 如 TITLEThisModelisonlyanExample 2020年2月21日星期五4时8分56秒 变量不能出现在一个约束条件的右端表达式中不接受括号 和逗号 等任何符号 例 400 X1 X2 需写为400X1 400X2表达式应化简 如2X1 3X2 4X1应写成 2X1 3X2缺省假定所有变量非负 可在模型的 END 语句后用 FREEname 将变量name的非负假定取消可在 END 后用 SUB 或 SLB 设定变量上下界例如 subx110 的作用等价于 x1 10 但用 SUB 和 SLB 表示的上下界约束不计入模型的约束 也不能给出其松紧判断和敏感性分析 使用LINDO的一些注意事项 2020年2月21日星期五4时8分56秒 14 END 后对0 1变量说明 INTn或INTname15 END 后对整数变量说明 GINn或GINname 使用LINDO的一些注意事项 16 简单错误的检查和避免 输入模型时可能会有某些输入错误 当问题规模较大时 要查找错误是比较困难的 在LINDO中有一些可帮助寻找错误的功能 其中之一就是菜单命令 Report Picture Alt 5 它的功能是可以将目标函数和约束表达式中的非零系数通过列表 或图形 显示出来 2020年2月21日星期五4时8分56秒 三个变量范围限定命令 FREE SUB SLB 的作用 求解如下的LP问题 这个模型中对变量x没有非负限制 对y有上限限制 对z有下限限制 用FREE SUB SLB三个命令可以实现这些功能 2020年2月21日星期五4时8分56秒 MAX2x 3y 4zS T con2 4x 3y 2z8con5 5x y z 2ENDfreex 说明 变量x没有非负限制suby20 说明 变量y的上界为20slbz30 说明 变量z的下界为30 具体输入如下 求解得到的结果 最大值为122 最优解为x 17 y 0 z 39 可以看出y的上界 20 在最优解中并没有达到 z的下界 30 也没有达到 因此模型中去掉 suby20 和 slbz30 两个语句 得到的结不变 但由于最优解中x的取值为负值 所以 freex 这个语句确实是不能少的 不妨试一下 去掉这个语句后效果会怎样 2020年2月21日星期五4时8分56秒 LINGO入门 设有线性规划模型如下 2020年2月21日星期五4时8分56秒 2020年2月21日星期五4时8分56秒 LINGO的语法规则 1 最大值MAX 最小值MIN 2 语句必须以分号 结束每行可多个语句语句可跨行3 变量名由字母 数字和下划线组成以字母开头长度不超32个字符不区分大小写4 默认决策变量非负其他要求可做说明5 模型以MODEL 开头 以END结束 此结构也可省略 6 注释以 开始 以 结束 7 可以用表示 2020年2月21日星期五4时8分56秒 程序语句输入的备注 LINGO总是根据 MAX 或 MIN 寻找目标函数 而除注释语句和TITLE语句外的其他语句都是约束条件 因此语句的顺序并不重要 限定变量取整数值的语句为 GIN X1 和 GIN X2 不可以写成 GIN 2 否则LINGO将把这个模型看成没有整数变量 LINGO中函数一律需要以 开头 其中整型变量函数 BIN GIN 和上下界限定函数 FREE SUB SLB 与LINDO中的命令类似 而且0 1变量函数是 BIN函数 2020年2月21日星期五4时8分56秒 一个简单的LINGO程序 例直接用LINGO来解如下二次规划问题 输入窗口如下 2020年2月21日星期五4时8分56秒 输出结果 运行菜单命令 LINGO Solve 最优整数解X 35 65 最大利润 11077 5 2020年2月21日星期五4时8分56秒 LINGO求解实例 例1 model max 2 x1 3 x2 2 x3 x4 x1 2 x2 3 x3 2 x4 5 x1 x2 2 x3 x4 10 End 2020年2月21日星期五4时8分56秒 Globaloptimalsolutionfoundatiteration 2Objectivevalue 18 33333VariableValueReducedCostX18 3333330 000000X20 0000000 6666667X30 0000004 333333X41 6666670 000000RowSlackorSurplusDualPrice118 333331 00000020 0000000 333333330 0000001 666667 运行结果如下 2020年2月21日星期五4时8分56秒 看完例1后 能解下面这个问题吗 例2 2020年2月21日星期五4时8分56秒 例3 model thisisanintegerprogrammingproblem max 4 x1 3 x2 4 x1 x2 10 2 x1 3 x2 8 gin x1 gin x2 end 2020年2月21日星期五4时8分56秒 Globaloptimalsolutionfoundatiteration 0Objectivevalue 11 00000VariableValueReducedCostX12 000000 4 000000X21 000000 3 000000RowSlackorSurplusDualPrice111 000001 00000021 0000000 00000031 0000000 000000 运行结果如下 2020年2月21日星期五4时8分56秒 例4 model thisisanuncontrainedoptimalproblem min 3 2 x1 2 1 2 x2 2 x1 x2 2 x1 free x1 free x2 end 2020年2月21日星期五4时8分56秒 Localoptimalsolutionfoundatiteration 73Objectivevalue 1 000000VariableValueReducedCostX10 99999950 000000X20 99999920 000000RowSlackorSurplusDualPrice1 1 000000 1 000000 运行结果如下 2020年2月21日星期五4时8分56秒 例5 model min 3 x1 2 x2 2 2 x3 2 x1 2 x2 2 x3 2 3 0 x1 x2 0 end 2020年2月21日星期五4时8分56秒 Localoptimalsolutionfoundatiteration 37Objectivevalue 6 000000VariableValueReducedCostX11 2128090 000000X21 2128090 000000X30 24122010 000000RowSlackorSurplusDualPrice1 6 000000 1 00000020 0000002 00000030 000000 2 425619 运行结果如下 2020年2月21日星期五4时8分56秒 例1加工奶制品的生产计划 50桶牛奶 时间480小时 至多加工100千克A1 制订生产计划 使每天获利最大 35元可买到1桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到30元 千克 应否改变生产计划 每天 三 建模实例 2020年2月21日星期五4时8分56秒 x1桶牛奶生产A1 x2桶牛奶生产A2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利 约束条件 非负约束 线性规划模型 LP 时间480小时 至多加工100千克A1 2020年2月21日星期五4时8分56秒 模型求解 软件实现 LINDO max72x1 64x2st2 x1 x2 503 12x1 8x2 4804 3x1 100end OBJECTIVEFUNCTIONVALUE1 3360 000VARIABLEVALUEREDUCEDCOSTX120 0000000 000000X230 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 00000048 0000003 0 0000002 0000004 40 0000000 000000NO ITERATIONS 2 DORANGE SENSITIVITY ANALYSIS No 20桶牛奶生产A1 30桶生产A2 利润3360元 2020年2月21日星期五4时8分56秒 结果解释 OBJECTIVEFUNCTIONVALUE1 3360 000VARIABLEVALUEREDUCEDCOSTX120 0000000 000000X230 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 00000048 0000003 0 0000002 0000004 40 0000000 000000NO ITERATIONS 2 原料无剩余 时间无剩余 加工能力剩余40 max72x1 64x2st2 x1 x2 503 12x1 8x2 4804 3x1 100end 三种资源 资源 剩余为零的约束为紧约束 有效约束 2020年2月21日星期五4时8分56秒 结果解释 OBJECTIVEFUNCTIONVALUE1 3360 000VARIABLEVALUEREDUCEDCOSTX120 0000000 000000X230 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 00000048 0000003 0 0000002 0000004 40 0000000 000000NO ITERATIONS 2 最优解下 资源 增加1单位时 效益 的增量 原料增加1单位 利润增长48 时间增加1单位 利润增长2 加工能力增长不影响利润 影子价格 35元可买到1桶牛奶 要买吗 35 48 应该买 聘用临时工人付出的工资最多每小时几元 2元 2020年2月21日星期五4时8分56秒 RANGESINWHICHTHEBASISISUNCHANGED OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172 00000024 0000008 000000X264 0000008 00000016 000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250 00000010 0000006 6666673480 00000053 33333280 0000004100 000000INFINITY40 000000 最优解不变时目标函数系数允许变化范围 DORANGE SENSITIVITY ANALYSIS Yes x1系数范围 64 96 x2系数范围 48 72 A1获利增加到30元 千克 应否改变生产计划 x1系数由24 3 72增加为30 3 90 在允许范围内 不变 约束条件不变 2020年2月21日星期五4时8分56秒 结果解释 RANGESINWHICHTHEBASISISUNCHANGED OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172 00000024 0000008 000000X264 0000008 00000016 000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250 00000010 0000006 6666673480 00000053 33333280 0000004100 000000INFINITY40 000000 影子价格有意义时约束右端的允许变化范围 原料最多增加10 时间最多增加53 35元可买到1桶牛奶 每天最多买多少 最多买10桶 目标函数不变 2020年2月21日星期五4时8分56秒 如果生产某一类型汽车 则至少要生产80辆 那么最优的生产计划应作何改变 例2汽车厂生产计划 汽车厂生产三种类型的汽车 已知各类型每辆车对钢材 劳动时间的需求 利润及工厂每月的现有量 制订月生产计划 使工厂的利润最大 2020年2月21日星期五4时8分56秒 设每月生产小 中 大型汽车的数量分别为x1 x2 x3 汽车厂生产计划 模型建立 线性规划模型 LP 2020年2月21日星期五4时8分56秒 模型求解 3 模型中增加条件 x1 x2 x3均为整数 重新求解 OBJECTIVEFUNCTIONVALUE1 632 2581VARIABLEVALUEREDUCEDCOSTX164 5161290 000000X2167 7419280 000000X30 0000000 946237ROWSLACKORSURPLUSDUALPRICES2 0 0000000 7311833 0 0000000 003226 结果为小数 怎么办 1 舍去小数 取x1 64 x2 167 算出目标函数值z 629 与LP最优值632 2581相差不大 2 试探 如取x1 65 x2 167 x1 64 x2 168等 计算函数值z 通过比较可能得到更优的解 但必须检验它们是否满足约束条件 为什么 2020年2月21日星期五4时8分56秒 IP可用LINDO直接求解 整数规划 IP gin3 表示 前3个变量为整数 等价于 ginx1ginx2ginx3 IP的最优解x1 64 x2 168 x3 0 最优值z 632 max2x1 3x2 4x3st1 5x1 3x2 5x3 600280 x1 250 x2 400 x3 60000endgin3 OBJECTIVEFUNCTIONVALUE1 632 0000VARIABLEVALUEREDUCEDCOSTX164 000000 2 000000X2168 000000 3 000000X30 000000 4 000000 模型求解 IP结果输出 2020年2月21日星期五4时8分56秒 LINDO中对0 1变量的限定 inty1inty2inty3 方法 引入0 1变量 化为整数规划 M为大的正数 可取1000 OBJECTIVEFUNCTIONVALUE1 610 0000VARIABLEVALUEREDUCEDCOSTX180 000000 2 000000X2150 000000 3 000000X30 000000 4 000000Y11 0000000 000000Y21 0000000 000000Y30 0000000 000000 若生产某类汽车 则至少生产80辆 求生产计划 x1 0或 80 2020年2月21日星期五4时8分56秒 应如何安排原油的采购和加工 例3原油采购与加工 市场上可买到不超过1500吨的原油A 购买量不超过500吨时的单价为10000元 吨 购买量超过500吨但不超过1000吨时 超过500吨的部分8000元 吨 购买量超过1000吨时 超过1000吨的部分6000元 吨 2020年2月21日星期五4时8分56秒 决策变量 目标函数 问题分析 利润 销售汽油的收入 购买原油A的支出难点 原油A的购价与购买量的关系较复杂 原油A的购买量 原油A B生产汽油甲 乙的数量 c x 购买原油A的支出 利润 千元 c x 如何表述 2020年2月21日星期五4时8分56秒 原油供应 约束条件 x 500吨单价为10千元 吨 500吨 x 1000吨 超过500吨的8千元 吨 1000吨 x 1500吨 超过1000吨的6千元 吨 目标函数 2020年2月21日星期五4时8分56秒 目标函数中c x 不是线性函数 是非线性规划 对于用分段函数定义的c x 一般的非线性规划软件也难以输入和求解 想办法将模型化简 用现成的软件求解 汽油含原油A的比例限制 约束条件 2020年2月21日星期五4时8分56秒 y1 y2 y3 1 以价格10 8 6 千元 吨 采购A 增加约束 0 1线性规划模型 可用LINDO求解 y1 y2 y3 0或1 OBJECTIVEFUNCTIONVALUE1 5000 000VARIABLEVALUEREDUCEDCOSTY11 0000000 000000Y21 0000002200 000000Y31 0000001200 000000X110 0000000 800000X210 0000000 800000X121500 0000000 000000X221000 0000000 000000X1500 0000000 000000X2500 0000000 000000X30 0000000 400000X1000 0000000 000000 购买1000吨原油A 与库存的500吨原油A和1000吨原油B一起 生产汽油乙 利润为5 000千元 x1 x2 x3 以价格10 8 6 千元 吨 采购A的吨数 2020年2月21日星期五4时8分56秒 例4 员工聘用方案 决策变量 周一至周日每天 新 聘用人数x1 x2 x7 目标函数 7天 新 聘用人数之和 约束条件 周一至周日每天需要人数 2020年2月21日星期五4时8分56秒 连续工作5天 设系统已进入稳态 聘用方案 整数规划模型 IP 2020年2月21日星期五4时8分56秒 首先在LINDO模型窗口输入模型 MINX1 X2 X3 X4 X5 X6 X7SUBJECTTOMON X1 X4 X5 X6 X7 50TUE X1 X2 X5 X6 X7 50WED X1 X2 X3 X6 X7 50THU X1 X2 X3 X4 X7 50FRI X1 X2 X3 X4 X5 80SAT X2 X3 X4 X5 X6 90SUN X3 X4 X5 X6 X7 90ENDGIN7 其中 GIN7 表示7个变量都是一般整数变量 仍然默认为取值是非负的 2020年2月21日星期五4时8分56秒 求解后状态窗口中与整数相关的三个域有了相关结果 BestIP 94 表示当前得到的最好的整数解的目标函数值为94 人 IPBound 93 5 表示该整数规划目标值的下界为93 5 人 Branches 1 表示分枝数为1 即在第1个分枝中就找到了最优解 2020年2月21日星期五4时8分56秒 OBJECTIVEFUNCTIONVALUE1 94 00000VARIABLEVALUEREDUCEDCOSTX10 0000001 000000X24 0000001 000000X340 0000001 000000X42 0000001 000000X534 0000001 000000X610 0000001 000000X74 0000001 000000ROWSLACKORSURPLUSDUALPRICESMON 0 0000000 000000TUE 2 0000000 000000WED 8 0000000 000000THU 0 0000000 000000FRI 0 0000000 000000SAT 0 0000000 000000SUN 0 0000000 000000NO ITERATIONS 18BRANCHES 1DETERM 1 000E0 求解结果的报告窗口如下 2020年2月21日星期五4时8分56秒 生产中通过切割 剪裁 冲压等手段 将原材料加工成所需大小 例5钢管和易拉罐下料 原料下料问题 按照工艺要求 确定下料方案 使所用材料最省 或利润最大 2020年2月21日星期五4时8分56秒 某钢管零售商从钢管厂进货 将钢管按照顾客的要求切割后售出 从钢管厂进货时得到的原料钢管都是19米长 1 现有一客户需要50根4米长 20根6米长和15根8米长的钢管 应如何下料最节省 2 零售商如果采用的不同切割模式太多 将会导致生产过程的复杂化 从而增加生产和管理成本 所以该零售商规定采用的不同切割模式不能超过3种 此外 该客户除需要1 中的三种钢管外 还需要10根5米长的钢管 应如何下料最节省 1 钢管下料 2020年2月21日星期五4时8分56秒 问题1 的求解 问题分析首先 应当确定哪些切割模式是可行的 所谓一个切割模式 是指按照客户需要在原料钢管上安排切割的一种组合 例如 我们可以将19米长的钢管切割成3根4米长的钢管 余料为7米显然 可行的切割模式是很多的 其次 应当确定哪些切割模式是合理的 通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸 在这种合理性假设下 切割模式一共有7种 如表所示 2020年2月21日星期五4时8分56秒 为满足客户需要 按照哪些种合理模式 每种模式切割多少根原料钢管 最为节省 合理切割模式 2 所用原料钢管总根数最少 钢管下料问题1 两种标准 1 原料钢管剩余总余量最小 2020年2月21日星期五4时8分56秒 xi 按第i种模式切割的原料钢管根数 i 1 2 7 约束 满足需求 决策变量 目标1 总余量 整数约束 xi为整数 2020年2月21日星期五4时8分56秒 模型求解 将整数线性规划模型 加上整数约束 输入LINDO如下 Title钢管下料 最小化余量 Min3x1 x2 3x3 3x4 x5 x6 3x7s t 4x1 3x2 2x3 x4 x5 50 x2 2x4 x5 3x6 20 x3 x5 2x7 15endgin7 2020年2月21日星期五4时8分56秒 求解可以得到最优解如下 OBJECTIVEFUNCTIONVALUE1 27 00000VARIABLEVALUEREDUCEDCOSTX10 0000003 000000X212 0000001 000000X30 0000003 000000X40 0000003 000000X515 0000001 000000X60 0000001 000000X70 0000003 000000 按模式2切割12根 按模式5切割15根 余料27米 2020年2月21日星期五4时8分56秒 目标2 总根数 钢管下料问题1 约束条件不变 xi为整数 2020年2月21日星期五4时8分56秒 将整数线性规划模型 加上整数约束 输入LINDO Title钢管下料 最小化钢管根数Minx1 x2 x3 x4 x5 x6 x7s t 4x1 3x2 2x3 x4 x5 50 x2 2x4 x5 3x6 20 x3 x5 2x7 15endgin7 模型求解 2020年2月21日星期五4时8分56秒 求解 可以得到最优解如下 OBJECTIVEFUNCTIONVALUE1 25 00000VARIABLEVALUEREDUCEDCOSTX10 0000001 000000X215 0000001 000000X30 0000001 000000X40 0000001 000000X55 0000001 000000X60 0000001 000000X75 0000001 000000 2020年2月21日星期五4时8分56秒 当余料没有用处时 通常以总根数最少为目标 最优解 x2 15 x5 5 x7 5 其余为0 最优值 25 按模式2切割15根 按模式5切割5根 按模式7切割5根 共25根 余料35米 虽余料增加8米 但减少了2根 与目标1的结果 共切割27根 余料27米 相比 2020年2月21日星期五4时8分56秒 钢管下料问题2 对大规模问题 用模型的约束条件界定合理模式 增加一种需求 5米10根 切割模式不超过3种 现有4种需求 4米50根 5米10根 6米20根 8米15根 用枚举法确定合理切割模式 过于复杂 决策变量 xi 按第i种模式切割的原料钢管根数 i 1 2 3 r1i r2i r3i r4i 第i种切割模式下 每根原料钢管生产4米 5米 6米和8米长的钢管的数量 2020年2月21日星期五4时8分56秒 满足需求 模式合理 每根余料不超过3米 整数非线性规划模型 钢管下料问题2 目标函数 总根数 约束条件 整数约束 xi r1i r2i r3i r4i i 1 2 3 为整数 2020年2月21日星期五4时8分56秒 增加约束 缩小可行域 便于求解 原料钢管总根数下界 特殊生产计划 对每根原料钢管模式1 切割成4根4米钢管 需13根 模式2 切割成1根5米和2根6米钢管 需10根 模式3 切割成2根8米钢管 需8根 原料钢管总根数上界 13 10 8 31 模式排列顺序可任定 需求 4米50根 5米10根 6米20根 8米15根 每根原料钢管长19米 2020年2月21日星期五4时8分56秒 将模型输入LINGO如下 model Title钢管下料 最小化钢管根数的LINGO模型 min x1 x2 x3 x1 r11 x2 r12 x3 r13 50 x1 r21 x2 r22 x3 r23 10 x1 r31 x2 r32 x3 r33 20 x1 r41 x2 r42 x3 r43 15 4 r11 5 r21 6 r31 8 r41 16 4 r12 5 r22 6 r32 8 r42 16 4 r13 5 r23 6 r33 8 r43 16 x1 x2 x3 26 x1 x2 x3 x2 x2 x3 gin x1 gin x2 gin x3 gin r11 gin r12 gin r13 gin r21 gin r22 gin r23 gin r31 gin r32 gin r33 gin r41 gin r42 gin r43 end 2020年2月21日星期五4时8分56秒 LINGO求解整数非线性规划模型 Localoptimalsolutionfoundatiteration 12211Objectivevalue 28 00000VariableValueReducedCostX110 000000 000000X210 000002 000000X38 0000001 000000R113 0000000 000000R122 0000000 000000R130 0000000 000000R210 0000000 000000R221 0000000 000000R230 0000000 000000R311 0000000 000000R321 0000000 000000R330 0000000 000000R410 0000000 000000R420 0000000 000000R432 0000000 000000 模式1 每根原料钢管切割成3根4米和1根6米钢管 共10根 模式2 每根原料钢管切割成2根4米 1根5米和1根6米钢管 共10根 模式3 每根原料钢管切割成2根8米钢管 共8根 原料钢管总根数为28根 2020年2月21日星期五4时8分56秒 问题某公司采用一套冲压设备生产一种罐装饮料的易拉罐 这种易拉罐是用镀锡板冲压制成的 易拉罐为圆柱形 包括罐身 上盖和下底 罐身高10cm 上盖和下底的直径均为5cm 该公司使用两种不同规格的镀锡板原料 规格1的镀锡板为正方形 边长24cm 规格2的镀锡板为长方形 长 宽分别为32cm和28cm 由于生产设备和生产工艺的限制 对于规格1的镀锡板原料 只可以按照模式1 模式2或模式3进行冲压 对于规格2的镀锡板原料只能按照模式4进行冲压 使用模式1 模式2 模式3 模式4进行每次冲压所需要的时间分别为1 5s 2s 1s 3s 2 易拉罐下料 2020年2月21日星期五4时8分56秒 该工厂每周工作40小时 每周可供使用的规格1 规格2的镀锡板原料分别为5万张和2万张 目前每只易拉罐的利润为0 10元 原料余料损失为0 001元 平方厘米 如果周末有罐身 上盖或下底不能配套组装成易拉罐出售 也看作是原料余料损失 问工厂应如何安排每周的生产 2020年2月21日星期五4时8分56秒 板材规格2 长方形 32 28cm 2万张 问题分析 罐身高10cm 上盖 下底直径均5cm 板材规格1 正方形 边长24cm 5万张 2020年2月21日星期五4时8分56秒 模式1 正方形边长24cm 问题分析 计算各种模式下的余料损失 上 下底直径d 5cm 罐身高h 10cm 模式1余料损失242 10 d2 4 dh 222 6cm2 2020年2月21日星期五4时8分56秒 问题分析 目标 易拉罐利润扣除原料余料损失后的净利润最大 约束 每周工作时间不超过40小时 原料数量 规格1 模式1 3 5万张 规格2 模式4 2万张 罐身和底 盖的配套组装 注意 不能装配的罐身 上下底也是余料 决策变量 xi 按照第i种模式的生产张数 i 1 2 3 4 y1 一周生产的易拉罐个数 y2 不配套的罐身个数 y3 不配套的底 盖个数 模型建立 2020年2月21日星期五4时8分56秒 目标 约束条件 时间约束 原料约束 模型建立 y1 易拉罐个数 y2 不配套的罐身 y3 不配套的底 盖 每只易拉罐利润0 10元 余料损失0 001元 cm2 罐身面积 dh 157 1cm2底盖面积 d2 4 19 6cm2 40小时 2020年2月21日星期五4时8分56秒 约束条件 配套约束 y1 易拉罐个数 y2 不配套的罐身 y3 不配套的底 盖 虽然xi和y1 y2 y3应是整数 但是因生产量很大 可以把它们看成实数 从而用线性规划模型处理 2020年2月21日星期五4时8分56秒 LINDO发出警告信息 数据之间的数量级差别太大 建议进行预处理 缩小数据之间的差别 模型求解 OBJECTIVEFUNCTIONVALUE1 4298 337VARIABLEVALUEREDUCEDCOSTY1160250 0000000 000000X10 0000000 000050X240125 0000000 000000X33750 0000000 000000X420000 0000000 000000Y20 0000000 223331Y30 0000000 036484 2020年2月21日星期五4时8分56秒 模型中数据不平衡的警告信息 2020年2月21日星期五4时8分56秒 输入LINDO 易拉罐下料 均衡数据 Max0 100y1 0 2226x1 0 1833x2 0 2618x3 0 1695x4 0 1571y2 0 0196y3s t 1 5x1 2 0 x2 1 0 x3 3 0 x4 010 x1 4x2 16x3 5x4 2y1 0 x1 2x2 4x4 y1 y2 010 x1 4x2 16x3 5x4 2y1 y3 0 将所有决策变量扩大10000倍 xi 万张 yi 万件 2020年2月21日星期五4时8分56秒 模式2生产40125张 模式3生产3750张 模式4生产20000张 共产易拉罐160250个 罐身和底 盖无剩余 净利润为4298元 OBJECTIVEFUNCTIONVALUE1 0 4298337VARIABLEVALUEREDUCEDCOSTY116 0250000 000000X10 0000000 000050X24 0125000 000000X30 3750000 000000X42 0000000 000000Y20 0000000 223331Y30 0000000 036484 求解得到 2020年2月21日星期五4时8分56秒 下料问题的建模 确定下料模式 构造优化模型 规格不太多 可枚举下料模式 建立整数线性规划模型 否则要构造整数非线性规划模型 求解困难 可用缩小可行域的方法进行化简 但要保证最优解的存在 一维问题 如钢管下料 二维问题 如易拉罐下料 具体问题具体分析 比较复杂 2020年2月21日星期五4时8分56秒 LINGO模型 例 选址问题 某公司有6个建筑工地 位置坐标为 ai bi 单位 公里 水泥日用量di 单位 吨 假设 料场和工地之间有直线道路 2020年2月21日星期五4时8分56秒 用例中数据计算 最优解为 总吨公里数为136 2 线性规划模型 决策变量 cij 料场j到工地i的运量 12维 2020年2月21日星期五4时8分56秒 选址问题 NLP 2 改建两个新料场 需要确定新料场位置 xj yj 和运量cij 在其它条件不变下使总吨公里数最小 决策变量 cij xj yj 16维 非线性规划模型 2020年2月21日星期五4时8分56秒 LINGO模型的构成 4个段 集合段 SETSENDSETS 数据段 DATAENDDATA 初始段 INITENDINIT 目标与约束段 局部最优 89 8835 吨公里 LP 移到数据段 2020年2月21日星期五4时8分56秒 边界 2020年2月21日星期五4时8分56秒 四 LINGO的建模语言 以运输问题逐步分析 6个仓库向8个小贩供应同一种货物 如何运 总运输费用最小 注 每个仓库可以向每个小贩供货 一共48个可能运货路线 仓库货存量 小贩需求量 每条路线的单位运输费用三个表如下 2020年2月21日星期五4时8分56秒 仓库货存量 capacity 2020年2月21日星期五4时8分56秒 小贩需求量 demand 2020年2月21日星期五4时8分56秒 每单位货物运输费用表 cost 2020年2月21日星期五4时8分56秒 demand j表示第j个小贩的需求量capacity i表示第i个仓库的库存量cost i j表示从第i个仓库到第j个小贩的单位运输费用 volume i j表示从第i个仓库到第j个小贩的运输量 2020年2月21日星期五4时8分56秒 数学模型可表示如下 2020年2月21日星期五4时8分56秒 当然目标函数可以如下输入 min 6 volume 1 1 2 volume 1 2 6 volume 1 3 1 volume 6 6 4 volume 6 7 3 volume 6 8 2020年2月21日星期五4时8分56秒 但是较大模型如果像上面那样输入又费时 又容易出错 这就需要LINGO的建模语言 2020年2月21日星期五4时8分56秒 LINGO的建模语言优点 1 可以用类似于标准数学符号的方式表示你的模型 2 可以用一个紧凑的语句表示一系列约束 3 数据可独立于模型 LINGO可以从文本文件 电子数据表 数据库中读取数据 2020年2月21日星期五4时8分56秒 LINGO模型的构成 5个段 目标函数与约束条件段集合段 sets endsets 数据段 data enddata 初始段 init endinit 计算段 calc endcalc Lingo建模语言的重点和难点是 对集合概念的理解和正确使用 2020年2月21日星期五4时8分56秒 为什么使用集合 集合是LINGO建模语言的基础 是LINGO程序设计最强有力的基本构件 借助于集合 能够用一个单一的 长的 简明的复合公式表示一系列相似的约束 从而可以快速方便地表达规模较大的模型 2020年2月21日星期五4时8分56秒 什么是集合 集合是一群相联系的对象 比如仓库 小贩 运输路线 这些对象也称为集合的成员 每个集合成员可能有一个或多个与之有关联的特征 我们把这些特征称为属性 属性值可以预先给定 也可以是未知的 有待于LINGO求解 2020年2月21日星期五4时8分56秒 从我们的数学模型看需要三个集合 1 仓库 6个成员 货存量 2 小贩 8个成员 需求量 3 运输路线 48个成员 单位运费和运货量 2020年2月21日星期五4时8分56秒 LINGO有两种类型的集合 原始集合 primitiveset 由一些最基本的对象组成的 派生集 derivedset 用一个或多个其它集来定义的 也就是说 它的成员来自于其它已存在的集 2020年2月21日星期五4时8分56秒 下面我们学习集合定义部分 1 以sets 开始 以endsets结束 sets endsets 2020年2月21日星期五4时8分56秒 2 原始集合定义法 setname member list attribute list setname是集合的名字 member list是成员列表 各成员之间可用空格或逗号分隔 attribute list是集合成员所具有的属性列表 多个属性之间用逗号分隔 原始集合的member list attribute list是可选项 2020年2月21日星期五4时8分56秒 仓库和小贩的集合可如下定义 sets warehouses w1w2w3w4w5w6 capacity vendors v1 v2 v3 v4 v5 v6 v7 v8 demand endsets 2020年2月21日星期五4时8分56秒 仓库和小贩的集合也可如下定义 sets warehouses w1 w6 capacity vendors v1 v8 demand endsets 2020年2月21日星期五4时8分56秒 3 派生集合定义法 setname parent set list member list attribute list parent set list是父集合名列表 2020年2月21日星期五4时8分56秒 48条运输路线集合定义 links warehouses vendors cost volume 2020年2月21日星期五4时8分56秒 三个集合定义如下 sets warehouses wh1 wh6 capacity vendors v1 v8 demand links warehouses vendors cost volume endsets 2020年2月21日星期五4时8分56秒 运输问题的三个集合说明 这段代码定义了4个属性值 在接下来的模型中就可以使用属性值capacity 1 capacity 2 capacity 6 demand 1 demand 2 demand 8 cost 1 1 cost 1 2 cost 1 8 cost 2 1 cost 2 2 cost 2 8 cost 6 1 cost 6 2 cost 6 8 volume的引用同cost 2020年2月21日星期五4时8分56秒 4 集合成员过滤 trucks 1 100 capacity heavy duty trucks capacity 1是集合索引号放置器 如果有两个父集合 就是 1 2 2020年2月21日星期五4时8分56秒 下面我们学习数据定义 以data 开始 以enddata结束 data enddata 2020年2月21日星期五4时8分56秒 例如 设有如下集合 sets set1 a b c x y endsets 如果想赋值x 1 1 x 2 2 x 3 3 y 1 4 y 2 5 y 3 6 则数据段可以为 2020年2月21日星期五4时8分56秒 data x 1 2 3 y 456 enddata data x y 142536 enddata 多个数据之间可用逗号或空格分隔 2020年2月21日星期五4时8分56秒 若成员属性值相同 数据段定义如下 data x 3 所有成员的x 3 y 6 所有成员的y 6 enddata 2020年2月21日星期五4时8分56秒 也可以在运行时输入属性值 data x 运行时输入所有成员的x值 y 6 enddata 2020年2月21日星期五4时8分56秒 运输问题的数据部分 data capacity 60 55 51 43 41 52 demand 3537223241324338 2020年2月21日星期五4时8分56秒 cost 626742594953858252197433767392712395726555228143 enddata 2020年2月21日星期五4时8分56秒 sets sett x y endsetsdata sett x y a14b25c36 enddata sets sett a b c x y endsetsdata x 123 y 456 enddata 集合成员可以在数据段定义 2020年2月