线性规划理论及其应用

毕业论文开题报告信息与计算科学线性规划理论及其应用一、选题的背景、意义[1][2]选题的背景线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料 .二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好 .一般地，求线性目标函数在线性约束条件下的最大化或最小化的问题，最大化问题是要在一个集合上使一个函数达到最大，最小化问题是要在一个集合上使一个函数达到最小。统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素。随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制定最佳决策的有力工具。选题的意义随着计算机技术的发展和普及，线性规划的应用越来越广泛。它已成为人们为合理利用有限资源制定最佳决策的有力工具。随着经济全球化的不断发展，企业面临更加激烈的市场竞争。企业必须不断提高盈利水平，增强其获利能力，在生产、销售、新产品研发等一系列过程中只有自己的优势，提高企业效率，降低成本，形成企业的核心竞争力，才能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销等方面没有利用线性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。在竞争日益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知识对战略计划、生产，销售各个环节进行优化从而降低生产成本，提高企业的效率。在各类经

济活动中，经常遇到这样的问题：在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”（LinearProgramming，简记为LP）问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益（产量最多、利润最大、效用最高）。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源（如资金，设备，原材料、人工、时间等）去完成任务。二、研究的基本内容与拟解决的主要问题2.1线性规划理论发展过程及方向2.1.1线性规划发展过程[3][4]法国数学家J.-B.-J.傅里叶和C.瓦莱一普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家刀.B.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹奇克提出线性规划的一般数学模型和求解线性规划问题的通用方法一一单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论，开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、 随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。

1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为 5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。2.1.2线性规划理论的发展方向[5][6][7]线性规划在军事、工农业、交通和城镇规划等领域中得到广泛的应用。实际问题有的是很大的，大到具有几万、几十万甚至上百万的变量和成千上万的约束条件。有的问题虽小些，一般也有几百几千的变量和成百上千的约束条件。显然解这类问题都离不开计算机。常用的计算机软件有LINGO,LINDO,MATLAB等。线性规划理论与大系统分析理论相结合，以解决经济、社会、生态、和政治因素交织在一起的复杂社会系统问题，或者解决设计、工艺、质量、生产计划、大型试验、技术改造、成本价格、市场营销等因素交织在一起的企业管理中的复杂问题，是线性规划理论的主要方向之一。在大系统理论中，对于一些含有几个层级的系统（系统含有分系统，分系统又含有子系统，子系统又含有更小的子系统等），通常采用递阶分析的方法进行分解和分析。从系统观点考虑问题的多学科优化理论和方法的研究与应用，已经成为线性规划理论的重要发展方向之一。我国的现代化建设进程中，众多大系统工程（如三峡工程、载人航天工程）中，也大量的采用了系统工程的一些科学方法，并取得了显著的成效。反过来，实践的发展又不断地催生新的理论，或者不断地开拓已有应用范围，不断地创新理论和方法，是所有学科发展的生命力源泉之所在，线性规划理论的发展也不例外。2.2线性规划的具体实现2.2.1线性规划问题的基本步骤⑻（1） 提出并抽象问题（2） 建立数学模型（3） 求解（4） 检验解（5） 解得灵敏度分析

（6）解得回归2.2.2线性规划方法的运用原则[8]（1） 合作原则（2） 打破常规原则（3） 相互渗透原则（4） 客观独立性原则（5） 包容性原则（6） 平衡性原则2.2.3线性规划问题的数学模型的一般形式[2]（1） 列出约束条件及目标函数（2） 画出约束条件所表示的可行域（3） 在可行域内求目标函数的最优解及最优值2.2.4线性规划的模型建立[1][2][9]从实际问题中建立数学模型一般有以下三个步骤；根据影响所要达到目的的因素找到决策变量；由决策变量和所在达到目的之间的函数关系确定目标函数；由决策变量所受的限制条件确定决策变量所要满足的约束条件。所建立的数学模型具有以下特点：1、 每个模型都有若干个决策变量3,x,x,X），其中n为决策变量个数。1 2 3 n决策变量的一组值表示一种方案，同时决策变量一般是非负的。2、 目标函数是决策变量的线性函数，根据具体问题可以是最大化 （max）或最小化（min），二者统称为最优化（opt）。3、 约束条件也是决策变量的线性函数。当我们得到的数学模型的目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。2.2.5线性规划的解法求解线性规划问题的基本方法是单纯形法，现在已有单纯形法的标准软件，可在

