• 最短路径问题 什么是最短路径问题 最短路径问题和线性规划间的关系 Python调用Gurobi求解最短路径问题 Dijkstra’s Algorithm Dijkstra’s Algorithm 证明 Dijkstra’s Algorithm 实现
Shortest Path Problem
Problem Formulation
Definition1.1  $G=\langle V, E, h\rangle$ is a weighted graph where the graph $G=\langle V, E\rangle$ is equipped with a positive cost function $h$ defined on all edges in $E$.
Definition1.2 Fix a weighted graph $G=\langle V, E, h\rangle$ and $O \in V$ the origin,  $T \in V$ the termination. The shortest-path problem for $G$ is defined by looking for a path $x_{0} x_{1}-x_{1} x_{2}-x_{N-1} x_{N}$ with$x_{0} =O$ and $x_{N}=T$ such that the total cost$\sum_{t=1}^{N} h\left(x_{t-1} x_{t}\right)$is minimized sum.
Relationship with Mathematical Programming

Note:
Explanation for the first constraint: Only need to find the shortest path from original to destination, and do not need to go through every vertices in the graph(while TSP needs).
Using Python with package ‘Gurobi’ to solve the shortest path problem
Here is an example.

$\begin{array}{ll}\min & \sum_{(i, j) \in A} x_{i j} d_{i j} \\ & \sum_{(0, j) \in A} x_{0 j}=1 \\ & \sum_{(j, t) \in A} x_{j t}=1 \\ & \sum_{(i, j) \in A} x_{i j}-\sum_{(j, k) \in A} x_{j k}=0 \quad \forall j \in V \backslash\{O, T\} \\ & x_{i j} \in\{0,1\}, \quad \forall(i, j) \in A\end{array}$
from gurobi import *
import pandas as pd
import numpy as np

Nodes = ['O','A','B','C','D','E','T']
Arcs = {
('O','A'):2,
('O','B'):5,
('O','C'):4,
('A','B'):2,
('A','D'):7,
('B','C'):1,
('B','D'):4,
('B','E'):3,
('C','E'):4,
('D','E'):1,
('D','T'):5,
('E','T'):7
}

model = Model('Shortest Path Problem')
X = {}
for key in Arcs.keys():
index = 'x_' + key[0] + ',' + key[1]
X[key] = model.addVar(vtype = GRB.BINARY,name = index)
obj = LinExpr(0)
for key in Arcs.keys():
model.setObjective(obj,GRB.MINIMIZE)

# constraint1 1 and constraint 2
lhs_1 = LinExpr(0)
lhs_2 = LinExpr(0)
for key in Arcs.keys():
if(key[0] == 'O'):
elif(key[1] == 'T'):
model.addConstr(lhs_1 == 1, name = 'Original flow')
model.addConstr(lhs_2 == 1, name = 'Termination flow')

# constraints 3
for node in Nodes:
lhs = LinExpr(0)
if(node != 'O' and node != 'T'):
for key in Arcs.keys():
if(key[1] == node):
elif(key[0] == node):
model.addConstr(lhs == 0, name = 'flow conservation')

model.write('model_spp.lp')
model.optimize()
print(model.ObjVal)
for var in model.getVars():
if(var.x>0):
print(var.varName,'\t', var.x)

Warning: constraint name "Original flow" has a space
Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (mac64)
Optimize a model with 9 rows, 12 columns and 24 nonzeros
Model fingerprint: 0x988b6d83
Variable types: 0 continuous, 12 integer (12 binary)
Coefficient statistics:
Matrix range     [1e+00, 1e+00]
Objective range  [1e+00, 7e+00]
Bounds range     [1e+00, 1e+00]
RHS range        [1e+00, 1e+00]
Found heuristic solution: objective 15.0000000
Presolve removed 9 rows and 12 columns
Presolve time: 0.00s
Presolve: All rows and columns removed

Explored 0 nodes (0 simplex iterations) in 0.01 seconds
Thread count was 1 (of 8 available processors)

Solution count 2: 13

Optimal solution found (tolerance 1.00e-04)
Best objective 1.300000000000e+01, best bound 1.300000000000e+01, gap 0.0000%
13.0
x_O,A 	 1.0
x_A,B 	 1.0
x_B,D 	 1.0
x_D,T 	 1.0

