18.1.4 特殊线性规划问题

18.1.4.1 运输问题

1. 建模

$m$ 个生产者 $E_1,\cdots ,E_m$ 生产一种产品,各家生产的数量是 $a_1,\cdots ,a_m$ ,产品需要运输到 $n$ 个消费者 $V_1,\cdots ,V_n$ ,其需求分别是 $b_1,\cdots ,b_n$ . 从生产者 $E_i$ 到消费者 $V_j$ 的单位运输成本是 $c_{ij}$ . 从 $E_i$ 到 $V_j$ 运输的产品数量是 $x_{ij}$ 件. 最优运输方案是使运输成本最小. 假定这个系统是平衡的, 即供给等于需求:

$$\begin{array}{}\text{(18.24)}& \sum _{i=1}^n{a}_i=\sum _{j=1}^n{b}_j\end{array}$$

首先构建成本矩阵 $\mathbf{C}$ 和分布矩阵 $\mathbf{X}$ 如下:

$$\begin{array}{}\text{(18.25a)}& \mathbf{C}=\left(\begin{array}{ccc}{c}_{1,1}& \cdots & c_{1,n}\\ ⋮& & ⋮\\ c_{m,1}& \cdots & c_{m,n}\end{array}\right)\begin{array}{c}E:\\ E_1\\ ⋮\\ E_m\end{array}\end{array}$$$$V:V_1\cdots V_n$$$$\sum :$$$$\begin{array}{}\text{(18.25b)}& \mathbf{X}=\left(\begin{array}{ccc}{x}_{1,1}& \cdots & x_{1,n}\\ ⋮& & ⋮\\ x_{m,1}& \cdots & x_{m,n}\end{array}\right)\begin{array}{c}{a}_1\\ ⋮\\ a_m\end{array}\end{array}$$$$\sum :b_1\cdots b_n$$

如果条件 (18.24) 不满足, 则需区分两种情形:

a) 如果 $\sum a_i>\sum b_j$ ,则引入虚构消费者 $V_{n+1}$ ,其需求为 $b_{n+1}=\sum a_i-\sum b_j$ , 运输成本为 $c_{i,n+1}=0$ .

b) 如果 $\sum a_i<\sum b_j$ ,则引入虚构生产者 $E_{m+1}$ ,其产能为 $a_{n+1}=\sum b_j-\sum a_i$ , 运输成本为 $c_{m+1,j}=0$ .

为了确定最优方案, 应该求解如下规划问题:

$$\begin{array}{}\text{(18.26a)}& \text{OF:}f\left(\mathbf{X}\right)=\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij}=min\text{!}\end{array}$$$$\text{CT:}\sum _{j=1}^n{x}_{ij}=a_i\left(i=1,\cdots ,m\right),$$$$\begin{array}{}\text{(18.26b)}& \sum _{i=1}^m{x}_{ij}=b_j\left(j=1,\cdots ,n\right),x_{ij}\ge 0.\end{array}$$

该问题的极小出现在可行集的某个顶点. 在 $m+n$ 个原始约束中有 $m+n-1$ 个线性无关的约束,从而在非退化情形下,解含有 $m+n-1$ 个正分量 $x_{ij}$ . 为了确定最优解, 使用下列所谓的运输算法.

2. 基本可行解的确定

使用西北角规则可以确定初始基本可行解:

a) 选择 $x_{11}=min\left\{a_1,b_1\right\}$ .(18.27a)

b) 如果 $a_1>b_1$ ,则删去 $\mathbf{X}$ 的第 1 列.(18.27b)

如果 $a_1<b_1$ ,则删去 $\mathbf{X}$ 的第 1 行.(18.27c)

如果 $a_1=b_1$ ,则或者删去 $\mathbf{X}$ 的第 1 行,或者删去 $\mathbf{X}$ 剩余的第 1 列.(18.27d)

如果只有一行而有几列, 则删去一列. 同样的的操作也适用于行.

