Skip to content

AU4303 线性规划与非线性规划

章节 链接 源文件
Sec1 Sec1-介绍 Sec1-介绍
Sec2 Sec2-线性规划 Sec2-线性规划
Sec3 Sec3-对偶理论 Sec3-对偶理论
Sec4 Sec4-运输问题和指派问题 Sec4-运输问题和指派问题

Sec1-介绍

Sec2-线性规划

Sec3-对偶理论

Sec4-运输问题和指派问题

运输问题

代码实现：

  1. greedy 方法求出初始可行解。（PPT P19）
def greedy_method():
ap = np.copy(a)
bp = np.copy(b)
v = []
for i in range(n):
    for j in range(m):
        v.append((P[i][j], i, j))
v.sort()
for k in v:
    p, i, j = k
    if ap[i] > 0 and bp[j] > 0:
        sel = min(ap[i], bp[j])
        ap[i] -= sel
        bp[j] -= sel
        bfs[i][j] = 1
        T[i][j] = sel
  1. 计算检验数（PPT P23，还是需要解方程）
def calc_check_score():
# 计算检验数
u = np.zeros(n)
v = np.zeros(m)
A = np.zeros((n + m, n + m))
b = np.zeros(n + m)
cnt = 0
for i in range(n):
    for j in range(m):
        if bfs[i][j] == 1:
            A[cnt][i] = 1
            A[cnt][n + j] = 1
            b[cnt] = P[i][j]
            cnt += 1
A[cnt][0] = 1
b[cnt] = 0
sol = np.linalg.solve(A, b)
u = sol[:n]
v = sol[n:]
check_score = np.zeros((n, m))
for i in range(n):
    for j in range(m):
        check_score[i][j] = u[i] + v[j] - P[i][j]
return check_score
  1. 更新基（PPT P25）
def bfs_update(check_score):
# 选择 check_score 最大的点入基
max_score = -1e9
in_i, in_j = -1, -1
for i in range(n):
    for j in range(m):
        if check_score[i][j] > max_score:
            max_score = check_score[i][j]
            in_i, in_j = i, j
if max_score <= 0:
    return False
print("in", in_i, in_j)

bfs[in_i][in_j] = 1
A = np.zeros((n + m, n + m))
id = np.zeros((n, m))
cnt = 0
p = []
for i in range(n):
    for j in range(m):
        if bfs[i][j] == 1:
            id[i][j] = cnt
            if i == in_i and j == in_j:
                k0 = cnt
            p.append((i, j))
            cnt = cnt + 1
for i in range(n):
    for j in range(m):
        if (bfs[i][j]):
            A[i][(int)(id[i][j])] = 1
for j in range(m):
    for i in range(n):
        if (bfs[i][j]):
            A[j + n][(int)(id[i][j])] = 1
V = scipy.linalg.null_space(A)
V = V / V[k0]
V = -V
minn = 1e9
out_i, out_j = -1, -1
for k in range(cnt):
    i, j = p[k]
    if not (i == in_i and j == in_j) and V[k] > 0 and T[i][j] / V[k] < minn:
        minn = T[i][j] / V[k]
        out_i, out_j = i,j
print("out", out_i, out_j)
for k in range(cnt):
    i, j = p[k]
    T[i][j] -= minn * V[k]
bfs[out_i][out_j] = 0
return True
  • 其实问题也可以用最小费用最大流解决，扩展阅读：https://oi-wiki.org/graph/flow/min-cost/

指派问题

  • 其实问题也可以用二分图最大权匹配解决，扩展阅读：https://oi-wiki.org/graph/graph-matching/bigraph-weight-match/