Chapter02_对偶理论与灵敏度分析

1. 对用矩阵形式表达的一般线性规划问题 $\max\{z = \boldsymbol{CX} + 0 \boldsymbol{X}_{s} \vert \boldsymbol{AX} + \boldsymbol{IX}_s = \boldsymbol{b},\ \boldsymbol{X}\ge 0, \boldsymbol{X}_s \ge 0\}$ ，或以 $\boldsymbol{X}_{B}$ 表示基变量，$\boldsymbol{X}_{N}$ 表示非基变量，$\boldsymbol{C}_B,\boldsymbol{C}_N$ 为他们相应在目标函数中的系数。据此列出初始单纯型表及迭代后的单纯型表$$\begin{array}{ccc|cc|c}\hline & \boldsymbol{C}_j & & \boldsymbol{C}_{B} & \boldsymbol{C}_{N} & \boldsymbol{C}_{s} \\ \boldsymbol{C}_{B} & 基 & \boldsymbol{b} & \boldsymbol{X}_B & \boldsymbol{X}_N & \boldsymbol{X}_{s} \\ \hline \boldsymbol{0} & \boldsymbol{X}_{s} & \boldsymbol{b} & \boldsymbol{B} & \boldsymbol{N} & \boldsymbol{I} \\ \hline & \sigma_{j} & & \boldsymbol{C}_B & \boldsymbol{C}_N & \boldsymbol{0} \\ \hline \boldsymbol{C}_{B} & \boldsymbol{X}_{B} & \boldsymbol{B}^{-1}\boldsymbol{b} & \boldsymbol{I} & \boldsymbol{B}^{-1}\boldsymbol{N} & \boldsymbol{B}^{-1} \\ \hline & \sigma_{j} & & \boldsymbol{0} & \boldsymbol{C}_{N}^{} - \boldsymbol{C}_{B}\boldsymbol{B}^{-1}\boldsymbol{N} & - \boldsymbol{C}_{B}\boldsymbol{B}^{-1} \\ \hline \end{array}$$
2. 简述改进单纯形法的计算步骤，并说明其在哪些方面对单纯形法的计算作了改进
   1. 步骤
      1. 首先，对于矩阵进行分块
         • 目标函数 $\max z = \begin{bmatrix}\boldsymbol{C}_B & \boldsymbol{C}_N\end{bmatrix}\begin{bmatrix}\boldsymbol{X}_B\\ \boldsymbol{X}_N\end{bmatrix} = \boldsymbol{C}_B\boldsymbol{X}_B + \boldsymbol{C}_N\boldsymbol{X}_N$
         • 约束 $\begin{bmatrix}\boldsymbol{B} & \boldsymbol{N}\end{bmatrix}\begin{bmatrix}\boldsymbol{X}_{B} \\ \boldsymbol{X}_{N}\end{bmatrix} = \boldsymbol{b}$
         • 非负条件 $\boldsymbol{X}_B,\boldsymbol{X}_N\ge 0$
      2. 迭代后的形式
         • 目标函数 $\max z = \boldsymbol{C}_{B}(\boldsymbol{B}^{-1}\boldsymbol{b} - \boldsymbol{B}^{-1}\boldsymbol{NX}_N) + \boldsymbol{C}_{N}\boldsymbol{X}_{N} = \boldsymbol{C}_{B}\boldsymbol{B}^{-1}\boldsymbol{b}+ (\boldsymbol{C}_{N} - \boldsymbol{C}_{B}\boldsymbol{B}^{-1}\boldsymbol{NX}_N)\boldsymbol{X}_{N}$
         • 约束条件 $\begin{bmatrix}\boldsymbol{I} & \boldsymbol{B}^{-1}\boldsymbol{N}\end{bmatrix}\begin{bmatrix}\boldsymbol{X}_{B} \\ \boldsymbol{X}_{N}\end{bmatrix} = \boldsymbol{B}^{-1}\boldsymbol{b}$
         • 迭代所得到的基可行解 $\boldsymbol{X}^* = \begin{bmatrix}\boldsymbol{B}^{-1}\boldsymbol{b}\\\boldsymbol{0}\end{bmatrix}$
      3. 是否迭代的判断标准，以及迭代时入基和出基变量的选择标准的普通单纯形法相同
   2. 改进之处 对于计算机而言，在迭代过程中采用对于矩阵求逆而不是高斯消去法的方式会产生相对更少的误差，也有助于计算机的计算。（在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数。这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量。）
