Lingo的基本使用方法.ppt

《Lingo的基本使用方法.ppt》由会员分享，可在线阅读，更多相关《Lingo的基本使用方法.ppt（167页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习提纲学习提纲 约束条件决策变量njiDx)(l,.,j,)x(g)(m,.,i ,)x(h. t . s)()x(fmax)ormin(3102101目标函数优化类型优化类型 线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中有非线性函数 二次规划(QP) 目标为二次函数、约束为线性 离散优化离散优化 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划建模时需要注意的几个基本问题建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整

2、数约束和整数变量2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y）4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103) LP QP NLP IP 全局优化(选) ILP IQP INLP LINGOLINGO软件的求解过程软件的求解过程 LINGO预处理程序线性优化求解程序非线性优化求解程序分枝定界管理程序1. 确定常数2. 识别类型1. 单纯形算法2. 内点算法(选)1、顺序线性规划法(SLP)

3、2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选) 内容提要内容提要LINGO入门入门2.在在LINGO中使用集合中使用集合3. 运算符和函数运算符和函数4. LINGO的主要菜单命令的主要菜单命令5. LINGO命令窗口命令窗口 6.习题1. LINGO入门入门LINGO入门入门2.在在LINGO中使用集合中使用集合3. 运算符和函数运算符和函数4. LINGO的主要菜单命令的主要菜单命令5. LINGO命令窗口命令窗口 6.习题LINGOLINGO的界面的界面LINGO软件的主窗口（用户软件的主窗口（用户界面），所有其他窗口都界面），所有其他窗口都在这个窗口

4、之内。在这个窗口之内。 模型窗口（模型窗口（Model Window），用于输入），用于输入LINGO优化模型（即优化模型（即LINGO程序）。程序）。 状态行（最左边显示状态行（最左边显示“Ready”，表示，表示 “准备就绪准备就绪”）当前时间当前时间 当前光标的当前光标的位置位置 max 2xmax 2x1 1+3x+3x2 2 St. 4xSt. 4x1 1+3x+3x2 2=10=10 3x 3x1 1+5x+5x2 2=12 =12 x x1 100 x x2 200目标函数约束条件决策变量设有数学模型如下： 1) 1)选择菜单选择菜单 LINGO|SolveLINGO|Solve

5、 或者按工具栏的或者按工具栏的 Solver Status Solver Status 窗口窗口4)4)计算完成后出现计算完成后出现Solution ReportSolution Report窗口窗口显示模型解的详细信息；显示模型解的详细信息；Solution Report Solution Report 窗口窗口Global optimal solution found at iteration: 2Global optimal solution found at iteration: 2Objective valueObjective value: : 7.4545457.454545Va

6、riable ValueVariable Value Reduced Cost Reduced Cost x1 1.272727x1 1.272727 0.000000 0.000000 x2 1.636364x2 1.636364 0.000000 0.000000Row Slack or Surplus Dual PriceRow Slack or Surplus Dual Price 1 7.454545 1.000000 1 7.454545 1.000000 2 0.000000 0.9090909E-01 2 0.000000 0.9090909E-01 3 0.000000 0.

7、5454545 3 0.000000 0.5454545在在maxmax模型模型中中： 相应变量的相应变量的 reduced costreduced cost值值表示表示当该变量每增加一个单位时目当该变量每增加一个单位时目标函数减少的量标函数减少的量。 本例中此值均本例中此值均为为0 0 给出约束条件的松驰变量或剩给出约束条件的松驰变量或剩余变量的值；余变量的值； 小 于 等 于 约 束 为 松 驰 变 量小 于 等 于 约 束 为 松 驰 变 量(SLACK)(SLACK)； + + 大 于 等 于 约 束 为 剩 余 变 量大 于 等 于 约 束 为 剩 余 变 量(SURPLUS); -

