数学规划图解法

1、引 言朴素的运筹学思想可追溯到公元前400年至第二次世界大战前夕.然而图解法是运筹学的形思维的启蒙,也是打开运筹学基本原理的一把钥匙,该方法简单、直观、具体.数学规划作为运筹学的重要分支,可想而知图解法在数学规划中的作用也是不可替代的.我们从几何图形上了解数学规划问题的一些基本概念、理论、及解的原理,并使我们能得心应手地解决数学规划问题.本文就图解法的基本理论和基本解题方法及其应用展开思考.一、 数学规划图解法理论说明（一）几个概念定义1 对数学规划问题： 价值向量 系数矩阵 资源向量 决策向量 称为数学规划（LP）的可行域.若,则称为（LP）的可行解.若且对任意有,则称为（LP）的最优解,为

2、最优值.定义2 对上述数学规划问题,设为约束方程组的阶系数矩阵,（设）,秩为是矩阵中一个阶的满秩子矩阵,称是数学规划问题的一个基阵或简称基.不是一般性,设 是每一个列向量称为基向量,与基向量对应的变量成为基变量. 数学规划中基变量以外的变量成为非基变量.在约束方程中,令所有非基变量,因为不是满秩矩阵,有Cramer法则,可以从方程组得到基变量的唯一解,称为数学规划问题的基解.显然,基解的总数不超过个.当基解满足时称为基可行解. 定义3 如果集合中任意两个点,其连线上的所有点也都是集合中的点,称为凸集.在多维空间中,用数学解析式课表示为：对任何有,则称为凸集.称为凸集的极点.（二）数学规划图解法

3、的适用范围、解题步骤1、适应范围数学规划图解法主要是通过等值线在极点的值,平移到另一个极点的等值线的值进行比较,然后求出最优解.即先画出有约束条件决定的区域,然后作目标函数的平行直线（或平面）族（目标函数视为参数）,让直线族在区域上移动,移动至区域顶点停止或不能在顶点停止而决定最优解在顶点确定或最优解不存在.其主要适用于有两个变量的线性规划问题,一个二维的线性规划,可以在平面图上求解,三维的则要在立体图形上求解,维数再高的就不能图试了.但对于多个变量的来说,只要在标准型中有个独立方程, 个未知数,且-=2.即仅有两个独立变量也可以用图解法解决问题.2、解题步骤数学规划问题图解法的基本步骤大体上

4、可分为两步,第一是可行域的确定,即在坐标系下用图形表示约束条件不等式（也就是约束条件的解域）;第二是最优解的确定,即画目标函数图,由零等值线逐步得到最优解.但在处理实际问题时,得到解的结果会是怎样,我们可以从下图清楚地看到：例 求满足 解 化为标准型求满足由上式中方程组增广矩阵的秩确定独立方程的个数 说明标准型中有3个独立方程,5个未知数,有两个独立变量,可以取为独立里变量.因此可以化为求满足 （1）（1）式中每一个不等式在平面直角坐标系下表示半个平面,如图中无界区域下面找使目标函数达到最小的方案:目标函数在图中一个相应直线族,且过原点的直线为=1, 又在点处,处,所以等值线=1在解域内向右下

5、方平移值渐小,到点为最小,即代入（1）得故原问题最优解为：,Z=2Z=1DA43B2C1O-115432-1（三）数学规划图解法理论依据1、基本理论依据定理1 若线性规划问题存在可行域,则可行域一定是凸集.证 设,是可行域内任意的两点,连接、,如则所在的直线方程是,对应线段上的任意一点的坐标为,不是一般性,设,两点的坐标满足约束条件则 即点的坐标也满足约束条件,同样也可以证明,点的坐标也满足其它约束条件,因点也是可行域的点.如则上任意一点,同样也可以证明点H也是可行域的点.即线段EF上的任意一点都属于可行域,可行域是凸集.定理2 线性规划问题的基可行解对应可行域的顶点.定理3 若线性规划问题有

6、可行解,则至少有一个可行解.证 设= 是线行规划问题的任一可行解,则有.不妨设的非零分量为前个,即有; .如果约束矩阵的前个列向量线性无关,则可知是基本可行解;否则存在着不全为零的数,使得 ，令=0,得到维向量,有， 由于,我们可取适当小的正数,使得,易知 .所以,均是问题的可行解.在满足不等式 ,的同时,可以选择,是上述诸式中至少有一个取等号.这样就得到一个可行解或,它的非零分量至少比少一个.如果这个解还不是基本可行解,那么上述过程还可继续下去,由于当可行解只有一个非零分量时,该非零分量所对应的列向量一定是线性无关的,所以原线性规划问题必存在基本可行解.定理4若线性规划问题有有限个最优值,则

