运筹学课件第2.pptVIP

第 2 章 基本概念 和 理论基础 第2章 基本概念和理论基础 1.1数学规划模型的一般形式 Min f(x) ——目标函数 s.t. x?S ——约束集合，可行集 其中，S ? Rn，f :S ? R，x?S称（f S )的可行解 最优解: x*?S，满足f (x*)≤ f (x), ? x?S，则称 x*为(f S)的全局最优解(最优解),记为 g.opt.(global optimum),简记 为opt. 。 最优值: x*为(f S)的最优解, 则称 f * = f (x*) 为 (f S)的最优值(最优目标函数值) 。 ( f S) 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 . 2.1数学规划模型的一般形式 函数形式: f (x), gi(x) , hj(x) : Rn?R Min f (x) (fgh) s.t. gi(x) ≤ 0 , i = 1,2,…,m hj(x) = 0 , j = 1,2,…,l 矩阵形式: Min f (x) ， f (x) : Rn?R (fgh) s.t. g(x) ≤ 0 , g(x) : Rn?Rm h(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 ， m m ? ?j =1, 那么称 ? ?j x(j) 为x(1), x(2), … , x(m)的 j =1 j = 1 凸组合。 m 比较: z = ? ?j x(j) j =1 ?j?R ——构成线性组合 —— 线性子空间 ?j≥0 , ? ?j 0 —— 构成半正组合 —— 凸锥 ?j≥0 , ? ?j =1 —— 构成凸组合 —— 凸集 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) 线性无关。 多胞形 单纯形 单纯形 2.2凸集、凸函数和凸规划 （2）凸集的性质 凸集的交集是凸集；（并？） 凸集的内点集是凸集；（逆命题是否成立？） 凸集的闭包是凸集。 （逆命题是否成立？） 分离与支撑：凸集边界上任意点存在支撑超