Dijkstra’s Algorithm

Proof of Dijkstra’s Algorithm
Optimality of Dijkstra’s algorithm:
once a node $i^{*}$ joins $P$ , its updated value $L\left(i^{*}\right)$ is the shortest path$\left(W^{*}\right)$ distance. Dijkstra’s algorithm assigns distance labels (from node s) to all other nodes in the graph. Node labels are either temporary or permanent. Initially all nodes have temporary labels. At any iteration, a node with the least distance label is marked as permanent, and the distances to its successors are updated. This is continued until no temporary nodes are left in the graph.Then we prove the optimality of Dijkstra’s algorithm, that is, once a node $i^{*}$ joins $P$ , its updated value $L(i^{*})$is the shortest path $W^{*}$ distance. Note that $T$ is the set of vertices, $T=V/P$, $j_{1}$ is the first point of sub path.Note that $T$ is the set of vertices, $T=V/P$.
$j_{1}$ is the first point of sub path.

Dijkstra’s Algorithm Implementation
import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
import copy
import re
import math

Nodes = ['O','A','B','C','D','E','T']
Arcs = {
('O','A'):2,
('O','B'):5,
('O','C'):4,
('A','B'):2,
('A','D'):7,
('B','C'):1,
('B','D'):4,
('B','E'):3,
('C','E'):4,
('D','E'):1,
('D','T'):5,
('E','T'):7
}

Graph = nx.DiGraph()
# print(Graph.nodes)

for node in Nodes:
for key in Arcs.keys():

def Dijkstra(Graph , org ,des):
Q = list(Graph.nodes())  #Q=V/P，the points excluding pionts in P
for node in Q:
#Initialization: Graph.nodes[org]['min_dis']=0, else: infinity
if (node == org) :
Graph.nodes[node]['min_dis']=0
else:
Graph.nodes[node]['min_dis'] =np.inf
current_node = org

while (len(Q)>0):
min_dis =np.inf
# Main parts of the algorithm, select k in Q=V/P, with the smallest L'(k) for all points
for node in Q:
if (Graph.nodes[node]['min_dis']<min_dis):
current_node =node
min_dis=Graph.nodes[node]['min_dis']
#current_node can be destination，thus holds no current_node
# Once find the smallest k^{*}, we remove it until no more points should be added to approach termination
if (current_node !=None):
Q.remove(current_node)
#Main parts of the algorithm, update the L'(k) for all point in connected with current_node
# graph.successsors： fined the point connected with current_node
for child in Graph.successors(current_node):
arc = (current_node, child)
#update the  L'(k) for k in Q=V/P
dis_temp = Graph.nodes[current_node]['min_dis']+Graph.edges[arc]['length']
if (dis_temp< Graph.nodes[child]['min_dis']):
# If there are k which have the same L'(k), we use the former.
Graph.nodes[child]['min_dis']= dis_temp
#useful for generate shortest path, current-previous
Graph.nodes[child]['previous_node'] = current_node
#des is the termination, and min_dis is the distance of the whole SP.
min_dis = Graph.nodes[des]['min_dis']
current_node = des
#use list to record the path.
shortest_path =[current_node]
#generate shortest path
while (current_node != org):
current_node=Graph.nodes[current_node]['previous_node']
# add current_node(nodes[current_node]['previous_node']) with index 0 in the list
shortest_path.insert(0,current_node)
return Graph, shortest_path, min_dis

org ='O'
des= 'T'
print(Dijkstra(Graph,org,des))

Author: Pengxiang Zhou, Tsinghua University, Tsinghua Berkeley Shenzhen College (PhD candidate)

The content of this courseware is from the course “Operations Research”, taught by Li Xiaoxi, department of Mathematical Economics and Mathematical Finance, School of Economics and Management, Wuhan University. \
Dijkstra’s Algorithm Implementation refer to https://blog.csdn.net/zaowuyingshu/article/details/110590947

Welcome to follow the public account