c) $a_1$ 用 $a_1-x_{11}$ 替代, $b_1$ 用 $b_1-x_{11}$ 替代,并且对缩减了的分布矩阵 $\mathbf{X}$ 的左上角顶重复此操作.

在 a) 中得到的变量是基变量, 所有其余变量都是取零值的非基变量.

$$\mathbf{X}=\left(\begin{array}{llll}{x}_{1,1}& x_{1,2}& x_{1,3}& x_{1,4}\\ x_{2,1}& x_{2,2}& x_{2,3}& x_{2,4}\\ x_{3,1}& x_{3,2}& x_{3,3}& x_{3,4}\end{array}\right)\begin{array}{l}\sum :\\ a_1=9\\ a_2=10\\ a_3=3\end{array}$$$$\sum :b_1=4b_2=6b_3=5b_4=7$$

使用西北角规则确定初始极端点:

第 1 步 第 2 步

还有别的考虑运输成本方法也可以找出初始基本解 (例如见 [18.15] 中的沃格尔 (Vogel) 近似法), 并且通常会得到更好的初始解.

3. 采用单纯形法求解运输问题的解

如果采用通常的单纯形法求解运输问题, 则会产生含有大量零元的十分庞大的表 $\left(\left(m+n\right)\times \left(m\cdot n\right)\right)$ : 在每一列中仅有两个元等于 1. 于是就需要构造简化表,下面的步骤对应于单纯形步骤中仅涉及理论单纯形表的非零元. 成本数据矩阵包含目标函数的系数. 基变量在迭代过程中变换为非基变量, 而成本矩阵相应的元在每一步中都需要修改. 下面通过一个例子说明此方法.

a) 从成本矩阵 $\mathbf{C}$ 确定修改的成本矩阵 $\tilde{\mathbf{C}}$ :

$$\begin{array}{}\text{(18.28a)}& {\tilde{c}}_{ij}=c_{ij}{p}_i+q_j\left(i=1,\cdots ,m;j=1,\cdots ,n\right),\end{array}$$

这里要求

${\tilde{c}}_{ij}=0$ ,如果(i, j)对应的 $x_{ij}$ 是现时基变量.(18.28b)

$C$ 中对应于基变量的元打上标记,并以 $p_1=0$ 代入. 其余量 $p_i$ 和 $q_j$ 也称作潜在乘子或单纯形乘子,这些量的确定应该使得 $p_i,q_j$ 和带标记的成本 $c_{ij}$ 之和为零:

$$\mathbf{C}=\left(\begin{array}{cccc}\left(5\right)& \left(3\right)& 2& 7\\ 8& \left(2\right)& \left(1\right)& \left(1\right)\\ 0& 2& 6& \left(3\right)\end{array}\right)\begin{array}{l}{p}_1=0\\ p_2=1\\ p_3=-1\end{array}$$$$q_1=-5q_2=-3q_3=-2q_4=-2$$$$\begin{array}{}\text{(18.28c)}& \Rightarrow \tilde{\mathbf{C}}=\left(\begin{array}{cccc}0& 0& 0& 5\\ 4& 0& 0& 0\\ 3& -2& 3& 0\end{array}\right).\end{array}$$

b) 数值

$$\begin{array}{}\text{(18.28d)}& {\tilde{c}}_{pq}=\underset{i,j}{min}\left\{{\tilde{c}}_{ij}\right\}\end{array}$$

必须确定. 如果 ${\tilde{c}}_{pq}>0$ ,则分布 $\mathbf{X}$ 是最优的; 否则,就选 $x_{pq}$ 作为一新的基变量. 在我们的例子中, ${\tilde{c}}_{pq}={\tilde{c}}_{32}=-2$ .

c) 在 $\tilde{\mathbf{C}}$ 中,给 ${\tilde{c}}_{pq}$ 以及与基变量相关的成本项打上标记,如果 $\tilde{\mathbf{C}}$ 包含至多有一个标记元的行或列, 则删去这些行或列. 对剩余矩阵重复这一操作, 直到不再需要进一步的删除操作.

