第二章对偶理论与灵敏度分析。
duality theory and sensitivity analysis)
第一节单纯形法的矩阵描述。
用矩阵描述单纯形法求解过程比较简便，也有助于加深对单纯形法的理解。
设有线性规划问题，用矩阵形式表示，在约束条件中加入松弛变量，将其化成标准型：
式中i为m×m的单位阵。
运用单纯形法求解，需将标准型中系数矩阵、变量和目标函数中的系数向量改写成分块形式：
系数矩阵(a，i)改写为(b，n)两块，b为基矩阵；
变量改写为，为对应于基矩阵b的基变量；
目标函数中系数向量(c，0)改写为(，)为对应于基变量的系数向量；
目标函数： z =
约束条件：所以，改写后的线性规划问题为，下面按照单纯形法求解原理，对改写后的线性规划模型进行分析：
从(2)式中，可得出用非基变量表示基变量的表达式：
在(3)式中，令，可得到一个基解。
再将(3)式代入(1)式，可得出用非基变量表示目标函数的表达式：
令，可得目标函数值，
再对(3)和(4)进行分析，又可得出：
在(4)式中，非基变量系数，即为非基变量的检验数，基变量的检验数为0；
这个非基变量检验数＝与前一章提到的非基变量。
在这个检验数＝中，由于中对应于的系数为0，所以，的检验数为。
另外，由于基变量的检验数为，所以，所有变量的检验数都可用和表示。
从(3)式，确定换出变量的θ规则，用矩阵可表示为，这里的θ规则与前面介绍的θ规则含义完全相同，在上一章介绍的θ规则为，在上式中，是向量的第i个分量，即；是的第i个分量，即。
用矩阵描述的单纯形表。
为用矩阵描述的单纯形表，需要将上面(1)和(2)再进行改写，将非基变量再分成两块，即。
将(4)式移项后，得，将(5)式代入(6)式，得，将(5)式和(7)式合并，用矩阵表示即为，用单纯形表表示即为，这是迭代后的单纯形表，从表中可以看出，各部分数字都与基矩阵b的逆矩阵b-1有关， 而逆矩阵b-1对应于松弛变量的位置。
第二节改进单纯形法。
从上一章介绍的**单纯形法可以看出，用该法求解线性规划问题时，每迭代一次都要把整个单纯形表计算一遍，实际上，从上一张单纯形表变换到下一张时，即迭代一次有许多计算是不必要的，所需重新计算的数据仅仅是检验数、主元列元素、当前的基变量及b列数据等，一些与基变换运算暂时无关的列向量没有必要计算。
因此，按此法用计算机求解线性规划问题，特别是大型线性规划问题时，计算效率非常低。为了提高计算效率，人们对**单纯形法进行了改进提出了适合于计算机计算的改进单纯形法。
改进单纯形法有两个特点：① 在迭代过程中，有许多数据计算都依赖于基矩阵b的逆矩阵b-1。所以，在迭代过程中，只要求出基矩阵的b的逆矩阵b-1，检验数、基可行解中的基变量、目标函数值及θ值等数据都可以从线性规划问题的初始数据直接求出。
② 在进行了基变换后，如何用最少的计算量来求出新的基矩阵的逆矩阵b-1，就成了该法的关键。如果每次迭代都必须从原始数据来计算b-1，计算量是很大的。改进单纯形法能够在相邻的两次迭代中，用上一次基矩阵的b的逆矩阵b-1直接计算出新的基矩阵的的逆矩阵，大大简化了计算。
改进单纯形法的计算步骤：
1] 根据给出的线性规划问题，在加入松弛变量或人工变量后，得到初始基变量，求出初始可行基b的逆矩阵b-1和初始基可行解，再计算单纯形乘子。
2] 计算非基变量的检验数，；如果，即每一个非基变量对应的检验数都小于零，则表示已得到了最优解，停止计算。如果还存在，转入下一步；
3] 根据，对应的非基变量为换人变量，再计算（为进基列向量，为所对应的原始系数列向量）；如果，原问题无界解，停止计算，否则，转入下一步；
4] 根据规则，求出。
对应的基变量为换出变量，同时，得到一组新的基变量和新的基矩阵；
5] 计算新的基矩阵的逆矩阵。先要构造一个初等变换矩阵，再利用计算出，再求出、；
6] 重复[2]至[5]步骤，直至求出最优解。
在两次相邻的迭代中，如何用用上一次基矩阵b的逆矩阵b-1直接计算出新的基矩阵的的逆矩阵，而不用新基的原始数据来计算逆矩阵。
由于在两次相邻的迭代中，上一步迭代的基矩阵b，在基变换后，即用非基变量取代基变量，得到下一步迭代的新基矩阵，两个基矩阵相比仅差一列的系数列向量，因此，可以直接根据上一步的基矩阵b的逆矩阵b-1和换人变量的系数列向量计算出新基矩阵。
在相邻的两次迭代中，设上一步迭代的可行基b为，经过基变换后，得到一新的可行基为，则迭代后所得到新的可行基的为，其中，称为初等变换矩阵。
证明：因为。
即， 已知，又因为，
根据矩阵知识，具体构造初等变换矩阵：在确定了换人变量和换出变量后，在与基同阶的单位阵中用进基列向量替换与换出变量所在列相对应的单位列向量，其中进基列向量中的元素取倒数，其余元素用元素去除，并取相反数，这样就得到初等变换矩阵。
例1． 用改进单纯形法求解下列线性规划问题。
解：将上述问题化为标准型，即。
取初始可行基，计算得，
初始基可行解，
单纯形乘子，
计算非基变量检验数，
按照，所以，确定为换人变量。
计算进基列向量，
确定换出变量，按照规则，对应的基变量为换出变量。所以，得到新基为。
第1次迭代： ，求新的基可行解，
单纯形乘子，
计算非基变量检验数，
对应的非基变量为换人变量。
计算进基列向量，确定换出变量，按照规则，对应的基变量为换出变量。所以，得到新基为。
第2次迭代：
求新的基可行解，
单纯形乘子，
计算非基变量检验数，
对应的非基变量为换人变量。
计算进基列向量，确定换出变量，按照规则，对应的基变量为换出变量。所以，得到新基为。
第3次迭代：
求新的基可行解，
单纯形乘子，
计算非基变量检验数，
非基变量全为非负，得到最优解。
第三节对偶问题的提出。
**性规划中，任何线性规划问题都具有对偶性，即任何一个线性规划问题都存在有与它相对应的另外一个线性规划问题，如果把前一个线性规划问题称为原问题，后一个相对应的线性规划问题就称为它的对偶问题，互为对偶的原问题和对偶问题是相对的。
线性规划的对偶理论是专门研究原问题与对偶问题之间的关系及其解的性质的理论，是线性规划理论的重要组成部分。
**性规划中，对偶理论有着很重要的应用。如，根据对偶理论，提出了另一个求解线性规划问题的方法对偶单纯形法；应用对偶理论可以对影子**进行分析，在经济管理中有着重要的意义；在灵敏度分析以及运输问题的算法中等都有着应用。
下面从一个实际问题引出对偶问题。在第一章例1中，我们讨论了一个工厂制订生产计划的线性规划问题。现在假设工厂的决策者决定自己不再生产产品，而将全部可以利用的资源出租，收取出租费，这样，工厂的决策者就得考虑如何给这些资源确定一个合理的**。
显然，决策者在确定收费**时，考虑的原则是，一是出租资源所收回的费用应不低于自己生产获得的利润，否则，就不出租，自己生产；二是定价又不能太高，要使对方愿意接受。
所以，合理的定价应在保证自己的收入不低于自己生产获得的利润的前提下，自己的收入即对方的支出尽可能小，这样自己不会吃亏，对方也能接受。否则，双方就不能成交。
假设y1、y2、y3分别为三种资源的收费单价，已知每生产一件产品i，需要1个设备台时和4吨原材料a，为不使工厂收益减少，出租生产一件产品的资源所获得的收入应不低于生产一件产品的利润，即有。
同样地，出租生产产品ii的资源所获得的收入也应不低于自己生产产品的利润，该厂所有资源都出租，所得的总收入(即对方的总支出)为，所以，该厂出租资源这个问题的数学模型，即为。
这一规划问题就是原问题的对偶问题。事实上，这两个问题是有内在联系的，它们的最优目标值是相同的，对决策者这两个方案都是最优方案。
这个对偶问题有它相应的意义，但有一些对偶问题很难从直观上给予解释。
下面从数学理论上提出线性规划的对偶问题。已知线性规划问题，其非基变量的检验数为，
当该线性规划问题得到最优解时，令，从(2)式可以得出，
因为所有变量的检验数(包括基变量和非基变量)都可表示为，又由，得，
由于y的上界为无穷大，所以，yb最优值只存在最小值。归纳起来，可以得到另一个线性规划问题，即原问题的对偶问题。
第四节原问题与对偶问题的关系。
原问题与对偶问题的关系分为对称型对偶关系和非对称型对偶关系。
1. 对称型对偶关系。
对称型对偶关系具有以下两点特征：
1〕 目标函数求max,约束条件是；目标函数求min,约束条件是；
2〕 所有变量为非负。
对称型对偶关系的标准形式如下：
原问题：对偶问题：
这一对对偶问题由于结构的对称性(约束类型和变量取值),所以，称为对称型对偶关系。
对称型对偶关系可归纳如下：
1〕 原问题求目标函数最大化；对偶问题求目标函数最小化；
2〕 原问题的约束条件是；对偶问题的约束条件是；
3〕 原问题约束条件的右端项是对偶问题目标函数的系数；对偶问题约束条件的右端项是原问题目标函数的系数；
4〕 原问题约束条件的个数等于对偶变量个数；对偶问题约束条件的个数等于原问题变量个数；
根据原问题与对偶问题的变换关系，可以写出一个线性规划问题的对偶问题。
例2． 原问题：
其对偶问题为：
2. 非对称型对偶关系。
如果线性规划的约束条件即包含有不等式又包含有等式，变量又有非正或无约束，那么，这一对对偶问题就称为非对称型对偶关系。
对于非对称型线性规划问题，可以将它转换为对称型，然后再按照对称型的变换规则，写出它的对偶问题。
例3． 写出下列线性规划的对偶问题。
解：令且，并将所有约束写成的形式，再令对偶变量为，写出对偶问题，再令，并将(2)、(3)两个约束合并成等式约束，得，对于非对称型对偶问题，关键在于处理等式约束和无约束变量，从上面例子可以看出，等式约束和无约束变量之间的关系：
原问题的等式约束条件，对应于对偶问题的无约束变量；
对偶问题的等式约束条件，对应于原问题的无约束变量；
所以，原问题与对偶问题的对偶规则可以归纳如下，根据这些规则直接写出一般线性规划问题的对偶问题：
例4． 写出下列线性规划问题的对偶问题。
运筹学讲义
第六讲排队论。x y zx处填写表示相继到达间隔时间的分布 y处填写表示服务时间的分布 z处填写并列的服务台的数目c.c 1 单服务台，c 1 多服务台。表示相继到达间隔时间和服务时间的各种分布的符号 m 负指数分布。d 确定型。ek k阶爱尔朗分布。gi 一般相互独立的时间间隔的分布。g 一般服务...
运筹学讲义
第三讲整数规划。一 整数规划模型。12年，第一题，15分 一家公司打算在甲地 乙地或甲乙两地新建工厂，一地至多建一个工厂，并且在甲乙两地至多建一个仓库，仓库位置随工厂地点而定 即，如某地有工厂，该地可设仓库或不设仓库 但如该地不设工厂，则该地一定不设仓库 若总资本可用量为20 百万元 其他数据如下表...
运筹学讲义
第三部分图与网络分析。图与网络分析部分内容框架。图与网络的基本概念。图连通图。图的矩阵表示。树与最小树。最短路问题。图论在网络分析的应用最大流问题。最小费用最大流问题。第四章图与网络分析。1.图与网络的基本概念。一 图及其分类。本章研究的图与平面几何中的图不同，我们只关心图中有多少个点，点与点之间有...