首页 > 代码库 > 线性规划问题中的差分约束与最短路径

线性规划问题中的差分约束与最短路径

先给一个线性规划的定义:

  在通用的线性规划问题中,我们通常给定一个m*n的矩阵A,一个m维的向量和一个n维向量(权值函数)。我们希望找到一个n维向量x,使得在由Ax<=b给定的m个约束条件下优化目标函数技术分享ci*xi,这里的优化是指目标函数的取值最大。

根据矩阵乘法,我们大概脑补出这样一幅图

技术分享

ps:上图中<号应为<=号(我会告诉你是我懒得改

通过化简我们得到 x1-x3<=b1;x3<=b2;x2-x3<=b3;

这跟我们的最短路径有什么关系呢?

在最短路径的三角不等式中,有dist[v]<=dist[u]+map[u][v];

貌似有点像!

上氏可以化简为x1<=x3+b1

所以可以看成在一张图内,x3到x1连了一条长为b1的边

为了方便求出其他几个点的解值,我们定义一个超原点为0,算出与其他点之间的最短距离,其他几个原点的其中一个解就是这个距离的数值(我们的差分关系都是建立在差的关系上,可以全部数加减一个值)

这是我们有问题了:如果算不出最短路径,怎么办?

恰巧的是,如果算不出最短路径,那么就是有负权环,然而这个线性约束就无解——没有一个实数符合这些约束。因为如果我们有一个环路(v1->v2->...->vn)

v1<=v2+map[v1][v2]

v2<=v3+map[v2][v3]

........

vn-1<=vn+map[vn-1][vn]

vn<=v1+map[1][n]

对于左右两边求和,得到0<=map[v1][v2]+map[v2][v3]+...+map[vn][1]

因为是负权环路,所以我们就有0<=一个负数

所以这个线性约束就无解啦。

 

线性规划问题中的差分约束与最短路径