一个原始的指派问题：有n个工人，和n个需要作业的地点。需要为每个工人安排一个工作的地点，记变量
x
i
j
=
0
o
r
1
x_{ij}=0 or 1
xij=0 or 1，代表派第i个工人去第j个地点的情况（0代表不指派，1代表指派）。同时将第i个工人派去第j个地点存在一定的开销，记录为
c
i
j
c_{ij}
cij。公司要求最小化开销，那么这个原始指派问题的数学描述是：
min
∑
i
=
1
n
∑
j
=
1
n
c
i
j
x
i
j
s
.
t
.
∑
j
=
1
n
x
i
j
=
1
∑
i
=
1
n
x
i
j
=
1
x
i
j
∈
{
0
,
1
}
min sum_{i=1}^nsum_{j=1}^n c_{ij}x_{ij}\ s.t. sum_{j=1}^n x_{ij}=1\ sum_{i=1}^n x_{ij}=1\ x_{ij}in{0,1}
mini=1∑nj=1∑ncijxijs.t.j=1∑nxij=1i=1∑nxij=1xij∈{0,1}
将
c
i
j
c_{ij}
cij写成矩阵
C
C
C
举例：
C
=
[
14
5
8
7
2
12
6
5
7
8
3
9
2
4
6
10
]
C = left[begin{matrix} 14& 5& 8&7\ 2& 12& 6&5\ 7& 8& 3& 9\ 2& 4& 6& 10 end{matrix}right]
C=⎣⎢⎢⎡1427251284863675910⎦⎥⎥⎤
- C C C的每一行减去该行的最小值。
- 第一步做差得到的矩阵再减去每列的最小值，得到矩阵 R R R。
这时候：
R
=
[
9
0
3
0
0
10
4
1
4
5
0
4
0
2
4
6
]
R = left[begin{matrix} 9& 0& 3&0\ 0& 10& 4&1\ 4& 5& 0& 4\ 0& 2& 4& 6 end{matrix}right]
R=⎣⎢⎢⎡90400105234040146⎦⎥⎥⎤
-
找到横线或者竖线用来覆盖 R R R中的0元素，并且使得用的线的数量最少
-
如果使用的线条数量刚好是n条（例子中n=4），那么已经求解得到一个最优解。只要在 R R R中选n个0元素，并且这n个元素互相不同行不同列，再使这n个元素对应 x i j x_{ij} xij为1，其余 x i j x_ij xij为0。
-
若线条的数量小于n条，那么就选择线条没覆盖的数字中的最小值 δ delta δ，使没被覆盖的数字所在行中的 R R R的元素全部减去 δ delta δ，再使被线条覆盖的列元素全部加上 δ delta δ。然后返回第三步。
画线后：
此时返回第三步，已经可以找到最少4条线覆盖所有0元素，那么可以得到一个最优解是 x 12 , x 24 , x 32 , x 41 = 1 x_{12},x_{24},x_{32},x_{41} =1 x12,x24,x32,x41=1。
采用对偶观点原始问题
min
∑
i
=
1
n
∑
j
=
1
n
c
i
j
x
i
j
s
.
t
.
∑
j
=
1
n
x
i
j
=
1
∑
i
=
1
n
x
i
j
=
1
x
i
j
∈
{
0
,
1
}
min sum_{i=1}^nsum_{j=1}^n c_{ij}x_{ij}\ s.t. sum_{j=1}^n x_{ij}=1\ sum_{i=1}^n x_{ij}=1\ x_{ij}in{0,1}
mini=1∑nj=1∑ncijxijs.t.j=1∑nxij=1i=1∑nxij=1xij∈{0,1}
为 C C C相关的约束，每行选择一个对偶变量 u i u_i ui，每列选择一个对偶变量 v j v_j vj。
对偶问题则可以写成：
max
(
∑
i
=
1
n
u
i
+
∑
j
=
1
n
v
j
)
s
.
t
.
u
i
+
v
j
≤
c
i
j
∀
(
i
,
j
)
max (sum_{i=1}^nu_i+sum_{j=1}^nv_j)\ s.t. u_i+v_jle c_{ij} forall(i,j)
max(i=1∑nui+j=1∑nvj)s.t. ui+vj≤cij ∀(i,j)
从对偶问题出发要找到最优解，则需要满足三个条件：
(a) u i , v j u_i,v_j ui,vj 对于对偶问题是可行的，对偶可行性。(b) 对偶问题中每个取“=”的约束对应的原始变量 x i j = 0 x_{ij}=0 xij=0，互补松弛性。( c) u i , v j u_i,v_j ui,vj 对应的原始问题的解 x i j x_{ij} xij是可行的，原始可行性。
表上求解的方法等价于，满足(a),(b)的条件，不断通过迭代调整使得(c )得到满足。
- C C C的每一行减去该行的最小值。
- 第一步做差得到的矩阵再减去每列的最小值，得到矩阵 R R R。
步骤1，2等价于确定一个初始对偶可行解 u i = min j c i j , v j = min i ( c i j − u i ) u_i = min_j c_{ij}, v_j =min_i(c_{ij}-u_i) ui=minjcij, vj=mini(cij−ui)。
这个初始对偶解满足对偶可行，原因是矩阵 R R R中的每个元素 R i j = c i j − u i − v j ≥ 0 R_{ij}=c_{ij}-u_i-v_j ge 0 Rij=cij−ui−vj≥0。即对偶问题约束 u i + v j + R i j = c i j u_i+v_j+R_{ij}=c_{ij} ui+vj+Rij=cij的松弛变量构成了矩阵 R R R。
对应上述例子中的第一次迭代中：
u
=
[
5
,
2
,
3
,
2
]
T
v
=
[
0
,
0
,
0
,
2
]
T
R
=
[
9
0
3
0
0
10
4
1
4
5
0
4
0
2
4
6
]
u=[5, 2, 3, 2]^Tqquad v=[0,0,0,2]^T\ R = left[begin{matrix} 9& 0& 3&0\ 0& 10& 4&1\ 4& 5& 0& 4\ 0& 2& 4& 6 end{matrix}right]
u=[5,2,3,2]Tv=[0,0,0,2]TR=⎣⎢⎢⎡90400105234040146⎦⎥⎥⎤
矩阵中的0元素对应的对偶问题的约束取"="，由（b）条件的互补松弛性满足可以得到对应原始问题的解 x i j = 0 , i f R i j = 0 x_{ij}=0,if R_{ij}=0 xij=0,if Rij=0。
这时条件(a)和(b)满足了，需要检验条件( c)是否满足。检验条件(c )即对应步骤3。
- 找到横线或者竖线用来覆盖 R R R中的0元素，并且使得用的线的数量最少
如果线条的数量小于n条，那么原问题不可行，否则原问题可行且找到最优解。
对于
R
=
[
9
0
3
0
0
10
4
1
4
5
0
4
0
2
4
6
]
R = left[begin{matrix}9& 0& 3&0\0& 10& 4&1\4& 5& 0& 4\0& 2& 4& 6end{matrix}right]
R=⎣⎢⎢⎡90400105234040146⎦⎥⎥⎤，对应的原问题的解不可行。那么对偶可行解需要进行调整，列出DRP问题（Dual Restriced Primal）以求得调整方向：
max
(
∑
i
=
1
n
Δ
u
i
+
∑
j
=
1
n
Δ
v
j
)
s
.
t
.
Δ
u
i
+
Δ
v
j
≤
0
∀
(
i
,
j
)
∈
{
(
i
,
j
)
∣
R
i
j
=
0
}
Δ
u
i
,
Δ
v
j
≤
1
max (sum_{i=1}^nDelta u_i+sum_{j=1}^nDelta v_j)\ s.t. Delta u_i+Delta v_jle 0 forall(i,j)in{(i,j)|R_{ij}=0}\ Delta u_i,Delta v_jle1
max(i=1∑nΔui+j=1∑nΔvj)s.t. Δui+Δvj≤0 ∀(i,j)∈{(i,j)∣Rij=0}Δui,Δvj≤1
例子中为:
max
(
∑
i
=
1
4
Δ
u
i
+
∑
j
=
1
4
Δ
v
j
)
s
.
t
.
Δ
u
1
+
Δ
v
2
≤
0
Δ
u
1
+
Δ
v
4
≤
0
Δ
u
2
+
Δ
v
1
≤
0
Δ
u
3
+
Δ
v
3
≤
0
Δ
u
4
+
Δ
v
1
≤
0
Δ
u
i
,
Δ
v
j
≤
1
max (sum_{i=1}^4Delta u_i+sum_{j=1}^4Delta v_j)\ s.t.Delta u_1+Delta v_2le0\ Delta u_1+Delta v_4le0\ Delta u_2+Delta v_1le0\ Delta u_3+Delta v_3le0\ Delta u_4+Delta v_1le0\ Delta u_i,Delta v_jle1
max(i=1∑4Δui+j=1∑4Δvj)s.t.Δ u1+Δv2≤0Δu1+Δv4≤0Δu2+Δv1≤0Δu3+Δv3≤0Δu4+Δv1≤0Δui,Δvj≤1
求解得到一个解
Δ
u
=
[
−
1
,
0
,
0
,
0
]
T
,
Δ
v
=
[
0
,
1
,
0
,
1
]
T
Delta u=[-1,0,0,0]^T,Delta v=[0,1,0,1]^T
Δu=[−1,0,0,0]T,Δv=[0,1,0,1]T
更新对偶问题的可行解为 [ u , v ] = [ u , v ] + [ Δ u , Δ v ] [u,v]=[u,v]+[Delta u,Delta v] [u,v]=[u,v]+[Δu,Δv]即可在保证对偶可行性的条件下，优化原始可行性条件。
例子中
u
n
e
w
=
u
+
Δ
u
=
[
4
,
2
,
3
,
2
]
T
,
v
n
e
w
=
v
+
Δ
v
=
[
0
,
1
,
0
,
3
]
T
u_{new} = u+Delta u =[4,2,3,2]^T,v_{new} = v+Delta v =[0,1,0,3]^T
unew=u+Δu=[4,2,3,2]T,vnew=v+Δv=[0,1,0,3]T，新的对偶可行解对应的新松弛变量矩阵为：
R
n
e
w
=
[
10
0
4
0
0
9
4
0
4
4
0
3
0
1
4
5
]
，
R
n
e
w
i
j
=
c
i
j
−
u
n
e
w
i
−
v
n
e
w
j
R_{new}=left[begin{matrix} 10& 0& 4&0\ 0& 9& 4&0\ 4& 4& 0& 3\ 0& 1& 4& 5end{matrix}right]，R_{new_{ij}}=c_{ij}-u_{new_i}-v_{new_j}
Rnew=⎣⎢⎢⎡10040094144040035⎦⎥⎥⎤，Rnewij=cij−unewi−vnewj
与执行步骤5“若线条的数量小于n条，那么就选择线条没覆盖的数字中的最小值
δ
delta
δ，使没被覆盖的数字所在行中的
R
R
R的元素全部减去
δ
delta
δ，再使被线条覆盖的列元素全部加上
δ
delta
δ。然后返回第三步。”后得到的结果一致。
对例子而言此时已经最优。
需要注意的是，步骤3和步骤5对应了对偶观点中求解DRP问题的过程：（i）步骤5中的矩阵变换做法可以保证 R R R矩阵中所有元素非负，并且矩阵的每行每列中至少存在一个0元素，这同时也保证了对应对偶解的可行性。（ii）在DRP求解过程中得到的解和划线方式有严格对应关系，例子中 Δ u i = − 1 Delta u_i=-1 Δui=−1表示第i行被横线划去， Δ v j = 0 Delta v_j=0 Δvj=0表示第j列被竖线划去。（iii）步骤5中，对矩阵的调整会使得下一步迭代中 u n e w = u + Δ u , v n e w = v + Δ v u_{new} = u+Delta u,v_{new} = v+Delta v unew=u+Δu,vnew=v+Δv。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）