第二章 线性规划问题解的性质

1、第二章第二章 线性规划问题解的性质线性规划问题解的性质 2.1 两个变量的线性规划问题的图解法两个变量的线性规划问题的图解法 2.2 线性规划问题的标准形式线性规划问题的标准形式 2.3 线性规划问题解的性质线性规划问题解的性质 2.1 两个变量的线性规划问题两个变量的线性规划问题 的图解法的图解法1. 二元一次不等式表示平面区域二元一次不等式表示平面区域2.1 两个变量的线性规划问题的图解法两个变量的线性规划问题的图解法问题问题1：x+y- -10以二元一次不等式以二元一次不等式 x + y- -1 0的的xy11ol：x+y-1=0 xy11ol：x+y - -1=0 x+y- -10以二

2、元一次方程以二元一次方程x + y- -1=0 的的 01 , yxyx解为坐标点的集合解为坐标点的集合表示什么图形？表示什么图形？问题问题2：解为坐标点的集合解为坐标点的集合表示什么图形？表示什么图形？x+y=0A练习练习画出不等式组画出不等式组表示的平面区域。表示的平面区域。解：解：画直线x-y+5=0，确定不等式x-y+50表示的区域；画直线x+y=0，确定不等式x+y0表示的区域；画直线x=3，确定不等式x3表示的区域；取公共区域部分。xyo24-2-424x-y+5=0 x=3BC 3005xyxyx基本概念：基本概念：(1) z= 2x+y(3). 象此问题一样，求线性目标函数在线

3、性约束条件下的最值 的问题统称为线性规划问题。(4). 满足约束条件的解(x，y)叫做可行解。(5). 可行解组成的集合叫做可行域。（阴影部分）(6).使目标函数取得最值的可行解叫做最优解最优解。目标函数目标函数，也叫线性目标函数。 1255334xyxyx(2).线性约束条件。x-4y+3=03x+5y-25=0 x=12x+y=t1xyo可行域A（5，2）B（1，1）0,8234212121xxxxxx例例2.1 max s = 2x1+5x2 x1Ox2再作： x1 4 x2 3 x1 +2 x2 8 对于仅具有两个变量的线性规划问题，利用作图的方法求最优解，简单、直观。约束条件约束条件

4、2. 两个变量的线性规划问题的图解法一般过程两个变量的线性规划问题的图解法一般过程ABCD解解 (1). 确定可行域确定可行域先作: x10 x20得可行域可行域(见上图)ABCDOx12x1+5x2=192x1+5x2=0 x2由小到大给s赋值，可得一组平行线，而位于同一直线上的点具有相同的目标函数值，因而称为等值线等值线。(2). 作目标函数的等值线作目标函数的等值线目标函数s=2x1+5x2它代表是以 s 为参数的一族平行线相应的目标函数的最大值为 S=22+53=19.823212xxx(3). 确定最优点确定最优点 先确定目标函数值增大的方向增大的方向，沿着这个方向平行移动直线 s=

5、 2x1+5x2，当移动到 B点时，s值就在可行域上达到最大,从而确定B点就是最优点，得最优解为x1=2，x2=3。ABCDOx12x1+5x2=192x1+5x2=0 x2ABCDOx1x1+2x2=8x2例例2.2 若将例2.1中的目标函数改为S=x1+2x2BC边上每一点的坐标都是最优解因此，最优解有无穷多个。因此，最优解有无穷多个。 0,8234 .212121xxxxxxts 0, 0021 .212121xxxxxxts例例2.3、若目标函数为 min s = 2x1+2x2解 确定可行域约束条件为Ox2x1A0221 xx121 xxBCDOx2x12x1+2x2=102x1+2

6、x2=22x1+2x2=6CBAD相应的目标函数最小值为 s=2。因此，最优解为 x1=1, x2=0作目标函数 的等值线确定最优点例例2.3、若目标函数为 min s = 2x1+2x2 0, 0021 .212121xxxxxxts 例例2.4、若将例2.3改为使目标函数的值最大， 即 max s=2x1+2x2 从图中可以看出，因为凸域ABCD无界，当平行直线族的直线无限远离原点时，都可以与ABCD相交，所以目标函数无上界，因此无最优解无最优解。2x1+2x2=2Ox2x12x1+2x2=102x1+2x2=6CBAD 0, 0021 .212121xxxxxxts例例2.5、min s

7、 =2x1+2x2 0, 021 .212121xxxxxxtsOx1x2-x1+x2=1x1+x2= -2如图，没有可行解，没有可行解，故没有最优解。故没有最优解。线性规划问题解的四种情况：线性规划问题解的四种情况：无可行解有可行解但没有最优解有无穷多最优解有唯一最优解 两个重要结论： 线性规划问题的任意两个可行解连线上的点都是可行解； 线性规划问题的最优值如果存在，必然可在某个“顶点”达到。以后证明以后证明.2.2 线性规划问题的标准形式线性规划问题的标准形式(1) 目标函数，有的要求最大化，有的要求最小化；(2) 约束条件也有多种形式LP问题有许多不同形式：这种多样性不仅给研究带来不便，

