优化建模与LINGO-2016

格式：ppt
大小：384.50 KB
文档页数：27

下载文档原格式

数学建模讲座优化建模与LINGO优化软件

x1 x2 50
12x1 8x2 480
约束条件
劳动时间加工能力非负约束
3x1 100 x1 , x2 0
线性规划模型 (LP)
模型求解
OBJECTIVE FUNCTION VALUE
max =72*x1+64*x2; x1+x2<50;
REDUCED COST 0.000000
Lingo

基础
计算结果为
Objective value:89.88349
模型的集部分

LINGO 有两种类型的集：原始集 ( primitive set) 和派生集 ( derived set)。一个原始集是由一些最基本的对象组成的。一个派生集是用一个或多个其它集来定义的，也就是说，它的成员来自于其它已存在的集。
如果在Lingo文件example3_4.lg4 加上以下内容其他不变 data:
@ole("d:\ 数学建 \EXAMPLE3_4.XLS","result")=c; @ole("d:\ 数学 \EXAMPLE3_4.XLS","x")=x; 建模模
@ole("d:\ 数学 \EXAMPLE3_4.XLS","y")=y;
@OLE 的使用例子 Lingo文件example3_4.lg4 的内容 data: a,b,d,e=@OLE("d:\数学建模 \EXAMPLE3_4.XLS"); enddata init: x,y=@Ole("d:\数学建模 \Example3_4.xls"); endinit

优化模型与LINGO优化软件

资源单位产品资源消耗量甲 A B C 单位产品利润 2 4 0 2 乙 2 0 5 3 12 16 15 资源拥有量
m ax z 2 x1 3 x 2 s .t . 2 x1 2 x 2 1 2 4x 16 1 5 x2 15 x1 , x 2 0
状态窗口说明（例1）
•Constraints(约束数量) •Nonzeros(非零系数数量) •内存使用量 •求解花费的时间
全局最优解求解步骤数
3、报告窗口说明（例1）
最优解变量的检验数松弛或剩余变量的值对偶价格的值
单纯形法计算步骤框图(目标函数求max)
至少存在一个元素ais>0
LINGO的窗口介绍
LINGO的主窗口 LINGO模型窗口 LINGO状态窗口 LINGO报告窗口

例1的运算结果：主窗口模型窗口报告窗口状态窗口
1、主窗口与模型窗口说明
定位某行
模型求解
模型图示
查找
匹配括号
显示解答
选项设置
2、状态窗口说明（例1）
③ LINGO中的语句顺序是不重要的,因为LINGO总是根据“Max=”或“Min=”语句寻找目标函数，其它语句都是约束条件. ④ LINGO 程序中不区分大小写字母 .( 实际上任何小写字符将被转换为大写字符) ⑤ LINGO中的变量必须以字母开头,且最多不能超过32个字符. ⑥ 在LINGO中,以@开头的都是函数的调用. ⑦ LINGO已假定所有变量非负, 可用限定变量取值范围的函数 @BIN 、 @GIN 、 @FREE 、 @BND 改变变量的非负假定.
•求解器状态框 •模型的类型 •解的状态 •Objective(解的目标函数值) •Infeasibility(约束不满足总量) •到目前为止的迭代次数 •扩展的求解器状态框

(外校培训课件)优化模型与LINGO软件求解——LINGO学习集全资料文档

NLP: 非线性规划
(2)最优状态全局全优
(3)最优目标值: 10
约束条件情况最优解： (1)约束总个数X4=100,按方法4 (2)非线性个数X6=50, 按方法6
25
[例1] 下料(截割问题)及求解
❖ [模型-2]的求解结果：
最优目标函数值：90
x1=40, 按方法1截割 x2=20, 按方法2截割 x6=30. 按方法6截割
26
[例1] 下料(截割问题)及求解
❖ 求解结果分析：
在追求“余料最少”目标时，“≥”约束把条件放宽了。
修正方法：改为“=”约束
模型(1)的求解结果：最优目标(余料)=10m
(x4,x6)=(100,50) 耗用原料 = 150根
是否符合原问题要求?
不符合。 (1)问题出在哪里? (2)如何修正?
2
一、竞赛题中的优化模型总结
❖ 2.优化类竞赛题小结 ❖ 在全国数模竞赛中，优化问题是出现频率最
高的一类竞赛题。 ❖ 从1992-20××年全国大学生数模竞赛试题
的解题方法统计结果来看，优化模型共出现了17次以上，占到了50%。 ❖ 即每两道竞赛题中就有一道涉及到利用优化理论来建模和求解。
3
一、竞赛题中的优化模型总结
题
13
(三) 典型数学规划问题及求解
❖ 例1 下料(截割)问题及求解 ❖ 例2 运输问题及求解 ❖ 例3 非线性规划问题及求解 ❖ 例4 分派(选址)问题及求解 ❖ 例5 动态规划问题及求解
14
[例1] 下料(截割)问题及求解
1. 问题提出 2. 建立数学模型 3. 编写LINGO求解程序 4. 执行程序 5. 获得计算结果并分析 6. 修正模型，重新求解 7.课后作业 8.编程小结

