线性规划问题解的概念和性质.pptx
线性规划线性规划(xin xn u hu)问题解的概念问题解的概念和性质和性质第一页，共13页。第五节线性规划问题(wnt)解的概念和性质 可行解：满足约束条件可行解：满足约束条件、的解的解X0=(x1X0=(x1，x2x2，xn xn)T)T为可行解。所有可行解的集合为可行域。为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。最优解：使目标函数达到最大值的可行解。基：设基：设A A为约束条件为约束条件的的mnmn阶系数阶系数(xsh)(xsh)矩阵矩阵(mn)(mn)，其秩为其秩为mm，B B是矩阵是矩阵A A中中mm阶满秩子矩阵（非奇异子矩阵）阶满秩子矩阵（非奇异子矩阵）（B0B0），称），称B B是线性规划问题的一个基。设：是线性规划问题的一个基。设：称称 B中每个列向量中每个列向量(xingling)Pj(j=1 2 m)为基向量为基向量(xingling)。与基向量。与基向量(xingling)Pj 对应的变量对应的变量xj(j=1 2 m)为基变量。除基变量以外的变量为基变量。除基变量以外的变量为非基变量。为非基变量。第1页/共13页第二页，共13页。第五节第五节 线性规划问题解的概念线性规划问题解的概念(ginin)(ginin)和性质和性质范范范范 例例例例A=1 0 1 0 0 0 2 0 1 03 4 0 0 1 x1 x2 x3 x4 x5a1 a2 a3 a4 a5 可取可取(kq)B0=（a3,a4,a5）为基（）为基（|B0|0）,这时这时称称 a3,a4,a5 为基向量，而为基向量，而 a1 ,a2 为非基向量；称为非基向量；称x3,x4,x5 为基变量，而为基变量，而 x1,x2 为非基变量。为非基变量。第2页/共13页第三页，共13页。第五节线性规划问题解的概念(ginin)和性质 基解（基本解）：某一确定基解（基本解）：某一确定(qudng)(qudng)的基的基B B，令非基变，令非基变量等于零，由约束条件方程量等于零，由约束条件方程解出基变量，称这组解为基解出基变量，称这组解为基解（基本解）。可见，有一个基就可以求出一个基本解。解（基本解）。可见，有一个基就可以求出一个基本解。在基解中变量取非在基解中变量取非0 0值的个数不大于方程数值的个数不大于方程数mm，基解的总数，基解的总数不超过不超过 基可行解：满足变量非负约束条件的基本解，简称基可基可行解：满足变量非负约束条件的基本解，简称基可行解。行解。可行基：对应于基可行解的基称为可行基。可行基：对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解第3页/共13页第四页，共13页。第五节第五节 线性规划问题解的概念线性规划问题解的概念(ginin)(ginin)和性质和性质基本基本(jbn)(jbn)解解 范例的标准形范例的标准形max z=3x1+5x2s.t.x1 +x3 =8 2 x2 +x4 =12 3x1+4x2 +x5=36 x1,x2,x3,x4,x5 0 取取 B0=（a3,a4,a5）为基，令一切）为基，令一切(yqi)非基非基变量变量 x1=x2=0,可解得基变量可解得基变量 x3=8，x4=12，x5=36则得一特解则得一特解 X0=(0，0，8，12，36)T 称为一个称为一个(关于关于 B0 为基的为基的)基本解基本解。第4页/共13页第五页，共13页。第五节第五节 线性规划问题线性规划问题(wnt)(wnt)解的概念和性质解的概念和性质也可取也可取B1=(a2,a3,a4)B1=(a2,a3,a4)为基为基,得得X1=(0X1=(0，9 9，8 8，-6-6，0)T0)T还可取还可取B2=(a1,a2,a3)B2=(a1,a2,a3)为基为基,得得X2=(4X2=(4，6 6，4 4，0 0，0)T0)T等等等等(dndn)(dndn)。基本可行解基本可行解满足非负性约束的基本解。满足非负性约束的基本解。如如X0X0，X2X2；而；而X1X1不可行。不可行。对基本对基本(可行可行)解而言：在其分量中，若有一个或更多个基变量取值为解而言：在其分量中，若有一个或更多个基变量取值为0 0，则称其为一个退化的基本，则称其为一个退化的基本(可行可行)解，否则为非退化的。解，否则为非退化的。如设：如设：X=(0X=(0，6 6，5 5，00，0)T0)T是一个基本可行解，其中是一个基本可行解，其中x5=0 x5=0为基变量，则该为基变量，则该X X为退化的基本可行解。为退化的基本可行解。第5页/共13页第六页，共13页。第五节第五节 线性规划问题解的概念线性规划问题解的概念(ginin)(ginin)和性质和性质非退化的基本非退化的基本(jbn)(jbn)(可行可行)解，解，并恰有并恰有nmnm个个00分量。分量。基本基本(jbn)可行解对应的基，称为可行基；可行解对应的基，称为可行基；最优基本最优基本(jbn)解对应的基，称为最优基。解对应的基，称为最优基。如：基如：基 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 m 个个非非非非 0 0 分量，分量，为为可行基可行基为为非可行非可行非可行非可行基基为为最优最优基基x*x*B*第6页/共13页第七页，共13页。第五节线性规划问题(wnt)解的概念和性质例：求线性规划问题的所有(suyu)基矩阵。解解:约束方程的系数约束方程的系数(xsh)矩阵为矩阵为25矩阵矩阵 r(A)=2，2阶子矩阵有阶子矩阵有10个，其中基矩阵个，其中基矩阵（不等于（不等于0）只有只有9个，即个，即第7页/共13页第八页，共13页。第五节第五节 线性规划问题线性规划问题(wnt)(wnt)解的概念和性质解的概念和性质凸性的几个基本概念凸性的几个基本概念一、凸集一、凸集 设设SSEnEn，对任意两点，对任意两点X XSS，Y YS S，若对满足，若对满足(mnz)01(mnz)01的一切的一切实数实数，都有，都有 X+(1-)YX+(1-)YSS则称则称S S为凸集。为凸集。XY YXY Y 凸凸集集凸集凸集非非凸集凸集非非表示表示(biosh)S 中两点中两点 X，Y 连线上的任连线上的任一点一点凸集凸集的的几何意义几何意义：凸集：凸集S S中任意两点中任意两点 X，Y Y 连线上的点，都在凸集连线上的点，都在凸集S S中。中。第8页/共13页第九页，共13页。第五节第五节 线性规划线性规划(xinxnuhu)(xinxnuhu)问题解的概念和性质问题解的概念和性质二、极点二、极点设凸集设凸集SSEn,XEn,XS S，如果，如果X X不能用不能用S S中不同的两点中不同的两点Y Y和和Z Z表示为表示为 X=Y+(1-)Z(01)X=Y+(1-)Z(01)则称则称X X为为S S的一个极点。的一个极点。三、三、凸组合凸组合(zh)(zh)设设XiXiEn,En,实数实数i0,i=1,2,s,i0,i=1,2,s,且且i=1i=1，则称，则称X=1X1+2X2+sXsX=1X1+2X2+sXs为点为点X1X1，X2X2，XsXs的一个凸组合的一个凸组合(zh)(zh)。第9页/共13页第十页，共13页。第五节第五节 线性规划问题线性规划问题(wnt)(wnt)解的概念和性质解的概念和性质线性规划的解的性质线性规划的解的性质 性质性质1 1：LPLP问题标准型的可行域问题标准型的可行域 R=X R=XAX=b,X 0 AX=b,X 0 是凸集。是凸集。性质性质2 2：LPLP问题标准型的一个基本可行解与可问题标准型的一个基本可行解与可行域行域 R R 的一个极点的一个极点 互相对应互相对应(duyng)(duyng)。性质性质3 3：线性规划的基本定理：线性规划的基本定理 对于一个给定的标准型对于一个给定的标准型LPLP问题问题标准型来说：标准型来说：若标准型有可行解，则必有若标准型有可行解，则必有基本可行解；基本可行解；若标准型有最优解，则必有若标准型有最优解，则必有最优基本解。最优基本解。性质性质4 4：若：若LPLP问题的可行域问题的可行域 R R,则则 R R 至少至少有一极点。有一极点。性质性质5 5：LPLP问题可行域问题可行域 R R 的极点数目必为有限的极点数目必为有限个。个。第10页/共13页第十一页，共13页。第五节第五节 线性规划问题线性规划问题(wnt)(wnt)解的概念和性质解的概念和性质仅就标准形仅就标准形LPLP问题说明其合理性。问题说明其合理性。因标准型是一个因标准型是一个(y)m(y)m阶阶n n维的维的LPLP问题，则从其系问题，则从其系数阵的数阵的n n列中取出列中取出mm列，所构成其基的个数不超过列，所构成其基的个数不超过C C mn=n！m！(n-m)！C C mn基本基本(jbn)(jbn)可行解可行解的个数的个数 基本解基本解的个数的个数而而标准型标准型问题的问题的 枚举法枚举法枚举法枚举法:当当m=50，n=100时时，此，此时需要求解的时需要求解的50元元50阶的线性方程组的个数为阶的线性方程组的个数为C C 50100=100！50！50！1029 这是一个天文数字！故需另寻其他有效方法。这是一个天文数字！故需另寻其他有效方法。第11页/共13页第十二页，共13页。1313第12页/共13页第十三页，共13页。