8、(SURPLUS); -一个简单的一个简单的LINGO程序程序例例1 直接用LINGO来解如下二次规划问题： 40,322100. .123 . 02779821212122212121为整数xxxxxxtsxxxxxxMax输入窗口如下：输入窗口如下：程序语句输入的备注：程序语句输入的备注：LINGO总是根据总是根据“MAX=”或或“MIN=”寻找目标函数，而除注寻找目标函数，而除注释语句和释语句和TITLE语句外的其他语句都是约束条件，因此语句的语句外的其他语句都是约束条件，因此语句的顺序并不重要顺序并不重要 。限定变量取整数值的语句为限定变量取整数值的语句为“GIN(X1)”和和“GIN

9、(X2)”，不，不可以写成可以写成“GIN(2)”，否则，否则LINGO将把这个模型看成没有整将把这个模型看成没有整数变量。数变量。LINGO中函数一律需要以中函数一律需要以“”开头，其中整型变量函数（开头，其中整型变量函数（BIN、GIN）和上下界限定函数（）和上下界限定函数（FREE、SUB、SLB）。而且）。而且0/1变量函数是变量函数是BIN函数。函数。输出结果：输出结果：运行菜单命令运行菜单命令“LINGO|Solve” 最优整数解最优整数解X=(35，65)最大利润最大利润=11077.5 输出结果备注：输出结果备注：通过菜单 “WINDOW| Status Window”看到状态

10、窗口，可看到最佳目标值“Best Obj”与问题的上界“Obj Bound”已经是一样的，当前解的最大利润与这两个值非常接近，是计算误差引起的。如果采用全局最优求解程序(后面介绍)，可以验证它就是全局最优解。LINGO是将它作为PINLP(纯整数非线性规划)来求解，因此找到的是局部最优解。运行状态窗口运行状态窗口Variables（变量数量）：（变量数量）： 变量总数（变量总数（Total）、）、 非线性变量数（非线性变量数（Nonlinear）、）、 整数变量数（整数变量数（Integer）。）。Constraints（约束数量）：（约束数量）： 约束总数（约束总数（Total）、）、 非线

11、性约束个数非线性约束个数(Nonlinear)。Nonzeros（非零系数数量）：（非零系数数量）： 总数（总数（Total）、）、 非线性项系数个数非线性项系数个数(Nonlinear)。Generator Memory Used (K) (内存使用内存使用量量)Elapsed Runtime (hh:mm:ss)（求（求解花费的时间）解花费的时间） 运行状态窗口运行状态窗口求解求解器器(求求解程解程序序)状状态框态框当前模型的类型当前模型的类型 :LP，QP，ILP，IQP，PILP， PIQP，NLP，INLP，PINLP （以（以I开头表示开头表示IP，以，以PI开头表示开头表示PIP

12、） 当前解的状态当前解的状态 : Global Optimum, Local Optimum, Feasible, Infeasible“(不可行不可行), Unbounded“(无界无界), Interrupted“(中断中断), Undetermined“(未确定未确定) 解的目标函数值解的目标函数值 当前约束不满足的总量当前约束不满足的总量(不是不不是不满足的约束的个数满足的约束的个数):实数（即使实数（即使该值该值=0，当前解也可能不可行，当前解也可能不可行，因为这个量中没有考虑用上下界因为这个量中没有考虑用上下界命令形式给出的约束）命令形式给出的约束） 目前为止的目前为止的迭代次数迭

13、代次数 运行状态窗口运行状态窗口扩展扩展的求的求解器解器(求解求解程序程序)状态状态框框使用的特殊求解程序使用的特殊求解程序 :B-and-B (分枝定界算法分枝定界算法)Global (全局最优求解程序全局最优求解程序)Multistart(用多个初始点求解的程序用多个初始点求解的程序) 目前为止找到的可行目前为止找到的可行解的最佳目标函数值解的最佳目标函数值 目标函数值的界目标函数值的界 特殊求解程序当前运行步数：特殊求解程序当前运行步数：分枝数分枝数(对对B-and-B程序程序)；子问题数子问题数(对对Global程序程序)；初始点数初始点数(对对Multistart程序程序)有效步数有

