详情可参考这里 我们常常遇到的Assignment、Transportation、Maximum flow、Shortest path等问题都具有特殊的结构，可以用network program来建模。具体来说，network program指的是如下问题： min c T x \min c^Tx mincTx A x = b Ax= b Ax=b l ≤ x ≤ u l\le x\le u l≤x≤u 其中 A ∈ − 1 , 0 , 1 n × m A\in {-1,0,1}^{n\times m} A∈−1,0,1n×m，并且每一行只有一个1和一个-1。 下面是一个例子： network program可以看做是最小费用流问题的数学模型。定义有向图 G = ( V , E ) G=(V,E) G=(V,E)， V V V用行表示， E E E用列表示，从 i i i到 k k k有边的话，则有一列的第 i i i行是1，第 k k k行是-1。 x j x_j xj表示第 j j j条边上的流量，如下图： 对于这类问题，如果存在一条path，那么 Σ \Sigma Σ方向*边 = e 终 点 − e 起 点 e_{终点}-e_{起点} e终点−e起点，其中 e e e表示单位向量。 定理：每一个连通图都有一个伸展树（包含所有节点的树） 定理：树的 A A A的列相互线性独立，秩为（节点数-1）。
选择一个根节点，添加虚拟变量 w w w和单位向量，如下： 根节点衍生出的伸展树和 e w e_w ew构成一组基 B B B。我们回忆一下单纯形法的出入基过程： 每次将负数残差 c N T − c B T B − 1 N c^T_N-c^T_BB^{-1}N cNT−cBTB−1N最小（绝对值最大）的非基变量 x i x_i xi替换为基变量，同时将 ( B − 1 b ( B − 1 N ) i ) j (\frac{B^{-1}b}{(B^{-1}N)_i})_j ((B−1N)iB−1b)j最小值对应的基变量 x j x_j xj替换为非基变量。 有3个地方用到 B − 1 B^{-1} B−1： y T B = c B T y^TB = c^T_B yTB=cBT B x = N q Bx= N_q Bx=Nq B x = b Bx=b Bx=b 这三个地方都可以用上面的图快速求解，不需要再存储 B − 1 B^{-1} B−1。以 y T B = c B T y^TB = c^T_B yTB=cBT为例： 我们有： 相当于从 y 2 y_2 y2出发遍历树。
