Lingo和Lindo.ppt

1、lifengbing,2007-4-16,1,优化建模与LINDO/LINGO软件介绍,单位: 桂林电子科技大学 数学与计算科学学院,制作人: 李丰兵,Lfb_,lifengbing,2007-4-16,2,简 要 提 纲,优化模型简介 优化问题与LINGO/LINDO软件 LINGO建模与求解实例（结合软件介绍） LINGO软件语法简介 LINGO建模注意事项,lifengbing,2007-4-16,3,优化模型简介,优化模型的一般形式如下:,Max（或 Min） z=f(x) , x=(x1, x2 , , xn)T s.t. gi(x)=0, i= 1, 2, , m hj(x)=0,

2、 j= m, m+1, , n,x 决策变量 f(x) 目标函数 gi(x) ,hj(x) 约束条件,lifengbing,2007-4-16,4,优 化 模 型 分 类,0-1 整数规划（ZOP）,纯整数规划（PIP）,混合整数规划（MIP）,当然还有其它规划,如: 随机规划,模糊规划 ,不确定规划, 半定规划 等等!,lifengbing,2007-4-16,5,优化问题与LINGO/LINDO软件,LINGO,LINDO,优化模型,线性规划 (LP),非线性规划 (NLP),二次规划 (QP),连续优化,整数规划(IP),lifengbing,2007-4-16,6,LP QP NLP

3、IP 全局优化(选) ILP IQP INLP,LINDO/LINGO软件的求解过程,LINDO/LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1. 确定常数 2. 识别类型,1. 单纯形算法 2. 内点算法(选),1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选),lifengbing,2007-4-16,7,编写Lingo模型时要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍

4、五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103),lifengbing,2007-4-16,8,需要掌握的几个重要方面,掌握集合(SETS)的应用； 正确阅读求解报告（尤其要掌握敏感性分析） 正确理解求解状态窗口； 学会设置基本的求解选项(OPTIONS) ； 掌握与外部文件的基本接口方法,lifengbing,2007-4-16,9,LINGO建模与求解实例,例 1,model: max=2*x1-3*x2-2*x3+x4; x1-2*x2-

5、3*x3-2*x4=5; x1-x2+2*x3+x4=10; End DEMO,lifengbing,2007-4-16,10,Global optimal solution found at iteration: 2 Objective value: 18.33333 Variable Value Reduced Cost X1 8.333333 0.000000 X2 0.000000 0.6666667 X3 0.000000 4.333333 X4 1.666667 0.000000 Row Slack or Surplus Dual Price 1 18.33333 1.000000

6、 2 0.000000 0.3333333 3 0.000000 1.666667,运行结果如下:,演示,lifengbing,2007-4-16,11,看完例1后,能解下面这个问题吗?,例 2,演示,lifengbing,2007-4-16,12,例 3,model: !this is an integer programming problem; max=4*x1+3*x2; 4*x1+x2=10; 2*x1+3*x2=8; gin(x1); gin(x2); end,lifengbing,2007-4-16,13,Global optimal solution found at iter

7、ation: 0 Objective value: 11.00000 Variable Value Reduced Cost X1 2.000000 -4.000000 X2 1.000000 -3.000000 Row Slack or Surplus Dual Price 1 11.00000 1.000000 2 1.000000 0.000000 3 1.000000 0.000000,运行结果如下:,演示,lifengbing,2007-4-16,14,例 4,model: !this is an uncontrained optimal problem; min=3/2*x12+1

8、/2*x22-x1*x2-2*x1; free(x1); free(x2); end,lifengbing,2007-4-16,15,Local optimal solution found at iteration: 73 Objective value: -1.000000 Variable Value Reduced Cost X1 0.9999995 0.000000 X2 0.9999992 0.000000 Row Slack or Surplus Dual Price 1 -1.000000 -1.000000,运行结果如下:,演示,lifengbing,2007-4-16,16

9、,例 5,model: init: x1=1; x2=1; endinit min=x12+2*x22-2*x1*x2-4*x1; free(x1); free(x2); end,初始值为:,lifengbing,2007-4-16,17,Local optimal solution found at iteration: 60 Objective value: -8.000000 Variable Value Reduced Cost X1 3.999997 0.000000 X2 1.999998 0.000000 Row Slack or Surplus Dual Price 1 -8.

