第1章 预备知识
§1.1 基本概念与术语
1.1.1 数学规划问题举例
例1 食谱（配食）问题
? 假设市场上有n种不同的食物，第j种食物每个单位的销售价为cj(j?1,2,?,n)。 ? 人体在正常生命活动过程中需要m种基本的营养成分。为了保证人体的健康，一个人
每天至少需要摄入第i种营养成分bi(i?1,2,?,m)个单位。 ? 第j种食物的每个单位包含第i种营养成分aij个单位。
食谱（配食）问题就是要求在满足人体基本营养需求的前提下，寻找最经济的配食方案（食谱）。
建立食谱的数学模型
引入决策变量xi ：食谱中第i种食物的单位数量
min?cixi
i?1ni?1,2,?,m s.t. ?aijxj?bi, j?1nxj?0, j?1,2,?,n
例2 选址与运输问题
? 假设某大型建筑公司有m个项目在不同的地点同时开工建设.记工地的位置分别为
Pi?(ai,bi), i?1,2,?,m.
? 第i个工地对某种建筑材料的日用量是已知的（比如水泥的日用量（单位：t）为Di）． ? 该公司准备分别在T1?(x1,y1)和T2?(x2,y2)两个地点建造临时料场，并且保证临时料
场对材料的日储量（单位：t）分别为M1和M2．
如何为该公司确定临时料场的位置，并且制订每天的材料供应计划，使建筑材料的总体运输负担最小？ 建立选址与运输问题的数学模型
引入决策变量：位置变量(xk,yk),从临时料场向各工地运送的材料数量
zki(k?1,2; i?1,2,?,m).
min??zki(xk?ai)2?(yk?bi)2
k?1i?12ms.t. ?zki?Mk, k?1,2
i?1mk?1?zki?Di, i?1,2,?,m
2zki?0, (xk,yk) ?R2 , k?1,2,i?1,2,?,m
例3 生产计划问题
? 某企业向客户提供一种机器，第1季度末需要交货c1台，第2季度末需要交货c2台，
第3季度末需要交货c3台．
? 该企业最大生产能力是每季度生产b 台.
? 若用x表示该企业在某季度生产的机器台数，则生产费用（单位：元）可以用函数
f(x)?a1x?a2x?来描述.
? 企业需为每台机器在每个季度多支付p元的存储费． ? 假设在第一个季度开始时无存货，不允许缺货.
如何制订生产计划，确定在每个季度应该生产多少台机器，才能既履行交货合同，又使企业总体费用最少？ 建立生产计划的数学模型
决策变量：用xi(i?1,2,3)表示企业在第i个季度生产的机器数量． 合同规定的总数量：x1?x2?x3?c1?c2?c3
每个季度生产数量要求：每个季度生产数量xj不大于最大生产能力b ，不少于该季度末的交货量cj与该季度初的库存量Ij之差.
第j个季度初库存量：Ij??(xi?ci), j?1,2,3 （I1=0）
i?j变量隐含要求：xj?0(j?1,2,3)，并且取整数． 企业总费用：所有季度生产与存储费用之和
33F(x)??f(xi)??pIi
i?1i?2minF(x)??(a1?(3?i)p)xi?a2xi?)?p(2c1?c2)
i?13s.t. ?xj??cj
j?1j?133x1?c1
x1?x2?c1?c2
0?xj?b,xj?Z,j?1,2,3(Z表示所有整数的集合)
1.1.2 数学规划问题的模型与分类
? 形成一个最优化问题的数学模型
? 首先需要辨识目标，确定优化标准，即待研究系统的性能定量描述，如成本、数量、
利润、时间、能量等；
? 其次用合适的决策变量描述系统的特征量，并将目标表示成决策变量的函数（目标
函数，objective function )；
? 此外需确定变量所受的范围限制，由若干个函数的等式或者不等式来定义（约束函
数，constraint functions)．
? 最优化问题指在决策变量所受限制范围内，对相关的目标函数进行极小化或者极大化.
f(x) minnx?Rs.t. gi(x)?0, i?I
hj(x)?0, j?E
满足约束条件的点称为可行点（feasible point ) ，所有可行点的集合称为可行域（feasible region) ，记为S.
? 当S?R，无约束优化问题;否则,约束优化问题．
? f,gi和hi都是线性函数，为线性规划（linear programming，LP);否则为非线性规划（nonlinear programming, NLP）.
? 所有变量取整数，称为整数规划（integer programming);允许一部分变量取整数，另一部分变量取实数，为混合整数规划（mixed integer programming, MIP）.
? 从一个连通无限集合（可行域）中寻找最优解, 称为连续优化(continuous optimization)问题；从一个有限的集合或者离散的集合中寻找最优解，称为组合优化（combinatorial optimization)，或者离散优化（discrete optimization）．
? 存在多个目标，即目标函数f(x)取一个向量值函数，称多目标规划（multi-objective programming)，或多目标优化．
? 最优化问题中出现的参数是完全确定的，称为确定型优化（deterministic optimization）问题;否则称为非确定型优化（uncertain optimization) 问题，包括了随机规划（stochastic programming）、模糊规划（fuzzy programming ) 等特殊情形．
n1.1.3 最优解的概念
定义: 设f(x)为目标函数，S为可行域，x?S，若对每个x?S，成立f(x)?f(x)，则称x为f(x)在S上的全局极小点。
定义: 设f(x)为目标函数，S为可行域，若存在x?S的
??0邻域
N(x,?)?{x|x?x??}，使得对每个x?S?N(x,?)成立f(x)?f(x)，则称x为f(x)在S上的局部极小点。
? 全局极小点也是局部极小点，而局部极小点不一定是全局极小点. ? 大多数的优化算法通常只是寻找局部最优解.
? 对于某些特殊情形，如凸规划，局部极小点也是全局极小点.
§1.2 多元函数分析
1.2.1 梯度及Hesse矩阵
函数f(x)在x处的梯度为n维列向量：
??f(x)?f(x)?f(x)??f(x)??,,?,?
?x2?xn???x1函数f(x)在x处的Hesse矩阵为n?n矩阵?f(x)：
2T??2f(x)??x?x?211??f(x)2?f(x)???x2?x1??2???f(x)??x?x?n1二次函数
?2f(x)??x1?x2?2f(x)??x2?x2?2?f(x)??xn?x2?2f(x)??x1?xn??2?f(x)??2?f(x)????? ?x2?x2???xi?xj??n?n????2f(x)??xn?xn??f(x)?1TxAx?bTx?c 2A是n阶对称矩阵，b是n维列向量，c是常数．
梯度：?f(x)?Ax?b Hesse矩阵: ?f(x)?A
对向量值函数h(x)??h1(x),h2(x),?,hm(x)?,每个分量hi(x)为n元实值函数.h在点x
T2的Jacobi矩阵为
??h1(x)??x1???h2(x)??x1????h(x)?m???x1?h1(x)??x2?h2(x)??x2??hm(x)??x2'?h1(x)??xn???h2(x)???hi(x)??xn????
?xj???m?n?????hm(x)??xn??T该矩阵称为h在x的导数,记作h(x)或?h(x), 其中
?h(x)???h1(x),?h2(x),?,?hm(x)?
?sinx1?cosx2??? 2x1?x2e例 向量值函数f(x)?f(x1,x2)???2??2x1?x1x2??f(x)在任一点(x1,x2)的Jacobi矩阵,即导数为
?cosx12x1?x2f'(x)??f(x)T??2e???4x1?x2?sinx2?e2x1?x2?? x1??1.2.2 多元函数的Taylor展式
假设f(x)在开集S上连续可微,给定点x?S，则f在点x的一阶Taylor展开式为
f(x)?f(x)??f(x)T(x?x)?o(x?x)
o(x?x)当x?x?0时,关于x?x是高阶无穷小量．
假设f(x)在开集S上二次连续可微,则f在点x?S的二阶Taylor展开式为
21f(x)?f(x)??f(x)T(x?x)?(x?x)T?2f(x)(x?x)?o(x?x)
2o(x?x)当x?x?0时,关于x?x是高阶无穷小量．
2221.2.3 方向导与最速下降方向
f(x)在点x处沿方向d的变化率用方向导数表示. f(x)在x处沿方向d的方向导数Df(x;d)定义为极限:
Df(x;d)?limf(x??d)?f(x)??0?
对于可微函数,方向导数等于梯度与方向的内积,即
Df(x;d)??f(x)Td
f(x)在点x处下降最快的方向,称为最速下降方向,它是f(x)在点x处的负梯度方
向:
d???f(x)?f(x)
§1.3 凸分析初步
1.3.1 凸集的定义、举例(常见凸集)及性质
定义：设S为n维欧氏空间R中一个集合．若对S中任意两点，联结它们的线段仍属于S；换言之，对S中任意两点x,x(1)(2)n及每个实数??[0,1]，都有
?x(1)?(1??)x(2)?S
第1章高等数学规划预备知识
