线性规划在实际问题中的应用.doc

分类号： 029 单位代码： 106 密 级： 学 号： 本科毕业论文（设计） 题 目：线性规划在实际问题中的应用 专 业： 数学与应用数学 姓 名： 指导老师： 职 称： 讲师 答辩日期： 二一三年五月十八日 延安大学学士学位论文原创性声明本人郑重声明：所呈交的学位论文,是本人在指导教师的指导下,独立进行研究所取得的成果.除文中已经注明引用的内容外,本论文不含任何其他个人或集体已经发表或撰写过的作品成果.对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明.本人完全意识到本声明的法律结果由本人承担.作者签名：_ 日期：_关于论文使用授权的说明学位论文作者完全了解延安大学有关保留和使用论文的规定,即：本科生在校攻读学士学位期间论文工作的知识产权单位属延安大学,学生公开发表需经指导教师同意.学校有权保留并向国家有关部门或机构送交论文的复印件,允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容,可以允许采用影印、缩印或者其他复制手段保存、汇编学位论文.保密论文注释：本学位论文属于保密范围,在2年解密后适用本授权书.非保密论文注释：本学位论文不属于保密范围,适用本授权书.作者签名：_ 日期：_指导教师签名：_ 日期：_ 线性规划在实际问题中的应用 摘要:本文研究用线性规划的方法解决生活中投资问题和生产问题.通过把实际问题抽象成数学问题建立数学模型,利用LINDO软件进行求解,得到最佳投资方案和生产计划方案，使经济效益最佳。 关键词:线性规划;数学模型;LINDO The application of Linear programming in the practical problemsAbstract:This paper solves two problems of the investment question and the production question by linear programming method . Abstracting the actual problem to a mathematical problem and establishing mathematical model which can be obtained by using LINDO software.At the same time we can get the best investment plan and production plan and make the best economic benefit. Key words: linear programming; mathematical model; LINDO1引言 线性规划作为运筹学的一个重要分支,是研究较早,理论较完善,应用最广泛的一门科学.它所研究的问题主要包括两个方面:一是在一项任务确定后,如何以最低限度和成本（如人力、物力、资金和时间等）去完成这一任务;二是如何在现有条件下进行组织和安排,以完成更多的工作.因此,线性规划就是求一组变量的值,使它满足一组线性式子,并使一个线性函数的值最大（或最小）的数学方法.即有关“多、快、好、省”的最优化问题. 目前运筹学相继在工业、农业、经济和社会问题等各领域都有应用.与此同时,运筹数学有了飞快的发展,并形成了运筹学的许多分支.如数学规划(线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等)、图论与网络、排队论、存贮论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等.线性规划是由丹捷格(G.B.Dantzig)在1947年发表的一篇成果,而应用到实际问题中的是美国空军军事规划小组,当时他们提出了求解线性规划的单纯形法.1974年,Zeleny等将解线性规划的单纯形法给予适当修改后,用来解多目标线性规划问题,或把多目标线性规划问题化成单目标的线性规划问题后求解,给运筹学工作者带来了很大方便,尤其是在求汽车运输调配规划问题上.上世纪六十年代初由LandDoig和Dakin等人提出用分枝定界法求解整数规划问题,由于该法灵活且便于用计算机求解,所以现在它己是解整数规划的重要方法.1951年美国数学家贝尔曼(R.Bellman)创造了解决最优化问题的一种新的方法一一动态规划.动态规划法是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法,但由于动态规划依赖条件较强,且存在维数障碍,故在供料运输的汽车模型上应用不是很广,在总体计划方面主要是从总体确定生产、存贮和劳动力的配合等计划以适应波动的需求计划,主要用线性规划和模拟方法等,国外有关运筹学的理论与实践方面的研究,对国内运筹学的发展起到了促进作用.国内对运筹学的研究始于上世纪80年代,与国外的研究几乎同时起步.钱颂迪、胡运权结合运筹学,运用线性规划和数学模拟方法解决了生产应用中的合理下料、配料问题,以及物料管理等方面的应用.李军、张锦运用线性规划,解决了物流运输中汽车路径选择的原则、方法及技巧,很好地建立了汽车运行费用最少的数学模型,方便物流规划者使用.郭耀煌、陈唐民结合线性规划、多目标决策等理论,重点解决了车辆调配或车流运输中最短时间的数学模型,给车流规划带来了方便.邓先礼、施光燕四人等运用最优化技术,结合线性规划,解决了运输规划中最短路径问题、最佳运费问题,给工程设计提供了参考依据.左永林、柳志新结合水电工程砂石料场优选的实例,运用动态规划的方法解决了供料方案的优化研究.本文主要基于线性规划进行展开研究,以期望对今后生产计划和投资题的顺利进行有所帮助.2预备知识 2.1线性规划的概对于求取一组变量(j =1,2,.,n),使之既满足线性约束条件,又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题,简称线性规划.2.2线性规划的一般形式目标函数： 约束条件： 2.3数学规划模型 一般地说,数学模型可以描述为,对于现实世界的一个特定对象,为了一个特定的目的,根据特有的内在规律,做出一些必要的简化假设,运用适当的数学工具,得到的一个数学结构.2.4线性规划模型的特点(1)决策变量对目标函数以及约束的影响与其取值成比例.(2)任一决策变量对目标函数以及约束的影响独立与其他变量.(3)决策变量允许连续的变化.(4)线性规划问题中的参数是确定的.2.5建立数学规划模型的一般步骤第一步,找出待定的未知变量(决策变量),并用数学符号表示它们.第二步,找出问题中所有的限制或约束,写出未知变量的线性方程或线性不等式.第三步,找到模型的目标或判据,写出决策变量的线性函数,以便求出其最大值或最值.3.正文 线性规划问题是工作和生活中最常见的问题,也是数学规划中最简单和最基础的问题.线性规划是数学规划的一个重要的分支,它历史悠久,理论成熟,方法也比较完善,可以用它来描述实际生活中如生产计划、生产调度、资源分配、运输与物质调配、交通调度、投资组合、人员安排、配料、管道设计、营养调配等.下面从投资和生产计划两个问题来说明.3.1线性规划模型在投资中应用投资是为了获得丰厚的收益.然而任何一种投资都存在着各种风险,使风险降至最低或没有风险是我们所期望的;在风险保持不变的情况下,我们又该选择投资哪种项目,使我们的收益更大,这是我们真正关心的问题.选择哪些项目进行投资,预计投入多少资金,资金的数目是个未知数,即变量;投资中存在各种风险(大小一般能确定),各种风险的总和约束在一定的范围内,即约束条件;每项投资都存在一定的利润所有利润的和,就是我们投资的目标,即目标函数.因此,线性规划是我们经营投资的好帮手.一家美装公司推出一系列新产品委托一家广告,公司做广告,其目的是尽可能多的招徕顾客.下面是市场调查结果：表1 市场调查结果 电视无线电广播杂志白天晚上一次广告费用（千元）40753015受每次广告影响的顾客数（千人）400900500200受每次广告影响的女客数（千人）300400200100 美装公司希望费用过800(千元),还要求:(1)至少要有两百万妇女看广告;(2)电视广告费用不超过500(千元);(3)电视广告白天至少播出3次,晚上时间至少播出2次;(4)通过广播、杂志做的广告要重复5到10次.3.1.1问题分析 该问题的目标是招徕的顾客最多，而要求投入不超过800千元;要的决策是电视白天,电视晚上,无限广播和志分别应该广播的次数;决策受到:广告经费,女顾客数,电视广告次数,广播次数和杂志次数都受到5个条件的限制.按照题目所给,将决策变量,目标函数和约束条件用数学符号表示出来,然后进行结果分析.3.1.2模型假设 (1)假设电视和无线广播播放广告时不会断电. (2)假设插广告后的杂志和插广告之前的杂志销量数量基本持平.3.1.3符号说明 表示目标函数; 表示白天电视播出的次数; 表示晚上电视播出的次数; 表示广播播出的次数; 表示杂志播出的次数;3.1.4模型建立与求解 白天电视播出次数,晚上电视播出次数,无线电广播播出次数,杂志播出次数分别为,. 潜在的顾客数为，即 投资白天电视,晚上电视,广,杂志总和不超过800千元,即 受广告影响的女顾客不得少于200万,即 经费不超过500千元，且播出白天至少3次，晚上至少2次,即, 无线电广播要重复的次数5到10，即 杂志要重复的次数5到10，即 综上可得,线性规划模型 利用LINDO软件进行求解(程序见附录1)输出的结果告诉我们,当最优解,时,最优值为10960千人,即电视白天广告3次,电视晚上广告3次，无线广播广告10次，杂志做的广告10次.可以获得最大潜在人数10960千人.3.2 线性规划在生产计划问题中的应用在日常生活中,我们离不开衣食住行,而衣食住行所学要的东西来自于生产活动,即生产活动为我们生活提供了一切物质.因此,我们离不开生产活动.在原料有限,时间有限,设备有限和各种产品投放市场获得的利润一定的条件下,我们该选择生产哪些产品才能使效益最大化？在这里原料,时间,设备有限是生产过程中的约束条件;生产各种产品的数量是个未知数,各种产品利润总和最大是我们的目标.所以,线性规划是解决生产规划问题的好方法.亚旭制造三场预计制造A,B,C三种产品,生产这三种产品需要三种资源技术：技术服务、劳动力和行政管理能力.下列列出三种产品对每种资源的需要量表2 三种产品对每种资源的需要量产品资源利润技术服务劳动力行政管理A110210B1426C1564现有100h的技术服务、和600h的劳动力和300h的行政管理时间可以使用.(1) 求出此问题的数学,并求出最优化生产方案.(2) 制造部门提出建议,生产一种新产品,该种产品需要技术服务1h、劳动力4h和行政 管理.销售部门预计这种产品售时有8元的单位利润.管理部门应有怎样的决策?(3) 假设该工厂至少生产10件产品C,试确定最优产品品种规划.3.2.1问题分析 (1)优化问题的目标是使获利最大，要作的决策是生产计划,生产多少A产品,生产多少B产品和生产多少C产品?决策受到3个条件限制:技术服务、劳动力、行政管理.按照题目所给,将决策变量、目标函数和约束条件用符号表示出来,然后用分析结果.(2)在问题一的基础上在生产一种新产品D,要是获利最大,作生产计划,分别要生产多少A,B,C,D?决策受到3个条件限制:技术服务、劳动力、行政管理.按照题目所给,将模型用数学符号表示出来,并求出结果,分析结果,确定是否要接受制造部门的建议生产D产品.(3)在限制C产品最少生产10件时,余下的2种产品不作限制,为了使获利最大,作生产计划,限制条件不变,用数学符号语言建立规划模型并求解,得出最优结果. 3.2.2模型假设(1)假设生产A,B,C三种产品的原料供应充足，不会影响生产;(2)假设生产出的每件产品都是合格的;(3)假设产品的市场销售情况良好;3.2.3符号说明 利润函数 表示生产A产品的数量 表示生产B产品的数量 表示生产C产品的数量 表示生产D产品的数量3.2.4模型建立与求解 对问题一的建模与求解三种产品A,B,C分别表示为 生产A,B,C三种产品的利润总和为，即 生产A,B,C三种产品总共需要技术服100h,即 . 生产A,B,C产品总的需要劳动力600h,即 . 生产A,B,C三种产品总的需要行政管300h,即 . 综上可得,线性规划模型 (1) 利用LINDO软件求解（程序见附录2）输出的结果的第,3,5,6,7行明确地告诉我们,最优解,最优值为，即生产A产品33件,生产B产品67件,生产C产品0件,可获得最大利润732元. 对问题二模型建立与求解四种产品A,B,C,D分别表示为生产A,B,C,D四种产品的利润总和为，即 生产A,B,C,D产品总需要技术服100h,即 . 生产A,B,C，D三种产品总的需要劳动600h，. 生产A,B,C产品总的需要行300h,即 . 综上可得，线性规划模型 (2)利用LINDO软件求解(程序见附录4)输出的结果的第2行告诉我们,当分别为任意实数时,最优值为z=833;当这个线性规划为gin 线性规划时第4,6,7,8,9行明确地告诉我们,最优解,最优值,即生产A产品34件,生产B产品14件,生产C产品0件,生产D产品为51件,可获得最大利润832元. 对问题三建模与求解三种产品A,B,C分别表示为 生产A,B,C三种产品的利润总和为，即 . 生产A,B,C三种产品总共需要技术服100h,即 . 生产A,B,C产品总的需要劳动力600h,即 . 生产A,B,C三种产品总的需要行政管300h,即 . 工厂要求生产C产品至少为10见,即 综上可得,线性规划模型 (3) 利用LINDO软件进行求解(程序见附录4)上面的结果的第2行告诉我们,当分别为任意实数时,最优值为=706.6;当这个线性规划为gin线性规划时第4,6,7,8行明确地告诉我们,最优解，最优值，即生产A产品31件,生产B产品59件,生产C产品10件,可获得最大利润704元.3.3模型的评价和推广 (1)线性规划模型简单实用,人为问题较少,可操作性强,能解决生活中的许多问题.如在金融投资中,如何设计比较好的证券组合或者投资项目组合,以便在可接受的风险度内获得尽可能大的投资回报?在产业结构调整,人员的优化组合或者多种商品的生产计划与调度过程中,如何有效地分配资源,以便在特定的空间和时间范围内谋求最大的经济？在工程设计中,选择恰当的,使工程设计方案既满足实际要求,又能降低工程造价;寻找飞行器或者机械的最优轨迹;设计汽车或者飞机的最佳外形,保证其运动的稳定性,减少其运动的阻力,还需要满足隐身性,控制一个化学过程或者机械装置,优化其性能,保证其满足稳定性等.(2)线性规划模型考虑的因素可能不全面，实际中有些情况没有被考虑到，这就使得线性规划模型过于理想化(3)实际运用线性规划模型时,虽然一些因素或约束条件被考虑到了,但是由于这些因素或约束条件不易量化或求得(如进行总生产计划常需考虑到的能源单耗就不易求得)时,线性规划模型的运用和有效性因而受到了一定的限制4小结 本文用线性规划的方法解决了在资金有限、投资项目确定的条件下获益最大的投资问题和在资源有限、人力有限、时间有限的情况下进行统筹安排,使总的经济效益达到最佳.把实际问题抽象成数学问题并建立数学模型,利用LINDO软件进行求解,从而确定投资方案和生产计划.从论文我们知道线性规划模型考虑的因素可能不太全面,实际中有些情况没有被考虑到,因此,在实际运用和有效性受到了一定的限制,但这并不影响我们把线性规划用于解决一些简单的生产计划问题、运输问题、指派问题、配料问题、投资问题等.此外,把实际问题抽象成数学模型,培养了我们应用数学的意识,锻炼了我们的思维能力，使我们全面认识了数学与科学、技术和生活的关系，并提高了分析问题和解决实际问题的能力. 参考文献: 习在筠,刘桂真.运筹学(第三版)M.高等教育出版社,2007.胡运权.运筹学基础及应用M.高等教育出版社,2008.黄玲华.线性规划在现代管理中的应用J.广西商业高等专科学院学报,2004,04:25-27.黄红选,韩继业.数学规划M.清华大学出版社,2006-06.赵静,但琦.数学建模与数学实验M.高等教育出版社,2000-11.谢金星,薛毅.优化建模LINDO/LINGO软件M.清华大学出版社,2005.Mark M.Meerschaert,Mathematical Modeling,Third EditionM.Academic Press,2008.张洪波,张启生.线性规划方法在生产中应用的实例分析J.徐州建筑职业技术学院学 报,2009-03:20-22.谢辞非常感谢李江荣老师在我大学的最后学习阶段-毕业设计对我的指导,从最初的定题,到资料收集,到写作、修改,到论文定稿,她给了我耐心的指导和无私的帮助，这种奉献的精神令我钦佩,在此我向她表示我真诚的谢意.同时感谢张娇同学，谢谢她教会我数学软件的使用.并祝所有的老师培养出优秀的人才，桃李满天下！ (论文共6035字) 附录1max 400x1+900x2+500x3+200x4s.t.2)40x1+75x2+30x3+15x4=20004)40x1+75x2=36)x2=27)x3=58)x3=510)x4=10endgin4LP OPTIMUM FOUND AT STEP 5 OBJECTIVE FUNCTION VALUE 1) 10960.00 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 3.066667 0.000000 X3 10.000000 0.000000 X4 10.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 12.000000 3) 3126.666748 0.000000 4) 150.000000 0.000000 5) 0.000000 -80.000000 6) 1.066667 0.000000 7) 5.000000 0.000000 8) 0.000000 140.000000 9) 5.000000 0.000000 10) 0.000000 20.000000 NO. ITERATIONS= 5 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 400.000000 80.000000 INFINITY X2 900.000000 100.000000 149.999985 X3 500.000000 INFINITY 140.000000 X4 200.000000 INFINITY 20.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 800.000000 150.000000 80.000000 3 2000.000000 3126.666748 INFINITY 4 500.000000 INFINITY 150.000000 5 3.000000 2.000000 3.000000 6 2.000000 1.066667 INFINITY 7 5.000000 5.000000 INFINITY 8 10.000000 2.666667 5.000000 9 5.000000 5.000000 INFINITY 10 10.000000 5.333333 5.000000附录2程序：max 10x1+6x2+4x3stx1+x2+x3=10010x1+4x2+5x36002x1+2x2+6x3 0.000000E+00 SET X1 TO = 34 AT 1, BND= 730.0 TWIN= 732.0 8 NEW INTEGER SOLUTION OF 730.000000 AT BRANCH 1 PIVOT 8 BOUND ON OPTIMUM: 733.3333 FLIP X1 TO = 33 AT 1 WITH BND= 732.00000 NEW INTEGER SOLUTION OF 732.000000 AT BRANCH 1 PIVOT 8 BOUND ON OPTIMUM: 733.3333 DELETE X1 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 8 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION. OBJECTIVE FUNCTION VALUE 1) 732.0000 VARIABLE VALUE REDUCED COST X1 33.000000 -10.000000 X2 67.000000 -6.000000 X3 0.000000 -4.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 2.000000 0.000000 4) 100.000000 0.000000 NO. ITERATIONS= 8 BRANCHES= 1 DETERM.= 1.000E 0附录3程序：max 10x1+6x2+4x3+8x4stx1+x2+x3+x4=10010x1+4x2+5x3+4x4=6002x1+2x2+6x3+4x4 0.000000E+00 SET X1 TO = 34 AT 1, BND= 832.0 TWIN= 832.0 8 NEW INTEGER SOLUTION OF 832.000000 AT BRANCH 1 PIVOT 8 BOUND ON OPTIMUM: 833.3333 DELETE X1 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 8 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTIO