《优化建模与LINGO第03章.ppt》由会员分享,可在线阅读,更多相关《优化建模与LINGO第03章.ppt(153页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、优优 化化 建建 模模优化建模与优化建模与LINDO/LINGO软件软件第第 3 章章 LINGO软件的基本使用方法软件的基本使用方法原书相关信息原书相关信息谢金星谢金星,薛毅编著薛毅编著,清华大学出版社清华大学出版社,2005年年7月第月第1版版.http:/ 化化 建建 模模内容提要内容提要1.LINGO入门入门2.在在LINGO中使用集合中使用集合3.运算符和函数运算符和函数4.LINGO的主要菜单命令的主要菜单命令5.LINGO命令窗口命令窗口 6.习题优优 化化 建建 模模1.LINGO入门入门1.LINGO入门入门2.在在LINGO中使用集合中使用集合3.运算符和函数运算符和函数4
2、.LINGO的主要菜单命令的主要菜单命令5.LINGO命令窗口命令窗口 6.习题优优 化化 建建 模模安装文件安装文件20M多一点,需要接受安装协议、选择安装多一点,需要接受安装协议、选择安装目录(缺省目录(缺省C:LINGO9)。)。LINGO软件的安装软件的安装安装过程安装过程:与与LINDO for WindowsLINDO for Windows类似类似.安装完成前,在出现的对话框安装完成前,在出现的对话框(如图如图)中选择缺省的建中选择缺省的建模模(即编程即编程)语言,系统推荐的是采用语言,系统推荐的是采用LINGO。安装。安装后可通过后可通过“LINGO|Options|File
3、Format”命令修改缺命令修改缺省的建模(即编程)语言。省的建模(即编程)语言。优优 化化 建建 模模第一次运行时提示输入授权密码,如图:第一次运行时提示输入授权密码,如图:优优 化化 建建 模模LINGO软件的主要特色软件的主要特色两种命令模式两种命令模式Windows模式模式:通过下拉式菜单命令驱动通过下拉式菜单命令驱动LINGO运运行(多数菜单命令有快捷键,常用的菜单命令有快捷行(多数菜单命令有快捷键,常用的菜单命令有快捷按钮),图形界面,使用方便;按钮),图形界面,使用方便;命令行命令行 模式:仅在命令窗口模式:仅在命令窗口(Command Window)下操作,下操作,通过输入行命
4、令驱动通过输入行命令驱动LINGO运行运行。(这里主要介绍这种模式这里主要介绍这种模式)优优 化化 建建 模模从从LINDO LINDO 到到 LINGOLINGOLINGO 9.0功能增强,性能稳定,解答结果可靠。与功能增强,性能稳定,解答结果可靠。与LINDO相比,相比,LINGO 软件主要具有两大优点软件主要具有两大优点:内置建模语言,允许以简练、直观的方式描述较大内置建模语言,允许以简练、直观的方式描述较大规模的优化问题,所需的数据可以以一定格式保存规模的优化问题,所需的数据可以以一定格式保存在独立的文件中。在独立的文件中。除具有除具有LINDO的全部功能外,还可用于求解非线的全部功能
5、外,还可用于求解非线性规划问题,包括非线性整数规划问题性规划问题,包括非线性整数规划问题;优优 化化 建建 模模在在LINGO中使用中使用LINDO模型模型LINGOLINGO的界面的界面LINGO软件的主窗口(用软件的主窗口(用户界面),所有其他窗口户界面),所有其他窗口都在这个窗口之内。都在这个窗口之内。模型窗口(模型窗口(Model Window),用于输入),用于输入LINGO优化模型(即优化模型(即LINGO程序)。程序)。状态行(最左边显状态行(最左边显示示“Ready”,表,表示示“准备就绪准备就绪”)当前时间当前时间 当前光标当前光标的位置的位置 优优 化化 建建 模模LING
6、OLINGO的文件类型的文件类型.LG4:LINGO格式的模型文件,保存了模型窗口中所格式的模型文件,保存了模型窗口中所能够看到的所有文本和其他对象及其格式信息;能够看到的所有文本和其他对象及其格式信息;.LNG:文本格式的模型文件,不保存模型中的格式信:文本格式的模型文件,不保存模型中的格式信息(如字体、颜色、嵌入对象等);息(如字体、颜色、嵌入对象等);.LDT:LINGO数据文件;数据文件;.LTF:LINGO命令脚本文件;命令脚本文件;.LGR:LINGO报告文件;报告文件;.LTX:LINDO格式的模型文件;格式的模型文件;.MPS:示:示MPS(数学规划系统)格式的模型文件。(数学
7、规划系统)格式的模型文件。除除“LG4”文件外,文件外,另外几种格式的文件另外几种格式的文件都是普通的文本文件,都是普通的文本文件,可以用任何文本编辑可以用任何文本编辑器打开和编辑。器打开和编辑。优优 化化 建建 模模在在LINGOLINGO中使用中使用LINDOLINDO模型模型 选择菜单命令选择菜单命令“File|Open(F3)”,可以看到,可以看到“打开打开文件文件”对话框。对话框。(如图)(如图)在在LINGO中可以直接使用中可以直接使用LINDO语法编写的优化模型(即优化程序)。作语法编写的优化模型(即优化程序)。作为一个最简单的例子,在名为为一个最简单的例子,在名为EXAM020
8、1.LTX的模型文件中保存了一个的模型文件中保存了一个LINDO模型,我们现在看看如何用模型,我们现在看看如何用LINGO把它打开。把它打开。优优 化化 建建 模模在在LINGOLINGO中使用中使用LINDOLINDO模型模型 打开打开“EXAM0201.LTX”文件文件(如下图)(如下图)选择选择“LINGO|Solve(Ctrl+S)”来运行这来运行这个程序(运行状态窗口个程序(运行状态窗口如右图)如右图)优优 化化 建建 模模 运行程序的运行程序的LINGO报告窗口(如下图)报告窗口(如下图)在在LINGOLINGO中使用中使用LINDOLINDO模型模型注:注:LINGO不询问是否进
9、行敏感性分析,敏感性分析不询问是否进行敏感性分析,敏感性分析需要将来通过修改系统选项启动敏感性分析后,再调需要将来通过修改系统选项启动敏感性分析后,再调用用“REPORT|RANGE”菜单命令来实现。现在同样可以菜单命令来实现。现在同样可以把模型和结果报告保存在文件中。把模型和结果报告保存在文件中。优优 化化 建建 模模运行状态窗口运行状态窗口Variables(变量数量):(变量数量):变量总数(变量总数(Total)、)、非线性变量数(非线性变量数(Nonlinear)、)、整数变量数(整数变量数(Integer)。)。Constraints(约束数量):(约束数量):约束总数(约束总数(
10、Total)、)、非线性约束个数非线性约束个数(Nonlinear)。Nonzeros(非零系数数量):(非零系数数量):总数(总数(Total)、)、非线性项系数个数非线性项系数个数(Nonlinear)。Generator Memory Used(K)(内存使用内存使用量量)Elapsed Runtime(hh:mm:ss)(求解花费的时间)(求解花费的时间)优优 化化 建建 模模运行状态窗口运行状态窗口求解求解器器(求求解程解程序序)状状态框态框当前模型的类型当前模型的类型:LP,QP,ILP,IQP,PILP,PIQP,NLP,INLP,PINLP(以(以I开头表示开头表示IP,以,以
11、PI开头表示开头表示PIP)当前解的状态当前解的状态:Global Optimum,Local Optimum,Feasible,Infeasible“(不可行不可行),Unbounded“(无界无界),Interrupted“(中断中断),Undetermined“(未确定未确定)解的目标函数值解的目标函数值 当前约束不满足的总量当前约束不满足的总量(不是不不是不满足的约束的个数满足的约束的个数):实数(即使实数(即使该值该值=0,当前解也可能不可行,当前解也可能不可行,因为这个量中没有考虑用上下界因为这个量中没有考虑用上下界命令形式给出的约束)命令形式给出的约束)目前为止的目前为止的迭代次
12、数迭代次数 优优 化化 建建 模模运行状态窗口运行状态窗口扩展扩展的求的求解器解器(求求解程解程序序)状态状态框框使用的特殊求解程序使用的特殊求解程序:B-and-B(分枝定界算法分枝定界算法)Global(全局最优求解程序全局最优求解程序)Multistart(用多个初始点求解的程序用多个初始点求解的程序)目前为止找到的可行目前为止找到的可行解的最佳目标函数值解的最佳目标函数值 目标函数值的界目标函数值的界 特殊求解程序当前运行步数:特殊求解程序当前运行步数:分枝数分枝数(对对B-and-B程序程序);子问题数子问题数(对对Global程序程序);初始点数初始点数(对对Multistart程
13、序程序)有效步数有效步数 优优 化化 建建 模模注:凡是可以从一个约束直接解出变量取值时,这个注:凡是可以从一个约束直接解出变量取值时,这个变量就不认为是决策变量而是固定变量,不列入统计变量就不认为是决策变量而是固定变量,不列入统计中;只含有固定变量的约束也不列入约束统计中。中;只含有固定变量的约束也不列入约束统计中。运行状态窗口运行状态窗口优优 化化 建建 模模LINGOLINGO早期版本对早期版本对LINDOLINDO的兼容问题的兼容问题在LINGO 9.0以前的版本中不能直接用File|Open命令打开LINDO模型,但由FILE|IMPORT LINDO FILE(F12)命令可以直接
14、把LINDO的模型文件转化成LINGO模型。运行后屏幕上会显示一个标准的“打开文件”的对话框,打开EXAM0201.LTX,在LINGO主窗口中又打开了命令窗口(Command Window)显示原始文件,名为“exam0201”的模型窗口显示的是等价的LINGO模型。当前光标位于命令窗口。优优 化化 建建 模模从从LINDO模型到模型到LINGO模型的实质性转化工作主要在模型的实质性转化工作主要在于以下几个方面于以下几个方面(这也是这也是LINGO模型的最基本特征模型的最基本特征):将目标函数的表示方式从将目标函数的表示方式从“MAX”变成了变成了“MAX=”;“ST”(SubjectTo)
15、在在LINGO模型中不需要,被删除;模型中不需要,被删除;在系数与变量之间增加运算符在系数与变量之间增加运算符“*”(即乘号不能省略即乘号不能省略);每行每行(目标、约束和说明语句目标、约束和说明语句)后面增加一个分号后面增加一个分号“;”;约束的名字被放到约束的名字被放到“”中,不放在右半括号中,不放在右半括号“)”前;前;LINGO中模型以中模型以“MODEL:”开始,以开始,以“END”结束。结束。对简单的模型,这两个语句也可以省略。对简单的模型,这两个语句也可以省略。LINGOLINGO早期版本对早期版本对LINDOLINDO的兼容问题的兼容问题优优 化化 建建 模模一个简单的一个简单
16、的LINGO程序程序例例 直接用LINGO来解如下二次规划问题:输入窗口如下:输入窗口如下:优优 化化 建建 模模程序语句输入的备注:程序语句输入的备注:LINGO总是根据总是根据“MAX=”或或“MIN=”寻找目标函数,寻找目标函数,而除注释语句和而除注释语句和TITLE语句外的其他语句都是约束条语句外的其他语句都是约束条件,因此语句的顺序并不重要件,因此语句的顺序并不重要。限定变量取整数值的语句为限定变量取整数值的语句为“GIN(X1)”和和“GIN(X2)”,不可以写成,不可以写成“GIN(2)”,否则,否则LINGO将把这个模型看成没有整数变量。将把这个模型看成没有整数变量。LINGO
17、中函数一律需要以中函数一律需要以“”开头,其中整型变量开头,其中整型变量函数(函数(BIN、GIN)和上下界限定函数()和上下界限定函数(FREE、SUB、SLB)与)与LINDO中的命令类似。而且中的命令类似。而且0/1变量函数是变量函数是BIN函数。函数。优优 化化 建建 模模输出结果:输出结果:运行菜单命令运行菜单命令“LINGO|Solve”最优整数解最优整数解X=(35,65)最大利润最大利润=11077.5 优优 化化 建建 模模输出结果备注:输出结果备注:通过菜单“WINDOW|Status Window”看到状态窗口,可看到最佳目标值“Best Obj”与问题的上界“Obj B
18、ound”已经是一样的,当前解的最大利润与这两个值非常接近,是计算误差引起的。如果采用全局最优求解程序(后面介绍),可以验证它就是全局最优解。LINGO是将它作为PINLP(纯整数非线性规划)来求解,因此找到的是局部最优解。优优 化化 建建 模模一个简单的一个简单的LINGO程序程序LINGO的基本用法的几点注意事项的基本用法的几点注意事项 LINGO中不区分大小写字母;变量和行名可以超过8个字符,但不能超过32个字符,且必须以字母开头。用LINGO解优化模型时已假定所有变量非负(除非用限定变量取值范围的函数free或sub或slb另行说明)。变量可以放在约束条件的右端(同时数字也可放在约束条
19、件的左端)。但为了提高LINGO求解时的效率,应尽可能采用线性表达式定义目标和约束(如果可能的话)。语句是组成LINGO模型的基本单位,每个语句都以分号结尾,编写程序时应注意模型的可读性。例如:一行只写一个语句,按照语句之间的嵌套关系对语句安排适当的缩进,增强层次感。以感叹号开始的是说明语句(说明语句也需要以分号结束))。优优 化化 建建 模模2.在在LINGO中使用集合中使用集合 1.LINGO入门入门2.在在LINGO中使用集合中使用集合3.运算符和函数运算符和函数4.LINGO的主要菜单命令的主要菜单命令5.LINGO命令窗口命令窗口 6.习题优优 化化 建建 模模集合的基本用法和集合的
20、基本用法和LINGO模型的基本要素模型的基本要素 理解理解LINGO建模语言最重要的是理解集合(建模语言最重要的是理解集合(Set)及其)及其属性(属性(Attribute)的概念。)的概念。例例 SAILCO公司需要决定下四个季度的帆船生产量。下公司需要决定下四个季度的帆船生产量。下四个季度的帆船需求量分别是四个季度的帆船需求量分别是40条,条,60条,条,75条,条,25条,条,这些需求必须按时满足。每个季度正常的生产能力是这些需求必须按时满足。每个季度正常的生产能力是40条帆船,每条船的生产费用为条帆船,每条船的生产费用为400美元。如果加班生产,美元。如果加班生产,每条船的生产费用为每
21、条船的生产费用为450美元。每个季度末,每条船的美元。每个季度末,每条船的库存费用为库存费用为20美元。假定生产提前期为美元。假定生产提前期为0,初始库存为,初始库存为10条船。如何安排生产可使总费用最小?条船。如何安排生产可使总费用最小?用用DEM,RP,OP,INV分别表示需求量、正常生产的产量、分别表示需求量、正常生产的产量、加班生产的产量、库存量,则加班生产的产量、库存量,则DEM,RP,OP,INV对每个对每个季度都应该有一个对应的值,也就说他们都应该是一个季度都应该有一个对应的值,也就说他们都应该是一个由由4个元素组成的数组,其中个元素组成的数组,其中DEM是已知的,而是已知的,而
22、RP,OP,INV是未知数。是未知数。优优 化化 建建 模模问题的模型问题的模型(可以看出是可以看出是LP模型模型)目标函数是所有费用的和目标函数是所有费用的和 约束条件主要有两个:约束条件主要有两个:1)能力限制:)能力限制:2)产品数量的平衡方程:)产品数量的平衡方程:加上变量的非负约束加上变量的非负约束优优 化化 建建 模模注:注:LINDO中没有数组,只能对每个季度分别定义变量,如正常产量就要有RP1,RP2,RP3,RP4 4个变量等。写起来就比较麻烦,尤其是更多(如1000个季度)的时候。记四个季度组成的集合QUARTERS=1,2,3,4,它们就是上面数组的下标集合,而数组DEM
23、,RP,OP,INV对集合QUARTERS中的每个元素1,2,3,4分别对应于一个值。LINGO正是充分利用了这种数组及其下标的关系,引入了“集合”及其“属性”的概念,把QUARTERS=1,2,3,4称为集合,把DEM,RP,OP,INV称为该集合的属性(即定义在该集合上的属性)。优优 化化 建建 模模QUARTERS集合的属性DEM RPOP INVQUARTERS集合2341 集合及其属性集合及其属性 优优 化化 建建 模模集合元素及集合的属性确定的所有变量集合元素及集合的属性确定的所有变量集合QUARTERS的元素1234定义在集合QUARTERS上的属性DEMDEM(1)DEM(2)
24、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中定义集合及其属性中定义集合及其属性 LP模型在模型在LINGO中的一个典型输入方式中的一个典型输入方式 以以“MODEL:”开始开始 以以“END”结结束束集合定义部分从集合定义部分从(“SETS:”到到“ENDSETS”):定:定义集合及其属性义集合及其属性集合定义部分从集合定义部分从(“DATA:”到到“ENDDATA”)给出优化目标给出优化目标和约束和约束 优优 化化 建建 模模目标函数的定
25、义方式目标函数的定义方式SUM(集合(下标):关于集合的属性的表达式集合(下标):关于集合的属性的表达式)对语句中冒号对语句中冒号“:”后面的表达式,按照后面的表达式,按照“:”前前面的集合指定的下标(元素)进行求和。面的集合指定的下标(元素)进行求和。本例中目标函数也可以等价地写成本例中目标函数也可以等价地写成SUM(QUARTERS(i):400*RP(i)+450*OP(i)+20*INV(i),“SUM”相当于求和符号相当于求和符号“”,“QUARTERS(i)”相当于相当于“iQUARTERS”的含义。的含义。由于本例中目标函数对集合由于本例中目标函数对集合QUARTERS的所有元素
26、的所有元素(下下标标)都要求和,所以可以将下标都要求和,所以可以将下标i省去。省去。优优 化化 建建 模模约束的定义方式约束的定义方式循环函数循环函数FOR(集合集合(下标下标):关于集合的属性的约束关系式:关于集合的属性的约束关系式)对冒号对冒号“:”前面的集合的每个元素(下标),冒号前面的集合的每个元素(下标),冒号“:”后面的约束关系式都要成立后面的约束关系式都要成立 本例中,每个季度正常的生产能力是本例中,每个季度正常的生产能力是40条帆船,这正是条帆船,这正是语句语句“FOR(QUARTERS(I):RP(I)40);”的含义。的含义。由于对所有元素由于对所有元素(下标下标I),约束
27、的形式是一样的,所以也约束的形式是一样的,所以也可以像上面定义目标函数时一样,将下标可以像上面定义目标函数时一样,将下标i省去,省去,这个语句可以简化成这个语句可以简化成“FOR(QUARTERS:RP1;“#GT#”是逻辑运算符号,意思是是逻辑运算符号,意思是“大于(大于(Greater Than的字首字母缩写)的字首字母缩写)”。约束的定义方式约束的定义方式优优 化化 建建 模模问题的求解:运行菜单命令问题的求解:运行菜单命令“LINGO|Solve”全局最优解全局最优解RP=(40,40,40,25),OP=(0,10,35,0)最小成本最小成本=78450 优优 化化 建建 模模注:注
28、:由于输入中没有给出行名,所以行名是系统自动按照行号由于输入中没有给出行名,所以行名是系统自动按照行号1-9生成的。生成的。选择菜单命令选择菜单命令“LINGO|Generate|Disply model(Ctrl+G)”,可以得到展开形式的模型,可以得到展开形式的模型(如图如图),可以看到完整的模型,也,可以看到完整的模型,也能确定行号能确定行号(行号放在方括号行号放在方括号“”中,且数字前面带有下划线中,且数字前面带有下划线“_”)。最好在输入模型时用户主动设定约束的行名最好在输入模型时用户主动设定约束的行名(即约束名即约束名),使,使程序清晰些。单一约束的行名设置方法就是将行名放在方括号
29、程序清晰些。单一约束的行名设置方法就是将行名放在方括号“”中,置于约束之前。中,置于约束之前。后面将结合具体例子介绍在使用集合的情况下如何设置行名。后面将结合具体例子介绍在使用集合的情况下如何设置行名。优优 化化 建建 模模小结小结:LINGO模型最基本的组成要素模型最基本的组成要素 一般来说,一般来说,LINGO中建立的优化模型可以由五个部分中建立的优化模型可以由五个部分组成,或称为五组成,或称为五“段段”(SECTION):):(1 1)集合段()集合段(SETSSETS):):以以“SETS:”开始,开始,“ENDSETS”结束,定义必要的集合变量(结束,定义必要的集合变量(SET)及其
30、)及其元素(元素(MEMBER,含义类似于数组的下标)和属性,含义类似于数组的下标)和属性(ATTRIBUTE,含义类似于数组)。,含义类似于数组)。如上例中定义了集合如上例中定义了集合quarters(含义是季节含义是季节),它包含四个元素即四个季节指标,它包含四个元素即四个季节指标(1,2,3,4),每个季节都有需求,每个季节都有需求(DEM)、正常生产量、正常生产量(RP)、加班生产量、加班生产量(OP)、库、库存量存量(INV)等属性等属性(相当于数组,数组下标由相当于数组,数组下标由quarters元素决定元素决定)。一旦这样的定。一旦这样的定义建立起来,如果义建立起来,如果quar
31、ters的数量不是的数量不是4而是而是1000,只需扩展其元素为只需扩展其元素为1,2,.,1000,每个季节仍然都有每个季节仍然都有DEM,RP,OP,INV这样的属性这样的属性(这些量的具体数值如果是常量,这些量的具体数值如果是常量,则可在数据段输入;如果是未知数,则可在初始段输入初值则可在数据段输入;如果是未知数,则可在初始段输入初值)。当。当quarters的数的数量不是量不是4而是而是1000时,没有必要把时,没有必要把1,2,.,1000全部一个一个列出来,而是可全部一个一个列出来,而是可以如下定义以如下定义quarters集合:集合:“quarters/1.1000/:DEM,R
32、P,OP,INV;”,“1.1000”的意思就是从的意思就是从1到到1000的所有整数。的所有整数。优优 化化 建建 模模(2 2)目标与约束段)目标与约束段:目标函数、约束条件等,没有段:目标函数、约束条件等,没有段的开始和结束标记,因此实际上就是除其它四个段的开始和结束标记,因此实际上就是除其它四个段(都有都有明确的段标记明确的段标记)外的外的LINGO模型。模型。这里一般要用到这里一般要用到LINGO的内部函数,尤其是与集合相的内部函数,尤其是与集合相关的求和函数关的求和函数SUM和循环函数和循环函数FOR等。等。上例中定义的目标函数与上例中定义的目标函数与quarters的元素数目是的
33、元素数目是 4或或 1000并无具体的关系。约束的表示也类似。并无具体的关系。约束的表示也类似。优优 化化 建建 模模(3 3)数据段)数据段(DATA)(DATA):以:以“DATA:”开始开始,“ENDDATA”结结束,对集合的属性束,对集合的属性(数组数组)输入必要的常数数据。输入必要的常数数据。格式为:格式为:“attribute(属性属性)=value_list(常数列表常数列表);”常数列表常数列表(value_list)中数据之间可以用逗号中数据之间可以用逗号“,”分开,分开,也可以用空格分开也可以用空格分开(回车等价于一个空格回车等价于一个空格),如上面对如上面对DEM的赋值也
34、可以写成的赋值也可以写成“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)的情况了。优优 化
35、化 建建 模模(4 4)初始段)初始段(INIT)(INIT):以:以“INIT:”开始,开始,“ENDINIT”结束,对集合的属性结束,对集合的属性(数组数组)定义初值定义初值(因为求解算法一因为求解算法一般是迭代算法,所以用户如果能给出一个比较好的迭代般是迭代算法,所以用户如果能给出一个比较好的迭代初值,对提高算法的计算效果是有益的初值,对提高算法的计算效果是有益的)。如果有一个接近最优解的初值,对如果有一个接近最优解的初值,对LINGO求解模型是求解模型是有帮助的。定义初值的格式为:有帮助的。定义初值的格式为:“attribute(属性)(属性)=value_list(常数列表);(常数
36、列表);”这与数据段中的用法是类似的。这与数据段中的用法是类似的。上例中没有初始化部分,我们将在下一个例子中举例上例中没有初始化部分,我们将在下一个例子中举例说明。说明。优优 化化 建建 模模(5 5)计算段)计算段(CALC)(CALC):以:以“CALC:”开始,开始,“ENDCALC”结束,对一些原始数据进行计算处理。结束,对一些原始数据进行计算处理。在实际问题中,输入的数据通常是原始数据,不一定在实际问题中,输入的数据通常是原始数据,不一定能在模型中直接使用,可以在这个段对这些原始数据进能在模型中直接使用,可以在这个段对这些原始数据进行一定的行一定的“预处理预处理”,得到模型中真正需要
37、的数据。,得到模型中真正需要的数据。例如上例,如果希望得到全年的总需求和季度平均需求,可以增加这个段:例如上例,如果希望得到全年的总需求和季度平均需求,可以增加这个段:CALC:T_DEM=SUM(quarters:DEM);!总需求总需求;A_DEM=T_DEM/size(quarters);!平均需求平均需求;ENDCALC在计算段中也可以使用集合函数(其中函数在计算段中也可以使用集合函数(其中函数size(quarters)表示集合表示集合quarters的元素个数,这里也就是的元素个数,这里也就是4)。这时,变量)。这时,变量T_DEM的值就是总需的值就是总需求,求,A_DEM的值就是
38、平均需求(如果需要的话,这两个变量就可以在程的值就是平均需求(如果需要的话,这两个变量就可以在程序的其它地方作为常数使用了)。序的其它地方作为常数使用了)。注:上面的两个语句不能交换顺序,因为计算注:上面的两个语句不能交换顺序,因为计算A_DEM必须要用到必须要用到T_DEM的的值。此外,在计算段中只能直接使用赋值语句,而不能包含需要经过解方值。此外,在计算段中只能直接使用赋值语句,而不能包含需要经过解方程或经过求解优化问题以后才能决定的变量。程或经过求解优化问题以后才能决定的变量。优优 化化 建建 模模基本集合与派生集合基本集合与派生集合 例例3.4 建筑工地的位置建筑工地的位置(用平面坐标
39、用平面坐标a,b表示,距离单位:表示,距离单位:公里公里)及水泥日用量及水泥日用量d(吨吨)下表给出。有两个临时料场位下表给出。有两个临时料场位于于P(5,1),Q(2,7),日储量各有日储量各有20吨。从吨。从A,B两料场分别两料场分别向各工地运送多少吨水泥,使总的吨公里数最小。两个向各工地运送多少吨水泥,使总的吨公里数最小。两个新的料场应建在何处,节省的吨公里数有多大?新的料场应建在何处,节省的吨公里数有多大?a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611优优 化化 建建 模模建立模型建立模型记工地的位置为记工地的位置为 ,水泥日用量为
40、,水泥日用量为 ;料场;料场位置为位置为 ,日储量为,日储量为 ;从料场;从料场 向工地向工地 的的运送量为运送量为 。使用现有临时料场时,决策变量只有使用现有临时料场时,决策变量只有 (非负),所以这是(非负),所以这是LP模型;当为新模型;当为新建料场选址时决策变量为建料场选址时决策变量为 和和 ,由于目标函数,由于目标函数 对对 是非线性的,是非线性的,所以在新建料场时是所以在新建料场时是NLP模型。先解模型。先解NLP模型,而把现有临时料场的位置作模型,而把现有临时料场的位置作为初始解告诉为初始解告诉LINGO。优优 化化 建建 模模本例中集合的概念本例中集合的概念利用集合的概念,可以
41、定义需求点利用集合的概念,可以定义需求点DEMAND和供应点和供应点SUPPLY两个集合,分别有两个集合,分别有6个和个和2个元素个元素(下标下标)。但决。但决策变量策变量(运送量运送量)与集合与集合DEMAND和集合和集合SUPPLY都都有关系的。该如何定义这样的属性?有关系的。该如何定义这样的属性?集合的属性相当于以集合的元素为下标的数组。这里的集合的属性相当于以集合的元素为下标的数组。这里的 相当于二维数组。它的两个下标分别来自集合相当于二维数组。它的两个下标分别来自集合DEMAND和和SUPPLY,因此可以定义一个由二元对组,因此可以定义一个由二元对组成的新的集合,然后将成的新的集合,
42、然后将 定义成这个新集合的属性。定义成这个新集合的属性。优优 化化 建建 模模输入程序输入程序 定义了三个集合,其中定义了三个集合,其中LINK在前在前两个集合两个集合DEMAND 和和SUPPLY的的基础上定义基础上定义表示集合表示集合LINK中的元素就是集合中的元素就是集合DEMAND 和和SUPPLY的元素组合成的有序二元组,的元素组合成的有序二元组,从数学上看从数学上看LINK是是DEMAND 和和SUPPLY的笛的笛卡儿积,也就是说卡儿积,也就是说LINK=(S,T)|SDEMAND,TSUPPLY因此,其属性因此,其属性C也就是一个也就是一个6*2的矩阵(或者说的矩阵(或者说是含有
43、是含有12个元素的二维数组)。个元素的二维数组)。LINGO建模语言也称为矩阵生成器(建模语言也称为矩阵生成器(MATRIX GENERATOR)。类似)。类似DEMAND 和和SUPPLY直接把元素列举出直接把元素列举出来的集合,称为来的集合,称为基本集合基本集合(primary set),而把而把LINK这种基于其它这种基于其它集合而派生出来的二维或多维集合称为集合而派生出来的二维或多维集合称为派生集合派生集合(derived set)。由于是由于是DEMAND 和和SUPPLY生成了派生集合生成了派生集合LINK,所以,所以DEMAND 和和SUPPLY 称为称为LINK的的父集合父集合
44、。优优 化化 建建 模模输入程序输入程序 初始段 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;优优 化化 建建 模模输入程序输入程序 定义目标和约束,与前例的方法是类似(这里包含了派生集合),请特别注意进一步体会集合函数SUM和FOR的用法。由于新建料场的位置理论上讲可以是任意的,所以在约束的最后(模型的“END”语句上面的一
45、行)用free函数取消了变量X、Y的非负限制在程序开头用TITLE语句对这个模型取了一个标题“LOCATION PROBLEM;并且对目标行(OBJ)和两类约束(DEMAND_CON、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是不是全局最优是不是全局
46、最优 是用是用“LINGO|Options”菜单命令打开选项对话框,在菜单命令打开选项对话框,在“Global Solver”选项卡上选择选项卡上选择“Use Global Solver”,激激活全局最优求解程序。活全局最优求解程序。优优 化化 建建 模模问题问题:最小运量最小运量89.8835是不是全局最优是不是全局最优 为减少计算工作量,对为减少计算工作量,对X,Y的取值再做一些限制。虽然理论上的取值再做一些限制。虽然理论上新建料场的位置可以是任意的,但显然最佳的料场位置不应该离新建料场的位置可以是任意的,但显然最佳的料场位置不应该离工地太远,至少不应该超出现在工地太远,至少不应该超出现在
47、6个工地所决定的坐标的最大、个工地所决定的坐标的最大、最小值决定的矩形之外,即最小值决定的矩形之外,即:0.5=x=8.75,0.75=y=7.75.可以用可以用bnd函数加上函数加上这个条件取代模型这个条件取代模型END上面的行,运行上面的行,运行NLP模型,全局最优模型,全局最优求解程序花费的时间求解程序花费的时间仍然很长,运行仍然很长,运行27分分35秒时人为终止求解秒时人为终止求解(按下按下“Interrupt Solver”按钮按钮)得到左得到左边模型窗口和全局求边模型窗口和全局求解器的状态窗口解器的状态窗口此时目标函数值的下界(此时目标函数值的下界(Obj Bound=85.263
48、8)与目前得到的最好)与目前得到的最好的可行解的目标函数值(的可行解的目标函数值(Best Obj=85.2661)相差已经非常小,可)相差已经非常小,可以认为已经得到了全局最优解。以认为已经得到了全局最优解。优优 化化 建建 模模计算结果计算结果 工地与料场示意图工地与料场示意图:“*”表示料场,表示料场,“+”表示工地表示工地 可以认为是模型的最后结果可以认为是模型的最后结果 附注:如果要把料厂P(5,1),Q(2,7)的位置看成是已知并且固定的,这时是LP模型。只需要把初始段的“X Y=5,1,2,7;”语句移到数据段就可以了。此时,运行结果告诉我们得到全局最优解(变量C的取值这里略去)
49、,最小运量136.2275(吨公里)。优优 化化 建建 模模稠密集合与稀疏集合稠密集合与稀疏集合 包含了两个基本集合构成的所有二元有序对的派生集合包含了两个基本集合构成的所有二元有序对的派生集合称为称为稠密集合稠密集合(简称稠集简称稠集)。有时候,在实际问题中,一。有时候,在实际问题中,一些属性些属性(数组数组)只在笛卡儿积的一个真子集合上定义,这只在笛卡儿积的一个真子集合上定义,这种派生集合称为种派生集合称为稀疏集合稀疏集合(简称疏集简称疏集)。例例(最短路问题最短路问题)在纵横交错的公路网中,货车司机希望找到一条在纵横交错的公路网中,货车司机希望找到一条从一个城市到另一个城市的最短路从一个
50、城市到另一个城市的最短路.下图表示的是公路网下图表示的是公路网,节点表节点表示货车可以停靠的城市示货车可以停靠的城市,弧上的权表示两个城市之间的距离弧上的权表示两个城市之间的距离(百公百公里里).那么那么,货车从城市货车从城市S出发到达城市出发到达城市T,如何选择行驶路线如何选择行驶路线,使所经使所经过的路程最短过的路程最短?STA1 A2 A3 B1 B2 C1 C2 633665874678956优优 化化 建建 模模STA1 A2 A3 B1 B2 C1 C2 633665874678956分析分析 假设从假设从S到到T的最优行驶路线的最优行驶路线 P 经过城市经过城市C1,则则P中从中