目录
第一章 引言 ................................................................. 1
第二章 主要结论.............................................................. 2
2.1 基本概念和记号 ....................................................... 2
2.2 基本定理和结论 ....................................................... 5
第三章 单一变化的灵敏度分析 .................................................. 7
3.1 jc的灵敏度分析 ...................................................... 7
3.1.1 rx为非基变量 .................................................. 7
3.1.2 jx为基变量 .................................................... 7
3.2 对ib的灵敏度分析 .................................................... 8
3.3 对ija的灵敏度分析 .................................................... 9
3.3.1 ija为基变量 .................................................... 9
3.3.2 ija为非基变量 .................................................. 9
3.4 增加约束条件灵敏度分析 .............................................. 10
第四章 全方位变化的灵敏度分析 ............................................... 11
4.1非基变量目标函数系数、约束系数向量以及约束右端项向量同时变化的灵敏度分析 ..................................................................... 12
4.2基变量目标函数系数、约束系数向量以及约束右端项向量同时变化的灵敏度分析 ....................................................................... 13
第五章 算例 ................................................................ 15
5.1 单一变量的灵敏度分析算例 ............................................ 15
5.1.1 问题1的求解： ................................................ 15
5.1.2 问题2的求解： ................................................ 17
5.1.3 问题3的求解： ................................................ 18
5.1.4 问题4的求解 .................................................. 19
5.1.5 问题5的求解： ................................................ 20
第六章 结论 ................................................................ 24
参考文献 ................................................................... 25
致 谢 ..................................................................... 26
1 第一章 引言
灵敏度分析是研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法.在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性.通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响.因此,灵敏度分析几乎在所有的运筹学方法中以及在对各种方案进行评价时都是很重要的.
由于线性规划中所使用的数据大多是估计值和预测值.在实际中尤其是经济问题中常会遇到因市场条件或生产条件改变导致的产品价格、生产工艺或技术条件以及资源限制条件等改变.而灵敏度分析是分析模型的参数变化对求解结果的影响,它是在原最优表的基础上对变化后的规划问题进行分析求解,避免因参数改变而去从头求解,故又称最优化后分析.
本文主要介绍线性规划问题中的灵敏度分析问题,以及在灵敏度分析的基础上,对变量目标函数系数,变量约束系数向量以及约束右端项向量发生变化时,进行分析讨论.由于以往人们对灵敏度分析的讨论仅限于单个参数、单一系数或单一限制条件的变化对结果的影响,而实际中多是规划问题中各参数同时变化,如前所述因市场条件变化导致产品价格、生产工艺以及资源限制条件同时发生改变等,本文又讨论了参数同时变化的情况.
文章大体分为三个部分：第一部分总结概述了基本概念、主要理论和灵敏度分析的算法基础；第二部分讨论分析变量目标函数系数、变量约束系数向量、约束右端项向量这些单一参数发生变化时,最优解的求的方法；第三部分讨论各种参数同时发生变化时求解最优解的方法.第四部分是在上述理论基础上以投入产出问题进一步说明.
2 第二章 主要结论
2.1 基本概念和记号
线性规划问题
求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题.
线性规划问题的标准型为：
11221111221121122222121122max..(,,...,0)0(1,2,....,)nnnnnnmmmmnnmjzcxcxcxaxaxaxbaxaxaxbstbbbaxaxaxbxjn （2.1.1）
这里,max表示求最大值,s.t.表示受约束于,X是目标函数, jx是决策变量.通常假定ija,ib和jc都是已知常数.
为讨论方便,将线性规划问题的标准型以矩阵形式给出:
max..0zcxAXbstX （2.1.2）
基
若系数矩阵A的秩为m,称A的任一mn非奇异子矩阵12,,...,jjjmBPPP为线性规划问题（LP）的一个基.
基变量、非基变量
当确定12,,...,jjjmBPPP为（LP）的一个基,12,,...,jjjmPPP称为基向量,A中的其余向量称为非基向量；与基向量对应的变量12,,...,jjjmxxx称为基向量,其余的变量称为非基变量. 3 解
若B是（LP）的一个基,令所有非基变量等于0得到的解10BNXBbXX称为对应于基B的基本解；若满足10Bb,这时100BbX称为对应于基B的一个基可行解；称B为（LP）的一个可行基.使目标函数达到最大值的基可行解称为基最优解.
单纯形变换
对于线性规划问题
max..0zcxAXbstX
将矩阵A,C,X分别按“基”和“非基”分成2块,即有ABN,BNCCC,BNXXX,其中：12,,...,mBPPP；12,,...,mmnNPPP；12,,...,BmCccc；12,,...,NmmnCccc；12,,...,TBmXxxc；12,,...,TNmmnXxxc.
由此可建立单纯形初表：
表1 单纯形初表
基 非基变量 基变量 解
BX NX SX
SX B N SE b
BC NC 0
用单纯形法对上初表做单纯形变换,变换后得到单纯形终表：
表2 单纯形终表
基 基变量 非基变量 解 4 BX NX SX
BX SE 1BN 1B 1Bb
λ 0 1NBCCBN
1BCB
11110SBNNBBBNbEBNBbCCZCCBNCBb
1NNBCCBN为非基变量的检验数向量,最优基本可行解10BNXBbXX,对应的基可行基为B,SE为一单位矩阵.最优结果为1BZCBb.
对偶问题
对偶问题与原问题的关系：
表3 对偶问题与原问题的关系
原问题（或对偶问题） 对偶问题（或原问题）
目标函数maxz
变量00n 目标函数min
n约束条件
约束条件m
约束条件右端项
目标函数变量的系数 00m变量
目标函数变量的系数
约束条件右端项
对偶单纯形法的计算步骤
（1）将问题化为标准型,列出初始单纯形表；
（2）若存在初始对偶可行的基本解,则进行迭代； 5 （3）检验常数列b中的分量,若检验数全部非正而常数列b中的分量都为非负,则问题已得到最优解,终止迭代；否则,若检验数全部非正而常数列b中的分量至少还有一个负分量,则进行下一步；
（4）确定换出变量,即按
111min{()|()0}()iilBbBbBb
对应的基变量lx为换出变量；
（5）确定换入变量：检查lx的所在行的各系数(1,2,...,)ijajn.若所有0ija,则无可行解,停止迭代；若存在0ija,按法则,即
min|0jkijijlkaaa
所对应的列的非基变量kx为换入变量.
（6）实施枢轴运算,即以lka为主元素按原单纯形法在表中进行迭代运算,得新的单纯形表：转入（3）继续迭代.
2.2 基本定理和结论
定理[1]2.2.1
对于线性规划问题（LP）的基B,若满足10Bb,则称基B为可行基；若满足10Bb且10NBCCBN,则对应的基B最优基,对应的基可行解1,0BNXBbX为最优解,1maxBZCBb.
定理[1]2.2.2
对于可行基B所对应的单纯形表中,若某个00jjb,且非基变量jx所对应