优化模型与Lingo软件

解最优化问题，后经不断完善和扩充，并成立 LINDO公司进行商业化运作，取得了巨大的成功。全球《财富》杂志500强的企业中，一半以上使用该公司产品，其中前25强企业中有23 家使用该产品。
➢该软件包功能强大，版本也很多，而我们使
用的只是演示版（试用版），演示版与正式版功能基本上是类似的，只是能够求解问题的规
s.t. 3x 5y 12 x, y 0
Lingo软件介绍
点击图标
运行，屏幕上显示运行状态窗口如下：对于Lingo运行状态窗口，
我们给于以下解释：
变量数目：变量总数（Total）、非线型变量数（Nonlinear）、整数变量数（Integer）
约束变量：约束总数（ Total ）、非线性约束个数（Nonlinear）
量
命令SLB、SUB类似的函数@ SLB、 @ SUB.
定
@BIN（X）：限制X为0或1。注意Lindo中的命令是INT，但Lingo中
界
这个函数却不是@INT.
函
@FREE(X) ：取消对X的符号限制（即可取负数，0或正数）.
数
@GIN（X）：限制X为整数.
LINGO中的集
• 对实际问题建模的时候，总会遇到一群或多群相联系的对象，比如工厂、消费者群体、交通工具和雇工等等。LINGO允许把这些相联系的对象聚合成集（sets）。一旦把对象聚合成集，就可以利用集来最大限度的发挥LINGO建模语言的优势。
Global Optimum、Local Optimum、Feasible、
State
当前解的状态IInnfteearrsuipbtlee（d（不中可断行））、、uUndnebtoeurmndineedd（（无未界确）、

优化建模与LINGO第11章

( 3 ) Cpi（i= 1,2, …,m）表示第 i 种产品的单位存贮费；
( 4 ) J, WT分别表示每次订货可占用资金和库存总容量；
( 5 ) wi（i =1,2,…,m）表示第 i 种物品的单位库存占用．
优化建模
1 具有资金约束的 EOQ 模型
对于第i ( i = 1 , 2 ， … ，m）种物品，当每次订货
模型定义：不允许缺货、货物生产 (或补充)的时间
很短（通常近似为0）.
经济订购批量存贮模型（EOQ）有以下假设：
( l ) 短缺费为无穷，即 Cs＝∞，
( 2 ) 当存贮降到零后，可以立即得到补充；
( 3 ) 需求是连续的、均匀的；
( 4 ) 每次的订货量不变，订购费不变；
( 5 ) 单位存贮费不变。
(1) 批量订货的订货费12000 元／次；
(2) 每个零件的单位成本为 10 元／件；
(3) 每个零件的存贮费用为 0.3元／(件 ·月)；
(4) 每个零件的缺货损失为 1.1 元／(件 ·月)。
公司应如何安排这些零件的订货时间与订货规模，使
得全部费用最少？
存贮论模型的基本概念
输入(供应)
储存
输出(需求)
m
m
in
m
CQ J,
st
..
i1
i
i
Q
0
, i
1
,2
, ,m
.
i
2 具有库容约束的 EOQ 模型
1

CD
D i

CQ
,
P
i i
Q
i12
i
m
m
in
m
st
..

优化建模与lingo优化软件

Teaching Plan on Optimization in Lingo
• 1992年: (Ａ)作物生长的施肥效果问题 (B)化学试验室的实验数据分解问题 • 1993年: (Ａ)通讯中非线性交调的频率设计问题 (Ｂ)足球甲级联赛排名问题
（1）1992-2008全国大学生数学建模竞赛题目如下：
4、合理设定变量上下界，尽可能给出变量初始值
5、模型中使用的参数数量级要适当 (如小于103)
Teaching Plan on Optimization in Lingo
优化问题1：
min z ( x1 1) 2 ( x1 x 2) 2 ( x 2 x3) 2 ( x3 x 4) 2 ( x 4 x5) 2
Teaching Plan on Optimization in Lingo
• 2009 (A)制动器试验台的控制方法分析 (B)眼科病床的合理安排 (C)卫星和飞船的跟踪测控 (D)会议筹备
Teaching Plan on Optimization in Lingo
(最)优化理论是运筹学的基本内容
3 x1 x2 2 x3 3 2 x2 x3 x4 2 s.t x1 x5 2 5 x 5 i
i 1,2,5
Teaching Plan on Optimization in Lingo
需要掌握的几个重要方面
LINGO：
掌握集合(SETS)的应用；
非线性规划
整数规划
组合优化
不确定规划
多目标规划
目标规划
网络优化
动态规划
Teaching Plan on Optimization in Lingo

优化建模与LINGO第05章

此时x和c(x)可以统一地表示为
x z1b1 z2b2 z3b3 z4b4 500z2 1000z3 1500z4 c( x) z1c(b1 ) z2 c(b2 ) z3c(b3 ) z4 c(b4 ) 5000z2 9000z3 12000 z4
优化建模
优化建模与LINDO/LINGO软件
第5 章
生产与服务运作管理中的优化问题
优化建模
内容提要
§5.1 生产与销售计划问题 §5.2 有瓶颈设备的多级生产计划问题 §5.3 下料问题 §5.4 面试顺序与消防车调度问题 §5.5 飞机定位和飞行计划问题
优化建模
§5.1 生产与销售计划问题
优化建模
优化建模
运行该程序得到： OBJECTIVE FUNCTION VALUE 1) 5000.000 VARIABLE VALUE REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 1000.000000 0.000000
§5.1.1问题实例
• 例5.1某公司用两种原油（A和B）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和 5600元。该公司现有原油A和B的库存量分别为500 吨和1000吨，还可以从市场上买到不超过1500吨的原油A。原油A的市场价为：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工。