7、一定存在一个基本可行解是最优解. 2、图解法与单纯性法等价的证明我们知道,线性规划的可行解集是一个凸多面体,若非空,在有界的情况下,它一定有最优解,单纯形法是仅涉及可行解集极点的方法 ,迭代法的极点,沿着凸多面体的一条棱走到相邻的一个极点,然后求得最优解或判断无最优解.图解法是通过等值线在极点的值,平移到另一个圾点的等值线的值进行比较,然后求出最优解,这两种方法的连续求解过程,其实是等价的,这样我们就搭起了这两种解法的桥梁,圆满地解释了这两种解法的共同本质.定义1若又连续映射:;其中为单纯形法, 为图解法; 为原问题可行解集,S为其标准型可行解集.定义2若: 连续,存在H：连续,使得= ,=,

8、称同伦于,记为定理 单纯形法与图解法是同伦的.我们要想证明图解法与单纯性法等价关系,只要在上述定理的基础上证明在某个集合上,同伦就是等价关系,这样我们就可证得了.下面我们来证明图解法与单纯性法等价的：在集合中,同伦是个等价关系.证明（1）反身性 设:是映射,则由= , ,定义的同伦是从到得同伦. （2）对称性 若：,则可定义同伦为：= , ,则H是从到的同伦.（3）传递性 若,定义H：为： 如图所示： 则连续,且=,=,故得.证毕单纯形法与图解法的传递性,对称性,使我们可将单纯形的理论用图解法直观地表述出来,图解法过极点的等值线对应单纯形法过极点的一条棱,其平移过程对应迭代过程.必然得到图解法

9、的最优解对应单纯形法的最优解.（四）数学规划图解问题解决方法对可行域(可行解集)的确定和对目标函数等值线平移方向的确定方法不一,掌握不当易出差错.下就介绍几种常见的方法：1、判定可行域的方法直接判定法对于 或 所表示的区域的情况有如下结论, 详见表1与表 2.表 1 或 （0） 所表示的区域情况不等式 （0）00表示直线 的上方区域表示直线的下方区域表示直线的下方区域表示直线 的上方区域表 2 或 （=0） 所表示的区域情况不等式 （=0）00表示直线 的右侧区域表示直线的左侧区域表示直线的左侧区域表示直线 的右侧区域必须注意不等式中的符号 “” 、 “” 或 “” 、 “” , 它们的唯一的

10、区别就是前者表示的区域包括边界, 后者表示的区域不包括边界.点判定法二元一次不等式 或 表示在直角坐标系中直线某一侧的平面区域的所有点.那么,任取区域中一点, 若该点的坐标满足约束条件或,则该约束条件表示的区域就是以直线分隔且包含该点的一侧半平面,否则就表示另一侧半平面.为了方便,一般来说都是取原点来判定或所表示在直线某一侧的平面区域的.当时,因原点已在直线 上,故不能通过原点来判定.Y6例1根据表1、表 2 我们可以直接判定：约束条件表示直线下方区域;约束条件表示直线上方区域; 约束条件表示直线右方区域;约束条件表示直线左方区域，如图.例2 判定不等式表示的平面区域X3解 先画直线 （画虚线

11、）取原点 ,代入,3原点在不等式 表示的平面区域内, 不等式表示的平面区域如图阴影部分.2、确定最优点的方法顶点比较法由于简单线性规划的可行域的边界类似于多边形的边界或部分边界,我们类似于多边形那样给可行域边界予边或顶点等概念.顶点比较法就是先求出可行域边界的所有顶点,再分别计算目标函数在各个顶点的值进行比较确定最优解的方法.斜率比较法由于目标函数(不同时为0) 可变形为(不妨设0),故将视作常数时,表示斜率为(称为目标斜率) 的直线.斜率比较法是指当直线+=0平移后难以判定最优解为等顶点时,将与等顶点相连的可行域的边的斜率求出来,并从小到大排列,观察目标斜率于哪两个斜率之间,求出和这两个斜率

