数学规划及软件2013.ppt

* 王文祥 2013.7 数学规规划模型、案例与 软软件求解 Date * 一一. . 数学规划模型与优化软件简介数学规划模型与优化软件简介 二二. LINDO/LINGO. LINDO/LINGO软件软件 Outline 四四. . LINGO LINGO建模语言建模语言 三三. . 建模实例建模实例 Date * 数学规划是优化问题的一个分支，起始 于20世纪30年代末，50年代与60年代发展成 为一个完整的分支并受到数学界和社会各界 的重视。七八十年代是数学规划飞速发展时 期，无论是从理论上还是算法方面都得到了 进一步完善。时至今日数学规划仍然是运筹 学领域中热点研究问题。从国内外的数学建 模竞赛的试题中看，有一半以上的问题可用 数学规划进行求解。 一一. . 数学规划模型与优化软件简介数学规划模型与优化软件简介 Date * 约 束 条 件 决策变量 数学规划模型的一般形式数学规划模型的一般形式 目标函数 可行域 三要素：决策变量；目标函数；约束条件 可行解（只满足约束）与最优解(取到最优值) “受约束于”之意 Date * 数学规划类型 连续规划连续规划: : 全部决策变量取值均全部决策变量取值均 为连续数值为连续数值 ( (实数实数) ) 离散规划离散规划: : 部分或全部决策变量部分或全部决策变量 只取离散数值只取离散数值 Date * 线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划 连 续 规 划 离 散 规 划 数学规划 ( Mathematical Programming ) Date * 常用优化软件常用优化软件 1.1.LINDOLINDO/ /LINGOLINGO软件软件 2.2.MATLABMATLAB优化工具箱优化工具箱 / /mathematicamathematica优化程序包优化程序包 3.3.EXCELEXCEL软件的优化功能软件的优化功能 4.4.SAS(SAS(统计分析统计分析) )软件的优化功能软件的优化功能 Date * LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于 1980年前后开发, 后来成立 LINDO系统公司（ LINDO Systems Inc.）， 网址： LINDO: Linear Interaction and Discrete Optimizer LINGO: Linear Interaction General Optimizer Date * LINDO和LINGO能求解的数学规划模型 LINGO LINDO 数学规划模型 线性规划 (LP) 非线性规划 (NLP) 二次规划 (QP) 连续规划 整数规划(IP) Date * LINDO 是专门用于求解数学规划的软件包。 LINDO 执行速度很快、易于方便输入，因此在 数学、科研和工业界得到广泛应用。 LINDO 主要用于解线性规划、二次规划。也可 以用于线性方程组的求解以及代数方程求根等。 LINDO 中包含了建模语言和许多常用的数学函 数（包括大量概论函数），可供使用者建立规划 问题时调用。 一般用LINDO（Linear Interactive and Discrete Optimizer）解决线性规划 二二. . LINDO/LINGO LINDO/LINGO软件简介软件简介 Date * 最大规模的模型的非零系数可以达到1,000,000 个 最大变量个数可以达到100,000个，最大目标函 数和约束条件个数可以达到32000个 最大整数变量个数可以达到100,000个 LINDO 6 .1 学生版至多可求解多达300 个变量 和150 个约束的规划问题 Date * 1.求解线性规划和非线性规划问题 2.模型输入简练直观 3.运行速度快 计算能力强 4.内置建模语言 提供内部函数 较少语句 直观描述大规模优化模型 5.引入集合 容易建模 6.数据交换方便(与EXCEL和数据库) LINGOLINGO软件的主要功能和特点软件的主要功能和特点 Date * 例1 简单的线性规划（LP）问题： 在空白的模型窗口中输入这个LP模型： max 2x+3y st 4x+3y=”可分别用“”代替。 一行中感叹号“！”后面的文字为是注释语句，可增强程序 的可读性，不参与模型的建立。 Date * 模型求解： 用鼠标点击工具栏中的图标 ， 或从菜单中选择Solve|Solve（Ctrl+S）命令 LINDO首先开始编译这个 模型，编译没有错误则开 始求解； 求解时会首先显示如右图 所示的LINDO “求解器运行状态窗口 ”。 Date * 求解器运行状态窗口显示的相应信息及含义： 名称含义义 Status 当前状态 显显示当前求解状态态：“Optimal”表示已 达到最优优解；其他可能的显显示还还有三个 ：Feasible(可行解), Infeasible(不可行 ), Unbounded(最优值优值 无界)。 Iterations 迭代次数 显显示迭代次数：“2”表示经过经过 了2次迭代 。 Infeasibility 不可行性 约约束不满满足的量(即各个约约束条件不满满 足的“数量”的和)：“0”表示解是可行的 。 Objective 当前目标值 显显示目标标函数当前的值值：7.45455。 Best IP 整数规划当前最 佳目标值 显显示整数规规划当前的最佳目标值标值 ： “N/A” （No Answer）表示无答案或无 意义义，因为这为这 个模型中没有整数变变量， 不是整数规规划（IP）。 Date * 名称含义 IP Bound 整数规划的界 显显示整数规规划的界（对对最大化问题显问题显 示上界；对对最小化问题问题 ，显显示下界） Branches分枝数显显示分枝定界算法已经计经计 算的分枝数： Elapsed Time 所用时间 显显示计计算所用时间时间 （秒）：“0.00”说说明 计计算太快了，用时还时还 不到0.005秒。 UpdateInterval 刷新本界面时间 间隔 显显示和控制刷新本界面的时间间时间间 隔： “1”表示1秒；用户户可以直接在界面上修 改这这个时间间时间间 隔。 Interrupt Solver 中断求解程序 当模型规规模比较较大时时，求解时间时间 会很 长长，可以在程序运行过过程中用鼠标标点击击 该该按钮终钮终 止计计算。 Close关闭该该按钮钮是关闭闭状态态窗口，并不终终止计计 算 Date * 紧接着弹出一对话框，询问你是否需要做灵敏性分析 （DO RANGE (SENSITIVITY) ANALYSIS? ）先选 择“否（N）”按钮，这个窗口就会关闭。然后，再把 状态窗口也关闭。 Date * 报告窗口 用鼠标选择“Window | Reports Window”（报告窗口）， 就可以查看该窗口的内容 Date * 输出结果表示的意思是： “LP OPTIMUM FOUND AT STEP2” 表示单纯形法在两次迭代（旋转）后得到最优解。 “OBJECTIVE FUNCTION VALUE 1) 7.454545 ” 表示最优目标值为7.454545.（注意：在LINDO中目标函数 所在的行总是被认为是第1行，这就是这里“1）”的含义） 。 Date * “VALUE” 给出最优解中各变量(VARIABLE)的值: X =1.272727, Y =1.636364. “REDUCED COST” 给出最优的单纯形表中目标函数行（ 第1行）中变量对应的系数. “SLACK OR SURPLUS（松驰或剩余）” 给出约束对应的 松驰变量的值: 第2、3行松驰变量均为0, 说明对于最优解来 讲，两个约束（第2、3行）均取等号，即都是紧约束。 Date * “DUAL PRICES” 给出对偶价格（或影子价格）的值:表示 最优解下“资源”增加1单位时“效益”的增量。 第2、3行对偶价格分别为 .090909，.545455。 “NO. ITERATIONS= 2” 表示用单纯形法进行了两次迭代 。 Date * 使用LINDO的一些注意事项 “”（或“=”（或“ 8 con5) -5x - y - z 2 END free x ! 说明：变量x没有非负限制 sub y 20 ! 说明：变量y的上界为20 slb z 30 ! 说明：变量z的下界为30 具体输入如下： 求解得到的结果：最大值为122，最优解为x=-17，y=0，z=39。 可以看出y的上界（20）在最优解中并没有达到，z的下界（30）也没有达到 ，因此模型中去掉“sub y 20”和“slb z 30”两个语句，得到的结不变。 但由于最优解中x的取值为负值，所以“free x”这个语句确实是不能少的。不 妨试一下，去掉这个语句后效果会怎样？ Date * LINGOLINGO入门入门 设有线性规划模型如下： Date * LP问题在lindo和lingo中不同的输入形式 Lindo: max 2x+3y st 4x+3y表示= Date * 程序语句输入的备注： LINGO总是根据“MAX=”或“MIN=”寻找目标函数，而 除注释语句和TITLE语句外的其他语句都是约束条件， 因此语句的顺序并不重要 。 限定变量取整数值的语句为“GIN(X1)”和“GIN(X2)” ，不可以写成“GIN(2)”，否则LINGO将把这个模型看 成没有整数变量。 LINGO中函数一律需要以“”开头，其中整型变量函数 （BIN、GIN）和上下界限定函数（FREE、 SUB、SLB）与LINDO中的命令类似。而且0/1变量 函数是BIN函数。 Date * 一个简单的LINGO程序 例 直接用LINGO来解如下二次规划问题： 输入窗口如下： Date * 输出结果： 运行菜单命令“LINGO|Solve” 最优整数解 X=(35，65) 最大利润=11077.5 Date * 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 Date * Global optimal solution found at iteration: 2 Objective value: 18.33333 Variable Value Reduced Cost X1 8.333333 0.000000 X2 0.000000 0.6666667 X3 0.000000 4.333333 X4 1.666667 0.000000 Row Slack or Surplus Dual Price 1 18.33333 1.000000 2 0.000000 0.3333333 3 0.000000 1.666667 运行结果如下: Date * 看完例1后,能解下面这个问题吗? 例 2 Date * 例 3 model: !this is an integer programming problem; max=4*x1+3*x2; 4*x1+x2=0; end Date * Local optimal solution found at iteration: 37 Objective value: -6.000000 Variable Value Reduced Cost X1 1.212809 0.000000 X2 1.212809 0.000000 X3 0.2412201 0.000000 Row Slack or Surplus Dual Price 1 -6.000000 -1.000000 2 0.000000 2.000000 3 0.000000 -2.425619 运行结果如下: Date * 例1 加工奶制品的生产计划 1桶 牛奶 3千克A1 12小时 8小时 4千克A2 或 获利24元/千克 获利16元/千克 50桶牛奶 时间480小时 至多加工100千克A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/千克，应否改变生产计划？ 每天： 三、建模实例三、建模实例 Date * 1桶 牛奶 3千克A1 12小时 8小时 4千克A2 或 获利24元/千克 获利16元/千克 x1桶牛奶生产A1 x2桶牛奶生产A2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利 约束条件 非负约束 线性 规划 模型 (LP) 时间480小时 至多加工100千克A1 50桶牛奶 每天 Date * 模型求解 软件实现 LINDO max 72x1+64x2 st 2)x1+x20 y=1 Date * 例4: 员工聘用方案 决策变量：周一至周日每天(新)聘用人数 x1, x2,x7 目标函数：7天(新)聘用人数之和 约束条件：周一至周日每天需要人数 Date * 连续工作5天周一工作的应是(上)周四至周一聘用的 设系统已进入稳态聘用方案 整数规划 模型(IP) Date * 首先在LINDO模型窗口输入模型 : MIN X1 + X2 + X3 + X4 + X5 + X6 + X7 SUBJECT TO MON) X1 + X4 + X5 + X6 + X7 = 50 TUE) X1 + X2 + X5 + X6 + X7 = 50 WED) X1 + X2 + X3 + X6 + X7 = 50 THU) X1+ X2 + X3 + X4 +X7 = 50 FRI) X1 + X2 + X3 + X4 - X5 = 80 SAT) X2 + X3 + X4 - X5 + X6 = 90 SUN) X3 + X4 - X5 + X6 + X7 = 90 END GIN 7 其中“GIN 7”表示7个变量都是一般整数变量。 （仍然默认为取值是非负的） Date * 求解后状态窗口中与整数相关的三个域有了相关结果: “Best IP ：94”表示当前 得到的最好的整数解的目 标函数值为94（人）。 “IP Bound ：93.5” 表示 该整数规划目标值的下界 为93.5 （人）。 “Branches ：1”表示分枝 数为1（即在第1个分枝中 就找到了最优解）。 Date * OBJECTIVE FUNCTION VALUE 1) 94.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 4.000000 1.000000 X3 40.000000 1.000000 X4 2.000000 1.000000 X5 34.000000 1.000000 X6 10.000000 1.000000 X7 4.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES MON) 0.000000 0.000000 TUE) 2.000000 0.000000 WED) 8.000000 0.000000 THU) 0.000000 0.000000 FRI) 0.000000 0.000000 SAT) 0.000000 0.000000 SUN) 0.000000 0.000000 NO. ITERATIONS= 18 BRANCHES= 1 DETERM.= 1.000E 0 求解结果的报告窗口如下： Date * 生产中通过切割、剪裁、冲压等 手段，将原材料加工成所需大小 例5 钢管和易拉罐下料 原料下料问题 按照工艺要求，确定下料方案， 使所用材料最省，或利润最大 Date * 某钢管零售商从钢管厂进货，将钢管按照顾客的要 求切割后售出。从钢管厂进货时得到的原料钢管都 是19米长。 1) 现有一客户需要50根4米长、20根6米长和15根8 米长的钢管。应如何下料最节省？ 2) 零售商如果采用的不同切割模式太多，将会导 致生产过程的复杂化，从而增加生产和管理成本， 所以该零售商规定采用的不同切割模式不能超过3 种。此外，该客户除需要1）中的三种钢管外，还 需要10根5米长的钢管。应如何下料最节省？ 1、钢管下料 Date * 问题1）的求解 问题分析 首先，应当确定哪些切割模式是可行 的。所谓一个切割模式，是指按照客户需要在原 料钢管上安排切割的一种组合。例如，我们可以 将19米长的钢管切割成3根4米长的钢管，余料为7 米显然，可行的切割模式是很多的。 其次，应当确定哪些切割模式是合理的。通 常假设一个合理的切割模式的余料不应该大于 或等于客户需要的钢管的最小尺寸。在这种合 理性假设下，切割模式一共有7种，如表所示。 Date * 为满足客户需要，按照哪些种合理模式，每种模式 切割多少根原料钢管，最为节省？ 合理切割模式 2. 所用原料钢管总根数最少 模式 4米钢管根数6米钢管根数8米钢管根数余料(米) 14003 23101 32013 41203 51111 60301 70023 钢管下料问题1 两种 标准 1. 原料钢管剩余总余量最小 Date * xi 按第i 种模式切割的原料钢管根数(i=1,2,7) 约束满足需求 决策变量 目标1（总余量） 模 式 4米 根数 6米 根数 8米 根数 余 料 14003 23101 32013 41203 51111 60301 70023 需 求 502015 整数约束： xi 为整数 Date * 模型求解 将整数线性规划模型（加上整数约束）输入LINDO如下： Title 钢管下料 - 最小化余量 Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7 Date * 求解可以得到最优解如下： OBJECTIVE FUNCTION VALUE 1) 27.00000 VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 按模式2切割12根,按模式5切割15根，余料27米 Date * 目标2（总根数） 钢管下料问题1 约束条 件不变 xi 为整数 Date * 将整数线性规划模型（加上整数约束）输入LINDO ： Title 钢管下料 - 最小化钢管根数 Min x1 + x2 + x3 + x4 + x5 + x6 + x7 s.t. 4x1 + 3x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15 end gin 7 模型求解 Date * 求解，可以得到最优解如下： OBJECTIVE FUNCTION VALUE 1) 25.00000 VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 Date * 当余料没有用处时，通常以总根数最少为目标 最优解：x2=15, x5=5, x7=5, 其余为0； 最优值：25。 按模式2切割15根， 按模式5切割5根， 按模式7切割5根， 共25根，余料35米 虽余料增加8米，但减少了2根 与目标1的结果“共切割27根，余料27米” 相比 Date * 钢管下料问题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米长的钢管的数量 Date * 满足需求 模式合理：每根 余料不超过3米 整数非线性规划模型 钢管下料问题2 目标函数（总根数） 约束 条件 整数约束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数 Date * 增加约束，缩小可行域，便于求解 原料钢管总根数下界： 特殊生产计划：对每根原料钢管 模式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米 Date * 将模型输入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 Date * 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 1.000000 0.000000 R32 1.000000 0.000000 R33 0.000000 0.000000 R41 0.000000 0.000000 R42 0.000000 0.000000 R43 2.000000 0.000000 模式1：每根原料钢管切割成3 根4米和1根6米钢管，共10根； 模式2：每根原料钢管切割成2 根4米、1根5米和1根6米钢管， 共10根； 模式3：每根原料钢管切割成2 根8米钢管，共8根。 原料钢管总根数为28根。 Date * 问题 某公司采用一套冲压设备生产一种罐装饮料 的易拉罐，这种易拉罐是用镀锡板冲压制成的。易拉 罐为圆柱形，包括罐身、上盖和下底，罐身高10cm， 上盖和下底的直径均为5cm。该公司使用两种不同规 格的镀锡板原料：规格1的镀锡板为正方形，边长 24cm；规格2的镀锡板为长方形，长、宽分别为32cm 和28cm。由于生产设备和生产工艺的限制，对于规格 1的镀锡板原料，只可以按照模式1、模式2或模式3进 行冲压；对于规格2的镀锡板原料只能按照模式4进行 冲压。使用模式1、模式2、模式3、模式4进行每次冲 压所需要的时间分别为1.5s、2s、1s、3s。 2、易拉罐下料 Date * 该工厂每周工作40小时，每周可供使用的规格1 、规格2的镀锡板原料分别为5万张和2万张。目前每只 易拉罐的利润为0.10元，原料余料损失为0.001元/平方 厘米（如果周末有罐身、上盖或下底不能配套组装成 易拉罐出售，也看作是原料余料损失）。 问工厂应如 何安排每周的生产？ Date * 板材规格2： 长方形， 3228cm， 2万张。 问题分析 模式1：1.5秒 模式2：2秒模式3：1秒 模式4：3秒 上盖 下底 罐 身 罐身高10cm， 上盖、下底直 径均5cm。 板材规格1： 正方形，边长 24cm，5万张。 Date * 罐身个数底、盖 个数 余料损失 （cm2） 冲压时间 （秒） 模式1110222.61.5 模式224183.32 模式3016261.81 模式445169.53 模式1: 正方形 边长24cm 问题分析计算各种模式下的余料损失 上、下底直径d=5cm， 罐身高h=10cm。 模式1 余料损失 242-10d2/4 - dh=222.6 cm2 Date * 问题分析 目标:易拉罐利润扣除原料余料损失后的净利润最大 约束：每周工作时间不超过40小时； 原料数量：规格1（模式1 3）5万张， 规格2（模式4）2万张； 罐身和底、盖的配套组装 。 注意：不能装配的罐身、上下底也是余料 决策 变量 xi 按照第i 种模式的生产张数(i=1,2,3,4)； y1 一周生产的易拉罐个数； y2 不配套的罐身个数； y3 不配套的底、盖个数。 模型建立 Date * 目标 约束 条件 时间约束 原料约束 产量余料时间 x1222.61.5 x2183.32 x3261.81 x4169.53 模型建立 y1 易拉罐个数；y2 不配套的罐身； y3 不配套的底、盖。 每只易拉罐利润0.10元， 余料损失0.001元 / cm2 罐身面积dh=157.1 cm2 底盖面积d2/4=19.6 cm2 (40小时) Date * 约束条件 配套约束 y1 易拉罐个数；y2 不配套的罐身； y3 不配套的底、盖。 罐身底、盖 110 24 016 45 产量 x1 x2 x3 x4 虽然xi和y1，y2，y3应是整数，但是因生产量很大， 可以把它们看成实数，从而用线性规划模型处理 。 Date * LINDO发出警告信息：“数据之间的数量级差别太 大，建议进行预处理，缩小数据之间的差别” 模型求解 OBJECTIVE FUNCTION VALUE 1) 4298.337 VARIABLE VALUE REDUCED COST Y1 160250.000000 0.000000 X1 0.000000 0.000050 X2 40125.000000 0.000000 X3 3750.000000 0.000000 X4 20000.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 Date * 模型中数据不平衡的警告信息 Date * 输入LINDO: ! 易拉罐下料：均衡数据 Max 0.100y1 - 0.2226x1 - 0.1833x2 - 0.2618x3 - 0.1695 x4 - 0.1571y2 - 0.0196y3 s.t. 1.5x1 + 2.0x2 + 1.0x3 +3.0x4 =0 10x1 + 4x2 + 16x3+ 5x4 - 2y1 =0 x1 + 2x2 + 4x4 - y1 - y2 =0 10x1 + 4x2 + 16x3+ 5x4 - 2y1 - y3=0 将所有决策变量扩大10000倍（xi 万张，yi 万件） Date * 模式2生产40125张，模式3生产3750张， 模式4生产20000张， 共产易拉罐160250个(罐身和底、盖无剩 余)，净利润为4298元 OBJECTIVE FUNCTION VALUE 1) 0.4298337 VARIABLE VALUE REDUCED COST Y1 16.025000 0.000000 X1 0.000000 0.000050 X2 4.012500 0.000000 X3 0.375000 0.000000 X4 2.000000 0.000000 Y2 0.000000 0.223331 Y3 0.000000 0.036484 求解得到： Date * 下料问题的建模 确定下料模式 构造优化模型 规格不太多，可枚举下料模式，建立整数线性规划 模型，否则要构造整数非线性规划模型，求解困难 ，可用缩小可行域的方法进行化简，但要保证最优 解的存在。 一维问题（如钢管下料） 二维问题（如易拉罐下料） 具体问题具体分析（比较复杂 ） Date * LINGO模型 例：选址问题 某公司有6个建筑工地，位置坐标为(ai, bi) (单位：公里), 水泥日用量di (单位：吨） 假设：料场 和工地之间 有直线道路 Date * 用例中数 据计算， 最优解为 总吨公里数为总吨公里数为136.2136.2 线性规划模型 决策变量：ci j ( 料场j到工地i的 运量）12维 Date * 选址问题：NLP 2）改建两个新料场，需要确定新料场位置(xj,yj)和 运量cij ，在其它条件不变下使总吨公里数最小。 决策变量： ci j，(xj,yj)16维 非线性规划模型 Date * LINGO模型的构成：4个段 集合段（SETS ENDSETS） 数据段（DATA ENDDATA） 初始段（INIT ENDINIT） 目标与 约束段 局部最优：89.8835(吨公里 ) LP：移到数据段 Date * 边界 Date * 四、四、LINGOLINGO的的建模语言建模语言 以运输问题逐步分析 6 6个仓库向个仓库向8 8个小贩供应同一种货物，个小贩供应同一种货物， 如何运如何运, ,总运输费用最小？总运输费用最小？ 注：每个仓库可以向每个小贩供货注：每个仓库可以向每个小贩供货 ， 一共一共4848个可能运货路线。个可能运货路线。 仓库货存量、小贩需求量、每条路线仓库货存量、小贩需求量、每条路线 的单位运输费用三个表如下：的单位运输费用三个表如下： Date * 仓库货存量：仓库货存量：capacitycapacity 仓库号仓库号货存量货存量 w1w1 6060 w2w2 5555 w3w3 5151 w4w4 4343 w5w5 4141 w6w6 5252 Date * 小贩需求量：小贩需求量：demanddemand 小贩代号小贩代号 货物需求量货物需求量 v1v1 3535 v2v2 3737 v3v3 2222 v4v4 3232 v5v5 4141 v6v6 3232 v7v7 4343 v8v8 3838 Date * 每单位货物运输费用表：每单位货物运输费用表：costcost 小 仓 贩 库 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 w1 62674259 w2 49538582 w3 52197433 w4 76739271 w5 23957265 w6 55228143 Date * demand_ j demand_ j 表示第表示第j j个小个小 贩的需求量贩的需求量 capacity_icapacity_i 表示第表示第i i个仓库个仓库 的库存量的库存量 cost_icost_i_ j _ j 表示从第表示从第i i个仓个仓 库到第库到第j j个小贩的单位运输费个小贩的单位运输费 用用 已 知 数 量 决策变量 volume_ivolume_i_ j _ j 表示从第表示从第i i个仓库到个仓库到 第第j j个小贩的运输量个小贩的运输量 Date * 数学模型可表示如下：数学模型可表示如下： Date * 当然目标函数可以如下输入: 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; Date * 但是较大模型如果像上面那样 输入又费时，又容易出错！ 这就需要LINGO的建模语言 Date * LINGOLINGO的的建模语言建模语言优点优点: : 1)1)可以用可以用类似于标准数学符号类似于标准数学符号的方式的方式 表示你的模型；表示你的模型； 2)2)可以用可以用一个紧凑的语句一个紧凑的语句表示表示一系列一系列 约束约束。 3)3)数据可独立于模型数据可独立于模型：LINGOLINGO可以从可以从 文本文件、电子数据表、数据库中读文本文件、电子数据表、数据库中读 取数据。取数据。 Date * LINGO模型的构成：5个段 目标函数与约束条件段目标函数与约束条件段 集合段（集合段（sets: sets: endsetsendsets） 数据段（数据段（data: data: enddataenddata） 初始段（初始段（init: init: endinitendinit） 计算段（计算段（calccalc： endcalcendcalc） LingoLingo建模语言的重点和难点是：建模语言的重点和难点是： 对对集合集合概念的理解和正确使用概念的理解和正确使用 Date * 为什么使用集合 集合是集合是LINGOLINGO建模语言的基础建模语言的基础 ，是，是LINGOLINGO程序设计最强有力的基程序设计最强有力的基 本构件。借助于集合，能够本构件。借助于集合，能够用一个用一个 单一的、长的、简明的复合公式表单一的、长的、简明的复合公式表 示一系列相似的约束示一系列相似的约束，从而可以快，从而可以快 速方便地表达规模较大的模型。速方便地表达规模较大的模型。 Date * 什么是集合什么是集合 集合是一群相联系的对象，比集合是一群相联系的对象，比 如如 仓库、小贩仓库、小贩、运输路线，运输路线，这些对象这些对象 也也 称为集合的称为集合的成员成员。每个集合成员可。每个集合成员可 能能 有一个或多个与之有关联的特征，有一个或多个与之有关联的特征， 我我 们把这些特征称为们把这些特征称为属性属性。 属性值可以预先给定，也可以属性值可以预先给定，也可以 是是 未知的，有待于未知的，有待于LINGOLINGO求解。求解。 Date * 从我们的数学模型看需要三个集合：从我们的数学模型看需要三个集合： （1 1）仓库仓库- -6 6个成员个成员- -货存量货存量 （2 2）小贩小贩- -8 8个成员个成员- -需求量需求量 （3 3）运输路线运输路线- -4848个成员个成员 - -单位运费单位运费和和运货量运货量 Date * LINGO有两种类型的集合 原始集合原始集合(primitive set)(primitive set)：由一：由一 些些 最基本的对象组成的。最基本的对象组成的。 派生集派生集(derived set): (derived set): 用一个或用一个或 多多 个其它集来定义的，也就是说，它个其它集来定义的，也就是说，它 的成员来自于其它已存在的集。的成员来自于其它已存在的集。 Date * *下面我们学习集合定义部分下面我们学习集合定义部分* 1. 1. 以以sets:sets:开始，以开始，以endsetsendsets结束结束 ； sets:sets: endsetsendsets Date * 2. 2. 原始集合定义法：原始集合定义法： setnamesetname / /member_listmember_list/ / : :attribute_listattribute_list ; 。setnamesetname是集合的名字；是集合的名字； 。member_listmember_list是成员列表是成员列表, ,各成员之间可各成员之间可 用用 空格空格或或逗号逗号分隔；分隔； 。attribute_listattribute_list是集合成员所具有的属性是集合成员所具有的属性 列列 表，多个属性之间用表，多个属性之间用逗号逗号分隔；分隔； 。原始集合的。原始集合的member_list, member_list, attribute_listattribute_list是可选项；是可选项； Date * * *仓库和小贩的集合可如下定义仓库和小贩的集合可如下定义* * sets:sets: warehouseswarehouses / w1 w2 w3 / w1 w2 w3 w4 w5 w6 / w4 w5 w6 /: : capacitycapacity; ; vendorsvendors / / v1,v2,v3,v4,v5,v6, v1,v2,v3,v4,v5,v6, v7,v8 / v7,v8 / : demand: demand; ; endsetsendsets Date * * *仓库和小贩的集合也可如下定义仓库和小贩的集合也可如下定义* * sets:sets: warehouseswarehouses / w1w6/:/ w1w6/: capacitycapacity; ; vendorsvendors / v1v8 /:/ v1v8 /: demanddemand; ; endsetsendsets Date * 3. 3. 派生集合定义法：派生集合定义法： setnamesetname ( (parent_set_listparent_set_list) ) / /member_listmember_list/ : :attribute_listattribute_list ; ; parent_set_listparent_set_list是父集合名列表是父集合名列表 Date * *48条运输路线集合定义* linkslinks(warehouses,vendors(warehouses,vendors) ) : cost, volume : cost, volume； Date * * *三个集合定义如下三个集合定义如下* * sets:sets: warehouseswarehouses / wh1wh6 /: / wh1wh6 /: capacitycapacity; ; vendorsvendors / v1v8 /: / v1v8 /: demanddemand; ; linkslinks( warehouses, vendors): ( warehouses, vendors): costcost，volumevolume； endsetsendsets Date * 运输问题的三个集合说明：运输问题的三个集合说明： 这段代码定义了这段代码定义了4 4个属性值，在接下来个属性值，在接下来 的模型中就可以使用属性值的模型中就可以使用属性值 capacity(1),capacity(2),capacity(6); capacity(1),capacity(2),capacity(6); demand(1),demand(2) ,demand(8);demand(1),demand(2) ,demand(8); cost(1,1), cost(1,2)