优化模型及lingo软件

《优化模型及lingo软件》由会员分享，可在线阅读，更多相关《优化模型及lingo软件（106页珍藏版）》请在金锄头文库上搜索。

1、桂林理工大学理学院,优化建模与LINGO软件,桂林理工大学理学院,简要提纲,1. 优化模型简介2. LINGO软件简介3. 建模与求解实例,桂林理工大学理学院,1. 优化模型简介,桂林理工大学理学院,优化模型和优化软件的重要意义,解决优化/决策问题的手段,经验积累，主观判断,作试验，比优劣,建立数学模型(优化模型)，求最优策略(决策),(最)优化:在一定条件下,寻求使目标最大(小)的决策,CUMCM赛题：50%与优化有关，规模大，需软件求解,OR/MS/DS的基础:OR(运筹学,Operations/-al Research) MS(管理科学,Management Science) DS(决策

2、科学,Decision Science) 工程技术/经济管理/科学研究/社会生活中经常遇到,桂林理工大学理学院,问题一 ：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,两个引例,桂林理工大学理学院,解: 设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6。可建立以下线性规划模型：,桂林理

3、工大学理学院,问题二：某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该工厂应聘一级、二级检验员各几名？,解: 设需要一级和二级检验员的人数分别为x1、x2人,则应付检验员的工资为：,因检验员错检而造成的损失为：,桂林理工大学理学院,故目标函数为：,约束条件为：,桂林理工大学理学院,线性规划模型：,桂林理工大学理学院,二 冰山运输,背景,波斯湾地区水资源贫乏，淡

4、化海水的成本为每立方米0.1英镑。,专家建议从9600千米远的南极用拖船运送冰山，取代淡化海水,从经济角度研究冰山运输的可行性。,建模准备,1. 日租金和最大运量,桂林理工大学理学院,2. 燃料消耗（英镑/千米）,3. 融化速率（米/天）,建模准备,桂林理工大学理学院,建模目的,选择船型和船速，使冰山到达目的地后每立米水的费用最低，并与淡化海水的费用比较,模型假设,航行过程中船速不变，总距离9600千米,冰山呈球形，球面各点融化速率相同,到达目的地后，每立方米冰可融化0.85立方米水,建模分析,目的地水体积,运输过程融化规律,总费用,桂林理工大学理学院,模型建立,1. 冰山融化规律,船速u (

5、千米/小时) 与南极距离d(千米) 融化速率r(米/天）,r是 u 的线性函数； d4000时u与d无关.,航行 t 天,第t天融化速率,桂林理工大学理学院,1. 冰山融化规律,冰山初始半径R0，航行t天时半径,冰山初始体积,t天时体积,总航行天数,选定u,V0, 航行t天时冰山体积,到达目的地时冰山体积,桂林理工大学理学院,2. 燃料消耗,燃料消耗 q1(英镑/千米),q1对u线性, 对log10V线性,选定u,V0, 航行第t天燃料消耗 q (英镑/天),燃料消耗总费用,桂林理工大学理学院,3. 运送每立方米水费用,冰山初始体积V0的日租金 f(V0)（英镑）,航行天数,总燃料消耗费用,拖

6、船租金费用,冰山运输总费用,桂林理工大学理学院,冰山到达目的地后得到的水体积,3. 运送每立方米水费用,冰山运输总费用,运送每立方米水费用,到达目的地时冰山体积,桂林理工大学理学院,模型求解,选择船型和船速，使冰山到达目的地后每立方米水的费用最低,V0只能取离散值,经验公式很粗糙,桂林理工大学理学院,结果分析,由于未考虑影响航行的种种不利因素，冰山到达目的地后实际体积会显著小于V(u,V0)。,有关部门认为，只有当计算出的Y(u,V0)显著低于淡化海水的成本时，才考虑其可行性。,大型拖船V0= 107 (米3)，船速 u=45(千米/小时), 冰山到达目的地后每立米水的费用 Y(u,V0)约0

7、.065(英镑),虽然0.065英镑略低于淡化海水的成本0.1英镑，但是模型假设和构造非常简化与粗糙。,2018/9/9,桂林理工大学理学院,优化问题三要素：决策变量；目标函数；约束条件,优化问题的一般形式,无约束优化(没有约束)与约束优化(有约束)可行解（只满足约束）与最优解(取到最优值),2018/9/9,桂林理工大学理学院,局部最优解与整体最优解,局部最优解 (Local Optimal Solution, 如 x1 )整体最优解 (Global Optimal Solution, 如 x2 ),桂林理工大学理学院,线性规划模型的解的几种情况,桂林理工大学理学院,优化模型的 简单分类,线

8、性规划(LP) 目标和约束均为线性函数非线性规划(NLP) 目标或约束中存在非线性函数二次规划(QP) 目标为二次函数、约束为线性整数规划(IP) 决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划,连续优化,离散优化,数学规划,桂林理工大学理学院,优化模型的简单分类和求解难度,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,问题求解的难度增加,2018/9/9,桂林理工大学理学院,整数规划问题一般形式,整数线性规划(ILP) 目标和约束均为线性函数整数非线性规划(INLP)

9、目标或约束中存在非线性函数,整数规划问题的分类,纯(全)整数规划(PIP) 决策变量均为整数混合整数规划(MIP) 决策变量有整数，也有实数,0-1规划 决策变量只取0或1,桂林理工大学理学院,无约束优化,更多的优化问题,线性规划,非线性规划,网络优化,组合优化,整数规划,不确定规划,多目标规划,目标规划,动态规划,连续优化,离散优化,从其他角度分类,应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便,桂林理工大学理学院,Optimization Tree http:/www-

10、fp.mcs.anl.gov/otc/Guide/OptWeb/,桂林理工大学理学院,优化建模如何创新？,方法1：大胆创新，别出心裁- 采用有特色的目标函数、约束条件等- 你用非线性规划，我用线性规划- 你用整数/离散规划，我用连续规划/网络优化- 方法2：细致入微，滴水不漏- 对目标函数、约束条件处理特别细致- 有算法设计和分析，不仅仅是简单套用软件- 敏感性分析详细 / 全面- ,桂林理工大学理学院,建模时需要注意的几个基本问题,1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最小值、四舍五入、取整函

11、数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103),桂林理工大学理学院,2. LINGO软件简介,桂林理工大学理学院,常用优化软件,1. LINGO软件2. MATLAB优化工具箱 / Mathematic的优化功能3. SAS(统计分析)软件的优化功能4. EXCEL软件的优化功能5. 其他（如CPLEX等）,桂林理工大学理学院,MATLAB优化工具箱能求解的优化模型,优化工具箱3.0 (MATLAB 7.0 R14),连续优化,离散优化,无约束优化,非线