14、效步数 注：凡是可以从一个约束直接解出变量取值时，这个变量就不注：凡是可以从一个约束直接解出变量取值时，这个变量就不认为是决策变量而是固定变量，不列入统计中；只含有固定变认为是决策变量而是固定变量，不列入统计中；只含有固定变量的约束也不列入约束统计中。量的约束也不列入约束统计中。运行状态窗口运行状态窗口一个简单的一个简单的LINGO程序程序LINGO的基本用法的几点注意事项的基本用法的几点注意事项 LINGO中不区分大小写字母；变量和行名可以超过8个字符，但不能超过32个字符，且必须以字母开头。用LINGO解优化模型时已假定所有变量非负(除非用限定变量取值范围的函数free或sub或slb另行

15、说明)。变量可以放在约束条件的右端(同时数字也可放在约束条件的左端)。但为了提高LINGO求解时的效率，应尽可能采用线性表达式定义目标和约束(如果可能的话)。语句是组成LINGO模型的基本单位,每个语句都以分号结尾，编写程序时应注意模型的可读性。例如：一行只写一个语句，按照语句之间的嵌套关系对语句安排适当的缩进，增强层次感。以感叹号开始的是说明语句(说明语句也需要以分号结束)。LINGOLINGO的文件类型的文件类型.LG4：LINGO格式的模型文件，保存了模型窗口中所能够看到格式的模型文件，保存了模型窗口中所能够看到的所有文本和其他对象及其格式信息；的所有文本和其他对象及其格式信息；.LNG

16、：文本格式的模型文件，不保存模型中的格式信息（如字：文本格式的模型文件，不保存模型中的格式信息（如字体、颜色、嵌入对象等）；体、颜色、嵌入对象等）；.LDT：LINGO数据文件；数据文件；.LTF：LINGO命令脚本文件；命令脚本文件；.LGR：LINGO报告文件；报告文件；.LTX： LINDO格式的模型文件；格式的模型文件；.MPS：表示：表示MPS（数学规划系统）格式的模型文件。（数学规划系统）格式的模型文件。除除“LG4”文件外，文件外，另外几种格式的文件另外几种格式的文件都是普通的文本文件都是普通的文本文件，可以用任何文本编，可以用任何文本编辑器打开和编辑。辑器打开和编辑。2.在在L

17、INGO中使用集合中使用集合 LINGO入门入门2.在在LINGO中使用集合中使用集合3. 运算符和函数运算符和函数4. LINGO的主要菜单命令的主要菜单命令5. LINGO命令窗口命令窗口 6.习题集合的基本用法和集合的基本用法和LINGO模型的基本要素模型的基本要素 理解理解LINGO建模语言最重要的是理解集合（建模语言最重要的是理解集合（Set）及其属性（）及其属性（Attribute）的概念。）的概念。 例例2 SAILCO公司需要决定下四个季度的帆船生产量。下四个季公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是度的帆船需求量分别是40条，条，60条，条，75条，条

18、，25条，这些需求必须条，这些需求必须按时满足。每个季度正常的生产能力是按时满足。每个季度正常的生产能力是40条帆船，每条船的生产条帆船，每条船的生产费用为费用为400美元。如果加班生产，每条船的生产费用为美元。如果加班生产，每条船的生产费用为450美元。美元。每个季度末，每条船的库存费用为每个季度末，每条船的库存费用为20美元。假定生产提前期为美元。假定生产提前期为0，初始库存为，初始库存为10条船。如何安排生产可使总费用最小？条船。如何安排生产可使总费用最小？用用DEM,RP,OP,INV分别表示需求量、正常生产的产量、加班生分别表示需求量、正常生产的产量、加班生产的产量、库存量，则产的产

