《第二章 线性规划问题解的性质》由会员分享，可在线阅读，更多相关《第二章 线性规划问题解的性质（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=0xy11ol：x+y -1=0x+y-10以二元一次方程x + y-1=0 的解为坐标点的集合 表示什么图形？问题2：解为坐标点的集合 表示什么图形？x+y=0A练习画出不等式组表示的平面区域。解：画直线x-y+5=0，确定不等式x-y+50表示的区域；画直线x+y=0，
2、确定不等式x+y0表示的区域； 画直线x=3，确定不等式x3表示的区域；取公共区域部分。xyo24-2-424x-y+5=0x=3BC基本概念：(1) z= 2x+y(3). 象此问题一样，求线性目标函数在线性约束条件下的最值 的问题统称为线性规划问题。(4). 满足约束条件的解(x，y) 叫做可行解。(5). 可行解组成的集合叫做可行域。（阴影部分） (6).使目标函数取得最值的可行解叫做最优解。目标函数，也叫线性目标函数。(2).线性约束条件。x-4y+3=03x+5y-25=0x=12x+y=t1xyo可行域A（5，2）B（1，1）例2.1 max s = 2x1+5x2 x1Ox2再作
3、：x1 4x2 3 x1 +2 x2 8对于仅具有两个变量的线性规划问题，利用 作图的方法求最优解，简单、直观。约束条件2. 两个变量的线性规划问题的图解法一般过程ABCD解 (1). 确定可行域先作: x10x20得可行域(见上图)ABCDOx12x1+5x2=192x1+5x2=0x2由小到大给s 赋值，可得一 组平行线，而 位于同一直线 上的点具有相 同的目标函数 值，因而称为 等值线。(2). 作目标函数的等值线目标函数s=2x1+5x2 它代表是以 s 为参数 的一族平行线相应的目标函数的最大值为S=22+53=19.(3). 确定最优点先确定目标函数值增大的方向，沿着这个方向平 行
4、移动直线 s= 2x1+5x2，当移动到 B点时，s值就在可 行域上达到最大,从而确定B点就是最优点，得最优解为x1=2，x2=3。ABCDOx12x1+5x2=192x1+5x2=0x2ABCDOx1x1+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作目标函数的等值线确定最
5、优点例2.3、若目标函数为 min s = 2x1+2x2例2.4、若将例2.3改为使目标函数的值最大，即 max s=2x1+2x2从图中可以看出， 因为凸域ABCD无 界，当平行直线族 的直线无限远离原 点时，都可以与 ABCD相交，所以 目标函数无上界， 因此无最优解。2x1+2x2=2Ox2x12x1+2x2=102x1+2x2=6CBAD例2.5、min s =2x1+2x2Ox1x2-x1+x2=1x1+x2= -2如图，没有可行解，故没有最优解。线性规划问题解的四种情况：两个重要结论：线性规划问题的任意两个可行解连线上的 点都是可行解；线性规划问题的最优值如果存在，必然可 在某个
6、“顶点”达到。以后证明.2.2 线性规划问题的标准形式(1) 目标函数，有的要求最大化，有的要求最小化；(2) 约束条件也有多种形式LP问题有许多不同形式：这种多样性不仅给研究带来不便，而且使你难以寻 找一种通用解法。人们发现：线性规划问题的各种不同形式可以相互 转化。因此，只需给出一种形式的解法。矩阵表示 min s = cx其中 c=(c1，c2，cn)min s = c1x1+c2x2+cnxn线性规划问题的标准形式如下：价值向量资源向量约束矩阵待定决策向量 min s = cx向量表示min s = cxLP问题 非标准形问题的标准化下面举例说明如何将非标准形线性规划问 题化为标准形。
7、（1）目标函数若问题的目标函数为最大化 max s = cx，（2）约束条件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
8、= x1+2x2-3x3 解 引进非负变量x4，x5，x6，则原问题的标准形为：松弛变量剩余变量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中任意两点
9、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的极点（顶点）。（二）线性规划问题解的性质定理1 线性规划问题的可行解集（可行域）为凸集。设LP问题: min s = cx证对于x (1) x (2) S, 0,1S是
10、其可行域，考查 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
11、中的极点. 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 最优值可以在极点上达到.分析：因为极点对应矩阵A中一组线性无关列向 量，而矩阵A中有 n 列，其向量无关组的个数是 有限的，因而极点个数有限。结论：如果线性规划问题有最优解， 就只需从有限的几个极点中去找。*最多有下一章介绍的单纯形方法，就是根据这一结论， 由一个极点出发迭代到另一个极点，经过有限次迭代 后，得到LP问题的最优解，或判定其无最优解。
