线性规划的用处非常的广泛，这主要是因为很多类型的问题是可以通过转化的方式转化为线性规划的问题。例如需要再图论中寻找起始点到给定的点的最短路径问题：

添加图片注释，不超过 140 字（可选）

假设要计算从节点0到节点4的最短路径，用变量d1到d4来表示节点0到节点1,2，3,4的最短路径，那么解决这个问题的本质上是解决如下的一个线性规划系统：

添加图片注释，不超过 140 字（可选）

而这里要注意的是问题所需要求的是最短路径，按照目标函数应该是查找最小值才对，但是这里是查找的最大值，因为如果查找最小值，那么问题的答案就是将所有变量设置为0，而这就与所需要的目标是不相符的。

由于最短路径肯定大于0，同时最短路径一定能满足上面线性系统的约束条件，且最大化可以让我们找到一个非零解，因此它才能对应正确的最短路径。

在图论中还存在一种称为极大流的问题，如果给定一个有向图G，其中有一个起点和一个终点，在两者之间存在很多中间点，同时点与点之间的连接存在一个容量上限，问题是从起点开始发出多少流量，