运筹学 / 习题/考试 / 作业 / 2

定义变量 $x_{ij}=\begin{cases} 1, & \text{路径中包含从\ } v_i\text{\ 到\ } v_j \text{\ 的边}\\ 0, & \text{不包含} \end{cases}$

那么我们的目标函数就是 $\min \sum\limits_{i,j=0}^n c_{ij}x_{ij}$.

接着考虑约束条件, 由于要用一条路径覆盖, 所以每个点只会有一个入边即 $\sum\limits_{i=0}^n x_{ij}=1$. 也只会有一条出边 $\sum\limits_{j=0}^nx_{ij}=1$.

但仍要保证路径是一条, 考虑加入辅助变量 $u_i, i=1,2,\ldots, n$, 只需满足 $u_i-u_j+x_{ij}(n)\leqslant n-1, i,j=1,2,\ldots,n$.

因为当 $1\sim n$ 中存在子连通图, 那么一定存在一个子环, 设大小, 而将这个环上的边 $(i,j)$ 对应的式子取出, 那么相加后所有的 $u_i,u_j$ 抵消, 左侧为 $kn$, 右侧为 $k(n-1)$ 显然不成立.

所以该限制确保了不存在子环. 而当只有一条路径时, 只需取 $u_i$ 表示第 i 个点的顺序即可保证所有等式成立, 因为此时 $1\leqslant u_i\leqslant n$, $u_i-u_j\leqslant n-1$ 成立.

故满足上述限制的解一定构成一条符合要求的路径. 汇总后可将模型写成.

$$\begin{cases} \min & z=\sum\limits_{i,j=0}^n c_{ij}x_{ij} &\\ \text{s.t.} & \sum\limits_{i=0}^{n}x_{ij}=1, & j=0,\ldots,n\\ & \sum\limits_{j=0}^n x_{ij}=1, & i=0,\ldots,n\\ & u_i-u_j+nx_{ij}\leqslant n-1, & 1\leqslant i,j \leqslant n. \\ & x_{ij}\in \{0,1\}, & i,j=0,\ldots,n\\ & u_i\in \mathbb{R} & i=1,\ldots,n \end{cases}$$

将 $A-K$ 对应到 $1-11$.

题目中的符号表示 $t_{ij}$ 表示第 $i$ 个任务在 $j$ 工作站上的耗时, 具体值见上表.

$P_i$ 表示任务 $i$ 的直接前序依赖任务集合, 例如 $P_{3}=\{2\}$.

$M$ 为充分大的常数.

决策变量:

$x_i\in\{0,1\}$: 表示任务 $i$ 是否分配给工作站 $1$, $1$ 表示是, $0$ 表示否 ($i=1,\ldots,11$).

$S_i$ 表示任务 $i$ 的开工时间 ($i=1,\ldots,11$).

$y_{ij}\in\{0,1\}$ 表示任务 $i$ 是否在任务 $j$ 之前完成 ($i\neq j$).

为了方便, 先推导每个任务的结束时间记作 $C_i=S_i+x_it_{i1}+(1-x_i)t_{i2}$ 用 $x_i$ 控制在哪个工作站上.

目标函数:

$f=\min C_{11}$.

约束条件:

第一类是依赖关系, 即对于每个任务 $i$, 要求 $C_j\leqslant S_i,\forall j\in P_i$.

第二类是单个工作站上任务不重叠, 那么考虑先限定 $y_{ij}+y_{ji}=1$.

然后当 $x_i=x_j$ 时要求根据 $y_{ij}$ 的取值判断 $i,j$ 的先后顺序.

可以构建下面的条件

$$\begin{cases} C_i\leqslant S_j+M(y_{ji}+2-x_i-x_j)\\ C_i\leqslant S_j+M(y_{ji}+x_i+x_j) \end{cases}$$

不难验证, 当 $x_i\neq x_j$ 时, 上述两个限制肯定成立. 而当 $x_i=x_j$ 时, 上述限制具有约束力, 仅当 $y_{ji}=0$, 即 $y_{ij}=1$. 此时要求 $i$ 在 $j$ 之前完成, 即 $C_i\leqslant S_j$. 满足定义.

所以只需对 $i\neq j$ 上述两条约束成立即可满足在单个工作站上不重叠.

综上, 汇总可得总的运筹模型可建立为

$$\begin{cases} \min & C_{11} & \\ \text{s.t.} & C_j\leqslant S_i & \forall j\in P_i, i=1,2,\ldots,11\\ & y_{ij}+y_{ji}=1 & 1\leqslant i\neq j\leqslant 11\\ & C_i\leqslant S_j+M(y_{ji}+2-x_i-x_j) & 1\leqslant i\neq j \leqslant 11 \\ & C_i\leqslant S_j+M(y_{ji}+x_i+x_j) & 1\leqslant i\neq j \leqslant 11\\ & x_{ij}\in \{0,1\} & 1\leqslant i\neq j\leqslant 11\\ & y_{ij}\in \{0,1\} & 1\leqslant i\neq j\leqslant 11\\ & C_i=S_i+x_i t_{i1}+(1-x_i)t_{i2} & i=1,\ldots,11\\ & S_i\geqslant 0 & i=1,\ldots,11 \end{cases}$$

下面是一组我得到的最优解, 并且分类讨论 A 一开始在 1,还是 2 可以证明该方案已经达到下界.

先简要证明.

如果 A 在工作站 1, 那么只考虑 A,B,C,F,G,J,K 这些任务, A 25h, B 最早 30h, C 最早 34h, F,G 最早 41h (F1G2), 再 J,K 依次完成最早要 47h.

如果 A 在工作站 2, 那么 D 最早在 35h 完成, E 最早 40h, H,I 最早 45h, 再 J,K 依次完成最早要 51h.

注意上述两种假设都忽略了部分任务以考虑最优, 所以实际必定不低于上述考虑, 所以总时间至少为 47h.

下面给出恰好为 47h 的方案.

在工作站 1 上依次完成 A,B,I,F.

在工作站 2 上依次完成 D,E,H,C,G,J,K.

几个重要的时间点,

$0\sim25h$ 工作站 1 完成 A, 工作站 2 完成 D,E,H.

$25\sim30h$ 工作站 1 完成 B, 工作站 2 等待.

$30\sim34h$ 工作站 1 完成 I, 工作站 2 完成 C.

$34\sim41h$ 工作站 1 完成 F, 工作站 2 完成 G.

接下来 6h 依次完成 J,K. 在 47h 时完成所有任务. 达到理论下界. 所以已经是最优解.