浅谈线性规划在生活中的应用2

-1-浅谈线性规划在生活中的应用摘要线性规划的研究对象是计划管理工作中有关安排和估值的问题,解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案.文章涉及的是在两个限定条件下的最大利润问题，它是一种最简单的线性规划，解决的方法就是用图象法和消去法.关键词线性规划;松弛变量;最优解;目标函数中图分类号0122.1线性规划作为数学规划中最简单的一种问题.它的研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足约束条件下的极大或极小值问题.如果约束条件和目标函数都是呈线性关系的就叫线性规划.要解决线性规划问题，从理论上讲都要解线性方程组，而解线性方程组的常见方法是图象法和消去法.1预备知识线性规划是数学规划中理论成熟,方法有效,应用最广泛的一个分支.它研究满足一组线性的等式或不等式约束条件,对一定的线性目标函数进行最优化处理的问题.它是由丹捷格(G.B.Dantzig)在1947年发表的成果.所解决的问题是美国制定空军军事规划时提出的,并提出了求解线性规划问题的方法.2线性规划问题解的基本概念2.1线性规划线性规划是在线性约束的有限集合上使一个仿射函数(仿射函数亦即线性函数)达到最大(或最小)的优化问题.2.2松弛变量松弛变量表示一个决策过程中原料消耗的剩余量.2.3可行解,可行域满足若干个约束条件的解称为线性规划问题的可行解,所有的可行解构成的集合叫它的可行域.2.4最优解满足若干个约束条件和某个目标函数式的可性解称为线性规划问题的最优解.2.5基本可行解满足若干个非负条件的基本解称为基本可行解.3简单线性规划问题的解法将实际生活中的线性规划问题,抽象为数学形式,目的在于找到解决问题的方法.为此,我们作以下一些讨论.3.1最大利润问题例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗.如表1所示:表1ⅠⅡ设备128台时原材料A4016㎏-2-原材料B0412㎏该厂每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元.问应如何安排计划,使该工厂在限定条件下获利最多?显见,这个问题可以用以下的数学模型来描述:设21,xx分别表示在计划期内产品Ⅰ、Ⅱ的产量.因为设备的有效台时是8,这是一个限制产量的条件,所以确定产品Ⅰ、Ⅱ的产量时,要考虑不超过设备的有效台时数,即可用不等式表示为:8221xx.同理,因原材料的限量,可以得到两个不等式:1641x,1242x.该厂的目标是在不超过所有资源限量的条件下,如何确定产量21,xx以得到最大的利润.用z表示利润,这时2132xxz.综合上述,此计划问题可用数学模型表示为:目标函数:1223zxx约束条件:0,12416482212121xxxxxx3.2两个变量的线性规划问题的图解法现在我们用图解法来解上述的例1:在以21,xx为坐标轴的直角坐标系中,非负条件0,021xx是指第一象限.每一个约束条件都代表一个半平面,如约束条件8221xx是代表以直线8221xx为边界的左下方的半平面.若同时满足:0,021xx,8221xx,1641x和1242x的约束条件的点,必然落在21,xx坐标轴和由这三个半平面交成的区域内(如右图).阴影区域中的每一个点(包括边界)都是这个线性规划问题的解,因而此区域是此线性规划问题的解集合,称它为可行域.再来分析目标函数2132xxz.在这个坐标平面上,它可表示以z为参数,以32为斜率的一族平行线:3)32(12zxx.位于同一直线上的点,具有相同的目标函数值,因而称它为“等值线”.当z值由小变大时,直线3)32(12zxx沿其法线方向向右上方移动．当移动到2Q点时，使z值在可行域边界上实现最大化（如下图）:这就得到了例１的最优解对应的点2Q,2Q点的坐标为)2,4(.于是可计算出满足x1x2Ox1+2x2=84x1=164x2=12Q3Q2Q1Q43所有约束条件的最大值14z．这说明该厂的最优生产计划方案是：生产４件产品Ⅰ，生产２件产品Ⅱ，可得最大利润为14元．x1x2Ox1+2x2=84x1=164x2=12Q3Q2Q1Q43.3用消去法解两个变量的线性规划问题例２某车间生产甲、乙两种产品，已知制造一件甲产品需要Ａ种元件５个,Ｂ种元件３个；制造一件乙产品需要Ａ种元件２个，Ｂ种元件３个.现因某种条件限制,只有A种元件180,B种元件135个；每件甲种产品可获利20元,每件乙种产品可获利15元.试问在这种条件下,应该生产甲、乙两种产品各多少件才能得到最大利润?解:设应该生产甲产品1x件,乙产品2x件,才能得到最大利润S元.根据题意,此问题可用数学模型表示为:目标函数122015Sxx满足约束条件0,1353318025212121xxxxxx即求解满足约束条件的21,xx,使目标函数211520xxS的值最大.为此,引进松弛变量43,xx,把线性规划问题化为标准形式:求21'1520xxSS的最小值,并且满足：0,,,13533180254321421321xxxxxxxxxx也就是求方程组)2(13533)1(180252121xxxx的非负解,并且使目标函数21'1520xxSS的值最小．显然,有一个可行解是:135,180,0,04321xxxx.相应的目标函数值为:0015020'S再从目标函数21'1520xxSS看出.如果1x不取0,而增大1x的值,目标函数的值可以减少.为此,把1x换成3x.4由)1(得321515236xxx这样,原方程组可改写成)4(3)515236(3135)3(5152362324321xxxxxxx相应的目标函数可改为:232'15)515236(20xxxSS3247720xx显然,又可得另一个可行解是:27,0,0,364321xxxx相应的目标函数值为:0407720'S720再从目标函数32'147720xxSS看出．如果2x不取0,而增大2x的值,目标函数的值还可以减少.为此,把2x换成4x,并且化简)4(得)5(953115432xxx将)5(式代入)3(式得343151)953115(5236xxxx43923130xx因而方程组可改写成)7(953115)6(923130432431xxxxxx相应的目标函数改为343'24)953115(7720xxxS4393535825xx显然,又可得另一个可行解是:0,0,15,304321xxxx相应的目标函数值为0935035825'2S8255从目标函数41'293535825xxS可以看出,目标函数825'2S已经是最小值,所以这一可行解是最优解.即原问题的最优解为15,3021xx相应的目标函数值825'SS所以在这种条件下,生产甲、乙产品各30件、15件,使得最大利润为825元.以上是用两种不同的方法解决了我们生产生活中常遇到的最大利润问题.消去法作为数学中常见的一个解方程组的方法,在解线性规划的问题中起到了很重要的作用.下面,我们再看一例,如何用消去法解线性规划中的问题.例3求21,xx的值,使它们满足约束条件0,8234212121xxxxxx并使目标函数2152xxS的最大值.解:引进松弛变量543,,xxx,把题目对应的线性规划问题化为标准形式:求21'52xxSS的最小值,并且满足：0,,,,8234543215214231xxxxxxxxxxxx也就是求方程组)3(28)2(3)1(42152413xxxxxxx的非负解,并且使目标函数21'52xxSS的值最小．显然,有一个可行解是:8,3,4,0,054321xxxxx.相应的目标函数值为:0502'1S再从目标函数21'152xxS看出．如果1x不取0,而增大1x的值,目标函数的值可以减少.为此,把1x换成3x.由)1()3(得623524xxx这样,原方程组可改写成)6(24)5(3)4(42352431xxxxxxx相应的目标函数可改为:23'25)4(2xxS23528xx显然,又可得另一个可行解是:4,3,0,0,454321xxxxx相应的目标函数值为:05028'2S从而8'1'2SS再从目标函数23'2528xxS看出．如果2x不取0,而增大2x的值,目标函数的值还可以减少.为此,把2x换成5x,由)6(21)5(得35421125xxx即53421211xxx由)6(21得53221212xxx因而方程组可改写成132354354(7)112(8)22111(9)22xxxxxxxx相应的目标函数改为)21212(5)4(2533'3xxxS53252118xx显然,又可得另一个可行解是:0,1,0,2,454321xxxxx7对应的目标函数值为02502118'3S从而10'2'3SS再从目标函数53'3252118xxS可以看出,如果3x不取0,而增大3x的值,目标函数的值还可以减少.为此,把3x换成4x由)9(2)7(并化简整理得54122xxx由)9()8(并化简整理得423xx由)9(2并化简整理得54322xxx因而方程组可改写成5434254122322xxxxxxxx相应的目标函数改为)3(5)22(2454'4xxxS54219xx显然,此时的可行解为:0,0,2,3,254321xxxxx对应的目标函数值为02019'4S从而1'3'4SS从目标函数54'4219xxS看出,目标函数19'4S已经是最小值,所以这一可行解是原方程组的最优解.即当3,221xx时满足给定的约束条件,并且使目标函数有最大值为19.众所周知,在生产生活中人们经常遇到一些要求对现有资源、设备进行统一分配,全面安排,合理调度或最优设计等问题.从而提高经济效益,创造更多的价值.而提高经济效益的途径,一方面是靠技术的改革,另一方面要改进生产组织和计划,也就是作到合理安排人力、物力资源,合理组织生产过程,在条件不变的情况下统筹安排.在众多可能的方案中,选取出最经济、最合理的一个可行方案,从而进行最优决策.8致谢在此,衷心的感谢周老师在本文写作过程中给予了悉心的指导！参考文献[1][M].(数学规划协会)[2]运筹学(三版)[M].《运筹学》教材编写组.清华大学出版社[3]线性规划导论[M].谢金星,姜启源,张立平等译[4]不等式与线性规划初步[M].吴德风.科学普及出版社[5]最优化模型与实验[M].米德通[6]顾基发,唐锡晋.软系统工程方法论与软运筹学.系统研究[M].浙江人民出版社DisscussionontheusageoflinearprogramminginpracticeHeTongleiinstructor:ZhouJun(StudentNumber3Class5of2007,SpecialtyofMathematicsandAppliedMathematicsDepartementofMathematics,HexiUniversity,