Chapter01_线性规划基础

1. 实际问题中线性的含义（线性规划的前提条件）
   1. 严格的比例性：如生产某产品对资源的消耗量和可获得的利润，同其产量严格成比例
   2. 可叠加性 如生产多种产品时，可获取的总利润是个产品的利润之和，对某项资源的消耗量等于各产品对此资源的消耗量之和
   3. 可分性 模型中的变量可以取值为小数、分数或某一实数
   4. 确定性 模型中的参数 $c_j,\ a_{ij},\ b_{i}$ 均为确定的常数
2. 线性规划的数学模型的结构和各要素的特征
   • 结构 线性规划的数学模型由三个要素组成：
     1. 变量 或称决策变量，问题中要确定的未知量，用于表明规划中的用数量表示的方案，举措，可由决策者决定和控制
     2. 目标函数 决策变量的函数，按优化目标分别在这个函数前加上 $\max$ 或 $\min$
     3. 约束条件 指决策变量取值时，所受到的各种资源条件的限制，通常表达为含决策变量函数的等式或不等式。

3. 线性规划问题可能出现的结果？哪些结果反映建模时有错误？

   • 唯一最优解：线性规划的最优解落在可行域的某个顶点上
   • 无穷多最优解：线性规划的最优解落在可行域的某条边上
   • 无界解：可行域无边界，而目标函数数值也可增大至无穷
   • 无解：可行域不存在

4. 什么是线性规划的标准形式？如何将一个非标准型的线性规划问题转化为标准形式？

   • 标准形式 $$\begin{split} & \max\ z = \sum_{j=1}^{n}c_{j}x_{j} \\ & \text{s.t.}\begin{cases}\displaystyle\sum_{j=1}^{n}{a}_{ij}x_{j} = b_i & (i = 1,\cdots,m)\\ x_{j}\ge 0 &(j = 1,\cdots, n)\end{cases} \end{split}$$
   • 转化方法
     1. 目标函数为求极小值，即 $\min z = \sum_{j=1}^{n} c_{j}x_{j}$：令 $z'=-z$，即转化为 $\max\ z' = -\sum_{j=1}^{n}c_jx_j$
     2. 约束条件的右端 $b_i < 0$：将等式或不等式两端同乘 $-1$，则右端必大于零
     3. 约束条件为不等式
        1. 约束条件为 $\le$ 时，加上一个非负的松弛变量，使之成为等式
        2. 约束条件为 $\ge$ 时，减去一个非负的松弛变量，使之成为等式
     4. 取值无约束的变量：用两个非负变量之差代替无约束变量带入线性规划模型即可
     5. 对于 $x\le 0$：令 $x' = -x$
5. 试述线性规划问题的可行解、基解、最优解的概念及上述解之间的相互关系
   1. 可行解：满足线性规划约束条件的所有解
   2. 基解：
      1. 基 设 $\boldsymbol{A}$ 为约束方程的 $m\times n$ 阶系数矩阵 $(m < n)$，其秩为 $m$，$\boldsymbol{B}$ 是矩阵 $\boldsymbol{A}$ 中的一个 $m\times m$ 阶的满秩子矩阵，则称 $\boldsymbol{B}$ 为线性规划问题的一个基，为了不失一般性，设 $$\boldsymbol{B} = \begin{bmatrix} a_{11} & \cdots & a_{1m} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mm} \end{bmatrix}= \begin{bmatrix}\boldsymbol{P}_1 & \cdots & \boldsymbol{P}_m\end{bmatrix}$$
         • $\boldsymbol{B}$ 中每个列向量 $\boldsymbol{P}_j\ (j=1,\cdots,m)$ 称为基向量，与基向量 $\boldsymbol{P}_j$ 对应的变量 $x_j$ 称为基变量，除基变量以外的变量称为非基变量
      2. 基解 约束方程组中令所有非基变量为零，因为 $\det(\boldsymbol{B})\ne 0$，故根据克莱姆法则，由 $m$ 个约束方程可解出 $m$ 个基变量的唯一解 $\boldsymbol{X}_{\boldsymbol{B}} = (x_1,\cdots,x_m)^{\text{T}}$，将这个解加上非基变量取零的值有 $\boldsymbol{X} = (x_1,\cdots,x_m,0,\cdots,0)^{\intercal}$，称 $\boldsymbol{X}$ 为线性规划的基解。
      3. 基可行解 满足变量非负约束条件的基解称为基可行解
      4. 可行基 对应于基可行解的基
   3. 最优解：满足约束条件切使目标函数取到最大值的解
   4. 相互关系
      1. 最优解一定是可行解
      2. 最优解一定包含某个基解
      3. 基解不一定是可行解