优化模型与LindoLingo优化软件

使用LINDO的一些注意事项
9. 变量不能出现在一个约束条件的右端 10. 表达式中不接受括号“( )”和逗号“,”等任何符号, 例: 400(X1+X2)需写为400X1+400X2 11. 表达式应化简，如2X1+3X2- 4X1应写成 -2X1+3X2 12. 缺省假定所有变量非负；可在模型的“END”语句后用“FREE name”将变量name的非负假定取消 13. 可在 “END”后用“SUB” 或“SLB” 设定变量上下界例如： “sub x1 10”的作用等价于“x1<=10” 但用“SUB”和“SLB”表示的上下界约束不计入模型的约束，也不能给出其松紧判断和敏感性分析。 14. “END”后对0-1变量说明：INT n 或 INT name 15. “END”后对整数变量说明：GIN n 或 GIN name
需要掌握的几个重要方面
1、LINDO: 正确阅读求解报告（尤其要掌握敏感性分析） 2、LINGO：掌握集合(SETS)的应用；正确阅读求解报告；正确理解求解状态窗口；学会设置基本的求解选项(OPTIONS) ；掌握与外部文件的基本接口方法
例1 加工奶制品的生产计划
1桶牛奶或 12小时 3公斤A1 4公斤A2 获利24元/公斤获利16元/公斤
reduced cost 值表示当该非基变量增加一个单位时（其他非基变量保持不变）目标函数减少的量 ( 对 max型问题) 也可理解为：为了使该非基变量变成基变量，目标函数中对应系数应增加的量
48.000000 2.000000 0.000000
NO. ITERATIONS=
结果解释
模型求解
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1 X2 ROW 2) 3) 4) 3360.000 VALUE 20.000000 30.000000 SLACK OR SURPLUS 0.000000 0.000000 40.000000 2 REDUCED COST 0.000000 0.000000 DUAL PRICES

数学建模优化模型与Lingo Lindo软件

型
表二：5名队员4中泳姿百米平均成绩
队员
甲
乙
丙
丁
戊
蝶泳 66.8 57.2
78
70
67.4
仰泳 75.6
66
67.8
74.2
71
蛙泳
87
66.4 84.6
69.6
83.8
自由泳 58.6
53
59.4
57.2
62.4
线性规
·划
模型
决策变量：引入0-1变量xij 若选择队员 i 参加泳姿 j
例-1 某服务部门一周中每天需要不同数目的
雇员：周一到周四每天至少需要50人，周五
需要80人，周六和周日需要90人。现规定应
聘者需连续工作5天，试确定聘用方案，即周
线
一到周日每天聘用多少人，是5在满足需要的前况下聘用总人数最少？
性
优化模型
规
决策变量：记周一到周日每天聘用的人数分别为X1，
划
X2，X3，X4，X5，X6 ，X7，这就是问题的决策变量。
的比赛，记 xij=1，否则记 xij=0.这就是问题的决策变量，共20个。
目标函数：当队员队员 i 入选泳姿 j 的比赛时，
cij xij表示他的成绩，否则cij xij=0。于是接力队的成绩
可以表示为：
45
f
cij xij
j1 i1
约束条件：根据组成接力队的要求， xij 应该满足下面
方案。显然这不是解决问题的最好方法，随着问题
线
规模的变大，穷举法的计算量是无法接受的。
性
可以用0-1变量表示一个队员是否入选接力队，从而建立这个问题的0-1规划模型.

