运筹学：第 2 次作业

Homework 2 #

Question 1: #

有一推销员, 从城市 $v_0$ 出发, 要依次访问城市 $v_1, v_2, \dots, v_n$ 各一次, 最后返回到 $v_0$ . 已知从 $v_i$ 到 $v_j$ 的旅费为 $c_{ij}$ , 对于任意的 $v_i$ 和 $v_j$ , 问他应按怎样的次序访问这些城市, 使得总旅费最小?

答案

定义变量 $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$ .

还需排除不经过仓库 $v_0$ 的子环。引入顺序变量 $u_i$ （ $i=1,2,\ldots,n$ ），并对非仓库节点加入 MTZ 约束。若这些节点中存在大小为 $k$ 的子环，将环上对应不等式相加后，顺序变量相互抵消，得到 $kn\leqslant k(n-1)$ ，矛盾。因此该约束能够排除子环。

当解只包含一条经过全部城市的回路时，可令 $u_i$ 表示城市 $v_i$ 在访问序列中的位置。完整模型为

\begin{aligned} \min\quad & z=\sum_{i=0}^{n}\sum_{\substack{j=0\\j\ne i}}^{n} c_{ij}x_{ij} \\ \text{s.t.}\quad & \sum_{\substack{i=0\\i\ne j}}^{n}x_{ij}=1, && j=0,\ldots,n,\\ & \sum_{\substack{j=0\\j\ne i}}^{n}x_{ij}=1, && i=0,\ldots,n,\\ & u_i-u_j+nx_{ij}\leqslant n-1, && i,j=1,\ldots,n,\ i\ne j,\\ & x_{ij}\in\{0,1\}, && i,j=0,\ldots,n,\ i\ne j,\\ & 1\leqslant u_i\leqslant n, && i=1,\ldots,n. \end{aligned}

Question 2: #

需要将 11 件加工任务 (A-K) 分配到两个工作站, 任务需要依次经过工作站 1, 2 以完成加工. 任务间的依赖关系如下图 (后续节点任务的启动需要前序任务完成), 每件任务在工作站所花费的时间如下表:

每件任务在两个工作站上所需时间如下表 (单位: 小时):

任务	A	B	C	D	E	F	G	H	I	J	K
工作站 1（小时）	25	5	5	35	10	7	8	7	2	4	7
工作站 2（小时）	20	6	4	15	5	5	4	5	10	4	2

题意说明： 当前题面“依次经过工作站 1、2”与下文采用的“每项任务在两站中择一分配”并不一致。以下保留原解答采用的后一种模型，待核对完整题面后再定稿。

设计装配任务分配方案, 目标是为工作站分配加工任务, 尽可能使总装配时间最短.

答案

将 $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_i\in \{0,1\} & i=1,\ldots,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\sim32h$ 工作站 1 完成 I，随后空闲等待；工作站 2 在 $30\sim34h$ 完成 C。

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

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

Homework 2 #

Question 1: #

Question 2: #

评论