$$\begin{array}{}\text{(18.28e)}& \tilde{\mathbf{C}}=\left(\begin{array}{cccc}\left(0\right)& \left(0\right)& 0& 5\\ 4& \left(0\right)& \left(0\right)& \left(0\right)\\ 3& \left(-2\right)& 3& \left(0\right)\end{array}\right).\end{array}$$

d) 与剩下的带标记的元 ${\tilde{c}}_{ij}$ 相关的元 $x_{ij}$ 形成一个回路. 新的基变量 ${\tilde{x}}_{pq}$ 被调整到正值 $\delta$ . 与带标记元相关的其余变量 ${\tilde{c}}_{ij}$ 由约束确定. 在实践中,从回路第二元减去 $\delta$ ,或将 $\delta$ 加到回路第二元. 为了保持这些变量非负,量值 $\delta$ 必须选为

$$\begin{array}{}\text{(18.28f)}& \delta =x_{rs}=min\left\{x_{ij}:{\tilde{x}}_{ij}=x_{ij}-\delta \right\},\end{array}$$

其中 $x_{rs}$ 将是非基变量. 在这个例子中, $\delta =min\{1,3\}=1$ .

$$\begin{array}{}\text{(18.28g)}& \Rightarrow \tilde{\mathbf{X}}=\left(\begin{array}{llll}4& 5& & \\ & & 5& 5\\ & 1& & 2\end{array}\right),f\left(\underset{―}{x}\right)=53.\end{array}$$

然后,取 $\mathbf{X}=\tilde{\mathbf{X}}$ ,重复上述程序.

$$\mathbf{C}=\left(\begin{array}{cccc}\left(5\right)& \left(3\right)& 2& 7\\ 8& 2& \left(1\right)& \left(1\right)\\ 9& \left(2\right)& 6& \left(3\right)\end{array}\right)\begin{array}{l}{p}_1=0\\ p_2=3\\ p_3=1\end{array}$$$$q_1=-5q_2=-3q_3=-4q_4=-4$$$$\begin{array}{}\text{(18.28h)}& \Rightarrow \tilde{\mathbf{C}}=\left(\begin{array}{cccc}\left(0\right)& \left(0\right)& \left(-2\right)& 3\\ 6& 2& \left(0\right)& \left(0\right)\\ 5& \left(0\right)& 3& \left(0\right)\end{array}\right)\end{array}$$$$\tilde{\mathbf{X}}=\left(\begin{array}{ccccc}4& 5-\delta & \leftarrow & \delta & \\ & & & \uparrow & \\ \downarrow & & 5-\delta & \leftarrow & 5+\delta \\ & & & & \uparrow \\ 1+\delta & \to & & & 2-\delta \end{array}\right)$$$$\begin{array}{}\text{(18.28i)}& \stackrel{\delta =2}{\Rightarrow }\tilde{\mathbf{X}}=\left(\begin{array}{cccc}4& 3& 2& \\ & & 3& 7\\ & 3& & \end{array}\right),f\left(\mathbf{X}\right)=49.\end{array}$$

下一个矩阵 $\tilde{\mathbf{C}}$ 不包含任何负元,故 $\tilde{\mathbf{X}}$ 是最优解.

18.1.4.2 配置问题

通过一个例子说明问题.

现有 $n$ 份销售合同要分给 $n$ 个公司,使得每家公司恰好收到一份合同. 为此必须作出分配安排使得总成本最低,这里第 $i$ 个公司负担第 $j$ 个合同的费用是 $c_{ij}$ . 配置问题是一种特殊的运输问题,这里 $m=n,a_i=b_j=1,\mathrm{\forall }i,j$ :

$$\begin{array}{}\text{(18.29a)}& \text{OF:}f\left(\underset{―}{\mathbf{x}}\right)=\sum _{i=1}^n\sum _{j=1}^n{c}_{ij}{x}_{ij}=min\text{!}\end{array}$$$$\text{CT:}\sum _{j=1}^n{x}_{ij}=1\left(i=1,\cdots ,n\right)\text{,}$$$$\begin{array}{}\text{(18.29b)}& \sum _{i=1}^n{x}_{ij}=1\left(j=1,\cdots ,n\right),x_{ij}\in \{0,1\}.\end{array}$$