19、量、库存量，则DEM,RP,OP,INV对每个季度都应该有一对每个季度都应该有一个对应的值，也就说他们都应该是一个由个对应的值，也就说他们都应该是一个由4个元素组成的数组，个元素组成的数组，其中其中DEM是已知的，而是已知的，而RP,OP,INV是未知数。是未知数。 问题的模型问题的模型( (可以看出是可以看出是LP模型模型 )目标函数是所有费用的和目标函数是所有费用的和4, 3 , 2, 1)(20)(450)(400MINIIINVIOPIRP 约束条件主要有两个：约束条件主要有两个：1）能力限制：）能力限制：4 , 3 , 2 , 1,40)(RPII2）产品数量的平衡方程：）产品数量的

20、平衡方程：4 , 3 , 2 , 1),()()() 1()(IIDEMIOPIRPIINVIINV10)0(INV加上变量的非负约束加上变量的非负约束注：注：LINGO中没有数组，只能对每个季度分别定义变量，如正常产量就要有RP1，RP2，RP3，RP4 4个变量等。写起来就比较麻烦，尤其是更多(如1000个季度)的时候。 记四个季度组成的集合QUARTERS=1，2，3，4，它们就是上面数组的下标集合，而数组DEM,RP,OP, INV对集合QUARTERS中的每个元素1，2，3，4分别对应于一个值。LINGO正是充分利用了这种数组及其下标的关系，引入了“集合”及其“属性”的概念，把QUA

21、RTERS=1，2，3，4称为集合，把DEM,RP,OP, INV称为该集合的属性(即定义在该集合上的属性)。QUARTERS集合的属性DEM RPOP INVQUARTERS集合2341 集合及其属性集合及其属性 集合元素及集合的属性确定的所有变量集合元素及集合的属性确定的所有变量集合QUARTERS的元素1234定义在集合QUARTERS上的属性DEM DEM(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)LINGO中定义集合及其属性中定义集合及其属

22、性 LP模型在模型在LINGO中的一个典型输入方式中的一个典型输入方式 以以“MODEL：”开始开始 以以“END”结束结束集合定义部分从集合定义部分从(“SETS：”到到“ENDSETS” )：定义集合及其属性定义集合及其属性数据输入部分从数据输入部分从(“DATA：”到到“ENDDATA” )给出优化目标给出优化目标和约束和约束 目标函数的定义方式目标函数的定义方式SUM(集合（下标）：关于集合的属性的表达式集合（下标）：关于集合的属性的表达式)对语句中冒号对语句中冒号“：”后面的表达式，按照后面的表达式，按照“：”前面的集合前面的集合指定的下标（元素）进行求和。指定的下标（元素）进行求和

23、。 本例中目标函数也可以等价地写成本例中目标函数也可以等价地写成SUM(QUARTERS(i): 400*RP(i) +450*OP(i) +20*INV(i) )，“SUM”相当于求和符号相当于求和符号“”，“QUARTERS(i)”相当于相当于“iQUARTERS”的含义。的含义。由于本例中目标函数对集合由于本例中目标函数对集合QUARTERS的所有元素的所有元素(下标下标) 都要都要求和，所以可以将下标求和，所以可以将下标i省去。省去。 约束的定义方式约束的定义方式循环函数循环函数FOR(集合集合(下标下标)：关于集合的属性的约束关系式：关于集合的属性的约束关系式) 对冒号对冒号“：”前

24、面的集合的每个元素（下标），冒号前面的集合的每个元素（下标），冒号“：”后面后面的约束关系式都要成立的约束关系式都要成立 本例中，每个季度正常的生产能力是本例中，每个季度正常的生产能力是40条帆船，这正是语句条帆船，这正是语句“FOR(QUARTERS(I):RP(I)40);”的含义。的含义。由于对所有元素由于对所有元素(下标下标I),约束的形式是一样的，所以也可以像上约束的形式是一样的，所以也可以像上面定义目标函数时一样，将下标面定义目标函数时一样，将下标i省去，省去，这个语句可以简化成这个语句可以简化成“FOR(QUARTERS:RP1；“#GT#”是逻辑运算符号，意思是是逻辑运算符号，

25、意思是“大于（大于（Greater Than的字首字母缩写的字首字母缩写）” 。约束的定义方式约束的定义方式问题的求解：运行菜单命令问题的求解：运行菜单命令“LINGO|Solve” 全局最优解全局最优解RP=(40,40,40,25),OP=(0,10,35,0) 最小成本最小成本=78450 注：注：由于输入中没有给出行名，所以行名是系统自动按照行号由于输入中没有给出行名，所以行名是系统自动按照行号1-9生成的。生成的。 选择菜单命令选择菜单命令“LINGO|Generate|Disply model（Ctrl+G）”，可以得到展开形式的模型，可以得到展开形式的模型(如图如图)，可以看到完

26、整的模型，也能，可以看到完整的模型，也能确定行号确定行号(行号放在方括号行号放在方括号“ ”中，且数字前面带有下划线中，且数字前面带有下划线“_”)。 最好在输入模型时用户主动设定约束的行名最好在输入模型时用户主动设定约束的行名(即约束名即约束名)，使程，使程序清晰些。单一约束的行名设置方法就是将行名放在方括号序清晰些。单一约束的行名设置方法就是将行名放在方括号“ ”中，置于约束之前。中，置于约束之前。 后面将结合具体例子介绍在使用集合的情况下如何设置行名。后面将结合具体例子介绍在使用集合的情况下如何设置行名。 小结小结:LINGO模型最基本的组成要素模型最基本的组成要素 一般来说，一般来说，

27、 LINGO中建立的优化模型可以由五个部分组成，或中建立的优化模型可以由五个部分组成，或称为五称为五“段段”（SECTION）：）：（1 1）集合段（）集合段（SETSSETS）：）：以以“ SETS:” 开始，开始， “ENDSETS”结束，定义必要的集合变量（结束，定义必要的集合变量（SET）及其元素（）及其元素（MEMBER，含义类似于数组的下标）和属性（含义类似于数组的下标）和属性（ATTRIBUTE，含义类似于，含义类似于数组）。数组）。如上例中定义了集合如上例中定义了集合quarters(含义是季节含义是季节)，它包含四个元素即四个季节指标，它包含四个元素即四个季节指标(1,2,3

28、,4)，每个季节都有需求，每个季节都有需求(DEM)、正常生产量、正常生产量(RP)、加班生产量、加班生产量(OP)、库、库存量存量(INV)等属性等属性(相当于数组，数组下标由相当于数组，数组下标由quarters元素决定元素决定)。一旦这样的定。一旦这样的定义建立起来，如果义建立起来，如果quarters的数量不是的数量不是4而是而是1000,只需扩展其元素为只需扩展其元素为1,2,.,1000,每个季节仍然都有每个季节仍然都有DEM,RP,OP,INV这样的属性这样的属性(这些量的具体数值如果是常量这些量的具体数值如果是常量，则可在数据段输入；如果是未知数，则可不，则可在数据段输入；如果

29、是未知数，则可不 在初始段输入初值在初始段输入初值)。当。当quarters的数量不是的数量不是4而是而是1000时，没有必要把时，没有必要把1,2，.,1000全部一个一个列出来，而是全部一个一个列出来，而是可以如下定义可以如下定义quarters集合：集合：“quarters/1.1000/:DEM,RP,OP,INV;” ,“1.1000”的意思就是从的意思就是从1到到1000的所有整数。的所有整数。（2 2）目标与约束段）目标与约束段：目标函数、约束条件等，没有段的开始和：目标函数、约束条件等，没有段的开始和结束标记，因此实际上就是除其它四个段结束标记，因此实际上就是除其它四个段(都有

30、明确的段标记都有明确的段标记)外的外的LINGO模型。模型。这里一般要用到这里一般要用到LINGO的内部函数，尤其是与集合相关的求和的内部函数，尤其是与集合相关的求和函数函数SUM和循环函数和循环函数FOR等。等。上例中定义的目标函数与上例中定义的目标函数与quarters的元素数目是的元素数目是 4或或 1000并无并无具体的关系。约束的表示也类似。具体的关系。约束的表示也类似。（3 3）数据段）数据段(DATA)(DATA)：以：以 “DATA:” 开始开始, “ENDDATA”结束，对集结束，对集合的属性合的属性(数组数组)输入必要的常数数据。输入必要的常数数据。格式为：格式为：“att

31、ribute(属性属性) = value_list(常数列表常数列表);”常数列表常数列表(value_list)中数据之间可以用逗号中数据之间可以用逗号“,”分开，也可以用空分开，也可以用空格分开格分开(回车等价于一个空格回车等价于一个空格),如上面对如上面对DEM的赋值也可以写成的赋值也可以写成“DEM=40 60 75 25；”。 在LINGO模型中，如果想在运行时才对参数赋值，可以在数据段使用输入语句。但这仅能用于对单个变量赋值，输入语句格式为：“变量名 = ？；”。例如，上例中如果需要在求解模型时才给出初始库存量(记为A)，则可以在模型中数据段写上语句：”A = ?；“在求解时LIN

32、DO系统给出提示界面，等待用户输入变量A的数值。当然，此时的约束语句 INV(1)=10+RP(1)+OP(1)-DEM(1);也应该改写成 INV(1)=A+RP(1)+OP(1)-DEM(1);这样，模型就可以计算任意初始库存量(而不仅仅只能计算初始库存量为10)的情况了。（4 4）初始段）初始段(INIT)(INIT)：以：以“INIT: ”开始，开始， “ENDINIT”结束，对结束，对集合的属性集合的属性(数组数组)定义初值定义初值(因为求解算法一般是迭代算法，所以因为求解算法一般是迭代算法，所以用户如果能给出一个比较好的迭代初值，对提高算法的计算效果用户如果能给出一个比较好的迭代初

33、值，对提高算法的计算效果是有益的是有益的)。如果有一个接近最优解的初值，对如果有一个接近最优解的初值，对LINGO求解模型是有帮助求解模型是有帮助的。定义初值的格式为：的。定义初值的格式为：“attribute（属性）（属性） = value_list（常数列表）；（常数列表）；”这与数据段中的用法是类似的。这与数据段中的用法是类似的。上例中没有初始化部分，我们将在下一个例子中举例说明。上例中没有初始化部分，我们将在下一个例子中举例说明。（5 5）计算段）计算段(CALC)(CALC)：以：以“CALC: ”开始，开始， “ENDCALC”结束结束，对一些原始数据进行计算处理。，对一些原始数据

34、进行计算处理。在实际问题中，输入的数据通常是原始数据，不一定能在模型在实际问题中，输入的数据通常是原始数据，不一定能在模型中直接使用，可以在这个段对这些原始数据进行一定的中直接使用，可以在这个段对这些原始数据进行一定的“预处理预处理”，得到模型中真正需要的数据。，得到模型中真正需要的数据。例如上例，如果希望得到全年的总需求和季度平均需求，可以增加这个段：例如上例，如果希望得到全年的总需求和季度平均需求，可以增加这个段：CALC: T_DEM = SUM(quarters: DEM); !总需求总需求; A_DEM = T_DEM / size(quarters); !平均需求平均需求;ENDC

35、ALC在计算段中也可以使用集合函数（其中函数在计算段中也可以使用集合函数（其中函数size(quarters)表示集合表示集合quarters的元素个数，这里也就是的元素个数，这里也就是4）。这时，变量）。这时，变量T_DEM的值就是总需求，的值就是总需求，A_DEM的值就是平均需求（如果需要的话，这两个变量就可以在程序的其它地方作的值就是平均需求（如果需要的话，这两个变量就可以在程序的其它地方作为常数使用了）。为常数使用了）。注：上面的两个语句不能交换顺序，因为计算注：上面的两个语句不能交换顺序，因为计算A_DEM必须要用到必须要用到T_DEM的的值。此外，在计算段中只能直接使用赋值语句，而

36、不能包含需要经过解方程值。此外，在计算段中只能直接使用赋值语句，而不能包含需要经过解方程或经过求解优化问题以后才能决定的变量。或经过求解优化问题以后才能决定的变量。基本集合与派生集合基本集合与派生集合 例例3 建筑工地的位置建筑工地的位置(用平面坐标用平面坐标a, b表示，距离单位：公里表示，距离单位：公里)及水及水泥日用量泥日用量d(吨吨)下表给出。有两个临时料场位于下表给出。有两个临时料场位于P (5,1), Q (2, 7),日日储量各有储量各有20吨。从吨。从A, B两料场分别向各工地运送多少吨水泥，使两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。两个新的料场应建在何处，节省的

37、吨公里数总的吨公里数最小。两个新的料场应建在何处，节省的吨公里数有多大？有多大？a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611建立模型建立模型记工地的位置为记工地的位置为 ，水泥日用量为，水泥日用量为 ；料场位置为；料场位置为 ，日储量为，日储量为 ；从料场；从料场 向工地向工地 的运送量为的运送量为 。 ),(iiba6, 1,idi),(jjyx2 , 1,jejjiijc 2622112161MIN1s.t.,1,2,62,1,23ijjijijiijijijjifcxayacdicej使用现有临时料场时，决策变量只有使用现有临时料场

38、时，决策变量只有 （非负），所以这是（非负），所以这是LP模型；当为新模型；当为新建料场选址时决策变量为建料场选址时决策变量为 和和 ，由于目标函数，由于目标函数 对对 是非线性的，是非线性的，所以在新建料场时是所以在新建料场时是NLP模型。先解模型。先解NLP模型，而把现有临时料场的位置作模型，而把现有临时料场的位置作为初始解告诉为初始解告诉LINGO。 ijcijcjjyx ,fjjyx ,本例中集合的概念本例中集合的概念利用集合的概念，可以定义需求点利用集合的概念，可以定义需求点DEMAND和供应点和供应点SUPPLY两个集合，分别有两个集合，分别有6个和个和2个元素个元素(下标下标)。

39、但决策变量。但决策变量(运送量运送量) 与集合与集合DEMAND和集合和集合SUPPLY都有关系的。该如何定义这样都有关系的。该如何定义这样的属性？的属性？ijc集合的属性相当于以集合的元素为下标的数组。这里的集合的属性相当于以集合的元素为下标的数组。这里的 相当于相当于二维数组。它的两个下标分别来自集合二维数组。它的两个下标分别来自集合DEMAND和和SUPPLY，因此可以定义一个由二元对组成的新的集合，然后将因此可以定义一个由二元对组成的新的集合，然后将 定义成定义成这个新集合的属性。这个新集合的属性。ijcijc输入程序输入程序 定义了三个集合，其中定义了三个集合，其中LINK在前在前两

40、个集合两个集合DEMAND 和和SUPPLY的的基础上定义基础上定义表示集合表示集合LINK中的元素就是集合中的元素就是集合DEMAND 和和SUPPLY的元素组合成的有序二元组，的元素组合成的有序二元组，从数学上看从数学上看LINK是是DEMAND 和和SUPPLY的笛的笛卡儿积，也就是说卡儿积，也就是说LINK=（S，T）|SDEMAND，TSUPPLY因此，其属性因此，其属性C也就是一个也就是一个6*2的矩阵（或者的矩阵（或者说是含有说是含有12个元素的二维数组）。个元素的二维数组）。LINGO建模语言也称为矩阵生成器（建模语言也称为矩阵生成器（MATRIX GENERATOR）。类似）

41、。类似DEMAND 和和SUPPLY直接把元素列举出来的集合，称直接把元素列举出来的集合，称为为基本集合基本集合(primary set),而把而把LINK这种基于其它集合而派生出这种基于其它集合而派生出来的二维或多维集合称为来的二维或多维集合称为派生集合派生集合(derived set)。由于是。由于是DEMAND 和和SUPPLY生成了派生集合生成了派生集合LINK，所以，所以DEMAND 和和SUPPLY 称为称为LINK的的父集合父集合。输入程序输入程序 初始段 INGO对数据是按列赋值的 语句的实际赋值顺序是X=(5,2), Y=(1,7), 而不是X=(5,1), Y=（2,7)

42、等价写法：“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；输入程序输入程序 定义目标和约束，与前例的方法是类似(这里包含了派生集合)，请特别注意进一步体会集合函数SUM和FOR的用法。由于新建料场的位置理论上讲可以是任意的，所以在约束的最后(模型的“END”语句上面的一行)用free函数取消了变量X、Y的非负限制在程序开头用TITLE语句对这个模型取了一个标题“LOCATION PROBLEM；并且对目标行（OBJ）和两类约束（DEMAND_CON、

43、SUPPLY_CON）分别进行了命名(请特别注意这里约束命名的特点)。 解答解答:运行菜单命令运行菜单命令“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”, 激活

44、全局最优求解程激活全局最优求解程序。序。问题问题:最小运量最小运量89.8835是不是全局最优是不是全局最优 为减少计算工作量，对为减少计算工作量，对X，Y的取值再做一些限制。虽然理论上的取值再做一些限制。虽然理论上新建料场的位置可以是任意的，但显然最佳的料场位置不应该离新建料场的位置可以是任意的，但显然最佳的料场位置不应该离工地太远，至少不应该超出现在工地太远，至少不应该超出现在6个工地所决定的坐标的最大、个工地所决定的坐标的最大、最小值决定的矩形之外，即最小值决定的矩形之外，即: 0.5=x=8.75, 0.75=y=7.75. 可以用可以用bnd函数加函数加上这个条件取代模型上这个条件取

45、代模型END上面的行，运行上面的行，运行NLP模型，全局最优模型，全局最优求解程序花费的时间求解程序花费的时间仍然很长，运行仍然很长，运行27分分35秒时人为终止求解秒时人为终止求解(按下按下“Interrupt Solver”按钮按钮)得到左得到左边模型窗口和全局求边模型窗口和全局求解器的状态窗口解器的状态窗口此时目标函数值的下界（此时目标函数值的下界（Obj Bound=85.2638）与目前得到的最好）与目前得到的最好的可行解的目标函数值（的可行解的目标函数值（Best Obj=85.2661）相差已经非常小，可）相差已经非常小，可以认为已经得到了全局最优解。以认为已经得到了全局最优解。

46、 计算结果计算结果 012345678901234567835476112016工地与料场示意图工地与料场示意图 : “*”表示料场，表示料场，“+”表表示工地示工地 可以认为是模型的最后结果可以认为是模型的最后结果 附注：如果要把料厂P(5, 1), Q (2, 7)的位置看成是已知并且固定的，这时是LP模型。只需要把初始段的“X Y =5，1，2，7；”语句移到数据段就可以了。此时，运行结果告诉我们得到全局最优解（变量C的取值这里略去），最小运量136.2275(吨公里)。稠密集合与稀疏集合稠密集合与稀疏集合 包含了两个基本集合构成的所有二元有序对的派生集合称为包含了两个基本集合构成的所有

47、二元有序对的派生集合称为稠密稠密集合集合(简称稠集简称稠集)。有时候，在实际问题中，一些属性。有时候，在实际问题中，一些属性(数组数组) 只在笛只在笛卡儿积的一个真子集合上定义，这种派生集合称为卡儿积的一个真子集合上定义，这种派生集合称为稀疏集合稀疏集合(简称简称疏集疏集)。例例 (最短路问题最短路问题) 在纵横交错的公路网中，货车司机希望找到一条在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路从一个城市到另一个城市的最短路. 下图表示的是公路网下图表示的是公路网, 节点表节点表示货车可以停靠的城市示货车可以停靠的城市,弧上的权表示两个城市之间的距离弧上的权表示两个城市

48、之间的距离(百公里百公里). 那么那么,货车从城市货车从城市S出发到达城市出发到达城市T,如何选择行驶路线如何选择行驶路线,使所经过使所经过的路程最短的路程最短?STA1 A2 A3 B1 B2 C1 C2 633665874678956分析分析 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

49、的最优行驶路线的路长: 0;1min,.2YXL SL XL Yd Y XXS本例的计算本例的计算 1231123321233112221221216,3,3;min6,8,7107;min5,6,474;min6,8158;min7,9169;min5,6205.L AL AL AL BL AL AL AL AL BL AL AL AL AL CL BL BL BL CL BL BL BL TL CL CL CSTA1 A2 A3 B1 B2 C1 C2 633665874678956所以, 从S到T的最优行驶路线的路长为20. 进一步分析以上求解过程, 可以得到从S到T的最优行驶路线为S

50、A3 B2 C1 T.这种计算方法在数学上称为动态规划(Dynamic Programming) 本例的本例的LINGO求解求解“CITIES”(城市城市):一个基本集合一个基本集合(元素通过枚举给出元素通过枚举给出)L:CITIES对应的属性变量对应的属性变量(我们要求的最短路长我们要求的最短路长) “ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。 D:稀疏集合ROADS对应的属性变量(给定的距离)本例的本例的LINGO求解求解从模型中还可以看出：这个从模型