12、性 极小 fminunc,非光滑(不可 微)优化 fminsearch,非线性 方程(组)fzero fsolve,全局 优化暂缺,非线性 最小二乘lsqnonlin lsqcurvefit,线性规划 linprog,纯0-1规划 bintprog 一般IP(暂缺),非线性规划 fmincon fminimax fgoalattain fseminf,上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit,约束线性 最小二乘 lsqnonneg lsqlin,约束优化,二次规划 quadprog,桂林理工大学理学院,LINDO 公司软件产品简要介绍,美国芝加哥(

13、Chicago)大学的Linus Schrage教授于1980年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址：http:/,LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINDO API: LINDO Application Programming Interface (V4.1) LINGO: Linear INteractive General Optimizer (V10.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0),演示(试用

14、)版、高级版、超级版、工业版、扩展版 （求解问题规模和选件不同）,桂林理工大学理学院,LINDO/LINGO软件能求解的模型,优化,线性规划,非线性规划,二次规划,连续优化,整数规划,LINDO,LINGO,桂林理工大学理学院,LINGO软件的功能与特点,LINGO模型的优点,集成了线性(非线性) / 连续(整数) 优化功能具有多点搜索 / 全局优化功能提供了灵活的编程语言(矩阵生成器)，可方便地输入模型提供与其他数据文件的接口提供与其他编程语言的接口LINDO API 可用于自主开发运行速度较快,桂林理工大学理学院,LP QP NLP IP 全局优化(选) ILP IQP INLP,LING

15、O软件的求解过程,LINGO预处理程序,线性优化求解程序,非线性优化求解程序,分枝定界管理程序,1. 确定常数 2. 识别类型,1. 单纯形算法 2. 内点算法(选),1、顺序线性规划法(SLP) 2、广义既约梯度法(GRG) (选) 3、多点搜索(Multistart) (选),桂林理工大学理学院,LINGO的界面,LINGO软件的主窗口（用户界面），所有其他窗口都在这个窗口之内。,模型窗口（Model Window），用于输入LINGO优化模型（即LINGO程序）。,状态行（最左边显示“Ready”，表示 “准备就绪”）,当前时间,当前光标的位置,桂林理工大学理学院,工具栏,File|Open （F3） 打开文件,File|Print （F7） 打印文件,Edit|Copy (Ctrl+C) 复制,Edit|Undo (Ctrl+Z) 取消操作,Edit|Find (Ctrl+F) 查找,LINGO|Solution (Alt+O)显示解答,Edit|Match Parenthesis (Ctrl+P) 匹配括号,LINGO|Options (Ctrl+I) 选项设置,Window|Close All(Alt+X) 关闭所有窗口,