8、而且使你难以寻找一种通用解法。人们发现：线性规划问题的各种不同形式可以相互转化。因此，只需给出一种形式的解法。矩阵表示矩阵表示min s = cx 0 .xbAxts其中 c=(c1，c2，cn) mnmmnnaaaaaaaaaA212222111211 mbbbb21 nxxxx21min s = c1x1+c2x2+cnxn 0, 0, 0 .2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats线性规划问题的标准形式如下：线性规划问题的标准形式如下：价值向量资源向量约束矩阵待定决策向量 0, , nmnm一般有一般有min

9、s = cx向量表示向量表示 0 .1xbPxtsjnjj), 2 , 1(21njaaaPmjjjj ),(21nPPPA ), 2 , 1(, 21njxaaaPjmjjjj 的的系系数数是是约约束束条条件件中中. 对对应应的的向向量量也也称称为为jjxPmin s = cx 0 .xbAxtsLP问题非标准形问题的标准化非标准形问题的标准化 下面举例说明如何将非标准形线性规划问题化为标准形。（1）目标函数 若问题的目标函数为最大化 max s = cx，（2）约束条件约束为形式的情形。如2x1-x2+3x318变量x4称为松弛变量松弛变量。则加入一个非负变量x40，改为：2x1-x2+3

10、x3+x4=18则 可化为求 min s = cx，即可。 约束为形式的情形。如c) 若对某变量xj没有非负限制，3x1+2x2-x418则减去一个非负变量x50，改为 3x1+2x2-x4-x5=18变量x5称为剩余变量剩余变量。则引进两个非负变量xj 0，xj 0，令xj=xj -xj 代入约束条件和目标函数中，化为对全部变量都有非负限制。自由变量例例2.6 将下面的线性规划问题化为标准形： max s = x1+2x2-3x3 解解 引进非负变量x4，x5，x6，则原问题的标准形为： 0,123263252616232153214321xxxxxxxxxxxxxxx32132minxxx