12、表示的边都相连的顶点确定最优解.例 正数,满足求目标函数=10+12的最大值.Y解 作出如图的可行域,作直线10+12=0 并平移后可知只有当直线=10+12过可行域的右上边界时才可能取最大值;而右上边界的边的B斜率由小到大排列为-1-4/5-3/10,目标斜X率为-5/6位于区间(-1,-4/5)之间, O故直线+=4.8与4+5=20的交点,即(4,0.8)为最优解,此时的值为49.6. 目标参与法目标参与法是指在目标函数中将或用,或,表示,代入约束条件, 再作出关于,型或,型可行域,确定的最值点后求出对应的关于,的最优解.例要将两种大小不同的钢板截成 3种规格的小钢板, 每张钢板可同时截

13、成3种规格小钢板的块数及相关数据如下表:类别A (块)B(块)C(块)面积(平方米/块)第一种钢板1211第二种钢板1132至少需要数(块)121227问各截这两种钢板多少张可得到所需三种规格成品, 且使所用钢板面积最小.解 设分别截第一种,第二种钢板各为,张, 所用钢板面积为,则=+2,且,为非负整数,同时满足Z由=+2得=-2代入约束条件得: 作出关于,型可行域如图, 故在点处(即纵坐标)取最小值,由-=12 和+=27联立方程组得=19.5,=7.5即点不是最优整数解,此时=19.5,M将直线=19.5平移,在可行域内发现当=20时,78;所以当=6,YO=7或=4,=8时取得最小值=2

14、0,这样当第一种钢板、第二种钢板分别截取6 张、7 张或4 张、8 张时,可得所需3 种规格成品,且使所用钢板面积最小.3、确定等值线增减方向的方法命题 设直线= (是常数),矢量是使增大的平移方向.证明 设平面数量场=()在点（）处的梯度为： 由梯度定义,的方向是点出值变化最大方向,而0, 值的变化时增加的.是常矢量,与点无关,所以是场中任意处值增大最快的方向.为使用方便,根据适量的平移性,记矢量,再令()=,得=,是场中等值线.所以=是等值线=的增大最快的平移方向,也就是增大的平移方向.注1：的方向取决于等值线=的常数,容易有图决定.注2：该定理除了确定等值线=的增大减小方向,另外一个应用

15、就是可以确定()表示的平面区域.因为直线: =把平面分为两部分,一部分是的区域,另一部分是的区域,而矢量=的方向是增大的方向,反之,的负向是减小的方向,由的方向就可定出区域.方法是作直线=定出点引矢量,以直线=为界,方向就是表示的区域.的负向是的区域.例 应图解法求解AFED解 如图由应用二方法作出问题的可行域为凸多边形.由应用一方法确定目标函数等值线:减小的平移方向的反向,即方向.由图知等直线平移在点达最小值故问题最优解为, 最优值注:对三变量的线性规划问题,其约束条件及目标函数式的图形与等值面有关,也可用上述方法进行图解,但空间图形不易画也不直观,求解不易、意义不大.二、数学规划图解法几种

16、模型数学规划的一般模型具备以下三个要素 ：1、决策变量决策问题待定的量值称为决策变量；决策变量的取值要求非负.2、约束条件 任何问题都是限定在一定的条件下求解,把各种限制条件表示为一组等式或不等式,称之为约束条件；约束条件是决策方案可行的保障；LP的约束条件,都是决策变量的线性函数.3、目标函数 衡量决策方案优劣的准则,如时间最省、利润最大、成本最低；目标函数是决策变量的线性函数；有的目标要实现极大,有的则要求极小.(一) 两个变量线性规划图解法模型1、基本步骤（1）可行域的确定满足所有约束条件的解的集合,称之为可行域.即所有约束条件共同围城的区域.例 = 五边形内(含边界)的任意一点 ()

17、都是满足所有约束条件的一个解,称之可行解 x1 =82x2 =12x1x24812369ABC (4,6)D0（2）最优解的确定目标函数= 代表以为参数的一族平行线.0Z=30Z=42Z=15x1 =82x2 =12x1x24812369ABC (4,6)D等值线：位于同一直线上的点的目标函数值相同.最优解：可行解中使目标函数最优(极大或极小)的解.2、几点说明由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合).可行域有有限个顶点.设规划问题有个变量,个约束,则顶点的个数不多于个.目标函数最优值一定在可行域的边界达到,而不可能在其内部.3、解的可能性唯一最