10、000000 -1.000000,运行结果如下:,演示,lifengbing,2007-4-16,18,例 6,model: min=-3*x12-x22-2*x32; x12+x22+x32-3=0; -x1+x2=0; end,lifengbing,2007-4-16,19,Local optimal solution found at iteration: 37 Objective value: -6.000000 Variable Value Reduced Cost X1 1.212809 0.000000 X2 1.212809 0.000000 X3 0.2412201 0.00

11、0000 Row Slack or Surplus Dual Price 1 -6.000000 -1.000000 2 0.000000 2.000000 3 0.000000 -2.425619,运行结果如下:,演示,lifengbing,2007-4-16,20,例 7,model: min=2*x12+2*x22-2*x1*x2-4*x1-6*x2; 2-x1-x2=0; 5-x1-5*x20; end,lifengbing,2007-4-16,21,Local optimal solution found at iteration: 33 Objective value: -7.16

12、1290 Variable Value Reduced Cost X1 1.129032 0.8823973E-07 X2 0.7741936 0.000000 Row Slack or Surplus Dual Price 1 -7.161290 -1.000000 2 0.9677434E-01 0.000000 3 0.000000 -1.032258,运行结果如下:,演示,lifengbing,2007-4-16,22,例 8,model: max=98*x1+277*x2-x12-0.3*x1*x2-2*x22; x1+x2100; x12*x2; gin(x1); gin(x2);

13、 end,lifengbing,2007-4-16,23,Local optimal solution found at iteration: 202 Objective value: 11077.50 Variable Value Reduced Cost X1 35.00000 -1.999947 X2 65.00000 0.000000 Row Slack or Surplus Dual Price 1 11077.50 1.000000 2 0.000000 6.500069 3 95.00000 0.000000,运行结果如下:,演示,lifengbing,2007-4-16,24,

14、例 9,model: sets: I/1,2,3,4/:c,a1,a2,x; !相当于定义c,a1,a2,x均为一维数组,含4个元素; endsets data: c=2,-3,-2,1; !给数组C赋值; a1=1,-2,-3,-2; a2=1,-1,2,1; enddata max=sum(I:c*x); sum(I:a1*x)=5; sum(I:a2*x)=10; end,lifengbing,2007-4-16,25,Global optimal solution found at iteration: 2 Objective value: 18.33333 Variable Valu

15、e Reduced Cost C( 1) 2.000000 0.000000 C( 2) -3.000000 0.000000 C( 3) -2.000000 0.000000 C( 4) 1.000000 0.000000 A1( 1) 1.000000 0.000000 A1( 2) -2.000000 0.000000 A1( 3) -3.000000 0.000000 A1( 4) -2.000000 0.000000 A2( 1) 1.000000 0.000000 A2( 2) -1.000000 0.000000 A2( 3) 2.000000 0.000000 A2( 4) 1

16、.000000 0.000000 X( 1) 8.333333 0.000000 X( 2) 0.000000 0.6666667 X( 3) 0.000000 4.333333 X( 4) 1.666667 0.000000 Row Slack or Surplus Dual Price 1 18.33333 1.000000 2 0.000000 0.3333333 3 0.000000 1.666667,lifengbing,2007-4-16,26,也可以单独显示变量,如 x=(x1,x2,x3,x4),Variable Value Reduced Cost X( 1) 8.33333

17、3 0.000000 X( 2) 0.000000 0.6666667 X( 3) 0.000000 4.333333 X( 4) 1.666667 0.000000,lifengbing,2007-4-16,27,还可以也图形形式显示变量,如显示x=(x1,x2,x3,x4),演示,lifengbing,2007-4-16,28,例10-(1),看看哪些变量是未知数?,lifengbing,2007-4-16,29,MODEL: TITLE LOCATION PROBLEM; SETS: s1/1.6/:A,B,D; s2/1,2/:X,Y,E; s3(s1,S2):C; ENDSETS D

