线性规划灵敏度分析

淮北师范大学2011届学士学位论文线性规划灵敏度分析学院、专业数学科学学院数学与应用数学研究方向运筹学学生姓名陈红学号20071101008指导教师姓名张发明指导教师职称副教授2011年4月10日线性规划的灵敏度分析陈红（淮北师范大学数学科学学院，淮北，235000）摘要本文主要从价值系数jc的变化，技术系数ija的变化，右端常数ib的变化以及增加新的约束条件和增加一个新变量的灵敏度这几个方面来进行研究；资源条件是线性规划灵敏度分析中的主要应用内容，而对于资源条件b的一个重要应用是：“影子价格问题”的实际应用，最后简述了线性规划在经济及管理问题上的典型应用和从求解例题的图解法揭示了最优解的一些重要特征。关键词单纯形法，灵敏度分析，最优解，资源条件，价值系数SensitivityAnalysisofLinearProgrammingChenHong(SchoolofMathematicalScience,HuaibeiNormalUniversity,Huaibei,235000)AbstractThisthesisismainlyfromthevarietyofthecostcoefficient‘jc’,thevarietyoftechnologycoefficient‘ija’,thevarietyoftheresourcescondition‘ib’andincreasethenewrestraintandnewvariabletoanalyticallinearprogrammingofsensitivityanalysis.Thisthesisismainlybasedonthesimplexmethodanddualsimplexmethodoflinearprogrammingtosystemanalyticaltheinfluenceofthevarietyupontheopticalsolutionofthecoefficientofthesimplextable.Linearprogrammingofsensitivityanalysisinphysicallyofapplicationismainlyaboutapplicationofthevarietyofresourcescondition‘ib’intheeconomicmanagement‘shadowpriceproblem’.Keywordssimplexmethod,sensitivityanalysis,optimumsolution，resourcescondition，costcoefficient目录引言………………………………………………………………………………………1一、价值系数的变化分析………………………………………………………………2二、技术系数的变化分析………………………………………………………………5三、右端常数的变化分析………………………………………………………………6四、增加新约束条件的灵敏度分析……………………………………………………8五、增加一个新变量的灵敏度分析……………………………………………………9六、线性规划灵敏度分析的应用………………………………………………………9七、线性规划在经济及管理问题上的典型应用………………………………………14八、从求解例题的图解法揭示了最优解的一些重要特征……………………………16结论………………………………………………………………………………………17参考文献…………………………………………………………………………………18致谢………………………………………………………………………………………191引言灵敏度分析是运筹学中一个比较重要的问题，在现实生活中，尤其是在经济管理与投资中有着广泛的应用.随着经济的发展，已有不少学者对其进行研究，本文基于已有的研究上进行归纳总结，并在对其研究理论的基础上，对灵敏度分析的应用进行分析.在研究线性规划的灵敏度分析之前，先了解几个定义：定义线性规划的标准形：（LP）max..0ZCXAXbstX(1.1)(1.2)(1.3)其中12,,,nCccc为行向量，12,,,TnXxxx，12,,,Tmbbbb均为列向量，ijmnAa为mn矩阵；0b，并假设A的秩为m，在问题（LP）中，约束方程（1.2）的系数矩阵A的任意一个mm阶满秩子矩阵B（0B）称为线性规划问题的一个基解或基.这就是说，基矩阵B是由矩阵A中m个线形无关的列向量组成的，不失一般性，可假设111121,,,mmmmmaaBpppaa并称1,2,ipim为基向量，与基向量相对应的变量1,2,iXim称为基变量不在B中的列向量1,2,jpjmmn称为非基向量，与非基变量相对应的变量1,2jXjmmn称为非基变量，并记1,11,12,1,,,mmmmnmmmnaaNpppaa，则系数矩阵A可以写成分块形式，不失一般性(,)ABN，（1.4）将基变量和非基变量组成的向量分别记为12,,,TBmXxxx，12,,,TNmmnXxxx，则向量X相应的写成分块形式BNXXX（1.5）再将（1.5）代入约束方程组（1.2）中，得,BNXBNbX，由矩阵的乘法可得BNBXNXb，又因为B是非奇异方阵，所以1B存在，将上式两边乘以1B，移项后，得211BNXBbBNX现在可以把NX看作一组自由变量（又称独立变量），给他们任意一组值NX，则相应的BX的一组值BX，于是BNXXX便是约束方程组（1.2）的一个解.特别令0NX时，则1NXBb，现把约束方程组的这种特殊形式的解10BbX，称为基本解.满足变量非负约束条件（1.3）的基本解称为基本可行解.现在来研究线性规划的灵敏度分析.灵敏度分析的含义是指对系统或事物因为周围条件变化显示出来的敏感度.具体说来就是要研究初始单纯形表上的系数变化对最优解的影响，研究这些系数在什么范围内变化时原最优基仍然是最优的.若原最优基不是最优的，如何用简便的方法找到新的最优解.现考虑标准形线性规划问题：（LP）max..0ZCXAXbstX当线性规划问题中的一个或几个参数变化时，可以用单纯形法从头计算，看最优解有没有变化.但这样做即麻烦又没有必要，因为单纯形法的迭代过程是从一组基向量变换为另一种基向量，每次迭代都和基变量的系数矩阵B有关，表中每次迭代得到的数据只随基向量的不同选择而改变，因此可以把个别参数的变化直接在计算得到的最优解的单纯形表上反映出来.这样就不需要从头计算，而直接在最优性单纯形表进行审查，看一些数字变化后，是否仍满足最优性的条件，如果不满足的话再从这个表开始进行迭代计算，求得最优解.可按下表中的几种情况进行处理：原问题对偶问题结论或继续计算的步骤可行解可行解表中的解仍是最优解可行解非可行解用单纯形法继续迭代求最优解非可行解可行解用对偶单纯形法继续迭代求最优解非可行解非可行解引进人工变量，编制新的单纯形表求最优解下面就各个参数改变后的情况进行讨论：一、价值系数jc的变化分析3（一）非基变量jx的价值系数jc的变化若非基变量jx的价值系数jc的改变为jjjccc，则变化后的检验数为1jjjBjccCBp，0要保持原最优基不变，即当jc变化为jc后，最终单纯形表中这个检验数小于或等于零，即10jjjBjccCBp，因此jjc，这就确定里在保持最优解不变时非基变量jx的目标函数jc，的变化范围，当超出这个范围时，原最优解将不是最优解了.为了求新的最优解，必须在原最优单纯形表的基础上，继续进行迭代以求得新的最优解.例1已知线性规划问题1234max534Zxxxx12341234123423280054341200..3453100001,2,3,4jxxxxxxxxstxxxxxj的最优单纯形表如下所示：（表1.1）jc1534000BcBxb1x2x3x4x5x6x7x05x1001/40-13/4011/4-144x20020-2101-152x100-3/4111/4003/41jjZcz1300-13/40-11/400-1/4-1（Ⅰ）为保持原最优解不变，分别求非基变量13,xx的系数13,cc的变化范围（Ⅱ）当1c变为5时，求新的最优解.解（i）由图表可知：113/4，311/4，于是由公式jjc知，保持原最优解不变，则有1313/4,11/4cc，当111113/417/4ccc，333311/423/4ccc时，原最优解不变.（ii）当1517/4c时，已经超出了1c的变化范围，最优解发生了变化，下面来求新的最优解.首先求出的检验数：11111/450,4,523/403/4BcCBp故1x为换入基，用新的检验数13/4代替原来的检验数113/4，其余数据不变，得到新的单纯形表，并继续迭代得：4序号jc5534000BcBXb1x2x3x4x5x6x7xⅠ05x1001/40-13/4011/4-144x20020-2101-152x100-1/4111/400-3/41jjZcz13003/40-11/400-1/4-1Ⅱ05x7500-31/811/8-7/851x10010-1201/2-1/252x1750123/80-3/85/8jjZcz137500-2-3/80-5/8-5/8表（1.2）由表中可看出已得到新的最优解*100,175,0,0,75Tx及新的目标函数最优值*1375Z.（二）基变量jx的价值系数jc的变化若rc是基变量rx的价值系数，因为rBcC，当rc变为rrcc时，就引起BC的变化，则1111120,,,0,,,BBBrBrrrrnCCBACBAcBACBAcaaa其中12,,,rrrnaaa是矩阵1BA的第r行.于是，变化后的检验数为1jjBjrrjjrrjcCBpcaca（j=1，2，，n）若要求最优解不变，则必须满足0jjrrjca（j=1，2，，n）由此可以导出当0rja时，有/rjrjca；当0rja时，有/rjrjca.因此，rc的允许范围是max/|0min/|0jrjrjrjrjrjjjaacaa使用此公式时，首先要在最优表上查出基变量rx所在行中的元素1,2,,rjajn，而且只取与非基变量所在列相对应的元素，将其中的正元素放在不等式的左边，负元素放在不等式右边，分别求出rc的上下界.例2为保持现有最优解不变，分别求出例1中基变量24,xx的变化范围.若当BC由（0，4，5）改变为（0，6，2）时，原最优解是否保持最优，如果不是，该怎么办？5解根据上述公式，利用表（1.1），为使最优基变量245,,xxx不变，4c的变化范围是413/41/413/41/4max,min,213/43/4c即4114c故当41554c时，原最优解不变，现在4c变为6，已超出了4c的允许变化范围.同样的，2c的允许范围是211/4113/41/4max,min,11/413/43/4c，即2113c故当21643c时，原最优解不变，现在2c变为2，也不在2c的允许变化范围内，当Bc由（0，4，5）变为（0，6，2）即4c变