线性规划问题基本概念与基本理论

1、关于线性规划问题基本概念和基本理论第一张，PPT共二十五页，创作于2022年6月第二章 基本概念和理论基础2.1 数学规划模型的一般形式 min f(x) -目标函数 s.t. xS -约束集合，可行集其中，S R n，f :S R，xS称（f S )的可行解最优解: x*S，满足f (x*) f (x), xS。则称 x*为(f S)的全局最优解(最优解), 记 g.opt.(global optimum),简记 opt.最优值: x*为(f S)的最优解, 则称 f * = f (x*) 为 (f S)的最优值(最优目标函数值)( f S )第二张，PPT共二十五页，创作于2022年6月2

2、.1 数学规划模型的一般形式（续）局部最优解: x*S， x* 的邻域 N(x*) ，使满足 f (x*) f (x), x S N(x*) 。则称 x*为(f S)的局部最优解,记 l .opt.(local optimum)在上述定义中，当x x* 时有严格不等式成立，则分别称 x* 为(f S)的严格全局最优解和严格局部最优解。严格l .opt .严格g .opt .l .opt .第三张，PPT共二十五页，创作于2022年6月2.1 数学规划模型的一般形式（续）函数形式: f(x), gi(x) , hj(x) : RnR min f(x)(fgh) s.t. gi(x) 0 , i

3、= 1,2,m hj(x) = 0 , j = 1,2,l矩阵形式: min f(x) ，f(x) : RnR(fgh) s.t. g(x) 0 , g(x) : RnRm h(x) = 0 , h(x) : RnRl 当 f(x), gi(x) , hj(x)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。第四张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划一、凸集1、凸集的概念：定义：设集合 S Rn，若x(1), x(2)S, 0,1，必有 x(1)(1- ) x(2) S ，则称 S 为凸集。规定：单点集 x 为凸集，空集为凸集。注: x(1)(1

4、- ) x(2) = x(2)(x(1)- x(2) 是连接 x(1)与x(2)的线段 。凸集非凸集非凸集第五张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)一、凸集 1、凸集的概念：例:证明集合 S = xAx = b 是凸集。其中，A为 mn矩阵，b为m维向量。凸组合：设 x(1) , x(2) , , x(m) Rn, j 0 m m j =1, 那么称 j x(j) 为x(1), x(2), , x(m)的 j =1 j = 1凸组合。 m比较: z = j x(j) j =1jR 构成线性组合 线性子空间j0 , j 0 构成半正组合 凸锥j0 , j =

5、0 构成凸组合 凸集第六张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)一、凸集 1、凸集的概念：定理：S是凸集S中任意有限点的凸组合属于S多胞形 H(x(1) , x(2) , , x(m) )： 由 x(1) , x(2) , , x(m) 的所有凸组合构成。单纯形：若多胞形 H(x(1) , x(2) , , x(m) )满足， x(2)-x(1) , x(3) -x(1) , , x(m)- x(1) 线性无关。多胞形单纯形单纯形第七张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)一、凸集 2、凸集的性质：凸集的交集是凸集；（并？

6、）凸集的内点集是凸集；（逆命题是否成立？）凸集的闭包是凸集。 （逆命题是否成立？）分离与支撑： 凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面支撑强分离分离非正常分离第八张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)一、凸集 3、凸锥：定义：C Rn, 若 x C, 0 有 x C, 则称 C 是以 0 为顶点的锥。如果 C 还是凸集，则称为凸锥。集合 0 、Rn 是凸锥。命题：C是凸锥C中任意有限点的半正组合属于S0第九张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)二、凸函数 1、凸函数及水平集定义: 设集合

7、S Rn 为凸集，函数 f :SR 若 x(1), x(2) S, ( 0 , 1 ) ，均有 f( x(1)(1- ) x(2) ) f(x(1)+(1- )f(x(2) ， 则称 f(x) 为凸集 S 上的凸函数。 若进一步有上面不等式以严格不等式成立，则称 f(x) 为凸集 S 上的严格凸函数。当- f(x) 为凸函数（严格凸函数）时，则称 f(x) 为凹函数（严格凹函数）。严格凸函数凸函数严格凹函数第十张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)二、凸函数 1、凸函数及水平集：定理： f(x) 为凸集 S 上的凸函数 S 上任意有限点的凸组合的函数值不大

8、于各点函数值的凸组合。思考：设f1, f2是凸函数，设1, 2 0, 1f1+2f2 , 1f1 - 2f2是否凸函数？f(x)= max f1(x) , f2 (x) , g(x)= min f1(x) , f2 (x) 是否凸函数？ 第十一张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)二、凸函数 1、凸函数及水平集：定义：设集合 S Rn ，函数 f :SR， R ， 称 S = x Sf(x) 为 f(x) 在 S 上 的 水平集。定理：设集合 S Rn 是凸集，函数 f :SR是凸函数，则对 R ，S 是凸集。注：水平集的概念相当于在地形图中，海拔高度不高

