第二章-线性规划问题解的性质PPT课件

1、第二章 线性规划问题解的性质,2.1 两个变量的线性规划问题的图解法 2.2 线性规划问题的标准形式 2.3 线性规划问题解的性质,2.1 两个变量的线性规划问题 的图解法,1. 二元一次不等式表示平面区域,2.1 两个变量的线性规划问题的图解法,问题1,以二元一次不等式 x + y-1 0的,x+y-10,以二元一次方程x + y-1=0 的,解为坐标点的集合表示什么图形,问题2,解为坐标点的集合表示什么图形,练习,画出不等式组,表示的平面区域,解,画直线x-y+5=0，确定不等式x-y+50表示的区域,画直线x+y=0，确定不等式x+y0表示的区域,画直线x=3，确定不等式x3表示的区域,

2、取公共区域部分,基本概念,1) z= 2x+y,3). 象此问题一样，求线性目标函数在线性约束条件下的最值 的问题统称为线性规划问题,2,例2.1 max s = 2x1+5x2,再作： x1 4 x2 3 x1 +2 x2 8,对于仅具有两个变量的线性规划问题，利用作图的方法求最优解，简单、直观,约束条件,2. 两个变量的线性规划问题的图解法一般过程,解,1). 确定可行域,先作: x10 x20,得可行域(见上图,A,B,C,D,O,x1,2x1+5x2=19,2x1+5x2=0,x2,由小到大给s赋值，可得一组平行线，而位于同一直线上的点具有相同的目标函数值，因而称为等值线,2). 作目

3、标函数的等值线,目标函数s=2x1+5x2它代表是以 s 为参数的一族平行线,相应的目标函数的最大值为 S=22+53=19,3). 确定最优点,先确定目标函数值增大的方向，沿着这个方向平行移动直线 s= 2x1+5x2，当移动到 B点时，s值就在可行域上达到最大,从而确定B点就是最优点,得最优解为x1=2，x2=3,A,B,C,D,O,x1,x1+2x2=8,x2,例2.2 若将例2.1中的目标函数改为S=x1+2x2,BC边上每一点的坐标都是最优解,因此，最优解有无穷多个,例2.3、若目标函数为 min s = 2x1+2x2,解 确定可行域,约束条件为,O,x2,x1,2x1+2x2=1

4、0,2x1+2x2=2,2x1+2x2=6,C,B,A,D,相应的目标函数最小值为 s=2,因此，最优解为 x1=1, x2=0,作目标函数 的等值线,确定最优点,例2.3、若目标函数为 min s = 2x1+2x2,例2.4、若将例2.3改为使目标函数的值最大， 即 max s=2x1+2x2,从图中可以看出，因为凸域ABCD无界，当平行直线族的直线无限远离原点时，都可以与ABCD相交，所以目标函数无上界，因此无最优解,2x1+2x2=2,例2.5、min s =2x1+2x2,O,x1,x2,x1+x2=1,x1+x2= -2,如图,没有可行解,故没有最优解,线性规划问题解的四种情况,两

5、个重要结论： 线性规划问题的任意两个可行解连线上的点都是可行解； 线性规划问题的最优值如果存在，必然可在某个“顶点”达到,以后证明,2.2 线性规划问题的标准形式,1) 目标函数，有的要求最大化，有的要求最小化,2) 约束条件也有多种形式,LP问题有许多不同形式,这种多样性不仅给研究带来不便，而且使你难以寻找一种通用解法,人们发现：线性规划问题的各种不同形式可以相互转化。因此，只需给出一种形式的解法,矩阵表示,min s = cx,其中 c=(c1，c2，cn,min s = c1x1+c2x2+cnxn,线性规划问题的标准形式如下,价值向量,资源向量,约束矩阵,待定决策向量,min s =

6、cx,向量表示,min s = cx,LP问题,非标准形问题的标准化 下面举例说明如何将非标准形线性规划问题化为标准形,1）目标函数,若问题的目标函数为最大化 max s = cx,2）约束条件,约束为形式的情形。如,2x1-x2+3x318,变量x4称为松弛变量,则加入一个非负变量x40，改为,2x1-x2+3x3+x4=18,则 可化为求 min s = cx，即可,约束为形式的情形。如,c) 若对某变量xj没有非负限制,3x1+2x2-x418,则减去一个非负变量x50，改为 3x1+2x2-x4-x5=18,变量x5称为剩余变量,则引进两个非负变量xj 0，xj 0,令xj=xj -x

7、j 代入约束条件和目标函数中,化为对全部变量都有非负限制,自由变量,例2.6 将下面的线性规划问题化为标准形： max s = x1+2x2-3x3,解 引进非负变量x4，x5，x6,则原问题的标准形为,松弛变量,剩余变量,1. 可行解、基础可行解、最优解、基础最优解,设线性规划问题 min s = cx,2.3 线性规划问题解的性质,一）几个概念,若 x(0)=0，或 x (0)的非零分量所对应的系数列向量组线性无关时，称可行解x (0)为基础可行解。使目标函数取最小值的基础可行解，称为基础最优解,使目标函数取最小值的可行解，称为最优解,例如,若对于x (1) ，x (2) S，x= x (

8、1) +(1-) x (2) S（01），则称S为凸集,连接 n 维点集合S中任意两点 x (1) ，x (2)的线段仍在S内，则称S为凸集,即,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,1,S是其可行域,考

9、查 x= x (1) +(1-) x (2) S,定理2 x是基础可行解 x是可行域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) +(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 最优值可以在极点上达到,