数学规划及软件2013

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,10/1/2024 9:41 AM,王文祥,2013.7,数学规划模型、案例与,软件求解,10/1/2024,一,.,数学规划模型与优化软件简介,二,. LINDO/LINGO,软件,Outline,四,.,LINGO,建模语言,三,.,建模实例,10/1/2024,数学规划,是优化问题的一个分支，起始于,20,世纪,30,年代末，,50,年代与,60,年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有一半以上的问题可用数学规划进行求解。,一,.,数学规划模型与优化软件简介,10/1/2024,约束条件,决策变量,数学规划模型的一般形式,目标函数,可行域,三要素：,决策变量,；,目标函数,；,约束条件,可行解（只满足约束）与最优解,(,取到最优值,),“受约束于”,之意,10/1/2024,数学规划类型,连续规划,:,全部决策变量取值均,为连续数值,(,实数,),离散规划,:,部分或全部决策变量,只取离散数值,10/1/2024,线性规划,(LP),目标和约束均为线性函数,非线性规划,(NLP),目标或约束中存在非线性函数,二次规划,(QP),目标为二次函数、约束为线性,整数规划,(IP),决策变量,(,全部或部分,),为整数,整数,线性,规划,(ILP),，整数,非线性,规划,(INLP),纯整数规划,(PIP),混合整数规划,(MIP),一般整数规划，,0-1,（整数）规划,连续规划,离散规划,数学规划,(,Mathematical Programming,),10/1/2024,常用优化软件,LINDO,/,LINGO,软件,MATLAB,优化工具箱,/,mathematica,优化程序包,EXCEL,软件的优化功能,SAS(,统计分析,),软件的优化功能,10/1/2024,LINDO,公司软件产品简要介绍,美国芝加哥,(Chicago),大学的,Linus,Schrage,教授于,1980,年前后开发,后来成立,LINDO,系统公司（,LINDO Systems Inc.,）， 网址：,http:/,LINDO: Linear Interaction and Discrete Optimizer,LINGO: Linear Interaction General Optimizer,10/1/2024,LINDO,和,LINGO,能求解的数学规划模型,LINGO,LINDO,数学规划模型,线性规划,(LP),非线性规划,(NLP),二次规划,(QP),连续规划,整数规划,(IP),10/1/2024,LINDO,是专门用于求解数学规划的软件包。,LINDO,执行速度很快、易于方便输入，因此在数学、科研和工业界得到广泛应用。,LINDO,主要用于解线性规划、二次规划。也可以用于线性方程组的求解以及代数方程求根等。,LINDO,中包含了建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。,一般用,LINDO,（,Linear Interactive and Discrete Optimizer,）,解决线性规划,二,.,LINDO/LINGO,软件简介,10/1/2024,最大规模的模型的非零系数可以达到,1,000,000,个,最大变量个数可以达到,100,000,个，最大目标函数和约束条件个数可以达到,32000,个,最大整数变量个数可以达到,100,000,个,LINDO 6 .1,学生版至多可求解多达,300,个变量和,150,个约束的规划问题,10/1/2024,1.,求解线性规划和非线性规划问题,2.,模型输入简练直观,3.,运行速度快 计算能力强,4.,内置建模语言 提供内部函数 较少语句直观描述大规模优化模型,5.,引入集合 容易建模,6.,数据交换方便,(,与,EXCEL,和数据库,),LINGO,软件的主要功能和特点,10/1/2024,例,1,简单的线性规划（,LP,）问题：,在,空白的模型窗口中输入这个LP模型,：,max 2x+3y,st 4x+3y=10,3x+5y12,end,10/1/2024,如图：,10/1/2024,LINDO,程序有以下特点：,程序以“,MAX”,（或“,MIN”,）开始，表示目标最大化（或最小化）问题，后面直接写目标函数表达式和约束表达式；,目标函数和约束之间用“,ST”,分开；（或用“,s.t,.”,）,程序以“,END”,结束（ “,END”,也可以省略）。,系数与变量之间的乘号必须省略。,系统对目标函数所在行自动生成行名“,1,）”,对约束默认的行名分别是“,2)” “3)”,，用户也可以自己输入行名；行名放在对应的约束之前。,书写相当灵活，不必对齐，不区分字符的大小写。,默认所有的变量都是非负的,所以不必输入非负约束。,约束条件中的“,=”,可分别用“,”,代替。,一行中感叹号“！”后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。,10/1/2024,模型求解：,用鼠标点击工具栏中的图标 ，,或从菜单中选择,Solve|Solve,（,Ctrl+S,）,命令,LINDO,首先开始编译这个模型，编译没有错误则开始求解；,求解时会首先显示如右图所示的,LINDO“,求解器运行状态窗口 ”。,10/1/2024,求解器运行状态窗口显示的相应信息及含义：,名称,含义,Status,当前状态,显示当前求解状态：“,Optimal,”,表示已达到最优解；其他可能的显示还有三个：,Feasible(,可行解,), Infeasible(,不可行,), Unbounded(,最优值无界,),。,Iterations,迭代次数,显示迭代次数：“,2,”,表示经过了,2,次迭代。,Infeasibility,不可行性,约束不满足的量,(,即各个约束条件不满足的“数量”的和,),：“,0,”,表示解是可行的。,Objective,当前目标值,显示目标函数当前的值：,7.45455,。,Best IP,整数规划当前最佳目标值,显示整数规划当前的最佳目标值：“,N/A,”,（,No Answer,）表示无答案或无意义，因为这个模型中没有整数变量，不是整数规划（,IP,）。,10/1/2024,名称,含义,IP Bound,整数规划的界,显示整数规划的界（对最大化问题显示上界；对最小化问题，显示下界）,Branches,分枝数,显示分枝定界算法已经计算的分枝数：,Elapsed Time,所用时间,显示计算所用时间（秒）：“,0.00,”,说明计算太快了，用时还不到,0.005,秒。,UpdateInterval,刷新本界面时间间隔,显示和控制刷新本界面的时间间隔：“,1,”,表示,1,秒；用户可以直接在界面上修改这个时间间隔。,Interrupt Solver,中断求解程序,当模型规模比较大时，求解时间会很长，可以在程序运行过程中用鼠标点击该按钮终止计算。,Close,关闭,该按钮是关闭状态窗口，并不终止计算,10/1/2024,紧接着弹出一对话框，询问你是否需要做灵敏性分析（,DO RANGE (SENSITIVITY) ANALYSIS?,）先选择“否（,N,）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。,10/1/2024,报告窗口,用鼠标选择“,Window | Reports Window,”,（报告窗口），,就可以查看该窗口的内容,10/1/2024,输出结果表示的意思是：,“,LP OPTIMUM FOUND AT STEP2,”,表示单纯形法在两次迭代（旋转）后得到最优解。,“,OBJECTIVE FUNCTION VALUE 1) 7.454545,”,表示最优目标值为,7.454545.,（注意：在,LINDO,中目标函数所在的行总是被认为是第,1,行，这就是这里“,1,）”的含义）。,10/1/2024,“,VALUE,”,给出最优解中各变量,(VARIABLE),的值,:,X =1.272727, Y =1.636364.,“,REDUCED COST,”,给出最优的单纯形表中目标函数行（第,1,行）中变量对应的系数,.,“,SLACK OR SURPLUS,（松驰或剩余）” 给出约束对应的松驰变量的值,:,第,2,、,3,行松驰变量均为,0,说明对于最优解来讲，两个约束（第,2,、,3,行）均取等号，即都是紧约束。,10/1/2024,“,DUAL PRICES,”,给出对偶价格（或影子价格）的值,:,表示,最优解下“资源”增加,1,单位时“效益”的增量。,第,2,、,3,行对偶价格分别为,.090909,，,.545455,。,“,NO. ITERATIONS= 2,”,表示用单纯形法进行了两次迭代。,10/1/2024,使用,LINDO,的一些注意事项,“,”,（或“,=”,（或“,=”,）功能相同,变量与系数间可有空格,(,甚至回车,),但无运算符,变量名以字母开头，不能超过,8,个字符,变量名不区分大小写（包括,LINDO,中的关键字）,目标函数所在行是第一行，第二行起为约束条件,行号,(,行名,),自动产生或人为定义。行名以“）”结束,行中注有“,!”,符号的后面部分为注释。如,:,! Its Comment.,在模型的任何地方都可以用“,TITLE”,对模型命名（最多,72,个字符），如：,TITLE This Model is only an Example,10/1/2024,变量不能出现在一个约束条件的右端,表达式中不接受括号“,( )”,和逗号“,”,等任何符号,例,:,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,的一些注意事项,10/1/2024,14.,“END”,后对,0-1,变量说明：,INT n,或,INT name,15.,“END”,后对整数变量说明：,GIN n,或,GIN name,使用,LINDO,的一些注意事项,16.,简单错误的检查和避免：,输入模型时可能会有某些输入错误,.,当问题规模较大时,要查找错误是比较困难的。在,LINDO,中有一些可帮助寻找错误的功能，其中之一就是菜单命令“,Report | Picture,（,Alt+5,）”,它的功能是可以将目标函数和约束表达式中的非零系数通过列表（或图形）显示出来。,10/1/2024,三个变量范围限定命令,(FREE,、,SUB,、,SLB),的作用,求解如下的,LP,问题：,这个模型中对变量,x,没有非负限制，对,y,有上限限制，对,z,有下限限制。用,FREE,、,SUB,、,SLB,三个命令可以实现这些功能。,10/1/2024,MAX 2x 3y + 4z,S.T.,con2) 4 x + 3y + 2z = 10,con3) -3x + 5 y - z 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”,这个语句确实是不能少的。不妨试一下，去掉这个语句后效果会怎样？,10/1/2024,LINGO,入门,设有线性规划模型如下：,10/1/2024,LP,问题在,lindo,和,lingo,中,不同的输入形式,Lindo,:,max 2x+3y,st,4x+3y10,3x+5y12,end,Lingo,:,max,=2*x+3*y;,4*x+3*y10;,3*x+5*y12;,（,1,） 将目标函数的表示方式从“,MAX,”,变成了“,MAX=,”,（,2,） “,ST,”,在,LINGO,模型中不再需要，所以被删除了,（,3,） 每个系数与变量间增加了运算符“,*,”（即乘号不能省略）,（,4,） 每行（目标、约束和说明语句）后面均增加了一个分号“,;,”,（,5,） 模型结束标志“,END”,也被删除了（,LINGO,中只有当模型以“,MODEL:”,开始时才能,以“,END,”,结束）。,10/1/2024,LINGO,的语法规则,1.,最大值,MAX=,最小值,MIN=,2.,语句必须以分号,”,;”,结束 每行可多个语句 语句可跨行,3.,变量名由字母、数字和下划线组成 以字母开头 长度,不超,32,个字符 不区分大小写,4.,默认决策变量非负 其他要求可做说明,5.,模型以,MODEL,：开头，以,END,结束,(,此结构也可省略）,6.,注释以 ！开始，以,;,结束；,7.,可以用,表示,表示,=,10/1/2024,程序语句输入的备注：,LINGO,总是根据“,MAX=”,或“,MIN=”,寻找目标函数，而除注释语句和,TITLE,语句外的其他语句都是约束条件，因此语句的顺序并不重要 。,限定变量取整数值的语句为“,GIN(X1)”,和“,GIN(X2)”,，不可以写成“,GIN(2)”,，否则,LINGO,将把这个模型看成没有整数变量。,LINGO,中函数一律需要以“,”,开头，其中整型变量函数（,BIN,、,GIN,）和上下界限定函数（,FREE,、,SUB,、,SLB,）与,LINDO,中的命令类似。而且,0/1,变量函数是,BIN,函数。,10/1/2024,一个简单的LINGO程序,例,直接用,LINGO,来解如下二次规划问题：,输入窗口如下：,10/1/2024,输出结果：,运行菜单命令“,LINGO|Solve,”,最优整数解,X=(35,，,65),最大利润,=11077.5,10/1/2024,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,10/1/2024,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,运行结果如下,:,10/1/2024,看完例,1,后,能解下面这个问题吗,?,例,2,10/1/2024,例,3,model,:,!this is an integer programming problem;,max,=4*x1+3*x2;,4*x1+x2=10;,2*x1+3*x2=0;,end,10/1/2024,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,运行结果如下,:,10/1/2024,例,1,加工奶制品的生产计划,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,千克,A,2,或,获利,24,元,/,千克,获利,16,元,/,千克,50,桶牛奶,时间,480,小时,至多加工,100,千克,A,1,制订生产计划，使每天获利最大,35,元可买到,1,桶牛奶，买吗？若买，每天最多买多少,?,可聘用临时工人，付出的工资最多是每小时几元,?,A,1,的获利增加到,30,元,/,千克，应否改变生产计划？,每天：,三、建模实例,10/1/2024,1,桶牛奶,3,千克,A,1,12,小时,8,小时,4,千克,A,2,或,获利,24,元,/,千克,获利,16,元,/,千克,x,1,桶牛奶生产,A,1,x,2,桶牛奶生产,A,2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型,(LP),时间,480,小时,至多加工,100,千克,A,1,50,桶牛奶,每天,10/1/2024,模型求解,软件实现,LINDO,max 72x1+64x2,st,2)x1+x250,3)12x1+8x2480,4)3x1100,end,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,桶牛奶生产,A,1, 30,桶生产,A,2,，,利润,3360,元。,10/1/2024,结果解释,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+64x2,st,2) x1+x250,3) 12x1+8x2480,4) 3x1100,end,三种资源,“资源” 剩余为零的约束为紧约束（有效约束）,10/1/2024,结果解释,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,元！,10/1/2024,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,x,1,系数范围,(64,96),x,2,系数范围,(48,72),A,1,获利增加到,30,元,/,千克，应否改变生产计划,x,1,系数由,24,3=72,增加,为,30,3=90,，在,允许范围内,不变！,(,约束条件不变,),10/1/2024,结果解释,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,桶,(,目标函数不变,),10/1/2024,如果生产某一类型汽车，则至少要生产,80,辆， 那么最优的生产计划应作何改变？,例,2,汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。,小型 中型 大型,现有量,钢材（吨）,1.5 3 5 600,劳动时间（小时）,280 250 400 60000,利润（万元）,2 3 4,制订月生产计划，使工厂的利润最大。,10/1/2024,设每月生产小、中、大型汽车的数量分别为,x,1,x,2,x,3,汽车厂生产计划,模型建立,小型 中型 大型 现有量,钢材,1.5 3 5 600,时间,280 250 400 60000,利润,2 3 4,线性规划模型,(LP),10/1/2024,模型求解,3,）,模型中增加条件：,x,1,x,2,x,3,均为整数，重新求解。,OBJECTIVE FUNCTION VALUE,1) 632.2581,VARIABLE 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,）舍去小数：取,x,1,=64,，,x,2,=167,，,算出目标函数值,z,=629,，与,LP,最优值,632.2581,相差不大。,2,）试探：如取,x,1,=65,，,x,2,=167,；,x,1,=64,，,x,2,=168,等，计算函数值,z,，,通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,10/1/2024,IP,可用,LINDO,直接求解,整数规划,(,IP,),“,gin 3,”,表示,“,前,3,个变量为整数,”,，等价于：,gin x1,gin x2,gin x3,IP,的最优解,x,1,=64,，,x,2,=168,，,x,3,=0,，,最优值,z,=632,max 2x1+3x2+4x3,st,1.5x1+3x2+5x3600,280x1+250x2+400x30,y,=1,10/1/2024,例,4:,员工聘用方案,决策变量,：周一至周日每天,(,新,),聘用人数,x,1, x,2,x,7,目标函数,：,7,天,(,新,),聘用人数之和,约束条件,：周一至周日每天需要人数,10/1/2024,连续工作,5,天,周一工作的应是,(,上,),周四至周一聘用的,设系统已进入稳态,聘用方案,整数规划,模型,(IP),10/1/2024,首先在,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,个变量都是一般整数变量。 （仍然默认为取值是非负的）,10/1/2024,求解后状态窗口中与整数相关的三个域有了相关结果,:,“,Best IP,：,94,”,表示当前得到的最好的整数解的目标函数值为,94,（人）。,“,IP Bound,：,93.5,”,表示该整数规划目标值的下界为,93.5,（人）。,“,Branches,：,1,”,表示分枝数为,1,（即在第,1,个分枝中就找到了最优解）。,10/1/2024,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,求解结果的报告窗口如下：,10/1/2024,生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小,例,5,钢管和易拉罐下料,原料下料问题,按照工艺要求，确定下料方案，使所用材料最省，或利润最大,10/1/2024,某,钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是,19,米长。,1),现有一客户需要,50,根,4,米长、,20,根,6,米长和,15,根,8,米长的钢管。应如何下料最节省？,2),零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过,3,种。此外，该客户除需要,1,）中的三种钢管外，还需要,10,根,5,米长的钢管。应如何下料最节省？,1,、,钢管下料,10/1/2024,问题,1,）的求解,问题分析,首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将,19,米长的钢管切割成,3,根,4,米长的钢管，余料为,7,米显然，可行的切割模式是很多的。,其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有,7,种，如表所示。,10/1/2024,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.,所用原料钢管总根数最少,模式,4,米钢管根数,6,米钢管根数,8,米钢管根数,余料,(,米,),1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,钢管下料问题,1,两种标准,1.,原料钢管剩余总余量最小,10/1/2024,x,i,按第,i,种模式切割的原料钢管根数,(,i,=,1,2,7,),约束,满足需求,决策变量,目标,1,（总余量）,模,式,4,米,根数,6,米,根数,8,米,根数,余,料,1,4,0,0,3,2,3,1,0,1,3,2,0,1,3,4,1,2,0,3,5,1,1,1,1,6,0,3,0,1,7,0,0,2,3,需,求,50,20,15,整数约束：,x,i,为,整数,10/1/2024,模型求解,将整数线性规划模型（加上整数约束）输入,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,10/1/2024,求解可以得到最优解如下：,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,米,10/1/2024,目标,2,（总根数）,钢管下料问题,1,约束条件不变,x,i,为,整数,10/1/2024,将整数线性规划模型（加上整数约束）输入,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,模型求解,10/1/2024,求解，可以得到最优解如下：,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,10/1/2024,当余料没有用处时，,通常以总根数最少为目标,最优解：,x,2,=15,x,5,=5,x,7,=5,其余为,0,；,最优值：,25,。,按模式,2,切割,15,根，按模式,5,切割,5,根，按模式,7,切割,5,根，共,25,根，余料,35,米,虽余料增加,8,米，但减少了,2,根,与,目标,1,的结果“共切割,27,根，余料,27,米” 相比,10/1/2024,钢管下料问题,2,对大规模问题，用模型的约束条件界定合理模式,增加一种需求：,5,米,10,根；切割,模式不超过,3,种。,现有,4,种,需求：,4,米,50,根，,5,米,10,根，,6,米,20,根，,8,米,15,根，用枚举法确定合理切割模式，过于复杂。,决策变量,x,i,按第,i,种模式切割的原料钢管根数,(,i,=,1,2,3,),r,1,i