基于线性规划的灵敏度分析问题的研究

基于线性规划的灵敏度分析问题的研究摘要：本文主要研究的是线性规划的灵敏度分析问题。讨论线性规划价值系数和资源系数中单个系数在什么区间变化时能保证最优解或最优基不变，以及多系数同时变化时最优解或者最优基不变的判定定理。最后通过实例进行说明验证。本文对线性规划的灵敏度分析问题进行研究，主要内容如下：第一章主要是简单的介绍了线性规划的发展历程，在线性规划的灵敏度分析的含义，灵敏度分析在其他方面的应用。第二章，技术系数矩阵A发生变化时，最优解的变化。举例验证，应用LINGO软件，进行灵敏度分析，确定在什么范围内，最优解不变。第三章，资源向量b发生变化时，讨论最优解的变化情况。并举例验证其理论知识，应用LINGO软件，确定在什么变化范围内，最优解不变。第四章，价值系数C发生变化时，最优解的变化情况。举例验证其理论实施过程，应用LINGO软件，分析其灵敏度。第五章，对本文研究内容进行总结，指出一些不足之处，并提出进一步研究的方向。关键词：运筹学；线性规划；灵敏度分析；技术系数；资源向量；价值系数；LINGOTheinventorymodelunderuncertaindemandAbstract:第一章绪论随着运筹学的发展，线性规划方面的知识也得到了逐步的完善，并广泛地运用到实际的生活中，尤其给经济管理和决策提供了强有力的理论根据．管理部门和企业在进行生产或投资决策时，一般通过建立数学模型和对模型的求解，做出具体的决策方案．在建立模型和求解的过程中，都是以价值系数jc、资源系数jb和消耗系数ija为基础的，这些数据不但难以确定，而且市场价格的变动、资源供应的波动、工人技术的提高、设备的改进等，都会使这些数据变动．本文讨论线性规划价值系数和资源系数中单个系数在什么区间变化时能保证最优解或最优基不变，以及多系数同时变化时最优解或者最优基不变的判定定理。线性规划发展史1）1939年，前苏联数学家康托洛维奇发表了《生产组织与计划中的数学方法》学术报告，首次提出了线性规划问题，但是他没有找到一个统一的求解这类问题的方法。2）美国学者希奇柯克（Hitchcock，1941）独立的提出了运输问题这样一类特殊的线性规划问题。3）1947年，美国学者丹捷格（Dantzig）提出求解线性规划的单纯形法和许多相关的理论，为线性规划奠定了理论基础，推动了线性规划的发展。灵敏度分析的概念研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。因此，灵敏度分析几乎在所有的运筹学方法中以及在对各种方案进行评价时都是很重要的。灵敏度分析的应用领域线性规划中灵敏度分析对于线性规划问题：1maxnjjjXcx公式1.1,2,01,2,nijjijjstaxbimxjn这里max表示求极大值，..st表示受约束于，X是目标函数,jx是决策变量。通常假定ija，ib和jc都是已知常数。但是实际上这些参数往往是一些根据估计或预测得到的数据，因而存在误差。同时，在实际过程中，这些参数还会发生不同程度的变化。例如，在处理产品搭配的线性规划问题中，目标函数中的jc一般同市场条件等因素有关。当市场条件等因素发生变化时，jc也会随之而变化。约束条件中的ija随工艺条件等因素的变化而改变，ib的值则同企业的能力等因素有关。线性规划中灵敏度分析所要解决的问题是：当这些数据中的一个或几个发生变化时，最优解将会发生怎样的变化。或者说，当这些数据在一个多大的范围内变化时最优解将不发生变化。投入产出法中灵敏度分析可以用来研究采取某一项重大经济政策后将会对国民经济的各个部门产生怎样的影响。例如，美国政府曾经利用投入产出表研究了提高职工工资10％对国民经济各部门商品价格的影响。研究的结果表明，在职工工资增加10％时，建筑业产品的价格将上涨7％，农产品的价格将上涨1.3％，其余各部门产品价格将上涨1.3～7％不等,生活费用将上升3.8％，职工的实际得益为6.2％。方案评价中灵敏度分析可以用来确定评价条件发生变化时备选方案的价值是否会发生变化或变化多少。例如，在利用评价表进行评价时，需要确定每一个分目标的权重系数和各分目标的评分数。这中间或多或少地会存在当事人的主观意识，不同的人可能会有截然不同的价值观念。因此就必须考虑当分配的权重系数或评分数在某一个范围内变化时，评价的结果将会产生怎样的变化。定货批量的灵敏度分析在分析整批间隔进货模型中，经济订货批量Q可用下式计算：iiiIWV。式中D为单位时间需求量，K为每次订货的固定费用，h为单位时间内每单位物资的保管费。它们一般都是根据统计资料估算的，与实际情况有所出入，需要进行灵敏度分析。用D1，K1，h1和Q壒分别表示实际的需求量、订货量、保管费和调整后的经济订货批量。ΔD，ΔK,Δh和ΔQ分别代表需求量、订货量、保管费和经济订货批量的相对变化值，即：1niiiIWV1/niiinIWV1hhhh***1*QQQQ通过计算后可得：*(1)(1)1DKQh代入具体的数值后便可用上式说明ΔD、ΔK和Δh对订货批量的综合影响程度。第二章技术系数的变化改进目标函数值的原理模型符号意义：12,,,TnXXXX为决策向量；12,,,nCCCC为价值向量；12,,,Tnbbbb为资源向量；*ijmnAa为系数矩阵;；Z为目标函数值(不妨设为总利润)。设B为原最优基，BX为基变量向量，*Z为最优值，为检验数向量,则有：1*11,,BBCXBbZCBbCCBA假设线性规划问题为max..(1)0ZCXAXbstX相应的最优单纯形表如表1所示．表1线性规划问题（1）BCBXb1x2xnx1BC2BCBmC1BX2BXBmX1Bb1112(,,,)nBABpppZ1BCBb1BCCBA第三章资源向量b的变化改进目标函数值的原理定理1当资源向量由bbb变化为时(0,,,,0Trbb)，那么必存在区间rI，当rrbI时，规划问题（1）的最优基不变（或者影子价格不变）。证明：当bbb变化为时，要保持最优基不变，则必有10BXBbb。由于1110,,,,0TrBbbBbBb，令112210,,,,0rrrTrrrrrmrmrrabaabaBbbaab，则有0,iiririrrbababb其中1,2,,im。而当0ira时，irirbba；当0ira时，irirbba，于是max|0min|0iirirriirirrbaabbaaI。所以这样的区间同样存在。定理2是当资源向量中的单元素在一定的区间上变化时，最优基不变的判定定理．下面给出当资源向量多元素同时变化的判定方法，作为定理2的推论。推论1资源向量b中的多元素同时变化时，若这些变化量占可行增加或者是可行减少的百分率之和没有超过100％，则最优基（或者影子价格）不变。第四章资源向量b的变化改进目标函数值的原理定理2【1】当价值向量由C转化到CC(其中0,0,,,,0iCc)，那么必存在区间iI，当iicI时，规划问题（1）的最优解不变．其中1,2,,im。证明：当C变化到CC时，，要使最优解保持不变，则必然有10BBCCCCBA成立。当ic是非基变量ix的系数时，有10iiiBiccCBp，所以有1iBiicCBpc，故只要ic在区间1,iBiiICBpc变化时，问题的最优解不变。当rc是基变量rx的系数时，1111120,,,,0,,,BBBrrrrnBrCCBACBAcBACBAcaaa，所以1rjjjBrcCBAca，其中1,2,,jn。要使0j，需使1rjrjjBrjrcCBAcaca。而0rja时，rjrjca；0rja时，rjrjca，所以max|0min|0rjrjjrrjrjjraacaaI。因此，存在这样的区间iI，当iicI时，规划问题（1）的最优解不变。不妨假设(,)iiiIMN，可知,0iiMN。定义1iI的右端点Ni称为ic的可行增加，即当ic的最大增量不超过iN时，规划（1）的最优解不变．定义2iI的左端点的绝对值iM称为的ic可行减少，既当ic的最大减少量不超过iM时，规划（1）的最优解不变．定理1是当价值向量中的单元素在一定的区间上变化时最优解不变的判定定理．有了可行增加和可行减少的定义以后，现在给出当价值向量多元素同时变化的判定方法，作为定理1的推论。推论2【2】价值向量中的多元素同时变化时，若其变化量占可行增加或者可行减少的百分率之和没有超过100％，则最优解不变。第五章总结灵敏度分析是用来考察微观变化对建立模型的整体影响的，你也知道，数学建模没有明确的答案，不同的人因为假设条件的不同，建立出来的模型一般是不同的。因此，假设条件成为了建模过程中一个影响模型好坏的影响因素，灵敏度分析就是在模型建立后，对假设条件变化，检验模型的优劣性。参考文献：[1]沈荣芳．运筹学[M]．北京：机械工业出版社，2004．53~67．[2]AndersonDR，SweeneyDJ，WilliamsTA．数据、模型与决策[M]．于淼译．北京：机械工业出版社，2003．1~48．[3]庞留勇,黄伟亮.线性规划多变量系数变化的灵敏度分析.天中学刊.2005,20(5).致谢本研究及学位论文是在我的导师孙士国老师的亲切关怀和悉心指导下完成的。他严肃的科学态度，严谨的治学精神，精益求精的工作作风，深深的感染和激励着我。孙老师不仅治学严谨而且为人师表，教给我们的不仅是书本上的知识，还有为人处世的积极态度，这些宝贵知识将积极影响我今后的学习和工作，在此谨向孙老师致以诚挚的谢意和崇高的敬意。我还要感谢在一起愉快的度过毕业论文的同学们，正是因为有了你们的帮助，才让我不仅学到了本次课题所涉及的新知识，更让我得到了知识以外的东西，就是团结和友谊。虽然毕业在即,我们各自心中通过这次实习更加的增进了友谊,心中更加多了一份不舍,使我们更加珍惜这段晚来的友谊。在老师和同学们的帮助下，我的专业知识得到了进一步的提高，在整个设计过程中我也体会到了坚持的重要性，对待任何困难都要有坚持不懈的心理和斗志，才能在学习的过程中取得更多的知识和经验。知识是人类进步的阶梯，而传授知识的各位老师则是我们登上阶梯的领路人。没有各位老师的辛勤教育，便不会有我们今天的累累果实。在这里，我要感谢那些曾经孜孜不倦传授我们知识的各位恩师，衷心祝愿你们桃李满天下。最后还要感谢我的母校---华北科技学院四年来对我的培养。她使我从一个不谙世事的丫头变成一个有理想，有抱负的青年，她教给我的不仅是进入社会后生存的本领，更重要的是艰苦朴实，求实进取的精神力量，遇到困难不懈不馁，多一份坚持少一份浮躁，这将鼓舞我在人生的道路上不断前进。我还要感谢含辛茹苦培养我的父母，谢谢你们！