9、于某一数值的区域。上述定理的逆不真。 考虑分段函数f(x)=1(x0)或0(x 0 充分小时有 x*+d S, 如果 lim f(x*+ d )-f(x*) / 存在（包括 ） 则称 f(x) 为在点沿方向的方向导数存在，记 f (x*;d) = lim f(x*+ d )-f(x*) / 若 f(x) 在 x* 可导，则 f (x*;d) = f (x*) Td .第十三张，PPT共二十五页，创作于2022年6月2.2 凸集、凸函数和凸规划(续)二、凸函数 2、凸函数的性质：以下设 S Rn 为非空凸集，函数 f :SR2）若f 凸，则 f 在 S 的内点集上连续； 注： f 在 S 上不一

10、定连续。 例: f(x)2(当x=1)； f(x)x2 (当x 0 , 总有 x + d S. d(1) = d(2) ( 0) 时，称 d(1)和d(2)同方向。4) 极方向：方向 d 不能表示为两个不同方向的组合 ( d = d(1)+d(2) ) .第十八张，PPT共二十五页，创作于2022年6月2.3 多面体、极点、极方向多面体 S = xRnAx = b , x0 的极点和极方向定理1（极点特征）设 A 满秩，x 是 S 极点的充分必要条件是: 存在分解 A = B , N ，其中B为m阶非奇异矩阵，使 xT = xBT, xNT , 这里 xB = B-1b0, xN =0.S中必

11、存在有限多个极点。( Cnm )第十九张，PPT共二十五页，创作于2022年6月2.3 多面体、极点、极方向多面体 S = xRnAx = b , x0 的极点和极方向定理2（极方向特征）设 A = p1, p2, ,pn满秩，d 是 S 极方向的充分必要条件是: 存在分解 A = B , N ，其中B为m阶非奇异矩阵，对于N中的列向量 pj 使 B-1pj0, dT = dBT, dNT , 这里 j dB = -B-1pj , dN = (0, . , 1, ,0)TS中必存在有限多个极方向。( (n-m)Cnm )第二十张，PPT共二十五页，创作于2022年6月考虑多面体 S = xRn

12、Ax = b , x0 ，其中 3 2 1 0 0 65 A = 2 1 0 1 0 b = 40 0 3 0 0 1 75 即 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0 例题第二十一张，PPT共二十五页，创作于2022年6月 3 2 1 0 0A = P1 , P2 , P3 , P4 , P5 = 2 1 0 1 0 0 3 0 0 1 A矩阵包含以下10个33的子矩阵： B1=p1 ，p2 ，p3 B2=p1 ，p2 ，p4 B3=p1 ，p2 ，p5 B4=p1 ，

13、p3 ，p4 B5=p1 ，p3 ，p5 B6=p1 ，p4 ，p5 B7=p2 ，p3 ，p4 B8=p2 ，p3 ，p5 B9=p2 ，p4 ，p5 B10=p3 ，p4 ，p5 例题 第二十二张，PPT共二十五页，创作于2022年6月 其中B4= 0，因而B4不能构成极点和极方向。其余均为非奇异方阵，因此该问题共有9个可构成极点、极方向的子矩阵，我们称之为基。 对于基B3=p1 ，p2 ，p5，令x3 = 0， x4 = 0，在等式约束中令x3 = 0，x4 = 0，解线性方程组： 3 x1 + 2 x2 + 0 x5 = 65 2 x1 + x2 + 0 x5 = 40 0 x1 + 3 x2 + x5 = 75 得到x1 =15，x2 = 10，x5 = 45，对应的极点： x = (x1，x2，x3，x4，x5 )T = (15，10，0，0，45 )T例题 第二十三张，PPT共二十五页，创作于2022年6月 类似可得到极点 x(2) = (5, 25, 0, 5, 0 )T （对应B2） x(7) = (20, 0, 5, 0, 75 )T （对应B5） x(8) = (0, 25, 15, 15, 0 )T （对应B7） x(9) = (0, 0, 65, 40, 75 )T （对应B10）