资源描述：
《线性规划图解法浅析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第24卷第2期河南财政税务高等专科学校学报Vol.24.No.22010年4月JournalofHenanCollegeofFinance&TaxationApr.2010线性规划图解法浅析王兰林(河南财政税务高等专科学校会计系,河南郑州450002)[摘要]对于只有两个变量的简单的线性规划问题,可以用图解法求最优解,也就是作出约束条件的可行域,利用图解的方法求出最优解,其特点是过程简洁、图形清晰。[关键词]线性规划;可行域;图解[中图分类号]O221.1[文献标识码]A[文章编号]1008-5793(2010)02
2、-0094-03线性规划可以在一定条件下合理安排人力、物力等资可行域内的所有整点依次验证,选出最优解。源,使经济效果达到最好。一般来说,求线性目标函数在二、线性规划图解法的应用线性约束条件下的最大值或最小值的问题,统称为线性规(一)一般问题划问题。满足线性约束条件的解叫做可行解,由所有可行设有一线性规划问题表达式(包括目标函数、约束条解组成的集合叫做可行域。决策变量、约束条件、目标函件)如下数是线性规划的三要素。对于只有两个变量的线性规划fmax=50X1+40X2问题,可以用图解法求最优解,也就是作出约束条件的可X
3、1+X2≤450(1)行域,利用图解的方法求出最优解,其特点是过程简洁、图2X1+X2≤800(2)形清晰。X1+3X2≤900(3)一、从数学角度看图解法的原理X1,X2≥0(4)设线性目标函数z=Ax+By+C(A,B不全为0),当B解:在直角坐标系中画出不等式(1)、(2)、(3)、(4)所Az-C决定的5条直线,如图1所示,由5条直线所围成的一个凸≠0时,y=-x+,这样目标函数可看成斜率为-BB多边形就是约束条件给定的区域,其中所有的点都满足约A,在y轴上的截距为z-C且随z值变化的一组平行线。束条件的要求
4、。实际上,它表示一个由凸多边形内无数多BB个点所组成的集合,称为凸集。用平行移动的方法可以从因此,求z的最大值或最小值的问题可转化为求直线y=无穷多点中求出使目标函数值最大的点。Az-C-Bx+B与可行域有公共点时,直线在y轴上的截距目标函数f=50X1+40X2的斜率为-5/4。当f为不的最大值或最小值问题。同值时,在X1、X2坐标系中实际上是一系列的平行线,在A每一条直线上X1、X2取不同的值,f总是某一定值。由于具体的解题步骤是,先作出直线y=-x,再平行移B直线是“等值线”,而且斜率相等,它们又是一系列平行线
5、。动这条直线,最先通过或最后通过的可行域的顶点就是最因此只要画出其中任意一条线,将它们平移到某个与凸集优解。当B>0时,z的值随着直线在y轴上的截距的增大相交的极限位置,所得的交点就是既满足约束条件(在凸而增大;当B<0时,z的值随着直线在y轴上的截距的增集范围内),又使f值为最大最优解的点。如图1中的点大而减小。这样由y在可行域上的最值,可以得出目标zB,X1=350,X2=100,f=21500。在可行域上的最优解。对于求最优整解,如果作图非常准(二)整解问题2确可用平移求解法,也可以取出目标函数可能取得最值的例
6、:某人有一栋楼房,室内面积为180m,拟分割成两[收稿日期]2010-02-16[作者简介]王兰林(1963—),男,河南荥阳人,河南财政税务高等专科学校讲师。942类房间作为旅游客房,大房间每间面积为18m,可住游客如图所示,当直线Z=200X+150Y经过可行域上点A25名,每名游客每天住宿费40元;小房间每间面积为15m,时,Z取得最大值。但是A点坐标不是整数,不是最优整数可住游客3名,每名游客每天住宿费50元;装修大房间每解,所以最优解在可行域内。经验证,经过可行域且使Z=间需要1000元,装修小房间每间需6
7、00元,如果他只能筹200X+150Y取得最大值的整点是(0,12)和(3,8),此时Z款8000元用于装修,且游客能住满客房,他应隔出大房间的最大值为1800元,即应隔出小房间12间,或是大房间3和小房间各多少间才能获得最大效益?间、小房间8间可以获得最大利润。三、线性规划图解的特殊情况其一多重解。当目标函数与某一约束条件平行时,有多重最优解。例如:Zmax=X+2X12X+2X≤812X≤41X≤32X,X≥0(如图3所示)12图1线性规划问题中的约束条件和最优解解:设隔出的大房间X间,小房间Y间,收益为Z元,则
8、X,Y满足如下条件。18X+15Y≤180图3目标函数与一约束条件平行1000X+600Y≤8000其二无界解。无界解出现在可行域没有边界限制时。X≥0例如:Y≥0Zmax=6X1+X2目标函数:Z=200X+150Y-2X1+X2≤4根据以上约束条件作出可行域如图2所示。X1-X2≤2X1,X2≥0(如图4所示)图4可行域没有边界图2客房收益