3. 已知单纯形法的某一步迭代的基为 $\boldsymbol{B}$，其对应变量为 $(x_{1},\cdots,x_{l-1},x_{l},x_{l+1},\cdots,x_{m})$，经迭代后其基为 $\boldsymbol{B}_1$，其对应变量为 $(x_{1},\cdots,x_{l-1},x_{k},x_{l+1},\cdots,x_{m})$，尝试写出 $\boldsymbol{B}$ 和 $\boldsymbol{B}_1$ 之间的关系式$$\begin{array}{ll}\boldsymbol{C}_{B}\boldsymbol{B}^{-1}\boldsymbol{b} \le \boldsymbol{C}_{B_{1}}\boldsymbol{B}_{1}^{-1}\boldsymbol{b} \end{array}$$
4. 从经济上解释对偶问题和对偶变量的含义
   1. 举例子
      1. 问题一：某一家公司拥有有限的几种资源，生产几种产品，每单位产品的价格一定，问该公司如何规划生产使得其获利最大？
      2. 问题二：另有一家公司看中了问题一中公司所拥有的资源，试图向其收购其拥有的几种资源，问这家公司如何出价才能以最小的成本收购前一家公司的所有资源
      3. 一般称问题一为原问题，问题二为问题一的对偶问题
   2. 从经济意义上，对偶变量可被视为一种潜在的价格，被称为影子价格，其可被视为第 $i$ 种资源在所给问题最优方案中做出贡献的估计。
5. 根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间，解及检验数之间的对应关系
   1. 弱对偶性 若 $\bar{x}_j\quad(j=1,2,\cdots,n)$ 为原问题的可行解，$\bar{y}_i \quad(i=1,2,\cdots,m)$ 为其对偶问题的可行解，则：$$\sum_{j=1}^{n}c_{j}\bar{x}_{j} \le \sum_{i=1}^m b_i\bar{y}_i$$
      1. 原问题最优解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题最优解的目标函数值原问题目标函数值的上界
      2. 若原问题有可行解切目标函数值无界，则其对偶问题无可行解；反之，若对有问题有无界解，则其对偶问题无可行解；
      3. 若原问题有可行解而其对偶问题无可行解，则原问题的目标函数值无界
   2. 最优性 若 $\hat{x}_j\quad(j=1,2,\cdots,n)$ 为原问题的可行解，$\hat{y}_i \quad(i=1,2,\cdots,m)$ 为其对偶问题的可行解，且有 $$\sum_{j=1}^{n}c_{j}\hat{x}_{j} = \sum_{i=1}^m b_i\hat{y}_i$$
      • 则 $\hat{x}_j \quad(j=1,2,\cdots,n)$ 为原问题的最优解，$\hat{y}_i\quad(i=1,2,\cdots,m)$ 为其对偶问题的最优解
   3. 强对偶性 若原问题和对偶问题均有可行解，则两者均具有最优解，且他们最优解的目标函数相等
   4. 松弛互补性 若对应某一约束条件的对偶变量值为非零，则其对应的约束条件严格取等号；反之若约束条件取严格不等式，则该约束条件对应的对偶变量一定为零。
