线性规划问题解的概念和性质.ppt

《线性规划问题解的概念和性质.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五节线性规划问题解的概念和性质线性规划问题的解线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。第五节线性规划问题解的概念和性质可行解：满足约束条件②、③的解X0=(x1，x2，…，xn)T为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件②的m×n阶系数矩阵(m

2、基向量。与基向量Pj对应的变量xj(j=12……m)为基变量。除基变量以外的变量为非基变量。第五节线性规划问题解的概念和性质范例A=101000201034001x1x2x3x4x5a1a2a3a4a5可取B0=（a3,a4,a5）为基（

3、B0

4、≠0）,这时称a3,a4,a5为基向量，而a1,a2为非基向量；称x3,x4,x5为基变量，而x1,x2为非基变量。第五节线性规划问题解的概念和性质基解（基本解）：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基解（基本解）。可见，有一个基就可以

5、求出一个基本解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过基可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解第五节线性规划问题解的概念和性质基本解范例的标准形maxz=3x1+5x2s.t.x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0取B0=（a3,a4,a5）为基，令一切非基变量x1=x2=0,可解得基变量x3=8，x4=12，x5=36则得一特解X0=(0，0，8，12，36)T称

6、为一个(关于B0为基的)基本解。第五节线性规划问题解的概念和性质也可取B1=(a2,a3,a4)为基,得X1=(0，9，8，-6，0)T还可取B2=(a1,a2,a3)为基,得X2=(4，6，4，0，0)T等等。基本可行解满足非负性约束的基本解。如X0，X2；而X1不可行。对基本(可行)解而言：在其分量中，若有一个或更多个基变量取值为0，则称其为一个退化的基本(可行)解，否则为非退化的。如设：X=(0，6，5，0，0)T是一个基本可行解，其中x5=0为基变量，则该X为退化的基本可行解。第五节线性规划问题解的概念和

7、性质非退化的基本(可行)解，并恰有n–m个0分量。基本可行解对应的基，称为可行基；最优基本解对应的基，称为最优基。如：基B0=(a2,a3,a4)对应X0=(0，0，8，12，36)T可行基B1=(a2,a3,a4)对应X1=(0，9，8，-6，0)T不可行基B2=(a1,a2,a3)对应X2=(4，6，4，0，0)T恰有m个非0分量，为可行基为非可行基为最优基x*x*B*第五节线性规划问题解的概念和性质例：求线性规划问题的所有基矩阵。解:约束方程的系数矩阵为2×5矩阵r(A)=2，2阶子矩阵有10个，其中基矩阵

8、（不等于0）只有9个，即第五节线性规划问题解的概念和性质凸性的几个基本概念一、凸集设SEn，对任意两点X∈S，Y∈S，若对满足0≤μ≤1的一切实数μ，都有μX+(1-μ)Y∈S则称S为凸集。XYXY凸集凸集非凸集非表示S中两点X，Y连线上的任一点凸集的几何意义：凸集S中任意两点X，Y连线上的点，都在凸集S中。第五节线性规划问题解的概念和性质二、极点设凸集SEn,X∈S，如果X不能用S中不同的两点Y和Z表示为X=λY+(1-λ)Z(0<λ<1)则称X为S的一个极点。三、凸组合设Xi∈En,实数μi≥0,i=1,

9、2,…,s,且∑μi=1，则称X=μ1X1+μ2X2+…+μsXs为点X1，X2，…，Xs的一个凸组合。第五节线性规划问题解的概念和性质线性规划的解的性质性质1：LP问题标准型的可行域R={X︱AX=b,X≥0}是凸集。性质2：LP问题标准型的一个基本可行解与可行域R的一个极点互相对应。性质3：线性规划的基本定理对于一个给定的标准型LP问题标准型来说：⑴若标准型有可行解，则必有基本可行解；⑵若标准型有最优解，则必有最优基本解。性质4：若LP问题的可行域R≠Ø,则R至少有一极点。性质5：LP问题可行域R的极点数目必

10、为有限个。第五节线性规划问题解的概念和性质仅就标准形LP问题说明其合理性。因标准型是一个m阶n维的LP问题，则从其系数阵的n列中取出m列，所构成其基的个数不超过Cmn=n！m！(n-m)！<∞≤Cmn基本可行解的个数≤基本解的个数而标准型问题的枚举法:当m=50，n=100时，此时需要求解的50元50阶的线性方程组的个数为C50100=100！50！50！≈1029这是一