18、优解：只有一个最优点.多重最优解：无穷多个最优解.若在两个顶点同时得到最优解,则它们连线上的每一点都是最优解.例 x1 =82x2 =123x1 +4 x2 =36x1x248123690ABC(4,6)DZ=24Z=36Z=12无界解：线性规划问题的可行域无界,使目标函数无限增大而无界.（缺乏必要的约束条件） （二）多个变量线性规划图解法模型 图解法在一般情况下只适用于二维的线性规划问题求解,有一定的局限性.但利用对偶线性规划及其最优解互补松弛条件来解决含有两个约束的多个变量的线性规划的求解问题,突破图解法只能用于二维线性规划求解的框框.对于多变量的线性规划问题,利用图解法求解思路是：应用线

19、性规划的对偶规划原理,先用图解法解含有两个约束的多变量线性规划的对偶线性规划 含有两个变量多个约束的线性规划问题.再根据图中哪个约束条件起作用 ,哪个不起作用 ,由对偶线性规划的最优解互补松弛条件确定对偶规划中不起作用的约束所对应的原规划中的相应变量为零. 这样就将原线性规划变成了含有两个变量的线性规划问题.从而可以再用一次图解法确定最优解及目标函数的最优值例 用图解法解含有五个变量的线性规划 54解 进行对偶变换213 854321-11 用图解法,如图所示,直线=0沿梯度方向平移时,=在 (2,2/3)点时取得最大值.max=20/3, 最优解=2,=2/3.因为(2,2/3)是直线和的交

20、点,也就是说在上面个约束中只有和这两个约束起作用,而第一,第四和第五个约束,和不起作用,所以于是原问题可简化为2 (4/3, 1/6)1 =021用图解法,见右图 直线沿梯度方向平移,在点 (4/3,1/6) ,=取得最小值=20/3,最优解=4/3,=1/6 .于是原问题的最优解为=( 0,4/3,1/6,0,0) ,最优值为= 20/3 .验证 =20/3=.图解法成功.对于多变量的线性规划问题的图解法除了应上述对偶方法外,三个决策变量的还可以在立体图形中画出可行域,进而应图解法解决线性规划问题.其图解问题一般要在三维空间中讨论,在问题中一个约束条件决定了一个平面及其切出的半个空间 ,这个

21、半空间的交就是线性规划问题的可行域.可行域一般是一个凸多面体.设有三个决策变量的线性规划问题 特殊情况下,可行域无界则可能导致线性规划问题无最优解,或个半空间的交为空集 ,则线性规划问题无解.另一种特殊情况是约束条件中有一等式,这时问题可转化为二维问题.事实上,不妨设第个约束条件为等式 ,则,其中,不全为零,不妨设,则把该式代入目标函数和约束条件中的其余不等式中去,则问题变为一个只有两个决策变量的线性规划问题.全部约束条件都是不等式的时候,在平面上,目标函数 的值恒等于常数,故称这样的平面为等值平面.线性规划问题在空间的可行域与等值平面的交便是使目标函数的值的可行解.平移该等值平面,使常数项的

22、值逐渐变大并且保持与可行域的交不空,则值达到最大的那个等值平面与可行域的交便是线性规划问题的最优解 ,这时等值平面的值便是目标函数的最大值,最优解还可以从另一个角度去理解,作一个特殊的等值平面,该平面过原点,而最优解可以理解为在可行域上到等值平面距离最远的点.例 解 首先建立空间直角坐标系,如下图. 再在坐标系中画出可行域则如图可行域为凸五面体,粗虚线所围平面为目标函数等值面,平移目标函数等值面得最优点为点.点对应着该线性规划的最优解 =(1,2,0)T 即=1 =2 =0 此时有Z=8对于三个决策变量的线性规划问题还可以用画迹线的方法解决,这里就不做介绍了.从上面用图解法求解例子过程中明显感

23、觉到对具有三个决策变量的线性规划进行图解就麻烦得多了.因此,尽管图解法具有简单、直观的优点,但它的使用是有局限性的,对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法,大多数情况下仅对含有两个决策变量的线性规划才使用图解法求.（三）非线性规划图解法模型 非线性规划的理论是在线性规划的基础上发展起来的.1951年,库恩（H.W.Kuhn）和塔克（A.W.Tucker）等人提出了非线性规划的最优性条件,为它的发展奠定了基础.以后随着电子计算机的普遍使用,非线性规划的理论和方法有了很大的发展,其应用的领域也越来越广泛,特别是在军事,经济,管理,生产过程自动化,工程设计和产品优化设计等方面都