展开全文
• % *lpint (BranchBound)- 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数规划(在MATLAB5.3使用) % *bnbgui - 非线性整数规划图形工具(在MATLAB5.3使用) % *...
• 第一章　线性规划及单纯形法 线性规划线性规划（Linear Programming简称LP）是运筹学的一个重要分支，也是...　掌握最短路问题及其求解方法； 　掌握最大流问题及其求解方法。 　掌握最小费用流问题及其求解方法。
• lingo算法实现单源单宿最短路问题代码 线性规划的学习内容 有完整代码，包括带整数约束的
• 整数规划的分支定界法；用MATLAB优化工具箱解线性规划；用Lingo软件求解；运输问题的数学模型；生产计划安排问题；分段函数的处理方法；人力资源安排问题；投资问题；最短路问题；设备更新问题
• 第2章 整数线性规划 2．1 割平面法 2．2 分枝定界法 2．3 习题 第3章 无约束优化 3．1 数学预备知识 3．2 无约束优化问题的解 3. 3 用MATLAB优化工具箱解无约束优化 3．4 习题 第4章 非线性...
• 中文版的，内容有：最优化问题、单纯元型算法、对偶性、原始-对偶算法、最大流有效算法、最短路、最小费用流、算法与复杂性、匹配算法、赋权匹配、指派问题、拟阵、整数线性规划、NP完备问题、近似算法、分支界定、...
• 离散优化程序，内含枚举法，蒙特卡洛法、线性整数规划，最小生成树、动态规划等等， %*enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint (BranchBound)- 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie ...
• matlab代码

2018-04-14 13:50:56
% *lpint (BranchBound)- 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数规划(在MATLAB5.3使用) % *bnbgui - 非线性整数规划图形工具(在MATLAB5.3使用) % *...
• lpint - 线性整数规划分支定界法 L01p_e - 0-1整数规划枚举法 L01p_ie - 0-1整数规划隐枚举法 0-1 bnb18 - 非线性整数规划 mintreek - 最小生成树kruskal算法 minroute - 最短路dijkstra算法 dynprog - 动态规划 ...
• 多项式规约

2019-11-08 11:15:32
有多项式时间算法的问题和可能没有多项式时间算法的问题 有多项式时间算法 可能没有多项式时间算法 最短路问题 最长路问题 最小割问题 ...整数线性规划问题 多项式规约...
有多项式时间算法的问题和可能没有多项式时间算法的问题

有多项式时间算法
可能没有多项式时间算法

最短路问题
最长路问题

最小割问题
最大割问题

2元可满足性问题
3元可满足性问题

平面图4着色问题
平面图3着色问题

二部图顶点覆盖问题
一般图顶点覆盖问题

匹配问题
3D匹配问题

素性测试问题
质因子分解问题

线性规划问题
整数线性规划问题

多项式规约
问题$X$能多项式规约到问题$Y$:
对于任意一个问题$X$的实例，进行多项式时间的标准计算步骤，加上多项式时间对$Y$问题求解方法的调用，最终能求解出问题$X$，则问题$X$能多项式规约到问题$Y$。
Note:
问题$Y$比问题$X$要更难，或者难的核心在$Y$上。
可以空跑问题$Y$算法，只是单纯的多项式时间的标准计算步骤
如果问题$X$和问题$Y$能够相互多项式时间规约，即$X\leq_p Y$且$Y\leq_p X$，那么我们用$X\equiv_p Y$，表示问题$X$和问题$Y$能够相互多项式时间规约。
由于自规约性，我们以下讨论的都是该问题的判定性问题（决策问题）
① 独立集问题 $\equiv_p$ 顶点覆盖问题
即若$S$是一个大小为$k$的独立集当且仅当$V-S$是一个大小为$n-k$的顶点覆盖
独立集问题
问题描述：给定一个图$G=(V,E)$和一个整数$k$，是否存在一个大小为$k$的顶点子集，使子集中任意两个顶点不邻接。
顶点覆盖问题
问题描述：给定一个图$G=(V,E)$和一个整数$k$，是否存在一个大小为$k$的顶点子集，使图中每一条边至少有一个顶点在上述顶点子集中。
如下图黑色顶点集合为大小为6的独立集，白色顶点集合为大小为4的顶点覆盖：