11、s 松弛变量剩余变量 0,1232632523212321321321xxxxxxxxxxxxx0 xbAx1. 可行解、基础可行解、最优解、基础最优解设线性规划问题 min s = cx2.3 线性规划问题解的性质线性规划问题解的性质（一）几个概念（一）几个概念我们把满足约束条件的称为LP问题的可行解。 )0()0(2)0(1)0(nxxxx 若 x(0)=0，或 x (0)的非零分量所对应的系数列向量组线性无关时，称可行解x (0)为基础可行解基础可行解。使目标函数取最小值的基础可行解，称为基础最优解。使目标函数取最小值的可行解，称为最优解。例如：例如：若对于x (1) ，x (2) S，

12、x= x (1) +(1-) x (2) S（01），则称S为凸集。 连接 n 维点集合S中任意两点 x (1) ，x (2)的线段仍在S内，则称S为凸集凸集 。即2. 凸集 点集中任意两点的连线段整个均是该点集的点，称该点集为凸集。x (1)x (2)x (1)x (2)x (1)x (2)x (1)x (2)x (1)x (2)3. 极点 (顶点)若凸集S中的点x，不能成为S中的内点，则称x为S的极点（顶点）。即， 若对于x (1) x (2) S, 不存在 (01),使 x= x (1) +(1-) x (2)则称x为S的极点（顶点）极点（顶点）。（二）线性规划问题解的性质（二）线性规划

13、问题解的性质定理定理1 线性规划问题的可行解集（可行域）为凸集。设设LP问题问题: min s = cx证 0 .xbAxts对于x (1) x (2) S, 0,1S是其可行域，,)2()1(Sxx 由于由于bAxAxxx )2()1()2()1(, 0, 0考查 x= x (1) +(1-) x (2) S, 0)1 ( 1 , 0)2()1( xxx bAxAxxxAAx )2()1()2()1()1 ( )1 ( Sxxx )2()1()1 ( 定理2 x是基础可行解 x是可行域S中的极点.（二）线性规划问题解的性质（二）线性规划问题解的性质设设LP问题问题: min s = cx证

14、0 .xbAxtsS是其可行域，“” 即若x是可行域S中的极点，则x是基础可行解.,0 ).1 (时时当当 x;是是基基础础可可行行解解显显然然x,0 ).2(且为极点时且为极点时当当 x),(, 21mkxxxxkiii 的的所所有有非非零零分分量量为为设设),(, 21mkPPPkiii 其所对应的列向量为其所对应的列向量为., 21线线性性无无关关问问题题转转化化为为说说明明向向量量组组kiiiPPP反证法线线性性相相关关若若向向量量组组kiiiPPP, 21,1k 一一组组不不全全为为零零的的数数则则 0 2121 kikiiPPP 使使得得定理2 x是基础可行解 x是可行域S中的极点

15、.反证法线线性性相相关关若若向向量量组组kiiiPPP, 21,1k 一一组组不不全全为为零零的的数数则则 0 2121 kikiiPPP 使使得得,R 对对)1 ( 0)(2121 kikiiPPP )2( 2211bPxPxPxkkiiiiii ,21的所有非零分量的所有非零分量是是由于由于xxxxkiii )()()(221121bPxPxPxkkikiiiii )1 ()2( )()()(221121bPxPxPxkkikiiiii )1 ()2(由此取|min, 10| tiktttx 定理2 x是基础可行解 x是可行域S中的极点.反证法线线性性相相关关若若向向量量组组kiiiPPP

16、, 21由此取|min, 10| tiktttx )()()(221121bPxPxPxkkikiiiii )()()(221121bPxPxPxkkikiiiii 构造 ),( , 0 :1)1()1(2)1(1)1()1(2211 kikiiiiiiiiixxxxxxxxkk ),( , 0 :1)2()2(2)2(1)2()2(2211 kikiiiiiiiiixxxxxxxxkk , , , 0, 0,1)2(1)1()2()1()2()1(bPxbPxxxxxniiiniii 充分性得证！充分性得证！定理2 x是基础可行解 x是可行域S中的极点.反证法线线性性相相关关若若向向量量组组

17、kiiiPPP, 21由此取|min, 10| tiktttx , , , 0, 0,1)2(1)1()2()1()2()1(bPxbPxxxxxniiiniii .LP ,)2()1(问问题题的的可可行行解解是是原原xx)2()1( 2121xxx 由由于于 .不不是是可可行行域域的的极极点点则则x ),( , 0 :1)1()1(2)1(1)1()1(2211 kikiiiiiiiiixxxxxxxxkk ),( , 0 :1)2()2(2)2(1)2()2(2211 kikiiiiiiiiixxxxxxxxkk定理2 x是基础可行解 x是可行域S中的极点.“” 即若x是基础可行解，则x是

18、可行域S中的极点.设设LP问题问题: min s = cx证 0 .xbAxtsS是其可行域，反证法若x不是可行域S中的极点.x (1) x (2) S, (0,1),使得 x= x (1) +(1-) x (2),(, 21mkxxxxkiii 的的所所有有非非零零分分量量为为设设),(, 21mkPPPkiii 其所对应的列向量为其所对应的列向量为 )1 , 0(, 0, )1 ( )2()1()2()1( iiiiixxxxxkiiiiiixx, 0 21)2()1( 即即 , ,1)2(1)1(bPxbPxntiiktiitttt 又又由由于于01)2()1( ktiiitttPxx)

19、2()1(0, 1ttiixxkt 使使得得且且定理2 x是基础可行解 x是可行域S中的极点.“” 即若x是基础可行解，则x是可行域S中的极点.设设LP问题问题: min s = cx证 0 .xbAxtsS是其可行域，反证法若x不是可行域S中的极点.),(, 21mkxxxxkiii 的的所所有有非非零零分分量量为为设设),(, 21mkPPPkiii 其所对应的列向量为其所对应的列向量为, 21线线性性相相关关向向量量kiiiPPP则则x不是基础可行解不是基础可行解矛盾！故故x是可行域是可行域S中的极点中的极点.01)2()1( ktiiitttPxx)2()1(0, 1ttiixxkt

20、使使得得且且定理3 最优值可以在极点上达到.（二）线性规划问题解的性质（二）线性规划问题解的性质, LP )0(问题的最优解问题的最优解是是设设 x证.) ()0()0(cxxS 最优值为最优值为., 0 )1()0()0(为为可可行行域域的的极极点点若若xx , 0 )2()0(且且不不是是极极点点若若 x),(, )0()0()0()0(21mkxxxxkiii 的的所所有有非非零零分分量量为为其其构构造造取取,|min )0(, 10| tiktttx 线线性性相相关关其其对对应应的的向向量量组组知知由由定定理理kiiiPPP, :221,1k 一一组组不不全全为为零零的的数数即即 0

21、2121 kikiiPPP 使使得得仿定理2的证明定理3 最优值可以在极点上达到.（二）线性规划问题解的性质（二）线性规划问题解的性质构构造造取取,|min )0(, 10| tiktttx ),( , 0 :1)1()0()1(2)0()1(1)0()1()1(2211 kikiiiiiiiiixxxxxxxxkk ),( , 0 :1)2()0()2(2)0()2(1)0()2()2(2211 kikiiiiiiiiixxxxxxxxkk 证,1k 一一组组不不全全为为零零的的数数即即 0 2121 kikiiPPP 使使得得, , 0 ,)2()1()2()1(xxxx . ,)0()2()1(个个的的非非零零分分量量的的个个数数少少一一比比量量的的个个数数中中至至少少有有一一个个其其非非零零分分且且在在xxx仿定理2的证明, ,1)2(1)1(bPxbPxniiiniii )1()1() (cxxS 而而且且定理3 最优值可以在极点上达到., LP )0(问题的最优解问题的最优解是是设设 x证.) ()0()0(cxxS 最优值为最优值为 ),( , 0 :1)1()0()1(2)0()1(1)0()1()1(2211 kikiiii