《31孙一帆-二维线性规划的图解法及线性规划在实际中的应用.doc》由会员分享，可在线阅读，更多相关《31孙一帆-二维线性规划的图解法及线性规划在实际中的应用.doc（12页珍藏版）》请在金锄头文库上搜索。
1、论文题目：二维线性规划的图解法及线性规划在实际中的应用 院 系： 数学系 专 业： 数学与应用数学 姓 名： 孙一帆 学 号： 03211023 指导教师： 汪凤贞 完成时间： 2007年5月 二维线性规划的图解法及线性规划在实际中的应用孙一帆（包头师范学院数学科学学院）摘要：线性规划是运筹学的一个最基本的分支，它是一门研究如何使用最少的人力、物力和财力去最优地完成科学研究、工业设计、经济管理中实际问题的专门学科.它已经成为帮助各级管理人员进行决策的一种十分重要的工具.关键词：线性规划，数学模型，图解法，实际问题现代化工业管理要求采用定性和定量分析相结合的方法，一切管理工作要力求做到定量化、最
2、优化，于是就产生了各种各样的管理优化技术.在诸多的管理优化技术中，线性规划是目前最常用、而又最为成功的一种.其原因有三：一是应用广泛，管理工作中的大量优化问题可以用线性规划的模型来表达；二是模型较为简单，容易建立、学习和掌握；三是求解方法成熟：1947年G.B.Dantzig已对一般的线性规划问题建立了解法，即单纯形法，且随着计算机技术的发展，用单纯形法解线性规划的计算程序已大量涌现.线性规划主要在以下两类问题中得到应用：一是在人力、物力、财力等资源一定的条件下，如何使用它们完成最多的任务；二是做一项任务，如何合理安排和规划，能以最少的人力、物力、资金等资源来完成该项任务（即少投入，多产出）.
3、在这里，重要的是建立线性规划的数学模型，一个实际问题的数学模型，是依据客观规律对该问题中我们所关心的那些量进行科学的分析后所得出反映这些量之间本质联系的数学关系式.线性规划问题的数学模型（简称线性规划模型）的一般形式为：（） （*）0 (j=1,2,n). （）（）和（）称为约束条件，（）中的每一个式子均称为线性约束，（）中若要求变量0 的条件称为非负条件.这说明，线性规划模型由三部分构成：1一组决策变量通常要求它们非负，但在某些实际问题中也会出现变量为负数的情况;2表示所给问题最优化指标的目标函数z;3一组约束条件.正因为目标函数和约束条件都是关于决策变量的线性表示式，所以，这种数学模型称为
4、线性规划模型，相应的问题叫做线性规划问题.若（）中的不等式都为等式且（）中的变量为非负，则叫做线性规划模型的标准型.解任一线性规划问题通用的方法是单纯形法，但对于某些特殊的线性规划问题也有特殊的解法，这样更加简便，下面是解二维线性规划问题的图解法：一解二维线性规划问题图解法：对于只含有两个决策变量的LP问题，用图解法求解是最有效的，此方法简便、直观，所给问题也无需化成标准形，比单纯形法更有效，具体步骤见例题： 例1某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72，第二种有56，假设生产每种产品都需要用两种木料，生产一张圆桌和一个衣柜分别所需木料如下表所示.每生产一张圆桌可获利60元,
5、生产一个衣柜可获利100元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?产 品木料(单位)第 一 种第 二 种圆 桌0.180.08衣 柜0.090.28解：设生产圆桌张,生产衣柜个,利润总额为元,则由已知条件得到的线性规划模型为： s这是二维线性规划，可用图解法解，先在xy坐标平面上作出满足约束条件的平面区域,即可行域S，如上图所示.再作直线,即,把直线平移至的位置时,直线经过可行域上点,且与原点距离最远,此时取最大值，为了得到M点坐标解方程组,得;于是知点坐标为(350,100)，从而得到使利润总额最大的生产计划，即生产圆桌350张,生产衣柜100个,能使利润总额达到最
6、大值31000元.这表明，当资源数量已知,经过合理制定生产计划,可使效益最好,这就是用线性规划来解决生产计划安排的问题之一. 例2 某养鸡场有1万只鸡,用动物饲料和谷物饲料混合喂养.每天每只鸡平均吃混合饲料0.5kg,其中动物饲料不能少于谷物饲料的.动物饲料每千克0.9元,谷物饲料每千克0.28元,饲料公司每周仅保证供应谷物饲料50000kg,问饲料应怎样混合,才使成本最低.解:设每周需用谷物饲料kg,动物饲料kg,每周总的饲料费用为元, 则由已知条件得到的线性规划模型为： 这是二维线性规划问题，可用图解法求解，先作出满足约束条件的平面区域,即可行域S，如下图所示.s再作直线,平行移动此直线，
7、得到过可行域且离原点最近的直线是经过直线和直线的交点的直线，从而得到饲料混合的最佳喂养方案,即当谷物饲料,动物饲料时,饲料的混合既能达到饲养的要求又能使费用最低.也就是说,谷物饲料和动物饲料按5:1的比例混合是最佳方案.这表明，要完成一项确定的任务,如何统筹安排,尽量做到用最少的资源去完成它,这是线性规划中最常见的问题之一；另外，若本题是一个求资源最大化的问题，由于可行域无界（见上图），导致平行移动直线时无法在可行域内交得一点使此点离原点最远，因而此时问题无解.例3某运输公司接受了向抗洪抢险地区每天至少运送180吨支援物资的任务,该公司有8辆载重为6吨的A型卡车与4辆载重为10吨的B型卡车,有
8、10名驾驶员.每辆卡车每天往返的次数为：A型卡车4次,B型卡车3次.每辆卡车每天往返的成本费用为A型卡车320元,B型卡车504元,请制订该公司的车辆调配计划,使公司所花的成本费用最低.解:设每天调出A型卡车辆,B型卡车辆,公司所花成本为元, 则由已知条件： 则该问题的线性规划模型为： S这是二维线性整数规划，也可用图解法解.根据约束条件，作出可行域S,如上图,作直线,把直线向右上方作平行移动,经过点时取最小值,但不是整数,所以(,0)不是最优解.继续平移直线,直线上的整点(5,2)应是首先经过的,使取最小值,.答:每天调出A型卡车5辆,B型卡车2辆,公司所花成本最低.例4某钢材厂要将两种大小
9、不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格小钢板的块数如下表：A规格B规格C规格第一种钢板121第二种钢板113需求121527每张钢板的面积，第一种为1m2，第二种为2 m2，今需要A、B、C三种规格的成品各12、15、27块，请你们为该厂计划一下，应该分别截这两种钢板多少张，可以得到所需的三种规格成品，而且使所用钢板的面积最小？若只截其中一种类型的钢板，能否达到钢板使用面积最小的效果？解：设需要截第一种钢板x张，第二种钢板y张，所用钢板面积为z m2，则由已知条件得到的线性规划模型为: 这是二维线性规划，可用图解法求解，先作出可行域（如图），再作直线:x+2y=0，平行移
10、动,与可行域交于A点，且离原点最近 2x+y=15Ax+y=12 x+3y=27 x+2y=0求解，可得交点A的坐标，但点不是可行域内的整点，可选择附近的整点（4，8）或（6，7）代入目标函数，得Z(4,8)=20,Z(6,7)=20,这表明两种不同钢板的选择有两种方案，都可使所用钢板的面积最少，即耗材最少，即minZ=20.若只截第一种钢板，由可行域可知x27，此时所用钢板面积最少为z=27(m2)；若只截第二种钢板，由可行域也可知y15，最少需要钢板面积z=215=30(m2).它们都比zmin大，因此都不行.小结：用图解法解线性规划的应用问题，一般步骤如下：1 设出决策变量，找出线性规划
11、的约束条件和线性目标函数；2 根据约束条件做出可行域D，若，则无可行解；若，有三种情况：；3 ；4 做直线，平行移动与D相交且离原点最远（或最近）的点的坐标即为最优解；5 解出点的坐标.以上所举例子都是可解出具体解的问题，而在有些实际LP问题中由于有些约束条件相互矛盾，故平面上没有点能同时满足全部的约束条件，即不存在可行解，因而导致所给问题无解；除此之外还有会造成有无穷多个最优解的情况，这些都是可能存在的，所以在用图解法解LP问题时也应该注意到这些问题.二：解线性规划问题的通用方法单纯形法：根据线性规划问题的理论研究得知，单纯形法仅对线性规划模型的标准型适用，若线性规划问题有最优解，则最优解一
12、定可以在基可行解中找到，且基可行解的个数是有限的，为此，我们在获得任意一个基可行解x后，若它不是最优解，通过换基迭代得到一个新的基可行解，且z()比z（x）接近目标函数的最优值，如此经过有限次迭代，便能达到最优解.具体说，分三个步骤：1 找出第一个（初始的）基可行解;2 判断基可行解是不是最优解;3 如果不是，用换基迭代得到新的“更优”的基可行解；如果是，结束.再判断是否为最优解，以致最终求出最优解或得到无最优解的结论.下面的例子就采用这三个步骤：例5某色拉油厂利用A、B、C三种机械生产、型三种色拉油，已知生产每吨型油需要在A、B、C上工作的时数为4、3、4；型油的相应时数为5、4、2；型的为
13、3、2、1.由于A、B、C三种机械每天可利用的工时数分别为12、10、8，又已知每吨、型色拉油所能提供的利润分别为6、4、3千元，现问该厂应如何安排每天三种油的生产量才能充分利用现有设备，使该厂获利最大？解：设生产、型三种色拉油的生产量分别为，利润为z，则由已知条件得到的线性规划模型为：643000453100123420101042100180100-1203210-14001-410020-0-0-15010-200-11-0-0现将单纯形法的基本步骤总结如下：第一步：将所给问题化为标准型;第二步：找出一个初始可行基，并作的单纯形表;第三步：若所有检验数，则是最优基，计算终止；否则转第四步
14、;第四步：若有某个检验数，而全部则所给LP问题无解，计算结束；否则转至第五步;第五步：设有某些检验数，且中有正数，则需要换基，即为入基变量，为决定出基变量，计算，设最小比值为，则所在行包含的基变量为出基变量，为主元，在其上加画圆圈，在中调出出基变量，调入入基变量，便得到新基;第六步：对的单纯形表进行单纯形变换，便可得的单纯形表。再回到第三步，如此反复.由以上的单纯形方法的步骤可以看出，对于一个线性规划问题的数学模型，一定可以化为标准型，且由单纯形方法一定可以解出结果（包括无解，无穷多解等）.在用单纯形法解实际问题时，由于以上的方法步骤是比较固定的，因此很多计算可以用计算机软件，所以我在下面的例子中把重点放到如何对一个实际问题建立线性规划模型上，而省略用单纯形法的求解过程.
