Chapter03_运输问题

1. 试述运输问题数学模型的特征，为什么模型的 $m+n$ 个约束中至多只有 $(m+n-1)$ 个是独立的
   1. 数学模型$$\begin{split}&\min z = \sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}\\&\text{s.t.}\begin{cases}\displaystyle\sum_{j=1}^{n}x_{ij} = a_i,& i=1,2,\cdots,m;\\\displaystyle\sum_{i=1}^nx_{ij} = b_{j},& j = 1,2,\cdots,n\\x_{ij}\ge0,&i=1,2,\cdots,m;j=1,2\cdots,n\end{cases}\end{split}$$
   2. 数学模型的特征
      1. 运输问题必然存在有限最优解
      2. 运输问题约束条件的特点
         1. 约束条件矩阵的元素为 $0$ 或 $1$
         2. 约束矩阵每列仅有两个非零元素，这对应于每一个变量在前 $m$ 个约束中出现一次，后 $n$ 个约束中出现一次
         3. 对于产销平衡的运输问题
            1. 所有的约束均为等式
            2. 各产地产量之和等于各销地销量之和
      3. 运输问题的解
         1. 作为基可行解，其非零元素个数应该和线性独立的约束个数相等，即不大于 $m+n-1$ 个；为了使得迭代顺利进行，基变量的个数应该始终保持在 $m+n-1$ 个
   3. 原因 因为有以下关系式的存在，故模型最多只有 $m+n-1$ 个独立约束$$\sum_{i=1}^ma_{i} = \sum_{j=1}^nb_{j}$$
2. 写出运输问题数学模型的约束条件的系数矩阵，和其中变量 $x_{ij}$ 的系数列向量 $\boldsymbol{p}_{ij}$ 的表达式
   1. $\begin{pmatrix}1 & 1 &\cdots & 1 \\&&&&1&1&\cdots &1 \\ &&&&&&&&\ddots\\&&&&&&&&&1&1&\cdots&1\\1&&&&1&&&&&1 \\&1&&&&1&&&&&1\\&&\ddots&&&&\ddots&&&&&\ddots\\&&&1&&&&1&&&&&1\end{pmatrix}$
   2. $\boldsymbol{p}_{ij} = \begin{pmatrix}0 &\cdots &1&0&\cdots &0&1 & \cdots &0\end{pmatrix}=\boldsymbol{e}_{i}+\boldsymbol{e}_{m+j}$
3. 试述最小元素法确定运输问题的初始基可行解的基本思路和步骤
   1. 基本思路：就近供应，即从单位运价中最小的运价开始确定供销关系，然后次小。一直到给出初始可行基为止。
   2. 步骤
      1. 对所有的 $i$ 和 $j$，找出 $c_{i_0j_0}=\min\{c_{ij}\}$，并将 $x_{i_0j_0} = \min\{a_{i_0},b_{j_0}\}$ 的物品量由 $A_{i_0}$ 送往 $B_{j_0}$
      2. 若 $x_{i_0j_0} = a_{i_0}$，则产地 $A_{i_0}$ 的可供物品已经用完，以后不再考虑该产地，且 $B_{j_0}$ 的需求量由 $b_{j_0}$ 下降为 $b_{j_0} - a_{i_0}$；若 $x_{i_0j_0} = b_{i_0}$，则销地 $B_{j_0}$ 的需求已经满足，以后不再考虑该销地，且 $A_{i_0}$ 的可供物品量由 $a_{i_0}$ 下降为 $a_{i_0} - b_{j_0}$
      3. 然后在余下的供、销地的供销关系中，继续按照上述方法安排调运，直到安排完所有的供销任务，得到一个完整的调运方案为止。
4. 为什么用伏格尔法给出运输问题的初始基可行解，较之用最小元素法给出的更接近于最优解？
   1. 最小元素法的缺点 可能开始时节省一处的运费，但随后在其他处要多花几倍的运费；
   2. 伏格尔法考虑到，一产地的产品假如不能按最小运费就近供应，就考虑次小运费，这就有一个差额。差额越大，说明不能按最小运费调运时，运费增加的越多，因而对差额最大处，就应该采用最小运费调运。因此，伏格尔法的初始基可行解更接近于最优解。
