《第二章 最优化-线性规划.ppt》由会员分享，可在线阅读，更多相关《第二章 最优化-线性规划.ppt（171页珍藏版）》请在金锄头文库上搜索。
1、第二章线性规划 2 2 1凸集与凸函数 3 凸集 定义2 1 1设集合DRn 若对于任意点x y D 及实数a 0 a 1 都有ax 1 a y D 则称集合D为凸集 常见的凸集 单点集 x 空集 整个欧式空间Rn 超平面H x Rn a1x1 a2x2 anxn b 半空间H x Rn a1x1 a2x2 anxn b 实心圆 实心球 实心长方体等都是凸集 4 凸集 从直观上看 没有凹入部分 或没有空洞的是凸集 几何解释为 集合D中任两点连线上的每一点仍在D中 则D为凸集 5 凸集的例 例2 1 2超球 x r为凸集证明设x y为超球中任意两点 0 a 1 则有 ax 1 a y a x 1
2、 a y ar 1 a r r 即点ax 1 a y属于超球 所以超球为凸集 6 凸集的性质 i 有限个 可以改成无限 凸集的交集为凸集 即 若Dj j J 是凸集 则它们的交集D x x Dj j J 是凸集 ii 设D是凸集 b是一实数 则下面集合是凸集bD y y bx x D 7 凸集的性质 iii 设D1 D2是凸集 则D1与D2的和集D1 D2 y y x z x D1 z D2 是凸集 注 和集与并集有很大的区别 凸集的并集未必是凸集 而凸集的和集是凸集 例 D1 x 0 T x R 表示x轴上的点 D2 0 y T y R 表示y轴上的点 则D1 D2表示两个轴的所有点 它不是
3、凸集 D1 D2 R2是凸集 8 推论凸集的线性组合是凸集 定义2 1 2设xi Rn i 1 k 实数li 0 则称为x1 x2 xk的凸组合 容易证明 凸集中任意有限个点的凸组合仍然在该凸集中 两点的凸组合 三点的凸组合 多点的凸组合 9 极点 定义2 1 3设D为凸集 x D 若D中不存在两个相异的点y z及某一实数a 0 1 使得x ay 1 a z则称x为D的极点 凸集 极点 凸集 极点 10 极点 例D x Rn x a a 0 则 x a上的点均为极点 证明 设 x a 若存在y z D及a 0 1 使得x ay 1 a z 则a2 x 2 a2 y 2 1 a 2 z 2 2a
4、 1 a y z a2 不等式取等号 必须 y z a 容易证明y z x 根据定义可知 x为极点 11 凸函数 定义2 1 4设函数f x 定义在凸集DRn上 若对任意的x y D 及任意的a 0 1 都有f ax 1 a y af x 1 a f y 则称函数f x 为凸集D上的凸函数 12 凸函数 定义2 1 5设函数f x 定义在凸集DRn上 若对任意的x y D x y 及任意的a 0 1 都有f ax 1 a y af x 1 a f y 则称函数f x 为凸集D上的严格凸函数 将上述定义中的不等式反向 可以得到凹函数和严格凹函数的定义 13 凸函数的例 例2 1 3设f x x
5、1 2 试证明f x 在 上是严格凸函数 证明 设x y R 且x y a 0 1 都有f ax 1 a y af x 1 a f y ax 1 a y 1 2 a x 1 2 1 a y 1 2 a 1 a x y 2 0 因此f x 在 上是严格凸函数 14 凸函数的几何性质 对一元函数f x 在几何上af x1 1 a f x2 0 a 1 表示连接 x1 f x1 x2 f x2 的线段 f ax1 1 a x2 表示在点ax1 1 a x2处的函数值 所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方 对于一元凸函数f x 可以发现 位于函数曲线上方的图形是凸集 事实
6、上这一结论对于多元函数也是成立的 而且是充要条件 即有下面的定理 15 凸函数的性质 i 设f x 是凸集DRn上的凸函数 实数k 0 则kf x 也是D上的凸函数 ii 设f1 x f2 x 是凸集DRn上的凸函数 实数l m 0 则lf1 x mf2 x 也是D上的凸函数 iii 设f x 是凸集DRn上的凸函数 b为实数 则水平集S f b x x D f x b 是凸集 下面的图形给出了凸函数f x y x4 3x2 y4 y2 xy的等值线 f x y 2 4 6 8 10 12 的图形 可以看出水平集为凸集 16 凸函数的性质 17 凸函数的判断 定理2 1 1设f x 定义在凸集
7、DRn上 x y D 令F t f tx 1 t y t 0 1 则 该定理的几何意义是 凸函数上任意两点之间的部分是一段向下凸的弧线 i f x 是凸集D上的凸函数的充要条件是对任意的x y D 一元函数F t 为 0 1 上的凸函数 ii f x 是凸集D上的严格凸函数的充要条件是对任意的x y D x y 一元函数F t 为 0 1 上的严格凸函数 18 凸函数的判断 19 一阶条件 定理2 1 2 一阶条件 设在凸集DRn上f x 可微 则f x 在D上为凸函数的充要条件是对任意的x y D 都有f y f x f x T y x 定理2 1 3 一阶条件 设在凸集DRn上f x 可微
8、 则f x 在D上为严格凸函数的充要条件是对任意的x y D x y 都有f y f x f x T y x 20 二阶条件 设在开凸集DRn上f x 可微 则 i f x 是D内的凸函数的充要条件为 在D内任一点x处 f x 的Hesse矩阵G x 半正定 其中 ii 若在D内G x 正定 则f x 在D内是严格凸函数 21 凸规划 定义2 1 6设DRn为凸集 则f x 为D上的凸函数 则称规划问题minf x s t x D为凸规划问题 定理2 1 5 i 凸规划的任一局部极小点x是整体极小点 全体极小点组成凸集 ii 若f x 是DRn上的严格凸函数 且凸规划问题minf x s t
9、x D的整体极小点存在 则整体极小点唯一 22 2 2线性规划的标准型与基本概念 23 线性规划的一般形式 min max c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn 或 b1a21x1 a22x2 a2nxn 或 b2 am1x1 am2x2 amnxn 或 bmx1 x2 xn 0 24 线性规划的标准型 minc1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0其中bi 0 在标准形式中目标函数一律改为最大化或最小化 此处我们统一为最小
10、化 约束条件 非负约束条件除外 一律化成等式 且要求其右端项大于等于零 25 矩阵 向量形式的标准型 mincTx LP s t Ax bx 0 其中c c1 c2 cn T x x1 x2 xn T b b1 b2 bm T c 价格向量A 约束矩阵b 右端向量 26 矩阵 向量形式的标准型 记A p1 p2 pn 其中pj a1j a2j amj T 线性规划 LP 又可以表示为 27 线性规划解的情况 满足约束条件的向量x是可行解 全体可行解构成可行域D D F时但目标函数无下界时 称线性规划 LP 无界或无最优解 D F时 称线性规划无可行解 D F时若目标函数有下界 可以证明线性规划
11、 LP 必有最优解 28 可行域为凸集 定理2 2 1线性规划问题mincTx LP s t Ax bx 0的可行域D为凸集 证明任取x y D 则有Ax b x 0 Ay b y 0 对任意的a 0 1 设z ax 1 a y 则z 0 且Az A ax 1 a y aAx 1 a Ay ab 1 a b b因此z DD为凸集 29 一般形式转化为标准型 i 极大 极小maxf x min f x ii 若约束条件是小于等于型 则在该约束条件不等式左边加上一个新变量 称为松弛变量 将不等式改为等式 如 iii 若约束条件是大于等于型 则在该约束条件不等式左边减去一个新变量 称为剩余变量 将不
12、等式改为等式 如 30 一般形式转化为标准型 iv 若某个约束方程右端项 则在约束方程两端乘以 1 不等号改变方向 然后再将不等式化为等式 v 若变量xj无非负约束 则引入非负变量xj 0 xj 0 令xj xj xj 31 例将线性规划miny 2x1 x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0 x3是自由变量化为标准型 解 令x3 x3 x3 得到标准型miny 2x1 x2 3x3 3x3 s t x1 x2 x3 x3 x4 7x1 x2 x3 x3 x5 2 3x1 x2 2x3 2x3 5x1 x2 x3 x3 x4 x5
13、0 32 例将线性规划maxy 250 x1 350 x2s t 5x1 6x2 2508x1 6x2 30010 x1 20 x2 700 x1 0 x2 0化为标准型 解 令x2 x2 得到标准型min y 250 x1 350 x2 s t 5x1 6x2 x3 2508x1 6x2 x4 300 10 x1 20 x2 700 x1 0 x2 0 x3 0 x4 0 33 基本概念 设约束矩阵A的秩为m 行满秩 且m n 则A中必存在m阶非奇异子阵B 不妨设B p1 p2 pm 称B为线性规划问题 LP 的一个基矩阵 或称为基 基矩阵中的列向量称为基向量 对应的决策变量称为基变量 其余
14、变量称为非基变量 34 基本概念 在约束方程组取定基矩阵B p1 p2 pm 之后 令非基变量均为0 得到的方程组p1x1 p2x2 pmxm b有唯一解 这样得到约束方程组的一个解向量x x1 x2 xm T通过这种方法得到的满足约束方程组的解称为基矩阵B对应的基解 35 基本概念 如果基解又满足非负条件 则称之为基可行解 此时的基B称为可行基 基可行解中非零分量的个数不会超过m 若基可行解中非零分量的个数恰为m 称此基可行解为非退化的基可行解 否则称为退化的基可行解 若一个线性规划的所有基可行解都是非退化的 称此线性规划是非退化的 线性规划 LP 的基解个数不会超过 36 例考虑线性规划m
15、in2x1 x2s t x1 x2 x3 5 x1 x2 x4 02x1 2x2 x5 22x1 x2 x3 x4 x5 0 该线性规划有5个变量 3个约束 最多个基解 事实上 该线性规划只有7个基解 p1 p2线性相关 下面列出7个基解及对应的基 p1 p3 p4 11 0 6 11 0 T不可行 p1 p3 p5 0 0 5 0 22 T退化 p1 p4 p5 5 0 0 5 12 T非退化 p2 p3 p4 0 11 6 11 0 T不可行 p2 p3 p5 0 0 5 0 22 T退化 p2 p4 p5 0 5 0 5 12 T非退化 p3 p4 p5 0 0 5 0 22 T退化 3
16、7 2 3线性规划的基本定理 38 本节的基本定理要说明要找线性规划的最优解只需在基可行解中选择就可以了 这样将选择的范围控制在有限个 定理2 3 1设x是标准型线性规划 LP 的可行解 x为 LP 的基可行解的充要条件是 x的正分量对应的系数列向量线性无关 39 定理2 3 2设x是标准型线性规划 LP 的可行解 x为 LP 的基可行解的充要条件是 x为可行域D的极点 证明 必要性不妨设x x1 x2 xm 0 0 T是 LP 的基可行解 且x1 x2 xm是基变量 假设有u v D 0 a 1 使得x au 1 a v当m 1 j n时 0 xj auj 1 a vj 因此uj vj 0 所以p1u1 p2u2 pmum p1v1 p2v2 pmvm b从而p1 u1 v1 p2 u2 v2 pm um vm 0由于x是基可行解 所以p1 p2 pm线性无关 uj vj i 1 2 m 从而u v 这说明x为极点 40 充分性设x x1 x2 xk 0 0 T是可行域的极点 其中x1 x2 xk 0 假设x不是基可行解 于是p1 p2 pk线性相关 即有一组不全为0的数a1 a2