24、有着重要的应用. 一般来说,解非线性规划问题要比求解线性规划问题困难得多,而且也不像线性规划那样有统一的数学模型及如单纯形法这一通用解法.非线性规划的各种算法大都有自己特定的适用范围.都有一定的局限性,如线性规划的最优解存在,其最优解只能在其可行域的边界上达到（特别是可行域的顶点上达到）;而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到.到目前为止还没有适合于各种非线性规划问题的一般算法.这正是需要人们进一步研究的课题.一般非线性规划的数学模型可表示为：; , ,式中是维向量,都是的映射（即自变量是维向量,因变量是实数的函数关系）,且其中至少存在一个非线性映射.与线性规划类

25、似,把满足约束条件的解称为可行解.若记则称为可行域.因此上述模型可简记为 当只有两个自变量时,非线性规划也可象线性规划那样,具有鲜明的几何解释,并且可象征地把这种解释推广到多维中去.对非线性规划问题 首先画出目标函数的等值线然后画出等式约束的图形它是一条抛物线最后画出不等式约束所代表的区域（带斜线区域）由图看出,可行解集是抛物线上的曲线段,即抛物线被限制在带斜线区域中的部分.不难分析,当动点从出发沿抛物线移动时,在段目标函数值下降;过了点,在段上升,过了点,在段下降.点是可行解集上使目标函数值获得最小值的点,因此是最优点,其坐标不难由下面方 程组得出： 最后的,. 三、数学规划图解法的应用线性

26、规划研究的是线性目标函数在线性约束条件下的最大值或最小值的问题,线性规划实质上是“ 数形结合 ” 思想的一种体现,即将最值问题直观、 简便地寻找出来,是一种较为简捷的求最值的方法 图解法.（一）数学规划图解法的理论应用用二元一次不等式表示平面区域,是简单的线性规划问题的基础.下面就介绍几种利用线性规划图解法来解决数学问题的方法：1、在方程中的应用例 1已知实系数一元二次方程的两个实根为,并且,求斜率的取值范围.解 已知,由一元二次方程根的分布图知, 即 由所求的结构式联想到是求斜率的取值范围,即可看成是由点与点 所确定的直线的斜率的取值范围.可用线性规划的方法来解决.如图,点在右图的阴影部分内

27、.直线与直线的交点与点 所定直线的斜率为;当过点的直线与平行时,点不在阴影部分,而此时,故 .注意:解题关键是“构造”与“转化”,即由所给出的根的范围列出条件不等式组,再将其转换成线性规划问题.2、求斜率范围的应用例 2已知(1,2) ,(4,-2),若过点(0,3)的直线与线段相交,求其斜率的取值范围.分析: 常规方法:数形结合,先特殊后一般,最后定范围.新方法:学习线性规划后,知在平面内,一直线将平面划分为三部分: , ,故直线 与线段要相交,注定点、点在直线的两侧或在直线上,即满足不等式,解之得直线的斜率的取值范围.解 设过(0,3) 的直线方程为,若与线段相交,则满足 解之得 3、在概

28、率中的应用例 3甲乙两人因工作需要每天都要上网查找资料.已知他们每天上网的时间都不超过2h, 则在某一天内, 则甲上网的时间不足乙上网时间的一半的概率.解 设甲上网时间为,乙上网的时间为504060M40x30y50O1210M10yY由题意知: 2满足线性条件的落在图中的阴影区域内.故甲上网的时间不足乙上网时间的一半的概率为OX2 （二）数学规划图解法的实际应用解线性规划应用问题的基本步骤 (1)转化 设元,写出约束条件和目标函数,从而将实际问题转化为数学上的线性规划问题. (2)求解 解这个纯数学的线性规划问题.线性规划在解决实际问题中的应用,常通过二元一次不等式表示的平面区域来确定实际问

29、题的解,应用极为广泛. 1、商品规划问题例1下岗职工要开一个卖T恤和运动鞋的小商店,由于资金和店面有限,在他经营时受到如下条件限制( 1)他最多能进50T恤( 2)他最多能进30动鞋( 3)他至少需要进T恤和运动鞋共40能维持经营( 4)已知进货价为T恤每件36运动鞋每双48,现在他有2400.假设每件T恤的利润是18,每双运动鞋的利润是20,问如何进货可使他取得最大利润?Y解 设需进T恤件,运动鞋双,利润总额,则50X3040M 605040由图知,过点,故解方程组 得 但点坐标不是整数解,故不能作最优解.这时,在可行区域内,点近旁取到点(50,12)和点(49,13) ,经比较值知,点(49,13)为最优解 .=1849