资源描述
LINGO软件基本使用办法软件基本使用办法第1页第1页内容提纲内容提纲1.LINGO入门入门2.在在LINGO中使用集合中使用集合3.运算符和函数运算符和函数4.LINGO主要菜单命令主要菜单命令5.LINGO命令窗口命令窗口 6.习题第2页第2页1.LINGO入门入门1.LINGO入门入门2.在在LINGO中使用集合中使用集合3.运算符和函数运算符和函数4.LINGO主要菜单命令主要菜单命令5.LINGO命令窗口命令窗口 第3页第3页LINGO软件主要特色软件主要特色两种命令模式两种命令模式Windows模式：模式：通过下拉式菜单命令驱动通过下拉式菜单命令驱动LINGO运运营（多数菜单命令有快捷键，惯用菜单命令有快捷按营（多数菜单命令有快捷键，惯用菜单命令有快捷按钮），图形界面，使用以便；钮），图形界面，使用以便；命令行命令行 模式：仅在命令窗口模式：仅在命令窗口(Command Window)下操下操作，通过输入行命令驱动作，通过输入行命令驱动LINGO运营运营。(这里主要简介这种模式这里主要简介这种模式)第4页第4页从从LINDO LINDO 到到 LINGO LINGO如今如今 LINGO 功效增强，性能稳定，解答结果可靠。功效增强，性能稳定，解答结果可靠。与与LINDO相比，相比，LINGO 软件主要含有两大长处软件主要含有两大长处:内置建模语言，允许以简练、直观方式描述较大规内置建模语言，允许以简练、直观方式描述较大规模优化问题，所需数据能够以一定格式保留在独立模优化问题，所需数据能够以一定格式保留在独立文献中。文献中。除含有除含有LINDO所有功效外，还可用于求解非线性所有功效外，还可用于求解非线性规划问题，包括非线性整数规划问题规划问题，包括非线性整数规划问题;第5页第5页LINGOLINGO界面界面LINGO软件主窗口（用户软件主窗口（用户界面），所有其它窗口都界面），所有其它窗口都在这个窗口之内。在这个窗口之内。模型窗口（模型窗口（Model Window），用于输入），用于输入LINGO优化模型（即优化模型（即LINGO程序）。程序）。状态行（最左边显状态行（最左边显示示“Ready”，表，表示示“准备就绪准备就绪”）当前时间当前时间 当前光标当前光标位置位置 第6页第6页LINGOLINGO文献类型文献类型.LG4：LINGO格式模型文献，保留了模型窗口中所能格式模型文献，保留了模型窗口中所能够看到所有文本和其它对象及其格式信息；够看到所有文本和其它对象及其格式信息；.LNG：文本格式模型文献，不保留模型中格式信息：文本格式模型文献，不保留模型中格式信息（如字体、颜色、嵌入对象等）；（如字体、颜色、嵌入对象等）；.LDT：LINGO数据文献；数据文献；.LTF：LINGO命令脚本文献；命令脚本文献；.LGR：LINGO汇报文献；汇报文献；.LTX：LINDO格式模型文献；格式模型文献；.MPS：示：示MPS（数学规划系统）格式模型文献。（数学规划系统）格式模型文献。除除“LG4”文献外，文献外，另外几种格式文献都另外几种格式文献都是普通文本文献，能是普通文本文献，能够用任何文本编辑器够用任何文本编辑器打开和编辑。打开和编辑。第7页第7页运营状态窗口运营状态窗口Variables（变量数量）：（变量数量）：变量总数（变量总数（Total）、）、非线性变量数（非线性变量数（Nonlinear）、）、整数变量数（整数变量数（Integer）。）。Constraints（约束数量）：（约束数量）：约束总数（约束总数（Total）、）、非线性约束个数非线性约束个数(Nonlinear)。Nonzeros（非零系数数量）：（非零系数数量）：总数（总数（Total）、）、非线性项系数个数非线性项系数个数(Nonlinear)。Generator Memory Used(K)(内存使用内存使用量量)Elapsed Runtime(hh:mm:ss)（求解花费时间）（求解花费时间）第8页第8页运营状态窗口运营状态窗口求解求解器器(求求解程解程序序)状状态框态框当前模型类型当前模型类型:LP，QP，ILP，IQP，PILP，PIQP，NLP，INLP，PINLP（以（以I开头表示开头表示IP，以，以PI开头表示开头表示PIP）当前解状态当前解状态:Global Optimum,Local Optimum,Feasible,Infeasible“(不可行不可行),Unbounded“(无界无界),Interrupted“(中断中断),Undetermined“(未拟定未拟定)解目的函数值解目的函数值 当前约束不满足总量当前约束不满足总量(不是不满不是不满足约束个数足约束个数):实数（即使该值实数（即使该值=0，当前解也也许不可行，由于这，当前解也也许不可行，由于这个量中没有考虑用上下界命令形个量中没有考虑用上下界命令形式给出约束）式给出约束）当前为止迭当前为止迭代次数代次数 第9页第9页运营状态窗口运营状态窗口扩展扩展求解求解器器(求求解程解程序序)状态状态框框使用特殊求解程序使用特殊求解程序:B-and-B(分枝定界算法分枝定界算法)Global(全局最优求解程序全局最优求解程序)Multistart(用多个初始点求解程序用多个初始点求解程序)当前为止找到可行解当前为止找到可行解最佳目的函数值最佳目的函数值 目的函数值界目的函数值界 特殊求解程序当前运营步数：特殊求解程序当前运营步数：分枝数分枝数(对对B-and-B程序程序)；子问题数子问题数(对对Global程序程序)；初始点数初始点数(对对Multistart程序程序)有效步数有效步数 第10页第10页注：但凡能够从一个约束直接解出变量取值时，这个注：但凡能够从一个约束直接解出变量取值时，这个变量就不认为是决议变量而是固定变量，不列入统计变量就不认为是决议变量而是固定变量，不列入统计中；只含有固定变量约束也不列入约束统计中。中；只含有固定变量约束也不列入约束统计中。运营状态窗口运营状态窗口第11页第11页一个简朴一个简朴LINGO程序程序例例 直接用LINGO来解下列二次规划问题：输入窗口下列：输入窗口下列：第12页第12页程序语句输入备注：程序语句输入备注：LINGO总是依据总是依据“MAX=”或或“MIN=”寻找目的函数，寻找目的函数，而除注释语句和而除注释语句和TITLE语句外其它语句都是约束条件，语句外其它语句都是约束条件，因此语句顺序并不主要因此语句顺序并不主要。限定变量取整数值语句为限定变量取整数值语句为“GIN(X1)”和和“GIN(X2)”，不能够写成，不能够写成“GIN(2)”，不然，不然LINGO将把这个模型当作没有整数变量。将把这个模型当作没有整数变量。LINGO中函数一律需要以中函数一律需要以“”开头，其中整型变量开头，其中整型变量函数（函数（BIN、GIN）和上下界线定函数（）和上下界线定函数（FREE、BND(L,X,U)）。并且）。并且0/1变量函数是变量函数是BIN函数。函数。第13页第13页输出结果：输出结果：运营菜单命令运营菜单命令“LINGO|Solve”最优整数解最优整数解X=(35，65)最大利润最大利润=11077.5 第14页第14页输出结果备注：输出结果备注：通过菜单“WINDOW|Status Window”看到状态窗口，可看到最佳目的值“Best Obj”与问题上界“Obj Bound”已经是同样，当前解最大利润与这两个值非常靠近，是计算误差引起。假如采用全局最优求解程序(后面简介)，能够验证它就是全局最优解。LINGO是将它作为PINLP(纯整数非线性规划)来求解，因此找到是局部最优解。第15页第15页一个简朴一个简朴LINGO程序程序LINGO基本使用办法几点注意事项基本使用办法几点注意事项 LINGO中不区别大小写字母；变量和行名能够超出8个字符，但不能超出32个字符，且必须以字母开头。用LINGO解优化模型时已假定所有变量非负(除非用限定变量取值范围函数free或BND另行阐明)。变量能够放在约束条件右端(同时数字也可放在约束条件左端)。但为了提升LINGO求解时效率，应尽量采用线性表示式定义目的和约束(假如也许话)。语句是构成LINGO模型基本单位,每个语句都以分号结尾，编写程序时应注意模型可读性。比如：一行只写一个语句，按照语句之间嵌套关系对语句安排适当缩进，增强层次感。以感慨号开始是阐明语句(阐明语句也需要以分号结束)）。第16页第16页2.在在LINGO中使用集合中使用集合 1.LINGO入门入门2.在在LINGO中使用集合中使用集合3.运算符和函数运算符和函数4.LINGO主要菜单命令主要菜单命令5.LINGO命令窗口命令窗口 6.习题第17页第17页集合基本使用办法和集合基本使用办法和LINGO模型基本要素模型基本要素 理解理解LINGO建模语言最主要是理解集合（建模语言最主要是理解集合（Set）及其属）及其属性（性（Attribute）概念。）概念。例例 SAILCO公司需要决定下四个季度帆船生产量。下四个季度帆船需求量分公司需要决定下四个季度帆船生产量。下四个季度帆船需求量分别是别是40条，条，60条，条，75条，条，25条，这些需求必须按时满足。每个季度正常生产能条，这些需求必须按时满足。每个季度正常生产能力是力是40条帆船，每条船生产费用为条帆船，每条船生产费用为400美元。假如加班生产，每条船生产费用美元。假如加班生产，每条船生产费用为为450美元。每个季度末，每条船库存费用为美元。每个季度末，每条船库存费用为20美元。假定生产提前期为美元。假定生产提前期为0，初，初始库存为始库存为10条船。如何安排生产可使总费用最小？条船。如何安排生产可使总费用最小？用用DEM,RP,OP,INV分别表示需求量、正常生产产量、分别表示需求量、正常生产产量、加班生产产量、库存量，则加班生产产量、库存量，则DEM,RP,OP,INV对每个季对每个季度都应当有一个相应值，也就说他们都应当是一个由度都应当有一个相应值，也就说他们都应当是一个由4个元素构成数组，其中个元素构成数组，其中DEM是已知，而是已知，而RP,OP,INV是是未知数。未知数。第18页第18页问题模型问题模型(能够看出是能够看出是LP模型模型)目的函数是所有费用和目的函数是所有费用和 约束条件主要有两个：约束条件主要有两个：1）能力限制：）能力限制：2）产品数量平衡方程：）产品数量平衡方程：加上变量非负约束加上变量非负约束第19页第19页注：注：LINDO中没有数组，只能对每个季度分别定义变量，如正常产量就要有RP1，RP2，RP3，RP4 4个变量等。写起来就比较麻烦，尤其是更多(如1000个季度)时候。记四个季度构成集合QUARTERS=1，2，3，4，它们就是上面数组下标集合，而数组DEM,RP,OP,INV对集合QUARTERS中每个元素1，2，3，4分别相应于一个值。LINGO正是充足利用了这种数组及其下标关系，引入了“集合”及其“属性”概念，把QUARTERS=1，2，3，4称为集合，把DEM,RP,OP,INV称为该集合属性(即定义在该集合上属性)。第20页第20页QUARTERS集合属性DEM RPOP INVQUARTERS集合2341 集合及其属性集合及其属性 第21页第21页集合元素及集合属性拟定所有变量集合元素及集合属性拟定所有变量集合QUARTERS元素1234定义在集合QUARTERS上属性DEMDEM(1)DEM(2)DEM(3)DEM(4)RPRP(1)RP(2)RP(3)RP(4)OPOP(1)OP(2)OP(3)OP(4)INVINV(1)INV(2)INV(3)INV(4)第22页第22页LINGO中定义集合及其属性中定义集合及其属性 LP模型在模型在LINGO中一个典型输入方式中一个典型输入方式 以以“MODEL：”开始开始 以以“END”结结束束集合定义部分从集合定义部分从(“SETS：”到到“ENDSETS”)：定：定义集合及其属性义集合及其属性集合定义部分从集合定义部分从(“DATA：”到到“ENDDATA”)给出优化目的给出优化目的和约束和约束 第23页第23页目的函数定义方式目的函数定义方式SUM(集合（下标）：关于集合属性表示式集合（下标）：关于集合属性表示式)对语句中冒号对语句中冒号“：”后面表示式，按照后面表示式，按照“：”前面前面集合指定下标（元素）进行求和。集合指定下标（元素）进行求和。本例中目的函数也能够等价地写成本例中目的函数也能够等价地写成SUM(QUARTERS(i):400*RP(i)+450*OP(i)+20*INV(i)，“SUM”相称于求和符号相称于求和符号“”，由于本例中目的函数对集合由于本例中目的函数对集合QUARTERS所有元素所有元素(下标下标)都要求和，因此能够将下标都要求和，因此能够将下标i省去。省去。第24页第24页约束定义方式约束定义方式循环函数循环函数FOR(集合集合(下标下标)：关于集合属性约束关系式：关于集合属性约束关系式)对冒号对冒号“：”前面集合每个元素（下标），冒号前面集合每个元素（下标），冒号“：”后面约束关系式都要成立后面约束关系式都要成立 本例中，每个季度正常生产能力是本例中，每个季度正常生产能力是40条帆船，这正是语条帆船，这正是语句句“FOR(QUARTERS(I):RP(I)40);”含义。含义。由于对所有元素由于对所有元素(下标下标I),约束形式是同样，因此也能够约束形式是同样，因此也能够像上面定义目的函数时同样，将下标像上面定义目的函数时同样，将下标i省去，省去，这个语句能够简化成这个语句能够简化成“FOR(QUARTERS:RP1；“#GT#”是逻辑运算符号，意思是是逻辑运算符号，意思是“不小于不小于（Greater Than字首字母缩写）字首字母缩写）”。约束定义方式约束定义方式第26页第26页问题求解：运营菜单命令问题求解：运营菜单命令“LINGO|Solve”全局最优解全局最优解RP=(40,40,40,25),OP=(0,10,35,0)最小成本最小成本=78450 第27页第27页注：注：由于输入中没有给出行名，因此行名是系统自动按照行号由于输入中没有给出行名，因此行名是系统自动按照行号1-9生成。生成。选择菜单命令选择菜单命令“LINGO|Generate|Disply model（Ctrl+G）”，能够得到展开形式模型，能够得到展开形式模型(如图如图)，能够看到完整模型，也能拟，能够看到完整模型，也能拟定行号定行号(行号放在方括号行号放在方括号“”中，且数字前面带有下划线中，且数字前面带有下划线“_”)。最好在输入模型时用户积极设定约束行名最好在输入模型时用户积极设定约束行名(即约束名即约束名)，使程，使程序清楚些。单一约束行名设置办法就是将行名放在方括号序清楚些。单一约束行名设置办法就是将行名放在方括号“”中，置于约束之前。中，置于约束之前。后面将结合详细例子简介在使用集合情况下如何设置行名。后面将结合详细例子简介在使用集合情况下如何设置行名。第28页第28页小结小结:LINGO模型最基本构成要素模型最基本构成要素 普通来说，普通来说，LINGO中建立优化模型能够由个四部分构中建立优化模型能够由个四部分构成，或称为四成，或称为四“段段”（SECTION）：）：（1 1）集合段（）集合段（SETSSETS）：）：以以“SETS:”开始，开始，“ENDSETS”结束，定义必要集合变量（结束，定义必要集合变量（SET）及其元）及其元素（素（MEMBER，含义类似于数组下标）和属性，含义类似于数组下标）和属性（ATTRIBUTE，含义类似于数组）。，含义类似于数组）。如上例中定义了集合如上例中定义了集合quarters(含义是季节含义是季节)，它包括四个元素即四个季节指标，它包括四个元素即四个季节指标(1,2,3,4)，每个季节都有需求，每个季节都有需求(DEM)、正常生产量、正常生产量(RP)、加班生产量、加班生产量(OP)、库、库存量存量(INV)等属性等属性(相称于数组，数组下标由相称于数组，数组下标由quarters元素决定元素决定)。一旦这样定义。一旦这样定义建立起来，假如建立起来，假如quarters数量不是数量不是4而是而是1000,只需扩展其元素为只需扩展其元素为1,2,.,1000,每个每个季节仍然都有季节仍然都有DEM,RP,OP,INV这样属性这样属性(这些量详细数值假如是常量，则可在这些量详细数值假如是常量，则可在数据段输入；假如是未知数，则可在初始段输入初值数据段输入；假如是未知数，则可在初始段输入初值)。当。当quarters数量不是数量不是4而是而是1000时，没有必要把时，没有必要把1,2，.,1000所有一个一个列出来，而是能够下列定所有一个一个列出来，而是能够下列定义义quarters集合：集合：“quarters/1.1000/:DEM,RP,OP,INV;”,“1.1000”意思意思就是从就是从1到到1000所有整数。所有整数。第29页第29页（2 2）目的与约束段）目的与约束段：目的函数、约束条件等，没有段：目的函数、约束条件等，没有段开始和结束标识，因此事实上就是除其它四个段开始和结束标识，因此事实上就是除其它四个段(都有明都有明确段标识确段标识)外外LINGO模型。模型。这里普通要用到这里普通要用到LINGO内部函数，尤其是与集合相关内部函数，尤其是与集合相关求和函数求和函数SUM和循环函数和循环函数FOR等。等。上例中定义目的函数与上例中定义目的函数与quarters元素数目是元素数目是 4或或 1000并并无详细关系。约束表示也类似。无详细关系。约束表示也类似。第30页第30页（3 3）数据段）数据段(DATA)(DATA)：以：以“DATA:”开始开始,“ENDDATA”结结束，对集合属性束，对集合属性(数组数组)输入必要常数数据。输入必要常数数据。格式为：格式为：“attribute(属性属性)=value_list(常数列表常数列表);”常数列表常数列表(value_list)中数据之间能够用逗号中数据之间能够用逗号“,”分开，分开，也能够用空格分开也能够用空格分开(回车等价于一个空格回车等价于一个空格),如上面对如上面对DEM赋值也能够写成赋值也能够写成“DEM=40 60 75 25；”。在LINGO模型中，假如想在运营时才对参数赋值，能够在数据段使用输入语句。但这仅能用于对单个变量赋值，输入语句格式为：“变量名=？；”。比如，上例中假如需要在求解模型时才给出初始库存量(记为A)，则能够在模型中数据段写上语句：”A=?；”在求解时LINDO系统给出提醒界面，等待用户输入变量A数值。当然，此时约束语句 INV(1)=10+RP(1)+OP(1)-DEM(1);也应当改写成 INV(1)=A+RP(1)+OP(1)-DEM(1);这样，模型就能够计算任意初始库存量(而不但仅只能计算初始库存量为10)情况了。第31页第31页（4 4）初始段）初始段(INIT)(INIT)：以：以“INIT:”开始，开始，“ENDINIT”结束，对集合属性结束，对集合属性(数组数组)定义初值定义初值(由于求解算法普通由于求解算法普通是迭代算法，因此用户假如能给出一个比较好迭代初值，是迭代算法，因此用户假如能给出一个比较好迭代初值，对提升算法计算效果是有益对提升算法计算效果是有益)。假如有一个靠近最优解初值，对假如有一个靠近最优解初值，对LINGO求解模型是有求解模型是有帮助。定义初值格式为：帮助。定义初值格式为：“attribute（属性）（属性）=value_list（常数列表）；（常数列表）；”这与数据段中使用办法是类似。这与数据段中使用办法是类似。上例中没有初始化部分，我们将在下一个例子中举例上例中没有初始化部分，我们将在下一个例子中举例阐明。阐明。第32页第32页基本集合与派生集合基本集合与派生集合 例例3.4 建筑工地位置建筑工地位置(用平面坐标用平面坐标a,b表示，距离单位：表示，距离单位：公里公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个暂时料场位下表给出。有两个暂时料场位于于P(5,1),Q(2,7),日储量各有日储量各有20吨。从吨。从A,B两料场分别两料场分别向各工地运送多少吨水泥，使总吨公里数最小。两个新向各工地运送多少吨水泥，使总吨公里数最小。两个新料场应建在何处，节约吨公里数有多大？料场应建在何处，节约吨公里数有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611第33页第33页建立模型建立模型记工地位置为记工地位置为 ，水泥日用量为，水泥日用量为 ；料场位；料场位置为置为 ，日储量为，日储量为 ；从料场；从料场 向工地向工地 运送运送量为量为 。使用既有暂时料场时，决议变量只有使用既有暂时料场时，决议变量只有 （非负），因此这是（非负），因此这是LP模型；当为新模型；当为新建料场选址时决议变量为建料场选址时决议变量为 和和 ，由于目的函数，由于目的函数 对对 是非线性，因是非线性，因此在新建料场时是此在新建料场时是NLP模型。先解模型。先解NLP模型，而把既有暂时料场位置作为初模型，而把既有暂时料场位置作为初始解告诉始解告诉LINGO。第34页第34页本例中集合概念本例中集合概念利用集合概念，能够定义需求点利用集合概念，能够定义需求点DEMAND和供应点和供应点SUPPLY两个集合，分别有两个集合，分别有6个和个和2个元素个元素(下标下标)。但决。但决议变量议变量(运送量运送量)与集合与集合DEMAND和集合和集合SUPPLY都都相关系。该如何定义这样属性？相关系。该如何定义这样属性？集合属性相称于以集合元素为下标数组。这里集合属性相称于以集合元素为下标数组。这里 相称于相称于二维数组。它两个下标分别来自集合二维数组。它两个下标分别来自集合DEMAND和和SUPPLY，因此能够定义一个由二元对构成新集合，然，因此能够定义一个由二元对构成新集合，然后将后将 定义成这个新集合属性。定义成这个新集合属性。第35页第35页输入程序输入程序 定义了三个集合，其中定义了三个集合，其中LINK在前在前两个集合两个集合DEMAND 和和SUPPLY基基础上定义础上定义表示集合表示集合LINK中元素就是集合中元素就是集合DEMAND 和和SUPPLY元素组合成有序二元组，元素组合成有序二元组，从数学上看从数学上看LINK是是DEMAND 和和SUPPLY笛卡笛卡儿积，也就是说儿积，也就是说LINK=（S，T）|SDEMAND，TSUPPLY因此，其属性因此，其属性C也就是一个也就是一个6*2矩阵（或者说是矩阵（或者说是含有含有12个元素二维数组）。个元素二维数组）。LINGO建模语言也称为矩阵生成器（建模语言也称为矩阵生成器（MATRIX GENERATOR）。类似）。类似DEMAND 和和SUPPLY直接把元素列举出直接把元素列举出来集合，称为来集合，称为基本集合基本集合(primary set),而把而把LINK这种基于其它集这种基于其它集合而派生出来二维或多维集合称为合而派生出来二维或多维集合称为派生集合派生集合(derived set)。由于。由于是是DEMAND 和和SUPPLY生成了派生集合生成了派生集合LINK，因此，因此DEMAND 和和SUPPLY 称为称为LINK父集合父集合。第36页第36页输入程序输入程序 初始段 INGO对数据是按列赋值 语句实际赋值顺序是X=(5,2),Y=(1,7),而不是X=(5,1),Y=（2,7)等价写法：“X=5,2；Y=1,7；”同理，数据段中对常数数组A，B赋值语句也能够写成A,B=1.25 1.25 8.75 0.75 0.5 4.75 5.75 5 3 6.5 7.25 7.75；第37页第37页输入程序输入程序 定义目的和约束，与前例办法是类似(这里包括了派生集合)，请尤其注意进一步体会集合函数SUM和FOR使用办法。由于新建料场位置理论上讲能够是任意，因此在约束最后(模型“END”语句上面一行)用free函数取消了变量X、Y非负限制在程序开头用TITLE语句对这个模型取了一个标题“LOCATION PROBLEM；并且对目的行（OBJ）和两类约束（DEMAND_CON、SUPPLY_CON）分别进行了命名(请尤其注意这里约束命名特点)。第38页第38页解答解答:运营菜单命令运营菜单命令“LINGO|Solve”局部最优解局部最优解X(1)=7.249997，X(2)=5.695940，Y(1)=7.749998，Y(2)=4.928524，C（略），（略），最小运量最小运量=89.8835(吨公里吨公里)。问题问题:最小运量最小运量89.8835是不是全局最优是不是全局最优 是用是用“LINGO|Options”菜单命令打开选项对话框，在菜单命令打开选项对话框，在“Global Solver”选项卡上选择选项卡上选择“Use Global Solver”,激激活全局最优求解程序。活全局最优求解程序。第39页第39页问题问题:最小运量最小运量89.8835是不是全局最优是不是全局最优 为减少计算工作量，对为减少计算工作量，对X，Y取值再做一些限制。即使理论上新取值再做一些限制。即使理论上新建料场位置能够是任意，但显然最佳料场位置不应当离工地太远，建料场位置能够是任意，但显然最佳料场位置不应当离工地太远，至少不应当超出现在至少不应当超出现在6个工地所决定坐标最大、最小值决定矩形个工地所决定坐标最大、最小值决定矩形之外，即之外，即:0.5=x=8.75,0.75=y=7.75.能够用能够用bnd函数加上函数加上这个条件取代模型这个条件取代模型END上面行，运营上面行，运营NLP模型，全局最优模型，全局最优求解程序花费时间仍求解程序花费时间仍然很长，运营然很长，运营27分分35秒时人为终止求解秒时人为终止求解(按下按下“Interrupt Solver”按钮按钮)得到左得到左边模型窗口和全局求边模型窗口和全局求解器状态窗口解器状态窗口此时目的函数值下界（此时目的函数值下界（Obj Bound=85.2638）与当前得到最好可）与当前得到最好可行解目的函数值（行解目的函数值（Best Obj=85.2661）相差已经非常小，能）相差已经非常小，能够认为已经得到了全局最优解。够认为已经得到了全局最优解。第40页第40页计算结果计算结果 工地与料场示意图工地与料场示意图:“*”表示料场，表示料场，“+”表示工地表示工地 能够认为是模型最后结果能够认为是模型最后结果 附注：假如要把料厂P(5,1),Q(2,7)位置当作是已知并且固定，这时是LP模型。只需要把初始段“X Y=5，1，2，7；”语句移到数据段就能够了。此时，运营结果告诉我们得到全局最优解（变量C取值这里略去），最小运量136.2275(吨公里)。第41页第41页稠密集合与稀疏集合稠密集合与稀疏集合 包括了两个基本集合构成所有二元有序正确派生集合称包括了两个基本集合构成所有二元有序正确派生集合称为为稠密集合稠密集合(简称稠集简称稠集)。有时候，在实际问题中，一些。有时候，在实际问题中，一些属性属性(数组数组)只在笛卡儿积一个真子集合上定义，这种派只在笛卡儿积一个真子集合上定义，这种派生集合称为生集合称为稀疏集合稀疏集合(简称疏集简称疏集)。例例(最短路问题最短路问题)在纵横交错公路网中，货车司机希望找到一条从在纵横交错公路网中，货车司机希望找到一条从一个都市到另一个都市最短路一个都市到另一个都市最短路.下图表示是公路网下图表示是公路网,节点表示货车节点表示货车能够停靠都市能够停靠都市,弧上权表示两个都市之间距离弧上权表示两个都市之间距离(百公里百公里).那么那么,货车货车从都市从都市S出发到达都市出发到达都市T,如何选择行驶路线如何选择行驶路线,使所通过路程最短使所通过路程最短?STA1 A2 A3 B1 B2 C1 C2 633665874678956第42页第42页STA1 A2 A3 B1 B2 C1 C2 633665874678956分析分析 假设从假设从S到到T最优行驶路线最优行驶路线 P 通过都市通过都市C1,则则P中从中从S到到C1子路也一子路也一定是从定是从S到到C1最优行驶路线最优行驶路线;假设假设 P 通过都市通过都市C2,则则P中从中从S到到C2子路也一定是从子路也一定是从S到到C2最优行最优行驶路线驶路线.因此因此,为得到从为得到从S到到T最优行驶路线最优行驶路线,只需要先求出从只需要先求出从S到到Ck(k=1,2)最优行驶路线最优行驶路线,就能够以便地得到从就能够以便地得到从S到到T最优行驶路线最优行驶路线.同样同样,为了求出从为了求出从S到到Ck(k=1,2)最优行驶路线最优行驶路线,只需要先求出从只需要先求出从S到到Bj(j=1,2)最优行驶路线最优行驶路线;为了求出从为了求出从S到到Bj(j=1,2)最优行驶路线最优行驶路线,只需要先求出从只需要先求出从S到到Ai(i=1,2,3)最优行驶路线最优行驶路线.而而S到到Ai(i=1,2,3)最优行驶路线是很容最优行驶路线是很容易得到易得到(事实上事实上,此例中此例中S到到Ai(i=1,2,3)只有唯一道路只有唯一道路)第43页第43页分析分析 STA1 A2 A3 B1 B2 C1 C2 633665874678956此例中可把从S到T行驶过程分成4个阶段,即 SAi(i=1,2或3),Ai Bj(j=1或2),Bj Ck(k=1或2),Ck T.记d(Y,X)为都市Y与都市X之间直接距离(若这两个都市之间没有道路直接相连，则能够认为直接距离为)，用L(X)表示都市S到都市X最优行驶路线路长:第44页第44页本例计算本例计算STA1 A2 A3 B1 B2 C1 C2 633665874678956因此,从S到T最优行驶路线路长为20.进一步分析以上求解过程,能够得到从S到T最优行驶路线为S A3 B2 C1 T.这种计算办法在数学上称为动态规划(Dynamic Programming)第45页第45页本例本例LINGO求解求解“CITIES”(都市都市):一个基本集合一个基本集合(元素通过枚举给出元素通过枚举给出)L:CITIES相应属性变量相应属性变量(我们要求最短路长我们要求最短路长)“ROADS”(道路):由CITIES导出一个派生集合(请尤其注意其使用办法),由于只有一部分都市之间有道路相连，因此不应当把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。D:稀疏集合ROADS相应属性变量(给定距离)第46页第46页本例本例LINGO求解求解从模型中还能够看出：这个从模型中还能够看出：这个LINGO程序能够没有目的程序能够没有目的函数，这在函数，这在LINGO中，能够用来找可行解中，能够用来找可行解(解方程组和解方程组和不等式组不等式组)。在数据段对在数据段对L进行赋值，只有进行赋值，只有L(S)=0已已知，后面值为空知，后面值为空(但位置必须留出来，但位置必须留出来，即逗号即逗号“，”一个也不能少，不然会犯一个也不能少，不然会犯错错)。假如这个语句直接写成。假如这个语句直接写成“L=0；”，语法上看也是正确，但其含义是，语法上看也是正确，但其含义是L所所有元素取值所有为有元素取值所有为0，因此也会与题意，因此也会与题意不符。不符。第47页第47页本例本例LINGO求解求解即使集合即使集合CITIES中元素不是数字，但当它中元素不是数字，但当它以以CITIES(I)形式出现在循环中时，引用下形式出现在循环中时，引用下标标I却事实上仍是正整数，也就是说却事实上仍是正整数，也就是说I指正是指正是元素在集合中位置元素在集合中位置(顺序顺序)，普通称为元素索，普通称为元素索引引(INDEX)。在在for循环中过滤条件里用了一个函数循环中过滤条件里用了一个函数“index”,其作用是返回一个元素在集合其作用是返回一个元素在集合中索引值，这里中索引值，这里index(S)=1(即元素即元素S在集在集合中索引值为合中索引值为1)，因此逻辑关系式，因此逻辑关系式“I#GT#index(S)”能够能够直接等价地能够能够直接等价地写成写成“I#GT#1”。这里。这里index(S)事实上还事实上还是是index(CITIES,S)简写，即返回简写，即返回S在集合在集合CITIES中索引值。中索引值。第48页第48页本例本例LINGO求解结果求解结果从S到T最优行驶路线路长为20(进一步分析，能够得到最优行驶路线为S A3 B2 C1 T)。本例中定义稀疏集合本例中定义稀疏集合ROADS办法是将其元素通过枚举给办法是将其元素通过枚举给出，有时假如元素比较多，用起来不以便。另一个定义出，有时假如元素比较多，用起来不以便。另一个定义稀疏集合办法是稀疏集合办法是“元素过滤元素过滤”法，能够从笛卡儿积中系法，能够从笛卡儿积中系统地过滤下来一些真正元素。统地过滤下来一些真正元素。第49页第49页例例 某班某班8名同窗准备分成名同窗准备分成4个调查队个调查队(每队两人每队两人)前往前往4个个地域进行社会调查。这地域进行社会调查。这8名同窗两两之间组队效率下列名同窗两两之间组队效率下列表所表示表所表示(由于对称性，只列出了严格上三角部分由于对称性，只列出了严格上三角部分)，问，问如何组队能够使总效率最高？如何组队能够使总效率最高？学生S1S2S3S4S5S6S7S8S1-9342156S2-173521S3-44292S4-1552S5-876S6-23S7-4第50页第50页分析分析 这是一个匹配（MATCHING）问题。把上表效率矩阵记为BENEFIT(由于对称性，这个矩阵只有严格上三角部分共28个数取非零值)。用MATCH（Si，Sj）=1表示同窗Si，Sj构成一队，而MATCH（Si，Sj）=0表示Si，Sj不组队。由于对称性，只需考虑ij共28个0-1变量(而不是所有32个变量)。显然,目的函数正好是BENEFIT(Si,Sj)*MATCH(Si,Sj)对I,j之和。约束条件是每个同窗只能(并且必须在)某一组，即对于任意i有:只要属性MATCH某个下标为i就加起来，此和应当等于1。由上面分析，因此，完整数学模型下列(显然，这是一个0-1线性规划)：第51页第51页问题问题LINGO求解求解“S1.S8”等价于写成“S1 S2 S3 S4 S5 S6 S7 S8”,它没有相关属性列表，只用于表示是一个下标集合 在派生集合PAIRS定义中增长了过滤条件“&2#GT#&1”,意思是第2个父集合元素索引值(用“&2”表示)不小于第1个父集合元素索引值(用“&1”表示)。PAIRS中元素相应于上表中严格上三角部分二维下标(共28个元素)。BENEFIT和MATCH是PAIRS属性。注意数据段对BENEFIT赋值方式，“LINGO按照列顺序对属性变量元素进行赋值。在约束部分，过滤条件“J#EQ#I#OR#K#EQ#I”是由逻辑运算符“#OR#（或者）”连接一个复合逻辑关系式，连接由“#EQ#（等于）”表示两个逻辑关系。由于“#OR#”运算级别低于“#EQ#”，因此这个逻辑式中没有必要使用括号指定运算顺序。第52页第52页LINGO求解结果求解结果“LINGO|SOLVE”运营这个程序，能够得到全局最优值为30 MATCH变量中多数为0，能够更清楚地浏览最优解解。选择菜单命令“LINGO|SOLUTION”，能够看到图示对话框。选择属性MATCH(变量)选择Text(文本格式)选择Nonzeros Only(只显示非零值)点击“OK”按钮，得到关于最优解非零分量汇报学生最佳组队方式是学生最佳组队方式是(1,8),(2,4),(3,7),(5,6).第53页第53页集合使用小结集合使用小结 集合不同类型及其关系 集合集合派生集合
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
