第1章预备知识§1。

1基本概念与术语1。

1.1数学规划问题举例例1食谱（配食）问题假设市场上有n 种不同的食物，第j 种食物每个单位的销售价为),,2,1(n j c j =。

人体在正常生命活动过程中需要m 种基本的营养成分。

为了保证人体的健康，一个人每天至少需要摄入第i 种营养成分),,2,1(m i b i =个单位。

第j 种食物的每个单位包含第i 种营养成分ij a 个单位.食谱（配食)问题就是要求在满足人体基本营养需求的前提下,寻找最经济的配食方案（食谱)。

建立食谱的数学模型引入决策变量i x ：食谱中第i 种食物的单位数量i ni i x c ∑=1mins 。

t.m i b x a i j nj ij ,,2,1 ,1=≥∑=n j x j ,,2,1 ,0 =≥例2选址与运输问题● 假设某大型建筑公司有m 个项目在不同的地点同时开工建设。

记工地的位置分别为m i b a P i i i ,,2,1 ),,( ==.● 第i 个工地对某种建筑材料的日用量是已知的（比如水泥的日用量(单位:t ）为i D ）． ● 该公司准备分别在),(111y x T =和),(222y x T =两个地点建造临时料场，并且保证临时料场对材料的日储量（单位:t ）分别为1M 和2M ．如何为该公司确定临时料场的位置，并且制订每天的材料供应计划，使建筑材料的总体运输负担最小？建立选址与运输问题的数学模型引入决策变量：位置变量),(k k y x ，从临时料场向各工地运送的材料数量),,2,1 ;2,1(m i k z ki ==.∑∑-+-==21122)()(min k mi i k i k ki b y a x zs 。

t 。

2,1 ,1=≤∑=k M z k mi kim i D z i k ki ,,2,1 ,21==∑=m i k y x z k k ki ,,2,1,2,1 , R ),( ,02 ==∈≥例3生产计划问题● 某企业向客户提供一种机器，第1季度末需要交货1c 台，第2季度末需要交货2c 台，第3季度末需要交货3c 台．● 该企业最大生产能力是每季度生产b 台。

● 若用x 表示该企业在某季度生产的机器台数，则生产费用（单位：元）可以用函数αx a x a x f 21)(+=来描述。

● 企业需为每台机器在每个季度多支付p 元的存储费． ● 假设在第一个季度开始时无存货，不允许缺货.如何制订生产计划，确定在每个季度应该生产多少台机器，才能既履行交货合同，又使企业总体费用最少？建立生产计划的数学模型决策变量:用)3,2,1(=i x i 表示企业在第i 个季度生产的机器数量． 合同规定的总数量：321321c c c x x x ++=++每个季度生产数量要求：每个季度生产数量j x 不大于最大生产能力b ，不少于该季度末的交货量j c 与该季度初的库存量j I 之差.第j 个季度初库存量：3,2,1 ,)(=∑-=<j c x I ji i i j （1I =0）变量隐含要求：)3,2,1(0=≥j x j ，并且取整数． 企业总费用:所有季度生产与存储费用之和∑+∑===3231)()(i i i i pI x f x F)2()))3(()(min 213121c c p x a x p i a x F i i i +-∑+-+==αs 。

t 。

∑=∑==3131j j j j c x11c x ≥2121c c x x +≥+3,2,1,,0=∈≤≤j Z x b x j j （Z 表示所有整数的集合）1.1。

2数学规划问题的模型与分类● 形成一个最优化问题的数学模型⏹ 首先需要辨识目标，确定优化标准,即待研究系统的性能定量描述，如成本、数量、利润、时间、能量等；⏹ 其次用合适的决策变量描述系统的特征量，并将目标表示成决策变量的函数（目标函数，objectivefunction )；⏹ 此外需确定变量所受的范围限制，由若干个函数的等式或者不等式来定义（约束函数，constraintfunctions ）．● 最优化问题指在决策变量所受限制范围内，对相关的目标函数进行极小化或者极大化。

)(min nRx f x ∈ s 。

t 。

I i x g i ∈≥ ,0)(E j x h j ∈= ,0)(满足约束条件的点称为可行点（feasiblepoint ），所有可行点的集合称为可行域（feasibleregion ）,记为S 。

-当nS R =，无约束优化问题;否则，约束优化问题．-i g f ,和i h 都是线性函数,为线性规划（linearprogramming ，LP ）;否则为非线性规划（nonlinearprogramming ，NLP ）.-所有变量取整数，称为整数规划（integerprogramming )；允许一部分变量取整数，另一部分变量取实数，为混合整数规划（mixedintegerprogramming,MIP ）。