证明：
$\Rightarrow$
已知$S$是一个大小为$k$的独立集，则$V-S$是一个大小为$n-k$的顶点集合。
考虑任意一条边$(u,v)\in E$:
因为$S$是一个独立集，要么$u\notin S$，要么$v\notin S$，要么都不属于$S$。不可能都属于，因为那样$S$就不是独立集了。
所以要么$u\in V-S$，要么$v\in V-S$，要么都属于$V-S$。
根据顶点覆盖的定义，$V-S$覆盖了任意边$(u,v)$
$\Leftarrow$
已知$V-S$是一个大小为$n-k$的顶点覆盖，则$S$是一个大小为$k$的顶点集合。
考虑任意一条边$(u,v)\in E$:
因为$V-S$是一个顶点覆盖，$u\in V-S$，要么$v\in V-S$，要么都属于$V-S$。
所以要么$u\notin S$，要么$v\notin S$，要么都不属于$S$。
因此$S$是一个独立集。
证毕！
②顶点覆盖问题$\leq_p$集合覆盖问题
集合覆盖问题
问题描述：给定集合$U$，$S$集合中每个元素都是集合$U$的子集，给定整数$k$。问能否用$S$集合中$\leq k$个元素，使它们的并集等于原集合$U$。
如图所示，下列集合覆盖大小为$k=2$:

目标：任意给一个顶点覆盖问题的实例，都能构造出对应的集合覆盖实例。集合覆盖大小为$k$当且仅当顶点覆盖大小为$k$。
构图思路如下：
原顶点覆盖的顶点相当于集合覆盖中的子集合，原顶点覆盖的边相当于集合覆盖的子集合中元素。

$\Rightarrow$不妨令$X\subseteq V$为$G$中大小为$k$的顶点覆盖，则$Y = \{S_v: v\in x\}$为大小为$k$的集合覆盖。
$\Leftarrow$不妨令$Y\subseteq S$为大小为$k$的集合覆盖，则$X=\{v:S_v\in Y\}$为$G$中大小为$k$的顶点覆盖。证毕！
③三元可满足性问题$\leq_P$独立集问题
三元可满足性问题
问题描述：多个文字的并集构成一个从句，多个从句的交集构成一个合取范式$(CNF)$。给定一个合取范式，问是否存在使合取范式为真的分配方案，为一般的$SAT$问题。若限定每个从句中文字的数量为3个，则为三元可满足性问题$(3-SAT)$。
目标：给定一个3-SAT问题的实例$\phi$，我们都能构造出一个图$G=(V,E)$独立集问题的实例。3-SAT问题有解，当且仅当$G$中有个大小为$k=|\phi|$，$|\phi|$大小为合取范式中从句的个数。
构图思路如下：

$G$中三个顶点构成一个三角形表示一个从句，每个节点表示一个文字
每个顶点与其对立节点连线

证明：
$\Rightarrow$(偏说明性)
若对于合取范式$\phi$我们找到一个分配方案使其为真，则我们对于图$G$每个三角形中选择分配方案中文字为真对应的一个顶点。一共$|\phi|$个三角形，每个三角形按照上述方案选择一个顶点，选完后构成的$|\phi|$个顶点的集合为图$G$的独立集。
$\Leftarrow$(偏说明性)
令$S$是一个大小为$k$的独立集，则由于构图性质，对于每个三角形中有且仅有独立集中的一个顶点。令这些顶点对应合取范式中的文字为真，则合取范式$\phi$可满足。
总结
$3-SAT\leq_p$独立集问题$\equiv_p$顶点覆盖$\leq_p$集合覆盖
补充
目标：决策问题、搜索问题、优化问题这三个问题可以相互多项式规约

决策问题：是否存在一个大小为$k$的顶点覆盖
搜索问题：找到一个大小为$k$的顶点覆盖
优化问题：找到一个最小的顶点覆盖

由于上述三种问题多项式等价，因此我们之后只以决策问题为例，讨论该问题的性质（该问题属于$P$问题、$NP$问题还是$NPC$问题）。