5. 试述用闭回路法计算检验数的原理和经济意义。如何从任一空格出发去寻找一条闭回路？
   1. 原理及经济意义 在已有的基可行解的表中，从某一个空格出发，若让闭回路上同该空格相近的顶点调运$1$单位给该空格，则闭回路上的各顶点为了满足供销平衡，就会以此做出调整；根据该调整以及各闭回路上个定点的单位运输价格，即可计算出该空格出增加一运输量，所需要的运费；若运费存在负数，则说明该基可行解并非最优，可继续优化。
   2. 寻找方法 从空格出发，用水平或垂直线向前划，直到基变量所在的表格，可以考虑转向或继续直行，利用此规则可以构造出一条闭回路。
6. 试述用位势法求检验数的原理和步骤
   1. 原理
      1. 用 $u_1,\cdots,u_m$ 分别代表前 $m$ 个约束等式对应的对偶变量(行位势)； $v_1,\cdots,v_n$ 分别代表后 $n$ 个约束等式对应的对偶变量(列位势)；即有对偶变量$$\boldsymbol{Y}= \begin{pmatrix}u_1 &\cdots &u_m &v_1 &\cdots &v_n\end{pmatrix}$$
      2. 根据对偶问题的相关性质$$\begin{split}\sigma_{ij} & = c_{ij} - \boldsymbol{C_{B}B}^{-1}\boldsymbol{P}_{ij}\\&=c_{ij}-\boldsymbol{YP}_{ij}\\ & = c_{ij} - (u_{i}+v_j)\end{split}$$
      3. 由基变量的检验数为零可得到方程组$$\begin{split} & \begin{cases} c_{j_{1}j_{1}} = u_{i_{1}} + v_{j_{1}} \\ c_{j_{2}j_{2}} = u_{i_{2}} + v_{j_{2}} \\ \cdots \\ c_{j_{s}j_{s}} = u_{i_{s}} + v_{j_{s}} \\ \end{cases}\\ & x_{i_{k}j_{j}}\quad(k=1,2,\cdots,s)\text{ 为当前表的基变量} \end{split}$$
      4. 由$3.$计算得出的行位势和列位势以及$2.$提及的对偶问题的性质可以计算出所有空格的检验数
   2. 步骤
      1. 根据如下方程组，计算出各行和列的位势$$\begin{split}&\begin{cases}c_{i_{1}j_{1}} = u_{i_{1}}+v_{j_{1}}\\c_{i_{2}j_{2}} = u_{i_{2}}+v_{j_{2}}\\\cdots\\c_{i_{s}j_{s}} = u_{i_{s}}+v_{j_{s}} \\\end{cases}\\&x_{i_{k}j_{k}}\quad(k=1,2,\cdots,s)\text{ 为当前表的基变量}\end{split}$$
      2. 根据$\sigma_{ij} = c_{ij} - (u_i+v_j)$计算出各单元格的检验数
7. 试述表上作业法中出现退化的含义及处理退化的方法
   1. 含义 线性独立的约束数小于 $m+n-1$；存在以下两种情况：
   2. 处理方法
      1. 确定初始基可行解时：若在 $(i,j)$ 填入某数字后，出现 $A_i$ 处的余量等于 $B_j$ 处的需求量，即同时划去行和列；这时为了保证基变量数目为$m+n-1$，这时，可在其所在的行或列的任意一个单元格内填入 $0$
      2. 用闭回路法进行调整时：闭回路上出现两个和两个以上具有 $(-1)$ 标记的相等最小值。经过调整后出现退化解。这时，除有一个最小处变为空格外，其余的最小值所在单元格必须填入 $0$
8. 如何把一个产销不平衡的运输问题，转化为产销平衡的运输问题？
   1. 产大于销：增加一个虚拟销地 $B_{n+1}$，其需求量($b_{n+1}$)等于$\sum_{i=1}^ma_i-\sum_{j=1}^{n}b_{j}$，且送往其的运送费用为 $c_{i,n+1}=0$；
   2. 产小于销 增加一个虚拟产地 $A_{m+1}$，其产量($a_{m+1}$)等于 $\sum_{j=1}^{n}b_j - \sum_{i=1}^m a_i$，且从其送出的运输费用 $c_{m+1,j}=0$
9. 一般线性规划问题应具有什么特征才可以转化并列出运输问题的数学模型，并用表上作业法求解