6. 什么是资源的影子价格，同相应的市场价格之间有什么区别？影子价格的意义？
   1. 定义和区别 对偶变量 $y^*_i$ （对偶问题取最优解时）代表在资源最优利用的条件下，对单位第 $i$ 种资源的估价。这种估价不是资源的实际市场价格，而是单位第 $i$ 种资源在所给问题的最优方案中作出的贡献的估价，为了区分起见，称为影子价格。
   2. 意义
      1. 资源的影子价格依赖于资源的利用情况，其是当目前一组基变量用于获得原问题最优解时，对偶变量 $y_i$ （即第 $i$ 种资源） 每单位对于利润的贡献。
      2. 影子价格是一种边际价格，$y^*_i$ 的值在理论上相当于在资源得到最优利用的生产条件下，$b_i$ 每增加一个单位时目标函数的 $z$ 的增量
      3. 影子价格实际上也是一种机会成本。当市场价格低于某一资源的影子价格时，可考虑买入；而当市场价格高于该资源的影子价格时，也可考虑卖出该资源
      4. 根据松弛互补性 当某种资源 $b_i$ 未得到充分利用时，该资源的影子价格为0；当资源的影子价格不为0时，表明该资源在生产中已耗费完毕。注意：当出现退化的最优解时，会出现某种资源 $i$ 刚好耗尽，而非稀缺，但资源的影子价格 $y_i$ 仍然大于0的情况，这时 $b_i$ 的任何增加只会带来该种资源的剩余，而不会增加任何利润。
      5. 从影子价格的含义上再次考察单纯性表的计算$$\sigma_j = c_j - \boldsymbol{C_BB}^{-1}\boldsymbol{P}_j = c_j - \sum_{i=1}^{m}a_{ij}y_i$$
         • $c_j$ 代表第 $j$ 种产品的利润，$\displaystyle \sum_{i=1}^m a_{ij}y_{i}$ 是生产该种产品所消耗各项资源的影子价格的总和，即产品的隐含成本。当利润大于隐含成本时，表明安排该产品生产有利，可在计划中安排。也就是单纯性表中各检验数的经济意义
7. 试述对偶单纯形法的计算步骤，他的优点和应用上的局限性
   1. 计算步骤
      1. 确定出基变量 因为总存在 $\bar{b}_i < 0$ ，令 $\displaystyle\bar{b}_r = \min_{i}\{\bar{b}_i\}$ 其对应变量 $x_r$ 为出基变量
      2. 确定入基变量
         1. 为了使下个表中 $\bar{b}_r>0$，需要满足 $a_{rj} <0$ 非基变量才可能被选为入基变量
         2. 为了使下一个表中对偶问题的解仍为可行解，令$$\theta = \min_{j}\bigg\{\left.\frac{c_j - z_j}{a_{rj}}\right\vert a_{rj}<0\bigg\} = \frac{c_j-z_j}{a_{rs}}$$称 $a_{rs}$ 为主元素，$x_s$ 为入基变量
      3. 用入基变量替换出基变量，得到一个新的基
      4. 循环1，2，3直到所有的 $b_i>0$ 得出最优解
   2. 优点和局限性
      1. 优点
         1. 初始解可以是非可行解，当检验数都是负数时，就可以进行基的变化，这时不需要加入人工变量，因此可以简化计算
         2. 当变量多于约束条件，对这样的线性规划问题，用对偶单纯形法计算可以减少计算量，因此，对变量较少，约束较多的线性规划问题，可以先化为其对偶问题，然后用对偶单纯形法求解
         3. 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可以使得问题的处理简化。
      2. 局限 对大多数线性规划问题，很难找到一个对偶问题初始可行基，因而此方法在求解线性规划问题中很少单独使用。