展开全文
• 第3版韩伯棠主编的国家级精品课程 管理运筹学 随书软件 软件使用简单，包括线性规划线性规划、运输、整数规划、目标规划和对策论） 、图与网络（最短路、最小生成树、最大流、关键线路）、以及存储论模型、排队论...
• 软件使用简单，包括线性规划线性规划、运输、整数规划、目标规划和对策论） 、图与网络（最短路、最小生成树、最大流、关键线路）、以及存储论模型、排队论模型、决策分析、预测、层次分析法模型
• 韩伯棠管理运筹学配套运算软件，含线性规划、运输问题、整数规划、目标规划、对策论、最短路问题、最小生成树问题、最大流问题、最小费用最大流问题、关键路径问题、存储论、排队论、决策分析、预测、层次分析法等。
• Python解运筹学问题PuLP一般线性规划问题构造并求解混合0-1整数规划问题numpy和scipy标准问题（最小值，约束为<=）非标准形式运输问题指派问题（*scipy的linear_sum_assignment*）networkx 解图论问题最小支撑树...
Python解运筹学问题PuLP一般线性规划问题构造并求解混合0-1整数规划问题numpy和scipy标准问题（最小值，约束为<=）非标准形式运输问题指派问题（*scipy的linear_sum_assignment*）networkx 解图论问题最小支撑树问题最短路问题最大流问题
PuLP
一般线性规划问题
例题：
from pulp import *

#构建问题
my_LpProblem = pulp.LpProblem("myProblem", LpMaximize)
# 设置变量
x1 = pulp.LpVariable("x1", 0, None)
x2 = pulp.LpVariable("x2", 0, None)
x3 = pulp.LpVariable("x3", 0, None)
# 最有函数
my_LpProblem += -x1+x2+x3
# 约束条件
my_LpProblem += x1 - x2 +2*x3 <= 10
my_LpProblem +=-x1 + x2 +  x3 >= 4
my_LpProblem +=-x1      +  x3 == 2
# 求解
status = my_LpProblem.solve()
print("Status:", LpStatus[my_LpProblem.status])
# 打印出最优解
for v in my_LpProblem.variables():
print(v.name, "=", v.varValue)
# 打印最优目标函数值
print("objective=", value(my_LpProblem.objective))

构造并求解混合0-1整数规划问题
例题:
from pulp import *

my_MipProblem = LpProblem("myproblem", LpMinimize)

solution = []

x1 = LpVariable("x1", lowBound=0, cat=LpInteger)# LpInteger:整数型
x2 = LpVariable("x2", cat=LpBinary)# LpBinary:0—1型

x3 = LpVariable("x3", lowBound=0)

my_MipProblem += 2 * x1 + 3 * x2 + x3, "obj"
my_MipProblem += 2 * x1 -     x2 + 3 * x3 >= 6, "c1"
my_MipProblem += 4 * x1 +     x2 + 5 * x3 == 24, "c2"

my_MipProblem.solve()
# 打印出已经求解问题的状态

print("Status:", LpStatus[my_MipProblem.status])

# 打印出最优解

for v in my_MipProblem.variables():
print(v.name, "=", v.varValue)

solution.append(v.varValue)

# 打印最优目标函数值
print("objective=", value(my_MipProblem.objective))

numpy和scipy
用scipy的linprog求解以下线性规划问题
标准问题（最小值，约束为<=）
例题：
import numpy as np
from scipy.optimize import linprog

c = np.array([-6, -1, -2])
A_ub = np.array([[1, 3, 1], [2, 0, 1], [1, 1, 0]])
b_ub = np.array([12, 6, 2])
x1_bounds = [0, None]
x2_bounds = [0, None]
x3_bounds = [0, None]

my_linprog_result = linprog(c, A_ub, b_ub, A_eq=None, b_eq=None, bounds=(x1_bounds, x2_bounds, x3_bounds), callback=None)
my_solution = my_linprog_result.x
my_optimum_value = my_linprog_result.fun
print(my_solution)
print(my_optimum_value)


非标准形式
用linprog求解时，只能求解最小值且为小于约束的问题，如果要求解其他问题，则需先变换成规定的标准形式。
例题：
import numpy as np
from scipy.optimize import linprog

c = np.array([-1,-1,2]) # 最大值变为最小值，取相反数
A_ub = np.array([[1,2,3],[-2,-1,2]]) # >=约束转换为<=约束，取相反数
b_ub = np.array([12,-8])
x1_bounds = [0,None]
x2_bounds = [0,None]
x3_bounds = [0,None]