6. 单纯性法的迭代原理

   1. 确定初始基可行解 （找出约束系数阵中的单位阵）
      1. 对于约束条件均为 $\le$ 的情况，其松弛变量 $x_{s_{1}},\cdots,x_{s_m}$ 的系数矩阵即为单位矩阵。
      2. 对于约束条件为 $\ge$ 或 $=$ 的情况，为了便于找到初始基可行解，可以构造人工基，人为产生一个单位矩阵
   2. 从一个基可行解转化为相邻的基可行解
      1. 定义 若两个基可行解是相邻的，则他们之间变换且仅变换一个基变量。
      2. 设 $\boldsymbol{P}_{1},\cdots, \boldsymbol{P}_m$ 是一个基，其对应的基可行解为 $\boldsymbol{X}^{(0)} = \left(\begin{matrix}x_{1}^{0} & x_{2}^{0} & \cdots & x_{m}^{0} & 0 & \cdots & 0\end{matrix}\right)^{\intercal}$，有 $$\sum_{i=1}^{m} \boldsymbol{P}_{i}x_{i}^{0} = \boldsymbol{b}$$其他向量可由该基的线性组合表示，有$$\begin{array}{cc} \displaystyle\boldsymbol{P}_j= \sum_{i=1}^{m}a_{ij}\boldsymbol{P}_{i}\\ \Downarrow \\ \displaystyle\theta\bigg(\boldsymbol{P}_{j} - \sum_{i=1}^{m}a_{ij}\boldsymbol{P}_i\bigg) = 0 \\\Downarrow \\ \displaystyle \sum_{i=1}^{m}\boldsymbol{P}_{i}(x_{i}^{0}-\theta a_{ij}) + \theta \boldsymbol{P}_j = \boldsymbol{b} \end{array}$$于是下一个基可行解变成了 $\boldsymbol{X}^{(1)} = \left(\begin{matrix} x_{1}^{0} - \theta a_{1j},\cdots, x_{m}^{0}-\theta a_{mj},0,\cdots,\theta,\cdots,0 \end{matrix}\right)$，于是有$$\begin{array}{cc}\end{array} \begin{cases}\theta \ge 0 \\ x_{i}^{0} - \theta a_{ij} \ge 0\end{cases}$$ 用此来找出找出出基变量，确定 $\theta$: $$\theta = \min_{i}\bigg\{\left.\frac{x_{i}^0}{a_{ij}}\right\vert a_{ij} > 0\bigg\}=\frac{x_{\ell}^{0}}{a_{\ell j}} =\frac{b^{0}_{\ell}}{a_{\ell j}}$$于是用 $\boldsymbol{P}_{j}$ 替换 $\boldsymbol{P}_{\ell}$ 进入基变量$$\begin{array}{cccccccc|c} \boldsymbol{P}_{1} & \boldsymbol{P}_{2} & \cdots & \boldsymbol{P}_{\ell-1} & \boldsymbol{P}_{j} & \boldsymbol{P}_{\ell+1} & \cdots & \boldsymbol{P}_{m} & \boldsymbol{b}^{0}\\ 1& 0 &\cdots & 0 & a_{1j} & 0 &\cdots & 0 & b_{1} \\ 0& 1 &\cdots & 0 & a_{2j} & 0 &\cdots & 0 & b_{2} \\ \vdots & \vdots & \ddots &\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0& 0 &\cdots & 1 & a_{\ell -1,j} & 0 &\cdots & 0 & b_{\ell -1} \\ 0& 0 &\cdots & 0 & a_{\ell j} & 0 &\cdots & 0 & b_{\ell} \\ 0& 0 &\cdots & 0 & a_{\ell+1, j} & 1 &\cdots & 0 & b_{\ell + 1} \\ \vdots & \vdots & \ddots &\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0& 0 &\cdots & 0 & a_{mj} & 0 &\cdots & 1 & b_{m} \\\end{array}$$ 然后通过初等行变化将左侧的系数矩阵化为单位阵，得到 $\boldsymbol{b}^{1}$，进入下一次迭代
   3. 最优性检验和解的判断
      1. 分别将 $\boldsymbol{X}^{(0)}$ 和 $\boldsymbol{X}^{(1)}$ 带入目标函数得 $$\begin{split} & z^{(0)} = \sum_{i=1}^{m} c_ix_{i}^{0} \\ &\begin{split} z^{(1)} &= \sum_{i=1}^{m}c_i(x_i^0-\theta a_{ij}) + \theta c_j \\ & = \sum_{i=1}^{m} c_ix_{i}^{0} + \theta \bigg(c_{j} - \sum_{i=1}^{m}c_ia_{ij}\bigg) \\ & = z^{(0)} + \theta \bigg(c_{j} - \sum_{i=1}^{m}c_ia_{ij}\bigg) \end{split} \end{split}$$ 因为 $\theta > 0$ 所以只要$(c_j - \sum_{i=1}^{m}c_ia_{ij} )>0$ 就有 $z^{(1)} > z^{(0)}$ 一般简写为 $(c_j - z_j)$ 或 $\sigma_j$
         1. 结果判别
            1. 所有的 $\sigma_j \le 0$，表明现有基可行解的目标函数比起相邻各顶点的目标函数值都大，故现有顶点对应的基可行解即为最优解
            2. 所有的 $\sigma_j \le 0$，有对某个非基变量有 $c_j - z_j = 0$，且可找到 $\theta > 0$，表明可以找到另一个顶点目标函数值也达到最大，于是有无穷多解
            3. 若存在某个 $\sigma_j > 0$，又 $\boldsymbol{P}_{j} \le 0$，于是对于任意 $\sigma > 0$，均有 $x^0_i - \theta a_{ij} \ge 0$，因此 $\theta$ 的取值可以无限增大而不受限制，于是出现无界解

