线性规划问题解性质.pptx
2.1 两个变量的线性规划问题两个变量的线性规划问题 的图解法的图解法第1页/共35页1.二元一次不等式表示平面区域2.1 两个变量的线性规划问题的图解法问题1：x+y-10以二元一次不等式 x+y-1 0的xy11ol：x+y-1=0 xy11ol：x+y-1=0 x+y-10以二元一次方程x+y-1=0 的解为坐标点的集合表示什么图形？问题2：解为坐标点的集合表示什么图形？第2页/共35页x+y=0A练习画出不等式组表示的平面区域。解：画直线x-y+5=0，确定不等式x-y+50表示的区域；画直线x+y=0，确定不等式x+y0表示的区域；画直线x=3，确定不等式x3表示的区域；取公共区域部分。xyo2 4-2-424x-y+5=0 x=3BC第3页/共35页基本概念：(1)z=2x+y(3).象此问题一样，求线性目标函数在线性约束条件下的最值 的问题统称为线性规划问题。(4).满足约束条件的解(x，y)叫做可行解。(5).可行解组成的集合叫做可行域。（阴影部分）(6).使目标函数取得最值的可行解叫做最优解最优解。目标函数目标函数，也叫线性目标函数。(2).线性约束条件。x-4y+3=03x+5y-25=0 x=12x+y=t1xyo可行域A（5，2）B（1，1）第4页/共35页例 max s=2x1+5x2 x1Ox2再作：x1 4 x2 3 x1+2 x2 8 对于仅具有两个变量的线性规划问题，利用作图的方法求最优解，简单、直观。约束条件约束条件2.两个变量的线性规划问题的图解法一般过程ABCD解(1).确定可行域先作:x10 x20得可行域可行域(见上图)第5页/共35页ABCDOx12x1+5x2=192x1+5x2=0 x2由小到大给s赋值，可得一组平行线，而位于同一直线上的点具有相同的目标函数值，因而称为等值线。(2).作目标函数的等值线目标函数s=2x1+5x2它代表是以 s 为参数的一族平行线第6页/共35页相应的目标函数的最大值为 S=22+53=19.(3).确定最优点 先确定目标函数值增大的方向，沿着这个方向平行移动直线 s=2x1+5x2，当移动到 B点时，s值就在可行域上达到最大,从而确定B点就是最优点，得最优解为x1=2，x2=3。ABCDOx12x1+5x2=192x1+5x2=0 x2第7页/共35页ABCDOx1x1+2x2=8x2例 若将例中的目标函数改为S=x1+2x2BC边上每一点的坐标都是最优解因此，最优解有无穷多个。第8页/共35页例、若目标函数为 min s=2x1+2x2解 确定可行域约束条件为Ox2x1ABCD第9页/共35页Ox2x12x1+2x2=102x1+2x2=22x1+2x2=6CBAD相应的目标函数最小值为 s=2。因此，最优解为 x1=1,x2=0作目标函数 的等值线确定最优点例、若目标函数为 min s=2x1+2x2第10页/共35页 例、若将例改为使目标函数的值最大，即 max s=2x1+2x2 从图中可以看出，因为凸域ABCD无界，当平行直线族的直线无限远离原点时，都可以与ABCD相交，所以目标函数无上界，因此无最优解。2x1+2x2=2Ox2x12x1+2x2=102x1+2x2=6CBAD第11页/共35页例、min s=2x1+2x2Ox1x2-x1+x2=1x1+x2=-2如图，没有可行解，故没有最优解。第12页/共35页线性规划问题解的四种情况：两个重要结论：线性规划问题的任意两个可行解连线上的点都是可行解；线性规划问题的最优值如果存在，必然可在某个“顶点”达到。以后证明.第13页/共35页2.2 线性规划问题的标准形式(1)目标函数，有的要求最大化，有的要求最小化；(2)约束条件也有多种形式LP问题有许多不同形式：这种多样性不仅给研究带来不便，而且使你难以寻找一种通用解法。人们发现：线性规划问题的各种不同形式可以相互转化。因此，只需给出一种形式的解法。第14页/共35页矩阵表示min s=cx其中 c=(c1，c2，cn)min s=c1x1+c2x2+cnxn线性规划问题的标准形式如下：价值向量资源向量约束矩阵待定决策向量 第15页/共35页min s=cx向量表示min s=cxLP问题第16页/共35页非标准形问题的标准化 下面举例说明如何将非标准形线性规划问题化为标准形。（1）目标函数 若问题的目标函数为最大化 max s=cx，（2）约束条件约束为形式的情形。如2x1-x2+3x318变量x4称为松弛变量。则加入一个非负变量x40，改为：2x1-x2+3x3+x4=18则 可化为求 min s=cx，即可。第17页/共35页 约束为形式的情形。如c)若对某变量xj没有非负限制，3x1+2x2-x418则减去一个非负变量x50，改为 3x1+2x2-x4-x5=18变量x5称为剩余变量。则引进两个非负变量xj 0，xj 0，令xj=xj-xj 代入约束条件和目标函数中，化为对全部变量都有非负限制。自由变量第18页/共35页例 将下面的线性规划问题化为标准形：max s=x1+2x2-3x3 解 引进非负变量x4，x5，x6，则原问题的标准形为：松弛变量剩余变量第19页/共35页1.可行解、基础可行解、最优解、基础最优解设线性规划问题 min s=cx2.3 线性规划问题解的性质（一）几个概念我们把满足约束条件的称为LP问题的可行解。若 x(0)=0，或 x(0)的非零分量所对应的系数列向量组线性无关时，称可行解x(0)为基础可行解基础可行解。使目标函数取最小值的基础可行解，称为基础最优解。使目标函数取最小值的可行解，称为最优解。第20页/共35页例如：若对于x(1)，x(2)S，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)第21页/共35页3.极点(顶点)若凸集S中的点x，不能成为S中的内点，则称x为S的极点（顶点）。即，若对于x(1)x(2)S,不存在(01),使 x=x(1)+(1-)x(2)则称x为S的极点（顶点）。第22页/共35页（二）线性规划问题解的性质定理1 线性规划问题的可行解集（可行域）为凸集。设LP问题:min s=cx证对于x(1)x(2)S,0,1S是其可行域，考查 x=x(1)+(1-)x(2)S第23页/共35页定理2 x是基础可行解 x是可行域S中的极点.（二）线性规划问题解的性质设LP问题:min s=cx证S是其可行域，“”即若x是可行域S中的极点，则x是基础可行解.反证法第24页/共35页定理2 x是基础可行解 x是可行域S中的极点.反证法由此取第25页/共35页定理2 x是基础可行解 x是可行域S中的极点.反证法由此取构造充分性得证！第26页/共35页定理2 x是基础可行解 x是可行域S中的极点.反证法由此取第27页/共35页定理2 x是基础可行解 x是可行域S中的极点.“”即若x是基础可行解，则x是可行域S中的极点.设LP问题:min s=cx证S是其可行域，反证法若x不是可行域S中的极点.x(1)x(2)S,(0,1),使得 x=x(1)+(1-)x(2)第28页/共35页定理2 x是基础可行解 x是可行域S中的极点.“”即若x是基础可行解，则x是可行域S中的极点.设LP问题:min s=cx证S是其可行域，反证法若x不是可行域S中的极点.则x不是基础可行解矛盾！故x是可行域S中的极点.第29页/共35页定理3 最优值可以在极点上达到.（二）线性规划问题解的性质证仿定理2的证明第30页/共35页定理3 最优值可以在极点上达到.（二）线性规划问题解的性质证仿定理2的证明第31页/共35页定理3 最优值可以在极点上达到.证第32页/共35页按以上步骤重复以上步骤重复以上步骤到某一时刻定理3 最优值可以在极点上达到.第33页/共35页分析：因为极点对应矩阵A中一组线性无关列向量，而矩阵A中有 n 列，其向量无关组的个数是有限的，因而极点个数有限。结论结论：如果线性规划问题有最优解，就只需从有限的几个极点中去找。*最多有 下一章介绍的单纯形方法，就是根据这一结论，由一个极点出发迭代到另一个极点，经过有限次迭代后，得到LP问题的最优解，或判定其无最优解。第34页/共35页感谢您的观看！第35页/共35页