电子计算机上求解约束条件和决策变量数达 10000个以上的线性规划问题。为了提高解题速度，又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。对于只有两个变量的简单的线性规划问题，也可采用图解法求解。这种方法仅适用于只有两个变量的线性规划问题。它的特点是直观而易于理解，但实用价值不大。通过图解法求解可以理解线性规划的一些基本概念。2.2.5.1单纯形法[1][2]单纯形法是求解线性规划问题的一般方法，原则上它适用于任何线性规划问题。这是丹齐克在1947年提出来的.它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。大量的实际表明，这是一种行之有效的解法.单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代，直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。下面把单纯形法的计算步骤及迭代过程归结如下图：显否所有LwnM算停止）得慌优解）汁算峥显否所有LwnM算停止）得慌优解）汁算峥止\是占所有hir/给山初排时行/底段对^典式换痢（以阡代咨凡）并术出新典式BJS■噤并得出单纯形表:C-CB-1A CB-1bB-iA B-ib这样就可以得出一般线性规划问题的解。有关单纯形法的进一步讨论，当线性规划问题化为标准形式后约束条件的系数矩阵中含有单位矩阵，以此作初始基，用人工变量法（划法）求解。用大M法处理人工变量，在用手工计算求解时不会碰到麻烦，但用电子计算机求解时，由于计算机取值时的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。2.2.5.2对偶单纯形法[6]每一个线性规划问题都有另一个与其相互关联的问题，这个新问题具有非常重要的性质，用这些性质可以更加有效地获得原来问题的解。为区别起见，我们称原来的问题为原问题，称与原问题相关联的问题为对偶问题。对偶理论以如下的线性规划问题和其对偶问题:P:mincxDP:mincx[Ax>b [wA<cs.t< s.t<[x>0 [w>0这里P表示原问题，D表示对偶问题。对偶单纯形法对偶单纯形算法可以概括如下：找出原问题的一个基B，构成起始对偶基可行解，是c对所有的j有c-z=c-CB-ia>0jjjBj构成原始对偶单纯形法表；(2)假如b=B-ib>0，则当前的解是最优解，停止计算。否则选择枢行r，其brV0，例如选择你最小者：br=minj}假如对所有列j,yrj>0，则对偶问题无界，原问题无解，停止计算。否则选择枢列k；以yrk为枢元素变换对偶单纯形表，然后转达步骤(2)。2.2.5.3灵敏度分析[2]⑹灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。灵敏度分析意义很大。其一，很多实际问题中数据常常是不够精确的，很多是估计出来的，因此调整数据是常事。其二，当一个用于决策的问题得出最优解后，决策者为了通观全局，常常要研究其中某些因素(数据)的改变对当前最优决策所造成的影响。其三，当作多种方案比较时，这些不同方案常常是某些数据不同而已。灵敏度分析的步骤可归纳如下：将参数的改变通过计算反映到最终单纯形表来。具体方法是，按照下列公式计算出由参数"，b.,c的变化而引起的最终单纯形表上有关数字的变化。可Ij邸=B-iAb询'=B-iAp(c-z)'=c-祝ay*jjjjii=1检查原问题是否仍为可行解。检查对偶问题是否仍为可行解。按下表所列情况得出结论或决定继续计算的步骤。原问题对偶问题结论或继续计算的步骤可行解可行解问题的最优解或最优基不变可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引用人工变量，编制新的单纯形表重新计算2.2.6线性规划的其他算法和问题[1][6]分解算法分解算法是一种处理大型问题的方法，它把一个大型问题分解成若干个规模较小的问题来求解，这种方法不仅可以减少存储量，也能减少计算量。因为线性规划的计算量对于约束条件的个数m很敏感，统计表明，计算量大约与m3成正比，因此，若把一个大型问题转化为求解若干个小型问题，由于每个小型问题的约束条件个数较少，可使总的计算量大大减少。Karmarkar算法1984年N.Karmarkar提出了一个属于多项式时间算法的内点法，并证明其计算复杂性是0，这是一种能解决大型线性规划问题的强有力的算法。它的应用十分广泛，如应用这一系统规模的多项式时间算法用于电力系统，可以使实时电价计算等问题变的简单。整数线性规划问题在线性规划问题中，当某些变量(或全部变量)取整数值时，该规划问题就称为整数规划问题。整数规划可以看成是线性规划问题中对变量进行整数约束的一种特殊形式，因此，可以认为，整数规划问题一般要比相应的线性规划问题约束得更紧。整数规划中，如果所有的变量都要求取整数值，则称此规划问题为纯整数规划；如果部分变量要求取整数值，则称此规划问题为混合整数规划；如果要求变量的取值为0或1，则称此规划问题为0-1规划。影子价格与影子成本[10]根据线性规划问题对偶变量和影子价格的经济意义，给出了影子成本的概念，讨论了影子成本与对偶价格的关系。通过灵敏度分析给出了影子成本的动态表示，并进一步阐明了影子价格和影子成本的惟一性以及影子成本在经济管理中的应用。有界变量线性规划问题实际应用中的许多线性规划问题，其决策变量具有上、下界限制。这类问题称为有界变量线性规划问题。它的一般数学模型可写为minx°=cx，s.tAx=b，l<x<u,其中，l=(l,l,...,l)t,U=(U,U，…,U)T分别为x=(x,x，…,x)T的下界和上界；12n 1 2n 1 2nA认为mxn阶矩阵，n>m>1，并设A的秩为m.2.3线性规划理论的应用2.3.1线性规划在企业中运用的必要性[11]随着经济全球化的不断发展，企业面临更加激烈的市场竞争。企业必须不断提高盈利水平，增强其获利能力，在生产、销售、新产品研发等一系列过程中只有自己的优势，提高企业效率，降低成本，形成企业的核心竞争力，才能在激烈的竞争中立于不败之地。过去很多企业在生产、运输、市场营销等方面没有利用线性规划进行合理的配置，从而增加了企业的生产，使企业的利润不能达到最大化。在竞争日益激烈的今天，如果还按照过去的方式，是难以生存的，所以就有必要利用线性规划的知识对战略计划、生产，销售各个环节进行优化从而降低生产成本，提高企业的效率。在各类经济活动中，经常遇到这样的问题:在生产条件不变的情况下，如何通过统筹安排，改进生产组织或计划，合理安排人力、物力资源，组织生产过程，使总的经济效益最好。这样的问题常常可以化成或近似地化成所谓的“线性规划”（LinearPmgramming,简记为LP）问题。线性规划是应用分析、量化的方法，对经济管理系统中的人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现有效管理。利用线性规划我们可以解决很多问题。如：在不违反一定资源限制下，组织安排生产，获得最好的经济效益（产量最多、利润最大、效用最高）。也可以在满足一定需求条件下，进行合理配置，使成本最小。同时还可以在任务或目标确定后，统筹兼顾，合理安排，用最少的资源（如资金，设备，原材料、人工、时间等）去完成任务。2.3.2线性规划的应用实例数学与经济的结合由来已久。从经济学作为一门学科的发展看，数学在其中的位置越来越重要，它不仅帮助人们在经营中获利，而且给予人们以能力，包括直观思维、逻辑思维、精确计算等等，以至于今天，不懂数学就无法研究经济。前苏联数学家坎托罗维奇因对物资最优调拨理论的贡献获1975年诺贝尔奖，他被公认为最优规划理论的创始人，经济数学理论的奠基人。坎托罗维奇创造的线性规划方法被广泛地应用于经济领域并为经济发展作出了卓越贡献。［⑵线性规划作为运筹学的一个重要分支，在经济管理中有着极其广泛的应用，比如设计一个物流网络的问题。［13］以下是一些常用的应用举例。线性规划在薪酬管理中的应用［14］知识经济时代，现代化的大型企业或企业集团不断涌现，大企业的内部管理模式更加复杂，必须提高企业内部的控制力、执行力、及对市场变化能够快速做出的反应能力。线性规划是人们进行科学管理的一种数学方法，通过在薪酬管理宏观和微观两方面的应用，提高企业管理水平，实现最佳经济效益。线性规划在企业生产计划中的应用［15］在企业生产过程中，生产计划安排直接影响到企业的经济效益，而解决生产计划问题的有效方法之一就是建立线性规划模型，线性规划为企业制定生产计划提供了一种简单又科学的方法，具有一定的实用价值。线性规划在服装生产任务分配中的应用［16］针对不确定条件下实际的服装生产任务分配问题，采用线性规划优化的方法予以解决。为此，建立了服装生产任务分配的数学模型，在保证交货期的前提下，将线性规划法对生产任务进行优化分配，使加工成本最小。生产实例表明，所提出的优化方法能够使服装生产系统得到整体优化，表明其有效性和可行性。线性规划在企业成本控制中的应用M企业成本由原材料，制造费用等要素构成，通过构建企业成本构成的数学模型及约束条件，求解使企业成本总体最低的最优解，同时解释各要素变化对企业利润的影响程度，为企业成本控制指明方向。线性规划在饮料的生产销售模型中的应用四应用运筹学中的线性规划原理，研究了在给定务件下，按某一衡量指标来寻找安排的最优方案问题.且研究了工厂安排合理的生产计划、管理资源和人力资源，使得企业在有限的资本情况下，获得总费用最少或者总收益最大问题.根据该实际情况将问题简单化为饮料的生产销售问题，建立了线性规划的数学模型.用MATLAB软件进行了模型求解.使得求解过程简便且得到的结果较准确.通过模型检验，进一步改进了模型，使其更加符合实际.最后将该模型推广到了更加广泛的情形。三、研究的方法与技术路线、研究难点，预期达到的目标研究内容了解线性规划理论的发展历史、基本概念及意义，知道线性规划理论的基本模型和模型特点。对线性规划问题有深刻认识，掌握解决线性规划问题的基本方法，了解线性规划研究的基本问题，了解线性规划在社会经济管理中的应用。清楚线性规划理论今后的发展方向及进一步研究需要的知识。研究方法及技术路线文献研究法。根据线性规划理论及其应用的课题，通过阅读文献来获得相关资料，从而全面地、正确地了解掌握所要研究问题的一种方法。其作用有：能了解有关问题的历史和现状，帮助确定研究课题；能形成关于研究对象的一般印象；能得到现实资料的比较资料；有助于了解事物的全貌。对比分析法。根据线性规划理论及其应用的课题，通过研究对象之间对比进行分析、讨论，从中得出结论，从而全面地、正确地了解掌握所要研究问题的一种方法。其作用有：通过具体对象的对比分析，更加加深对其的认识；能启发人们的思维。研究难点(1)对线性规划理论的基本理论知识及它在社会经济管理中的应用的掌握程度有待加强，对线性规划理论的方法及应用的广度有待拓宽；（2） 由于论题比较宽泛，很难有对一点或一面进行深入研究和探讨；（3） 线性规划理论的方法有很多种，本文只讲述基本的方法；（4） 线性规划的应用领域很广泛，本文只论述常见的方面。对具体的应用例子中的优缺点和改进方面论述不够具体和详细；4、预期达到的目标通过这次论文的撰写更好的了解了线性规划理论的发展历史、基本概念，深入的认识了线性规划问题，更好的掌握了解决线性规划问题的方法，并会应用此理论来解决社会经济中常见的优化问题，同时还可以结合其他知识来综合解决这类问题。除此，对线性规划理论的掌握，还能更好的学习其他相关理论，能更好的解决这类问题。四、 论文详细工作进度和安排第7学期第9周（2010年11月5号）至第7学期第19周（2011年1月10号）完成毕业论文文献检索、文献综述、外文文献翻译及开题报告。第7学期第19周（2011年1月10号）至第8学期第3周（2011年3月11号）完成毕业论文的数据收集、论文初稿。第8学期第3周（2011年3月11号）至第8学期第11周（2011年5月3号）1、 进入实习单位进行毕业实习，对论文进行修改；2、 第11周（2011年5月3日）前必须返校，完成毕业实习返校，并递交毕业实习报告，进一步完善毕业论文；第8学期第14周（2011年5月23号2011年5月28号）完成第一轮毕业论文答辩；第8学期第15周（2011年5月28号2011年6月3号）第一轮毕业论文答辩未通过的学生完成第二轮毕业论文答辩，并随机抽取部分完成较好地毕业论文进行校级答辩五、 主要参考文献：张干宗.线性规划[M].第二版.武汉:武汉大学出版社,2008,6:1-39.胡运权.运筹学教程[M].第三版.北京:清华大学出版社,2007,4:1-10