优化建模与LINGO软件

决策科学(DS: Decision Science) 优化(Optimization), 规划(Programming)
无约束优化
线性规划
非线性规划
整数规划
组合优化
不确定规划
多目标规划
目标规划
网络优化
动态规划
2017/8/29
6
优化问题的一般形式
2017/8/29
18
LINDO和LINGO软件能求解的优化模型
优化模型
连续优化
整数规划(IP)
线性规划 (LP)
二次规划 (QP)
非线性规划 (NLP) LINGO
LINDO
2017/8/29
19
LINDO/LINGO软件的求解过程
LINDO/LINGO预处理程序
1. 确定常数 2. 识别类型
2017/8/29
7
无约束优化:最优解的分类和条件
给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即
Min f ( x) 其中 x ( x1 , x2 ,, xn )T n x
局部最优解
全局最优解 x
f ( x* ) ( f x1 ,, f xn )T 0
2017/8/29
13
SAS(统计分析)软件的优化功能
Mathematical programming • Linear, mixed-integer and integer programming. • Network flow optimization: min- or max-cost flow with side constraints; maximum flow; shortest or longest path. • Simplex-based and interior-point methods available. • General nonlinear programming: unconstrained and constrained (boundary, linear and nonlinear constraints). • Solution of least squares minimization and linear complementarity problems. • Quadratic programming. • Post-optimality analysis (linear): right-hand-side and price sensitivity analysis, range analysis and parametric programming.

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

s.t.
c
j 1 6 i 1
决策变量： ci j，(xj,yj)~16维
ij d i ,
i 1,...,6
c
ij e j ,
j 1,2
非线性规划模型
(NLP)
优化建模
更多的优化问题
无约束优化线性规划非线性规划整数规划组合优化不确定规划多目标规划目标规划网络优化动态规划
LINDO: Linear INteractive and Discrete Optimizer (V6.1)
LINDO API: LINDO Application Programming Interface (V4.1)
LINGO: Linear INteractive General Optimizer What’s Best!: (SpreadSheet e.g. EXCEL) (V10.0) (V8.0)
3. SAS(统计分析)软件的优化功能
4. EXCEL软件的优化功能 5. 其他（如CPLEX等）
优化建模
MATLAB优化工具箱能求解的优化模型
优化工具箱3.0 (MATLAB 7.0 R14) 连续优化无约束优化非线性极小 fminunc 非光滑(不可微)优化 fminsearch 全局优化离散优化纯0-1规划 bintprog 一般IP(暂缺)
优化建模
线性规划模型的解的几种情况
线性规划问题
有可行解(Feasible)
无
可行解（Infeasible）
有最优解（ Optimal ）
无
最优 (Unbounded)
解
优化建模
二次规划模型(QP)-例1.2
目标
max z ( x1 , x2 ) 98 x1 + 277 x2 － x12 － 0.3 x1 x2 － 2x22
演示(试用)版、高级版、超级版、工业版、扩展版… （求解问题规模和选件不同）
优化建模
LINDO/LINGO软件能求解的模型
优化
连续优化
整数规划
线性规划
二次规划
LINDO
非线性规划
LINGO
优化建模
建模时需要注意的几个基本问题
1、尽量使用实数优化，减少整数约束和整数变量
2、尽量使用光滑优化，减少非光滑约束的个数
2、LINGO：
掌握集合(SETS)的应用；正确阅读求解报告；（尤其要掌握敏感性分析）正确理解求解状态窗口；掌握与外部文件的基本接口方法学会设置基本的求解选项(OPTIONS) ；
优化建模
2. 优化模型实例
例2.1 线性规划模型(LP) •LINGO
目标函数 Max z 72x1 64x2 model: max = 72*x1+64*x2; x1 x2 50 约束条件 [milk] x1 + x2<50; 12x1 8x2 480 [time] 12*x1+8*x2<480; 3x1 100 [cpct] 3*x1<100; x1 , x2 0 end
连续优化
离散优化
从其他角度分类
• 应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 • 实际问题规模往往较大，用软件求解比较方便
优化建模
3. LINDO/LINGO软件简介
优化建模
常用优化软件
1. LINDO/LINGO软件 2. MATLAB优化工具箱 / Mathematic的优化功能
• （4）可以给语句加上标号，例如 [OBJ]MAX=200*X1+300*X2；
优化建模
LINGO的语法规定：
• （5）以惊叹号“！”开头，以分号“；”结束的语
句是注释语句; • （6）如果对变量的取值范围没有作特殊说明，则默认所有决策变量都非负； • （7）LINGO模型以语句“MODEL：”开头，以 “END”结束，对于比较简单的模型，这两个语句可以省略。
优化建模
1. 优化模型的基本概念
优化建模
优化模型和算法的重要意义
最优化: 在一定条件下，寻求使目标最大(小)的决策最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题, 如: 结构设计资源分配生产计划运输方案
解决优化问题的手段
• 经验积累，主观判断
• 作试验，比优劣 • 建立数学模型，求解最优策略
x1 , x2
约束
x1 + x2 ≤100 x1 ≤ 2 x2 x1 , x2 ≥ 0
二次规划模型(QP)
若还要求产量为整数，则是整数二次规划模型(IQP)
优化建模
非线性规划模型(NLP)－例1.3：
min