my_linprog_result = linprog(c,A_ub,b_ub,A_eq=None,b_eq=None,bounds=(x1_bounds,x2_bounds,x3_bounds),method='simplex',callback=None)
my_solution = my_linprog_result.x
my_optimum_value = -my_linprog_result.fun # 将最优值转换为最大值
print(my_solution)
print(my_optimum_value)

运输问题
例题：
from pulp import *
import numpy as np
from itertools import product

production = 3 #3个产地
sale = 4       #3个销地+1个虚拟销地

demand = [20, 40, 60, 10]  # 销量
capacity = [45, 30, 55]  # 产量
cost = np.array([[7, 2, 2, 0], [1, 6, 5, 0], [5, 4, 7, 0]])
# 建立模型
prob = LpProblem("Transportation", LpMinimize)
x = LpVariable.dicts("x", product(range(production), range(sale)), lowBound=0, upBound=None, cat=LpInteger)  # product 作用未知
prob += pulp.lpSum(cost[l, c] * x[l, c] for l in range(production) for c in range(sale))

# 约束条件
for l in range(production):
prob += lpSum(x[l, c] for c in range(sale)) == capacity[l]
for c in range(sale):
prob += lpSum(x[l, c] for l in range(production)) == demand[c]
# 求解
prob.solve()

min_cost = value(prob.objective)
solution = []

for v in prob.variables():
solution.append(v.varValue)
solution = np.array(solution).reshape(3, 4)

print(solution)
print(min_cost)

指派问题（scipy的linear_sum_assignment）
学习阅读scipy.optimize.linear_sum_assignment
注意

linear_sum_assignment只能求解目标函数为最小值的线性指派问题
可以直接求解任务数与人数不对等的指派问题
输入参数必须为一个2D的numpy.array实例
返回的结果为最优指派对应在此2D array上的index

例题1：

import numpy as np
from scipy.optimize import linear_sum_assignment

s1 = [11, 10, 11, 3, 11]
s2 = [8, 11, 10, 12, 14]
s3 = [15, 5, 16, 2, 3]
s4 = [15, 3, 5, 17, 14]

time_array_standardized = np.vstack((s1, s2, s3, s4,s4))

row_ind, col_ind = linear_sum_assignment(time_array_standardized)
print(row_ind)#开销矩阵对应的行索引
print(col_ind)#对应行索引的最优指派的列索引
print(time_array_standardized[row_ind,col_ind])#提取每个行索引的最优指派列索引所在的元素，形成数组
minimum_time = time_array_standardized[row_ind,col_ind].sum()#数组求和
print(minimum_time)

例题2：

import numpy as np
from scipy.optimize import linear_sum_assignment

s1 = [-320, -300, -440, -470, -450]
s2 = [-370, -490, -420, -550, -310]
s3 = [-360, -510, -440, -490, -300]
s4 = [-310, -420, -420, -450, -450]
s5 = [-340, -330, -400, -450, -510]

time_array_standardized = np.vstack((s1, s2, s3, s4, s5))

row_ind, col_ind = linear_sum_assignment(time_array_standardized)
print(row_ind)#开销矩阵对应的行索引
print(col_ind)#对应行索引的最优指派的列索引
print(time_array_standardized[row_ind,col_ind])#提取每个行索引的最优指派列索引所在的元素，形成数组
maximum_sales = -time_array_standardized[row_ind,col_ind].sum()#数组求和
print(maximum_sales)

networkx 解图论问题
Python的Networkx包
NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and function of complex networks.
With NetworkX you can load and store networks in standard and nonstandard data formats, generate many types of random and classic networks, analyze network structure, build network models, design new network algorithms, draw networks, and much more.
官方文档
入门教程
算法
networkx整理内容
预习内容：

nx.Graph(无向图)和nx.DiGraph(有向图)的生成
用Networkx的minimum_spanning_tree和minimum_spanning_edges方法求解最小支撑树问题
用
Networkx的最短路求解方法求解最短路问题

最小支撑树问题
用Networkx的minimum_spanning_tree和minimum_spanning_edges方法求解以下最小支撑树问题，要求：