18、ATA: A=1.25 8.75 0.5 5.75 3 7.25; B=1.25 0.75 4.75 5 6.5 7.75; D=3 5 4 7 6 11; E=20 20; ENDDATA OBJ MIN=SUM(s3(I,J):C(I,J)*(X(J)-A(I)2+(Y(J)-B(I)2)(1/2); FOR(s1(I):DEMAND_CON SUM(S2(J): C(I,J)=D(I);); FOR(S2(I): SUPPLY_CON SUM(s1(J):C(J,I)E(I);); FOR(S2:FREE(X); FREE(Y); END,lifengbing,2007-4-16,30,

19、测试,目标函数和未知变量的最优结果如下,Local optimal solution found at iteration: 14 Objective value: 89.88350 X( 1) 7.249997 0.3920238E-08 X( 2) 5.695940 0.000000 Y( 1) 7.749998 0.8434833E-07 Y( 2) 4.928524 0.000000 E( 1) 20.00000 0.000000 E( 2) 20.00000 0.000000 C( 1, 1) 0.000000 1.765974 C( 1, 2) 3.000000 0.000000

20、C( 2, 1) 0.000000 0.6737687 C( 2, 2) 5.000000 0.000000 C( 3, 1) 0.000000 0.8781433 C( 3, 2) 4.000000 0.000000 C( 4, 1) 0.000000 1.733379 C( 4, 2) 7.000000 0.000000 C( 5, 1) 5.000000 0.000000 C( 5, 2) 1.000000 0.000000 C( 6, 1) 11.00000 0.000000 C( 6, 2) 0.000000 4.530640,lifengbing,2007-4-16,31,已知,例

21、10-(2),lifengbing,2007-4-16,32,MODEL: TITLE LOCATION PROBLEM; SETS: s1/1.6/:A,B,D; s2/1,2/:X,Y,E; s3(s1,S2):C; ENDSETS DATA: A=1.25 8.75 0.5 5.75 3 7.25; B=1.25 0.75 4.75 5 6.5 7.75; D=3 5 4 7 6 11; E=20 20; ENDDATA INIT: X=5 2; Y=1, 7; ENDINIT OBJ MIN=SUM(s3(I,J):C(I,J)*(X(J)-A(I)2+(Y(J)-B(I)2)(1/2

22、); FOR(s1(I):DEMAND_CON SUM(S2(J): C(I,J)=D(I);); FOR(S2(I): SUPPLY_CON SUM(s1(J):C(J,I)E(I);); !FOR(S2:FREE(X), FREE(Y); FOR(S2: BND(0.5,X,8.75); BND(0.75,Y,7.75);); END,测试,lifengbing,2007-4-16,33,目标函数和未知变量的最优结果如下,Local optimal solution found at iteration: 8 Objective value: 89.88349 Variable Value

23、 Reduced Cost X( 1) 5.695940 0.000000 X( 2) 7.249997 0.000000 Y( 1) 4.928524 0.000000 Y( 2) 7.750000 -4.451556 E( 1) 20.00000 0.000000 E( 2) 20.00000 0.000000 C( 1, 1) 3.000000 0.000000 C( 1, 2) 0.000000 1.765974 C( 2, 1) 5.000000 0.000000 C( 2, 2) 0.000000 0.6737694 C( 3, 1) 4.000000 0.000000 C( 3,

24、 2) 0.000000 0.8781434 C( 4, 1) 7.000000 0.000000 C( 4, 2) 0.000000 1.733380 C( 5, 1) 1.000000 0.000000 C( 5, 2) 5.000000 0.000000 C( 6, 1) 0.000000 4.530643 C( 6, 2) 11.00000 0.00000,lifengbing,2007-4-16,34,模型2目标函数最优值要比模型1的目标函数最优值好 模型2迭代次数比模型1少 模型2的运行时间比模型1少 未知变量的求解结果可能不相同,例10的两个模型对比,lifengbing,200

25、7-4-16,35,求各点到T的最短路,例 11 最短路问题,最短路径上任意两点之间的路径都是最短路径,建模与求解实例,lifengbing,2007-4-16,36,数学模型如下:,lifengbing,2007-4-16,37,model: sets: I1/s,a1,a2,a3,b1,b2,c1,c2,t/:L; I2(I1,I1)/ s,a1, s,a2, s,a3 a1,b1 a1,b2, a2,b1 a2,b2, a3,b1 a3,b2 b1,c1 b1,c2 b2,c1 b2,c2 c1,t c2,t/:D endsets data: D=6 3 3 6 5 8 6 7 4 6

26、7 8 9 5 6; L=0,; enddata for(I1(i)|i#GT#index(s): L(i)=min(I2(j,i):L(j)+D(j,i);); end,lifengbing,2007-4-16,38,部分变量结果如下,Feasible solution found at iteration: 0 Variable Value L( S) 0.000000 L( A1) 6.000000 L( A2) 3.000000 L( A3) 3.000000 L( B1) 10.00000 L( B2) 7.000000 L( C1) 15.00000 L( C2) 16.00000

27、 L( T) 20.00000,测试,lifengbing,2007-4-16,39,LINGO软件语法简介,目标与约束段 集合段（SETS ENDSETS） 数据段（DATA ENDDATA） 初始段（INIT ENDINIT）,1 LINGO模型的构成：4个段,lifengbing,2007-4-16,40,例 12,x-y=2; x+y=10;,lifengbing,2007-4-16,41,Feasible solution found at iteration: 0 Variable Value X 6.000000 Y 4.000000 Row Slack or Surplus 1

28、 0.000000 2 0.000000,lifengbing,2007-4-16,42,2 集合的类型,集合 派生集合 基本集合 稀疏集合 稠密集合 元素列表法 元素过滤法 直接列举法 隐式列举法,setname /member_list/ : attribute_list;,setname(parent_set_list) /member_list/ : attribute_list;,SETS: CITIES /A1,A2,A3,B1,B2/; ROADS(CITIES, CITIES)/ A1,B1 A1,B2 A2,B1 A3,B2/:D; ENDSETS,SETS: STUDENT

29、S /S1.S8/; PAIRS( STUDENTS, STUDENTS) | ENDSETS,lifengbing,2007-4-16,43,3 集合元素的隐式列举,lifengbing,2007-4-16,44,4 运算符的优先级,三类运算符：算术运算符, 逻辑运算符, 关系运算符,lifengbing,2007-4-16,45,5 集合循环函数,四个集合循环函数：FOR、SUM 、 MAX、MIN function( setname ( set_index_list) | condition : expression_list);,objective MAX = SUM( PAIRS(

30、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:,lifengbing,2007-4-16,46,6 变量定界函数,bin(x) 限制x为0或

31、1 gin(x) 限制x为整数 bnd(L,x,U) 限制LxU free(x) 取消对变量x的默认下界为0的限制，即x可以取任意实数 在默认情况下，LINGO规定变量是非负的，也就是说下界为0，上界为+。free取消了默认的下界为0的限制，使变量也可以取负值。bnd用于设定一个变量的上下界,它也可以取消默认下界为0的约束。,lifengbing,2007-4-16,47,7 状态窗口,Solver Type: B-and-B Global Multistart,Model Class: LP， QP，ILP， IQP，PILP, PIQP，NLP，INLP，PINLP,State: Glob

32、al Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined,lifengbing,2007-4-16,48,8 选项卡的设置(可设置80-90个控制参数),lifengbing,2007-4-16,49,程序与数据分离,文 本 文 件,9 使用外部数据文件,Cut (or Copy) Paste 方法 FILE 输入数据、TEXT输出数据（文本文件） OLE函数与电子表格软件（如EXCEL）连接 ODBC函数与数据库连接 LINGO命令脚本文件,LG4 （LONGO模型文件） LNG （LONG

33、O模型文件） LTF （LONGO脚本文件） LDT （LONGO数据文件） LRP （LONGO报告文件）,常用文件后缀,lifengbing,2007-4-16,50,FILE和TEXT：文本文件输入输出,MODEL: SETS: MYSET / FILE(myfile.txt) / : FILE(myfile.txt); ENDSETS MIN = SUM( MYSET( I): SHIP( I) * COST( I); FOR( MYSET( I): CON1 SHIP( I) NEED( I); CON2 SHIP( I) SUPPLY( I); DATA: COST = FILE(

34、myfile.txt); NEED = FILE(myfile.txt); SUPPLY = FILE(myfile.txt); TEXT(result.txt)=SHIP, DUAL(SHIP), DUAL(CON1); ENDDATA END,myfile.txt文件 的内容、格式： Seattle,Detroit,Chicago,Denver COST,NEED,SUPPLY,SHIP 12,28,15,20 1600,1800,1200,1000 1700,1900,1300,1100,演示 MyfileExample.lg4,lifengbing,2007-4-16,51,注意事项,一 每次运行结果未别相同,例:把T=10