优化建模与LINDO/LINGO优化软件

四川理工学院理学院张先君电话:15983177157(66647)邮箱:2899945082@qq.
com数学建模讲座1.
优化模型简介2.
LINDO公司的主要软件产品及功能简介3.
LINDO软件的使用简介4.
LINGO软件的使用简介5.
建模与求解实例(结合软件使用)简要提纲1.
优化模型简介优化模型实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划优化问题三要素:决策变量;目标函数;约束条件约束条件决策变量可行解(满足约束)与可行域(可行解的集合)最优解(取到最小/大值的可行解)目标函数优化问题的一般形式1.
LINDO/LINGO软件2.
MATLAB优化工具箱3.
EXCEL软件的优化功能4.
SAS(统计分析)软件的优化功能5.
其他常用优化软件2.
LINDO公司的主要软件产品及功能简介LINDO公司软件产品简要介绍美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司(LINDOSystemsInc.
),网址:http://www.
lindo.
comLINDO:LinearINteractiveandDiscreteOptimizer(V6.
1)LINGO:LinearINteractiveGeneralOptimizer(V8.
0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.
0)What'sBest!
:(SpreadSheete.
g.
EXCEL)V7.
0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版…(求解问题规模和选件不同)LINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)LPQPNLPIP全局优化(选)ILPIQPINLPLINDO/LINGO软件的求解过程LINDO/LINGO预处理程序线性优化求解程序非线性优化求解程序分枝定界管理程序1.
确定常数2.
识别类型1.
单纯形算法2.
内点算法(选)1、顺序线性规划法(SLP)2、广义既约梯度法(GRG)(选)3、多点搜索(Multistart)(选)建模时需要注意的几个基本问题1、尽量使用实数优化,减少整数约束和整数变量2、尽量使用光滑优化,减少非光滑约束的个数如:尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等3、尽量使用线性模型,减少非线性约束和非线性变量的个数(如x/y"(或"="(或"=350;x1>=100;2*x1+x21;"#GT#"是逻辑运算符号,意思是"大于(GreaterThan的字首字母缩写)".
约束的定义方式问题的求解:运行菜单命令"LINGO|Solve"全局最优解RP=(40,40,40,25),OP=(0,10,35,0)最小成本=78450小结:LINGO模型最基本的组成要素一般来说,LINGO中建立的优化模型可以由五个部分组成,或称为五"段"(SECTION):(1)集合段(SETS):以"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的所有整数.
(2)目标与约束段:目标函数、约束条件等,没有段的开始和结束标记,因此实际上就是除其它四个段(都有明确的段标记)外的LINGO模型.
这里一般要用到LINGO的内部函数,尤其是与集合相关的求和函数@SUM和循环函数@FOR等.
上例中定义的目标函数与quarters的元素数目是4或1000并无具体的关系.
约束的表示也类似.
(3)数据段(DATA):以"DATA:"开始,"ENDDATA"结束,对集合的属性(数组)输入必要的常数数据.
格式为:"attribute(属性)=value_list(常数列表);"常数列表(value_list)中数据之间可以用逗号","分开,也可以用空格分开(回车等价于一个空格),如上面对DEM的赋值也可以写成"DEM=40607525;".
在LINGO模型中,如果想在运行时才对参数赋值,可以在数据段使用输入语句.
但这仅能用于对单个变量赋值,输入语句格式为:"变量名=;".
例如,上例中如果需要在求解模型时才给出初始库存量(记为A),则可以在模型中数据段写上语句:"A=;"在求解时LINDO系统给出提示界面,等待用户输入变量A的数值.
当然,此时的约束语句INV(1)=10+RP(1)+OP(1)-DEM(1);也应该改写成INV(1)=A+RP(1)+OP(1)-DEM(1);这样,模型就可以计算任意初始库存量(而不仅仅只能计算初始库存量为10)的情况了.
(4)初始段(INIT):以"INIT:"开始,"ENDINIT"结束,对集合的属性(数组)定义初值(因为求解算法一般是迭代算法,所以用户如果能给出一个比较好的迭代初值,对提高算法的计算效果是有益的).
如果有一个接近最优解的初值,对LINGO求解模型是有帮助的.
定义初值的格式为:"attribute(属性)=value_list(常数列表);"这与数据段中的用法是类似的.
上例中没有初始化部分,我们将在下一个例子中举例说明.
(5)计算段(CALC):以"CALC:"开始,"ENDCALC"结束,对一些原始数据进行计算处理.
在实际问题中,输入的数据通常是原始数据,不一定能在模型中直接使用,可以在这个段对这些原始数据进行一定的"预处理",得到模型中真正需要的数据.

例如上例,如果希望得到全年的总需求和季度平均需求,可以增加这个段:CALC:T_DEM=@SUM(quarters:DEM)总需求;A_DEM=T_DEM/@size(quarters);!
平均需求;ENDCALC在计算段中也可以使用集合函数(其中函数@size(quarters)表示集合quarters的元素个数,这里也就是4).
这时,变量T_DEM的值就是总需求,A_DEM的值就是平均需求(如果需要的话,这两个变量就可以在程序的其它地方作为常数使用了).
注:上面的两个语句不能交换顺序,因为计算A_DEM必须要用到T_DEM的值.
此外,在计算段中只能直接使用赋值语句,而不能包含需要经过解方程或经过求解优化问题以后才能决定的变量.

LINGO模型—例:选址问题某公司有6个建筑工地,位置坐标为(ai,bi)(单位:公里),水泥日用量di(单位:吨)假设:料场和工地之间有直线道路用例中数据计算,最优解为总吨公里数为136.
2线性规划模型决策变量:cij(料场j到工地i的运量)~12维2)改建两个新料场,需要确定新料场位置(xj,yj)和运量cij,在其它条件不变下使总吨公里数最小.
决策变量:cij,(xj,yj)~16维非线性规划模型选址问题:NLPLINGO模型的构成:4个段集合段(SETSENDSETS)数据段(DATAENDDATA)初始段(INITENDINIT)目标与约束段局部最优:89.
8835(吨公里)LP:移到数据段边界集合的类型集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法setname[/member_list/][:attribute_list];setname(parent_set_list)[/member_list/attribute_list];SETS:CITIES/A1,A2,A3,B1,B2/;ROADS(CITIES,CITIES)/A1,B1A1,B2A2,B1A3,B2/:D;ENDSETSSETS:STUDENTS/S1.
.
S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS集合元素的隐式列举OCT2001,NOV2001,DEC2001,JAN2002OCT2001.
.
JAN2002monthYearM.
.
monthYearN年份-月份型OCT,NOV,DEC,JANOCT.
.
JANmonthM.
.
monthN月份型MON,TUE,WED,THU,FRIMON.
.
FRIdayM.
.
dayN星期型Car101,car102,…,car208Car101.
.
car208stringM.
.
stringN字符-数字型1,2,3,4,51.
.
51.
.
n数字型示例集合的元素示例隐式列举格式类型运算符的优先级最低#AND##OR##EQ##NE##GT##GE##LT##LE#+—(减法)*/^#NOT#—(负号)最高运算符优先级三类运算符:算术运算符逻辑运算符关系运算符集合循环函数四个集合循环函数:FOR、SUM、MAX、MIN@function(setname[(set_index_list)[|condition]]:expression_list);[objective]MAX=@SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J));@FOR(STUDENTS(I):[constraints]@SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K))=1);@FOR(PAIRS(I,J):@BIN(MATCH(I,J)));MAXB=@MAX(PAIRS(I,J):BENEFIT(I,J));MINB=@MIN(PAIRS(I,J):BENEFIT(I,J));Example:状态窗口SolverType:B-and-BGlobalMultistartModelClass:LP,QP,ILP,IQP,PILP,PIQP,NLP,INLP,PINLPState:GlobalOptimumLocalOptimumFeasibleInfeasibleUnboundedInterruptedUndetermined7个选项卡(可设置80-90个控制参数)程序与数据分离文本文件使用外部数据文件Cut(orCopy)–Paste方法@FILE输入数据、@TEXT输出数据(文本文件)@OLE函数与电子表格软件(如EXCEL)连接@ODBC函数与数据库连接LINGO命令脚本文件LG4(LONGO模型文件)LNG(LONGO模型文件)LTF(LONGO脚本文件)LDT(LONGO数据文件)LRP(LONGO报告文件)常用文件后缀@FILE和@TEXT:文本文件输入输出MODEL:SETS:MYSET/@FILE('myfile.
txt')/:@FILE('myfile.
txt');ENDSETSMIN=@SUM(MYSET(I)SHIP(I)*COST(I));@FOR(MYSET(I)CON1]SHIP(I)>NEED(I)CON2]SHIP(I)NEED(I)CON2]SHIP(I)xls','CITIES');COST,NEED,SUPPLY=@OLE(mydata.
xls);@OLE(mydata.
xls,'SOLUTION')=SHIP;ENDDATAENDmydata.
xls文件中必须有下列名称(及数据):CITIES,COST,NEED,SUPPLY,SOLUTION在EXCEL中还可以通过"宏"自动调用LINGO(略)也可以将EXCEL表格嵌入到LINGO模型中(略)演示MydataExample.
lg4@ODBC:与数据库连接输入基本集合元素:setname/@ODBC(['datasource'[,'tablename'[,'columnname']]])/输入派生集合元素:setname/@ODBC(['source'[,'table'[,'column1'[,'column2'…]]]])/目前支持下列DBMS:(如为其他数据库,则需自行安装驱动)ACCESS,DBASE,EXCEL,FOXPRO,ORACLE,PARADOX,SQLSERVER,TEXEFILES使用数据库之前,数据源需要在ODBC管理器注册输入数据:Attr_list=@ODBC(['source'[,'table'[,'column1'[,'column2'…]]]])输出数据:@ODBC(['source'[,'table'[,'column1'[,'column2'Attr_list具体例子略还能干什么走近Lingo求解非线性方程组Lingo上机作业1、熟悉Lingo的安装2、简单熟悉Lingo的语法规范,并可以解题算例:某玻璃制造厂与三个不同地点的纯碱供应商签订合同,由他们供货给三个分厂,条件是不超过合同所定的数量,但必须满足生产需要.
该问题如表3-1所示.
问题中所给费率是每个供应商到每个工厂之间最短路径的运输费率.
求运输方案2Lingo上机作业工厂1工厂2工厂3供应量供应商1x11x12x13400供应商2x21x22x23700供应商3x31x32x33500需求量6005005003-1运输问题-供需情况供销平衡2Lingo上机作业工厂1工厂2工厂3供应商1476供应商2314供应商39583-1运输问题-运输成本2Lingo上机作业利用集的概念构造相应的Lingo模型并求解4.
建模与求解实例(结合软件使用)建模实例与求解最短路问题下料问题飞机定位露天矿的运输问题钢管运输问题电力市场的堵塞管理求各点到T的最短路56774968658336C1B1C2B2A1A2A3TS6例最短路问题STA1A2A3B1B2C1C2633665874678956分析假设从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)只有唯一的道路)分析STA1A2A3B1B2C1C2633665874678956此例中可把从S到T的行驶过程分成4个阶段,即S→Ai(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的最优行驶路线的路长:本例的计算STA1A2A3B1B2C1C2633665874678956所以,从S到T的最优行驶路线的路长为20.
进一步分析以上求解过程,可以得到从S到T的最优行驶路线为S→A3→B2→C1→T.
这种计算方法在数学上称为动态规划(DynamicProgramming)本例的LINGO求解"CITIES"(城市):一个基本集合(元素通过枚举给出)L:CITIES对应的属性变量(我们要求的最短路长)"ROADS"(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连,所以不应该把它定义成稠密集合,将其元素通过枚举给出,这就是一个稀疏集合.

D:稀疏集合ROADS对应的属性变量(给定的距离)本例的LINGO求解从模型中还可以看出:这个LINGO程序可以没有目标函数,这在LINGO中,可以用来找可行解(解方程组和不等式组).
在数据段对L进行赋值,只有L(S)=0已知,后面的值为空(但位置必须留出来,即逗号","一个也不能少,否则会出错).
如果这个语句直接写成"L=0;",语法上看也是对的,但其含义是L所有元素的取值全部为0,所以也会与题意不符.

本例的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中的索引值.
本例的LINGO求解结果从S到T的最优行驶路线的路长为20(进一步分析,可以得到最优行驶路线为S→A3→B2→C1→T).
本例中定义稀疏集合ROADS的方法是将其元素通过枚举给出,有时如果元素比较多,用起来不方便.
另一种定义稀疏集合的方法是"元素过滤"法,能够从笛卡儿积中系统地过滤下来一些真正的元素.

问题1.
如何下料最节省问题2.
客户增加需求:原料钢管:每根19米4米50根6米20根8米15根客户需求节省的标准是什么由于采用不同切割模式太多,会增加生产和管理成本,规定切割模式不能超过3种.
如何下料最节省5米10根例钢管下料按照客户需要在一根原料钢管上安排切割的一种组合.
切割模式余料1米4米1根6米1根8米1根余料3米4米1根6米1根6米1根合理切割模式的余料应小于客户需要钢管的最小尺寸余料3米8米1根8米1根钢管下料为满足客户需要,按照哪些种合理模式,每种模式切割多少根原料钢管,最为节省合理切割模式2.
所用原料钢管总根数最少模式4米钢管根数6米钢管根数8米钢管根数余料(米)14003231013201341203511116030170023钢管下料问题1两种标准1.
原料钢管剩余总余量最小xi~按第i种模式切割的原料钢管根数(i=1,2,…7)约束满足需求决策变量目标1(总余量)按模式2切割12根,按模式5切割15根,余料27米模式4米根数6米根数8米根数余料14003231013201341203511116030170023需求502015最优解:x2=12,x5=15,其余为0;最优值:27整数约束:xi为整数当余料没有用处时,通常以总根数最少为目标目标2(总根数)钢管下料问题1约束条件不变最优解:x2=15,x5=5,x7=5,其余为0;最优值:25.
xi为整数按模式2切割15根,按模式5切割5根,按模式7切割5根,共25根,余料35米虽余料增加8米,但减少了2根与目标1的结果"共切割27根,余料27米"相比钢管下料问题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米长的钢管的数量满足需求模式合理:每根余料不超过3米整数非线性规划模型钢管下料问题2目标函数(总根数)约束条件整数约束:xi,r1i,r2i,r3i,r4i(i=1,2,3)为整数增加约束,缩小可行域,便于求解原料钢管总根数下界:特殊生产计划:对每根原料钢管模式1:切割成4根4米钢管,需13根;模式2:切割成1根5米和2根6米钢管,需10根;模式3:切割成2根8米钢管,需8根.
原料钢管总根数上界:31模式排列顺序可任定钢管下料问题2需求:4米50根,5米10根,6米20根,8米15根每根原料钢管长19米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根.

演示cut02a.
lg4;cut02b.
lg40yxVOR2x=629,y=375309.
00(1.
30)864.
3(2.
0)飞机x=,y=VOR1x=764,y=1393161.
20(0.
80)VOR3x=1571,y=25945.
10(0.
60)北DMEx=155,y=987飞机与监控台(图中坐标和测量距离的单位是"公里")例飞机精确定位问题飞机精确定位模型2.
0(km)d4=864.
3(km)987155DME1.
30(0.
0227弧度)309.
00(5.
39307弧度)2591571VOR30.
60(0.
0105弧度)45.
10(0.
78714弧度)375629VOR20.
80(0.
0140弧度)161.
20(2.
81347弧度)1393746VOR1原始的(或d4)yixi飞机精确定位模型第1类模型:不考虑误差因素超定方程组,非线性最小二乘!
量纲不符!
飞机精确定位模型第2类模型:考虑误差因素(作为硬约束)Minx;Miny;Maxx;Maxy.
以距离为约束,优化角度误差之和(或平方和);或以角度为约束,优化距离误差.
非线性规划仅部分考虑误差!
角度与距离的"地位"不应不同!
有人也可能会采用其他目标,如:误差非均匀分布!
飞机精确定位模型误差一般服从什么分布正态分布!
不同的量纲如何处理无约束非线性最小二乘模型归一化处理!
shili0702.
m飞机坐标(978.
31,723.
98),误差平方和0.
6685(<<4)角度需要进行预处理,如利用Matlab的atan2函数,值域(-pi,pi)第3类模型:考虑误差因素(作为软约束);且归一化飞机精确定位模型小技巧:LINGO中没有atan2函数,怎么办可以直接利用@tan函数!
exam0507c.
lg4同前面的模型/结果飞机坐标(980.
21,727.
30),误差平方和2.
6与前面的结果有所不同,为什么哪个模型合理些最后:思考以下模型:exam0507d.
lg4露天矿里铲位已分成矿石和岩石:平均铁含量不低于25%的为矿石,否则为岩石.
每个铲位的矿石、岩石数量,以及矿石的平均铁含量(称为品位)都是已知的.
每个铲位至多安置一台电铲,电铲平均装车时间5分钟卡车在等待时所耗费的能量也是相当可观的,原则上在安排时不应发生卡车等待的情况.
矿石卸点需要的铁含量要求都为29.
5%1%(品位限制),搭配量在一个班次(8小时)内满足品位限制即可.
卸点在一个班次内不变.
卡车载重量为154吨,平均时速28km,平均卸车时间为3分钟.

问题:出动几台电铲,分别在哪些铲位上;出动几辆卡车,分别在哪些路线上各运输多少次例露天矿生产的车辆安排(CUMCM-2003B)平面示意图问题数据0.
501.
271.
620.
782.
812.
253.
163.
723.
864.
42倒装Ⅱ6.
105.
053.
724.
212.
602.
741.
831.
271.
760.
64岩石漏0.
571.
062.
462.
463.
653.
514.
565.
615.
615.
89岩场3.
513.
092.
041.
482.
251.
271.
131.
900.
991.
90倒装Ⅰ1.
270.
641.
902.
462.
742.
954.
004.
215.
195.
26矿石漏铲位10铲位9铲位8铲位7铲位6铲位5铲位4铲位3铲位2铲位1距离31%33%31%32%33%31%32%29%28%30%铁含量1.
251.
351.
151.
051.
351.
151.
051.
351.
101.
25岩石量1.
251.
351.
301.
051.
251.
101.
051.
001.
050.
95矿石量铲位10铲位9铲位8铲位7铲位6铲位5铲位4铲位3铲位2铲位1问题分析与典型的运输问题明显有以下不同:这是运输矿石与岩石两种物资的问题;属于产量大于销量的不平衡运输问题;为了完成品位约束,矿石要搭配运输;产地、销地均有单位时间的流量限制;运输车辆只有一种,每次满载运输,154吨/车次;铲位数多于铲车数意味着要最优的选择不多于7个产地作为最后结果中的产地;最后求出各条路线上的派出车辆数及安排.

近似处理:先求出产位、卸点每条线路上的运输量(MIP模型)然后求出各条路线上的派出车辆数及安排如理解为严格不等待,难以用数学规划模型来解模型假设卡车在一个班次中不应发生等待或熄火后再启动的情况;在铲位或卸点处由两条路线以上造成的冲突问题面前,我们认为只要平均时间能完成任务,就认为不冲突.
我们不排时地进行讨论;空载与重载的速度都是28km/h,耗油相差很大;卡车可提前退出系统,等等.