《数学规划及软件》PPT课件.ppt

2020年4月29日星期三5时4分54秒,王文祥2013.7,数学规划模型、案例与软件求解,2020年4月29日星期三5时4分54秒,一.数学规划模型与优化软件简介,二.LINDO/LINGO软件,Outline,四.LINGO建模语言,三.建模实例,2020年4月29日星期三5时4分54秒,数学规划是优化问题的一个分支，起始于20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有一半以上的问题可用数学规划进行求解。,一.数学规划模型与优化软件简介,2020年4月29日星期三5时4分54秒,数学规划模型的一般形式,可行域,三要素：决策变量；目标函数；约束条件,可行解（只满足约束）与最优解(取到最优值),“受约束于”之意,2020年4月29日星期三5时4分54秒,数学规划类型,连续规划:全部决策变量取值均为连续数值(实数)离散规划:部分或全部决策变量只取离散数值,2020年4月29日星期三5时4分54秒,线性规划(LP)目标和约束均为线性函数非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划,连续规划,离散规划,数学规划(MathematicalProgramming),2020年4月29日星期三5时4分54秒,常用优化软件,LINDO/LINGO软件MATLAB优化工具箱/mathematica优化程序包EXCEL软件的优化功能SAS(统计分析)软件的优化功能,2020年4月29日星期三5时4分54秒,LINDO公司软件产品简要介绍,美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：,LINDO:LinearInteractionandDiscreteOptimizerLINGO:LinearInteractionGeneralOptimizer,2020年4月29日星期三5时4分54秒,LINDO和LINGO能求解的数学规划模型,LINGO,LINDO,数学规划模型,线性规划(LP),非线性规划(NLP),二次规划(QP),连续规划,整数规划(IP),2020年4月29日星期三5时4分54秒,LINDO是专门用于求解数学规划的软件包。LINDO执行速度很快、易于方便输入，因此在数学、科研和工业界得到广泛应用。LINDO主要用于解线性规划、二次规划。也可以用于线性方程组的求解以及代数方程求根等。LINDO中包含了建模语言和许多常用的数学函数（包括大量概论函数），可供使用者建立规划问题时调用。一般用LINDO（LinearInteractiveandDiscreteOptimizer）解决线性规划,二.LINDO/LINGO软件简介,2020年4月29日星期三5时4分54秒,最大规模的模型的非零系数可以达到1,000,000个最大变量个数可以达到100,000个，最大目标函数和约束条件个数可以达到32000个最大整数变量个数可以达到100,000个LINDO6.1学生版至多可求解多达300个变量和150个约束的规划问题,2020年4月29日星期三5时4分54秒,1.求解线性规划和非线性规划问题2.模型输入简练直观3.运行速度快计算能力强4.内置建模语言提供内部函数较少语句直观描述大规模优化模型5.引入集合容易建模6.数据交换方便(与EXCEL和数据库),LINGO软件的主要功能和特点,2020年4月29日星期三5时4分54秒,例1简单的线性规划（LP）问题：,在空白的模型窗口中输入这个LP模型：,max2x+3yst4x+3y<=103x+5y”（或“=”（或“<=”）功能相同变量与系数间可有空格(甚至回车),但无运算符变量名以字母开头，不能超过8个字符变量名不区分大小写（包括LINDO中的关键字）目标函数所在行是第一行，第二行起为约束条件行号(行名)自动产生或人为定义。行名以“）”结束行中注有“!”符号的后面部分为注释。如:!ItsComment.在模型的任何地方都可以用“TITLE”对模型命名（最多72个字符），如：TITLEThisModelisonlyanExample,2020年4月29日星期三5时4分54秒,变量不能出现在一个约束条件的右端表达式中不接受括号“()”和逗号“,”等任何符号,例:400(X1+X2)需写为400X1+400X2表达式应化简，如2X1+3X2-4X1应写成-2X1+3X2缺省假定所有变量非负；可在模型的“END”语句后用“FREEname”将变量name的非负假定取消可在“END”后用“SUB”或“SLB”设定变量上下界例如：“subx110”的作用等价于“x12ENDfreex!说明：变量x没有非负限制suby20!说明：变量y的上界为20slbz30!说明：变量z的下界为30,具体输入如下：,求解得到的结果：最大值为122，最优解为x=-17，y=0，z=39。可以看出y的上界（20）在最优解中并没有达到，z的下界（30）也没有达到，因此模型中去掉“suby20”和“slbz30”两个语句，得到的结不变。但由于最优解中x的取值为负值，所以“freex”这个语句确实是不能少的。不妨试一下，去掉这个语句后效果会怎样？,2020年4月29日星期三5时4分54秒,LINGO入门,设有线性规划模型如下：,2020年4月29日星期三5时4分54秒,2020年4月29日星期三5时4分54秒,LINGO的语法规则,1.最大值MAX=,最小值MIN=2.语句必须以分号”;”结束每行可多个语句语句可跨行3.变量名由字母、数字和下划线组成以字母开头长度不超32个字符不区分大小写4.默认决策变量非负其他要求可做说明5.模型以MODEL：开头，以END结束(此结构也可省略）6.注释以！开始，以;结束；7.可以用表示>=,2020年4月29日星期三5时4分54秒,程序语句输入的备注：,LINGO总是根据“MAX=”或“MIN=”寻找目标函数，而除注释语句和TITLE语句外的其他语句都是约束条件，因此语句的顺序并不重要。限定变量取整数值的语句为“GIN(X1)”和“GIN(X2)”，不可以写成“GIN(2)”，否则LINGO将把这个模型看成没有整数变量。LINGO中函数一律需要以“”开头，其中整型变量函数（BIN、GIN）和上下界限定函数（FREE、SUB、SLB）与LINDO中的命令类似。而且0/1变量函数是BIN函数。,2020年4月29日星期三5时4分54秒,一个简单的LINGO程序,例直接用LINGO来解如下二次规划问题：,输入窗口如下：,2020年4月29日星期三5时4分54秒,输出结果：,运行菜单命令“LINGO|Solve”,最优整数解X=(35，65),最大利润=11077.5,2020年4月29日星期三5时4分54秒,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,2020年4月29日星期三5时4分54秒,Globaloptimalsolutionfoundatiteration:2Objectivevalue:18.33333VariableValueReducedCostX18.3333330.000000X20.0000000.6666667X30.0000004.333333X41.6666670.000000RowSlackorSurplusDualPrice118.333331.00000020.0000000.333333330.0000001.666667,运行结果如下:,2020年4月29日星期三5时4分54秒,看完例1后,能解下面这个问题吗?,例2,2020年4月29日星期三5时4分54秒,例3,model:!thisisanintegerprogrammingproblem;max=4*x1+3*x2;4*x1+x2<=10;2*x1+3*x2=0;end,2020年4月29日星期三5时4分54秒,Localoptimalsolutionfoundatiteration:37Objectivevalue:-6.000000VariableValueReducedCostX11.2128090.000000X21.2128090.000000X30.24122010.000000RowSlackorSurplusDualPrice1-6.000000-1.00000020.0000002.00000030.000000-2.425619,运行结果如下:,2020年4月29日星期三5时4分54秒,例1加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100千克A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到30元/千克，应否改变生产计划？,每天：,三、建模实例,2020年4月29日星期三5时4分54秒,x1桶牛奶生产A1,x2桶牛奶生产A2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100千克A1,2020年4月29日星期三5时4分54秒,模型求解,软件实现,LINDO,max72x1+64x2st2)x1+x2<503)12x1+8x2<4804)3x1<100end,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元。,2020年4月29日星期三5时4分54秒,结果解释,OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2,原料无剩余,时间无剩余,加工能力剩余40,max72x1+64x2st2)x1+x2<503)12x1+8x2<4804)3x1<100end,三种资源,“资源”剩余为零的约束为紧约束（有效约束）,2020年4月29日星期三5时4分54秒,结果解释,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桶牛奶，要买吗？,35<48,应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,2020年4月29日星期三5时4分54秒,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，在允许范围内,不变！,(约束条件不变),2020年4月29日星期三5时4分54秒,结果解释,RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000,影子价格有意义时约束右端的允许变化范围,原料最多增加10,时间最多增加53,35元可买到1桶牛奶，每天最多买多少？,最多买10桶,(目标函数不变),2020年4月29日星期三5时4分54秒,如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？,例2汽车厂生产计划,汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量。,制订月生产计划，使工厂的利润最大。,2020年4月29日星期三5时4分54秒,设每月生产小、中、大型汽车的数量分别为x1,x2,x3,汽车厂生产计划,模型建立,线性规划模型(LP),2020年4月29日星期三5时4分54秒,模型求解,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，通过比较可能得到更优的解。,但必须检验它们是否满足约束条件。为什么？,2020年4月29日星期三5时4分54秒,IP可用LINDO直接求解,整数规划(IP),“gin3”表示“前3个变量为整数”，等价于：ginx1ginx2ginx3,IP的最优解x1=64，x2=168，x3=0，最优值z=632,max2x1+3x2+4x3st1.5x1+3x2+5x3<600280 x1+250 x2+400 x3=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>=90ENDGIN7,其中“GIN7”表示7个变量都是一般整数变量。（仍然默认为取值是非负的）,2020年4月29日星期三5时4分54秒,求解后状态窗口中与整数相关的三个域有了相关结果:,“BestIP：94”表示当前得到的最好的整数解的目标函数值为94（人）。“IPBound：93.5”表示该整数规划目标值的下界为93.5（人）。“Branches：1”表示分枝数为1（即在第1个分枝中就找到了最优解）。,2020年4月29日星期三5时4分54秒,OBJECTIVEFUNCTIONVALUE1)94.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X24.0000001.000000X340.0000001.000000X42.0000001.000000X534.0000001.000000X610.0000001.000000X74.0000001.000000ROWSLACKORSURPLUSDUALPRICESMON)0.0000000.000000TUE)2.0000000.000000WED)8.0000000.000000THU)0.0000000.000000FRI)0.0000000.000000SAT)0.0000000.000000SUN)0.0000000.000000NO.ITERATIONS=18BRANCHES=1DETERM.=1.000E0,求解结果的报告窗口如下：,2020年4月29日星期三5时4分54秒,生产中通过切割、剪裁、冲压等手段，将原材料加工成所需大小,例5钢管和易拉罐下料,原料下料问题,按照工艺要求，确定下料方案，使所用材料最省，或利润最大,2020年4月29日星期三5时4分54秒,某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出。从钢管厂进货时得到的原料钢管都是19米长。1)现有一客户需要50根4米长、20根6米长和15根8米长的钢管。应如何下料最节省？2)零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要1）中的三种钢管外，还需要10根5米长的钢管。应如何下料最节省？,1、钢管下料,2020年4月29日星期三5时4分54秒,问题1）的求解,问题分析首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。例如，我们可以将19米长的钢管切割成3根4米长的钢管，余料为7米显然，可行的切割模式是很多的。,其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。在这种合理性假设下，切割模式一共有7种，如表所示。,2020年4月29日星期三5时4分54秒,为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？,合理切割模式,2.所用原料钢管总根数最少,钢管下料问题1,两种标准,1.原料钢管剩余总余量最小,2020年4月29日星期三5时4分54秒,xi按第i种模式切割的原料钢管根数(i=1,2,7),约束,满足需求,决策变量,目标1（总余量）,整数约束：xi为整数,2020年4月29日星期三5时4分54秒,模型求解,将整数线性规划模型（加上整数约束）输入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,2020年4月29日星期三5时4分54秒,求解可以得到最优解如下：,OBJECTIVEFUNCTIONVALUE1)27.00000VARIABLEVALUEREDUCEDCOSTX10.0000003.000000X212.0000001.000000X30.0000003.000000X40.0000003.000000X515.0000001.000000X60.0000001.000000X70.0000003.000000,按模式2切割12根,按模式5切割15根，余料27米,2020年4月29日星期三5时4分54秒,目标2（总根数）,钢管下料问题1,约束条件不变,xi为整数,2020年4月29日星期三5时4分54秒,将整数线性规划模型（加上整数约束）输入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,模型求解,2020年4月29日星期三5时4分54秒,求解，可以得到最优解如下：,OBJECTIVEFUNCTIONVALUE1)25.00000VARIABLEVALUEREDUCEDCOSTX10.0000001.000000X215.0000001.000000X30.0000001.000000X40.0000001.000000X55.0000001.000000X60.0000001.000000X75.0000001.000000,2020年4月29日星期三5时4分54秒,当余料没有用处时，通常以总根数最少为目标,最优解：x2=15,x5=5,x7=5,其余为0；最优值：25。,按模式2切割15根，按模式5切割5根，按模式7切割5根，共25根，余料35米,虽余料增加8米，但减少了2根,与目标1的结果“共切割27根，余料27米”相比,2020年4月29日星期三5时4分54秒,钢管下料问题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米长的钢管的数量,2020年4月29日星期三5时4分54秒,满足需求,模式合理：每根余料不超过3米,整数非线性规划模型,钢管下料问题2,目标函数（总根数）,约束条件,整数约束：xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数,2020年4月29日星期三5时4分54秒,增加约束，缩小可行域，便于求解,原料钢管总根数下界：,特殊生产计划：对每根原料钢管模式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米,2020年4月29日星期三5时4分54秒,将模型输入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,2020年4月29日星期三5时4分54秒,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根。,2020年4月29日星期三5时4分54秒,问题某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的。易拉罐为圆柱形，包括罐身、上盖和下底，罐身高10cm，上盖和下底的直径均为5cm。该公司使用两种不同规格的镀锡板原料：规格1的镀锡板为正方形，边长24cm；规格2的镀锡板为长方形，长、宽分别为32cm和28cm。由于生产设备和生产工艺的限制，对于规格1的镀锡板原料，只可以按照模式1、模式2或模式3进行冲压；对于规格2的镀锡板原料只能按照模式4进行冲压。使用模式1、模式2、模式3、模式4进行每次冲压所需要的时间分别为1.5s、2s、1s、3s。,2、易拉罐下料,2020年4月29日星期三5时4分54秒,该工厂每周工作40小时，每周可供使用的规格1、规格2的镀锡板原料分别为5万张和2万张。目前每只易拉罐的利润为0.10元，原料余料损失为0.001元/平方厘米（如果周末有罐身、上盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。问工厂应如何安排每周的生产？,2020年4月29日星期三5时4分54秒,板材规格2：长方形，3228cm，2万张。,问题分析,罐身高10cm，上盖、下底直径均5cm。,板材规格1：正方形，边长24cm，5万张。,2020年4月29日星期三5时4分54秒,模式1:正方形边长24cm,问题分析,计算各种模式下的余料损失,上、下底直径d=5cm，罐身高h=10cm。,模式1余料损失242-10d2/4-dh=222.6cm2,2020年4月29日星期三5时4分54秒,问题分析,目标:易拉罐利润扣除原料余料损失后的净利润最大,约束：每周工作时间不超过40小时；原料数量：规格1（模式13）5万张，规格2（模式4）2万张；罐身和底、盖的配套组装。,注意：不能装配的罐身、上下底也是余料,决策变量,xi按照第i种模式的生产张数(i=1,2,3,4)；y1一周生产的易拉罐个数；y2不配套的罐身个数；y3不配套的底、盖个数。,模型建立,2020年4月29日星期三5时4分54秒,目标,约束条件,时间约束,原料约束,模型建立,y1易拉罐个数；y2不配套的罐身；y3不配套的底、盖。,每只易拉罐利润0.10元，余料损失0.001元/cm2,罐身面积dh=157.1cm2底盖面积d2/4=19.6cm2,(40小时),2020年4月29日星期三5时4分54秒,约束条件,配套约束,y1易拉罐个数；y2不配套的罐身；y3不配套的底、盖。,虽然xi和y1，y2，y3应是整数，但是因生产量很大，可以把它们看成实数，从而用线性规划模型处理。,2020年4月29日星期三5时4分54秒,LINDO发出警告信息：“数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别”,模型求解,OBJECTIVEFUNCTIONVALUE1)4298.337VARIABLEVALUEREDUCEDCOSTY1160250.0000000.000000X10.0000000.000050X240125.0000000.000000X33750.0000000.000000X420000.0000000.000000Y20.0000000.223331Y30.0000000.036484,2020年4月29日星期三5时4分54秒,模型中数据不平衡的警告信息,2020年4月29日星期三5时4分54秒,输入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=0,将所有决策变量扩大10000倍（xi万张，yi万件）,2020年4月29日星期三5时4分54秒,模式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,求解得到：,2020年4月29日星期三5时4分54秒,下料问题的建模,确定下料模式,构造优化模型,规格不太多，可枚举下料模式，建立整数线性规划模型，否则要构造整数非线性规划模型，求解困难，可用缩小可行域的方法进行化简，但要保证最优解的存在。,一维问题（如钢管下料）,二维问题（如易拉罐下料）,具体问题具体分析（比较复杂）,2020年4月29日星期三5时4分54秒,LINGO模型例：选址问题,某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）,假设：料场和工地之间有直线道路,2020年4月29日星期三5时4分54秒,用例中数据计算，最优解为,总吨公里数为136.2,线性规划模型,决策变量：cij(料场j到工地i的运量）12维,2020年4月29日星期三5时4分54秒,选址问题：NLP,2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。,决策变量：cij，(xj,yj)16维,非线性规划模型,2020年4月29日星期三5时4分54秒,LINGO模型的构成：4个段,集合段（SETSENDSETS）,数据段（DATAENDDATA）,初始段（INITENDINIT）,目标与约束段,局部最优：89.8835(吨公里),LP：移到数据段,2020年4月29日星期三5时4分54秒,边界,2020年4月29日星期三5时4分54秒,四、LINGO的建模语言,以运输问题逐步分析,6个仓库向8个小贩供应同一种货物，如何运,总运输费用最小？,注：每个仓库可以向每个小贩供货，一共48个可能运货路线。,仓库货存量、小贩需求量、每条路线的单位运输费用三个表如下：,2020年4月29日星期三5时4分54秒,仓库货存量：capacity,2020年4月29日星期三5时4分54秒,小贩需求量：demand,2020年4月29日星期三5时4分54秒,每单位货物运输费用表：cost,2020年4月29日星期三5时4分54秒,demand_j表示第j个小贩的需求量capacity_i表示第i个仓库的库存量cost_i_j表示从第i个仓库到第j个小贩的单位运输费用,volume_i_j表示从第i个仓库到第j个小贩的运输量,2020年4月29日星期三5时4分54秒,数学模型可表示如下：,2020年4月29日星期三5时4分54秒,当然目标函数可以如下输入: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;,2020年4月29日星期三5时4分54秒,但是较大模型如果像上面那样输入又费时，又容易出错！这就需要LINGO的建模语言,2020年4月29日星期三5时4分54秒,LINGO的建模语言优点:,1)可以用类似于标准数学符号的方式表示你的模型；2)可以用一个紧凑的语句表示一系列约束。3)数据可独立于模型：LINGO可以从文本文件、电子数据表、数据库中读取数据。,2020年4月29日星期三5时4分54秒,LINGO模型的构成：5个段,目标函数与约束条件段集合段（sets:endsets）数据段（data:enddata）初始段（init:endinit）计算段（calc：endcalc）,Lingo建模语言的重点和难点是：对集合概念的理解和正确使用,2020年4月29日星期三5时4分54秒,为什么使用集合,集合是LINGO建模语言的基础，是LINGO程序设计最强有力的基本构件。借助于集合，能够用一个单一的、长的、简明的复合公式表示一系列相似的约束，从而可以快速方便地表达规模较大的模型。,2020年4月29日星期三5时4分54秒,什么是集合,集合是一群相联系的对象，比如仓库、小贩、运输路线，这些对象也称为集合的成员。每个集合成员可能有一个或多个与之有关联的特征，我们把这些特征称为属性。属性值可以预先给定，也可以是未知的，有待于LINGO求解。,2020年4月29日星期三5时4分54秒,从我们的数学模型看需要三个集合：,（1）仓库-6个成员-货存量（2）小贩-8个成员-需求量（3）运输路线-48个成员-单位运费和运货量,2020年4月29日星期三5时4分54秒,LINGO有两种类型的集合,原始集合(primitiveset)：由一些最基本的对象组成的。派生集(derivedset):用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。,2020年4月29日星期三5时4分54秒,*下面我们学习集合定义部分*,1.以sets:开始，以endsets结束；sets:endsets,2020年4月29日星期三5时4分54秒,2.原始集合定义法：,setname/member_list/:attribute_list;。setname是集合的名字；。member_list是成员列表,各成员之间可用空格或逗号分隔；。attribute_list是集合成员所具有的属性列表，多个属性之间用逗号分隔；。原始集合的member_list,attribute_list是可选项；,2020年4月29日星期三5时4分54秒,*仓库和小贩的集合可如下定义*,sets:warehouses/w1w2w3w4w5w6/:capacity;vendors/v1,v2,v3,v4,v5,v6,v7,v8/:demand;endsets,2020年4月29日星期三5时4分54秒,*仓库和小贩的集合也可如下定义*,sets:warehouses/w1.w6/:capacity;vendors/v1.v8/:demand;endsets,2020年4月29日星期三5时4分54秒,3.派生集合定义法：,setname(parent_set_list)/member_list/:attribute_list;parent_set_list是父集合名列表,2020年4月29日星期三5时4分54秒,*48条运输路线集合定义*,links(warehouses,vendors):cost,volume；,2020年4月29日星期三5时4分54秒,*三个集合定义如下*,sets:warehouses/wh1.wh6/:capacity;vendors/v1.v8/:demand;links(warehouses,vendors):cost，volume；endsets,2020年4月29日星期三5时4分54秒,运输问题的三个集合说明：,这段代码定义了4个属性值，在接下来的模型中就可以使用属性值capacity(1),capacity(2),capacity(6);demand(1),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。,2020年4月29日星期三5时4分54秒,4.集合成员过滤：,trucks/1.100/:capacity;heavy_duty(trucks)|capacity(endsets,如果想赋值x(1)=1,x(2)=2,x(3)=3,y(1)=4，y(2)=5,y(3)=6，则数据段可以为,2020年4月29日星期三5时4分54秒,data:x=1,2,3;y=456;enddata,data:x,y=142536;enddata,多个数据之间可用逗号或空格分隔,2020年4月29日星期三5时4分54秒,若成员属性值相同，数据段定义如下：,data:x=3;!(所有成员的x=3);y=6;!(所有成员的y=6);enddata,2020年4月29日星期三5时4分54秒,也可以在运行时输入属性值：,data:x=?;！(运行时输入所有成员的x值);y=6;enddata,2020年4月29日星期三5时4分54秒,*运输问题的数据部分*,data:capacity=60,55,51,43,41,52;demand=3537223241324338;,2020年4月29日星期三5时4分54秒,cost=626742594953858252197433767392712395726555228143;enddata,2020年4月29日星期三5时4分54秒,sets:sett:x,y;endsetsdata:sett,x,y=a14b25c36;enddata,sets:sett/a,b,c/:x,y;endsetsdata:x=123;y=456;enddata,集合成员可以在数据段定义：,2020年4月29日星期三5时4分54秒,运输实例：,sets:warehouses:capacity;endsetsdata:!可以写成warehouses=w1.w6;!也可以同时定义集合成员列表和属性值;warehouses,capacity=w160,w255,w351,w443,w541,w652;enddata,2020年4月29日星期三5时4分54秒,*初始化定义*,只在非线性规划中使用，指定初始值。init:.endinit,2020年4月29日星期三5时4分54秒,例：init:x=0.999;y=0.002;endinity<=log(x);x2+y2<=1;给了恰当的初始值，会减少运算时间。,2020年4月29日星期三5时4分54秒,*计算段定义*,calc:.endcalc,计算段的作用：在模型输入后，LINGO开始正式求解模型之前对原始数据进行一定的计算，得到我们模型中要使用的部分数据。,2020年4月29日星期三5时4分54秒,一个简单的计算段例子:,model:data:x,y,z=1,2,3;enddatacalc:avg=(x+y+z)/3;endcalcend,2020年4月29日星期三5时4分54秒,*目标函数和约束条件段*,LINGO提供了集合循环函数和集合操作函数使得目标函数和约束条件的书写如同数学公式那样简单。,四个集合循环函数,FOR、SUM、MAX、MIN,2020年4月29日星期三5时4分54秒,sum(setname(set_index_list)|condition:expression);,求和,2020年4月29日星期三5时4分54秒,*运输问题的目标函数*,min=sum(links(i,j):cost(i,j)*volume(i,j);,min=sum(links:cost*volume);,2020年4月29日星期三5时4分54秒,*运输问题实例中的求和*,！从6个仓库发到第j个小贩的货物量总和；sum(warehouses(i):volume(i,j);,2020年4月29日星期三5时4分54秒,从第i个仓库发出到8个小贩的货物量总和；,sum(vendors(j):volume(i,j),2020年4月29日星期三5时4分54秒,for(setname(set_index_list)|condition:expression_list);,生成约束for,对集合setname中的每个成员独立地生成约束，约束由约束表达式列表expression_list描述;多个表达式之间用分号相隔。,2020年4月29日星期三5时4分54秒,*每个小贩的需求约束*,！（要求6个仓库发给每个小贩的货物总量=小贩的需求量）；for(vendors(j):sum(warehouses(i):volume(i,j)=demand(j);,2020年4月29日星期三5时4分54秒,*每个仓库的供货约束*,for(warehouses(i):sum(vendors(j):volume(i,j)<capacity(i);,！（要求每个仓库发给8个小贩的货物总量<仓库的货存量）；,2020年4月29日星期三5时4分54秒,使用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):volume(I,J)<=capacity(I);,*运输问题的完整模型,2020年4月29日星期三5时4分54秒,!这里是数据;data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend然后点击工具条上的按钮即可。,2020年4月29日星期三5时4分54秒,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等,2020年4月29日星期三5时4分54秒,建模时需要注意的几个基本问题,3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y<5改为x<5y）4、合理设定变量上下界，尽可能给出变量初始值5、模型中使用的参数数量级要适当(如小于103),2020年4月29日星期三5时4分54秒,某储蓄所每天的营业时间为上午9点到下午5点.根据经验,每天不同时间所需要的服务员数量为:,练习1服务人员安排问题,2020年4月29日星期三5时4分54秒,储蓄所可以雇用全时和半时两类服务员.全时服务员每天报酬100元,从上午9点到下午5点工作,但中午12点到下午2点之间必须安排1小时的午餐时间储蓄所每天还可以雇用不超过3名的半时服务员,每个半时服务员必须连续工作4小时,报酬40元,问该储蓄所该如何雇用全时和半时服务员？如果不能雇用半时服务员,每天至少增加多少费用？如果雇用半时服务员的数量没有限制,每天可以减少多少费用?,2020年4月29日星期三5时4分54秒,分析,解决此问题的关键是确定雇用全时服务员及半时服务员的人数,但还要考虑全时服务员有吃午餐的时间,故把全时服务员分为两类:午餐时间为12时至下午1时的及下午1时至下午2时的;而半时服务员按上班时间进行划分.,2020年4月29日星期三5时4分54秒,模型建立,设为午餐时间为下午12时的全时服务员的人数,为午餐时间为下午1时的全时服务员的人数,而分别表示从9点,10点,11点,1点开始上班的半时服务员人数,则目标函数为,约束条件按各个小时需要的服务员人数确定,则有,2020年4月29日星期三5时4分54秒,2020年4月29日星期三5时4分54秒,此外,对半时服务员人数的限制,对决策变量的限制为,为整数.,由上述分析,得到相应的数学模型为,2020年4月29日星期三5时4分54秒,为整数.,2020年4月29日星期三5时4分54秒,模型求解,利用LINDO软件得到问题的解:,若不能雇佣半时服务员,则最优解为,因而多支出元.,若对半时服务员人数没有限制,则最优解为,节省开支元.,2020年4月29日星期三5时4分54秒,用4台机床加工3件产品。各产品的机床加工顺序，以及产品i在机床j上的加工工时aij如下表。由于某种原因，产品2的加工总时间不得超过d，现要求确定各件产品在机床上的加工方案，使在最短的时间内加工完全部产品。,a32a33机床2机床3,产品3,a21a22a24机床1机床2机床4,产品2,a11a13a14机床1机床3机床4,产品1,练习2机床加工顺序问题,2020年4月29日星期三5时4分54秒,解：设xij表示产品i在机床j上开始加工的时间(i=1,2,3;j=1,2,3,4)(不妨记开始为0时刻)下面将逐步列出问题的整数规划模型1、同一件产品在不同机床上的加工顺序约束对于同一件产品，在下一台机床上加工的开始时间不得早于在上一台机床上加工的约束时间，故应有：,产品3：,2020年4月29日星期三5时4分54秒,2、每一台机床对不同产品的加工顺序约束一台机床在工作中，如已开始的加工还没有结束，则不能开始另一件产品的加工。对于机床1，有两种加工顺序。或先加工产品1，后加工产品2；或反之。对于其它3台机床，情况也类似。为了容纳两种相互排斥的约束条件，对于每台机床，分别引入0-1变量,各yj的意义是明显的。如当y1=0时，表示机床1先加工产品1，后加工产品2，当y1=1时，表示机床1先加工产品2，后加工产品1。,2020年4月29日星期三5时4分54秒,那么，每台机床上的加工产品的顺序可用下列四组约束条件来保证,2020年4月29日星期三5时4分54秒,3、产品2的加工时间约束产品2的开始加工时间是x21，结束加工时间是x24+a24故应有：,4、目标函数的建立设全部产品加工完毕的结束时间为w，由于三件产品的加工结束时间分别为x14+a14，x24+a24，x33+a33，故全部产品的实际加工结束时间为：,2020年4月29日星期三5时4分54秒,转化为线性表达式：,整理即的数学规划模型。,