j 1 x j ai ) 2 ( y j bi ) 2 ]1 / 2
上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit
优化建模
LINDO 公司软件产品简要介绍
美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.），网址：
如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数（如x/y <5 改为x<5y）
4、合理设定变量上下界，尽可能给出变量初始值
5、模型中使用的参数数量级要适当 (如小于103)
优化建模
需要掌握的几个重要方面
1、LINDO（不必再学）
优化建模
局部最优解与整体最优解
f( x)
* x 1
o x2
x
• 局部最优解 (Local Optimal Solution, 如 x1 ) • 整体最优解 (Global Optimal Solution, 如 x2 )
优化建模
优化模型的 min f ( x) 简单分类 s.t. hi ( x) 0, i 1,...,m
优化建模
优化问题的一般形式
优化问题三要素：决策变量；目标函数；约束条件目标函数约束条件
min s.t.
决策变量
f ( x) hi ( x) 0, i 1,...,m g j ( x ) 0, j 1,...,l xD
n
• 无约束优化(没有约束)与约束优化(有约束) • 可行解（只满足约束）与最优解(取到最优值)
优化建模
优化建模与计算
优化建模
参考书《优化建模与LINDO/LINGO软件》
谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版.
/~jxie/lindo
优化建模
内容提要
1. 优化模型的基本概念 2. 优化问题的建模实例 3. LINDO/LINGO 软件简介
优化建模
0-1规划模型
•目标函数
•约束条件
min Z cij xij
j 1 i 1
4
5
x
j 1
5 i 1
4
ij
1, i 1,,5
1, j 1,,4
x
ij
xij=1 或 xij=0
优化建模
•模型求解 •输入LINGO求解
Model: MIN=66.8*x11+75.6*x12+87*x13+58.6*x14 +… … +67.4*x51+71 * x52+83.8*x53+62.4*x54； x11+x12+x13+x14 <=1； …… x41+x42+x43+x44 <=1； x11+x21+x31+x41+x51 =1； …… x14+x24+x34+x44+x54 =1； @BIN(x11);@BIN(x12)；… @BIN(x54)； END
优化建模
优化模型的简单分类和求解难度
优化
连续优化
整数规划
线性规划
二次规划
非线性规划
问题求解的难度增加
优化建模
2. 优化模型实例
例2.1 线性规划模型(LP) 目标函数 Max z 72x1 64x2 约束条件
x1 x2 50
12x1 8x2 480
3x1 100 x1 , x2 0
g j ( x ) 0, j 1,...,l
数学规划连续优化离散优化
xD
n
• 线性规划(LP) 目标和约束均为线性函数 • 非线性规划(NLP) 目标或约束中存在非线性函数二次规划(QP) 目标为二次函数、约束为线性 • 整数规划(IP) 决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划
min=@sum(link: c*x); @for(person(i): @sum(position(j):x(i,j))<=1;); @for(position(i): @sum(person(j):x(j,i))=1;); @for(link: @bin(x)); END
约束优化
线性规划 linprog 二次规划 quadprog
非线性非线性方程 ( 组 ) 最小二乘 fzero fsolve lsqnonlin lsqcurvefit