《线性规划问题及其软件实现本科毕业论文.doc》由会员分享，可在线阅读，更多相关《线性规划问题及其软件实现本科毕业论文.doc（21页珍藏版）》请在三一文库上搜索。
1、贵州师范学院毕业论文（设计）学科分类号 本 科 毕 业 论 文 题 目 线性规划问题及其软件实现 Title Linear programming problem and its software implementation 姓 名 学 号 院 （系） 数学与计算机科学学院 专 业 数学与应用数学 年 级 2010级 指导教师 职 称 讲师 二一 年 月 贵州师范学院本科毕业论文（设计）诚信声明本人郑重声明：所呈交的本科毕业论文(设计)，是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作
2、品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 本科毕业论文作者签名：（亲笔签名） 年 月 日目 录摘 要1ABSTACT：1引言21线性规划的简介及其来源32线性规划初步认识52.1 什么叫规划52.2如何进行规划53数学模型64线性规划的解法75线性规划的应用85.1 分析条件85.2模型假设85.3模型应用95.4用LINGO软件求解106 解决问题126.1问题126.2 模型建立136.3 模型求解14参考文献17致谢18摘 要 随着世界科学技术的不断发展，我们面临更加激烈的市场竞争。生活中的很多问题涉及线性规划问题，
3、如组合投资、运输问题、生产组织问题等，而这些问题需要解决，所以产生了软件来解决这些问题。基于这些，我们可以通过将线性规划问题的数学模型的一般形式转变为标准形式，从而应用单纯形法求解。并用LINGO软件分析解决问题。关键词：线性规划；单纯形法；模型建立ABSTACT：With the continuous development of science and technology in the world, we are facing more and more fierce market competition. Many of lifes problems involving linear
4、programming problems, such as portfolio investment, transportation, production problems, and these problems need to be solved, so the software to solve these problems. Based on these, we can through the general form of linear programming mathematical model of the problem into a standard form, and ap
5、plication of the simplex method. And using LINGO software to analyze and solve problems.Key words: linear programming ; simplex method ; LINGOsoftware引言 在生活、生产、管理等各类经济活动中，我们经常遇到这样的问题：什么是最好的决策、最佳的方案。例如消费者的总收入一定，怎样买物品才能使消费者获得最大的利益；企业在生产条件不变的前提下，怎样统筹安排，改变其他条件，使得生产成本最低；工厂在各原材料固定的情况下，如何最佳地使用原材料使得利润最大等等。这
6、些生产的最优化决策问题都可以通过建立相应的线性规划模型，即转化为线性规划问题通过数学运算进行解决。 线性规划是数学规划与运筹学的分支，线性规划所处理的问题是在现实生活中如何用最优计划来获得最大利润，如何充分发挥资源配置等。为了得到一个最优结果，线性规划先拟定计划，然后在备选方案中选择最好方案。随着经济管理理论知识和线性规划方法的更紧密结合。由于线性规划的研究越来越深入，线性规划在经济管理中应用的范围也越来越广泛，几乎整个社会都有运用到，像社会、经济、生态等等，而且在微观和宏观上都得到了应用。近十几年来，线性规划在我国的许多领域也得到了很好的应用，取得了可喜的成绩。资源不是无限的，怎样分配有限的
7、资源才能得的我们想要的结果；而在各种经济活动中，怎样提升经济效益，耗费最少的劳动力，得到较多的使用价值，这些问题涉及分配，而线性规划为最优分配提供了工具。线性规划研究的问题主要有两类：一是一项任务确定后，怎样规划设计，怎样用较少的资源去做完这个任务这是很重要的；二是已经拥有确定数量的资源，怎样安排使用它们，让任务完成的最好这也是一个令人思考的问题。本文将运用线性规划模型，做出方案，帮助企业在已有的产业资源下，怎样才能获得最大利润。运用线性代数知识刚好可以建立数学模型，这样有助于解决这类难题，从而获得有依据的最好方案。1线性规划的简介及其来源 线性规划是运筹学中研究较早、发展较快、应用广泛、方法
8、较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提升经济效果是人们不可或缺的，所以提升经济效果可以有两种路径：一是有关技术方面的改进，如生产工艺的改善，使用新设备和新型原材料.二是生产组织与计划的改进，如有效的安排资源，他探讨的是：在一定基础上，人力、物力等资源的合理安排，这样会得到不一样的经济效果。通常情况下，应用线性规划模型，求解在线性限制条件条件下的线性目标函数的极大值或极小值的问题，这个问题被称为线性规划问题。可行解是满足线性限制条件条件的解，所有可行解组成的集合叫做可行域。决策变量、限制条件条件、目标函数是线性规划的三要素。
9、由于现在科技的发展，有很多软件可以解决线性规划问题，比如MATLAB软件等等。 1911年，比利时数学家VPoussin写了一篇涉及线性规划的论文，22年后，法国数学家JBJFourier在此基础上也写了一篇关于线性规划的问题，然而这些孤立的工作没有产生任何影响。到了1939年，苏联数学家.康托罗维奇在生产组织与计划中的数学方法中提出线性规划问题，也未引起重视。 直到1947年，单纯形法的提出者美国数学家G.B.丹齐克，单纯形法是线性规划的一般数学模型，也是求解线性规划问题的常用方法，通常被认为标志着一个新学科的诞生。同一年，美国数学家J.von诺伊曼得出对偶理论,让更多的新领域得到研究，拓宽
10、线性规划的使用范围及解题能力。而在1951年，美国经济学家T.C.库普曼斯把这种方法运用到经济领域，因为这项发现他与康托罗维奇一起获得1975年诺贝尔经济学奖。此后，此线性规划逐渐成熟起来，并且发展的越来越好，也出现很多适用于运算线性规划的软件，如LINGO软件、MPSX等等，能够简便地求解多个变量的线性规划问题。 1979年，苏联数学家L. G. Khachian得出求解线性规划问题的另一种算法椭球算法，而且还验证它是多项式时间算法。1984年，印度数学家N.卡马卡提出新的多项式时间算法，用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50，这对当时的研究来说，这是
11、一个全新的研究。 对于优化设计，可以将发动机的三个学科循环、流体通路、推进、变速系统，将他们的设计数据进行统筹优化，再根据多维目标将发动机寿命和变速范围最大化、成本与油料消耗最小化来进行规划，这些都取得了显著的效果。因此从系统观点考虑问题的大系统、多学科优化理论和方法的研究与应用，已经成为线性规划理论的重要发展方向之一。 在我国的现代化建设过程中，众多大系统工程(比如三峡工程、载人航天工程)中，也大量地采用了系统工程的一些科学方法，取得了显著的成效。相反的，实践不断产生新的理论，或不停地拓宽现有的使用范围，不间断地开创全新理念和办法，这也正是全部学科发展的生命力源泉，当然也包括线性规划。2线性
12、规划初步认识2.1 什么叫规划 通俗地讲：规划是一种特定的过程，它的基础是某个事情触及的战略原则、资源范围和技术性控制等，推演各种条件组合下所能产生的各种结果，并根据优化原则对逻辑推理结果做出分析与评价，从中找出对当事人（系统)最有利的结果，并给出应该限制(减少)哪些活动要素(单元)，加强(增加)哪些活动要素(单元)，哪些资源显得剩余，哪些资源显得不足的信息与建议。规划的流程，其本质是要实现某个特殊目标对其相关事物的发展过程的优化分析。小到一个人、一个家庭、一个课题小组，大到一个企业、一个科研院所，甚至一个国家，只要是一个利益和权益主体，要想在推进事物发展的过程中获得最多的利益或最优的结果，就
13、都需要进行科学的运筹和规划。现在的大学很多也开设了这门课程，就是希望能够好好的掌握这种方法。 2.2如何进行规划 规划的过程本质上讲就是在特定的资源条件、特定的运行规则和特定的价值取向限制条件下，进行方案优化选择的过程。任何需要并且可以通过选择运行要素来选择结果的事件，都应该进行预先的规划。 任何一种特定的活动(过程)，在其进行的过程中，只要没有达到结束的那个时刻，就存在选择结果的机会，因此，也就存在规划的必要。当然，效益最高的规划是事件还没有发生之前的规划，因为这时的规划最有效果。3数学模型 线性规划的一般数学模型为：求一个线性目标函数的最优值，可以是最大值，也可以是最小值，而且要满足一组线
14、性不等式(或线性等式)，其数学模型由三个要素构成：(1)变量，是问题中需要确定的未知量，它说明规划用数量表示的计划、步骤，能够有决策者确定及限定；决策变量的取值，可以为任何数，但在通常情况下，要求为非负的、连续的实数。(2)目标函数，是决策变量的线性表达式，根据线性目标可以在这个表达式前加上max或min。(3)限制条件，是含变量的线性不等式(或线性等式)，它表示决策变量在取值过程中受到的不同资源条件的局限。线性规划的定义如下： 定义：在满足一组线性限制条件(线性不等式或线性等式)的若干决策变量组中，寻找能使线性目标函数(决策变量的线性表达式)达到最优值(最大值或最小值)的数学问题，称为线性规
15、划问题。线性规划问题的一般模型如下：max(或min)f=st. 上述模型的简写形式为：max(或min)f=st. (i=) x0 (i=) 有矩阵和向量形式来表示可写为： Max(或min)f=CX St. AX(或=，)b X0 A=其中：C是一个n维行向量；X是一个n维列向量；b是一个m维列向量。4线性规划的解法 求解线性规划问题的基本方法是单纯形法，如今已有标准软件来证明，能够在电脑解决限制条件及决策变量数高达万个的线性规划难题，而且也发现了多种不同的算法，所以现在的线性规划问题不算难题了。两个变量的线性规划问题能够采用简单易于观察的图解法来解决，但实用价值不大。通过图解法求解能够了
16、解线性规划的一些简单概念。因此，在解决线性规划问题时，多数情况下采用单纯形法。 5线性规划的应用 线性规划问题是比较常见的问题，所以本文将以羊奶销售问题和水的运输问题为例来加以研究。5.1 分析条件 加工厂用羊奶生产、两种奶制品，甲机器用12小时把1桶羊奶加工成3公斤的，或乙机器用8小时把1桶羊奶加工成4公斤的。根据市场的需求，生产的、均可以卖出，且每斤可以获利12元，每斤A2可以获利8元。如今加工厂每天可以有50桶羊奶的供应，每天正式工人总的劳动时间为480小时，并且甲机器每天至多能加工100公斤，乙机器的加工能力不加以限制。现在需要拟定一个生产计划，使每天都获得最大的利润，再更深的讨论以下
17、问题：1）1桶羊奶用35元可以购买到，这项投资能不能进行？如果要投资，每天最多可以购买多少桶羊奶？2）如果为了增加劳动时间来聘用一些临时工人，那么给这些临时工人的工资最多是每小时几元？3）因为市场需要的变化，的利润增加到30元/公斤，这时候是否需要改变生产计划？5.2模型假设 ,:羊奶的两种类型； :每天用于生产的羊奶的桶数； :每天用于生产A2的羊奶的桶数；5.3模型应用数学模型 设每天用桶羊奶生产 ，用桶羊奶生产 ；目标函数 设每天获利为z元。桶羊奶可生产3公斤，获利24*3，桶羊奶可生产4公斤，获利16*4，故z=72+64限制条件条件 原料供应 生产、的原料（羊奶）总量不超过每天的供应
18、50桶，即 +50劳动时间 生产、的总加工时间不超过每天正式工人总的劳动时间480小时，即 12+8480机器能力 的产量不得超过设备甲每天的加工能力100小时，即 3100非负限制条件 、均不能为负值，即0，0综上所述可得Max z=72+64 (1)s.t. +50 (2)12+8480 (3)3100 (4)0，0 (5)5.4用LINGO软件求解 在LINGO下新建一个模型文件，直接输入：Model:Max=72*x1+64*x2;milkx1+x250;time12*x1+8*x2480;cpct 3*x1100;End 运算结果为：Global optimal solution f
19、ound.Objective value: 3360.000Total solver iterations: 2Variable Value Reduced Cost X1 20.000000 0.000000 X2 30.000000 0.000000Row Slack or surplus Dual price MILK 0.000000 48.000000 TIME 0.000000 2.000000 CPCT 40.000000 0.000000计算结果分析：从这个结果可以看到：=20.000000，=30.000000。敏感性分析：Ranges in which the basis
20、is unchanged: Objective Coefficient RangesCurrent Allowable Allowable Variable Cofficient Increase Decrease X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES Row Current Allowable Allowable RHS Increase Decrease MILK 50.000000 10.000000 6.666667 TIME 480.000000 53
21、.333332 80.000000 CPCT 100.000000 INFINITY 40.000000“GURRENT COEF“（敏感性分析）的“ALLOWABLE INCREASE”(允许的增加量)和“ALLOWABLE DECREASE”(允许的减少量)给出了最优解不变条件下目标函数系数的允许变化范围：的系数为（72-8，72+24）即（64，96）。并且，x1系数的允许范围需要的系数保持64不变。的系数为（64-16，64+8）即（48，72）。同理，x2系数的允许范围需要x1的系数保持72不变。对附加问题的回答：（1） 由于一桶羊奶的影子价格为48元，因为35=30;+=70;+=
22、10;x+=10;+=50;end输出结果 OBJECTIVE FUNCTION VALUE 1) 24400.00 VARIABLE VALUE REDUCED COST X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.000000 0.000000 X32 0.
23、000000 10.000000 X33 10.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 可以看到，最合适的送水方案为：甲区由C水库供应40千吨，乙区由A、B水库都分别供应50千吨，丙区由C水库供应10千吨，丁区由B水库供应10千吨，那么有饮水管理费24 400元，利润144 000-72 000-24 000=47 600元。 另外，在撰写论文的过程中，我的专业综合能力明显比以前增强了许多，让我更有信心。在撰写论文遇到阻碍时，先自己努力使用各种方式来查阅资料，实在搞
24、不明白，我就虚心向老师和同学请教。总体上，我觉得自己态度还是比较好的，没有那种敷衍的心理，既然做一件事情了，那就要把它做到最好。 与此同时，我自身也存在很多问题。譬如我在撰写过程中会遇到很多阻碍，但是缺乏一定的耐心，急于求成，不能定不下心来去冷静地思考进而想出对策来解决问题。为了尽早完成毕业设计，便四处寻求老师、学长、同事，寻求他人的指引。但是我后来才发现，其实没有必要向他们请教太多问题，应该自己去查找资料，培养自学的能力。这个方面，我感觉自己做得不够好，在今后的工作生活中，我会努力完善自己。除此之外，虽然本次毕业设计的倒立摆仿真效果还不错，但实际控制效果不是很好，主要是模糊控制那一块做得不怎
25、么完美，以后有时间，我会继续怎么完善模糊算法，分析出影响实际控制效果的因素，提高实际控制效果，找出理论和实际有如此差距的原因。通过这几个月的努力，本次毕业设计的效果基本实现了。 参考文献1张干宗.线性规划第二版. 武汉大学出版社,2007年.2潘平奇著. 线性规划计算(上). 科学出版社, 2012.3高红卫.实用线性规划工具.科学出版社,2007年.4吕彬，郭全魁，陈磊著.线性规划问题的新算法.国防工业出版社,2013.5姜启源，谢金星，叶俊编. 数学模型（第四版）.高等教育出版社,2011.6李朝霞. 线性规划的数学模型及实际应用J. 宿州教育学院学报, 2006, (01) . 7卢刚夫
26、. 浅谈线性规划方法的应用J. 商场现代化, 2007, (36) 8刘红.数学建模过程中若干常见问题处理的技巧J.成都航空职业技术学院学报，2000，16（4） 9许海深.数学模型及数学建模的逻辑变量方法J.哈尔滨师范大学自然科学学报，2005，21（2）致谢 此文章从拟订题目到定稿，历时数月首先要向我的指导老师致以诚挚的谢意杨国荣老师在本次写作过程中耐心的指导，从论文的选题到撰写，每道步骤都经过他严格指导，这几个月来，他给予了我很多的指导和帮助，使我有了进一步的并在论文资料方面以及论文的结构格式和论文的修改方面给予了宝贵提议，在此表示由衷的感谢！同时他对工作的积极热情、认真负责、有条不紊、实事求是的态度，给我留下了深刻的印象，使我受益非浅在此我谨向杨老师表示忠心的感谢和深深的敬意。 最后，向我的同学和朋友表示深深的谢意，他们给予我的爱、帮助、关心和支持是我不断前进的动力。以后，将是我终身学习的开始。 18