线性规划

线性规划与差分约束一般形式的线性规划问题可用矩阵来表述，而差分约束为线性规划的特例，其可用有向图表示。给出相关定义： 1) 线性规划：给定\(m\times n\)矩阵\(A\)、\(m\)维向量\(b\)、\(n\)维向量\(c\)。求在\(Ax \leq b\)约束下使\(\sum  c_ix_i\)取最大值的\(n\)维向量\(x\)； 2) 差分约束：若矩阵\(A\)每行是仅有1个-1、仅有1个1、其余都为0的，且\(x\)仅需满足\(Ax \leq b\)约束即可； 3) 差分约束图：用有向图\(G\)的边\((v_i,v_j)\)与权重\(w(v_i,v_j)\)表示\(x_j – x_i \leq w(v_i,v_j)\)，则\(G\)可表示给定差分约束，再在\(G\)加入\(v_0\)顶点得到\(G’\)，规定\(v_0\)仅有直达其他所有顶点的0权重边。\(G’\)为差分约束图，\(G’\)与\(G\)的解等价；… 阅读全文