线性规划问题基本概念和基本理论.ppt

第1页，共25页，星期日，2025年，2月5日第二章基本概念和理论基础2.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页，共25页，星期日，2025年，2月5日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.第3页，共25页，星期日，2025年，2月5日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)均为线性函数时，称线性规划；若其中有非线性函数时，称非线性规划。第4页，共25页，星期日，2025年，2月5日2.2凸集、凸函数和凸规划一、凸集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)的线段。凸集非凸集非凸集第5页，共25页，星期日，2025年，2月5日2.2凸集、凸函数和凸规划(续)一、凸集1、凸集的概念：例:证明集合S={x∣Ax=b}是凸集。其中，A为m?n矩阵，b为m维向量。凸组合：设x(1),x(2),…,x(m)?Rn,?j≥0mm??j=1,那么称??jx(j)为x(1),x(2),…,x(m)的j=1j=1凸组合。m比较:z=??jx(j)j=1?j?R—构成线性组合——线性子空间?j≥0,??j0—构成半正组合——凸锥?j≥0,??j=0—构成凸组合——凸集第6页，共25页，星期日，2025年，2月5日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(