运筹学基础实务

第１章图论基础及应用1.1图的基本概念1.2树的定义及应用1.3中国邮递员问题1.4旅行商问题返回1.1图的基本概念１.１.１引例例１邮递员问题一位邮递员投递邮件，从邮局出发，经过他所负责投送的全部街道，完成任务后必须返回邮局。问应采用怎样的行进路线，才能使所走路程最短？设邮递员负责投递的街道如图１．１所示，v１表示邮局，vi（i＝２，３，４，…１０）表示街道之交叉点。为了使计算方便，设两交叉点之间距离为１单位。邮递员从v１出发，经图中的所有街道，最后返回v１，求其最短路程。下一页返回1.1图的基本概念从v１出发最后回到v１的方案很多。如（１）v１→v２→v３→v７→v６→v２→v６→v７→v１０→v９→v５→v６→v５→v９→v８→v４→v５→v４→v１这条路线的总路程为１８单位；（２）v１→v２→v３→v７→v６→v２→v６→v５→v９→v１０→v７→v１０→v９→v８→v４→v５→v４→v１这条路线的总路程为１７单位。这里出现了两个路程，虽然１７单位比１８单位优，但１７单位是不是最短路程呢？即投递方案（２）是不是最佳投递路线？这是图论要解决的问题之一。上一页下一页返回1.1图的基本概念例２哥尼斯堡（ｋｏｎｉｓｂｅｒｇ）七桥问题哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥，如图１．２所示。那里的居民热衷于这样的问题：一个散步者能否过七座桥，且每座桥只走一次，最后回到出发点？１７３６年欧拉将此问题归结为如图１．３所示图形的一笔画问题，即能否从某一点开始一笔画出这个图形，最后回到原出发点，而不重复。欧拉证明了这是不可能的，因为图１．３中的每个点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。这是古典图论中的一个著名问题。上一页下一页返回1.1图的基本概念例３旅行商问题一名旅行商要到某些城镇去经商，他想经过每一城镇一次，且仅仅一次，还要行程最短。问应该如何确定行走路线？在邮政通信中，农村邮递员的邮递路线及城市转趟车的行走路线与此类似。我们可以用图来表示这一问题，如图１．４所示。图中顶点代表要去的城镇，顶点间的连线代表两城镇间路程最短的道路及其最短路程，问题是如何找出一条路线，经过所有顶点一次且仅仅一次，又回到出发的顶点，而使所经过边的总长度最小？这个问题中，当城镇数较多时是很复杂的问题，一直吸引着众多研究者的兴趣。上一页下一页返回1.1图的基本概念1.１.２图的定义及应用图论中所研究的图与人们通常所熟悉的图（如数学中的各种几何图形、函数图形等）是完全不相同的。图论中所研究的图，指的是由若干个点和连接这些点中的某些“点对”的连线所组成的图形。它不按比例尺画，线段不代表真正的长度，点和线条的位置有随意性。图中的点称之为顶点，线称之为边，图的顶点表示某一具体事物，边表示事物之间的某种特定关系。上一页下一页返回1.1图的基本概念例如，图１．５表示某地区的公路交通图，Ａ、Ｂ、Ｃ、Ｄ、Ｅ表示五个城镇，两城之间的连线表示公路。若Ａ、Ｂ间有公路相通，则两城间有一条连线（即边），它表示Ａ和Ｂ之间的特定关系，我们感兴趣的是Ａ、Ｂ之间是否有这种特定关系。也就是说，两点间有无连线是重要的，而连接方式无关紧要。因此，图１．５所示的两城间公路也可以用直线表示，如图１．６。又如，用点可表示支局所，边表示支局所间的邮路；用点表示电话机，边表示电话线路；用点表示各级邮区中心局，边表示中心局间的邮路；用点表示电子元件，边表示导线等等，都可以用图来描述。综上所述，所谓图是由点和边组成，即点集和边集构成了图。用G表示图，用V表示点集，E表示边集，有上一页下一页返回1.1图的基本概念例４某问题构成如下图在图１．７中，点集V由６个顶点构成，即边集E由１０条边构成，即其中，每一条边都可以用两个端点表示，即上一页下一页返回1.1图的基本概念图G中，点的个数记为p（G），边的条数记为q（G），简记为p，q。若e＝（u，v）∈E，则称u，v是边e的端点，称e是u，v的关联边。若点u和点v与同一条边相关联，我们就说点u和点v是相邻的。若两个边ei和ej有一个公共端点，则称ei，ej是相邻的。称次数为１的点为悬挂点，与悬挂点关联的边称为悬挂边。次数为零的点称为孤立点。根据点的次数的定义，我们有如下定理。定理１图G中，所有顶点次的和，等于边数的两倍。即结论是显然的，这是因为在计算各点的次数时，每条边均用了两次，于是，G中全部顶点的次的和，就是边数的两倍。上一页下一页返回1.1图的基本概念另外，如果我们称次数为奇数的点为奇点，次数为偶数的点为偶点，则有：定理２任一图中，奇点的个数必为偶数。证明：设V１和V２分别为图G中奇点、偶点的集合，由定理１有：关于图的应用，范围是非常广泛的，在这里我们仅就图中点和边的着色问题做一简单讨论。问题１课程考试安排问题：设某一学校有n种课程由学生选修，学期终了要进行考试，当然每个学生每场只能参加一门课程的考试。试问该次考试最少要进行几场？显然没有共同学生的两门课程的考试可以在同一时间进行。上一页下一页返回1.1图的基本概念在平面上取n个顶点v１，v２…，vn分别表示这n门课程，若有同学同时选了课程i和课程j，则过vi和vj点连一条边，结果得一有n个顶点的图G。考试的安排问题相当于图G的顶点着色问题。着同一颜色的顶点对应的课程可同时进行考试。使图G的相邻顶点有不同颜色的最少数目，便是进行考试的最少场数。问题２时间表问题：设x１，x２，…，xm为m个工作人员，y１，y２，…，yn为n种设备。设工作人员对设备提出要求，使用时间假定均以单位时间计算。自然每一个工作人员在同一个时间只能使用一种设备，一种设备在同一时间里只能为一个工作人员所使用。问应如何合理安排，使得在尽可能短时间里满足工作人员的要求？上一页下一页返回1.1图的基本概念用m个点x１，x２，…，xm表示m个工作人员，用n个点y１，y２，…，yn表示n种设备。工作人员xi要求使用设备yj，每单位时间对应一条从xi到yj的边，这样从xi到yj的边可能不只一条，问题变为对所得图G的边的着色问题，有相同颜色的边可以安排在同一时间里。问题３物资储存问题：设有n种物资要存放在仓库里，但有的物资不能放在同一房间里，否则将引起损坏，甚至发生危险。问存放这n种物资最少要几个房间？同样，在平面上取n个顶点v１，v２…，vn，分别表示n种物资。设vi，vj为不能放在一起的两种物资，则过vi，vj点连一条边，得一个n个顶点的图G，于是问题又变为图G的顶点的着色问题。上一页下一页返回1.1图的基本概念例５有八种化学药品Ａ，Ｂ，Ｃ，Ｄ，Ｐ，Ｒ，Ｓ，Ｔ要放进贮藏室保管。出于安全原因，下列各组药品不能贮藏在同一室内：Ａ—Ｒ，Ａ—Ｃ，Ａ—Ｔ，Ｒ—Ｐ，Ｐ—Ｓ，Ｓ—Ｔ，Ｔ—Ｂ，Ｂ—Ｄ，Ｄ—Ｃ，Ｒ—Ｓ，Ｒ—Ｂ，Ｐ—Ｄ，Ｓ—Ｃ，Ｓ—Ｄ，问贮藏这八种药品至少需要多少房间？解：用八个点①，②，③，④，⑤，⑥，⑦，⑧分别代表Ａ，Ｂ，Ｃ，Ｄ，Ｐ，Ｒ，Ｓ，Ｔ八种药品，将不能放在同一室内的药品用边连接，得如下图１．８。将①着为红色，则⑦可着为红色，②可着为红色，将③着为绿色，则⑤可着为绿色，⑧可着为绿色，而④，⑥可着为黄色。上一页下一页返回1.1图的基本概念于是至少需要三个房间贮藏这八种化学药品。其中一个最优方案是Ａ，Ｂ，Ｓ占一间，Ｃ，Ｐ，Ｔ占一间，Ｄ，Ｒ占一间。例６有十六名运动员参加Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ八个项目的游泳比赛，已知运动员号码及参加比赛项目如下表所示（表中打*者为参加项目）。为使参加多项比赛的运动员恢复体力，要求比赛顺序安排保证每个运动员不连续参加两项比赛，问如何安排才能做到这一点？解：将每个比赛项目用一个点表示，同一运动员参加比赛项目的点用边连接，如图１．９所示。安排比赛的顺序做到相邻的项目点隔开安排。上一页下一页返回1.1图的基本概念安排顺序上可以有多个方案，其中之一可以是：Ｅ→Ａ→Ｇ→Ｄ→Ｃ→Ｆ→Ｂ→Ｈ１.１.３连通图的概念若图G的一个点与一条边的交替序列｛vi１，ei１，vi２，ei２，…，ei（k－１），vik｝满足eit＝（vit，vi（t＋１））（t＝１，２，…，k－１），则称这个点边序列为一条从vi１到vik的链，为简便，以后我们就记为μ＝｛vi１，vi２，…，vik｝。链μ＝｛vi１，vi２，…，vik｝中，若vi１＝vik，则称之为圈。圈实际上就是闭链。若链（圈）中含的边均不相同，则称之为简单链（圈），若不仅边不相同，点也不相同，称之为初等链（圈）。上一页下一页返回1.1图的基本概念定义一个图中，若任意两点之间，至少有一条链存在，则称这个图为连通图，否则，称为不连通图。１.１.４子图在研究和描述图的性质以及图的局部结构中，子图的概念占有重要的地位。设G１＝（V１，E１），G２＝（V２，E２），如果V１.V２，E１.E２，则称G１是G２的子图，并且：（１）若V１＝V２，E１∈E２，则称G１是G２的一个部分图。上一页下一页返回1.1图的基本概念（２）若V１∈V２，E１∈E２，即G１不包含G２中所有的顶点和边，则称G１是G２的真子图。（３）若V１.V２，E１＝｛（u，v）∈E２｜u∈V１，v∈V１｝，则称G１是G２的由V１生成的子图。记为G（V１）。上一页返回１．２树的定义及应用在众多的图中，有一类图就其结构而言很像天然的树，如图１．１２所示，故命名为树，这类图的应用很广，如企业的组织机构、通信线路、生产流程、计算机工作中的各种故障等等都可以用树来描述。为了更好地利用树来研究实际问题，这里我们介绍树及其性质。１.２.１树及其性质定义无圈的连通图称为树。记作性质１在树T中，任意两点之间有且仅有一条链。性质２在树T中，若去掉任一条边，则成为不连通图。性质３在树T中，不相邻的两个顶点间加上一条边，恰好得到一个圈。下一页返回１．２树的定义及应用性质４设T为p个顶点的一棵树，则T的边数为p－１条。１.２.２图的部分树定义如果G＝（V，E）的部分图T＝（V，E′）是树，则称T为G的一个部分树。例如图１．１３是图１．１１（ａ）的一个部分树。若T＝（V，E′）是G＝（V，E）的一个部分树，则G中属于T的边称为树T内的边，其余边称为树T外的边。显然，若图G有部分树，那么G必定是连通图，反过来，结论也成立。上一页下一页返回１．２树的定义及应用１.２.３最小部分树定义设图G＝（V，E），对G中的每一条边（vi，vj）相应地赋予一数字ωij，称为边（vi，vj）的权，则图G称为赋权图。这里的权指的是与边有关的数量指标，根据实际问题的要求，权有它的相应含义。如表示距离、时间、费用、容量等等。对于连通的赋权图来说，在其一切部分树中，必有一棵总权最小的树，称其为最小部分树，简称最小树。即，设连通图G＝（V，E），对于一切（vi，vj）∈E，均有一权ωij≥０，若T*是G的一棵部分树，且有为最小，则称T*是G的一棵最小部分树。上一页返回１．３中国邮递员问题1.３.１问题的提出一个邮递员传送邮件，从邮局出发，走完他所负责的全部街道，完成任务后回到邮局，问应该按照怎样的路线走，才能使所走的路程最短？这个问题的一般描述如下：给定一个连通图G＝（V，E），在每一边ei∈G上赋予一权，试求一个圈，过图G每边至少一次，并使圈的总权最小。这个问题是我国管梅谷在１９６２年首先提出的，因此在国际上通称为“中国邮递员问题”。下一页返回１．３中国邮递员问题１.３.２欧拉图在多重连通图G中，若存在一个圈，过G每边一次且仅有一次，则称G为欧拉图（简称图），也叫欧拉圈。在G中，若存在一条链，过每边一次且仅有一次，则称此链为欧拉链。欧拉图的一个重要特点是图G中无奇点。事实上，设某一始点为S，由于G存在E圈，故S又是终点，G的其余点为中间点，记为Z，对于中间点Z，每进入一次必出来一次，故Z的次数为偶数，即d（Z）＝２k；对于S点，出去一边，最后返回一边，故有上一页下一页返回１．３中国邮递员问题由此可见，E图中无奇点。同时，我们可以证明：无奇点的有限多重连通图G必是E图。事实上，我们可以利用构造E图的方法来证明G是E图。在G中任取一点v０∈V，取其关联边记（v０，v１），因为d（v１）＝２k１，所以必须步出v１，再取未用过的关联边记为（v１，v２），因为d（v２）＝２k２，所以必须步出v２，再取未用过的关联边记为（v２，v３），……不断重复上述过程，每次都取未用过的关联边，直至返回v０，这就构造成E图，记作C１。（这一定能实现。d（v０）＝２k）上一页下一页返回１．３中国邮递员问题显然有下述情况发生：（１）C１＝G由欧拉图的定义可知G是E图。（２）C１∈G即是G的一个子图。在这种情况下，可以从与C１某点相关联的任何一条未用过的边出发，仿照上述构造法，得另一个E圈C２。一般说来，可不断构造出C３，C４，…，Cn，直至把G中所有边都经过一次为止。由于G的有限性，这一点是可以做到的，然后根据G的连通性，把所有圈C１，C２，…，Cn结成一个大圈C，其方法是：从C１圈的v０出发，沿C１圈前进，遇到C１，C２的交叉点，转入C２，沿C２前进，同样凡遇到两子圈交叉点时，转入另一圈继续上法，最后返回v０，于是得C＝G，由构造C可知G是E图。上一页下一页返回１．３中国邮递员问题有了上述E图的概念，很容易判断七桥问题。由于七桥问题所示的图中有四个奇点，所以要想从某点出发经过每边一次且仅仅一次，最后返回出发点的圈不存在。即七桥图不存在E圈。１.３.３最佳投递路线设投递路线图G，显然有两种情况。（１）G是E图，则G为最佳投递路线图；（２）G中有奇点，非E图。上一页下一页返回１．３中国邮递员问题例如，图１．２０所示的投递路线图（边旁的数字为路权），其中有六个奇点，所以要想从某点v１出发经过每一边一次且仅有一次，最后返回v１是不可能的办到的。因此要经过每边至少一次，最后返回出发点，中间某些边必然要重复经过，而这样的投递方案有很多，如在图１．２０中的投递方案至少有两种，这使我们看到，含奇点的G中，两条投递路线的总权之差等于相应的重复边总权之差。因此对于一个含有奇点的G，要达到投递路线最短，实际上，只要求所增加的重复边总权最小。为了叙述方便，把增加重复边后不含奇点的新图称为可行方案，同时把重复边总权最小的可行方案称为最优方案（即最佳投递路线）。上一页下一页返回１．３中国邮递员问题现在的问题是：（１）在含奇点的图G中，如何确定初始可行方案；（２）如何判别可行方案的最优方案；（３）当可行方案不是最优时，又如何调整可行方案，使其成为最优方案。上一页返回1.4旅行商问题１.４.１哈密尔登回路设有二十个名城如图１．２４所示，每个点代表一个城市。要求从某一城市出发，经过每一城市一次，且仅一次，最后返回原地。这一问题是哈密尔登首先提出的，故这一类型的回路称为哈密尔登回路（H回路）。若图G存在一条道路P，它通过每一顶点各一次，则称P为图G的哈密尔登道路。显然，当哈密尔登回路去掉一条边时，将成为一条哈密尔登道路。和前面讲到的欧拉圈不同，直到现在还没有找到在任意图中判别H回路的充要条件。不过有些特殊的图中，肯定能找出H回路，如完全图就是这样。下一页返回1.4旅行商问题完全图是每对不同顶点之间都有一条边相连的简单图。如图１．２５、图１．２6所示、图１．２７所示，分别为３，４，５个顶点组成的完全图。而且已经证明完全图中的H回路数与图的顶点数n有关系为：H回路数＝（n－１）！／２。旅行商问题实际上就是要在给定的赋权图中找出一个总权数最小的H回路，如果有H回路存在的话，在完全图中，当顶点数不多时，可用分枝定界法或枚举法求解。上一页下一页返回1.4旅行商问题１.４.２分枝定界法解旅行商问题解题思路如下：设给定的连通图有n个顶点，要形成H回路必须用n条边，而且每个顶点连接的边数必为２。解题时首先选取最短的n条边，检查是否已构成H回路。如未形成，必有连接边数超过２的顶点，依次更换这些顶点所连接的边即形成分枝。当有一枝已获得H回路时，与其他各枝的总权相比较，如果小于此H回路的总权，则可继续分枝；如果各枝的总权均已大于此H回路的总权，则此H回路就是最小的H回路。计算结束。上一页返回图１．１投递街道图返回图１．２七桥示意图返回图１．３返回图１．４旅行商问题示意图返回图１．５公路交通图返回图１．６交通示意图返回图１．７返回图１．８返回图１．９返回图１．１２返回图１．１３返回图１．２０返回图１．２４返回图１．２５返回图１．２６返回图１．２７返回第２章网络分析技术２．１有向图的概念２．２最短路及其求法２．３网络的最大流求法２．４最小费用最大流问题返回2.1有向图的概念实际问题中事物之间的关系往往是有一定顺序的。如生产程序，水流方向，车辆往返路线等都有一定方向。为了形象地反映事物之间的方向性这种关系，将“点对”连线标以箭头“→”，称为有向边，记为表示该有向边的始点为vi，终点为vj。注意（vi，vj）与（vj，vi）是表示两个不同方向的有向边。由点集V和有向边集A组成的图称为有向图。下一页返回2.1有向图的概念为了区别起见，有时把第一章所说到的图称为无向图。例如，图２．１表示一个有向图。其中若将有向图D中所有有向边的箭头去掉，所得的无向图称为D的基础图，记作G（D）。设D＝（V，A）中点和有向边的交替序列上一页下一页返回2.1有向图的概念如果μ在G（D）中是一条链，那么μ也称为D的一条链。类似地，在有向图中也有圈和初等链的概念。若

