线性规划问题解的性质.ppt

《线性规划问题解的性质.ppt》由会员分享，可在线阅读，更多相关《线性规划问题解的性质.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 的的解为坐标点的集合解为坐标点的集合表示什么图形？表示什么图形？问题问题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基本概念：基本概念：(1)z=2x+y(3).象此问题一样，求线性目标函数在线性约束条件下的最值 的问题统称为线性规划问题。(4).满足约束条件的解(x，y

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

4、域(见上图)ABCDOx12x1+5x2=192x1+5x2=0 x2由小到大给s赋值，可得一组平行线，而位于同一直线上的点具有相同的目标函数值，因而称为等值线等值线。(2).作目标函数的等值线作目标函数的等值线目标函数s=2x1+5x2它代表是以 s 为参数的一族平行线相应的目标函数的最大值为 S=22+53=19.(3).确定最优点确定最优点 先确定目标函数值增大的方向增大的方向，沿着这个方向平行移动直线 s=2x1+5x2，当移动到 B点时，s值就在可行域上达到最大,从而确定B点就是最优点，得最优解为x1=2，x2=3。ABCDOx12x1+5x2=192x1+5x2=0 x2ABCDO

5、x1x1+2x2=8x2例例2.2 若将例2.1中的目标函数改为S=x1+2x2BC边上每一点的坐标都是最优解因此，最优解有无穷多个。因此，最优解有无穷多个。例例2.3、若目标函数为 min s=2x1+2x2解 确定可行域约束条件为Ox2x1ABCDOx2x12x1+2x2=102x1+2x2=22x1+2x2=6CBAD相应的目标函数最小值为 s=2。因此，最优解为 x1=1,x2=0作目标函数 的等值线确定最优点例例2.3、若目标函数为 min s=2x1+2x2 例例2.4、若将例2.3改为使目标函数的值最大，即 max s=2x1+2x2 从图中可以看出，因为凸域ABCD无界，当平行

6、直线族的直线无限远离原点时，都可以与ABCD相交，所以目标函数无上界，因此无最优解无最优解。2x1+2x2=2Ox2x12x1+2x2=102x1+2x2=6CBAD例例2.5、min s=2x1+2x2Ox1x2-x1+x2=1x1+x2=-2如图，没有可行解，没有可行解，故没有最优解。故没有最优解。线性规划问题解的四种情况：线性规划问题解的四种情况：两个重要结论：线性规划问题的任意两个可行解连线上的点都是可行解；线性规划问题的最优值如果存在，必然可在某个“顶点”达到。以后证明以后证明.2.2 线性规划问题的标准形式线性规划问题的标准形式(1)目标函数，有的要求最大化，有的要求最小化；(2)

7、约束条件也有多种形式LP问题有许多不同形式：这种多样性不仅给研究带来不便，而且使你难以寻找一种通用解法。人们发现：线性规划问题的各种不同形式可以相互转化。因此，只需给出一种形式的解法。矩阵表示矩阵表示min s=cx其中 c=(c1，c2，cn)min s=c1x1+c2x2+cnxn线性规划问题的标准形式如下：线性规划问题的标准形式如下：价值向量资源向量约束矩阵待定决策向量 min s=cx向量表示向量表示min s=cxLP问题非标准形问题的标准化非标准形问题的标准化 下面举例说明如何将非标准形线性规划问题化为标准形。（1）目标函数 若问题的目标函数为最大化 max s=cx，（2）约束条

8、件a)约束为形式的情形。如2x1-x2+3x318变量x4称为松弛变量松弛变量。则加入一个非负变量x40，改为：2x1-x2+3x3+x4=18则 可化为求 min s=cx，即可。b)约束为形式的情形。如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，则原问题的

9、标准形为：松弛变量剩余变量1.可行解、基础可行解、最优解、基础最优解设线性规划问题 min s=cx2.3 线性规划问题解的性质线性规划问题解的性质（一）几个概念（一）几个概念我们把满足约束条件的称为LP问题的可行解。若 x(0)=0，或 x(0)的非零分量所对应的系数列向量组线性无关时，称可行解x(0)为基础可行解基础可行解。使目标函数取最小值的基础可行解，称为基础最优解。使目标函数取最小值的可行解，称为最优解。例如：例如：若对于x(1)，x(2)S，x=x(1)+(1-)x(2)S（01），则称S为凸集。连接 n 维点集合S中任意两点 x(1)，x(2)的线段仍在S内，则称S为凸集凸集。即

10、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的极点（顶点）极点（顶点）。（二）线性规划问题解的性质（二）线性规划问题解的性质定理定理1 线性规划问题的可行解集（可行域）为凸集。设设LP问题问题:min s=cx证对于x(1)x(2)S,0,1S是其可行域，考查 x=x(1)+(1-)x(2)S定理2 x是基础可行解 x是可行

11、域S中的极点.（二）线性规划问题解的性质（二）线性规划问题解的性质设设LP问题问题:min s=cx证S是其可行域，“”即若x是可行域S中的极点，则x是基础可行解.反证法定理2 x是基础可行解 x是可行域S中的极点.反证法由此取定理2 x是基础可行解 x是可行域S中的极点.反证法由此取构造充分性得证！充分性得证！定理2 x是基础可行解 x是可行域S中的极点.反证法由此取定理2 x是基础可行解 x是可行域S中的极点.“”即若x是基础可行解，则x是可行域S中的极点.设设LP问题问题:min s=cx证S是其可行域，反证法若x不是可行域S中的极点.x(1)x(2)S,(0,1),使得 x=x(1)+

12、(1-)x(2)定理2 x是基础可行解 x是可行域S中的极点.“”即若x是基础可行解，则x是可行域S中的极点.设设LP问题问题:min s=cx证S是其可行域，反证法若x不是可行域S中的极点.则则x不是基础可行解不是基础可行解矛盾！故故x是可行域是可行域S中的极点中的极点.定理3 最优值可以在极点上达到.（二）线性规划问题解的性质（二）线性规划问题解的性质证仿定理2的证明定理3 最优值可以在极点上达到.（二）线性规划问题解的性质（二）线性规划问题解的性质证仿定理2的证明定理3 最优值可以在极点上达到.证按以上步骤重复以上步骤重复以上步骤到某一时刻定理3 最优值可以在极点上达到.分析分析：因为极点对应矩阵A中一组线性无关列向量，而矩阵A中有 n 列，其向量无关组的个数是有限的，因而极点个数有限。结论结论：如果线性规划问题有最优解，就只需从有限的几个极点中去找。*最多有 下一章介绍的单纯形方法，就是根据这一结论，由一个极点出发迭代到另一个极点，经过有限次迭代后，得到LP问题的最优解，或判定其无最优解。