浅谈线性规划中的检验数(2)
时间:2019-09-29 20:04 来源:毕业论文 作者:毕业论文 点击:次
自从《生产组织与计划中的数学方法》一文的问世开创了线性规划问题相关理论以来,近百年来,随着线性规划在人类的生产生活中发挥的重大作用及其在工业生产中的重要指导意义,促进者后继的数学家和研究工作者不断深入研究完善线性规划理论和实际应用.美国数学家G.B. Dantzing在1947年提出单纯形法的求解方法,奠定了线性规划发展的基础,有着至关重要的作用.同一年,对偶理论理论的提出开阔了线性规划的研究领域,使得其应用范围更广,同时也更易于理解.到了50年代以后,随着相关理论研究的不断加深,许多线性规划算法的新的研究成果问世,这其中包括有: C.莱姆基给出的对偶单纯形法以及 S.加斯和T.萨迪等人的有关灵敏度分析和参数规划问题[3],还有A.塔克研究提出的互补松弛定理,以及G.B.丹齐克和P.沃尔夫两人给出的一种分解算法等.后来数学家L.G. Khachian 提出了椭球算法,并在其研究成果中证明了其为一种多项式时间算法.1984年数学家N.卡马卡在以往研究成果的基础上提出新的多项式时间算法,使得计算效率远远高于传统的单纯形法,大大提高了计算速度,为现有的线性规划多项式算法奠定了基础[4-9]. 最优解计算和判定问题是我们最为关心的问题,其中的关键是检验数.在求线性性规划中,检验数是证明和保证结果最优的依据,同时其对于对偶问题的计算有着至关重要的意义,根据检验数的定义及其理论意义,为对偶问题的求解提供了一种有效的思路和方法,从而实现对偶问题的直接或间接求解,使得求解更加简单容易.因此,本文中将对线性规划中的检验数及其在实际问题中的重要作用进行学习研究. 1.线性规划及其对偶问题 在人们的日常生产生活中,常见的线性规划问题主要分为两类:一类是资源有限,另外一类是目标确定.所谓的资源有限,指的是在生产活动中对生产涉及的现有劳动力、资金、设备等资源进行合理的有效安排,目标是使得资源效益最大化,这也是最为人熟知的一类经典问题;而对于目标确定的线性规划问题则是指生产的工作任务是一定的,在现有条件下该确定的任务是可以完成的,但完成任务的生产流程、方法、工艺等不定,此时线性规划的目标是设计有效合理的生产方案,组织生产,使得总的资源需求最少. 给定一个资源有限的生产任务,假设该生产任务中含有 个变量（即有 个生成目标商品）,分别用 表示,不同的商品的生产价值不同,商品 的价值用符号 表示.由于资源有限,生产受限制,限制条件有 个,用 表示对应每种资源的上限,对应每种商品xj的每种资源的消耗量为变量 .该生产任务的目标为使得Z值最大,于是,该线性规划用数学语言表述如下式所示: (1) 1.1线性规划 线性规划是一门指导人类科学有效地进行生产管理活动的学科,作为运筹学中的最为重要的分支之一,它自成立以来快速的发展成熟,并且已经广泛的应用到了相关领域中,相关的理论基础已经相对成熟.线性规划研究的主要内容为有约束限制的线性目标函数的最优解问题,目前在指挥军事作战,指导工程技术生产以及进行经济管理分析等方面有着十分广泛的应用.基于线性规划理论的决策问题,能够有效地对人力财力物力资源进行合理分配,达到资源效用的最大化,从而为最优决策的制定提供理论支撑. 1.2线性规划问题数学模型 对于线性规划问题,通常具有以下几点共性:(1)都存在一组决策变量;(2)都有一个关于决策变量的函数;(3)对应决策变量存在相应的约束条件. 假定线性规划问题中含n个变量,分别用 表示,在目标函数中, 的系数为 (通常称为价值系数). 的取值受m项资源的限制,用 表示第 种资源的拥有量,用 表示变量 的取值为一个单位时所消耗或含有的第i 种资源的数量,于是,通过数学模型对上述内容进行表述,如下列公式所示 (责任编辑：qin) |