是D的一条链，且满足则称μ为从vi１到vik的一条路。例如，在图２．１中，就是从v１到v６的一条路。若路的第一个点和最后一个点重合，则称之为回路。例如，图２．１中所示，就是一条回路。上一页返回２．２最短路及其求法设有向图D＝（V，A），在每一条有向边（vi，vj）∈A上给定一个数ωij，那么称D为赋权有向图。记为D＝（V，A，ω）例如，图２．２就是一个赋权有向图。在赋权有向图D中，若ωij表示两点之间的距离，而D中，任意两点之间往往有几条路可通，每条路都有一个总权，因此就存在一条总权为最小的路，这条路称为该有向图的最短路。在图２．２中，从v１至v６的路有：下一页返回２．２最短路及其求法从图２．２可以看出，从v１走向v６的路线很多，且总权各不相同，如何找到总权为最小的路线成为我们要解决的问题。如果采用把所有v１至v６的路线全部找出的办法，即采用穷举法，则对于复杂的赋权有向图是很困难的。下面介绍一种叫做Ｐ-Ｔ标号法的有效算法求有向图的最短路。上一页下一页返回２．２最短路及其求法２.２.１P-T标号法我们从v１（始点）出发，用两个标号来搜索最短路径，一个标号数为Ｔ，称为临时标号，且可以改变；另一个标号数为Ｐ，称为固定标号，不能改变。对某点vi来说，不是标以Ｔ标号，就是标以Ｐ标号。若vi标上Ｐ标号P（vi），则说明v１到vi的最短路程为P（vi）；若vi标以Ｔ标号T（vi），则说明v１到vi路程的上界为T（vi），以后需逐步修改，直至得到P（vi）为止。一旦终点vn标上P（vn），则说明已求得从v１到vn的最短路程为P（vn）。上一页下一页返回２．２最短路及其求法２.２.２列表法列表法的思路和Ｐ-Ｔ标号法的思路相同，列表法是解决有负数的赋权有向图最短路的有效算法。设Ln为v１到vn的最短路程，Ln－１为v１到vn－１的最短路程，依此类推。一般地，若已知ωij，则Lj必须满足下列方程为了求得这个方程的解L１，L２，…，Ln，可用如下的递推公式：首先令上一页下一页返回２．２最短路及其求法对t＝２，３，…，有当进行到某一步，例如第k步时，对所有j＝１，２，…，n上一页返回２．３网络的最大流求法设在有向图D＝（V，A）中给定一点为发点（记作vs）和另一点为收点（记作vt），其余的点叫中间点，并赋予每一有向边（vi，vj）一个c（vi，vj）（简记为cij），称为该有向边的容量，通常称这样的D为网络，记作其中C为容量集，容量的实际含义是相应边的承受能力。如图２．６就是一个网络。２.３.１可行流的概念网络上的流指定义在有向边集A上的一个函数下一页返回２．３网络的最大流求法其中f（vi，vj）为有向边（vi，vj）上的流量，简记为fij。如图２．７所示为网络图２．６上的一个流，边旁数字为（cij，fij）。设f是网络D＝（V，A，C）上的流，且满足：（１）容量约束条件：对每一有向边（vi，vj）∈A，有０≤fij≤cij；（２）平衡条件：对于一切中间点vi，有流出量等于流入量，即上一页下一页返回２．３网络的最大流求法对于vs，vt点有则称f是D上的可行流，其中v（f）是可行流的流量。可行流一定存在，当网络中所有边的流量均为零时，就是一个可行流。此时，在网络D的一切可行流中，流量最大的一个称为网络的最大流。上一页下一页返回２．３网络的最大流求法２.３.２增广链设网络D＝（V，A，C），fij为（vi，vj）∈A上的流量，（１）若fij＝cij，则称（vi，vj）为饱和边；否则为非饱和边（即fij＜cij）；（２）若fij＝０，称（vi，vj）为零流边；否则为非零流边（即fij＞０）；（３）若μ是D中从发点vs到收点vt的一条链，且定义链的走向是从vs到vt，则链上的所有边被分为两类：一类是其方向与链的走向一致的边，称为正向边；一类是其方向与链的走向相反的边，称为反向边。正向边集合记为μ＋，反向边集合记为μ－，如图２．７中，上一页下一页返回２．３网络的最大流求法设f是D＝（V，A，C）的一个可行流，μ是从vs到vt的一条链，若μ满足条件：第一，在有向边（vi，vj）∈μ＋上，有０≤fij＜cij，即μ＋中每一条边均为非饱和边；第二，在有向边（vi，vj）∈μ－上，有０＜fij≤cij，即μ－中每一条边均为非零流边，则称μ是关于可行流f的一条增广链。上一页下一页返回２．３网络的最大流求法２.３.３网络最大流网络最大流的存在定理：可行流f是网络最大流的充分必要条件为网络中不存在关于f的增广链。网络最大流存在定理为寻找网络的最大流提供了一条明确的思路，首先判断对网络的可行流f，是否存在由vs到vt的一条增广链。其次，若存在增广链μ，可根据下式确定调整量并调整流量，以消除增广链。上一页下一页返回２．３网络的最大流求法于是，得到网络新的可行流f′，重复上述过程，直至得到网络的最大流。对于含有多个发点（或多个收点）的网络，求最大流时，可首先虚设一发点（或收点），该发点（或收点）与相应多个发点（或多个收点）相连接，其边的方向是由虚设发点指向多个发点（或由多个收点指向虚设收点）。其添加边的容量设为＋∞。如图２．１６所示。图２．１６中，vs，vt为虚设的发点和收点，vs１，vs２，…，vsm为原问题的m个发点，vt１，vt２，…，vtn为原问题的n个收点。这样会很方便地通过找增广链的方法求得该网络的最大流。上一页下一页返回２．３网络的最大流求法2.３.４网络的截集与截量设D＝（V，A，C），V被划分为两个非空子集V１和V１，使vs∈V１，vt∈V１，那么把始点在V１，终点在V１的边的全体称为一个截集，并记作（V１，V１）。截集中所有边的容量之和称为该截集的截量，记作C（V１，V１），即有所有截集中截量最小的截集称为最小截集。上一页返回2.4最小费用最大流问题设网络D＝（V，A，C）在（vi，vj）∈A上单位流量耗资bij＞０，求D的最大流f，使f的总耗资b（f）为最小，即利用有向图最短路和网络最大流的求解方法就可以解决这类问题。增广链在求网络的最大流时有两个明显的功能，它的不存在可用来判断当前可行流是最大流；它的存在可用来调整网络的流量，直至获得最大流。可以这样说，网络的最大流流量是在增广链上获得的。由此可见，如果已知f是费用最小的可行流，而μ是关于f所有增广链中费用最小的一条，那么沿着μ调整流量，调整后的新可行流仍是费用最小的（在流量相等的可行流中），按此思路，当得到网络的最大流时，即是最小费用的最大流。对于寻找关于f的最小费用增广链，则需用赋权有向图的最短路来解决。下一页返回2.4最小费用最大流问题为此，我们构造一个赋权有向图W（f），它的顶点集是原网络D的顶点集V，而把D中的每一条边（vi，vj）变成两个方向相反的边（vi，vj）和（vj，vi），并定义边上的权如下：我们约定，权为＋∞的边可以在W（f）图中省略，于是在D中寻找关于f的最小费用增广链就等价于在W（f）中寻找从vs到vt的最短路。上一页下一页返回2.4最小费用最大流问题同时，我们注意到，当所有fij＝０时，为初始最小费用的可行流。计算步骤如下：（１）取f（０）＝０为初始可行流；（２）构造赋权有向图W（f（０）），并求出从vs到vt的最短路；（３）找出在网络中与这条最短路相对应的增广链μ；（４）在μ上施行调整流量的过程，得到新的最小费用可行流f（１）。一般地，①若计算到第k－１次时，得到新的最小费用可行流f（k－１）；上一页下一页返回2.4最小费用最大流问题②构造赋权有向图W（f（k－１）），并求出从vs到vt的最短路；③找出在网络中与这条最短路相对应的增广链μ；④在μ上施行调整流量的过程，其调整量为：调整按（２．１）式进行。上一页下一页返回2.4最小费用最大流问题经过调整流量，我们得到新的最小费用可行流f（k），对f（k）重复上述步骤，直至在赋权图中找不到vs到vt的最短路为止。事实上，那时网络中已不存在从vs到vt的增广链，即取得了最小费用最大流。上一页返回图２．１返回图２．２返回图２．６返回图２．７返回图２．１６返回第３章统筹法及应用３．１网络图３．２时间参数的计算３．３网络计划的优化返回3.1网络图网络图又称箭头图或统筹图，它是计划项目的各个组成部分内在逻辑关系的综合反映，是进行计划和计算的基础。也可以说，统筹法的基础是网络图。网络图分为箭线式网络图和结点式网络图两种。箭线式网络图由带箭头的线加结点组成。箭线代表活动（或工序，作业），结点代表活动的开始和完成。结点式网络图以结点代表活动，以箭线表示各活动之间的先后承接关系。箭线式网络图需要引进虚活动（以虚线表示的），但它的布图清晰明朗，因此使用十分广泛。结点式网络图虽不引进虚活动，但在复杂的网络图中，线条纵横交错，看起来不易一目了然，因此使用较少。在这里我们只讨论箭线式网络图(如图3.1)。下一页返回3.1网络图圆圈和里面的数字表示各事项，就是两个活动之间的交接点，它指明某一项活动的开始或完成，它不占用时间，也不消耗资源。一项规划一般地只有一个总开始（开工）结点和一个总结束（完工）结点。箭线表示活动（工序、作业），符号为“→”。箭线的方向表示活动前进的方向，从箭尾到箭头表示一项活动的开始到终结的过程。活动需要消耗一定的资源，占用一定的时间。有些自然过程虽然不消耗资源，但也要占用时间，如混凝土浇灌后的凝结过程，油漆后的干燥过程等，则在网络图中也要作为一项活动反映出来。活动名称和活动所用时间分别写在箭线旁边。虚活动用虚箭线表示。它表示工时为０，不消耗任何资源的虚构活动。其作用只是为了正确表示工作的前行后继关系。上一页下一页返回3.1网络图３.１.１画网络图的规则把表示各活动的箭线按照先后顺序及逻辑关系，由左至右排列画成图。再给结点统一编号，起始结点表示整个工程的开始（总开始事项），图中最大的数码的结点表示工程结束事项（总完工事项），结点由小到大编号，对任一工序来讲，箭尾结点编号小于箭头结点编号。在绘制网络图时，还要注意以下规则：（１）网络图只能有一个总起点事项，一个总终点事项。图３．２是错误的，因为有①和⑦两个总开工事项，有④、⑥和⑨三个总完工事项。（２）网络图是有向图，不允许有回路，否则将造成逻辑上的错误，使回路上的活动永远到达不了终点。图３．３是错误的，因为③→⑤→⑥→③构成回路。上一页下一页返回3.1网络图（３）两结点之间不允许有两个或两个以上的活动。如图３．４是错误的。（４）必须正确表示工作之间的前行后继关系。如某工程其中的４项活动a，b，c，d的关系为：c必须在a，b均完成之后才能开工，而d只需要在b完工后即可开工，如表示该４项活动的部分画成图３．５是错误的，因本来与a工作无关的工作d被错误地表示为必须在a完成后才能开工。（５）虚活动的运用。虚活动的引进大致有两种情况：一种是先后两个结点之间的工作过程只能代表一项活动，当两个或两个以上的活动具有同一个始点和终点时，需要引入虚活动，予以区别，如图３．１，机械部分维修与电器部分维修属于两个并行活动。上一页下一页返回3.1网络图另一种是为了正确表示各个活动之间的先后承接关系，有时必须引入虚活动，如有一项工程其各个活动之间的先后承接关系如表３-１所示，则它的网络图就如图３．６所示。３.１.２实例一般网络图的绘制可分为三步，我们用某产品投产前全部准备工作来说明。（１）任务的分解。一个任务首先要分解成若干项活动，并分析清楚这些活动之间工艺上和组织上的联系及制约关系，确定各活动的先后顺序，列出活动项目细表，见表３-２。上一页下一页返回3.1网络图（２）绘制网络图。按照明细表中所示的活动，遵循前面的画图规则作出网络图，并在箭线上标出工时，如图３．７。（３）结点编号。事项结点编号要满足前述的要求，即从始点到终点要从小到大编号，对表示任一活动的箭线，箭尾结点编号小于箭头结点编号。编号不一定连续，可留些间隔便于修改和增添活动。上一页返回3.2时间参数的计算计算网络图有关的时间参数，主要目的是找出关键路线。路线是指从网络的始点开始，顺着箭线的方向，中间经过互相连接的结点和箭线，到网络终点为止的一条连线。在一条路线上，把各个活动的作业时间加起来，就是该路线的总作业时间。在所有路线中，总作业时间最长的路线就是关键路线，或叫主要矛盾线。即关键路线是指网络图中需时最长的路线（总起点事项到总终点事项），关键路线决定着网络计划的完工时间。图３．８是一个简单的网络图，从始点１到终点８共有４条路线。下一页返回3.2时间参数的计算这４条路线分别为：可以看出①→②→③→④→⑥→⑦→⑧所需时间最长，它表明整个任务的总完工期为２１周。很明显，这条线上的活动，若有一个迟延一周，整个工作的工期就要推迟一周；若某一活动能提前一周，整个任务就提前一周完成。而不在这条路线上的活动对总工期则没有这种直接影响的关系，如工作②→⑥，可以在①→②工作开始后四周就开始，也可以推迟四周，都不影响总完工期。通常把网络图中需时最长的路线叫关键路线，在图中用红线或粗线或双线画出。上一页下一页返回3.2时间参数的计算关键路线上的活动称为关键活动。要想使任务按期或提前完成，就要在关键路线的关键活动上想办法。网络图的关键路线可以通过时间参数的计算求得。网络图的时间参数包括活动所需时间，结点的最早、最迟时间，工作的最早、最迟时间及时差等。进行时间参数的计算不仅可以得到关键路线，确定和控制整个任务在正常进度下的最早完工期，而且在掌握非关键活动基础上可进行人、财、物等资源的合理安排，进行网络计划的优化。下面介绍各种时间参数的确定和计算方法。上一页下一页返回3.2时间参数的计算３.２.１活动时间t（i，j）的确定活动（i，j）所需工时可记为t（i，j），有以下两种确定方法：（１）确定型。在具备工时定额和劳动定额的任务中，活动的工时t（i，j）可以用这些定额资料确定，有些活动虽无定额可查，但有有关活动的统计资料，也可以利用统计资料通过分析来确定活动的工时。（２）概率型。对于开发性试制性的任务，往往不具备（１）中所讲的资料，对工作所需工时难以准确估计时，可以用三点时间估计法来确定活动的工时。这种方法对每项活动先要作出下面情况的时间估计：上一页下一页返回3.2时间参数的计算a———最快可能完成时间（最乐观时间）；m———最可能完成时间；b———最慢可能完成时间（最悲观时间）。利用三个时间a，m，b，每项活动的期望作业时间可估计为方差为例如，已知某一任务中各项活动的a，m，b值（单位为月），见表３-３的第２，３，４列。求每项活动的平均工时t及均方差σ。上一页下一页返回3.2时间参数的计算解：用公式（３．１）和式（３．２）计算出各项活动的平均工时t和均方差σ，填入表３-３第５，６列中。３.２.２结点时间参数（１）结点的最早时间。结点的最早时间用tE（j）表示，它表明以它为始点的各项活动最早可能开始时间，也表示以它为终点的各项活动的最早完成时间，它等于从始点事项到该事项的最长路线上所有工作的工时总和。结点最早时间可用下列递推公式，按照结点从小到大的顺序逐个计算。设总开工结点编号为①，则，上一页下一页返回3.2时间参数的计算（２）结点的最迟时间。结点i的最迟时间用tL（i）表示，它表明在不影响任务总工期条件下，以它为始点的工作的最迟必须开始时间，或以它为终点的各项活动的最迟必须完成时间。由于一般情况下，我们都把任务的最早完工时间作为任务的总工期，所以结点最迟时间的计算方法为其中tL（j）———与结点i相邻的各紧后结点的最迟时间。结点的最迟时间是从终点事项开始，按编号由大至小的顺序逐个由后向前计算。上一页下一页返回3.2时间参数的计算３.２.３活动的时间参数（１）工作的最早可能开工时间与工作的最早可能完工时间。一项活动（i，j）的最早可能开工时间用tES（i，j）表示，任何一项活动必须在其所有紧前活动全部完成之后才能开始。活动（i，j）的最早可能完工时间用tEF（i，j）表示，它表示工作按最早开工时间开始所能达到的完工时间。它们的计算公式为上一页下一页返回3.2时间参数的计算这组公式也是递推公式。即所有从总开工事项出发的活动（１，j），其最早可能开工时间为０；任一活动（i，j）的最早开工时间要由它所有紧前工作（k，i）的最早开工时间决定；工作（i，j）的最早完工时间显然等于其最早开工时间与其作业时间之和。（２）活动的最迟必须开工时间与活动的最迟必须完工时间。一个工作（i，j）的最迟必须开工时间用tLS（i，j）表示。它表示活动（i，j）在不影响整个任务如期完成的前提下，必须开始的最晚时间。上一页下一页返回3.2时间参数的计算活动（i，j）的最迟必须完工时间用tLF（i，j）表示。它表示工作（i，j）按最迟时间开工，所能达到的完工时间。它们的计算公式为这组公式是按活动的最迟必须开工时间由终点向始点逐个递推的公式。凡是进入总完工事项n的工作（i，n），其最迟完工时间必须等于预定总工期或等于这项活动的最早可能完工时间。任一活动（i，j）最迟必须开工时间由它的所有紧后工作（j，k）的最迟开工时间确定，而活动（i，j）最迟完工时间显然等于本项活动的最迟开工时间加上作业时间。上一页下一页返回3.2时间参数的计算３.２.４时差活动的时差又叫活动的机动时间或缓冲时间。常用的时差有两种。（１）活动的总时差。在不影响任务总工期的条件下，某项活动（i，j）可以延迟其开工时间的最大幅度，叫做该活动的总时差，用R（i，j）表示。其计算公式为即活动（i，j）的总时差等于它的最迟完工时间与最早完工时间之差。显然R（i，j）也等于该工作的最迟开工时间与最早开工时间之差。上一页下一页返回3.2时间参数的计算（２）活动的单时差。活动的单时差是指不影响紧后工作的最早开工时间的条件下，此工作可以延迟其开工时间的最大幅度，用r（i，j）表示。其计算公式为即单时差等于其紧后工作的最早开工时间与本项活动的最早完工时间之差。上一页下一页返回3.2时间参数的计算３.２.５时间参数的图上计算法网络图时间参数的计算方法很多，如图上计算法，表上计算法，矩阵法以及使用计算机计算等。先讨论图上计算法。例１资料数据见图３．９，试运用图上计算法求该网络的各项时间参数。（１）先计算结点的时间参数。结点的最早时间从总开工结点①开始，利用公式（３．３），在图上由编号小→大逐个计算，如上一页下一页返回3.2时间参数的计算把计算结果标入图中相应结点编号旁方框的上部，然后计算结点的最迟时间，从总完工事项⑩，由后向前利用公式（３．４）逐个进行计算，当任务给定完工期限时，结点⑩的最迟时间就等于规定期限，否则就等于刚计算出的事项⑩的最早时间３２。如上一页下一页返回3.2时间参数的计算在图上边计算边把计算结果标入框的下方。结点时间参数计算结果见图３．１０。（２）活动时间参数的计算。在图上计算活动的时间参数时，利用公式（３．５），式（３．６）计算出活动的最早开工时间和最迟开工时间填入图中。图中标有活动的工时，所以活动的最早开工时间及最迟完工时间极易算出。与计算结点的时间参数类似，先用公式（３．５）从始点开始，逐个计算活动的最早可能开工时间tES（i，j），标入箭杆上方的菱形方框的上半部。然后从终点由后向前按公式（３．６）逐个计算最迟必须开工时间tLS（i，j），填入菱形方框的下半部。如：上一页下一页返回3.2时间参数的计算而且有：上一页下一页返回3.2时间参数的计算计算结果及过程见图３．１１。然后用公式（３．７）计算总时差填入图３．１１中［］处。由于图３．１１上没有tEF（i，j）只有tES（i，j）和t（i，j）。所以将公式（３．８）变形为用此公式来计算工作的单时差，填入图３．１１中（）内，最后结果见图３．１１。上一页下一页返回3.2时间参数的计算由关键路线的定义可知，这条路线上的活动在时间上没有回旋的余地，即每个关键活动应满足“最早开工时间等于最迟必须开工时间”的条件。而非关键活动则有缓冲时间。所以总时差为０的路线就是关键路线。检查图３．１１中各活动的总时差，得到其关键路线为：①→②→③→④→⑤→⑥→⑦→⑨→⑩，总工期３２周。通过这个例子还可以进一步了解总时差与单时差的区别。我们把图３．１１中部分活动的路线取出来观察，如图３．１２。上一页下一页返回3.2时间参数的计算活动（１，７）有单时差１３，如果把活动（１，７）拖至１３周开工，对它后面的活动最早开工时间及时差等没有影响，对整个工期也没有影响。而只有总时差没有单时差的活动则不然，如活动（７，８）有总时差１而没有单时差，如果让活动（７，８）推迟１周于２４周开工时，虽然总工期不受影响，但其后面的活动的最早时间及时差都要受影响，变为图３．１３的情况。所以使用时差来调整工作时应尽量先用单时差。上一页返回3.3网络计划的优化通过画网络图并计算网络时间参数，已得到一个初步的网络计划。而网络计划技术的核心却在于从工期、成本、资源等方面对这个初步计划作进一步的改善和调整，以求得最佳效果。这一过程，就是网络计划的优化。不同的优化目标有不同的优化方法，下面给出了网络优化的几种方法。一是把串联活动改成并行活动或交叉活动。为了缩短整个任务的完工期，达到时间优化的目标，可以研究关键路线上串联活动有无能改为平行或交叉进行的活动，以缩短工期。二是利用时差。由于网络图中非关键路线上活动都有时差，所以这些活动在开工时间上，具体作业时间上都有一定的弹性。为了缩短任务的总工期，可以考虑放慢非关键活动的进度，减少这些活动的人力、资源，转去支援关键活动，以使关键活动的作业时间缩短来达到目的。下一页返回3.3网络计划的优化三是有限资源的合理分配。一项任务的可用资源，一般情况下都是有限的，因此时间计划必须考虑资源问题。如讨论在有限资源情况下使工期最短问题。３.３.１时间与资源优化以人力资源为例。图３．１５所示的网络图，已计算出关键路线１→２→３→５→６，总工期为１１天。箭杆上标注数字为活动每天所需人力数（假设所有活动都需要同一种专业工人）。画出带日程的网络图及资源动态曲线，如图３．１６所示（图中虚线为非关键活动的总时差）。上一页下一页返回3.3网络计划的优化由图３．１６可见，若按每道工作的最早开工时间安排，人力需求很不均匀，最多者为第四开工时，２０人／日，最少为第八至第十一开工时，１人／日。这种安排即使在人力资源充足条件下也是很不经济的。现假设资源有限，每天可用人力为１０人，下面进行计划调整，希望能不延迟总工期或尽量少延迟。调整的基本规则是：（１）尽量保证关键活动的日资源需求量。（２）利用非关键活动的时差错开各项活动的使用资源时间。（３）在技术章程允许条件下，可适当延长时差大的活动时间，或中断某非关键活动，以减少日总需求量。上一页下一页返回3.3网络计划的优化具体方法是按资源的日需求量划分时间段逐步从始点向终点进行调整，本例中，第一时间段为［０，２］，需求量为１８人／日，在调整时要对本时间段内各项活动按总时差的递增顺序排队编号，如：活动（１，２），总时差０，编号为１＃活动（１，４），总时差１，编号为２＃活动（１，６），总时差７，编号为３＃对编号小的优先满足资源需求量，当累计和超过１０人时，未得到人力安排的活动应移入下一时间段。本例中活动（１，２）与（１，４）人力日需求量为９，而活动（１，６）需求９人／日，所以应把（１，６）移出［０，２］时间后开工，见图３．１７。上一页下一页返回3.3网络计划的优化接着调整［２，３］时间段。在编号时要注意，如果已进行的非关键活动不允许中断，则编号要优先考虑，把它们按照新的总时差与最早开工时间之和的递增顺序排列，否则同第一段的编号规则。本例中（１，４）为已进行中活动，假设不允许中断。而（２，３）为关键活动，（１，６）还有时差５天，则编号顺序为：工作（１，４），总时差１，编号为１＃；工作（２，３），总时差０，编号为２＃；工作（１，６），总时差５，编号为３＃，累计所需人力资源数，工作（１，４）与（２，３）共１０人／日。所以工作（１，６）要移出［２，３］时间段。调整结果见图３．１８。上一页下一页返回3.3网络计划的优化以后各时间段做类似处理，经过几次调整，又得图３．１９。此时人力资源的日需求量已满足不超过１０人的限制，总工期未受到影响，必要时总工期可能会延迟，这种方法也可用于多种资源分配问题。３.３.２时间与成本优化项目或任务的成本一般包括直接费用和间接费用两部分。直接费用是完成各项活动直接所需人力、资源、设备等费用，为缩短活动的作业时间，须采用一些技术组织措施，相应会增加一些费用，在一定范围内，活动的作业时间越短，直接费用越大。间接费用则包括管理费、办公费等，常按任务期长短分摊，在一定条件下，工期越长，间接费用越大。它们与工期的关系如图３．２０所示：工期缩短使直接费用增加而间接费用减少，总成本是由直接费用和间接费用相加而得。通过计算网络计划的不同完工期相应的总费用，以求得成本最低的日程安排就是“最低成本日程”，又称“时间与成本优化”。上一页下一页返回3.3网络计划的优化直接费用与活动所需工时关系，常假定为直线关系，如图３．２１，工作（i，j）的正常工时为Dij，所需费用Mij，特急工时为dij，所需费用mij，工作（i，j）从正常工时每缩短一个单位所需增加的费用称为成本斜率，用cij表示。如某工作正常工时为５天，费用为６００元；按特急工时３天所需费用为９００元计算，即每缩短一天需增加费用１５０元。上一页返回图３．１返回图３．２返回图３．３返回图３．４返回图３．５返回表３-１返回图３．６返回表３-２返回图３．７返回图３．８返回表３-３返回图３．９返回图３．１０返回图３．１１返回图３．１２返回图３．１３返回图３．１５返回图３．１６返回图３．１７返回图３．１８返回图３．１９返回图３．２０返回图３．２１返回第４章线性规划４．１线性规划所研究的问题４．２线性规划问题的数学模型４．３二维线性规划的图解法４．４线性规划数学模型的标准化４．５单纯形方法４．６线性规划应用实例返回4.1线性规划所研究的问题运输问题中寻求货运量最多而运费最省的最佳运输方案；生产中寻求产量高而消耗低的最优生产组织方案；基建中寻求投资少收益大的最优经济计划方案以及合理下料等优化问题均属线性规划所研究的范畴。例１要从A１，A２，A３三个产地运送产品到四个销地B１，B２，B３，B４，产量、销量及运价如表４-１所示。问如何调运才能使运费最省？假定运费与运量成正比，就是说，如果运１个单位产品的运费是c，那么运x个单位产品的运费就是cx。在这种情况下，不同的运输方案，运费就可能不同。下一页返回4.1线性规划所研究的问题如表４-２，A１向B２运送５个单位产品，向B４运送４个单位产品；A２向B１运送３个单位产品，向B４运送２个单位产品；A３向B２运送３个单位产品，向B３运送４个单位产品。这个方案既使得产地的产品全部运送了出去，又保证了四个销地各自的需求。此时运费为：５×９＋４×７＋３×１＋２×２＋３×４＋４×２＝１００如果A１，A２两地的产品运输计划作一调整，如，A１运往B１３个单位产品，A１运往B４６个单位产品，A２的产品全部运往B２，如表４-３所示。上一页下一页返回4.1线性规划所研究的问题此时运费为：３×２＋６×７＋５×３＋３×４＋４×２＝８３从两个运输方案的运费可以看出，后一种方案比前一种节省运费１７。当然还有很多种运输方案，如表４-４就是其中的一个方案。此时运费为：３×２＋６×９＋２×３＋３×４＋１×２＋６×５＝１１０运输方案非常多，用怎样的方法找到运费最省的运输方案呢？我们可以把这个问题用数学的形式表示出来。假设xij表示从Ai运往Bj的产品数量，即x１１，x１２，x１３，x１４分别表示从A１运往B１，B２，B３，B４的产品数量；x２１，x２２，x２３，x２４分别表示从A２运往B１，B２，B３，B４的产品数量；x３１，x３２，x３３，x３４分别表示从A３运往B１，B２，B３，B４的产品数量。上一页下一页返回4.1线性规划所研究的问题从A１，A２，A３分别运往B１，B２，B３，B４的产品数量的总和应该分别等于９，５，７，所以这些变量应该满足：而销往B１，B２，B３，B４的产品数量应该分别为３，８，４，６，所以xij还应满足：上一页下一页返回4.1线性规划所研究的问题另外，xij是所运产品数量，不能是负数，所以还有约束条件：xij≥０（i＝１，２，３；j＝１，２，３，４）（４．３）除了满足上述要求以外，还应该使运费最省。总运费应该是所有产地到销地的运量分别乘以各自的运价再求和，若用Z表示总运费，则有总之，我们要找的是xij（i＝１，２，３；j＝１，２，３，４），在满足公式（４．１）、式（４．２）、式（４．３）的条件下，使Z达到最小。综合上述，即求xij，满足：上一页下一页返回4.1线性规划所研究的问题上一页下一页返回4.1线性规划所研究的问题并且使达到极小。用xij表示从Ai运往Bj的产品数量，则xij应满足：上一页下一页返回4.1线性规划所研究的问题并且使达到最小。其中，式（４．４）表示从Ai发出的物资总量是ai，式（４．５）表示Bj处得到的物资总量是bj。上一页返回4.2线性规划问题的数学模型线性规划问题是具有下列形式的数学问题：求x１，x２，…，xn，满足条件式（４．７）且使Z＝c１x１＋c２x２＋…＋cnxn达到最大（或最小）。下一页返回4.2线性规划问题的数学模型其中，xj（j＝１，２，…，n）称为决策变量，式（４．７）称为约束条件，Z称为目标函数。线性规划问题中约束条件式（４．７）左端及目标函数都是xj（j＝１，２，…，n）的线性函数。决策变量、约束条件、目标函数构成了线性规划的数学模型。线性规划数学模型一般表示为：上一页下一页返回4.2线性规划问题的数学模型其中，cj（j＝１，２，…，n）称为价值系数；bi（i＝１，２，…，m）称为限定系数；aij（i＝１，２，…，m；j＝１，２，…，n）称为技术系数。线性规划的数学模型还可以表示为如下两种形式：向量形式：上一页下一页返回4.2线性规划问题的数学模型其中，C＝称为价值系数向量；X＝称为价值系数向量；称为技术系数分向量；b＝称为限定系数向量。矩阵形式：上一页下一页返回4.2线性规划问题的数学模型其中，称为技术系数矩阵，C、X、b同式（４．９）。上一页返回４．３二维线性规划的图解法对于含有两个变量的线性规划问题（如４．１节中例３），其求解若用图像方法则既直观又方便，而且可以从中观察到线性规划问题解的一些特性。下面以４．１节中的例３来讨论图解法的求解过程。例３的数学模型为：下一页返回４．３二维线性规划的图解法选取x１为横坐标，x２为纵坐标，建立直角坐标系，先图示约束条件：①由x１≥０，x２≥０显然知问题的解一定在第一象限；②在条件（１）（２）（３）（４）为等式时，作出相应的直线如图４．１所示。③（１）～（５）确定了区域D，称为可行域，可行域中任一点均满足约束条件，称为可行解，二维线性规划问题的可行域为一凸多边形。（凸多边形：设D为一多边形，若D中任意两点的连线仍在D区域中，则称D为凸多边形。如OABCFE。）再图示目标函数（Z＝４x１＋５x２）：上一页下一页返回４．３二维线性规划的图解法具体做法是：①当Z＝０时，作直线４x１＋５x２＝０。（６）②当Z值连续增大时，得到以Z为参数的平行直线族x可以看出，当直线（７）沿其法线方向远离原点，向直线（６）右上方移动时，所到之处，凡落在D中的线段，其上每一点均具有同一目标函数值。根据本题目的实际情况，直线（７）离原点越远，即x１↑，x２↑，则Z值增大。上一页下一页返回４．３二维线性规划的图解法③使目标函数达到最大的可行解称为该线性规划问题的最优解。该点如果存在，一定在可行域D的边界上。直线（７）最终与可行域D交于C点，此时，Z＝３５，x１＝５，x２＝３，即该线性规划问题的最优解为：上一页返回４．４线性规划数学模型的标准化4.４.１线性规划数学模型的标准化形式下一页返回４．４线性规划数学模型的标准化若约束条件等式右边数小于零，可在等式两端同乘以（－１）。由线性规划数学模型的一般标准形式可写出和式、向量、矩阵表示的标准模型如式（４．１２）、式（４．１３）、式（４．１４）所示。上一页下一页返回４．４线性规划数学模型的标准化其中C，X，Pj，A，b同式（４．９）、式（４．１０）。４.４.２线性规划数学模型的标准化方法（１）目标函数标准化。若原问题求目标函数极小值，即上一页下一页返回４．４线性规划数学模型的标准化则有ｍａｘZ＝c１x１＋c２x２＋…＋cnxn，当我们求到ｍａｘZ后，只要前面加负号即可得到ｍｉｎZ′。（２）约束条件标准化。若不等式为“≤”形式，可在不等号左端加入非负变量x狊（称为松弛变量），使原不等式变为等式；若不等式为“≥”形式，则可在不等式左端减去一非负变量x狋（称为剩余变量，也可叫松弛变量），使原不等式变为等式；上一页下一页返回４．４线性规划数学模型的标准化若某一变量xj为自由变量，则可另设两个非负变量yj，zj，使得并将约束条件和目标函数中的所有xj换为yj－zj。若某变量xj≤a，xi≥b，可设则yj≥０，yi≥０，并用a－yj，yi＋b换掉数学模型中的xj及xi。上一页返回４．５单纯形方法４.５.１线性规划问题解的几个概念（１）可行解：我们称满足约束条件的解为线性规划问题的可行解。（２）可行域：可行解的全体称为线性规划的可行域。二维线性规划问题的可行域是一凸多边形，多维线性规划问题的可行域是一凸多面体，统称为凸集。凸集：设有点集D，X（１），X（２）为D中任意两点，X（３）是X（１），X（２）连线上的任意一点，且下一页返回４．５单纯形方法若X（３）也属于D，则称D为凸集。（３）最优解：使目标函数达到极值的可行解称为线性规划问题的最优解，此时的目标函数值称为最优值。（４）基：设约束条件方程组的系数矩阵Am×n（n≥m），其秩狉（A）＝m，则A中m×m阶非奇异子阵Bm×m称为线性规划问题的一个基。４.５.２单纯形方法运用线性规划的典式和基础可行解的概念可以求解线性规划问题。下面通过例题进一步讨论这个过程。上一页下一页返回４．５单纯形方法例９用单纯形方法求解下列线性规划问题解：由约束条件可得：上一页下一页返回４．５单纯形方法（１）选B＝，则上述问题的典式为：上一页下一页返回４．５单纯形方法令x１＝０，x２＝０，得基础可行解X（１）＝（０，０，３０，８，７，５）Ｔ，此时，目标函数Z＝０。由目标函数典式可以看出，非基变量x１，x２的检验数（即目标函数典式中非基变量的系数）均大于零，故X（１）不是本线性规划问题的最优解。而当x１或x２取某一正值时，目标函数显然会增大。设x２变为基变量，x１仍为非基变量，设x１＝０，则有上一页下一页返回４．５单纯形方法原来的四个基变量中一个须变为非基变量，随着x２的增大，上式中哪个变量首先变为零，则该变量应作为换出变量。由当x２＝５时，x３，x４，x５均大于零，只有x６＝０，故x６由基变量变为非基变量。上述过程，可用θ规则选择换出变量，即上一页下一页返回４．５单纯形方法因此，x６应为换出变量。（２）选则x２，x３，x４，x５为新的基变量，x１，x６为新的非基变量，写出典式如下：上一页下一页返回４．５单纯形方法令x１＝０，x６＝０，得基础可行解X（２）＝（０，５，５，３，７，０）Ｔ，Z＝２５。由典式可以看出，σ１＝４＞０，故X（２）仍非线性规划问题的最优解。令x６＝０，即x６仍作为非基变量，x１为换入变量，有根据θ规则：上一页下一页返回４．５单纯形方法故x３为换出变量。（３）再选新基其典式为上一页下一页返回４．５单纯形方法令x３＝０，x６＝０得基础可行解由典式可看出，x６的检验数σ６＞０，故x６应为换入变量，将哪一个变量换出呢？设x３仍为非基变量，且令x３＝０，我们有上一页下一页返回４．５单纯形方法根据θ规则，故x４为换出变量。（４）选基其典式为上一页下一页返回４．５单纯形方法上例中，如（２）选x１为换入变量，令x２＝０，即仍为非基变量，则会得到基础可行解X＝（７，０，９，１，０，５）Ｔ；再选x２为换入变量，得到X＝（７，１，４，０，０，４）Ｔ；最后选x５作为换入变量，得到最优解X＝（５，３，０，０，２，２）Ｔ。把该问题的基础可行解与４．３图解法中该线性规划可行域凸集的顶点比较，可以看出，线性规划问题可行域凸集的顶点与其基础可行解是一一对应的。此结论对多维线性规划同样适用，且线性规划问题如果存在最优解，一定可以在可行域凸集的顶点（即基础可行解）中找到。况且线性规划问题约束条件的系数矩阵Am×n是有限的，基的个数也一定有限，基础可行解的个数有限，故从基础可行解中一定可以找到最优解（如果存在）。上一页下一页返回４．５单