《第1章 高等数学规划预备知识》由会员分享，可在线阅读，更多相关《第1章 高等数学规划预备知识（12页珍藏版）》请在金锄头文库上搜索。
1、1第 1 章 预备知识1.1 基本概念与术语1.1.1 数学规划问题举例例 1 食谱（配食）问题 假设市场上有 n 种不同的食物，第 j 种食物每个单位的销售价为 。),21(njc 人体在正常生命活动过程中需要 m 种基本的营养成分。为了保证人体的健康，一个人每天至少需要摄入第 i 种营养成分 个单位。),21(ib 第 j 种食物的每个单位包含第 i 种营养成分 个单位。ija食谱（配食）问题就是要求在满足人体基本营养需求的前提下，寻找最经济的配食方案（食谱） 。建立食谱的数学模型引入决策变量 ：食谱中第 i 种食物的单位数量ixinic1ms.t. mibxaijji ,21 ,nj0例
2、 2 选址与运输问题 假设某大型建筑公司有 m 个项目在不同的地点同时开工建设.记工地的位置分别为.ibaPii ,21 ),( 第 i 个工地对某种建筑材料的日用量是已知的（比如水泥的日用量（单位：t）为 ）iD 该公司准备分别在 和 两个地点建造临时料场，并且保证临时),(11yxT),(22yx料场对材料的日储量（单位：t）分别为 和 1M如何为该公司确定临时料场的位置，并且制订每天的材料供应计划，使建筑材料的总体运输负担最小？建立选址与运输问题的数学模型引入决策变量：位置变量 ,从临时料场向各工地运送的材料数量)(kyx.),21 ;,(mikzi 22)()(nki ikikbaz2
3、s.t. 2,1 1kMzmik miDki , ,2 ikyxzki ,21, R)(02例 3 生产计划问题 某企业向客户提供一种机器，第 1 季度末需要交货 台，第 2 季度末需要交货 台，1c2c第 3 季度末需要交货 台3c 该企业最大生产能力是每季度生产 b 台. 若用 x 表示该企业在某季度生产的机器台数，则生产费用（单位：元）可以用函数来描述.af21)( 企业需为每台机器在每个季度多支付 p 元的存储费 假设在第一个季度开始时无存货，不允许缺货.如何制订生产计划，确定在每个季度应该生产多少台机器，才能既履行交货合同，又使企业总体费用最少？建立生产计划的数学模型决策变量：用 表
4、示企业在第 i 个季度生产的机器数量)3,21(ix合同规定的总数量： 321cx每个季度生产数量要求：每个季度生产数量 不大于最大生产能力 b ，不少于该季度jx末的交货量 与该季度初的库存量 之差.jcjI第 j 个季度初库存量： （ =0）, ,)(jcxjiij 1I变量隐含要求： ，并且取整数3,210xj企业总费用：所有季度生产与存储费用之和 3231)()(iiipIxfF)()(min 2131 caaxi iis.t. 31jjcx1cx22(Z 表示所有整数的集合)3,0jbxjj1.1.2 数学规划问题的模型与分类 形成一个最优化问题的数学模型3 首先需要辨识目标，确定优
5、化标准，即待研究系统的性能定量描述，如成本、数量、利润、时间、能量等； 其次用合适的决策变量描述系统的特征量，并将目标表示成决策变量的函数（目标函数，objective function )； 此外需确定变量所受的范围限制，由若干个函数的等式或者不等式来定义（约束函数，constraint functions) 最优化问题指在决策变量所受限制范围内，对相关的目标函数进行极小化或者极大化. )(minRxfs.t. Iixgi ,0)(Ejhj满足约束条件的点称为 可行点 （feasible point ) ，所有可行点的集合称为 可行域（feasible region) ，记为 S. 当 ，无
6、约束优化问题;否则,约束优化问题nSR 和 都是线性函数，为 线性规划 （linear programming，LP );否则为 非线性规igf,ih划 （nonlinear programming, NLP ）. 所有变量取整数，称为 整数规划 （integer programming);允许一部分变量取整数，另一部分变量取实数，为 混合整数规划 （mixed integer programming, MIP）. 从一个连通无限集合（可行域）中寻找最优解 , 称为 连续优化 (continuous optimization)问题；从一个有限的集合或者离散的集合中寻找最优解，称为 组合优化（c
7、ombinatorial optimization)，或者 离散优化 （discrete optimization） 存在多个目标，即目标函数 取一个向量值函数，称 多目标规划 （multi-)(xfobjective programming)，或 多目标优化 最优化问题中出现的参数是完全确定的，称为 确定型优化 （deterministic optimization）问题 ;否则称为 非确定型优化 （uncertain optimization) 问题，包括了 随机规划（stochastic programming）、 模糊规划 （fuzzy programming ) 等特殊情形1.1.3
8、 最优解的概念定义: 设 为目标函数， 为可行域， ，若对每个 ，成立)(xfSSxSx，则称 为 在 上的 全局极小点 。)(xf定义: 设 为目标函数， 为可行域，若存在 的 邻域f 0，使得对每个 成立 ，则称 为|,N),(xNS)(xf在 上的 局部极小点 。)(xfS 全局极小点也是局部极小点，而局部极小点不一定是全局极小点. 大多数的优化算法通常只是寻找局部最优解. 对于某些特殊情形，如凸规划，局部极小点也是全局极小点.41.2 多元函数分析1.2.1 梯度及 Hesse 矩阵函数 在 x 处的梯度为 n 维列向量：)(f Tnxffxf )(,)(,)(21函数 在 x 处的
9、Hesse 矩阵为 矩阵 ：)(f nfnjinnn nxfxfxfxf fxff xf )()()()()()()()( 22212 2212 122 二次函数 cbAfT2)(A 是 n 阶对称矩阵，b 是 n 维列向量，c 是常数梯度： xf)(Hesse 矩阵: 2对向量值函数 ,每个分量 为 n 元实值函数.h 在点Tmxhh)(,)(,)(21 )(xix 的 Jacobi 矩阵为 nmjinmmnxhxhx)()()()()()()(212212111 该矩阵称为 h 在 x 的导数,记作 或 , 其中 T)()()(21xhm例 向量值函数 2121cosi,)( xexf在任
10、一点 的 Jacobi 矩阵,即导数为)(xf,2151212 4sinco)(xexff xT1.2.2 多元函数的 Taylor 展式假设 在开集 S 上连续可微,给定点 ，则 f 在点 的一阶 Taylor 展开式为)(xf Sxx)()(oxfT当 时,关于 是高阶无穷小量)(o0假设 在开集 S 上二次连续可微,则 f 在点 的二阶 Taylor 展开式为xf Sx)()()(21)()( 22xoxf TT 当 时,关于 是高阶无穷小量2xo021.2.3 方向导与最速下降方向在点 处沿方向 d 的变化率用 方向导数 表示.)(xf在 处沿方向 d 的方向导数 定义为极限:);(d
11、xDf)(lim0xf对于可微函数,方向导数等于梯度与方向的内积,即 dfxfT)(;(在点 处下降最快的方向,称为 最速下降方向 ,它是 在点 处的负梯度方向:)(xf )(xf)(xfd1.3 凸分析初步1.3.1 凸集的定义、举例(常见凸集)及性质定义：设 S 为 n 维欧氏空间 中一个集合若对 S 中任意两点，联结它们的线段仍nR属于 S；换言之，对 S 中任意两点 , 及每个实数 ，都有)1(x21,0x)2(则称 S 为凸集6常见凸集： 集合 为凸集（p 为 n 维列向量， 为实数）|xHT 集合 H 称为 中的超平面，故超平面为凸集nR 集合 为凸集|集合 称为半空间，故半空间为
12、凸集 集合 为凸集（d 是给定的非零向量， 是定点）0,|)0(xL )0(x集合 称为射线,故射线为凸集.证明：对任意两点 及每一个 ，必有)2(1, 1,dx)0()1(dx2)0()2(以及 xx )( )()1( 21)0 2)0(2()由于 ，因此有21Lxx)()(凸集的性质:设 和 为 中的两个凸集, 是实数,则1S2nR(1) 为凸集;|1Sx(2) 为凸集;21(3) 为凸集;,| 2)(1)(2)( Sx(4) 为凸集.121xS凸锥和多面集定义: 设有集合 ，若对 C 中每一点 x，当 取任何非负数时，都有 ,则nRCx称 C 为 锥 .又若 C 为凸集，则称 C 为 凸
13、锥 例 向量集 的所有非负线性组合构成的集合)()2(1,k kiii ,21,0|1)( 为凸锥定义 有限个半空间的交 称为 多面集 |bAx7例: 集合 为多面集0,1,42|221 xxxS若 b=0，则多面集 也是凸锥，称为多面锥0|Ax极点和极方向定义: 设 S 为非空凸集， ，若 x 不能表示成 S 中两个不同点的凸组合；换言之，S若假设, )2()1(xx)2(1必推得 ，则称 x 是凸集 S 的 极点 定义: 设 S 为非空凸集，d 为非零向量，如果对 S 中的每一个 x，都有射线,则称向量 d 为 S 的方向x0|又设 和 是 S 的两个方向，若对任何正数 ，有 , 则称 和
14、)1()2( )2()1(d)1(是两个不同的方向)2(d若 S 的方向 d 不能表示成该集合的两个不同方向的正的线性组合，则称 d 为 S 的极方向8注意:有界集不存在方向，因而也不存在极方向对于无界集才有方向的概念多面集的一个重要性质表示定理：设 为非空多面集，则有：0,|xbAS(l)极点集非空，且存在有限个极点 .)()1(,kx(2)极方向集合为空集的充要条件是 S 有界若 S 无界，则存在有限个极方向.)()1(,ld(3) 的充要条件是: Sx， ， ， .ljjkj1)(1)(kj1kjj ,21,0ljj ,21,01.3.2 凸集分离定理及其应用(择一定理)凸集的另一个重要
15、性质分离定理集合的分离：指对于两个集合 和 ，存在一个超平面 H，使 在 H 的一边， 在1S2 1S2SH 的另一边如果超平面的方程为 ，那么对位于 H 某一边的点 x，必有 ，而对位xpT pT于 H 另一边的点 x，必有 .定义:设 和 是两个非空集合， 为超平面如对每个 ,有1S2 |xpHT 1Sx，对每个 ，有 (或情形恰好相反），则称 H 分离集合 和 .xpTxxpT 2定理(凸集分离定理)：设 和 是两个非空凸集， ，则存在超平面 H，1S2 21S使得 ， .|1HT |xTS1 S2 H9凸集分离定理的另一种表述方法：设 和 是两个非空凸集， ，则存在1S2 21S非零向量 p，使 |sup|inf21xxpTT凸集分
