《线性规划灵敏度分析共23页》由会员分享，可在线阅读，更多相关《线性规划灵敏度分析共23页（23页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上淮北师范大学 2011届学士学位论文 线性规划灵敏度分析 学 院、专 业 数学科学学院 数学与应用数学 研 究 方 向 运筹学 学 生 姓 名 陈 红 学 号 指导教师姓名 张发明 指导教师职称 副教授 2011年4月10日线性规划的灵敏度分析 陈 红（淮北师范大学数学科学学院，淮北，）摘 要本文主要从价值系数的变化，技术系数的变化，右端常数的变化以及增加新的约束条件和增加一个新变量的灵敏度这几个方面来进行研究；资源条件是线性规划灵敏度分析中的主要应用内容，而对于资源条件的一个重要应用是：“影子价格问题”的实际应用，最后简述了线性规划在经济及管理问题上的典型应用和从求
2、解例题的图解法揭示了最优解的一些重要特征。关键词 单纯形法，灵敏度分析，最优解，资源条件，价值系数Sensitivity Analysis of Linear ProgrammingChen Hong(School of Mathematical Science,Huaibei Normal University ,Huaibei,)AbstractThis thesis is mainly from the variety of the cost coefficient , the variety of technology coefficient , the variety of the
3、resources conditionand increase the new restraint and new variable to analytical linear programming of sensitivity analysis.This thesis is mainly based on the simplex method and dual simplex method of linear programming to system analytical the influence of the variety upon the optical solution of t
4、he coefficient of the simplex table.Linear programming of sensitivity analysis in physically of application is mainly about application of the variety of resources conditionin the economic management shadow price problem. Keywords simplex method, sensitivity analysis, optimum solution， resources con
5、dition，cost coefficient 目 录 引言 1 一、价值系数的变化分析 2 二、技术系数的变化分析 5 三、右端常数的变化分析 6 四、增加新约束条件的灵敏度分析 8 五、增加一个新变量的灵敏度分析 9 六、线性规划灵敏度分析的应用 9 七、线性规划在经济及管理问题上的典型应用14 八、从求解例题的图解法揭示了最优解的一些重要特征16 结论17 参考文献18 致谢19专心-专注-专业引言灵敏度分析是运筹学中一个比较重要的问题，在现实生活中，尤其是在经济管理与投资中有着广泛的应用.随着经济的发展，已有不少学者对其进行研究，本文基于已有的研究上进行归纳总结，并在对其研究理论的基础
6、上，对灵敏度分析的应用进行分析.在研究线性规划的灵敏度分析之前，先了解几个定义：定义 线性规划的标准形： （） 其中为行向量，均为列向量，为矩阵；，并假设的秩为，在问题（）中，约束方程（1.2）的系数矩阵的任意一个阶满秩子矩阵（）称为线性规划问题的一个基解或基.这就是说，基矩阵是由矩阵中个线形无关的列向量组成的，不失一般性，可假设并称为基向量，与基向量相对应的变量称为基变量不在中的列向量称为非基向量，与非基变量相对应的变量称为非基变量，并记，则系数矩阵可以写成分块形式，不失一般性 ， （1.4）将基变量和非基变量组成的向量分别记为，则向量X相应的写成分块形式 （1.5）再将（1.5）代入约束方
7、程组（1.2）中，得，由矩阵的乘法可得，又因为是非奇异方阵，所以存在，将上式两边乘以，移项后，得现在可以把看作一组自由变量（又称独立变量），给他们任意一组值，则相应的的一组值，于是 便是约束方程组（1.2）的一个解.特别令时，则，现把约束方程组的这种特殊形式的解 ，称为基本解.满足变量非负约束条件（1.3）的基本解称为基本可行解. 现在来研究线性规划的灵敏度分析.灵敏度分析的含义是指对系统或事物因为周围条件变化显示出来的敏感度.具体说来就是要研究初始单纯形表上的系数变化对最优解的影响，研究这些系数在什么范围内变化时原最优基仍然是最优的.若原最优基不是最优的，如何用简便的方法找到新的最优解.现考
8、虑标准形线性规划问题：（） 当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有没有变化.但这样做即麻烦又没有必要，因为单纯形法的迭代过程是从一组基向量变换为另一种基向量，每次迭代都和基变量的系数矩阵有关，表中每次迭代得到的数据只随基向量的不同选择而改变，因此可以把个别参数的变化直接在计算得到的最优解的单纯形表上反映出来.这样就不需要从头计算，而直接在最优性单纯形表进行审查，看一些数字变化后，是否仍满足最优性的条件，如果不满足的话再从这个表开始进行迭代计算，求得最优解.可按下表中的几种情况进行处理：原问题对偶问题结论或继续计算的步骤可行解可行解表中的解仍是最优解可行解非可
9、行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表求最优解下面就各个参数改变后的情况进行讨论：一、 价值系数的变化分析（一）非基变量的价值系数的变化若非基变量的价值系数的改变为，则变化后的检验数为，0要保持原最优基不变，即当变化为后，最终单纯形表中这个检验数小于或等于零，即，因此 ，这就确定里在保持最优解不变时非基变量的目标函数，的变化范围，当超出这个范围时，原最优解将不是最优解了.为了求新的最优解，必须在原最优单纯形表的基础上，继续进行迭代以求得新的最优解.例1 已知线性规划问题的最优单纯形表如下所示：（表1.1） 153
10、400001001/40-13/4011/4-1420020-2101-15100-3/4111/4003/411300-13/40-11/400-1/4-1（）为保持原最优解不变，分别求非基变量的系数的变化范围（）当变为5时，求新的最优解.解 （i）由图表可知：，于是由公式知，保持原最优解不变，则有 ，当，时，原最优解不变.（ii）当时，已经超出了的变化范围，最优解发生了变化，下面来求新的最优解.首先求出的检验数：故为换入基，用新的检验数代替原来的检验数，其余数据不变，得到新的单纯形表，并继续迭代得：序号 5534000b 01001/40-13/4011/4-1420020-2101-15
11、100-1/4111/400-3/41 3/40-11/400-1/4-107500-31/811/8-7/8510010-1201/2-1/251750123/80-3/85/8 00-2-3/80-5/8-5/8 表（1.2）由表中可看出已得到新的最优解及新的目标函数最优值 .（二）基变量的价值系数的变化若是基变量的价值系数，因为，当变为时，就引起的变化，则其中 是矩阵的第行.于是，变化后的检验数为 （j = 1，2，n）若要求最优解不变，则必须满足 （j = 1，2，n）由此可以导出 当时，有 ； 当时，有.因此，的允许范围是使用此公式时，首先要在最优表上查出基变量所在行中的元素，而且只取与非基变量所在列相对应的元素，将其中的正元素放在不等式的左边，负元素放在不等式右边，分别求出的上下界.例2 为保持现有最优解不变，分别求出例1 中基变量的变化范围.若当由（0，4，5）改变为（0，6，2）时，原最优解是否保持最优，如果不是，该怎么办？解 根据上述公式，利用表（1.1），为使最优基变量不变，的变化范围是即故当时，原最优解不变， 现在变为6，已超出了的允许变化范围.同样的，的允许范围是，即故当时，原最优解不变，现在变为2，也不在的允许变化范围内，当由（0，4，5）变为（0，6，2）即变
