例题6.11
例题6.11代码
import cvxpy as cp
import networkx as nx
import numpy as np
Adjt = [(1,2,18),(1,5,15),(2,3,20),(2,4,60),(2,5,12),
(3,4,30),(3,5,18),(4,6,10),(5,6,15)]
W = np.ones((6,6))*1e4 #邻接矩阵初始化
for i in range(len(Adjt)):
W[Adjt[i][0]-1, Adjt[i][1]-1] = Adjt[i][2]
W[Adjt[i][1]-1, Adjt[i][0]-1] = Adjt[i][2]
origin, target = 1, 3
x = cp.Variable((6,6), boolean=True)
obj = cp.Minimize(cp.sum(cp.multiply(W, x)))
cons = [
cp.sum(x[origin, :]) == 1,
cp.sum(x[:, origin]) == 0,
cp.sum(x[:, target]) == 1,
]
other_nodes = set(range(len(W))) - set([origin, target])
for i in other_nodes:
cons.append(cp.sum(x[i, :]) == cp.sum(x[:, i]))
prob = cp.Problem(obj, cons)
prob.solve(solver='GLPK_MI')
print(f'最优解为：\n{x.value}'); print(f'最优值为：{prob.value}')
start, end = np.nonzero(x.value)
print("\n起点：", start + 1); print("终点：", end + 1)
