第章 高等数学规划预备知识.docVIP

第1章 预备知识 §1.1 基本概念与术语 1.1.1 数学规划问题举例 例1 食谱（配食）问题 假设市场上有n种不同的食物，第j种食物每个单位的销售价为。 人体在正常生命活动过程中需要m种基本的营养成分。为了保证人体的健康，一个人每天至少需要摄入第i种营养成分个单位。 第j种食物的每个单位包含第i种营养成分个单位。 食谱（配食）问题就是要求在满足人体基本营养需求的前提下，寻找最经济的配食方案（食谱）。 建立食谱的数学模型 引入决策变量 ：食谱中第i种食物的单位数量 s.t. 例2 选址与运输问题 假设某大型建筑公司有m个项目在不同的地点同时开工建设.记工地的位置分别为. 第i个工地对某种建筑材料的日用量是已知的（比如水泥的日用量（单位：t）为）． 该公司准备分别在和两个地点建造临时料场，并且保证临时料场对材料的日储量（单位：t）分别为和． 如何为该公司确定临时料场的位置，并且制订每天的材料供应计划，使建筑材料的总体运输负担最小？ 建立选址与运输问题的数学模型 引入决策变量：位置变量,从临时料场向各工地运送的材料数量. s.t. 例3 生产计划问题 某企业向客户提供一种机器，第1季度末需要交货台，第2季度末需要交货台，第3季度末需要交货台． 该企业最大生产能力是每季度生产b 台. 若用x表示该企业在某季度生产的机器台数，则生产费用（单位：元）可以用函数来描述. 企业需为每台机器在每个季度多支付p元的存储费． 假设在第一个季度开始时无存货，不允许缺货. 如何制订生产计划，确定在每个季度应该生产多少台机器，才能既履行交货合同，又使企业总体费用最少？ 建立生产计划的数学模型 决策变量：用表示企业在第i个季度生产的机器数量． 合同规定的总数量： 每个季度生产数量要求：每个季度生产数量不大于最大生产能力b ，不少于该季度末的交货量与该季度初的库存量之差. 第j个季度初库存量： （=0） 变量隐含要求：，并且取整数． 企业总费用：所有季度生产与存储费用之和 s.t. (Z表示所有整数的集合) 1.1.2 数学规划问题的模型与分类 形成一个最优化问题的数学模型 首先需要辨识目标，确定优化标准，即待研究系统的性能定量描述，如成本、数量、利润、时间、能量等； 其次用合适的决策变量描述系统的特征量，并将目标表示成决策变量的函数（目标函数，objective function )； 此外需确定变量所受的范围限制，由若干个函数的等式或者不等式来定义（约束函数，constraint functions)． 最优化问题指在决策变量所受限制范围内，对相关的目标函数进行极小化或者极大化. s.t. 满足约束条件的点称为可行点（feasible point ) ，所有可行点的集合称为可行域（feasible region) ，记为S. ( 当，无约束优化问题;否则,约束优化问题． ( 和都是线性函数，为线性规划（linear programming，LPnonlinear programming, NLP）. ( 所有变量取整数，称为整数规划（integer programmingmixed integer programming, MIP）. ( 从一个连通无限集合（可行域）中寻找最优解, 称为连续优化(continuous optimization)问题；从一个有限的集合或者离散的集合中寻找最优解，称为组合优化（combinatorial optimization)（discrete optimization）取一个向量值函数，称多目标规划（multi-objective programming)（deterministic optimization）（uncertain optimization)（stochastic programming）（fuzzy programming ) 1.1.3 最优解的概念 定义: 设为目标函数，为可行域，，若对每个，成立，则称为在上的全局极小点。 定义: 设为目标函数，为可行域，若存在的邻域，使得对每个成立，则称为在上的局部极小点。 全局极小点也是局部极小点，而局部极小点不一定是全局极小点. 大多数的优化算法通常只是寻找局部最优解. 对于某些特殊情形，如凸规划，局部极小点也是全局极小点. §1.2 多元函数分析 1.2.1 梯度及Hesse矩阵 函数在x处的梯度为n维列向量： 函数在x处的Hesse矩阵为矩阵： 二次函数 A是n阶对称矩阵，b是n维列向量，c是常数． 梯度： Hesse矩阵: 对向量值函数,每个分量为n元实值函数.h在点x的Jacobi矩阵为 该矩阵称为h在x的导数,记作或, 其中 例 向量值函数 在任一点的Jacobi矩