《LIDO软件的使用》PPT课件.ppt

数学规划建模与LINDO/LINGO软件,LINDO公司软件产品简要介绍,美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：,LINDO:LinearINteractiveandDiscreteOptimizerLINGO:LinearINteractiveGeneralOptimizerLINDOAPI:LINDOApplicationProgrammingInterface,演示(试用)版、学生版、高级版、超级版、工业版、扩展版（求解问题规模和选件不同）,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y5改为x5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103),LINDO和LINGO能求解的数学规划模型,LINGO,LINDO,数学规划模型,线性规划(LP),非线性规划(NLP),二次规划(QP),连续规划,整数规划(IP),一、LINDO软件的基本使用方法,以下介绍的软件软件是LINDO6.1forWindows试用版,安装过程中，用户只需要按照程序给出的提示，一步一步走下去，直到安装成功为止。,第一次运行刚安装的LINDO软件时，系统会弹出一个对话框，要求你输入密码（Password）。如果你买的是正版软件，请在密码框中输入LINDO公司给你提供的密码，然后按“OK”按钮即可。否则，你只能使用演示版(即试用版)，按下“DemoVersion(演示版)”按钮即可。,编写一个简单的LINDO程序,例1简单的线性规划（LP）问题：,在空白的模型窗口中输入这个LP模型：,max2x+3yst4x+3y=103x+5y12end,如图：,LINDO程序有以下特点：,程序以“MAX”（或“MIN”）开始，表示目标最大化（或最小化）问题，后面直接写目标函数表达式和约束表达式；目标函数和约束之间用“ST”分开；（或用“s.t.”，“sunjectto”）程序以“END”结束（“END”也可以省略）。系数与变量之间的乘号必须省略。系统对目标函数所在行自动生成行名“1）”,对约束默认的行名分别是“2)”“3)”，用户也可以自己输入行名；行名放在对应的约束之前。书写相当灵活，不必对齐，不区分字符的大小写。默认所有的变量都是非负的,所以不必输入非负约束。约束条件中的“=”可分别用“”代替。一行中感叹号“！”后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。,模型求解：,用鼠标点击工具栏中的图标，或从菜单中选择Solve|Solve（Ctrl+S）命令,LINDO首先开始编译这个模型，编译没有错误则开始求解；求解时会首先显示如右图所示的LINDO“求解器运行状态窗口”。,求解器运行状态窗口显示的相应信息及含义：,紧接着弹出一对话框，询问你是否需要做灵敏性分析（DORANGE(SENSITIVITY)ANALYSIS?）先选择“否（N）”按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。,报告窗口,用鼠标选择“Window|ReportsWindow”（报告窗口），就可以查看该窗口的内容,输出结果表示的意思是：,“LPOPTIMUMFOUNDATSTEP2”表示单纯形法在两次迭代（旋转）后得到最优解。,“OBJECTIVEFUNCTIONVALUE1)7.454545”表示最优目标值为7.454545.（注意：在LINDO中目标函数所在的行总是被认为是第1行，这就是这里“1）”的含义）。,“VALUE”给出最优解中各变量(VARIABLE)的值:X=1.272727,Y=1.636364.,“REDUCEDCOST”给出最优的单纯形表中目标函数行（第1行）中变量对应的系数.,“SLACKORSURPLUS（松驰或剩余）”给出约束对应的松驰变量的值:第2、3行松驰变量均为0,说明对于最优解来讲，两个约束（第2、3行）均取等号，即都是紧约束。,“DUALPRICES”给出对偶价格（或影子价格）的值:表示最优解下“资源”增加1单位时“效益”的增量。第2、3行对偶价格分别为.090909，.545455。“NO.ITERATIONS=2”表示用单纯形法进行了两次迭代。,保存文件,选择File|Save（F5）命令把“结果报告”保存在一个文件中（缺省的后缀名为LTX,即LINDO文本文件）类似地，回到模型窗口，可以把输入的模型保存在一个文件中。保存的文件将来可以用File|Open（F3）和File|View（F4）重新打开，用前者打开的程序可以进行修改，而后者只能浏览。,如果模型有错误,运行时会弹出出错信息报告窗口(LINDOErrorMessage)，则需要修改模型。,二、LINDO模型的一些注意事项,1.变量名由字母和数字组成，但必须以字母开头，且长度不能超过8个字符，不区分大小写字母，包括关键字（如MAX、MIN等）也不区分大小写字母。,2.对目标函数和约束用行号（行名）进行标识，这些标识会在将来的求解结果报告中用到。行名可以和变量名一样命名，也可以只用数字命名，还可以含有中文字符，但长度同样不能超过8个字符。为了方便将来阅读求解结果报告，建议用户总是自觉地对每个约束进行命名。行名结束标志符号、即右括号“）”必须是英文字符，否则会出现错误。,3.可以用“TITLE”语句对输入的模型命名，用法是在TITLE后面写出其名字（最多72个字符，可以有汉字），在程序中单独占一行，可以在模型的任何地方。模型命名的第一个作用类似于对模型的注释和说明。模型命名的另一个目的，是为了方便将来阅读求解结果报告。因为用户有可能同时处理多个模型，很容易混淆模型与求解结果的对应关系。这时如果对不同模型分别进行了命名，就可以随时（例如在求解当前模型前）使用菜单命令“FILE|TITLE”将当前模型的名字显示在求解结果报告窗口中，这样就容易判别每个求解结果与每个模型的对应关系。,4.模型中以感叹号“!”开头的是注释行（注释语句，或称为说明语句），可以帮助他人或以后自己理解这个模型。实际上，每行中“!”符号后面的都是注释或说明。注释语句中可以使用汉字字符。,5.变量不能出现在一个约束条件的右端（即约束条件的右端只能是常数）;变量与其系数间可以有空格（甚至回车）,但不能有任何运算符号（包括乘号*等）。,6.模型中不接受括号“()”和逗号“,”等符号（除非在注释语句中）。例如:4(X1+X2)需写为4X1+4X2；“10,000”需写为10000。,7.表达式应当已经经过化简。如不能出现2X1+3X2-4X1，而应写成-2X1+3X2等。,8.LINDO中已假定所有变量非负。若要取消变量的非负假定，可在模型的“END”语句后面用命令“FREE”。例如，在“END”语句后输入FREEvname，可将变量vname的非负假定取消。,9.数值均衡化考虑：如果约束系数矩阵中各非零元的绝对值的数量级差别很大（相差1000倍以上），则称其为数值不均衡的。为了避免数值不均衡引起的计算问题,使用者应尽可能自己对矩阵的行列进行均衡化。此时还有一个原则,即系数中非零元的绝对值不能大于100000或者小于0.0001。LINDO不能对LP中的系数自动进行数值均衡化，但如果LINDO觉得矩阵元素之间很不均衡,将会给出警告。,10.简单错误的检查和避免：输入模型时可能会有某些输入错误.当问题规模较大时,要查找错误是比较困难的。在LINDO中有一些可帮助寻找错误的功能，其中之一就是菜单命令“Report|Picture（Alt+5）”,它的功能是可以将目标函数和约束表达式中的非零系数通过列表（或图形）显示出来。,例2菜单命令“Report|Picture（Alt+5）”的功能,用Report|Picture命令，将弹出一个对话框,在弹出的对话框中采用缺省选项（即不采用下三角矩阵形式，并以图形方式显示），直接按“OK”按钮可得到一个输出图形。可以从图中很直观地发现,其实错误原因只不过是在输入5)行的表达式中C0与CO弄混了（英文字母O与数字0弄混了）。在图中，还可以用鼠标控制显示图形的缩放，这对于规模较大的模型是有用的。,MIN5A0+6A1+2A2+4B0+3B1+7B2+2C0+9C1+8C2A0+Al+A2=83)SUBJECTTO2)B0+B1+B2=94)C0+C1+C2=65)A0+B0+CO=66)A1+B1+C1=57)A2+B2+C2=9END,对如下的一个有错误的模型输入：,Lingo是一个目前求解非线性规划的常用软件包，同时它也能够求解线性规划，但是，如果将Lingo用于求解线性规划，则其计算速度要比只能求解线性规划的软件Lindo慢得多。因此，如果专门求解线性规划，而且自变量个数或者限定条件较多，请使用Lindo.,三、LINGO软件的基本使用方法,LINGO软件简介,目标与约束段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）,LINGO模型的构成：4个段,LINGO模型的优点,包含了LINDO的全部功能提供了灵活的编程语言（矩阵生成器）,安装文件20M多一点，需要接受安装协议、选择安装目录（缺省C:LINGO9）。,LINGO软件的安装,安装过程:与LINDOforWindows类似.,安装完成前，在出现的对话框(如图)中选择缺省的建模(即编程)语言，系统推荐的是采用LINGO。安装后可通过“LINGO|Options|FileFormat”命令修改缺省的建模（即编程）语言。,第一次运行时提示输入授权密码，如图：,安装完成后，启动Lingo,你会看到如下窗口：,命令窗口,求解按钮,将求解内容填入窗口后，按求解按钮，则得到计算结果.,LINGO软件的主要特色,两种命令模式,Windows模式：通过下拉式菜单命令驱动LINGO运行（多数菜单命令有快捷键，常用的菜单命令有快捷按钮），图形界面，使用方便；,命令行模式：仅在命令窗口(CommandWindow)下操作，通过输入行命令驱动LINGO运行。,从LINDO到LINGO,LINGO9.0功能增强，性能稳定，解答结果可靠。与LINDO相比，LINGO软件主要具有两大优点:,内置建模语言，允许以简练、直观的方式描述较大规模的优化问题，所需的数据可以以一定格式保存在独立的文件中。,除具有LINDO的全部功能外，还可用于求解非线性规划问题，包括非线性整数规划问题;,一个简单的LINGO程序,例直接用LINGO来解如下二次规划问题：,输入窗口如下：,程序语句输入的备注：,LINGO总是根据“MAX=”或“MIN=”寻找目标函数，而除注释语句和TITLE语句外的其他语句都是约束条件，因此语句的顺序并不重要。限定变量取整数值的语句为“GIN(X1)”和“GIN(X2)”，不可以写成“GIN(2)”，否则LINGO将把这个模型看成没有整数变量。LINGO中函数一律需要以“”开头，其中整型变量函数（BIN、GIN）与LINDO中的命令类似。而且0/1变量函数是BIN函数。,输出结果：,运行菜单命令“LINGO|Solve”,最优整数解X=(35，65),最大利润=11077.5,一个简单的LINGO程序,LINGO的基本用法的几点注意事项,LINGO中不区分大小写字母；变量和行名可以超过8个字符，但不能超过32个字符，且必须以字母开头。用LINGO解优化模型时已假定所有变量非负(除非用限定变量取值范围的函数free或sub或slb另行说明)。变量可以放在约束条件的右端(同时数字也可放在约束条件的左端)。但为了提高LINGO求解时的效率，应尽可能采用线性表达式定义目标和约束(如果可能的话)。语句是组成LINGO模型的基本单位,每个语句都以分号结尾，编写程序时应注意模型的可读性。例如：一行只写一个语句，按照语句之间的嵌套关系对语句安排适当的缩进，增强层次感。以感叹号开始的是说明语句(说明语句也需要以分号结束)。,以上是对LINGO所作的最简单的介绍,LINGO中即提供了一个详细的帮助文件,这可在LINGO中的HELP菜单得到,同时它也提供了几十个演示程序,这可以在LINGO中打开FILE菜单的OPEN选项,然后选取LINGO目录中的SAMPLES子目录,这个子目录中都是LINGO的例子,用OPEN装入后即可求解.,例1加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100千克A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/千克，应否改变生产计划？,每天：,案例1奶制品的生产与销售,建模实例与求解,x1桶牛奶生产A1,x2桶牛奶生产A2,获利243x1,获利164x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100千克A1,模型求解,软件实现,LINDO6.1,max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end,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元。,结果解释,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,原料无剩余,时间无剩余,加工能力剩余40,max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,结果解释,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桶牛奶，要买吗？,3548,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,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系数由243=72增加为303=90，在允许范围内,不变！,(约束条件不变),结果解释,RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶,(目标函数不变),注意:充分但可能不必要,例2奶制品的生产销售计划,在例1基础上深加工,制订生产计划，使每天净利润最大,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,50桶牛奶480小时,至多100千克A1,B1，B2的获利经常有10%的波动，对计划有无影响？,出售x1千克A1,x2千克A2，,x3千克B1,x4千克B2,原料供应,劳动时间,加工能力,决策变量,目标函数,利润,约束条件,非负约束,x5千克A1加工B1，x6千克A2加工B2,附加约束,模型求解,软件实现,LINDO6.1,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000NO.ITERATIONS=2,结果解释,每天销售168千克A2和19.2千克B1，利润3460.8（元）,8桶牛奶加工成A1，42桶牛奶加工成A2，将得到的24千克A1全部加工成B1,除加工能力外均为紧约束,结果解释,OBJECTIVEFUNCTIONVALUE1)3460.800VARIABLEVALUEREDUCEDCOSTX10.0000001.680000X2168.0000000.000000X319.2000010.000000X40.0000000.000000X524.0000000.000000X60.0000001.520000ROWSLACKORSURPLUSDUALPRICES2)0.0000003.1600003)0.0000003.2600004)76.0000000.0000005)0.00000044.0000006)0.00000032.000000,增加1桶牛奶使利润增长3.1612=37.92,增加1小时时间使利润增长3.26,30元可增加1桶牛奶，3元可增加1小时时间，应否投资？现投资150元，可赚回多少？,投资150元增加5桶牛奶，可赚回189.6元。（大于增加时间的利润增长）,结果解释,B1,B2的获利有10%的波动，对计划有无影响,RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX124.0000001.680000INFINITYX216.0000008.1500002.100000X344.00000019.7500023.166667X432.0000002.026667INFINITYX5-3.00000015.8000002.533334X6-3.0000001.520000INFINITY,B1获利下降10%，超出X3系数允许范围,B2获利上升10%，超出X4系数允许范围,波动对计划有影响,生产计划应重新制订：如将x3的系数改为39.6计算，会发现结果有很大变化。,如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？,例1汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。,制订月生产计划，使工厂的利润最大。,案例2汽车生产与原油采购,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,汽车厂生产计划,模型建立,线性规划模型(LP),模型求解,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，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,LINDO求解整数线性规划概述,LINDO可用于求解线性纯整数规划或混合整数规划(IP)，模型的输入与LP问题类似,但需在END标志后定义整型变量。,0/1型的变量可由INTEGER（可简写为INT）命令来标识，有以下两种可能的用法：INTvnameINTn前者只将决策变量vname标识为0/1型,后者将当前模型中前n个变量标识为0/1型（模型中变量顺序由模型中输入时出现的先后顺序决定,该顺序可由输出结果中的变量顺序查证是否一致）。,一般的整数变量可用命令GIN（是GENERALINTEGER的意思）,其使用方式及格式与INT命令相似。,IP可用LINDO直接求解,整数规划(IntegerProgramming,简记IP),“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3,IP的最优解x1=64，x2=168，x3=0，最优值z=632,max2x1+3x2+4x3st1.5x1+3x2+5x30;x120;x210;x220;x10;x20;x30;end,Objectivevalue:4800.000VariableValueReducedCostX11500.00000.0000000E+00X21500.00000.0000000E+00X120.0000000E+000.0000000E+00X220.0000000E+000.0000000E+00X10.1021405E-1310.00000X20.0000000E+008.000000X30.0000000E+006.000000X0.0000000E+000.0000000E+00,LINGO得到的是局部最优解，还能得到更好的解吗？,用库存的500吨原油A、500吨原油B生产汽油甲，不购买新的原油A，利润为4,800千元。,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的吨数,方法2,优于方法1的结果,案例3饮料厂的生产与检修,单阶段生产计划,多阶段生产计划,生产批量问题,企业生产计划,考虑与产量无关的固定费用,给优化模型求解带来新的困难,安排生产计划,满足每周的需求,使4周总费用最小。,存贮费:每周每千箱饮料0.2千元。,例1饮料厂的生产与检修计划,在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?,某种饮料4周的需求量、生产能力和成本,问题分析,除第4周外每周的生产能力超过每周的需求；生产成本逐周上升；前几周应多生产一些。,饮料厂在第1周开始时没有库存；从费用最小考虑,第4周末不能有库存；周末有库存时需支出一周的存贮费；每周末的库存量等于下周初的库存量。,模型假设,目标函数,约束条件,产量、库存与需求平衡,决策变量,能力限制,非负限制,模型建立,x1x4：第14周的生产量,y1y3：第13周末库存量,存贮费:0.2(千元/周千箱),模型求解,4周生产计划的总费用为528(千元),最优解：x1x4：15，40，25，20；y1y3：0，15，5.,LINDO求解,检修计划,0-1变量wt：wt=1检修安排在第t周(t=1,2,3,4）,在4周内安排一次设备检修，占用当周15千箱生产能力，能使检修后每周增产5千箱，检修应排在哪一周?,检修安排在任一周均可,约束条件,能力限制,产量、库存与需求平衡条件不变,增加约束条件：检修1次,检修计划,目标函数不变,0-1变量wt：wt=1检修安排在第t周(t=1,2,3,4）,LINDO求解,总费用由528千元降为527千元,检修所导致的生产能力提高的作用,需要更长的时间才能得到充分体现。,最优解：w1=1,w2,w3,w4=0;x1x4：15,45,15,25；y1y3：0,20,0.,例2饮料的生产批量问题,安排生产计划,满足每周的需求,使4周总费用最小。,存贮费:每周每千箱饮料0.2千元。,饮料厂使用同一条生产线轮流生产多种饮料。若某周开工生产某种饮料,需支出生产准备费8千元。,某种饮料4周的需求量、生产能力和成本,生产批量问题的一般提法,ct时段t生产费用(元/件)；ht时段t(末)库存费(元/件)；st时段t生产准备费(元)；dt时段t市场需求(件)；Mt时段t生产能力(件)。,假设初始库存为0,制订生产计划,满足需求,并使T个时段的总费用最小。,决策变量,xt时段t生产量；yt时段t(末)库存量；wt=1时段t开工生产(wt=0不开工)。,目标,约束,混合0-1规划模型,最优解：x1x4：15，40，45，0；总费用：554.0(千元),生产批量问题的一般提法,将所给参数代入模型，用LINDO求解,生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小,案例4钢管和易拉罐下料,原料下料问题,按照工艺要求，确定下料方案，使所用材料最省，或利润最大,某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19米长。1)现有一客户需要50根4米长、20根6米长和15根8米长的钢管。应如何下料最节省？2)零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要1）中的三种钢管外，还需要10根5米长的钢管。应如何下料最节省？,例1钢管下料,问题1）的求解,问题分析首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将19米长的钢管切割成3根4米长的钢管，余料为7米。显然，可行的切割模式是很多的。,其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有7种，如表所示。,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.所用原料钢管总根数最少,钢管下料问题1,两种标准,1.原料钢管剩余总余量最小,xi按第i种模式切割的原料钢管根数(i=1,2,7),约束,满足需求,决策变量,目标1（总余量）,整数约束：xi为非负整数,模型建立,模型求解,将整数线性规划模型（加上整数约束）输入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,LINDO求解,求解可以得到最优解如下：,OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000,按模式2切割12根,按模式5切割15根，余料27米,目标2（总根数）,钢管下料问题1,约束条件不变,xi为整数,将整数线性规划模型（加上整数约束）输入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,模型求解,LINDO求解,求解，可以得到最优解如下：,OBJECTIVEFUNCTIONVALUE1)25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000,当余料没有用处时，通常以总根数最少为目标,最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米”相比,钢管下料问题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米长的钢管的数量,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数（总根数）,约束条件,整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管模式1：切割成4根4米钢管，需13根；模式2：切割成1根5米和2根6米钢管，需10根；模式3：切割成2根8米钢管，需8根。原料钢管总根数上界：13+10+8=31,模式排列顺序可任定,钢管下料问题2,需求：4米50根，5米10根，6米20根，8米15根,每根原料钢管长19米,将模型输入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,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根。,板材规格2：长方形，3228cm，2万张。,例2易拉罐下料,每周工作40小时，每只易拉罐利润0.10元，原料余料损失0.001元/cm2（不能装配的罐身、盖、底也是余料）,罐身高10cm，上盖、下底直径均5cm。,板材规格1：正方形，边长24cm，5万张。,如何安排每周生产？,模式1:正方形边长24cm,问题分析,计算各种模式下的余料损失,上、下底直径d=5cm，罐身高h=10cm。,模式1余料损失242-10d2/4-dh=222.6cm2,问题分析,目标:易拉罐利润扣除原料余料损失后的净利润最大,约束：每周工作时间不超过40小时；原料数量：规格1（模式13）5万张，规格2（模式4）2万张；罐身和底、盖的配套组装。,注意：不能装配的罐身、上下底也是余料,决策变量,xi按照第i种模式的生产张数(i=1,2,3,4)；y1一周生产的易拉罐个数；y2不配套的罐身个数；y3不配套的底、盖个数。,模型建立,目标,约束条件,时间约束,原料约束,模型建立,y1易拉罐个数；y2不配套的罐身；y3不配套的底、盖。,每只易拉罐利润0.10元，余料损失0.001元/cm2,罐身面积dh=157.1cm2底盖面积d2/4=19.6cm2,(40小时),约束条件,配套约束,y1易拉罐个数；y2不配套的罐身；y3不配套的底、盖。,虽然xi和y1，y2，y3应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理。,LINDO发出警告信息：“数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别”,模型求解,OBJECTIVEFUNCTIONVALUE1)4298.337VARIABLEVALUEREDUCEDCOSTY1160250.0000000.000000X10.0000000.000050X240125.0000000.000000X33750.0000000.000000X420000.0000000.000000Y20.0000000.223331Y30.0000000.036484,模型中数据不平衡的警告信息,输入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=0end,将所有决策变量扩大10000倍（xi万张，yi万件）,模式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,求解得到：,下料问题的建模,确定下料模式,构造规划模型,规格不太多，可枚举下料模式，建立整数线性规划模型，否则要构造整数非线性规划模型，求解困难，可用缩小可行域的方法进行化简，但要保证最优解的存在。,一维问题（如钢管下料）,二维问题（如易拉罐下料）,具体问题具体分析（比较复杂）,要想学好和灵活应用LINDO软件,首先要多练习使用LINDO来解决问题,熟能生巧。LINDO中的显示报告完全是英文的，大家要熟悉其含义。不要太拘泥于书本或别人教你的方法,要会举一反三,综合使用,才能用得巧而精。这就象编程序一样,同样的几条程序命令,有的人只能生搬硬套,而有的人却能发挥得淋漓尽致,这中间的功夫不是光靠一招招向书本学能得来的了。,备注,LINDO的主要菜单命令,内容提要：菜单条上的6个主菜单文件（File）主菜单编辑（Edit）主菜单求解（Solve）主菜单报告（Report）主菜单,LINDO软件的6个主菜单,菜单条上有6个主菜单：,File(文件)Edit（编辑）Solve（求解）Reports（报告）Window（窗口）Help（帮助）,File(文件)菜单包括了LINDO通过文件与外部设备（如磁盘）交换信息的命令；Edit（编辑）菜单包括了在当前窗口下编辑文本的命令；Solve（求解）菜单包括了求解模型的命令；REPORTS（报告）菜单包括了生成解答结果报告的命令；Window（窗口）菜单包括了窗口切换的命令；HELP（帮助）菜单包括了访问在线帮助文挡的命令。,对于几乎所有的菜单命令，LINDO都提供了快捷键（快捷键的提示位于每个菜单命令的右侧）；对于常用的菜单命令，LINDO在工具栏提供了相应的图形按钮（参见下一页）。工具栏是浮动式的，可以用鼠标拖到屏幕上任何地方。这些菜单的用法都是和WINDOWS下其他应用程序的标准用法类似的，所以，我们不准备对所有的菜单命令进行完整和详细的介绍，而是只对前4个主菜单中有一定LINDO特色的主要命令进行简要介绍。,LINDO工具栏及其对应的菜单命令和快捷键,1.4.1文件（File）主菜单,由于LINDO编辑器对文件的大小是有限制的，因此用File|New和File|Open打开的文件不能太大（通常不能超过64000字符）；而File|View不受文件大小限制，这对浏览特别大规模的文件（通常不一定是由LINDO本身的编辑器产生的）是有用的。,File|New、File|Open与File|View命令：File|New用于新建一个模型文件；File|Open用于打开一个已有文件，打开后可以对这个文件进行编辑、求解、保存等；File|View只用于打开已有文件供浏览（也可以求解）但不能编辑。,File|LOGOUTPUT该命令将打开一个对话框（图2-28），要求你指定一个文件名（该文件成为“LOG（日志）文件”）。以后，LINDO软件的所有输出都被送到这个日志文件中保存下来，供你以后查看。注意：正常情况下，在菜单驱动模式下，LINDO的输出应当是被送到报告窗口；在“CommandWindow(命令窗口)”模式下（参见1.6节)，LINDO的输出应当是被送到命令窗口。对话框中有两个检验盒：1.如果选择“EchotoScreen（屏幕显示）”检验盒，屏幕上也会同时显示输出结果，否则屏幕上就不再显示了；2.如果选择“Appendoutput（追加输出）”检验盒，则以后所有LINDO的输出被追加到这个日志文件的结尾，否则系统将首先清空这个文件，然后开始追加内容。,File|TakeCommands（提取命令）用于打开和执行一个LINDO命令脚本文件(命令脚本文件中包含的是由一些列LINDO命令组成的命令序列。,File|BasisSave（保存基）打开一个标准的文件保存对话框，可以将单纯形算法的当前的基（解）以你指定的文件名和文件格式保存下来；将来可以用File|BasisRead（读取基）命令读出这个基（解），并可以从这个基（解）开始继续运行单纯形算法。保存时可以有三种文件格式可供选择：*.PUN(以M