节点的编号从0开始
边的权重用weight表示
返回G，其为下图所对应的Graph.
返回T，为G对应的最小支撑树
返回T_edges，为T中的所有边，T_edges可以是一个list，或tuple，或generator.
返回T_weight，T的权重之和.
提示：使用Graph.size会有帮助.

例题：
import networkx as nx
G = nx.Graph()
# 设置节点
v = {}
for i in range(10):
v[i] = f'v{i}'
# 设置无向边
weight = [(0,1,17), (0,2,21), (0,6,14), (0,8,24), (0,9,10),
(1,4,10), (1,5,17), (1,6,11), (1,8,22),
(2,3,18), (2,8,22),
(3,5,11), (3,6,10), (3,7,14), (3,9,23),
(4,7,7), (4,8,18),
(5,9,18),
(6,7,20),
(7,8,11)]
# 生成无向图
for (start,end,flow) in weight:
# 求最小树和最小树的边
T = nx.minimum_spanning_tree(G)
T_edges = list(nx.minimum_spanning_edges(G))
# 计算T_weight(从tuple中取出dict，再从dict中取出值)
T_weight = 0 # 初始化
for (start, end, weight) in T_edges:
T_weight = T_weight + weight.get('weight') # dict没有value方法（T_weight = T_weight + weight.value()）

print(sorted(T.edges(data=True)))
print(T_weight)

最短路问题
用Networkx的最短路求解方法求解以下最短路问题，要求：

节点的编号从0开始
返回G，其为下图所对应的DiGraph.
返回all_shortest_paths，为G中source和target之间的所有最短路径，例如如果v1到v8的最短路径有两条：v1→v2→v8和v1→v3→v4→v8，则返回一个list或generator，其格式为[[0,1,7], [0,2,3,7]].
返回shortest_path_length，为最短路的长度.

例题1：求解下图中从v1至v8的最短路径及最短距离.

import networkx as nx
# 生成有向图
G = nx.DiGraph()
edge = [(0, 1, 1), (0, 2, 4), (0, 3, 3),
(1, 2, 3), (1, 4, 8),
(2, 4, 5), (2, 5, 3), (2, 6, 6),
(3, 2, 4), (3, 6, 5),
(4, 5, 4), (4, 7, 3),
(5, 7, 4),
(6, 5, 2), (6, 7, 5)] #可以是list，也可以是tuple
for (start, end, flow) in edge:
# 求解最短路径
all_shortest_paths = list(nx.all_shortest_paths(G, source=0, target=7, weight='weight')) #默认算法是dijkstra，调出属性
shortest_path_length = nx.shortest_path_length(G,source=0,target=7,weight='weight')
print(all_shortest_paths)
print(shortest_path_length)

例题2：
import networkx as nx
# 生成有向图
G = nx.DiGraph()
edge = [(0, 1, 3), (0, 2, 2), (0, 4, 3),
(1, 3, -2), (1, 4, 7),
(2, 4, 4), (2, 5, 1),
(3, 4, 5), (3, 6, 4),
(4, 5, 1), (4, 6, 4),
(5, 6, 2), (5, 7, 5),
(6, 7, 6), (6, 8, 4),
(7, 8, 6)] #可以是list，也可以是tuple
for (start, end, flow) in edge:
# 求解最短路径
all_shortest_paths = list(nx.all_shortest_paths(G, source=0, target=8, weight='weight')) #默认算法是dijkstra，调出属性
shortest_path_length = nx.shortest_path_length(G,source=0,target=8, weight='weight')
print(all_shortest_paths)
print(shortest_path_length)

最大流问题
用Networkx的Maximum Flow算法方法求解以下网络最大流问题。
例题要求：

节点的编号从0开始

返回G，其为下图所对应的DiGraph，其中弧上的权重用capacity表示.

返回max_flow_value，为最大流的流量(数值).

返回cut_set，为最小割集，可以是一个list或set.

求解下图中从v1至v11的最大流及最小割，并思考最小割集是什么。图中弧上的数字表示其容量.