7. 叙述单纯型法的计算步骤。如何在单纯型表上判别问题是具有唯一最优解、无穷多最优解、无界解还是无可行解？

   1. 求初始基可行解，列出初始单纯形表。表的结构：第1列是基变量对应的价值系数，表的第2－3列列出基可行解中的基变量及其取值；接下来列出问题中的所有变量，基变量下为单位矩阵，非基变量下面的数字是该系数向量 $\boldsymbol{P}_{j}$ 表为基向量现行组合时的系数。
   2. 最优性检验：若表中的检验数 $c_j - z_j \le 0$，且基变量中不含人工变量时，表中的基可行解即为最优解。若表中的检验数 $c_j - z_j\le 0$，而非基变量中存在 $c_j - z_j = 0$，且可找到对应的 $\theta >0$，表明存在无穷最优解；若 $c_j - z_j >0$ 且对应的 $\boldsymbol{P}_j<0$ 则出现了无界解
   3. 从一个基可行解转化到相邻的目标函数更大的基可行解
      1. 确定入基变量，找出最大的正检验数对应的变量，让其入基 $$\sigma_k=\max_j\{\sigma_j \vert \sigma_j > 0\}$$
      2. 确定出基变量，根据确定 $\theta$ 的原则，找出相应的出基变量$$\theta = \min_i\bigg\{\left.\frac{b_i}{a_{ik}}\right\vert a_{ik} > 0 \bigg\}$$
      3. 用入基变量代替出基变量，得到新的基可行解，同时得到一新的单纯形表，并且在该表中的基仍为单位矩阵。通过初等行变换将入基变量化为同其他基变量正交的单位向量
      4. 重复2，3步直至计算结束
8. 若线性规划的标准型变化为求目标函数的最小化 $\min\ z$，则用单纯型法计算时如何判别问题已得到最优解？
   1. 当所有 $\sigma_j \ge 0$ 时，说明已经得到最优解
   2. 当所有 $\sigma_{j}\ge 0$ 时，且存在某个非基变量的 $\sigma_{j} = 0$，并能找到相应的 $\theta >0$，使得该非基变量可以进基时，说明存在无穷多解
   3. 当存在 $\sigma_{j} < 0$，且对应的 $\boldsymbol{P}_j < 0$ 时，说明对于任意的 $\theta >0$，都满足 ${\boldsymbol{P}_{i}(x_{i}^{0} - \theta\cdot a_{ij})} \ge 0$，则当 $\theta$ 可以无限增大，目标函数可以无限减小，则出现无界解
9. 在确定初始可行基时，什么情况下要在约束条件中增加人工变量？在目标函数中人工变量前的系数为 $-M$ 的经济意义是什么？
   1. 当确定初始可行基而无法找到现成的单位矩阵时，需要增加人工变量
   2. $-M$ 称为“罚因子”，因为在加入人工变量之前，约束已经满足等式，因此人工变量的取值必须为0；即只要人工变量的取值大于0，便不是最优解。
10. 什么是单纯型法计算的两阶段法？为什么要将计算分为两个阶段进行？如何根据第一阶段的计算结果来判定第二阶段的计算是否需要继续进行？
    1. 定义 两阶段法是对单纯形法中人工变量进行处理的一种方法。其可分为两个阶段：
       1. 在第一阶段，求解目标函数仅包含人工变量的线性规划问题（即：令其他变量的价值系数取0，而人工变量的价值系数取得某一常数（一般取$1$）），在保持原问题约束不变的情况下，求这个目标函数最小时的解
       2. 若第一阶段的最优解的人工变量取值均为0，则可进行下一步，若最优解包含不为0的人工变量，则说明原问题无可行解
       3. 在第二阶段，在原问题中去除人工变量，并沿用第一阶段的最优解，找出原问题的最优解。
    2. 为什么 大 $M$ 法的局限性：对于计算机而言，$M$ 只能是计算机内一段较大的数字，若线性规划问题中的 $a_{ij},\ b_i,\ c_j$ 等参数值与这个代表 $M$ 的数值相近或远小于这个数值时，由于计算机取值的误差，可能使结果发生错误，于是出现了两阶段法
11. 简述退化的含义和处理退化的勃兰特规则
    1. 含义 按 $\theta$ 的最小值约定出基变量时，可能会出现存在两个以上相同最小值，从而使得下一个表的基可行解出现一个或多个基变量等于零的退化解。这一般是由于模型中存在多余的约束。
    2. 勃兰特准则
       1. 当存在多个 $\sigma_{i} > 0$ 时，始终选取下标值最小的变量作为换入变量
       2. 当存在 两个以上相同的 $\theta$ 时，始终选取下标最小的作为出基变量
12. 举例说明生产和生活中引用线性规划的可能案例，并对如何应用进行必要描述。