每个可行分布矩阵在其每一行和每一列恰有一个 1 , 所有其余元均为零. 然而在这样维度的一般运输问题中,一个非退化基本解会有 $2n-1$ 个正变量. 因此,该分配问题的基本可行解是高度退化的,具有 $n-1$ 个等于零的基变量. 从可行分布矩阵 $\mathbf{X}$ 出发,分配问题可以借助一般的运输算法求解. 这样做是非常耗时的. 但是,由于基本可行解的高度退化特征, 配置问题可以通过非常有效的匈牙利(Hungarian) 方法求解 (见 [18.11]).

18.1.4.3 分配问题

同样通过一个例子来说明问题.

$m$ 个产品 $E_1,\cdots ,E_m$ 需要生产数量分别为 $a_1,\cdots ,a_m$ . 每一种产品可以在 $n$ 台机器 $M_1,\cdots ,M_n$ 的任一台上生产. 在机器 $M_j$ 上生产一件产品 $E_i$ 需要耗时 $b_{ij}$ 和成本 $c_{ij}$ . 机器 ${}_j$ 的时间容量是 $b_j$ . 用 $x_{ij}$ 表示机器 $M_j$ 生产产品 $E_i$ 的数量. 总的生产成本应该达到最小. 这个分配问题的一般模型如下:

$$\begin{array}{}\text{(18.30a)}& \text{OF:}f\left(\underset{―}{\mathbf{x}}\right)=\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij}=min\text{!}\end{array}$$$$\text{CT:}\sum _{j=1}^m{x}_{ij}=a_i\left(i=1,\cdots ,m\right)\text{,}$$$$\begin{array}{}\text{(18.30b)}& \sum _{i=1}^n{b}_{ij}{x}_{ij}\le b_j\left(j=1,\cdots ,n\right),x_{ij}\ge 0,\mathrm{\forall }i,j.\end{array}$$

分配问题是运输问题的推广,它可以用单纯形法求解. 如果所有 $b_{ij}=1$ ,则可以在引入虚构产品 $E_{m+1}$ (参见第 1194 页 18.1.4.1) 后使用更有效的运输算法 (参见第 1195 页 18.1.4.1).

18.1.4.4 游路问题

假定有 $n$ 个地方 $O_1,\cdots ,O_n$ . 从 $O_i$ 到 $O_j$ 的旅行时间是 $c_{ij}$ . 这里 $c_{ij}\ne c_{ji}$ 是可能的. 现在要确定游客恰好一次通过每个地方并最终返回出发点所需要的最短旅程.

与配置问题相类似,在时间矩阵 $C$ 的每行每列中恰好选择一个元,使得所选元之和最小. 数值求解这个问题的难点在于带标记元需要按照如下方式排序:

$$\begin{array}{}\text{(18.31)}& c_{i_1,i_2},c_{i_2,i_3},\cdots ,c_{i_n,i_{n+1}}\text{,这里}i\ne j\text{时}{i}_k\ne i_j\text{,并且}{i}_{n+1}=i_1\text{.}\end{array}$$

游路问题可以用分枝法和限界法求解.

18.1.4.5 调度问题

$n$ 种不同产品在 $m$ 台不同的机器上按照相关产品订单进行加工. 在任何时间只能有一种产品在一台机器上加工. 每种产品在每台机器上的加工时间假定是已知的. 一种给定产品不在加工过程而处于等待加工, 以及机器出现空闲都有可能.

要求确定加工作业的最优调度, 这里目标函数选择为全部加工完成的时间, 或者加工作业中总的等待时间, 或者总的机器闲置时间. 在无等待时间或闲置时间的情形下, 往往选择完成全部加工时间之和作为目标函数.