-从一个连通无限集合（可行域）中寻找最优解，称为连续优化(continuousoptimization )问题；从一个有限的集合或者离散的集合中寻找最优解，称为组合优化（combinatorialoptimization)，或者离散优化（discreteoptimization ）．-存在多个目标，即目标函数)(x f 取一个向量值函数，称多目标规划(multi —objectiveprogramming),或多目标优化．-最优化问题中出现的参数是完全确定的，称为确定型优化（deterministicoptimization ）问题;否则称为非确定型优化（uncertainoptimization)问题,包括了随机规划(stochasticprogramming ）、模糊规划（fuzzyprogramming ）等特殊情形．1。

1.3最优解的概念定义：设)(x f 为目标函数,S 为可行域，S x ∈,若对每个S x ∈，成立)()(x f x f ≥，则称x 为)(x f 在S 上的全局极小点。

定义：设)(x f 为目标函数,S 为可行域，若存在S x ∈的0>ε邻域}|{),(εε<-=x x x x N ，使得对每个),(εx N S x ⋂∈成立)()(x f x f ≥,则称x 为)(x f 在S 上的局部极小点。

● 全局极小点也是局部极小点，而局部极小点不一定是全局极小点. ● 大多数的优化算法通常只是寻找局部最优解.● 对于某些特殊情形，如凸规划，局部极小点也是全局极小点。

§1.2多元函数分析1。

2。

1梯度及Hesse 矩阵函数)(x f 在x 处的梯度为n 维列向量：Tn x x f x x f x x f x f ⎥⎦⎤⎢⎣⎡∂∂∂∂∂∂=∇)(,,)(,)()(21函数)(x f 在x 处的Hesse 矩阵为n n ⨯矩阵)(2x f ∇：n n j i n n n n n x x x f x x x f x x x f x x x f x x x f x x x f x x x f x x x f x x x f x x x f x f ⨯⎥⎥⎦⎤⎢⎢⎣⎡∂∂∂=⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂=∇)()()()()()()()()()()(222212222222122122121122二次函数c x b Ax x x f T T++=21)( A 是n 阶对称矩阵，b 是n 维列向量，c 是常数．梯度:b Ax x f +=∇)( Hesse 矩阵：A x f =∇)(2对向量值函数()Tm x h x h x h x h )(,),(),()(21 =，每个分量)(x h i 为n 元实值函数。

h 在点x 的Jacobi 矩阵为n m j i n m m m n n x x h x x h x x h x x h x x h x x h x x h x x h x x h xx h ⨯⎥⎥⎦⎤⎢⎢⎣⎡∂∂=⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂∂)()()()()()()()()()(212221212111 该矩阵称为h 在x 的导数，记作)('x h 或Tx h )(∇,其中())(,),(),()(21x h x h x h x h m ∇∇∇=∇例向量值函数⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡++==+2121221212cos sin ),()(21x x x e x x x x f x f x x )(x f 在任一点),(21x x 的Jacobi 矩阵，即导数为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡+-=∇=++1212221'42sin cos )()(2121x x x e e x x x f x f x x x x T 1.2。

2多元函数的Taylor 展式假设)(x f 在开集S 上连续可微，给定点S x ∈，则f 在点x 的一阶Taylor 展开式为)()()()()(x x o x x x f x f x f T -+-∇+=)(x x o -当0→-x x 时,关于x x -是高阶无穷小量．假设)(x f 在开集S 上二次连续可微，则f 在点S x ∈的二阶Taylor 展开式为)())(()(21)()()()(22x x o x x x f x x x x x f x f x f T T -+-∇-+-∇+=)(2x x o -当02→-x x 时，关于2x x -是高阶无穷小量．1。

2。

3方向导与最速下降方向)(x f 在点x 处沿方向d 的变化率用方向导数表示。

)(x f 在x 处沿方向d 的方向导数);(d x Df 定义为极限:λλλ)()(lim);(0x f d x f d x Df -+=→对于可微函数，方向导数等于梯度与方向的内积，即d x f d x Df T )();(∇=)(x f 在点x 处下降最快的方向，称为最速下降方向,它是)(x f 在点x 处的负梯度方向： )()(x f x f d ∇∇-=§1.3凸分析初步1.3.1凸集的定义、举例(常见凸集）及性质定义：设S 为n 维欧氏空间nR 中一个集合．若对S 中任意两点，联结它们的线段仍属于S ;换言之,对S 中任意两点)1(x ,)2(x及每个实数]1,0[∈λ,都有S x x ∈-+)2()1()1(λλ则称S 为凸集．常见凸集：①集合}|{α==x p x H T为凸集．(p 为n 维列向量，α为实数) 集合H 称为n R 中的超平面，故超平面为凸集． ②集合}|{α≤=-x p x H T 为凸集． 集合-H 称为半空间，故半空间为凸集． ③集合}0,|{)0(≥+==λλd x x x L 为凸集．(d 是给定的非零向量，)0(x 是定点）集合L 称为射线,故射线为凸集.证明:对任意两点L xx ∈)2()1(,及每一个]1,0[∈λ，必有d x x 1)0()1(λ+=d x x 2)0()2(λ+=以及dxd x d x x x ])1([ ))(1()()1(21)0(2)0(1)0()2()1(λλλλλλλλλλ-++=+-++=-+由于0)1(21≥-+λλλλ，因此有L x x ∈-+)2()1()1(λλ凸集的性质：设1S 和2S 为nR 中的两个凸集，β是实数,则 （1）}|{11S x x S ∈=ββ为凸集; （2）21S S 为凸集； （3）},|{2)2(1)1()2()1(21S x S x x x S S ∈∈+=+为凸集；（4)},|{2)2(1)1()2()1(21S x S x x x S S ∈∈-=-为凸集.凸锥和多面集定义:设有集合nR C ⊂，若对C 中每一点x ，当λ取任何非负数时，都有C x ∈λ，则称C 为锥.又若C 为凸集,则称C 为凸锥．例向量集)()2()1(,,k ααα 的所有非负线性组合构成的集合⎭⎬⎫⎩⎨⎧=≥∑=k i i ki i i ,,2,1,0|1)( λαλ 为凸锥．定义有限个半空间的交}|{b Ax x ≤称为多面集．例：集合}0,0,1,42|{212121≥≥≤-≤+=x x x x x x x S 为多面集．若b =0,则多面集}0|{≤Ax x 也是凸锥，称为多面锥．极点和极方向定义:设S 为非空凸集，S x ∈,若x 不能表示成S 中两个不同点的凸组合;换言之，若假设)2()1()1(x x x λλ-+=，S x x ∈)2()1(,必推得)2()1(x xx ==，则称x 是凸集S 的极点．定义:设S为非空凸集，d 为非零向量，如果对S 中的每一个x ,都有射线S d x ⊂≥+}0|{λλ,则称向量d 为S 的方向．又设)1(d和)2(d 是S 的两个方向，若对任何正数λ，有)2()1(d dλ≠,则称)1(d 和)2(d 是两个不同的方向．若S 的方向d 不能表示成该集合的两个不同方向的正的线性组合，则称d 为S 的极方向．注意:有界集不存在方向，因而也不存在极方向．对于无界集才有方向的概念．多面集的一个重要性质-—表示定理：设}0,|{≥==x b Ax x S 为非空多面集，则有： （l ）极点集非空，且存在有限个极点)()1(,,k xx .(2)极方向集合为空集的充要条件是S 有界．若S 无界，则存在有限个极方向)()1(,,l d d 。