运筹学课件第2章.ppt

第2章 基本概念和理论基础 第2章基本概念和理论基础 1 1数学规划模型的一般形式Minf x 目标函数s t x S 约束集合 可行集其中 S Rn f S R x S称 fS 的可行解最优解 x S 满足f x f x x S 则称x 为 fS 的全局最优解 最优解 记为g opt globaloptimum 简记为opt 最优值 x 为 fS 的最优解 则称f f x 为 fS 的最优值 最优目标函数值 fS 2 1数学规划模型的一般形式 局部最优解 x S x 的邻域N x 使满足f x f x x S N x 则称x 为 fS 的局部最优解 记为l opt localoptimum 在上述定义中 当x x 时有严格不等式成立 则分别称x 为 fS 的严格全局最优解和严格局部最优解 严格l opt 严格g opt l opt 2 1数学规划模型的一般形式 函数形式 f x gi x hj x Rn RMinf x fgh s t gi x 0 i 1 2 mhj x 0 j 1 2 l矩阵形式 Minf x f x Rn R fgh s t g x 0 g x Rn Rmh x 0 h x Rn Rl当f x gi x hj x 均为线性函数时 称其为线性规划 若其中有非线性函数时 称其为非线性规划 2 2凸集 凸函数和凸规划 1 凸集 1 凸集的概念定义1设集合S Rn 若 x 1 x 2 S 0 1 必有 x 1 1 x 2 S 则称S为凸集 规定 单点集 x 为凸集 空集 为凸集 注 x 1 1 x 2 x 2 x 1 x 2 是连接x 1 与x 2 的线段 凸集 非凸集 非凸集 2 2凸集 凸函数和凸规划 例1证明集合S x Ax b 是凸集 其中 A为m n矩阵 b为m维向量 凸组合 设x 1 x 2 x m Rn j 0 mm j 1 那么称 jx j 为x 1 x 2 x m 的j 1j 1凸组合 m比较 z jx j j 1 j R 构成线性组合 线性子空间 j 0 j 0 构成半正组合 凸锥 j 0 j 1 构成凸组合 凸集 2 2凸集 凸函数和凸规划 定理1S是凸集 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 线性无关 多胞形 单纯形 单纯形 2 2凸集 凸函数和凸规划 2 凸集的性质凸集的交集是凸集 并 凸集的内点集是凸集 逆命题是否成立 凸集的闭包是凸集 逆命题是否成立 分离与支撑 凸集边界上任意点存在支撑超平面 两个互相不交的凸集之间存在分离超平面 支撑 强分离 分离 非正常分离 2 2凸集 凸函数和凸规划 3 凸锥定义2C Rn 若x C 0 有 x C 则称C是以0为顶点的锥 如果C还是凸集 则称为凸锥 集合 0 Rn是凸锥 命题 C是凸锥 C中任意有限点的半正组合属于S 0 2 2凸集 凸函数和凸规划 2 凸函数 1 凸函数及水平集定义3设集合S Rn为凸集 函数f S R 若 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上的严格凸函数 几何意义见P27 当 f x 为凸函数 严格凸函数 时 则称f x 为凹函数 严格凹函数 严格凸函数 凸函数 严格凹函数 2 2凸集 凸函数和凸规划 定理2f x 为凸集S上的凸函数 S上任意有限点的凸组合的函数值不大于各点函数值的凸组合 思考 设f1 f2是凸函数 设 1 2 0 1f1 2f2 1f1 2f2是否凸函数 都是 2 f x max f1 x f2 x g x min f1 x f2 x 是否凸函数 不一定 2 2凸集 凸函数和凸规划 定义4设集合S Rn 函数f S R R 称S x S f x 为f x 在S上的 水平集 定理3设集合S Rn是凸集 函数f S R是凸函数 则对 R S 是凸集 注 水平集的概念相当于在地形图中 海拔高度不高于某一数值的区域 上述定理的逆不真 考虑分段函数f x 1 x 0 或0 x 0 函数非凸 但任意水平集是凸集 2 2凸集 凸函数和凸规划 2 凸函数的性质方向导数 设S Rn为非空凸集 函数f S R 再设x S d为方向 使当 0充分小时有x d S 如果lim f x d f x 存在 包括 则称f x 为在点x 沿方向d的方向导数存在 记f x d lim f x d f x 若f x 在x 可导 则f x d f x Td 2 2凸集 凸函数和凸规划 以下设S Rn为非空凸集 函数f S R2 若f凸 则f在S的内点集上连续 注 f在S上不一定连续 例如 f x 2 当 x 1 f x x2 当 x 1 3 设f凸 则对任意方向的方向导数存在 前提首先要是 可行方向 4 设S是开集 f在S上可微 则f凸 x S 有f x f x fT x x x x S 5 设S是开集 f在S上二次可微 则 f凸 x S 2f x 半正定 若 x S 2f x 正定 则f严格凸 2 2凸集 凸函数和凸规划 例 f x x12 2x1x2 2x22 10 x1 4f x 3x12 x1x2 x22 2x32 2x2x3 26f x 3x12 ax1x2 2x22 4x1 6 a 5 4 5 2 2凸集 凸函数和凸规划 3 凸规划当 fS 中 S为凸集 f是S上的凸函数 求min 时 称 fS 为凸规划 对于 fgh 当f gi为凸函数 hj为线性函数时 fgh 为凸规划 定理4设集合S Rn为凸集 函数f S R f x 为凸集S上的凸函数 x 为问题 fs 的l opt 则x 为g opt 又如果f是严格凸函数 那么x 是 fs 的唯一g opt 2 3多面体 极点 极方向 1 多面体 有限个半闭空间的交例 S x Rn Ax b x 0 2 3多面体 极点 极方向 2 多面体的极点 顶点 x S 不存在S中的另外两个点x 1 和x 2 及 0 1 使x x 1 1 x 2 3 方向 x S d Rn d 0及 0 总有x d S 可行方向 其中 当d 1 d 2 0 时 称d 1 和d 2 同方向 4 极方向 方向d不能表示为两个不同方向的组合 d d 1 d 2 2 3多面体 极点 极方向 定理5 极点特征 设A满秩 x是S极点的充分必要条件是 存在分解A B N 其中B为m阶非奇异矩阵 使xT xBT xNT 这里xB B 1b 0 xN 0 S中必存在有限多个极点 Cnm 2 3多面体 极点 极方向 定理6 极方向特征 设A p1 p2 pn 秩为m d是S极方向的充分必要条件是 存在分解A B N 其中B为m阶非奇异矩阵 对于N中的列向量pj使B 1pj 0 dT dBT dNT 这里dB B 1pj dN 0 1 0 TjS中必存在有限多个极方向 n m Cnm 例2考虑多面体S x Rn Ax b x 0 其中3210065A 21010b 400300175即3x1 2x2 x3 652x1 x2 x4 403x2 x5 75x1 x2 x3 x4 x5 0 例题 32100A p1 p2 p3 p4 p5 2101003001A矩阵包含以下10个3 3的子矩阵 B1 p1 p2 p3 B2 p1 p2 p4 B3 p1 p2 p5 B4 p1 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 例题 其中 B4 0 因而B4不能构成极点和极方向 其余均为非奇异方阵 因此该问题共有9个可构成极点 极方向的子矩阵 我们称之为基 对于基B3 p1 p2 p5 令x3 0 x4 0 在等式约束中令x3 0 x4 0 解线性方程组3x1 2x2 0 x5 652x1 x2 0 x5 400 x1 3x2 x5 75得到x1 15 x2 10 x5 45 对应的极点x x1 x2 x3 x4 x5 T 15 10 0 0 45 T 例题 类似可得到极点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 而x 3 0 32 5 0 7 5 22 5 T 对应B9 x 4 65 3 0 0 10 3 75 T 对应B6 x 5 7 5 25 7 5 0 0 T 对应B1 x 6 0 40 15 0 45 T