import networkx as nx
G = nx.DiGraph()
edge = [(0, 1, 155), (0, 2, 180), (0, 3, 30),
(1, 4, 155), (1, 5, 185),
(2, 4, 105), (2, 5, 65), (2, 6, 60),
(3, 5, 120), (3, 6, 160),
(4, 7, 110), (4, 8, 60),
(5, 7, 180), (5, 8, 155), (5, 9, 60),
(6, 8, 135), (6, 9, 135),
(7, 10, 85),
(8, 10, 85),
(9, 10, 155)]
for (start, end, flow) in edge:
# 计算最大流的值
max_flow_value = nx.maximum_flow_value(G, 0, 10, capacity="capacity")
# 计算最小割
cut_value, partition = nx.minimum_cut(G, 0, 10,capacity="capacity")# partition (u,v)
reachable, non_reachable = partition
# 设置弧
cut_set = set()
for u, nbrs in ((n, G[n]) for n in reachable):
cut_set.update((u, v) for v in nbrs if v in non_reachable)




展开全文
• 17．Linear and Integer Programming （缩写为 LP-ILP ，线性规划与整数线性规划） 用于求解线性规划、整数规划、对偶问题等，可进行灵敏度分析、参数分析。 18．Goal Programming （缩写为 GP ，目标规划） 用于...
• 线性规划整数规划、多元规划、二次规划等规划类4．图论算法（最短路、网络流、二分图等算法）5．动态规划、回溯搜索、分治算法、分支定界等计算机算法6．最优化理论的三大非经典算法：模拟退火法、神经网络、遗传...

数据建模十类算法
1、蒙特卡罗算法2．数据拟合、参数估计、插值等数据处理算法3．线性规划、整数规划、多元规划、二次规划等规划类4．图论算法（最短路、网络流、二分图等算法）5．动态规划、回溯搜索、分治算法、分支定界等计算机算法6．最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法7．网格算法和穷举法8．连续离散化方法9．数值分析算法10．图象处理算法
以上十类算法开篇。

转载于:https://www.cnblogs.com/bubblefu/p/3872064.html
展开全文
• 3：线性规划整数规划、多元规划、二次规划(用lingo、lingdo、matlab即可实现)；4：图论算法（包括最短路、网络流、二分图）；5：动态规划、回溯搜索、分治算法、分支界定；6：最优化理论的三大经典算法（模拟退火...
• WinqSB绿色2.0版

热门讨论 2010-06-02 14:33:11
• 为解决考虑端口连通性限制的路由与波长分配问题，建立了其整数线性规划(ILP)模型，并提出了3种考虑端口连通性(IPCA)的动态路由机制，包括基于K最短路(KSP)的IPCA(IPCA-KSP)机制、IPCA-Dijkstra机制与全路径搜索机制...
• 在 Q 的基础上，量化不同目标为有向赋权 图的不同权矩阵(见 5.2.0)，以所求顶点u 到顶点v的路径是否包含 xij 弧为决策变量， 上述 5 项用户需求为目标，始、终点连通为约束建立 0-1 整数线性规划模型(见 5.2.3 模型...
• 4、图与网络分析这是一门应用相当广的学科，要求掌握基本概念、树、最短路、最大源以及最大费用最大源问题的解法。会绘制生产计划管理的计划网络图。利用网络图进行成本、资源等优化分析。最好结合自己的工作实践...
• % fmincon - 非线性规划(在MATLAB5.3使用) % % 离散优化 % *enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint - 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数...
• MATLAB数学建模工具箱

热门讨论 2013-05-20 15:06:10
% fmincon - 非线性规划(在MATLAB5.3使用) % % 离散优化 % *enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint - 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数...
• Matlab数学建模工具箱

热门讨论 2010-03-15 12:14:21
% fmincon - 非线性规划(在MATLAB5.3使用) % % 离散优化 % *enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint - 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数...
• 《运筹学上机实验指导》分为两个部分，第一部分12学时，是与运筹学理论课上机同步配套的4个实验（线性规划、灵敏度分析、运输问题与指派问题、最短路问题和背包问题）的Excel、LONGO和LINDO求解方法和3个大综合作业...
•  ③回归分析、图论及最短路优化资料 ①赛题及赛题解析  ②优秀论文11篇  ③多元线性回归、决策树资料 ①赛题及赛题解析  ②优秀论文8篇+ ( \9 y' ; D5 E) B  ③微分方程、非线性拟合资料 ①赛题及赛题解析; ~...