8. 将 $a_{ij},b_i,c_j$ 的变化分别直接反映到最终单纯形表中，表中原问题和对偶问题的解各自会出现什么变化？有多少种不同情况及如何去处理？
   1. 对于资源数量 $b_r$ 发生变化
      1. 当 $\boldsymbol{X_{B}}' = \boldsymbol{B}^{-1}(\boldsymbol{b} + \Delta \boldsymbol{b})\ge 0$ 时，因终表的检验数不变，故最优基不变，但最优解的值发生了变化，故 $\boldsymbol{X_{B}}'$ 为最优解。
      2. 当 $\Delta b_{r}$ 不满足 $\max\{-\bar{b}_i/a_{ir}\vert a_{ir} >0\} \le \Delta b_{r}\le \min\{-\bar{b}_i/a_{ir}\vert a_{ir}<0\}$ 时，原问题的解发生变化出现非可行解，采用对偶单纯形法继续求解。而其对偶问题的检验数发生变化变为非最优解。
   2. 对于目标函数价值系数 $c_j$ 的变化分析
      1. 非基变量对应的 $c_j$
         1. 若 $\sigma_{j} = c_j + \Delta c - \boldsymbol{C_{B}B}^{-1}\boldsymbol{P}_j \le 0$，则原问题的最优解和最优基均不变
         2. 若 $\sigma_{j} = c_j + \Delta c - \boldsymbol{C_{B}B}^{-1}\boldsymbol{P}_j > 0$，则原问题的最优基和最优解发生改变 $\boldsymbol{X}_j$ 入基，需要通过单纯形法确定出基变量并迭代。
      2. 基变量对应的 $c_r$
         1. 这时$$\begin{split}(\boldsymbol{C_{B}} + \Delta\boldsymbol{C_{B}})\boldsymbol{B}^{-1}\boldsymbol{A} &= \boldsymbol{C_{B}B}^{-1}\boldsymbol{A} + \begin{pmatrix}0 & \cdots& \Delta c_r & \cdots & 0\end{pmatrix}\boldsymbol{B}^{-1}\boldsymbol{A}\\&=\boldsymbol{C_{B}B}^{-1}\boldsymbol{A} + \Delta c_r\begin{pmatrix}\bar{a}_{r1} & \bar{a}_{r2} & \cdots & \bar{a}_{rn} \end{pmatrix}\end{split}$$检验数变为 $$\sigma_{j}' = c_j - \boldsymbol{C_BB}^{-1}\boldsymbol{P}_j - \Delta c_j\bar{a}_{rj} = \sigma_j - \Delta c_j\bar{a}_{rj}$$故其变化范围在$$\max_{j}\bigg\{\left.\frac{\sigma_j}{\bar{a}_{rj}}\right\vert \bar{a}_{rj}>0\bigg\}\le\Delta c_j\le \min_{j}\bigg\{\left.\frac{\sigma_j}{\bar{a}_rj}\right\vert \bar{a}_{rj}<0\bigg\}$$
         2. 若不在此范围内，则原问题的检验数发生变化，需要通过单纯形法进一步求出最优解
   3. 技术系数 $a_{ij}$ 的变化
      1. 增加一列 $\boldsymbol{P}_j$
         1. 原问题依然为可行解，但新一列的检验数可能大于0，若发生，则采用单纯形法来求出新的最优解
      2. 原产品技术系数发生改变
         1. 出现对偶问题和原问题均为可行解，则最优解和最优基不变
         2. 出现对偶问题和原问题均非可行解，则通过引入人工变量的方式来进一步求解
9. 试叙述参数线性规划的分析步骤，它同灵敏度分析的相似之处及主要差别表现在哪里？
   1. 步骤
      1. 对含有某参变量 $t$ 的参数线性规划问题，先令 $t=0$，y用单纯形法求出最优解；
      2. 用灵敏度分析法，将参数 $t$ 直接反映在终表中
      3. 当参数变量 $t$ 连续变化大或变小时，观察 $\boldsymbol{B}^{-1}\boldsymbol{b}$ 列和检验数的变化。若在$\boldsymbol{B}^{-1}\boldsymbol{b}$ 列出现负值，则以其对应的变量作为出基变量，利用对偶单纯形法进行迭代；若在检验数行首次出现某正值时，以其对应的变量作为出基变量，利用单纯形法进行迭代。
      4. 在经过迭代一步后得到的新表上，令参变量 $t$ 继续增大或减小，重复步骤3，直到$\boldsymbol{B}^{-1}\boldsymbol{b}$ 列不再出现负值，检验数行不再出现正值。
   2. 相似之处和差别
      1. 相似之处：二者的分析方法相似
      2. 差别：研究目的不同
         1. 灵敏度分析讨论最优基不变的情况下，确定 $a_{ij},b_{i},c_j$ 的变化范围
         2. 参数线性规划研究这些参数中某一参数连续变化时，使最优解发生变化的各临界点的值