数学规划模型.

《数学规划模型.》由会员分享，可在线阅读，更多相关《数学规划模型.（103页珍藏版）》请在金锄头文库上搜索。

1、第四章 数学规划模型 4.1 奶制品的生产与销售 4.2 自来水输送与货机装运 4.3 汽车生产与原油采购 4.4 接力队选拔和选课策略 4.5 饮料厂的生产与检修 4.6 钢管和易拉罐下料 y 数学规划模型 实际问题中 的优化模型 x决策变量f(x)目标函数 gi(x)0约束条件 多元函数 条件极值 决策变量个数n和 约束条件个数m较大 最优解在可行域 的边界上取得 数 学 规 划 线性规划 非线性规划 整数规划 重点在模型的建立和结果的分析 优化模型与优化软件的重要意义 (最)优化:在一定条件下,寻求使目标最大(小)的决策 最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问 题,

2、 如: 结构设计 资源分配 生产计划 运输方案 解决优化问题的手段 经验积累，主观判断 作试验，比优劣 建立数学模型(优化模型)，求最优策略(决策) (最)优化:在一定条件下,寻求使目标最大(小)的决策 CUMCM赛题：约一半以上与优化有关，需用软件求解。 (最)优化理论是运筹学的基本内 容 运筹学(OR: Operations/Operational Research) 管理科学(MS: Management Science) 决策科学(DS: Decision Science) 优化(Optimization), 规划(Programming) 无 约 束 优 化 线 性 规 划 非 线

3、性 规 划 网 络 优 化 组 合 优 化 整 数 规 划 不 确 定 规 划 多 目 标 规 划 目 标 规 划 动 态 规 划 OR/ MS/ DS 优化问题的一般形式 优化问题三要素：决策变量；目标函数；约束 条件 可行解（满足约束）与可行域（可行解的集合） 最优解（取到最小大值的可行解） 约 束 条 件 目标函数 决策变量 给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即 其中 局部最优解 全局最优解 必要条件 x * f(x)xl xg o 充分条件 Hessian阵 最优解在可行域边界上取得时不能用无约束优化方法求解 无约束优化:最优解的分类和条 件 约束优化的简单分类

4、 线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划 数学规划 连 续 优 化 离 散 优 化 常用优化软件 1. LINDO/LINGO软件 2. MATLAB优化工具箱 3. EXCEL软件的优化功能 4. SAS(统计分析)软件的优化功能 5. 其他 MATLAB优化工具箱能求解的优 化模型 The toolbox incl

5、udes routines for many types of optimization including : Unconstrained nonlinear minimization Constrained nonlinear minimization, including goal attainment problems, minimax problems, and semi-infinite minimization problems Quadratic and linear programming Nonlinear least squares and curve-fitting N

6、onlinear system of equation solving Constrained linear least squares Sparse and structured large-scale problems MATLAB优化工具箱能求解的优 化模型 优化工具箱3.0 (MATLAB 7.0 R14) 连续优化离散优化 无约束优化 非线性 极小 fminunc 非光滑(不可 微)优化 fminsearch 非线性 方程(组 ) fzero fsolve 全局 优化 暂缺 非线性 最小二乘 lsqnonlin lsqcurvefit 线性规划 linprog 纯0-1规划 bint

7、prog 一般IP(暂缺) 非线性规划 fmincon fminimax fgoalattain fseminf 上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit 约束线性 最小二乘 lsqnonneg lsqlin 约束优化 二次规划 quadprog LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980年 前后开发, 后来成立LINDO系统公司（LINDO Systems Inc. ） 网址： LINDO: Linear INteractive and Discrete Optimizer (V6

8、.1) LINGO: Linear INteractive General Optimizer (V9.0) LINDO API: LINDO Application Programming Interface (V2.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V7.0) 演示(试用)版、学生版、高级版、超级版、工业版、扩展版 求解问题规模和选件不同 LINDO API 使用LINDO API可以建立求最佳解的应用程序。LINDO API允许你将强大的线性 、整数或非线性求解引擎挂入你已写好的应用程序中。 迅速、容易的应用程序开发 LINDO API

