优化模型 数学建模讲座(2004年7月~8月江西) 优化模型与 LINDO/LINGO优化软件 谢金星 清华大学数学科学系 Tel:010-62787812 Email:jxie@math.tsinghua.edu.cn http://faculty.mathtsinghua.edu.cn/jxie
数学建模讲座(2004年7月~8月江西) 优化模型与LINDO/LINGO优化软件 谢金星 清华大学数学科学系 Tel: 010-62787812 Email:jxie@math.tsinghua.edu.cn http://faculty.math.tsinghua.edu.cn/~jxie
优化模型 简要提纲 优化模型简介 LⅠNDO公司的主要软件产品及功能简介 LⅠNDO软件的使用简介 LINGO软件的使用简介 建模与求解实例(结合软件使用)
简要提纲 • 优化模型简介 • LINDO公司的主要软件产品及功能简介 • LINDO软件的使用简介 • LINGO软件的使用简介 • 建模与求解实例(结合软件使用)
优化模型 优化模型 实际问题中Mm(或Max)z=f(x),x=(x2…xn) 的优化模型 s.g(x)≤0,i=1,2,…m x决策变量x)}目标函数g(x)≤0~约束条件 数学规划 线性规划(LP)0-1整数规划纯整数规划(PIP) 二次规划(QP)一般整数规划混合整数规划(MIP 非线性规划NLP) 连续规划 整数规划(IP
优化模型 实际问题中 的优化模型 st g x i m Min Max z f x x x x i T n . . ( ) 0, 1,2, ( ) ( ), ( , ) 1 或 x~决策变量 f(x)~目标函数 gi(x)0~约束条件 数学规划 线性规划(LP) 二次规划(QP) 非线性规划(NLP) 纯整数规划(PIP) 混合整数规划(MIP) 整数规划(IP) 0-1整数规划 一般整数规划 连续规划
优化模型 LⅠN0公司软件产品简要介绍 美国芝加哥( Chicago)大学的 Linus Schrage教授于1980 年前后开发,后来成立LⅠNDO系统公司( LINDO Systems Inc.),网址:htt:/ww. lindo. com LINDO: Linear INteractive and Discrete optimizer (V6.1) LINGO: Linear INteractive General optimizer (V8.0) LINDO API: LINDO Application Programming Interface(V2.0) What's Best! :(Spreadsheet e.g. EXCEL (V7.0) 演示(试用)版、学生版、高级版、超级版、工业版、 扩展版….(求解问题规模和选件不同)
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 (V8.0) LINDO API: LINDO Application Programming Interface (V2.0) What’s Best!: (SpreadSheet e.g. EXCEL) (V7.0) 演示(试用)版、学生版、高级版、超级版、工业版、 扩展版… (求解问题规模和选件不同)
优化模型 LIND0和LING0软件能求解的优化模型 优化模型 连续优化 整数规划(IP 线性规划二次规划非线性规划 (LP) (QP NLP LINDO LINGO
LINDO和LINGO软件能求解的优化模型 LINDO LINGO 优化模型 线性规划 (LP) 非线性规划 (NLP) 二次规划 (QP) 连续优化 整数规划(IP)
优化模型 LINDO/LINGO软件的求解过程 1确定常数 LINDO/LINGO预处理程序 2识别类型 LP/QP NLP IP全局优化(选) 分枝定界管理程序 ILP IQP INLP 线性优化求解程序非线性优化求解程序 单纯形算法 1、顺序线性规划法(SLP 2、广义既约梯度法(GRG)(选) 2.内点算法(选) 3、多点搜索 Multistart)(选)
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<5改为x<5y) 4、合理设定变量上下界,尽可能给出变量初始值 5、模型中使用的参数数量级要适当(如小于103)
建模时需要注意的几个基本问题 1、尽量使用实数优化,减少整数约束和整数变量 2、尽量使用光滑优化,减少非光滑约束的个数 如:尽量少使用绝对值、符号函数、多个变量求 最大/最小值、四舍五入、取整函数等 3、尽量使用线性模型,减少非线性约束和非线性变 量的个数 (如x/y <5 改为x<5y) 4、合理设定变量上下界,尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于10 3)
优化模型 需要掌握的几个重要方面 1、 LINDO 正确阅读求解报告(尤其要掌握敏感性分析) 2、 LINGO 掌握集合(SETS)的应用 正确阅读求解报告; 正确理解求解状态窗口; 学会设置基本的求解选项 OPTIONS); 掌握与外部文件的基本接口方法
需要掌握的几个重要方面 1、LINDO: 正确阅读求解报告(尤其要掌握敏感性分析) 2、LINGO: 掌握集合(SETS)的应用; 正确阅读求解报告; 正确理解求解状态窗口; 学会设置基本的求解选项(OPTIONS) ; 掌握与外部文件的基本接口方法
优化模型 例1加工奶制品的生产计划 1桶 12小时 3公斤A1获利24元/公斤 牛奶或 8小时4公厅A2 获利16元/公斤 2 每天:50桶牛奶时间480小时至多加工100公斤A1 制订生产计划,使每天获利最大 35元可买到1桶牛奶,买吗?若买,每天最多买多少? 可聘用临时工人,付出的工资最多是每小时几元? °A1的获利增加到30元/公斤,应否改变生产计划?
例1 加工奶制品的生产计划 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划,使每天获利最大 • 35元可买到1桶牛奶,买吗?若买,每天最多买多少? • 可聘用临时工人,付出的工资最多是每小时几元? • A1的获利增加到 30元/公斤,应否改变生产计划? 每天:
优化模型 牛奶或/12小时3公厅A 1桶 获利24元/公斤 8小时 4公斤A2获利16元/公斤 每天50桶牛奶时间480小时至多加工100公斤A1 决策变量x1桶牛奶生产A1x2桶牛奶生产A2 目标函数获利24×3x1获利16×4x2 每天获利Mxz=72x1+64x2 线性 原料供应 x1+x2≤50 规划 约束条件劳动时间12xX+8x2≤480模型 加工能力 3x,<100 (LP) 非负约束 x1,x2≥0
1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 原料供应 50 x1 x2 劳动时间 12x1 8x2 480 加工能力 3 100 x1 决策变量 目标函数 1 2 每天获利 Max z 72x 64x 约束条件 非负约束 x1 , x2 0 线性 规划 模型 (LP) 时间480小时 至多加工100公斤A1 每天 50桶牛奶