第2章对偶理论与灵敏度分析。
2.1 线性规划的对偶问题的提法。
原问题的矩阵-向量形式为。
这个对偶问题写成矩阵形式为：
或者。例1-1的线性规划问题：
称为原问题。
原问题的矩阵-向量形式为。
其中。对偶问题的矩阵-向量形式为。
其中。或者。
其中。2.2 线性规划的对偶问题的性质。
性质1：原问题与对偶问题互为对偶关系。
性质2：弱对偶性如果是原线性规划问题的可行解，是它的对偶问题的可行解，则。
性质3：最优性准则如果是原线性规划问题的可行解，是它的对偶问题的可行解，并且，则是原线性规划问题的最优解，是它的对偶问题的最优解。
由这两个性质可以得出结论：如果原问题和对偶问题都存在最优解，则对偶问题的解是原问题的影子**，原问题的解是对偶问题的影子**。两个问题的目标函数的最优值相等。
性质4 互补松弛性**性规划问题的最优解中，如果对应某个约束条件的对偶变量为0，则该约束条件取严格等式；反之如果约束条件取严格不等式则其对应的对偶变量一定为0。.
即如果，则；如果，则。
性质5 最优互补解特性单纯形法完成时原问题得到一个最优解，同时得到对偶问题的一个最优互补解，满足。
根据以上讨论知，可以通过解对偶问题得到影子**。
最终单纯形表中原变量系数大于等于0，即，记则化为，化为。因此最优单纯形表中z行松弛变量的系数对应对偶问题的解，既是资源约束的影子**。
2.3对偶问题的经济解释—影子**。
线性规划的对偶问题的解的经济意义是影子**，
对于对偶问题的经济解释依赖于原问题的经济含义，假设原问题生产计划问题，则如我们在例子中所说的对偶问题的解的经济意义是单位第种资源对最大利润的贡献，或称为对第种资源的估价这种估价不是市场的**，而是单位资源对于生产中获得最大利润的贡献，称为影子**。影子**又边际**。
资源的影子**不同于它的市场**，资源的影子**是它对最优利润的贡献，当影子**高于市场**时可以考虑买进这种资源，反之，当影子**低于市场**时可以考虑出让这种资源。
有的公司借助影子**，确定一些资源的内部结算**，以控制有限资源的使用和考核下属部门的工作。社会上，可以根据影子**规定使用某些最紧缺的资源时必需上交的利润额。
2.4 灵敏度分析。
**性规划问题中假设是已知常数，事实上，这些值是随着环境的变化而变化的。因此需要分析这些常数的变化对于最优解的影响。即分析这些参数中的一个或几个发生变化时对最优解产生的影响，分析这些参数在多大范围内变化时问题的最优解不变。
这些就是灵敏度分析要研究的问题。最优解对参数的灵敏度是不同的，有的参数的变化对于最优解没有影响，有的参数的变化将会产生新的最优解，而原来的解可能变得很差。因此灵敏度分析的一个重要目的就是识别敏感参数。
对于不太敏感的参数分析他们在什么范围内变化不影响最优解。这两方面的研究都很重要，对于敏感参数，在确定它的值时应该特别慎重，对于其它参数应注意它们的变化范围，当它们的变化超出范围时应该改变方案。
由于已经有解线性规划问题的非常好用的软件，对于一般规模的线性规划问题，当这些参数变化时可以方便地从新计算最优解，这样既方便又快捷。对于大规模的线性规划问题每一次参数变化都从头计算最优解，会花费过多的计算时间。因此需要更直接的对灵敏度进行分析的方法。
主要是分析参数的变化如何反应在最终的单纯形表上。
设改变后的向量和矩阵为，即向量换为，基矩阵化为，向量换为，灵敏度分析的第一步是修订最1终单纯形表来反应这些变化。
由第1章，单纯形法的矩阵形式得到的表。
这个矩阵方程对应于以下单纯形表。
令--第1行至第行中松弛变量的系数矩阵，-第1行至第行中原变量的系数矩阵，-z行中松弛变量的系数向量，-=是z行中原变量的系数向量，-目标函数的最优值，-第1行至第行的右端向量。
于是以上单纯形表化为。
单纯形表的变形。
当向量换为，基矩阵化为，向量换为时单纯形表化为。
参数变化后的单纯形表。
下面应用这个表做当某个参数变化时对最优解的影响。先从最简单的情况开始。
1. 改变的情况：当约束条件的右端发生变化时目标函数值会产生什么样的变化？
影子**分析已经提供了这方面的信息，右端项在一定范围内变化时，目标函数值的变动等于右端项变动的值乘以影子**。下面依据上表做进一步的分析。
当改变时，最终的单纯形表唯一的改变是右端列向量和。因此解的最优性没有受到影响，改变后唯一的问题是基变量的值是否仍然是非负的，如果有一个基变量不再是非负的，那么就破坏了解的可行性。线性规划问题是求使目标函数最大的可行解，可行性破坏了，就不是线性规划问题的解了。
例如在例1-4中。
化为标准型。
用单纯形法求解。
用单纯形法求解。
z行没有负系数，得到了最优解：
目标函数的最大值为：。
在z行与松弛变量对应的位置给出了资源的影子**。例如第2种资源的影子**是1.5，因此当第2种资源由12增加到13是目标函数的最大值将增加1.
5，为36+1.5=37.5。
当第2种资源由12增加到15是目标函数的最大值将增加，为36+4.5=40.5。
这样推论下去是不是正确呢？
现在换为，即。
由表中，于是。
已经不能直接得到最优解。
下面分析在什么范围内变化时原最优解不变。设。则。即。
由此得到。在这个范围内变化时，最优性和可行性都保持不变影子**也保持不变，目标函数的增量可以有影子**乘增量来计算。
b改变以后： =15
根据以上分析如果，则最优性不变。这时。
目标函数的最优值的增量恰好等于3x第2种资源的影子**=2x1.5=4.5,36+4.5=40.5.
也验证了z行对应松弛变量的位置给出了影子**。在范围内最优性没有变，影子**也没有变。在这个范围内最优值的增量等于的增量乘第2种资源的影子**。
第2章复习题。
1.简述线性规划的原问题和对偶问题的最优解、影子**和最优值之间的关系。
2.简述线性规划问题中影子**的经济含义。影子**为0和影子**为正各说明什么问题？
3.在资源约束下的利润最大化的问题中如何求资源的影子**？影子**在实际中如何应用？
运筹学 2 复习重点
2013年运筹学 2 期末复习重点。提醒 同学们要真正理解并掌握以下内容，不要死记硬背！第一部分对策论。1.对策行为的三个基本要素 局中人 策略集和赢得函数 支付函数 掌握局中人 策略集 局势和赢得函数 支付函数 的含义 对实际问题能根据某一局中人 策略集及赢得矩阵建模求解。2.对策的分类。3.矩阵...
运筹学 2 复习重点
运筹学 2 复习重点。2021年。运筹学 2 期末复习重点。提醒 同学们要真正理解并掌握以下内容，不要死记硬背！第一部分。对策论。1.对策行为的三个基本要素 局中人 策略集和赢得函数 支付函数 掌握局中人 策略集 局势和赢得函数 支付函数 的含义 对实际问题能根据某一局中人 策略集及赢得矩阵建模求解...
2《运筹学》复习题
一 填空1 10 二 判断题1 10 三 简答题6 4 简述单纯形法的基本思路。简述运筹学中背包问题的一般提法。简述著名的哥尼斯堡七桥难题及答案。建立动态规划模型时，应定义状态变量，请说明状态变量的特点。运输问题是特殊的线性规划问题，但为什么不用单纯形法求解。简述目标规划的目标函数主要类型及其数学表...