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

第二章 线性规划问题解的性质§ 2.1 两个变量的线性规划问题的图解法§ 2.2 线性规划问题的标准形式§ 2.3 线性规划问题解的性质第一页，共三十五页。§ 2.1 两个变量的线性规划问题 的图解法第二页，共三十五页。y1o1xl：x+y-1=0y1x+y-1＞0o1xl：x+y -1=0§2.1 两个变量的线性规划问题的图解法1. 二元一次不等式表示平面区域问题1：以二元一次方程x + y-1=0 的解为坐标点的集合表示什么图形？问题2：以二元一次不等式 x + y-1 ＞0的解为坐标点的集合表示什么图形？x+y-1＜0第三页，共三十五页。yx-y+5=0Cx+y=04A2o-424x-2Bx=3练习画出不等式组表示的平面区域。解：①画直线x-y+5=0，确定不等式x-y+5≥0表示的区域；②画直线x+y=0，确定不等式x+y≥0表示的区域；③画直线x=3，确定不等式x≤3表示的区域；④取公共区域部分。第四页，共三十五页。目标函数，也叫线性目标函数。(2).线性约束条件。yx=12x+y=t(4). 满足约束条件的解(x，y)叫做可行解。可行域x-4y+3=0(5). 可行解组成的集合叫做可行域。（阴影部分）A（5，2）3x+5y-25=0o(6).使目标函数取得最值的x1B（1，1）可行解叫做最优解。基本概念：(1) z= 2x+y(3). 象此问题一样，求线性目标函数在线性约束条件下的最值 的问题统称为线性规划问题。第五页，共三十五页。x2BACDx1O2. 两个变量的线性规划问题的图解法一般过程 对于仅具有两个变量的线性规划问题，利用作图的方法求最优解，简单、直观。例2.1 max s = 2x1+5x2 约束条件解(1). 确定可行域再作： x1 ≤4 x2 ≤3x1 +2 x2 ≤8先作: x1≥0 x2≥0得可行域(见上图)第六页，共三十五页。(2). 作目标函数的等值线x2目标函数s=2x1+5x2它代表是以 s 为参数的一族平行线2x1+5x2=19BA由小到大给s赋值，可得一组平行线，而位于同一直线上的点具有相同的目标函数值，因而称为等值线。CDx1O2x1+5x2=0第七页，共三十五页。x22x1+5x2=19BACDx1O2x1+5x2=0(3). 确定最优点 先确定目标函数值增大的方向，沿着这个方向平行移动直线 s= 2x1+5x2，当移动到 B点时，s值就在可行域上达到最大,从而确定B点就是最优点，得最优解为x1=2，x2=3。相应的目标函数的最大值为 S=2×2+5×3=19.第八页，共三十五页。例2.2 若将例2.1中的目标函数改为S=x1+2x2x2x1+2x2=8BABC边上每一点的坐标都是最优解CODx1因此，最优解有无穷多个。第九页，共三十五页。x2ABx1ODC例2.3、若目标函数为 min s = 2x1+2x2约束条件为解 ⑴确定可行域第十页，共三十五页。例2.3、若目标函数为 min s = 2x1+2x2x2⑵作目标函数 的等值线2x1+2x2=10⑶确定最优点A因此，最优解为 x1=1, x2=0BDCx1O2x1+2x2=6相应的目标函数最小值为 s=2。2x1+2x2=2第十一页，共三十五页。x22x1+2x2=10ABDCx1O2x1+2x2=6 例2.4、若将例2.3改为使目标函数的值最大， 即 max s=2x1+2x2 从图中可以看出，因为凸域ABCD无界，当平行直线族的直线无限远离原点时，都可以与ABCD相交，所以目标函数无上界，因此无最优解。2x1+2x2=2第十二页，共三十五页。例2.5、min s =2x1+2x2x2如图，-x1+x2=1没有可行解，故没有最优解。x1Ox1+x2= -2第十三页，共三十五页。线性规划问题解的四种情况：两个重要结论： ★线性规划问题的任意两个可行解连线上的点都是可行解； ★线性规划问题的最优值如果存在，必然可在某个“顶点”达到。以后证明.第十四页，共三十五页。§2.2 线性规划问题的标准形式LP问题有许多不同形式：(1) 目标函数，有的要求最大化，有的要求最小化；(2) 约束条件也有多种形式这种多样性不仅给研究带来不便，而且使你难以寻找一种通用解法。人们发现：线性规划问题的各种不同形式可以相互转化。因此，只需给出一种形式的解法。第十五页，共三十五页。线性规划问题的标准形式如下：min s = c1x1+c2x2+…+cnxn矩阵表示min s = cx价值向量约束矩阵其中 c=(c1，c2，…，cn)资源向量待定决策向量 第十六页，共三十五页。LP问题min s = cx向量表示min s = cx第十七页，共三十五页。非标准形问题的标准化 下面举例说明如何将非标准形