优化软件 LinGo的使用
1,优化模型与优化软件简介最优化是工程技术、经济管理、科学研究、
社会生活中经常遇到的问题,如,
优化模型和优化软件的重要意义结构设计 资源分配 生产计划 运输方案解决优化问题的手段
经验积累，主观判断
作试验，比优劣
建立数学模型 (优化模型 )，求最优策略 (决策 )
(最 )优化,在一定条件下,寻求使目标最大 (小 )的决策
CUMCM赛题：约一半以上与优化有关，需用软件求解运筹学 (OR,Operations/Operational Research)
管理科学 (MS,Management Science)
决策科学 (DS,Decision Science)
(最 )优化理论是运筹学的基本内容无约束优化
OR/
MS/
DS
优化 (Optimization),规划 (Programming)
线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划优化问题三要素,决策变量 ； 目标函数 ； 约束条件约束条件决策变量优化问题的一般形式
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
可行解（满足约束）与可行域（可行解的集合）
最优解（取到最小／大值的可行解）
目标函数无约束优化,最优解的分类和条件
)( xfM inx
给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即
nTnxxxx ),,,( 21?其中局部最优解 全局最优解必要条件 0),,()(
1
* Txx
nffxf?
充分条件 0)(,0)( *2* xfxf
Hessian阵
nnji
xx
ff
22
最优解在可行域边界上取得时不能用无约束优化方法求解
x*
f(x) xl
xgo
约束优化的简单分类
线性规划 (LP) 目标和约束均为线性函数
非线性规划 (NLP) 目标或约束中存在非线性函数
二次规划 (QP) 目标为二次函数、约束为线性
整数规划 (IP) 决策变量 (全部或部分 )为整数
整数 线性 规划 (ILP)，整数 非线性 规划 (INLP)
纯整数规划 (PIP),混合整数规划 (MIP)
一般整数规划,0-1（整数）规划
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
连续优化离散优化数学规划常用优化软件
1,LINDO/LINGO软件
2,MATLAB优化工具箱
3,EXCEL软件的优化功能
4,SAS(统计分析 )软件的优化功能
5,其它
MATLAB优化工具箱 能求解的优化模型优化工具箱 3.0 (MATLAB 7.0 R14)
连续优化 离散优化无约束优化非线性极小
fminunc
非光滑 (不可微 )优化
fminsearch
非线性方程 (组 )
fzero
fsolve
全局优化暂缺非线性最小二乘
lsqnonlin
lsqcurvefit
线性规划
linprog
纯 0-1规划 bintprog
一般 IP(暂缺 )
非线性规划
fmincon
fminimax
fgoalattain
fseminf
上下界约束
fminbnd
fmincon
lsqnonlin
lsqcurvefit
约束线性最小二乘
lsqnonneg
lsqlin
约束优化二次规划
quadprog
2,LINDO公司的主要软件产品及功能简介
LINDO 公司软件产品简要介绍美国芝加哥 (Chicago)大学的 Linus Schrage教授于 1980
年前后开发,后来成立 LINDO系统公司（ LINDO
Systems Inc.）,网址,http://www.lindo.com
LINDO,Linear INteractive and Discrete Optimizer (V6.1)
LINGO,Linear INteractive General Optimizer (V9.0)
LINDO API,LINDO Application Programming Interface (V3.0)
What’s Best!,(SpreadSheet e.g,EXCEL) (V8.0)
演 示 (试用 )版、学生版、高级版、超级版、工业版、
扩展版 … （求解 问题规模 和 选件 不同）
LINDO和 LINGO软件能求解的优化模型
LINGOLINDO
优化模型线性规划
(LP)
非线性规划
(NLP)
二次规划
(QP)
连续优化 整数规划 (IP)
LP QP NLP IP 全局优化 (选 )
ILP IQP INLP
LINDO/LINGO软件的求解过程
LINDO/LINGO预处理程序线性优化求解程序 非线性优化求解程序分枝定界管理程序
1,确定常数
2,识别类型
1,单纯形算法
2,内点算法 (选 )
1、顺序线性规划法 (SLP)
2、广义既约梯度法 (GRG) (选 )
3、多点搜索 (Multistart) (选 )
建模时需要注意的几个基本问题
1,尽量使用实数优化，减少整数约束和整数变量
2,尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大 /最小值、四舍五入、取整函数等
3,尽量使用线性模型，减少非线性约束和非线性变量的个数 （如 x/y <5 改为 x<5y）
4,合理设定变量上下界，尽可能给出变量初始值
5,模型中使用的参数数量级要适当 (如小于 103)
3,LINGO软件的使用简介界面帮助界面模型
min或 max f(x)
S.T,G(x)≤或 ≥或＝ 0
L ≤x≤U 要素,
1.变量 (符号 )
2.常量 （数据）
3.关系 （函数、方程）
需要掌握的几个重要方面
LINGO：
掌握集合 (SETS)的应用；
正确阅读求解报告；
正确理解求解状态窗口；
学会设置基本的求解选项 (OPTIONS) ；
掌握与外部文件的基本接口方法
LINGO软件简介
目标与约束段
集合段（ SETS ENDSETS）
数据段（ DATA ENDDATA）
初始段（ INIT ENDINIT）
计算段 (CALC ENDCALC) - LINGO9.0
LINGO模型的构成,5个段
LINGO模型的优点
包含了 LINDO的全部功能
提供了灵活的编程语言（矩阵生成器）
实例变量声明区数据赋值区关系表示区模型变量
数学表示：
LinGo表示：
{ },,{ 1,,}ix x i I I n其 中
1.单下标变量
SI/1..n/,x；
变量
数学表示：
LinGo表示：
{ },,
{ 1,,} = { 1,,}
ijx x i I j J
I n J m
，
其 中,
2.多下标变量
I/1..n/；
J/1..m/；
IJ(I,J),x；
变量取值限制
@BND(下限,变量或分量,上限 )； 默认下限为 0
@FREE(变量或分量 ) ；
@GIN(变量或分量 )；
限制变量或分量为整数
@BIN( 变量或分量 ) ；
限制变量或分量为 0,1
通常与 @for联用
@for(I,@bin(x))；
0 1,ix i I?取 或数学函数
@ABS(X)
@COS(X)
@EXP(X)
@LOG(X)
@SIN(X)
@TAN(X)
@SMAX(X1,X2,...,XN)
@SMIN(X1,X2,...,XN)
@FLOOR(X) integer function
@LGM(X) gamma function
@SIGN(X) sign function
条件和逻辑运算符
#EQ# ＝
#NE# ≠
#GT# ＞
#GE# ≥
#LT# ＜
#LE# ≤
#AND# 与
#OR# 或
#NOT# 非
@IF(条件表达式,
真值,否值 )
条件函数
XCOST = @IF( x #GT# 0,100,0) + 2 * x;
@IF(条件表达式,真值,否值 )
特殊符号
！ 段落注释符； 段落结束符
[ ] 方程注释符
1 0 0 + 2,0
X C O ST =
2,
xx
x
其 他集合函数
数学表示：
LinGo表示：
1
2,( )
k
i
ai
2.@SUM( SI( i) | i #LE# k,a( i));
1.@SUM( SI,a);
SI/1..n/,a；
1
1,( )
n
i
ai
集合函数特征
@函数 ( 下标集 [ (下标变量 ) [ |条件表达式 ]],变量表达式 );
@SUM( SI( i) | i #LE# k,a( i));
重要的集合函数
@FOR
@SUM
@MIN
@MAX
@FOR（ SI(i)|i#NE#3,x(i)<=100） ;
1 0 0,,3 ;ix i I i
例题 1
数学模型：
min
s.t.
34
11
ij ij
ij
cx
3
1
,1 4ij j
i
x x l j
4
1
,1 3i j i
j
x c l i
0,1 3,1 4ijx i j
其中,
xl＝ 5 2 4 6
cl= 4 9 4
c = 10 6 7 12
16 10 5 9
5 4 10 10
分析：
下标变量有：
1,xl 4个分量
2,cl 3个分量
3,x,c 3× 4个分量
下标集：
si 1,?,3
sj 1,?,4
sij ＝（ si,sj）
1.下标变量
si/1..3/:cl;
sj/1..4/:xl;
sij(si,sj):c,x;
lingo建模,
min @sum(si(i),
@sum(sj(j),c(i,j)*x(i,j))
） ;
lingo建模
2.目标函数
34
11
ij ij
ij
cx
,
ij ij
ij
cx?或
min @sum(sij:c*x);
min
简写 @sum(sij(i,j):c(i,j)*x(i,j));
2.约束条件：
3
1
,1 4ij j
i
x x l j
4
1
,1 3i j i
j
x c l i
3
1
ij j
i
x x l
14j?
@for(sj(j):等式 );
@for(si(i):@sum(sj(j)):x(i,j))=cl(i));
0,1 3,1 4ijx i j
默认
@sum(si(i):x(i))=xl(j)
完整模型：
model:
sets:
si/1..3/:cl;
sj/1..4/:xl;
sij(si,sj):c,x;
endsets
！ 数据设置 ；
data:
xl= 5 2 4 6;
cl= 4 9 4;
c = 10 6 7 12
16 10 5 9
5 4 10 10;
enddata
[obj] min = @sum( sij,c*x);
@for( sj(j),
[eq1] @sum( si(i),x(i,j)) = xl(j));
@for( si(i):
[eq2] @sum( sj(j),x(i,j)) = cl(i));
end
模型求解最优非零解灵敏度分析例题 2
数学模型,2000,B
min
s.t.
7 1 5 1 5
1 1 1
0,5 [ ( 1 ) ( 1 ) ]i j i j j j j j
i j j
c x y y z z
15
1
5 0 0,1 7i i j i i
j
t x s t i
7
1
,1 1 5ij j j
i
x y z j
,,0,0 1 ; 1 7,1 1 5i j j j ix y z t i j取 或其中,
b,c,s为常量
1,1 1 4j j jy z b j
1 1 50,0yz
完整模型：
model:
sets:
GC/1..7/:s,t;
A/1..15/:y,z,b;
link(GC,A):c,x;
endsets
min=@sum(link(i,j):c(i,j)*x(i,j))+0.1*@sum(A(j):
0.5*((1+y(j))*y(j)+(1+z(j))*z(j)));
@for(GC(i):@sum(A(j):x(i,j))>=500*t(i);
@sum(A(j):x(i,j))<=s(i)*t(i));
@for(A(j):@sum(GC(i):x(i,j))=y(j)+z(j));
@for(A(j)|j#LE#14:z(j)+y(j+1)=b(j));
y(1)=0.0;z(15)=0.0;
@for(GC:@BIN(t));
data:
s= ;
b= ;
c= ;
enddata
end
求解情况求解情况例题 3
1
2
3
4
5
13
12
11
12
3
6
Fi = min{Dij + Fj},j与 i相连,i＜ 5
F5＝ 0
Dij,相邻第 i城市到第 j城市的路程
Fi：第 i城市到第 5城市的最短路
SETS:
CITIES/1..5/:F;ROADS(CITIES,CITIES)/
1,2 1,3 1,42,5
3,54,5/:D;
ENDSETS
DATA,
D=13 12 1112
36;
ENDDATA
F(5) = 0;
@FOR(CITIES(i)|i #LT# 5,F(i) =
@MIN(ROADS(i,j):D(i,j)+F(j))
);
求解情况数据文件
数据文件的格式,
数据向量或数据矩阵 ~
35 37 22 32 41 32 43 38~
6 2 6 7 4 2 5 9
2 3 9 5 7 2 6 5
5 5 2 2 8 1 4 3~
DATA:
CAPACITY =@file(nlp_em.txt);
DEMAND = @file(nlp_em.txt);
ENDDATA
数据文件读入：
常量＝ @FILE(数据文件文件名 )；
文件名,nlp_em.txt
选址问题,NLP
改建两个新料场，需要确定新料场位置 (xj,yj)和运量 cij,在其它条件不变下使总吨公里数最小。
2,1,
6,.,,,1,..
])()[(m i n
6
1
2
1
2
1
6
1
2/122
jec
idcts
byaxc
jij
i
iij
j
j i
ijijij
决策变量：
ci j,(xj,yj)~16维非线性规划模型
LINGO模型的构成,4个段集合段（ SETS ENDSETS）
数据段（ DATA ENDDATA）
初始段（ INIT ENDINIT）
目标与约束段局部最优,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,B1 A1,B2 A2,B1 A3,B2/:D;
ENDSETS
SETS:
STUDENTS /S1..S8/;
PAIRS( STUDENTS,STUDENTS) |
&2 #GT# &1,BENEFIT,MATCH;
ENDSETS
集合元素的 隐式列举类型 隐式列举格式 示例 示例集合的元素数字型 1..n 1..5 1,2,3,4,5
字符 -
数字型
stringM..stringN Car101..car20
8
Car101,
car102,…,
car208
星期型 dayM..dayN MON..FRI MON,TUE,WED,
THU,FRI
月份型 monthM..monthN OCT..JAN OCT,NOV,DEC,
JAN
年份 -
月份型
monthYearM..mo
nthYearN
OCT2001..JA
N2002
OCT2001,
NOV2001,
DEC2001,
JAN2002
运算符的优先级优先级 运算符最高 #NOT# — （负号）
^
* /
+ — （减法）
#EQ# #NE# #GT# #GE# #LT# #LE#
#AND# #OR#
最低 <(=) = >(=)
三类运算符：
算术运算符 逻辑运算符 关系运算符集合循环函数四个集合循环函数,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,?
P A I R SJI
JIM A T C HJIB E N E F I T
),(
),(*),(
1),(
),(
IK
orIJ
P A I R SKJ
KJM A T C H
Solver Type:
B-and-B
Global
Multistart
Model Class:
LP,QP,ILP，
IQP,PILP,
PIQP,NLP，
INLP,PINLP
State:
Global Optimum
Local Optimum
Feasible
Infeasible
Unbounded
Interrupted
Undetermined
7个选项卡 (可设置 80-90个控制参数 )
程序与数据分离文本文件使用外部数据文件
Cut (or Copy) – 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’);
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(‘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
@OLE,与 EXCEL连接
MODEL:
SETS:
MYSET,COST,SHIP,NEED,SUPPLY;
ENDSETS
MIN = @SUM( MYSET( I),SHIP( I) * COST( I));
@FOR( MYSET( I),
[CON1] SHIP( I) > NEED( I);
[CON2] SHIP( I) < SUPPLY( I));
DATA:
MYSET =@OLE('D:\JXIE\BJ2004MCM\mydata.xls','CITIES');
COST,NEED,SUPPLY =@OLE(mydata.xls);
@OLE(mydata.xls,'SOLUTION')=SHIP;
ENDDATA
END
mydata.xls文件中必须有下列名称 (及数据 )：
CITIES,COST，
NEED,SUPPLY，
SOLUTION
在 EXCEL中还可以通过“宏”自动调用 LINGO(略 )
也可以将 EXCEL表格嵌入到 LINGO模型中 (略 )
@ODBC,与数据库连接输入基本集合元素：
setname/@ODBC([‘datasource’ [,‘tablename’ [,‘columnname’]]])/
输入派生集合元素：
setname/@ODBC([‘source’[,‘table’ [,‘column1’[,‘column2’…]]]])/
目前支持下列 DBMS,(如为其他数据库，则需自行安装驱动 )
ACCESS,DBASE,EXCEL,FOXPRO,ORACLE，
PARADOX,SQL SERVER,TEXE FILES
使用数据库之前，数据源需要在 ODBC管理器注册输入数据：
Attr_list=@ODBC([‘source’[,‘table’ [,‘column1’[,‘column2’…]]]])
输出数据：
@ODBC([‘source’[,‘table’ [,‘column1’[,‘column2’…]]]])= Attr_list
具体例子略
Excel与 Lingo数据交换
Lingo运算求解设置
4,建模与求解实例（结合软件使用）
问题 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米钢管根数 余料 (米 )
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
钢管下料问题 1
两种标准
1,原料钢管剩余总余量最小
xi ~按第 i 种模式切割的原料钢管根数 (i=1,2,…7 )
约束 满足需求决策变量目标 1（总余量）
76543211 3333 xxxxxxxZM i n
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
按模式 2切割 12根,按模式 5切割 15根，余料 27米模式
4米根数
6米根数
8米根数余料
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
需求
50 20 15
最优解,x2=12,x5=15,
其余为 0；
最优值,27
整数约束,xi 为整数当余料没有用处时,通常以总根数最少为目标
76543212 xxxxxxxZM i n
目标 2（总根数）
钢管下料问题 1
约束条件不变最优解,x2=15,
x5=5,x7=5,
其余为 0；
最优值,25。
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
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米长的钢管的数量满足需求
50313212111 xrxrxr
10323222121 xrxrxr
20333232131 xrxrxr
15343242141 xrxrxr
模式合理：每根余料不超过 3米
19865416 41312111 rrrr
19865416 42322212 rrrr
19865416 43332313 rrrr
整数非线性规划模型钢管下料问题 2
目标函数（ 总根数）
321 xxxM i n
约束条件整数约束,xi,r1i,r2i,
r3i,r4i (i=1,2,3)为整数增加约束，缩小可行域，便于求解
321 xxx
原料钢管总根数下界,2619 158206105504
特殊生产计划：对每根原料钢管模式 1：切割成 4根 4米钢管，需 13根；
模式 2：切割成 1根 5米和 2根 6米钢管，需 10根；
模式 3：切割成 2根 8米钢管，需 8根。
原料钢管总根数上界,31
3126 321 xxx
模式排列顺序可任定钢管下料问题 2
需求,4米 50根,5米 10
根,6米 20根,8米 15根每根原料钢管长 19米
LINGO求解整数非线性规划模型
Local optimal solution found at
iteration,12211
Objective value,28.00000
Variable Value Reduced Cost
X1 10.00000 0.000000
X2 10.00000 2.000000
X3 8.000000 1.000000
R11 3.000000 0.000000
R12 2.000000 0.000000
R13 0.000000 0.000000
R21 0.000000 0.000000
R22 1.000000 0.000000
R23 0.000000 0.000000
R31 1.000000 0.000000
R32 1.000000 0.000000
R33 0.000000 0.000000
R41 0.000000 0.000000
R42 0.000000 0.000000
R43 2.000000 0.000000
模式 1：每根原料钢管切割成 3
根 4米和 1根 6米钢管，共 10根；
模式 2：每根原料钢管切割成 2
根 4米,1根 5米和 1根 6米钢管，
共 10根；
模式 3：每根原料钢管切割成 2
根 8米钢管，共 8根。
原料钢管总根数为 28根。
1,优化模型与优化软件简介最优化是工程技术、经济管理、科学研究、
社会生活中经常遇到的问题,如,
优化模型和优化软件的重要意义结构设计 资源分配 生产计划 运输方案解决优化问题的手段
经验积累，主观判断
作试验，比优劣
建立数学模型 (优化模型 )，求最优策略 (决策 )
(最 )优化,在一定条件下,寻求使目标最大 (小 )的决策
CUMCM赛题：约一半以上与优化有关，需用软件求解运筹学 (OR,Operations/Operational Research)
管理科学 (MS,Management Science)
决策科学 (DS,Decision Science)
(最 )优化理论是运筹学的基本内容无约束优化
OR/
MS/
DS
优化 (Optimization),规划 (Programming)
线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划优化问题三要素,决策变量 ； 目标函数 ； 约束条件约束条件决策变量优化问题的一般形式
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
可行解（满足约束）与可行域（可行解的集合）
最优解（取到最小／大值的可行解）
目标函数无约束优化,最优解的分类和条件
)( xfM inx
给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即
nTnxxxx ),,,( 21?其中局部最优解 全局最优解必要条件 0),,()(
1
* Txx
nffxf?
充分条件 0)(,0)( *2* xfxf
Hessian阵
nnji
xx
ff
22
最优解在可行域边界上取得时不能用无约束优化方法求解
x*
f(x) xl
xgo
约束优化的简单分类
线性规划 (LP) 目标和约束均为线性函数
非线性规划 (NLP) 目标或约束中存在非线性函数
二次规划 (QP) 目标为二次函数、约束为线性
整数规划 (IP) 决策变量 (全部或部分 )为整数
整数 线性 规划 (ILP)，整数 非线性 规划 (INLP)
纯整数规划 (PIP),混合整数规划 (MIP)
一般整数规划,0-1（整数）规划
n
j
i
Dx
ljxg
mixhts
xf
,.,,,1,0)(
,.,,,1,0)(..
)(m i n
连续优化离散优化数学规划常用优化软件
1,LINDO/LINGO软件
2,MATLAB优化工具箱
3,EXCEL软件的优化功能
4,SAS(统计分析 )软件的优化功能
5,其它
MATLAB优化工具箱 能求解的优化模型优化工具箱 3.0 (MATLAB 7.0 R14)
连续优化 离散优化无约束优化非线性极小
fminunc
非光滑 (不可微 )优化
fminsearch
非线性方程 (组 )
fzero
fsolve
全局优化暂缺非线性最小二乘
lsqnonlin
lsqcurvefit
线性规划
linprog
纯 0-1规划 bintprog
一般 IP(暂缺 )
非线性规划
fmincon
fminimax
fgoalattain
fseminf
上下界约束
fminbnd
fmincon
lsqnonlin
lsqcurvefit
约束线性最小二乘
lsqnonneg
lsqlin
约束优化二次规划
quadprog
2,LINDO公司的主要软件产品及功能简介
LINDO 公司软件产品简要介绍美国芝加哥 (Chicago)大学的 Linus Schrage教授于 1980
年前后开发,后来成立 LINDO系统公司（ LINDO
Systems Inc.）,网址,http://www.lindo.com
LINDO,Linear INteractive and Discrete Optimizer (V6.1)
LINGO,Linear INteractive General Optimizer (V9.0)
LINDO API,LINDO Application Programming Interface (V3.0)
What’s Best!,(SpreadSheet e.g,EXCEL) (V8.0)
演 示 (试用 )版、学生版、高级版、超级版、工业版、
扩展版 … （求解 问题规模 和 选件 不同）
LINDO和 LINGO软件能求解的优化模型
LINGOLINDO
优化模型线性规划
(LP)
非线性规划
(NLP)
二次规划
(QP)
连续优化 整数规划 (IP)
LP QP NLP IP 全局优化 (选 )
ILP IQP INLP
LINDO/LINGO软件的求解过程
LINDO/LINGO预处理程序线性优化求解程序 非线性优化求解程序分枝定界管理程序
1,确定常数
2,识别类型
1,单纯形算法
2,内点算法 (选 )
1、顺序线性规划法 (SLP)
2、广义既约梯度法 (GRG) (选 )
3、多点搜索 (Multistart) (选 )
建模时需要注意的几个基本问题
1,尽量使用实数优化，减少整数约束和整数变量
2,尽量使用光滑优化，减少非光滑约束的个数如：尽量少使用绝对值、符号函数、多个变量求最大 /最小值、四舍五入、取整函数等
3,尽量使用线性模型，减少非线性约束和非线性变量的个数 （如 x/y <5 改为 x<5y）
4,合理设定变量上下界，尽可能给出变量初始值
5,模型中使用的参数数量级要适当 (如小于 103)
3,LINGO软件的使用简介界面帮助界面模型
min或 max f(x)
S.T,G(x)≤或 ≥或＝ 0
L ≤x≤U 要素,
1.变量 (符号 )
2.常量 （数据）
3.关系 （函数、方程）
需要掌握的几个重要方面
LINGO：
掌握集合 (SETS)的应用；
正确阅读求解报告；
正确理解求解状态窗口；
学会设置基本的求解选项 (OPTIONS) ；
掌握与外部文件的基本接口方法
LINGO软件简介
目标与约束段
集合段（ SETS ENDSETS）
数据段（ DATA ENDDATA）
初始段（ INIT ENDINIT）
计算段 (CALC ENDCALC) - LINGO9.0
LINGO模型的构成,5个段
LINGO模型的优点
包含了 LINDO的全部功能
提供了灵活的编程语言（矩阵生成器）
实例变量声明区数据赋值区关系表示区模型变量
数学表示：
LinGo表示：
{ },,{ 1,,}ix x i I I n其 中
1.单下标变量
SI/1..n/,x；
变量
数学表示：
LinGo表示：
{ },,
{ 1,,} = { 1,,}
ijx x i I j J
I n J m
，
其 中,
2.多下标变量
I/1..n/；
J/1..m/；
IJ(I,J),x；
变量取值限制
@BND(下限,变量或分量,上限 )； 默认下限为 0
@FREE(变量或分量 ) ；
@GIN(变量或分量 )；
限制变量或分量为整数
@BIN( 变量或分量 ) ；
限制变量或分量为 0,1
通常与 @for联用
@for(I,@bin(x))；
0 1,ix i I?取 或数学函数
@ABS(X)
@COS(X)
@EXP(X)
@LOG(X)
@SIN(X)
@TAN(X)
@SMAX(X1,X2,...,XN)
@SMIN(X1,X2,...,XN)
@FLOOR(X) integer function
@LGM(X) gamma function
@SIGN(X) sign function
条件和逻辑运算符
#EQ# ＝
#NE# ≠
#GT# ＞
#GE# ≥
#LT# ＜
#LE# ≤
#AND# 与
#OR# 或
#NOT# 非
@IF(条件表达式,
真值,否值 )
条件函数
XCOST = @IF( x #GT# 0,100,0) + 2 * x;
@IF(条件表达式,真值,否值 )
特殊符号
！ 段落注释符； 段落结束符
[ ] 方程注释符
1 0 0 + 2,0
X C O ST =
2,
xx
x
其 他集合函数
数学表示：
LinGo表示：
1
2,( )
k
i
ai
2.@SUM( SI( i) | i #LE# k,a( i));
1.@SUM( SI,a);
SI/1..n/,a；
1
1,( )
n
i
ai
集合函数特征
@函数 ( 下标集 [ (下标变量 ) [ |条件表达式 ]],变量表达式 );
@SUM( SI( i) | i #LE# k,a( i));
重要的集合函数
@FOR
@SUM
@MIN
@MAX
@FOR（ SI(i)|i#NE#3,x(i)<=100） ;
1 0 0,,3 ;ix i I i
例题 1
数学模型：
min
s.t.
34
11
ij ij
ij
cx
3
1
,1 4ij j
i
x x l j
4
1
,1 3i j i
j
x c l i
0,1 3,1 4ijx i j
其中,
xl＝ 5 2 4 6
cl= 4 9 4
c = 10 6 7 12
16 10 5 9
5 4 10 10
分析：
下标变量有：
1,xl 4个分量
2,cl 3个分量
3,x,c 3× 4个分量
下标集：
si 1,?,3
sj 1,?,4
sij ＝（ si,sj）
1.下标变量
si/1..3/:cl;
sj/1..4/:xl;
sij(si,sj):c,x;
lingo建模,
min @sum(si(i),
@sum(sj(j),c(i,j)*x(i,j))
） ;
lingo建模
2.目标函数
34
11
ij ij
ij
cx
,
ij ij
ij
cx?或
min @sum(sij:c*x);
min
简写 @sum(sij(i,j):c(i,j)*x(i,j));
2.约束条件：
3
1
,1 4ij j
i
x x l j
4
1
,1 3i j i
j
x c l i
3
1
ij j
i
x x l
14j?
@for(sj(j):等式 );
@for(si(i):@sum(sj(j)):x(i,j))=cl(i));
0,1 3,1 4ijx i j
默认
@sum(si(i):x(i))=xl(j)
完整模型：
model:
sets:
si/1..3/:cl;
sj/1..4/:xl;
sij(si,sj):c,x;
endsets
！ 数据设置 ；
data:
xl= 5 2 4 6;
cl= 4 9 4;
c = 10 6 7 12
16 10 5 9
5 4 10 10;
enddata
[obj] min = @sum( sij,c*x);
@for( sj(j),
[eq1] @sum( si(i),x(i,j)) = xl(j));
@for( si(i):
[eq2] @sum( sj(j),x(i,j)) = cl(i));
end
模型求解最优非零解灵敏度分析例题 2
数学模型,2000,B
min
s.t.
7 1 5 1 5
1 1 1
0,5 [ ( 1 ) ( 1 ) ]i j i j j j j j
i j j
c x y y z z
15
1
5 0 0,1 7i i j i i
j
t x s t i
7
1
,1 1 5ij j j
i
x y z j
,,0,0 1 ; 1 7,1 1 5i j j j ix y z t i j取 或其中,
b,c,s为常量
1,1 1 4j j jy z b j
1 1 50,0yz
完整模型：
model:
sets:
GC/1..7/:s,t;
A/1..15/:y,z,b;
link(GC,A):c,x;
endsets
min=@sum(link(i,j):c(i,j)*x(i,j))+0.1*@sum(A(j):
0.5*((1+y(j))*y(j)+(1+z(j))*z(j)));
@for(GC(i):@sum(A(j):x(i,j))>=500*t(i);
@sum(A(j):x(i,j))<=s(i)*t(i));
@for(A(j):@sum(GC(i):x(i,j))=y(j)+z(j));
@for(A(j)|j#LE#14:z(j)+y(j+1)=b(j));
y(1)=0.0;z(15)=0.0;
@for(GC:@BIN(t));
data:
s= ;
b= ;
c= ;
enddata
end
求解情况求解情况例题 3
1
2
3
4
5
13
12
11
12
3
6
Fi = min{Dij + Fj},j与 i相连,i＜ 5
F5＝ 0
Dij,相邻第 i城市到第 j城市的路程
Fi：第 i城市到第 5城市的最短路
SETS:
CITIES/1..5/:F;ROADS(CITIES,CITIES)/
1,2 1,3 1,42,5
3,54,5/:D;
ENDSETS
DATA,
D=13 12 1112
36;
ENDDATA
F(5) = 0;
@FOR(CITIES(i)|i #LT# 5,F(i) =
@MIN(ROADS(i,j):D(i,j)+F(j))
);
求解情况数据文件
数据文件的格式,
数据向量或数据矩阵 ~
35 37 22 32 41 32 43 38~
6 2 6 7 4 2 5 9
2 3 9 5 7 2 6 5
5 5 2 2 8 1 4 3~
DATA:
CAPACITY =@file(nlp_em.txt);
DEMAND = @file(nlp_em.txt);
ENDDATA
数据文件读入：
常量＝ @FILE(数据文件文件名 )；
文件名,nlp_em.txt
选址问题,NLP
改建两个新料场，需要确定新料场位置 (xj,yj)和运量 cij,在其它条件不变下使总吨公里数最小。
2,1,
6,.,,,1,..
])()[(m i n
6
1
2
1
2
1
6
1
2/122
jec
idcts
byaxc
jij
i
iij
j
j i
ijijij
决策变量：
ci j,(xj,yj)~16维非线性规划模型
LINGO模型的构成,4个段集合段（ SETS ENDSETS）
数据段（ DATA ENDDATA）
初始段（ INIT ENDINIT）
目标与约束段局部最优,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,B1 A1,B2 A2,B1 A3,B2/:D;
ENDSETS
SETS:
STUDENTS /S1..S8/;
PAIRS( STUDENTS,STUDENTS) |
&2 #GT# &1,BENEFIT,MATCH;
ENDSETS
集合元素的 隐式列举类型 隐式列举格式 示例 示例集合的元素数字型 1..n 1..5 1,2,3,4,5
字符 -
数字型
stringM..stringN Car101..car20
8
Car101,
car102,…,
car208
星期型 dayM..dayN MON..FRI MON,TUE,WED,
THU,FRI
月份型 monthM..monthN OCT..JAN OCT,NOV,DEC,
JAN
年份 -
月份型
monthYearM..mo
nthYearN
OCT2001..JA
N2002
OCT2001,
NOV2001,
DEC2001,
JAN2002
运算符的优先级优先级 运算符最高 #NOT# — （负号）
^
* /
+ — （减法）
#EQ# #NE# #GT# #GE# #LT# #LE#
#AND# #OR#
最低 <(=) = >(=)
三类运算符：
算术运算符 逻辑运算符 关系运算符集合循环函数四个集合循环函数,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,?
P A I R SJI
JIM A T C HJIB E N E F I T
),(
),(*),(
1),(
),(
IK
orIJ
P A I R SKJ
KJM A T C H
Solver Type:
B-and-B
Global
Multistart
Model Class:
LP,QP,ILP，
IQP,PILP,
PIQP,NLP，
INLP,PINLP
State:
Global Optimum
Local Optimum
Feasible
Infeasible
Unbounded
Interrupted
Undetermined
7个选项卡 (可设置 80-90个控制参数 )
程序与数据分离文本文件使用外部数据文件
Cut (or Copy) – 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’);
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(‘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
@OLE,与 EXCEL连接
MODEL:
SETS:
MYSET,COST,SHIP,NEED,SUPPLY;
ENDSETS
MIN = @SUM( MYSET( I),SHIP( I) * COST( I));
@FOR( MYSET( I),
[CON1] SHIP( I) > NEED( I);
[CON2] SHIP( I) < SUPPLY( I));
DATA:
MYSET =@OLE('D:\JXIE\BJ2004MCM\mydata.xls','CITIES');
COST,NEED,SUPPLY =@OLE(mydata.xls);
@OLE(mydata.xls,'SOLUTION')=SHIP;
ENDDATA
END
mydata.xls文件中必须有下列名称 (及数据 )：
CITIES,COST，
NEED,SUPPLY，
SOLUTION
在 EXCEL中还可以通过“宏”自动调用 LINGO(略 )
也可以将 EXCEL表格嵌入到 LINGO模型中 (略 )
@ODBC,与数据库连接输入基本集合元素：
setname/@ODBC([‘datasource’ [,‘tablename’ [,‘columnname’]]])/
输入派生集合元素：
setname/@ODBC([‘source’[,‘table’ [,‘column1’[,‘column2’…]]]])/
目前支持下列 DBMS,(如为其他数据库，则需自行安装驱动 )
ACCESS,DBASE,EXCEL,FOXPRO,ORACLE，
PARADOX,SQL SERVER,TEXE FILES
使用数据库之前，数据源需要在 ODBC管理器注册输入数据：
Attr_list=@ODBC([‘source’[,‘table’ [,‘column1’[,‘column2’…]]]])
输出数据：
@ODBC([‘source’[,‘table’ [,‘column1’[,‘column2’…]]]])= Attr_list
具体例子略
Excel与 Lingo数据交换
Lingo运算求解设置
4,建模与求解实例（结合软件使用）
问题 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米钢管根数 余料 (米 )
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
钢管下料问题 1
两种标准
1,原料钢管剩余总余量最小
xi ~按第 i 种模式切割的原料钢管根数 (i=1,2,…7 )
约束 满足需求决策变量目标 1（总余量）
76543211 3333 xxxxxxxZM i n
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
按模式 2切割 12根,按模式 5切割 15根，余料 27米模式
4米根数
6米根数
8米根数余料
1 4 0 0 3
2 3 1 0 1
3 2 0 1 3
4 1 2 0 3
5 1 1 1 1
6 0 3 0 1
7 0 0 2 3
需求
50 20 15
最优解,x2=12,x5=15,
其余为 0；
最优值,27
整数约束,xi 为整数当余料没有用处时,通常以总根数最少为目标
76543212 xxxxxxxZM i n
目标 2（总根数）
钢管下料问题 1
约束条件不变最优解,x2=15,
x5=5,x7=5,
其余为 0；
最优值,25。
50234 54321 xxxxx
2032 6542 xxxx
152 753 xxx
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米长的钢管的数量满足需求
50313212111 xrxrxr
10323222121 xrxrxr
20333232131 xrxrxr
15343242141 xrxrxr
模式合理：每根余料不超过 3米
19865416 41312111 rrrr
19865416 42322212 rrrr
19865416 43332313 rrrr
整数非线性规划模型钢管下料问题 2
目标函数（ 总根数）
321 xxxM i n
约束条件整数约束,xi,r1i,r2i,
r3i,r4i (i=1,2,3)为整数增加约束，缩小可行域，便于求解
321 xxx
原料钢管总根数下界,2619 158206105504
特殊生产计划：对每根原料钢管模式 1：切割成 4根 4米钢管，需 13根；
模式 2：切割成 1根 5米和 2根 6米钢管，需 10根；
模式 3：切割成 2根 8米钢管，需 8根。
原料钢管总根数上界,31
3126 321 xxx
模式排列顺序可任定钢管下料问题 2
需求,4米 50根,5米 10
根,6米 20根,8米 15根每根原料钢管长 19米
LINGO求解整数非线性规划模型
Local optimal solution found at
iteration,12211
Objective value,28.00000
Variable Value Reduced Cost
X1 10.00000 0.000000
X2 10.00000 2.000000
X3 8.000000 1.000000
R11 3.000000 0.000000
R12 2.000000 0.000000
R13 0.000000 0.000000
R21 0.000000 0.000000
R22 1.000000 0.000000
R23 0.000000 0.000000
R31 1.000000 0.000000
R32 1.000000 0.000000
R33 0.000000 0.000000
R41 0.000000 0.000000
R42 0.000000 0.000000
R43 2.000000 0.000000
模式 1：每根原料钢管切割成 3
根 4米和 1根 6米钢管，共 10根；
模式 2：每根原料钢管切割成 2
根 4米,1根 5米和 1根 6米钢管，
共 10根；
模式 3：每根原料钢管切割成 2
根 8米钢管，共 8根。
原料钢管总根数为 28根。
