第7章线性规划问题与网络流

7.1概述在生产管理和经营活动中，经常会遇到两类问题：一类是如何合理地使用现有的劳动力、设备、资金等资源，以得到最大的收益；另一类是为了达到一定的目标，应该如何组织生产，或管理安排工艺流程使得所消耗的资源最少；P211如：配载问题：某种交通工具的容积和载重一定(约束)，运输若干物资，如何运输可以使得运输工具装载的物资最多(目标函数)。

物资调运问题：

将这些约束条件和目标函数都是决策变量的线性函数的规划问题称为线性规划问题。第7章线性规划问题与网络流17.1.1一般线性规划问题的描述为了解决这类问题：首先，需要确定问题的决策变量；然后，确定问题的目标，并将目标表示为决策变量的线性函数;最后，找出问题所有约束，并将其表示为决策变量的线性方程.P214:变量满足约束条件的一组值称为线性规划问题的一个可行解。使目标函数取得极值的可行解称为最优解。在最优解处目标函数的值称为最优值。2线性规划问题一般用单纯形算法求解；

单纯形算法是由1947年乔治.丹捷格发明的一种求解线性规划问题的方法。

例题1解：将线性规划问题转化为约束标准型如下：

令3由约束标准形式可知：x1,x5,x6是基本变量，x2,x3,x4是非基本变量，建立初始单纯形表如表7-2所示。由此可得，基本可行解为X(0)=（7,0,0,0,12,10），z’=0。由表7-2可知：x3为入基变量，x5为离基变量，根据迭代公式得出如表7-3所示的单纯形表3。由此可得，基本可行解为X(1)=（10,0,3,0,0,1）,z’=94由表7-3可知：x2为入基变量，x1为离基变量，根据迭代公式迭代得如表7-4所示的单纯形表4。由此可得，基本可行解为X(2)=（0,4,5,0,0,11）,z’=11。同时，由表7-4可知，所有检验数均小于等于0，故X(2)=（0,4,5,0,0,11）为该线性规划问题的唯一最优解，其最优值z=-11。练习：5举例：

设有一个水管网络该网络有进水口与出水口，每个管道的粗细作为该管道的权值，反映该管道的最大流量；则在该水流网络中，进一步加大流量由于受到水管网络的限制，加到一定流量后，再也加不进去，这就是此水管网络的最大流量。7.2最大网络流问题61基本概念和术语

（1）网络G是一个简单有向图，G=(V,E)，V={1，2，…，n}。在V中指定一个顶点s，称为源和另一个顶点t，称为汇。有向图G的每一条边(v,w)∈E，对应有一个值cap(v,w)≥0，称为边的容量。这样的有向图G称作一个网络。（2）网络流网络上的流是定义在网络的边集合E上的一个非负函数flow={flow(v,w)}，并称flow(v,w)为边(v,w)上的流量。7（3）最大流最大流问题即求网络G的一个可行流flow，使其流量f达到最大。即flow满足：0≤flow(v,w)≤cap(v,w)，(v,w)∈E；且8（5）增广路设flow是一个可行流，P是从s到t的一条路，若P满足下列条件：在P的所有向前边(v,w)上，flow(v,w)<cap(v,w)，即P+中的每一条边都是非饱和边；在P的所有向后边(v,w)上，flow(v,w)>0，即P-中的每一条边都是非零流。则称P为关于可行流flow的一条可增广路。对于最大网络流问题一般使用一种叫增广路算法来求解。97.2.2增广路算法增广路定理：设flow是网络G的一个可行流，如果不存在从s到t关于flow的可增广路P，则flow是G的一个最大流.增广路算法（1）初始化为0流（2）找关于当前可行流的可增广路，若找到，转3；否则，当前可行流为网络的最大流。（3）沿增广路增流。因此，增广路算法主要包括两个过程：找增广路和沿增广路增流。对于最大网络流问题一般使用一种叫增广路算法来求解。10可采用标号法找可增广路。对网络中的每个节点j，其标号包括两部分信息（pred(j)，maxl(j)），其中pred(j)表示节点j在可能的增广路中的前一个节点，maxl(j)表示沿该可能的增广路到节点j为止可以增加的最大流量。具体步骤为：步骤1：源点s的标号为（0，+∞）。步骤2：从已标号而未检查的点v出发，对于边<v，w>，如果flow(v，w)<cap(v，w)，则w的标号为(v，maxl(w))，maxl(w)=min{maxl(v),cap(v，w)-flow(v，w)}；对于边<w，v>，flow(w，v)>0，则w的标号为(-v，maxl(w))，maxl(w)=min{maxl(v)，flow(w，v)}。步骤3：不断重复步骤2，直到已经不存在已标号未检查的点或标到了汇点结束。如果不存在已标号未检查的点，则说明不存在关于当前可行流的可增广路，当前流就是最大流。如果标到了汇点，则找到了一条可增广路，需要沿着该可增广路进行增流，转过程（2）。沿增广路增流具体方法

11例题用增广路算法找出如下图所示的网络及可行流的最大流，其中，顶点1为源点，顶点6为汇点，边上的权为（cap，flow）12标号法找增广路

沿着增广路增流

13标号法找增广路

沿着增广路