数学规划与软件ppt课件.ppt

2022年11月12日星期六2时38分31秒,王文祥 2013.7,数学规划模型、案例与软件求解,2022年11月12日星期六2时38分31秒,一. 数学规划模型与优化软件简介,二. LINDO/LINGO软件,Outline,四. LINGO建模语言,三. 建模实例,2022年11月12日星期六2时38分31秒,数学规划是优化问题的一个分支，起始于20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有一半以上的问题可用数学规划进行求解。,一. 数学规划模型与优化软件简介,2022年11月12日星期六2时38分31秒,数学规划模型的一般形式,可行域,三要素：决策变量；目标函数；约束条件,可行解（只满足约束）与最优解(取到最优值),“受约束于”之意,2022年11月12日星期六2时38分31秒,数学规划类型,连续规划: 全部决策变量取值均 为连续数值 (实数)离散规划: 部分或全部决策变量 只取离散数值,2022年11月12日星期六2时38分31秒,线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划,连续规划,离散规划,数学规划 ( Mathematical Programming ),2022年11月12日星期六2时38分31秒,常用优化软件,LINDO/LINGO软件MATLAB优化工具箱/mathematica优化程序包EXCEL软件的优化功能SAS(统计分析)软件的优化功能,2022年11月12日星期六2时38分31秒,LINDO 公司软件产品简要介绍,美国芝加哥(Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http:/,LINDO: Linear Interaction and Discrete OptimizerLINGO: Linear Interaction General Optimizer,2022年11月12日星期六2时38分31秒,LINDO和LINGO能求解的数学规划模型,LINGO,LINDO,数学规划模型,线性规划(LP),非线性规划(NLP),二次规划(QP),连续规划,整数规划(IP),2022年11月12日星期六2时38分31秒,LINDO 是专门用于求解数学规划的软件包。LINDO 执行速度很快、易于方便输入，因此在数学、科研和工业界得到广泛应用。LINDO 主要用于解线性规划、二次规划。也可以用于线性方程组的求解以及代数方程求根等。LINDO 中包含了建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。一般用LINDO（Linear Interactive and Discrete Optimizer）解决线性规划,二. LINDO/LINGO软件简介,2022年11月12日星期六2时38分31秒,最大规模的模型的非零系数可以达到1,000,000个最大变量个数可以达到100,000个，最大目标函数和约束条件个数可以达到32000个最大整数变量个数可以达到100,000个 LINDO 6 .1 学生版至多可求解多达300 个变量和150 个约束的规划问题,2022年11月12日星期六2时38分31秒,1.求解线性规划和非线性规划问题2.模型输入简练直观3.运行速度快 计算能力强4.内置建模语言 提供内部函数 较少语句直观描述大规模优化模型5.引入集合 容易建模6.数据交换方便(与EXCEL和数据库),LINGO软件的主要功能和特点,2022年11月12日星期六2时38分31秒,例1 简单的线性规划（LP）问题：,在空白的模型窗口中输入这个LP模型：,max 2x+3yst 4x+3y=10 3x+5y12end,2022年11月12日星期六2时38分31秒,如图：,2022年11月12日星期六2时38分31秒,LINDO程序有以下特点：, 程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写目标函数表达式和约束表达式； 目标函数和约束之间用“ST”分开；（或用“s.t.”） 程序以“END”结束（ “END” 也可以省略）。 系数与变量之间的乘号必须省略。 系统对目标函数所在行自动生成行名“1）”,对约束默认的行名分别是“2)” “3)”，用户也可以自己输入行名；行名放在对应的约束之前。 书写相当灵活，不必对齐，不区分字符的大小写。 默认所有的变量都是非负的, 所以不必输入非负约束。 约束条件中的“=”可分别用“”代替。 一行中感叹号“！”后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。,2022年11月12日星期六2时38分31秒,模型求解：,用鼠标点击工具栏中的图标 ，或从菜单中选择Solve|Solve（Ctrl+S）命令,LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所示的LINDO“求解器运行状态窗口 ”。,2022年11月12日星期六2时38分31秒,求解器运行状态窗口显示的相应信息及含义：,2022年11月12日星期六2时38分31秒,2022年11月12日星期六2时38分31秒,紧接着弹出一对话框，询问你是否需要做灵敏性分析（DO RANGE (SENSITIVITY) ANALYSIS? ）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。,2022年11月12日星期六2时38分31秒,报告窗口,用鼠标选择“Window | Reports Window”（报告窗口），就可以查看该窗口的内容,2022年11月12日星期六2时38分31秒,输出结果表示的意思是：,“LP OPTIMUM FOUND AT STEP2”表示单纯形法在两次迭代（旋转）后得到最优解。,“OBJECTIVE FUNCTION VALUE 1) 7.454545 ”表示最优目标值为7.454545.（注意：在LINDO中目标函数所在的行总是被认为是第1行，这就是这里“1）”的含义）。,2022年11月12日星期六2时38分31秒,“VALUE” 给出最优解中各变量(VARIABLE)的值: X =1.272727, Y =1.636364.,“REDUCED COST” 给出最优的单纯形表中目标函数行（第1行）中变量对应的系数.,“SLACK OR SURPLUS（松驰或剩余）” 给出约束对应的松驰变量的值: 第2、3行松驰变量均为0, 说明对于最优解来讲，两个约束（第2、3行）均取等号，即都是紧约束。,2022年11月12日星期六2时38分31秒,“DUAL PRICES” 给出对偶价格（或影子价格）的值:表示最优解下“资源”增加1单位时“效益”的增量。 第2、3行对偶价格分别为 .090909，.545455。 “NO. ITERATIONS= 2” 表示用单纯形法进行了两次迭代。,2022年11月12日星期六2时38分31秒,使用LINDO的一些注意事项,“”（或“=”（或“=”）功能相同变量与系数间可有空格(甚至回车), 但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义。行名以“）”结束行中注有“!”符号的后面部分为注释。如: ! Its Comment.在模型的任何地方都可以用“TITLE” 对模型命名（最多72个字符），如： TITLE This Model is only an Example,2022年11月12日星期六2时38分31秒,变量不能出现在一个约束条件的右端表达式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1+X2)需写为400X1+400X2表达式应化简，如2X1+3X2- 4X1应写成 -2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消可在 “END”后用“SUB” 或“SLB” 设定变量上下界 例如： “sub x1 10”的作用等价于“x1=10” 但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。,使用LINDO的一些注意事项,2022年11月12日星期六2时38分31秒,14. “END”后对0-1变量说明：INT n 或 INT name15. “END”后对整数变量说明：GIN n 或 GIN name,使用LINDO的一些注意事项,16. 简单错误的检查和避免： 输入模型时可能会有某些输入错误. 当问题规模较大时, 要查找错误是比较困难的。在LINDO 中有一些可帮助寻找错误的功能，其中之一就是菜单命令“Report | Picture（Alt+5）” , 它的功能是可以将目标函数和约束表达式中的非零系数通过列表（或图形）显示出来。,2022年11月12日星期六2时38分31秒,三个变量范围限定命令(FREE、SUB、SLB)的作用,求解如下的LP问题：,这个模型中对变量x没有非负限制，对y有上限限制，对z有下限限制。用FREE、SUB、SLB三个命令可以实现这些功能。,2022年11月12日星期六2时38分31秒,MAX 2x 3y + 4zS.T.con2) 4 x + 3y + 2z 8con5) -5x - y - z 2ENDfree x ! 说明：变量x没有非负限制sub y 20 ! 说明：变量y的上界为20slb z 30 ! 说明：变量z的下界为30,具体输入如下：,求解得到的结果：最大值为122，最优解为x=-17，y=0，z=39。可以看出y的上界（20）在最优解中并没有达到，z的下界（30）也没有达到，因此模型中去掉“sub y 20”和“slb z 30”两个语句，得到的结不变。但由于最优解中x的取值为负值，所以“free x”这个语句确实是不能少的。不妨试一下，去掉这个语句后效果会怎样？,2022年11月12日星期六2时38分31秒,LINGO入门,设有线性规划模型如下：,2022年11月12日星期六2时38分31秒,2022年11月12日星期六2时38分31秒,LINGO的语法规则,1.最大值MAX=,最小值MIN=2.语句必须以分号”;”结束 每行可多个语句 语句可跨行3.变量名由字母、数字和下划线组成 以字母开头 长度 不超32个字符 不区分大小写4.默认决策变量非负 其他要求可做说明5.模型以MODEL：开头，以END结束(此结构也可省略）6.注释以 ！开始，以 ; 结束；7.可以用表示=,2022年11月12日星期六2时38分31秒,程序语句输入的备注：,LINGO总是根据“MAX=”或“MIN=”寻找目标函数，而除注释语句和TITLE语句外的其他语句都是约束条件，因此语句的顺序并不重要 。限定变量取整数值的语句为“GIN(X1)”和“GIN(X2)”，不可以写成“GIN(2)”，否则LINGO将把这个模型看成没有整数变量。LINGO中函数一律需要以“”开头，其中整型变量函数（BIN、GIN）和上下界限定函数（FREE、SUB、SLB）与LINDO中的命令类似。而且0/1变量函数是BIN函数。,2022年11月12日星期六2时38分31秒,一个简单的LINGO程序,例 直接用LINGO来解如下二次规划问题：,输入窗口如下：,2022年11月12日星期六2时38分31秒,输出结果：,运行菜单命令“LINGO|Solve”,最优整数解X=(35，65),最大利润=11077.5,2022年11月12日星期六2时38分31秒,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,2022年11月12日星期六2时38分31秒,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,运行结果如下:,2022年11月12日星期六2时38分31秒,看完例1后,能解下面这个问题吗?,例 2,2022年11月12日星期六2时38分31秒,例 3,model:!this is an integer programming problem;max=4*x1+3*x2;4*x1+x2=10;2*x1+3*x2=8;gin(x1); gin(x2);end,2022年11月12日星期六2时38分31秒,Global optimal solution found at iteration: 0 Objective value: 11.00000 Variable Value Reduced Cost X1 2.000000 -4.000000 X2 1.000000 -3.000000 Row Slack or Surplus Dual Price 1 11.00000 1.000000 2 1.000000 0.000000 3 1.000000 0.000000,运行结果如下:,2022年11月12日星期六2时38分31秒,例 4,model:!this is an uncontrained optimal problem;min=3/2*x12+1/2*x22-x1*x2-2*x1;free(x1); free(x2);end,2022年11月12日星期六2时38分31秒,Local optimal solution found at iteration: 73 Objective value: -1.000000 Variable Value Reduced Cost X1 0.9999995 0.000000 X2 0.9999992 0.000000 Row Slack or Surplus Dual Price 1 -1.000000 -1.000000,运行结果如下:,2022年11月12日星期六2时38分31秒,例 5,model:min=-3*x12-x22-2*x32;x12+x22+x32-3=0;-x1+x2=0;end,2022年11月12日星期六2时38分31秒,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,运行结果如下:,2022年11月12日星期六2时38分31秒,例1 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100千克A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/千克，应否改变生产计划？,每天：,三、建模实例,2022年11月12日星期六2时38分31秒,x1桶牛奶生产A1,x2桶牛奶生产A2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100千克A1,2022年11月12日星期六2时38分31秒,模型求解,软件实现,LINDO,max 72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生产A1, 30桶生产A2，利润3360元。,2022年11月12日星期六2时38分31秒,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,原料无剩余,时间无剩余,加工能力剩余40,max 72x1+64x2st2) x1+x2503) 12x1+8x24804) 3x1100end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,2022年11月12日星期六2时38分31秒,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位, 利润增长48,时间增加1单位, 利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,2022年11月12日星期六2时38分31秒,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),2022年11月12日星期六2时38分31秒,结果解释,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶,(目标函数不变),2022年11月12日星期六2时38分31秒,如果生产某一类型汽车，则至少要生产80辆， 那么最优的生产计划应作何改变？,例2 汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。,制订月生产计划，使工厂的利润最大。,2022年11月12日星期六2时38分31秒,设每月生产小、中、大型汽车的数量分别为x1, x2, x3,汽车厂生产计划,模型建立,线性规划模型(LP),2022年11月12日星期六2时38分31秒,模型求解,3） 模型中增加条件：x1, x2, x3 均为整数，重新求解。,OBJECTIVE FUNCTION VALUE 1) 632.2581VARIABLE VALUE REDUCED COST X1 64.516129 0.000000 X2 167.741928 0.000000 X3 0.000000 0.946237 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.731183 3) 0.000000 0.003226,结果为小数，怎么办？,1）舍去小数：取x1=64，x2=167，算出目标函数值z=629，与LP最优值632.2581相差不大。,2）试探：如取x1=65，x2=167；x1=64，x2=168等，计算函数值z，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,2022年11月12日星期六2时38分31秒,IP可用LINDO直接求解,整数规划(IP),“gin 3”表示“前3个变量为整数”，等价于：gin x1gin x2gin x3,IP 的最优解x1=64，x2=168，x3=0，最优值z=632,max 2x1+3x2+4x3st1.5x1+3x2+5x3600280 x1+250 x2+400 x360000endgin 3,OBJECTIVE FUNCTION VALUE 1) 632.0000VARIABLE VALUE REDUCED COST X1 64.000000 -2.000000 X2 168.000000 -3.000000 X3 0.000000 -4.000000,模型求解,IP 结果输出,2022年11月12日星期六2时38分31秒,LINDO中对0-1变量的限定：int y1int y2int y3,方法：引入0-1变量，化为整数规划,M为大的正数，可取1000,OBJECTIVE FUNCTION VALUE 1) 610.0000VARIABLE VALUE REDUCED COST X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000,若生产某类汽车，则至少生产80辆，求生产计划。,x1=0 或 80,2022年11月12日星期六2时38分31秒,应如何安排原油的采购和加工 ？,例3 原油采购与加工,市场上可买到不超过1500吨的原油A： 购买量不超过500吨时的单价为10000元/吨； 购买量超过500吨但不超过1000吨时，超过500吨的 部分8000元/吨； 购买量超过1000吨时，超过1000吨的部分6000元/吨。,2022年11月12日星期六2时38分31秒,决策变量,目标函数,问题分析,利润：销售汽油的收入 - 购买原油A的支出 难点：原油A的购价与购买量的关系较复杂,原油A的购买量,原油A, B生产汽油甲,乙的数量,c(x) 购买原油A的支出,利润(千元),c(x)如何表述？,2022年11月12日星期六2时38分31秒,原油供应,约束条件,x 500吨单价为10千元/吨； 500吨 x 1000吨，超过500吨的8千元/吨；1000吨 x 1500吨，超过1000吨的6千元/吨。,目标函数,2022年11月12日星期六2时38分31秒,目标函数中c(x)不是线性函数，是非线性规划； 对于用分段函数定义的c(x)，一般的非线性规划软件也难以输入和求解； 想办法将模型化简，用现成的软件求解。,汽油含原油A的比例限制,约束条件,2022年11月12日星期六2时38分31秒,y1, y2 , y3=1 以价格10, 8, 6(千元/吨)采购A,增加约束,0-1线性规划模型，可用LINDO求解,y1,y2,y3 =0或1,OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 1000.000000 0.000000,购买1000吨原油A，与库存的500吨原油A和1000吨原油B一起，生产汽油乙，利润为5,000千元 。,x1 , x2 , x3 以价格10, 8, 6(千元/吨)采购A的吨数,2022年11月12日星期六2时38分31秒,例4: 员工聘用方案,决策变量：周一至周日每天(新)聘用人数 x1, x2,x7,目标函数：7天(新)聘用人数之和,约束条件：周一至周日每天需要人数,2022年11月12日星期六2时38分31秒,连续工作5天,设系统已进入稳态,聘用方案,整数规划模型(IP),2022年11月12日星期六2时38分31秒,首先在LINDO模型窗口输入模型 :,MIN X1 + X2 + X3 + X4 + X5 + X6 + X7SUBJECT TOMON) 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 = 90ENDGIN 7,其中“GIN 7”表示7个变量都是一般整数变量。 （仍然默认为取值是非负的）,2022年11月12日星期六2时38分31秒,求解后状态窗口中与整数相关的三个域有了相关结果:,“Best IP ：94”表示当前得到的最好的整数解的目标函数值为94（人）。“IP Bound ：93.5” 表示该整数规划目标值的下界为93.5 （人）。“Branches ：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。,2022年11月12日星期六2时38分31秒,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,求解结果的报告窗口如下：,2022年11月12日星期六2时38分31秒,生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小,例5 钢管和易拉罐下料,原料下料问题,按照工艺要求，确定下料方案，使所用材料最省，或利润最大,2022年11月12日星期六2时38分31秒,某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19米长。 1)现有一客户需要50根4米长、20根6米长和15根8米长的钢管。应如何下料最节省？ 2)零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要1）中的三种钢管外，还需要10根5米长的钢管。应如何下料最节省？,1、钢管下料,2022年11月12日星期六2时38分31秒,问题1）的求解,问题分析 首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将19米长的钢管切割成3根4米长的钢管，余料为7米显然，可行的切割模式是很多的。,其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有7种，如表所示。,2022年11月12日星期六2时38分31秒,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2. 所用原料钢管总根数最少,钢管下料问题1,两种标准,1. 原料钢管剩余总余量最小,2022年11月12日星期六2时38分32秒,xi 按第i 种模式切割的原料钢管根数(i=1,2,7),约束,满足需求,决策变量,目标1（总余量）,整数约束： xi 为整数,2022年11月12日星期六2时38分32秒,模型求解,将整数线性规划模型（加上整数约束）输入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 = 15endgin 7,2022年11月12日星期六2时38分32秒,求解可以得到最优解如下：,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米,2022年11月12日星期六2时38分32秒,目标2（总根数）,钢管下料问题1,约束条件不变,xi 为整数,2022年11月12日星期六2时38分32秒,将整数线性规划模型（加上整数约束）输入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 = 15endgin 7,模型求解,2022年11月12日星期六2时38分32秒,求解，可以得到最优解如下：,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,2022年11月12日星期六2时38分32秒,当余料没有用处时，通常以总根数最少为目标,最优解：x2=15, x5=5, x7=5, 其余为0；最优值：25。,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米” 相比,2022年11月12日星期六2时38分32秒,钢管下料问题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米长的钢管的数量,2022年11月12日星期六2时38分32秒,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数（总根数）,约束条件,整数约束： xi ,r1i, r2i, r3i, r4i (i=1,2,3)为整数,2022年11月12日星期六2时38分32秒,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管模式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米,2022年11月12日星期六2时38分32秒,将模型输入LINGO如下：,model:Title 钢管下料 - 最小化钢管根数的LINGO模型;min=x1+x2+x3;x