9、可以使你容易地将最佳化的功能整合到你自己开发的应用程序中。 LINDO API 附有完整的文件和范例帮助您迅速上手。 强大的求解引擎 LINDO API 提供的强大求解引擎包括针对线性、非线性 (convex和nonconvex)， 二次和整数的最佳化。 完整的求解程序 LINDO API 提供了你需要的弹性和功能，不管你的应用程序是大或小，简单或 复杂。它包含了数十个程序(routine) 来公式化、求解、查询和修改你的问题。 分析不可实行和无边际模型(Infeasible and Unbounded Models) LINDO API 内含工具可以找出导致模型无合理解或无边际模型的原因。

10、建立因特网和企业内部网络的应用程序 LINDO API 允许你建立因特网和企业内部网络的应用程序可同时供多人使用 LINDO和LINGO软件能求解的优化模型 LINGO LINDO 优化模型 线性规划 (LP) 非线性规划 (NLP) 二次规划 (QP) 连续优化 整数规划(IP) LINDO/LINGO软件的求解过程 LP QP NLP IP 全局优化(选 ) ILP IQP INLP LINDO/LINGO预处理程序 线性优化求解程序非线性优化求解程序 分枝定界管理程序 1. 确定常数 2. 识别类型 1. 单纯形算法 2. 内点算法(选) 1、顺序线性规划法(SLP) 2、广义既约梯度法

11、(GRG) (选) 3、多点搜索(Multistart) (选) 建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最大/最 小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量的个数 （如x/y 5 改为x5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当(如小于 103) 需要掌握的几个重要方面 1、LINDO: 正确阅读求解报告（尤其要掌握敏感性分析 ） 2、LINGO： 掌握集合(SETS)的应用； 正确阅读求解报告

12、； 正确理解求解状态窗口； 学会设置基本的求解选项(OPTIONS) ； 掌握与外部文件的基本接口方法 DIFFERENCE BETWEEN LINGO AND LINDO LINDO 用于求解线性规划和二次规划 LINGO 还可用于非线性规划求解，一些线性和 非线性方程组的求解。 LINDO不提供数组或类似的数据结构。 LINGO包含内置的建模语言，允许以简练、直 观的方式描述较大规模的优化问题，模型中所 需要的数据可以以一定格式保存在独立的文件 中。 文件类型描述 .lg4 LINGO格式的模型文件 二进制格式文件 .lng 文本格式的模型文件（不保存字体、颜色 、嵌入对象） .ldt L

13、INGO数据文件 .ltf LINGO命令脚本文件 .lgr LINGO报告文件 .ltx LINDO格式的模型文件 .mps 数学规划系统格式的模型文件 状态窗口 Model Class: LP,QP,ILP,IQ,PILP,PI QP,NLP,INLP,PINLP State: Global Optimum Local Optimum Feasible Infeasible Unbounded Interrupted Undetermined Solver Type: B-and-B 分支定界 Global 全局最优 Multistart 多个初始点 LINGO软件简介 LINGO模型的优

14、点 包含了LINDO的全部功能 提供了灵活的编程语言（矩阵生成器） LINGO模型的构成：5个段 目标与约束段 集合段（SETS ENDSETS） 数据段（DATA ENDDATA） 初始段（INIT ENDINIT） 计算段(CALC ENDCALC) - LINGO9.0 企业生产计划 4.1 奶制品的生产与销售 空间层次 工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划； 车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。 时间层次 若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多

15、阶段生产计划。 本节课题 例1 加工奶制品的生产计划 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 35元可买到1桶牛奶，买吗？若买，每天最多买多少? 可聘用临时工人，付出的工资最多是每小时几元? A1的获利增加到 30元/公斤，应否改变生产计划？ 每天： 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利 约束条件 非负约束 线性 规划 模型 (LP) 时间480小时 至多加工100公斤A1 50桶牛奶 每天 模型分析与假设 比 例 性