《数学规划与软件共160页》由会员分享，可在线阅读，更多相关《数学规划与软件共160页（160页珍藏版）》请在金锄头文库上搜索。
1、* 王文祥王文祥2013.7数学规划模型、案例与数学规划模型、案例与软件求解软件求解1*一一. . 数学规划模型与优化软件简介数学规划模型与优化软件简介二二. LINDO/LINGO. LINDO/LINGO软件软件Outline四四. LINGO. LINGO建模语言建模语言 三三. . 建模实例建模实例2* 数学规划数学规划是优化问题的一个分支，起始是优化问题的一个分支，起始于于2020世纪世纪3030年代末，年代末，5050年代与年代与6060年代发展成年代发展成为一个完整的分支并受到数学界和社会各界为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时的重视。七八
2、十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有一半以上的问题可用模竞赛的试题中看，有一半以上的问题可用数学规划进行求解。数学规划进行求解。 一一. . 数学规划模型与优化软件简介数学规划模型与优化软件简介3*约约束束条条件件决策变量决策变量数学规划模型的一般形式数学规划模型的一般形式目标函数目标函数可行域 三要素：三要素：决策变量决策变量；目标函数目标函数；约束条件约束
3、条件可行解（只满足约束）与最优解可行解（只满足约束）与最优解(取到最优值取到最优值)“受约束于受约束于”之意4*数学规划类型数学规划类型连续规划连续规划: : 全部决策变量取值均全部决策变量取值均 为连续数值为连续数值 ( (实数实数) )离散规划离散规划: : 部分或全部决策变量部分或全部决策变量 只取离散数值只取离散数值5*线性规划线性规划(LP)目标和约束均为线性函数目标和约束均为线性函数非线性规划非线性规划(NLP)目标或约束中存在非线性函数目标或约束中存在非线性函数二次规划二次规划(QP)目标为二次函数、约束为线性目标为二次函数、约束为线性整数规划整数规划(IP)决策变量决策变量(全
4、部或部分全部或部分)为整数为整数整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP)纯整数规划纯整数规划(PIP),混合整数规划混合整数规划(MIP)一般整数规划，一般整数规划，0-1（整数）规划（整数）规划连连续续规规划划离离散散规规划划数学规划数学规划(Mathematical Programming Mathematical Programming )6*常用优化软件常用优化软件 LINDO/LINGO软件软件MATLAB优化工具箱优化工具箱/mathematica优化程序包优化程序包EXCEL软件的优化功能软件的优化功能SAS(统计分析统计分析)软件的优化功能
5、软件的优化功能7*LINDO公司软件产品简要介绍公司软件产品简要介绍美国芝加哥美国芝加哥(Chicago)大学的大学的LinusSchrage教授于教授于1980年前后开发年前后开发,后来成立后来成立LINDO系统公司系统公司（LINDOSystemsInc.），），网址：网址：LINDO:LinearInteractionandDiscreteOptimizerLINGO:LinearInteractionGeneralOptimizer8*LINDO和和LINGO能求解的数学规划模型能求解的数学规划模型LINGOLINDO数学规划模型数学规划模型线性规划线性规划(LP)非线性规划非线性规划
6、(NLP)二次规划二次规划(QP)连续规划连续规划整数规划整数规划(IP)9*LINDO 是专门用于求解数学规划的软件包。是专门用于求解数学规划的软件包。LINDO 执行速度很快、易于方便输入，因此在数执行速度很快、易于方便输入，因此在数学、科研和工业界得到广泛应用。学、科研和工业界得到广泛应用。LINDO 主要用于解线性规划、二次规划。也可以主要用于解线性规划、二次规划。也可以用于线性方程组的求解以及代数方程求根等。用于线性方程组的求解以及代数方程求根等。LINDO 中包含了建模语言和许多常用的数学函数中包含了建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题（包括大量
7、概论函数），可供使用者建立规划问题时调用。时调用。一般用一般用LINDO（Linear Interactive and Discrete Optimizer）解决线性规划）解决线性规划二二. . LINDO/LINGO LINDO/LINGO软件简介软件简介10*最大规模的模型的非零系数可以达到最大规模的模型的非零系数可以达到1,000,0001,000,000个个最大变量个数可以达到最大变量个数可以达到100,000100,000个，最大目标函数个，最大目标函数和约束条件个数可以达到和约束条件个数可以达到3200032000个个最大整数变量个数可以达到最大整数变量个数可以达到100,0001
8、00,000个个 LINDO 6 .1 学生版至多可求解多达学生版至多可求解多达300 个变量和个变量和150 个约束的规划问题个约束的规划问题11*1.求解线性规划和非线性规划问题2.模型输入简练直观3.运行速度快 计算能力强4.内置建模语言 提供内部函数 较少语句直观描述大规模优化模型5.引入集合 容易建模6.数据交换方便(与EXCEL和数据库) LINGO LINGO软件的主要功能和特点软件的主要功能和特点12*例例1 简单的线性规划（简单的线性规划（LP）问题：）问题： 在在空白的模型窗口中输入这个空白的模型窗口中输入这个LP模型模型：max2x+3yst4x+3y=103x+5y12
9、end13*如图：如图： 14*LINDO程序有以下特点：程序有以下特点： 程序以程序以“MAX”（或（或“MIN”）开始，表示目标最大化（或）开始，表示目标最大化（或最小化）问题，后面直接写目标函数表达式和约束表达式；最小化）问题，后面直接写目标函数表达式和约束表达式； 目标函数和约束之间用目标函数和约束之间用“ST”分开；（或用分开；（或用“s.t.”） 程序以程序以“END”结束（结束（ “END” 也可以省略）。也可以省略）。 系数与变量之间的乘号必须省略。系数与变量之间的乘号必须省略。 系统对目标函数所在行自动生成行名系统对目标函数所在行自动生成行名“1）”,对约束默认对约束默认的行
10、名分别是的行名分别是“2)” “3)”，用户也可以自己输入行名；行名，用户也可以自己输入行名；行名放在对应的约束之前。放在对应的约束之前。 书写相当灵活，不必对齐，不区分字符的大小写。书写相当灵活，不必对齐，不区分字符的大小写。 默认所有的变量都是非负的默认所有的变量都是非负的, 所以不必输入非负约束。所以不必输入非负约束。 约束条件中的约束条件中的“=”可分别用可分别用“”代替。代替。 一行中感叹号一行中感叹号“！”后面的文字为是注释语句，可增强程后面的文字为是注释语句，可增强程序的可读性，不参与模型的建立。序的可读性，不参与模型的建立。15*模型求解：模型求解：用鼠标点击工具栏中的图标用鼠
11、标点击工具栏中的图标 ，或从菜单中选择或从菜单中选择Solve|Solve（Ctrl+S）命令命令LINDO首先开始编译这个首先开始编译这个模型，编译没有错误则开模型，编译没有错误则开始求解；始求解；求解时会首先显示如右图求解时会首先显示如右图所示的所示的LINDO“求解器运行状态窗口求解器运行状态窗口 ”。16*求解器运行状态窗口显示的相应信息及含义：求解器运行状态窗口显示的相应信息及含义： 17*18*紧接着弹出一对话框，询问你是否需要做灵敏性分析紧接着弹出一对话框，询问你是否需要做灵敏性分析（DO RANGE (SENSITIVITY) ANALYSIS? ）先选）先选择择“否（否（N）
12、”按钮，这个窗口就会关闭。然后，再按钮，这个窗口就会关闭。然后，再把状态窗口也关闭。把状态窗口也关闭。 19*报告窗口 用鼠标选择用鼠标选择“Window | Reports Window”（报告窗口），（报告窗口），就可以查看该窗口的内容就可以查看该窗口的内容 20*输出结果表示的意思是：“LP OPTIMUM FOUND AT STEP2”表示单纯形法在两次迭代（旋转）后得到最优解。表示单纯形法在两次迭代（旋转）后得到最优解。 “OBJECTIVE FUNCTION VALUE 1) 7.454545 ”表示最优目标值为表示最优目标值为7.454545.（注意：在（注意：在LINDO中目标
13、函数中目标函数所在的行总是被认为是第所在的行总是被认为是第1行，这就是这里行，这就是这里“1）”的含义）。的含义）。 21*“VALUE” 给出最优解中各变量给出最优解中各变量(VARIABLE)的值的值: X =1.272727, Y =1.636364. “REDUCED COST” 给出最优的单纯形表中目标函数行给出最优的单纯形表中目标函数行（第（第1行）中变量对应的系数行）中变量对应的系数. “SLACK OR SURPLUS（松驰或剩余）（松驰或剩余）” 给出约束对应的给出约束对应的松驰变量的值松驰变量的值: 第第2、3行松驰变量均为行松驰变量均为0, 说明对于最优解来说明对于最优解
14、来讲，两个约束（第讲，两个约束（第2、3行）均取等号，即都是紧约束。行）均取等号，即都是紧约束。22* “DUAL PRICES” 给出对偶价格（或影子价格）的值给出对偶价格（或影子价格）的值:表示表示最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增量。的增量。 第第2、3行对偶价格分别为行对偶价格分别为 .090909，.545455。 “NO. ITERATIONS= 2” 表示用单纯形法进行了两次迭代。表示用单纯形法进行了两次迭代。 23*使用使用LINDOLINDO的一些注意事项的一些注意事项“”（或（或“=”（或（或“=”）功能相同）功能相同变量与系数间可有空格变量
15、与系数间可有空格(甚至回车甚至回车),但无运算符但无运算符变量名以字母开头，不能超过变量名以字母开头，不能超过8个字符个字符变量名不区分大小写（包括变量名不区分大小写（包括LINDO中的关键字）中的关键字）目标函数所在行是第一行，第二行起为约束条件目标函数所在行是第一行，第二行起为约束条件行号行号(行名行名)自动产生或人为定义。行名以自动产生或人为定义。行名以“）”结结束束行中注有行中注有“!”符号的后面部分为注释。如符号的后面部分为注释。如:!ItsComment.在模型的任何地方都可以用在模型的任何地方都可以用“TITLE”对模型命名对模型命名（最多（最多72个字符），如：个字符），如：T
16、ITLEThisModelisonlyanExample24*变量不能出现在一个约束条件的右端变量不能出现在一个约束条件的右端表达式中不接受括号表达式中不接受括号“()”和逗号和逗号“,”等任何符号等任何符号,例例:400(X1+X2)需写为需写为400X1+400X2表达式应化简，如表达式应化简，如2X1+3X2-4X1应写成应写成-2X1+3X2缺省假定所有变量非负；可在模型的缺省假定所有变量非负；可在模型的“END”语句后语句后用用“FREEname”将变量将变量name的非负假定取消的非负假定取消可在可在“END”后用后用“SUB”或或“SLB”设定变量上下界设定变量上下界例如：例如：
17、“subx110”的作用等价于的作用等价于“x1=10”但用但用“SUB”和和“SLB”表示的上下界约束不计入模型表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。的约束，也不能给出其松紧判断和敏感性分析。使用使用LINDOLINDO的一些注意事项的一些注意事项25*14.“END”后对后对0-1变量说明：变量说明：INTn或或INTname15.“END”后对整数变量说明：后对整数变量说明：GINn或或GINname使用使用LINDOLINDO的一些注意事项的一些注意事项16. 简单错误的检查和避免：简单错误的检查和避免： 输入模型时可能会有某些输入错误输入模型时可能会有某
18、些输入错误. 当问题规模当问题规模较大时较大时, 要查找错误是比较困难的。在要查找错误是比较困难的。在LINDO 中有一中有一些可帮助寻找错误的功能，其中之一就是菜单命令些可帮助寻找错误的功能，其中之一就是菜单命令“Report | Picture（Alt+5）” , 它的功能是可以将它的功能是可以将目标函数和约束表达式中的非零系数通过列表（或图目标函数和约束表达式中的非零系数通过列表（或图形）显示出来。形）显示出来。 26*三个变量范围限定命令三个变量范围限定命令(FREE(FREE、SUBSUB、SLB)SLB)的作用的作用 求解如下的求解如下的LP问题：问题： 这个模型中对变量这个模型中
19、对变量x没有非负限制，对没有非负限制，对y有上限限制，有上限限制，对对z有下限限制。用有下限限制。用FREE、SUB、SLB三个命令三个命令可以实现这些功能。可以实现这些功能。27*MAX 2x 3y + 4zS.T.con2) 4 x + 3y + 2z = 10con3) -3x + 5 y - z 8con5) -5x - y - z 2ENDfree x ! 说明：变量说明：变量x没有非负限制没有非负限制sub y 20 ! 说明：变量说明：变量y的上界为的上界为20slb z 30 ! 说明：变量说明：变量z的下界为的下界为30具体输入如下：具体输入如下： 求解得到的结果：最大值为求
20、解得到的结果：最大值为122，最优解为，最优解为x=-17，y=0，z=39。可以看出可以看出y的上界（的上界（20）在最优解中并没有达到，）在最优解中并没有达到，z的下界（的下界（30）也没有达到，）也没有达到，因此模型中去掉因此模型中去掉“sub y 20”和和“slb z 30”两个语句，得到的结不变。两个语句，得到的结不变。但由于最优解中但由于最优解中x的取值为负值，所以的取值为负值，所以“free x”这个语句确实是不能少的。不这个语句确实是不能少的。不妨试一下，去掉这个语句后效果会怎样？妨试一下，去掉这个语句后效果会怎样？ 28*LINGOLINGO入门入门设有线性规划模型如下：设
21、有线性规划模型如下：29*30*LINGO的语法规则1.最大值MAX=,最小值MIN=2.语句必须以分号”;”结束每行可多个语句语句可跨行3.变量名由字母、数字和下划线组成以字母开头长度不超32个字符不区分大小写4.默认决策变量非负其他要求可做说明5.模型以MODEL：开头，以END结束(此结构也可省略）6.注释以！开始，以;结束；7.可以用表示表示=31*程序语句输入的备注：程序语句输入的备注：LINGO总是根据总是根据“MAX=”或或“MIN=”寻找目标函数，而寻找目标函数，而除注释语句和除注释语句和TITLE语句外的其他语句都是约束条件，语句外的其他语句都是约束条件，因此语句的顺序并不重
22、要因此语句的顺序并不重要。限定变量取整数值的语句为限定变量取整数值的语句为“GIN(X1)”和和“GIN(X2)”，不可以写成，不可以写成“GIN(2)”，否则，否则LINGO将将把这个模型看成没有整数变量。把这个模型看成没有整数变量。LINGO中函数一律需要以中函数一律需要以“”开头，其中整型变量函开头，其中整型变量函数（数（BIN、GIN）和上下界限定函数（）和上下界限定函数（FREE、SUB、SLB）与）与LINDO中的命令类似。而且中的命令类似。而且0/1变量变量函数是函数是BIN函数。函数。32*一个简单的一个简单的LINGO程序程序例例 直接用LINGO来解如下二次规划问题：输入窗
23、口如下：输入窗口如下：33*输出结果：输出结果：运行菜单命令运行菜单命令“LINGO|Solve”最优整数解最优整数解X=(35，65)最大利润最大利润=11077.534*LINGO求解实例求解实例例例 1 1model:max=2*x1-3*x2-2*x3+x4;x1-2*x2-3*x3-2*x4=5;x1-x2+2*x3+x4=10;End35*Globaloptimalsolutionfoundatiteration:2Objective value: 18.33333VariableValueReducedCostX18.3333330.000000X20.0000000.66666
24、67X30.0000004.333333X41.6666670.000000RowSlackorSurplusDualPrice118.333331.00000020.0000000.333333330.0000001.666667运行结果如下运行结果如下: :36*看完例看完例1 1后后, ,能解下面这个问题吗能解下面这个问题吗? ?例例 2 237*例例 3 3model:!thisisanintegerprogrammingproblem;max=4*x1+3*x2;4*x1+x2=10;2*x1+3*x2=0;end42*Localoptimalsolutionfoundatitera
25、tion:37Objectivevalue:-6.000000VariableValueReducedCostX11.2128090.000000X21.2128090.000000X30.24122010.000000RowSlackorSurplusDualPrice1-6.000000-1.00000020.0000002.00000030.000000-2.425619运行结果如下运行结果如下: :43*例例1加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3千克A1 12小时 8小时 4千克A2 或获利24元/千克 获利16元/千克 50桶牛奶桶牛奶时间时间480小时小时 至多加工
26、至多加工100千克千克A1制订生产计划，使每天获利最大制订生产计划，使每天获利最大 35元可买到元可买到1桶牛奶，买吗？若买，每天最多买多少桶牛奶，买吗？若买，每天最多买多少?可聘用临时工人，付出的工资最多是每小时几元可聘用临时工人，付出的工资最多是每小时几元?A1的获利增加到的获利增加到30元元/千克，应否改变生产计划？千克，应否改变生产计划？每天：每天：三、建模实例三、建模实例44*1桶牛奶 3千克A1 12小时 8小时 4千克A2 或获利24元/千克 获利16元/千克 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2原料供应原料供应 劳动时间劳动时间 加工能力加工能力 决策变量决
27、策变量 目标函数目标函数 每天获利每天获利约束条件约束条件非负约束非负约束 线性线性规划规划模型模型(LP)时间时间480小时小时至多加工至多加工100千克千克A150桶牛奶桶牛奶每天每天45*模型求解模型求解 软件实现软件实现 LINDOmax72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100endOBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048
28、.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2DORANGE(SENSITIVITY)ANALYSIS?No20桶牛奶生产桶牛奶生产A1,30桶生产桶生产A2，利润，利润3360元。元。46*结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004
29、)40.0000000.000000NO.ITERATIONS=2原料无剩余原料无剩余时间无剩余时间无剩余加工能力剩余加工能力剩余40max72x1+64x2st2)x1+x2503)12x1+8x24804)3x1100end三三种种资资源源“资源资源”剩余为零的约束为紧约束（有效约束）剩余为零的约束为紧约束（有效约束）47*结果解释结果解释 OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0
30、0000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2最优解下最优解下“资源资源”增加增加1单位时单位时“效益效益”的增的增量量原料增加原料增加1单位单位,利润增长利润增长48时间增加时间增加1单位单位,利润增长利润增长2加工能力增长不影响利润加工能力增长不影响利润影子价格影子价格35元可买到元可买到1桶牛奶，要买吗？桶牛奶，要买吗？3548,应该买！应该买！聘用临时工人付出的工资最多每小时几元？聘用临时工人付出的工资最多每小时几元？2元！元！48*RANGESINWHICHTHEBASISISUNCHANGED:O
31、BJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最优解不变时目标函最优解不变时目标函数系数允
32、许变化范围数系数允许变化范围DORANGE(SENSITIVITY)ANALYSIS?Yesx1系数范围系数范围(64,96)x2系数范围系数范围(48,72)A1获利增加到获利增加到30元元/千克，应否改变生产计划千克，应否改变生产计划x1系数由系数由24 3=72增加增加为为30 3=90，在在允许范围内允许范围内不变！不变！(约束条件不变约束条件不变)49*结果解释结果解释 RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX1
33、72.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子价格有意义影子价格有意义时约束右端的允时约束右端的允许变化范围许变化范围原料最多增加原料最多增加10时间最多增加时间最多增加5335元可买到元可买到1桶牛奶，每天最多买多少？桶牛奶，每天最
34、多买多少？最多买最多买10桶桶(目标函数不变目标函数不变)50* 如果生产某一类型汽车，则至少要生产如果生产某一类型汽车，则至少要生产8080辆，辆， 那么最优的生产计划应作何改变？那么最优的生产计划应作何改变？例例2汽车厂生产计划汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。材、劳动时间的需求，利润及工厂每月的现有量。小型小型中型中型大型大型现有量现有量钢材（吨）钢材（吨）1.535600劳动时间（小时）劳动时间（小时）28025040060000利润（万元）利润（万元）234制订月生产计
35、划，使工厂的利润最大。制订月生产计划，使工厂的利润最大。51*设每月生产小、中、大型汽车的数量分别为设每月生产小、中、大型汽车的数量分别为x1, x2, x3汽车厂生产计划汽车厂生产计划 模型建立模型建立 小型小型中型中型大型大型现有量现有量钢材钢材1.535600时间时间28025040060000利润利润234线性线性规划规划模型模型(LP)52*模型模型求解求解 3）模型中增加条件：模型中增加条件：x1, x2, x3均为整数，重新求解。均为整数，重新求解。OBJECTIVEFUNCTIONVALUE1)632.2581VARIABLEVALUEREDUCEDCOSTX164.51612
36、90.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，通过比较可能得到更优的解。，通过比较可能得到更优的解。但必须检验它们是否满足约束条
37、件。为什么？但必须检验它们是否满足约束条件。为什么？53*IP可用可用LINDO直接求解直接求解整数规划整数规划( (IP) )“gin3”表示表示“前前3个变个变量为整数量为整数”，等价于：，等价于：ginx1ginx2ginx3IP的最优解的最优解x1=64，x2=168，x3=0，最优值，最优值z=632max2x1+3x2+4x3st1.5x1+3x2+5x3600280x1+250x2+400x30y=160*例例4: 4: 员工聘用方案决策变量决策变量：周一至周日每天：周一至周日每天(新新)聘用人数聘用人数x1, x2,x7目标函数目标函数：7天天(新新)聘用人数之和聘用人数之和约
38、束条件约束条件：周一至周日每天需要人数：周一至周日每天需要人数61*连续工作连续工作5天天周一工作的应是周一工作的应是(上上)周四至周一聘用的周四至周一聘用的设系统已进入稳态设系统已进入稳态聘用方案聘用方案整数规划整数规划模型模型(IP)(IP)62*首先在首先在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
39、) 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个变量都是一般整数变量。个变量都是一般整数变量。 （仍然默认为取值是非负的）（仍然默认为取值是非负的）63*求解后状态窗口中与整数相关的三个域有了相关结果求解后状态窗口中与整数相关的三个域有了相关结果:“Best IP ：94”表示当前表示当前得到的最好的整数解的目得到的最好的整数解的目标函数值为标函数值
40、为94（人）。（人）。“IP Bound ：93.5” 表示表示该整数规划目标值的下界该整数规划目标值的下界为为93.5 （人）。（人）。“Branches ：1”表示分枝表示分枝数为数为1（即在第（即在第1个分枝中个分枝中就找到了最优解）。就找到了最优解）。64* 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.0
41、00000 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求解结果的报告窗口
42、如下：求解结果的报告窗口如下： 65*生产中通过切割、剪裁、冲压等生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小手段，将原材料加工成所需大小例例5钢管和易拉罐下料钢管和易拉罐下料原料下料问题原料下料问题按照工艺要求，确定下料方案，按照工艺要求，确定下料方案，使所用材料最省，或利润最大使所用材料最省，或利润最大66*某钢管零售商从钢管厂进货，将钢管按照顾客的要某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都求切割后售出。从钢管厂进货时得到的原料钢管都是是19米长。米长。1) 现有一客户需要现有一客户需要50根根4米长、米长、20根根6米长和米长和
43、15根根8米长的钢管。应如何下料最节省？米长的钢管。应如何下料最节省？2) 零售商如果采用的不同切割模式太多，将会导零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要种。此外，该客户除需要1）中的三种钢管外，还）中的三种钢管外，还需要需要10根根5米长的钢管。应如何下料最节省？米长的钢管。应如何下料最节省？1、钢管下料钢管下料 67*问题问题1 1）的求解）的求解问题分析问题分析 首先，应当确定哪些切割模式是可
44、行首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以料钢管上安排切割的一种组合。例如，我们可以将将1919米长的钢管切割成米长的钢管切割成3 3根根4 4米长的钢管，余料为米长的钢管，余料为7 7米显然，可行的切割模式是很多的。米显然，可行的切割模式是很多的。 其次，应当确定哪些切割模式是合理的。通其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合或等于客户需要的钢管的最小尺寸。在
45、这种合理性假设下，切割模式一共有理性假设下，切割模式一共有7 7种，如表所示。种，如表所示。68*为满足客户需要，按照哪些种合理模式，每种模式为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？切割多少根原料钢管，最为节省？合理切割模式合理切割模式2.所用原料钢管总根数最少所用原料钢管总根数最少模式模式4米钢管根数米钢管根数6米钢管根数米钢管根数8米钢管根数米钢管根数余料余料(米米)14003231013201341203511116030170023钢管下料问题钢管下料问题1 1 两种两种标准标准1.原料钢管剩余总余量最小原料钢管剩余总余量最小69*xi 按第按第i 种
46、模式切割的原料钢管根数种模式切割的原料钢管根数( (i= =1,2,7) ) 约束约束满足需求满足需求 决策变量决策变量 目标目标1（总余量）（总余量）模模式式4米米根数根数6米米根数根数8米米根数根数余余料料14003231013201341203511116030170023需需求求502015整数约束：整数约束：xi 为整数为整数70*模型求解模型求解将整数线性规划模型（加上整数约束）输入将整数线性规划模型（加上整数约束）输入LINDO如下：如下：Title 钢管下料 - 最小化余量Min 3x1 + x2 + 3x3 + 3x4 + x5 + x6 + 3x7 s.t. 4x1 + 3
47、x2 + 2x3 + x4 + x5 = 50 x2 + 2x4 + x5 + 3x6 = 20 x3 + x5 + 2x7 = 15endgin 771*求解可以得到最优解如下：求解可以得到最优解如下：OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000按模式按模式2切割切割12根
48、根, ,按模式按模式5切割切割15根，余料根，余料27米米72*目标目标2（总根数）（总根数）钢管下料问题钢管下料问题1 1 约束条约束条件不变件不变 xi 为整数73*将整数线性规划模型（加上整数约束）输入将整数线性规划模型（加上整数约束）输入LINDOLINDO：Title钢管下料钢管下料-最小化钢管根数最小化钢管根数Minx1+x2+x3+x4+x5+x6+x7s.t.4x1+3x2+2x3+x4+x5=50x2+2x4+x5+3x6=20x3+x5+2x7=15endgin7模型求解模型求解74*求解，可以得到最优解如下：求解，可以得到最优解如下：OBJECTIVEFUNCTIONVA
49、LUE1)25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.00000075*当余料没有用处时，当余料没有用处时，通常以总根数最少为目标通常以总根数最少为目标 最优解：最优解：x2=15,x5=5,x7=5,其余为其余为0；最优值：最优值：25。按模式按模式2切割切割15根，根，按模式按模式5切割切割5根，根，按模式按模式7切割切割5根，根，
50、共共25根，余料根，余料35米米虽余料增加虽余料增加8米，但减少了米，但减少了2根根与与目标目标1的结果的结果“共切割共切割27根，余料根，余料27米米”相相比比76*钢管下料问题钢管下料问题2对大规模问题，用模型的约束条件界定合理模式对大规模问题，用模型的约束条件界定合理模式增加一种需求：增加一种需求：5米米10根；切割根；切割模式不超过模式不超过3种。种。现有现有4种种需求：需求：4米米50根，根，5米米10根，根，6米米20根，根，8米米15根，用枚举法确定合理切割模式，过于复杂。根，用枚举法确定合理切割模式，过于复杂。决策变量决策变量 xi 按第按第i 种模式切割的原料钢管根数种模式切
51、割的原料钢管根数( (i= =1,2,3) ) r1i, r2i, r3i, r4i 第第i 种切割模式下，每根原料钢管种切割模式下，每根原料钢管生产生产4米、米、5米、米、6米和米和8米长的钢管的数量米长的钢管的数量77*满足需求满足需求模式合理：每根模式合理：每根余料不超过余料不超过3米米整数非线性规划模型整数非线性规划模型钢管下料问题钢管下料问题2目标函数（目标函数（总根数）总根数）约束约束条件条件整数约束：整数约束：xi ,r1i, r2i, r3i, r4i ( (i= =1,2,3) )为整为整数数78*增加约束，缩小可行域，便于求解增加约束，缩小可行域，便于求解原料钢管总根数下界
52、：原料钢管总根数下界：特殊生产计划：对每根原料钢管特殊生产计划：对每根原料钢管模式模式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米米79*将模型输入LINGO如下：model:Title钢管下料钢管下料-最小化钢管根数的最小化钢管
53、根数的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=19;4*r12+5*r22+6*r32+8*r42=19;4*r13+5*r23+6*r33+8*r43=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(x
54、2);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 80*LINGO求解整数非线性规划模型求解整数非线性规划模型Localoptimalsolutionfoundatiteration:12211Objectivevalue:28.00000VariableValueReducedCostX110.000000.000000X210.000002.000000X38.0000001.000000R113
55、.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：每根原料钢管切割成：每根原料钢管切
56、割成2根根4米、米、1根根5米和米和1根根6米钢管，米钢管，共共10根；根；模式模式3：每根原料钢管切割成：每根原料钢管切割成2根根8米钢管，共米钢管，共8根。根。原料钢管总根数为原料钢管总根数为28根。根。81* 问题 某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的。易拉罐为圆柱形，包括罐身、上盖和下底，罐身高10cm，上盖和下底的直径均为5cm。该公司使用两种不同规格的镀锡板原料：规格1的镀锡板为正方形，边长24cm；规格2的镀锡板为长方形，长、宽分别为32cm和28cm。由于生产设备和生产工艺的限制，对于规格1的镀锡板原料，只可以按照模式1、模式2或模式3
57、进行冲压；对于规格2的镀锡板原料只能按照模式4进行冲压。使用模式1、模式2、模式3、模式4进行每次冲压所需要的时间分别为1.5s、2s、1s、3s。2、易拉罐下料易拉罐下料82* 该工厂每周工作40小时，每周可供使用的规格1、规格2的镀锡板原料分别为5万张和2万张。目前每只易拉罐的利润为0.10元，原料余料损失为0.001元/平方厘米（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。 问工厂应如何安排每周的生产？83*板材板材规格规格2：长方形，长方形，32 28cm，2万张。万张。问题分析问题分析模式模式1：1.5秒秒模式模式2：2秒秒模式模式3：1秒秒模式模式4
58、：3秒秒上盖上盖下底下底罐罐身身罐身高罐身高10cm，上上盖盖、下底直、下底直径均径均5cm。板材规格板材规格1：正方形，边长正方形，边长24cm，5万张。万张。84*罐身个数罐身个数底、盖底、盖个数个数余料损失余料损失（cm2）冲压时间冲压时间（秒）（秒）模式模式1110222.61.5模式模式224183.32模式模式3016261.81模式模式445169.53模式模式1:正方形正方形边长边长24cm问题分析问题分析计算各种模式下的余料损失计算各种模式下的余料损失上、下底直径上、下底直径d=5cm，罐身高罐身高h=10cm。模式模式1余料损失余料损失242-10 d2/4- dh=222
59、.6cm285*问题分析问题分析目标目标: :易拉罐利润扣除原料余料损失后的净利润最大易拉罐利润扣除原料余料损失后的净利润最大 约束：约束：每周工作时间不超过每周工作时间不超过40小时；小时；原料数量：原料数量：规格规格1（模式（模式13）5万张，万张， 规格规格2（模式（模式4）2万张；万张；罐身和底、盖的配套组装罐身和底、盖的配套组装。注意：不能装配的罐身、上下底也是余料注意：不能装配的罐身、上下底也是余料决策决策变量变量 xi 按照第按照第i 种模式的生产张数种模式的生产张数( (i= =1,2,3,4) )；y1一周生产的易拉罐个数；一周生产的易拉罐个数；y2 不配套的罐身个数；不配套
60、的罐身个数；y3 不配套的底、盖个数。不配套的底、盖个数。 模型建立模型建立86*目标目标 约束约束条件条件 时间约束时间约束 原料约束原料约束 产量产量余料余料时间时间x1222.61.5x2183.32x3261.81x4169.53模型建立模型建立y1易拉罐个数；易拉罐个数；y2 不配套的罐身；不配套的罐身；y3 不配套的底、盖。不配套的底、盖。每只易拉罐利润每只易拉罐利润0.10元，元，余料损失余料损失0.001元元/cm2罐身罐身面积面积 dh=157.1cm2底盖底盖面积面积 d2/4=19.6cm2(40小时小时)87*约束条件约束条件 配套约束配套约束 y1易拉罐个数；易拉罐个
61、数；y2 不配套的罐身；不配套的罐身；y3 不配套的底、盖。不配套的底、盖。罐身罐身底、盖底、盖1102401645产量产量x1x2x3x4虽然虽然xi和和y1，y2，y3应是整数，但是因生产量很大，应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理可以把它们看成实数，从而用线性规划模型处理。88*LINDO发出警告信息：发出警告信息：“数据之间的数量级差别太数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别大，建议进行预处理，缩小数据之间的差别”模型求解模型求解OBJECTIVEFUNCTIONVALUE1)4298.337VARIABLEVALUEREDUCE
62、DCOSTY1160250.0000000.000000X10.0000000.000050X240125.0000000.000000X33750.0000000.000000X420000.0000000.000000Y20.0000000.223331Y30.0000000.03648489*模型中数据不平衡的警告信息模型中数据不平衡的警告信息90*输入输入LINDO:!易拉罐下料：均衡数据易拉罐下料：均衡数据Max0.100y1-0.2226x1-0.1833x2-0.2618x3-0.1695x4-0.1571y2-0.0196y3s.t.1.5x1+2.0x2+1.0x3+3.0x
63、4=14.4x1+x2+x3=5x4=010x1+4x2+16x3+5x4-2y1=0x1+2x2+4x4-y1-y2=010x1+4x2+16x3+5x4-2y1-y3=0将所有决策变量扩大将所有决策变量扩大10000倍（倍（xi 万张，万张，yi 万件）万件） 91*模式模式2生产生产40125张，模式张，模式3生产生产3750张，张，模式模式4生产生产20000张，张，共产易拉罐共产易拉罐160250个个( (罐身和底、盖无剩罐身和底、盖无剩余余) )，净利润为，净利润为4298元元OBJECTIVEFUNCTIONVALUE1)0.4298337VARIABLEVALUEREDUCED
64、COSTY116.0250000.000000X10.0000000.000050X24.0125000.000000X30.3750000.000000X42.0000000.000000Y20.0000000.223331Y30.0000000.036484求解得到求解得到：92*下料问题的建模下料问题的建模 确定下料模式确定下料模式构造优化模型构造优化模型规格不太多，可枚举下料模式，建立整数线性规划规格不太多，可枚举下料模式，建立整数线性规划模型，否则要构造整数非线性规划模型，求解困难，模型，否则要构造整数非线性规划模型，求解困难，可用可用缩小可行域缩小可行域的方法进行化简，但要保证最优
65、解的方法进行化简，但要保证最优解的存在。的存在。一维问题（如钢管下料）一维问题（如钢管下料）二维问题（如易拉罐下料）二维问题（如易拉罐下料）具体问题具体分析（比较复杂具体问题具体分析（比较复杂）93*LINGOLINGO模型模型 例：选址问题例：选址问题某公司有某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi)(单位：公里单位：公里),水泥日用量水泥日用量di(单位：吨）单位：吨）假设：假设：料场料场和工地之间和工地之间有直线道路有直线道路94*用例中数据计算，最优解为总吨公里数为总吨公里数为总吨公里数为总吨公里数为136.2136.2线性规划模型线性规划模型决策变量：决策变
66、量：ci j(料场料场j到到工地工地i的的运量）运量）12维维95*选址问题：选址问题：NLPNLP2）改建两个新料场，需要确定新料场位置）改建两个新料场，需要确定新料场位置(xj,yj)和和运量运量cij，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。决策变量：决策变量：ci j，(xj,yj)16维维非线性规划模型非线性规划模型96*LINGO模型的构成：模型的构成：4个段个段集合段（集合段（SETSENDSETS）数据段（数据段（DATAENDDATA）初始段（初始段（INITENDINIT）目标与目标与约束段约束段局部最优：局部最优：89.8835(吨公里吨公里
67、 )LP：移到数据段：移到数据段97*边界98*四、四、LINGOLINGO的建模语言的建模语言以以运输问题运输问题逐步分析逐步分析6个仓库向个仓库向8个小贩供应同一种货物，个小贩供应同一种货物，如何运如何运,总运输费用最小？总运输费用最小？注：每个仓库可以向每个小贩供货，注：每个仓库可以向每个小贩供货，一共一共4848个可能运货路线。个可能运货路线。 仓库货存量、小贩需求量、每条路线仓库货存量、小贩需求量、每条路线的单位运输费用三个表如下：的单位运输费用三个表如下：99*仓库货存量：仓库货存量：capacitycapacity100*小贩需求量：小贩需求量：demanddemand101*每
68、单位货物运输费用表：每单位货物运输费用表：costcost102*demand_ j 表示第表示第j个小贩个小贩的需求量的需求量capacity_i 表示第表示第i个仓库的个仓库的库存量库存量cost_i_ j 表示从第表示从第i个仓个仓库到第库到第j个小贩的单位运输费用个小贩的单位运输费用已已知知数数量量决策变量决策变量volume_i_ j 表示从第表示从第i个仓库到个仓库到第第j个小贩的运输量个小贩的运输量103*数学模型可表示如下：数学模型可表示如下：104*当然目标函数可以如下输入当然目标函数可以如下输入: min = 6 * volume_1_1 + 2 * volume_1_2
69、+ 6 * volume_1_3 + . 1 * volume_6_6 + 4 * volume_6_7 + 3 * volume_6_8;105* 但是较大模型如果像上面那样但是较大模型如果像上面那样输入又费时，又容易出错！输入又费时，又容易出错！ 这就需要这就需要LINGOLINGO的的建模语言建模语言106*LINGOLINGO的的建模语言建模语言优点优点: :1)1)可以用可以用类似于标准数学符号类似于标准数学符号的方式的方式表示你的模型；表示你的模型；2)2)可以用可以用一个紧凑的语句一个紧凑的语句表示表示一系列一系列约束约束。3)3)数据可独立于模型数据可独立于模型：LINGOLI
70、NGO可以从可以从文本文件、电子数据表、数据库中读文本文件、电子数据表、数据库中读取数据。取数据。107*LINGOLINGO模型的构成：模型的构成：5 5个段个段 目标函数与约束条件段目标函数与约束条件段 集合段（集合段（sets: endsetssets: endsets） 数据段（数据段（data: enddatadata: enddata） 初始段（初始段（init: endinitinit: endinit） 计算段（计算段（calccalc： endcalcendcalc）LingoLingo建模语言的重点和难点是：建模语言的重点和难点是：对对集合集合概念的理解和正确使用概念的理解
71、和正确使用108*为什么使用为什么使用集合集合 集集合合是是L LI IN NG GO O建建模模语语言言的的基基础础，是是L LI IN NG GO O程程序序设设计计最最强强有有力力的的基基本本构构件件。借借助助于于集集合合，能能够够用用一一个个单单一一的的、长长的的、简简明明的的复复合合公公式式表表示示一一系系列列相相似似的的约约束束，从从而而可可以以快快速速方方便便 地地 表表 达达 规规 模模 较较 大大 的的 模模 型型 。109*什么是集合什么是集合 集合是一群相联系的对象，比如集合是一群相联系的对象，比如仓库、小贩仓库、小贩、运输路线，运输路线，这些对象也这些对象也称为集合的称
72、为集合的成员成员。每个集合成员可能。每个集合成员可能有一个或多个与之有关联的特征，我有一个或多个与之有关联的特征，我们把这些特征称为们把这些特征称为属性属性。 属性值可以预先给定，也可以是属性值可以预先给定，也可以是未知的，有待于未知的，有待于LINGOLINGO求解。求解。 110*从我们的数学模型看需要三个集合：从我们的数学模型看需要三个集合：（1 1）仓库仓库- -6 6个成员个成员- -货存量货存量（2 2）小贩小贩- -8 8个成员个成员- -需求量需求量（3 3）运输路线运输路线- -4848个成员个成员 - -单位运费单位运费和和运货量运货量111*LINGOLINGO有两种类型
73、的集合有两种类型的集合原始集合原始集合(primitive set)(primitive set)：由一些：由一些最基本的对象组成的。最基本的对象组成的。派生集派生集(derived set): (derived set): 用一个或多用一个或多个其它集来定义的，也就是说，它个其它集来定义的，也就是说，它的成员来自于其它已存在的集。的成员来自于其它已存在的集。112*下面我们学习集合定义部分下面我们学习集合定义部分*1. 以以sets:开始，以开始，以endsets结束；结束； sets: endsets113*2. 2. 原始集合定义法：原始集合定义法：setname /member_lis
74、t/ :attribute_list ;。setname是集合的名字；是集合的名字；。member_list是成员列表是成员列表,各成员之间可用各成员之间可用空格空格或或逗号逗号分隔；分隔；。attribute_list是集合成员所具有的属性列是集合成员所具有的属性列表，多个属性之间用表，多个属性之间用逗号逗号分隔；分隔；。原始集合的。原始集合的member_list, attribute_list是可选项；是可选项；114* *仓库和小贩的集合可如下定义仓库和小贩的集合可如下定义* *sets: warehouses / w1 w2 w3 w4 w5 w6 /: capacity; vend
75、ors / v1,v2,v3,v4,v5,v6, v7,v8 / : demand;endsets115* *仓库和小贩的集合也可如下定义仓库和小贩的集合也可如下定义* *sets: warehouses / w1.w6/: capacity; vendors / v1.v8 /: demand;endsets116*3. 派生集合定义法：派生集合定义法：setname (parent_set_list) /member_list/ :attribute_list;parent_set_list是父集合名列表是父集合名列表117*48条运输路线集合定义条运输路线集合定义*links(wareh
76、ouses,vendors) : cost, volume；118* *三个集合定义如下三个集合定义如下* *sets: warehouses / wh1.wh6 /: capacity; vendors / v1.v8 /: demand; links( warehouses, vendors): cost，volume；endsets119*运输问题的三个集合说明：运输问题的三个集合说明：这段代码定义了这段代码定义了4个属性值，在接下来个属性值，在接下来的模型中就可以使用属性值的模型中就可以使用属性值capacity(1),capacity(2),capacity(6);demand(1)
77、,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。120*4.4.集合成员过滤：集合成员过滤：trucks/1.100/:capacity;heavy_duty (trucks) | capacity(&1) #gt# 50000 : ; &1是集合索引号放置器，是集合索引号放置器，如果有两个父集合，就是如果有两个父集合，就是&1,&2121*下面我们学习数据定义下面我们学习数据定义*
78、* 以以data:开始，以开始，以enddata结束；结束； data: . enddata122*例如：设有如下集合例如：设有如下集合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，则数据段可以为则数据段可以为123* data: x=1,2,3; y=4 5 6; enddatadata: x,y=1 4 2 5 3 6; enddata 多个数据之间可用多个数据之间可用逗号逗号或或空格空格分隔分隔 124*若成员属性值相同，数据段定义如下：若成员属性值相同，数据段定义如下：d
79、ata:x=3;!(所有成员的所有成员的x=3);y=6;!(所有成员的所有成员的y=6);enddata 125*也可以在运行时输入属性值：也可以在运行时输入属性值：data: x=?; ！(运行时输入所有运行时输入所有成员的成员的x值值); y=6; enddata126* *运输问题的数据部分运输问题的数据部分* *data:capacity=60,55,51,43,41,52;demand=35 37 22 32 41 32 43 38;127*cost = 6 2 6 7 4 2 5 9 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1
80、2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3;enddata128*sets: sett : x, y ;endsetsdata: sett, x, y = a 1 4 b 2 5 c 3 6;enddata sets: sett/a,b,c/ : x, y ;endsetsdata: x =1 2 3; y=4 5 6; enddata 集合成员可以在数据段定义：集合成员可以在数据段定义：129*运输实例：运输实例：sets:warehouses:capacity;endsetsdata:!可以写成可以写成warehouses=w1.w6;!也可以同时定义集合成员列表和属性
81、值也可以同时定义集合成员列表和属性值;warehouses,capacity=w160,w255,w351,w443,w541,w652;enddata130* * * 初始化定义初始化定义* 只在只在非线性规划非线性规划中使用，指定初中使用，指定初始值。始值。 init: . endinit131* 例：例： init: x=0.999; y=0.002; endinit y=log(x); x2+y2=1;给了恰当的初始值，会减少运算时间。给了恰当的初始值，会减少运算时间。132*计算段定义计算段定义*calc: . . .endcalc计算段的作用计算段的作用： 在模型输入后，在模型输入
82、后，LINGOLINGO开始正式求解模开始正式求解模型之前对原始数据进行一定的计算，得到型之前对原始数据进行一定的计算，得到我们模型中要使用的部分数据。我们模型中要使用的部分数据。133*一个简单的计算段例子一个简单的计算段例子:model:data:x,y,z=1,2,3;enddatacalc:avg=(x+y+z)/3;endcalcend134*目标函数和约束条件段目标函数和约束条件段* LINGO LINGO提供了提供了集合循环函数集合循环函数和和集合操作集合操作函数函数使得目标函数和约束条件的书写如同使得目标函数和约束条件的书写如同数学公式那样简单。数学公式那样简单。四个集合循环函
83、数四个集合循环函数FOR、SUM 、 MAX、MIN135*sum ( setname ( set_index_list) | condition : expression);求和求和136* *运输问题的目标函数运输问题的目标函数* *min = sum( links ( i, j) : cost( i, j) * volume( i, j) );min = sum( links : cost* volume );137* *运输问题实例中的求和运输问题实例中的求和* *！从！从6 6个仓库发到个仓库发到第第j j个小贩的货物个小贩的货物量总和量总和；sum( warehouses(i) :
84、 volume(i, j) );138*从从第第i i个仓库发出个仓库发出到到8 8个小贩个小贩的货物量总和的货物量总和；sum( vendors(j) : volume( i , j ) )139*for ( setname ( set_index_list) | condition : expression_list ); 生成约束生成约束for for 对集合对集合setnamesetname中的每个成员独立地生中的每个成员独立地生成约束，约束由约束表达式列表成约束，约束由约束表达式列表expression_listexpression_list描述描述; ; 多个表达式之间用多个表达式
85、之间用分号相隔。分号相隔。140* *每个小贩的需求约束每个小贩的需求约束* *！（要求！（要求6个仓库发给个仓库发给每个小贩每个小贩的的货物总货物总量量=小贩的需求量小贩的需求量）；for( vendors(j) : sum( warehouses( i): volume( i, j) ) =demand( j) );141* *每个仓库的供货约束每个仓库的供货约束* *for( warehouses( i) : sum( vendors(j) : volume( i, j) ) capacity( i) );！（要求！（要求每个仓库发给每个仓库发给8 8个小贩的个小贩的货物总量货物总量 仓
86、库的货存量仓库的货存量）；）；142*使用LINGO软件，编制程序如下：model:!6发点8收点运输问题;sets: warehouses/wh1.wh6/: capacity; vendors/v1.v8/: demand; links(warehouses,vendors): cost, volume;endsets!目标函数; min=sum(links: cost*volume);!需求约束; for(vendors(J): sum(warehouses(I): volume(I,J)=demand(J);!产量约束; for(warehouses(I): sum(vendors(J
87、): volume(I,J)=capacity(I);* *运输问题的完整模型运输问题的完整模型143*!这里是数据;data: capacity=60 55 51 43 41 52; demand=35 37 22 32 41 32 43 38; cost=6 2 6 7 4 2 9 5 4 9 5 3 8 5 8 2 5 2 1 9 7 4 3 3 7 6 7 3 9 2 7 1 2 3 9 5 7 2 6 5 5 5 2 2 8 1 4 3;enddataend然后点击工具条上的按钮 即可。144*建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1 1、尽量使用尽量使用实数优化
88、实数优化，减少整数约，减少整数约束和整数变量束和整数变量2 2、尽量使用尽量使用光滑优化光滑优化，减少非光滑，减少非光滑约束的个数约束的个数 如：尽量少使用绝对值、符号函数、如：尽量少使用绝对值、符号函数、多个变量求最大多个变量求最大/ /最小值、四舍五入、最小值、四舍五入、取整函数等取整函数等145*建模时需要注意的几个基本问题建模时需要注意的几个基本问题 3 3、尽量使用尽量使用线性模型线性模型，减少非线性约，减少非线性约束和非线性变量的个数束和非线性变量的个数 （如（如x/y 5 改为改为x5y）4 4、合理设定合理设定变量上下界变量上下界，尽可能给出，尽可能给出变量初始值变量初始值 5
89、 5、模型中使用的模型中使用的参数数量级参数数量级要适当要适当( (如小于如小于10103 3) )146*某储蓄所每天的营业时间为上午某储蓄所每天的营业时间为上午9点到下午点到下午5点点.根据经验根据经验,每天不同时间所需要的服务员数每天不同时间所需要的服务员数量为量为:练习1 服务人员安排问题147*储蓄所可以雇用全时和半时两类服务员储蓄所可以雇用全时和半时两类服务员.全全时服务员每天报酬时服务员每天报酬100元元,从上午从上午9点到下午点到下午5点点工作工作,但中午但中午12点到下午点到下午2点之间必须安排点之间必须安排1小时小时的午餐时间储蓄所每天还可以雇用不超过的午餐时间储蓄所每天还
90、可以雇用不超过3名名的半时服务员的半时服务员,每个半时服务员必须连续工作每个半时服务员必须连续工作4小时小时,报酬报酬40元元,问该储蓄所该如何雇用全时和问该储蓄所该如何雇用全时和半时服务员？如果不能雇用半时服务员半时服务员？如果不能雇用半时服务员,每天至每天至少增加多少费用？如果雇用半时服务员的数量没少增加多少费用？如果雇用半时服务员的数量没有限制有限制,每天可以减少多少费用每天可以减少多少费用?148*分析分析解决此问题的关键是确定雇用全时服务员及半解决此问题的关键是确定雇用全时服务员及半时服务员的人数时服务员的人数,但还要考虑全时服务员有吃午但还要考虑全时服务员有吃午餐的时间餐的时间,故
91、把全时服务员分为两类故把全时服务员分为两类:午餐时间午餐时间为为12时至下午时至下午1时的及下午时的及下午1时至下午时至下午2时的时的;而而半时服务员按上班时间进行划分半时服务员按上班时间进行划分.149*模型建立模型建立设设为午餐时间为下午为午餐时间为下午12时的全时服务员的人数时的全时服务员的人数,为午餐时间为下午为午餐时间为下午1时的全时服务员的人数时的全时服务员的人数,而而分别分别表示从表示从9点点,10点点,11点点,1点开始上班的半时服务员点开始上班的半时服务员人数人数,则目标函数为则目标函数为约束条件按各个小时需要的服务员人数确定约束条件按各个小时需要的服务员人数确定,则有则有1
92、50*151*此外此外,对半时服务员人数的限制对半时服务员人数的限制对决策变量的限制为对决策变量的限制为为整数为整数.由上述分析由上述分析,得到相应的数学模型为得到相应的数学模型为152*为整数为整数.153*模型求解模型求解利用利用LINDO软件得到问题的解软件得到问题的解:若不能雇佣半时服务员若不能雇佣半时服务员,则最优解为则最优解为因而多支出因而多支出元元.若对半时服务员人数没有限制若对半时服务员人数没有限制,则最优解为则最优解为节省开支节省开支元元.154*用用4台机床加工台机床加工3件产品。各产品的机床加工顺件产品。各产品的机床加工顺序，以及产品序，以及产品i在机床在机床j上的加工工
93、时上的加工工时aij如下表。由如下表。由于某种原因，产品于某种原因，产品2的加工总时间不得超过的加工总时间不得超过d，现要，现要求确定各件产品在机床上的加工方案，使在最短的求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。时间内加工完全部产品。a32a33机床机床2机床机床3产品产品3a21a22a24机床机床1机床机床2机床机床4产品产品2a11a13a14机床机床1机床机床3机床机床4产品产品1练习2 机床加工顺序问题155*解：设解：设xij表示产品表示产品i在机床在机床j上开始加工的时间上开始加工的时间(i=1,2,3;j=1,2,3,4)(不妨记开始为不妨记开始为0时
94、刻时刻)下面将逐步列出问题的整数规划模型下面将逐步列出问题的整数规划模型1、同一件产品在不同机床上的加工顺序约束、同一件产品在不同机床上的加工顺序约束对于同一件产品，在下一台机床上加工的开始时对于同一件产品，在下一台机床上加工的开始时间不得早于在上一台机床上加工的约束时间，故间不得早于在上一台机床上加工的约束时间，故应有：应有：产品产品1：及及产品产品2：及及产品产品3：156*2、每一台机床对不同产品的加工顺序约束、每一台机床对不同产品的加工顺序约束一台机床在工作中，如已开始的加工还没有结束，一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工。对于机床则不能开始另一件产品
95、的加工。对于机床1，有两，有两种加工顺序。或先加工产品种加工顺序。或先加工产品1，后加工产品，后加工产品2；或反；或反之。对于其它之。对于其它3台机床，情况也类似。为了容纳两台机床，情况也类似。为了容纳两种相互排斥的约束条件，对于每台机床，分别引入种相互排斥的约束条件，对于每台机床，分别引入0-1变量变量各各yj的意义是明显的。如当的意义是明显的。如当y1=0时，表示机床时，表示机床1先加先加工产品工产品1，后加工产品，后加工产品2，当，当y1=1时，表示机床时，表示机床1先加先加工产品工产品2，后加工产品，后加工产品1。157*机床机床1：及及机床机床2：及及机床机床3：及及机床机床4：及及
96、那么，每台机床上的加工产品的顺序可用下列四那么，每台机床上的加工产品的顺序可用下列四组约束条件来保证组约束条件来保证158*3、产品、产品2的加工时间约束的加工时间约束产品产品2的开始加工时间是的开始加工时间是x21，结束加工时间是，结束加工时间是x24+a24故应有：故应有：4、目标函数的建立、目标函数的建立设全部产品加工完毕的结束时间为设全部产品加工完毕的结束时间为w，由于三件产，由于三件产品的加工结束时间分别为品的加工结束时间分别为x14+a14，x24+a24，x33+a33，故全部产品的实际加工结束时间为：故全部产品的实际加工结束时间为：159*转化为线性表达式：转化为线性表达式：整理即的数学规划模型。整理即的数学规划模型。160
