第一章 离散最优化算法

1、第一章 线性规划线性规划是运筹学的重要分枝之一，诞生于第二次世界大战期间。战后得到了迅速发展。它的应用范围极为广泛。从农业上的作物轮作计划到大规模的军事行动计划；从港口间的船艇运行路线到物流的分配。研究者们把这些似乎无关的问题，统一个到同一个数学框架线性规划。GBDantzig给出简洁求解方法单纯形方法（Dantzig，GB，1963）实际上，上个世纪三十年代中期，前苏联的数学家康特洛维奇已在生产组织和计划中，提出了一些数学方法。其中就含线性规划模型，并给出了其求解线性规划的一个方法，称之为解乘数法，尽管解乘数法在理论上和应用上都没有单纯形算法好，但他是首先用线性规划去解决实际生产问题的人之一

2、。他在1939年的著作生产组织与计划中的数学方法中，讲述了九个应用问题。由于高速的电子计算机的出现，线性规划的应用越来越广泛。人们发现对某些特殊的线性规划实例16，单纯形算法的迭代步数随变量个数的增加而以指数的速度增长。因此，从理论上看，单纯形算法所能解的线性规划，其变量个数不能太多。由此引起了对线性规划的算法研究的重视，自上世纪七十年代中期开始，出现了一系列新的方法。但这些算法都比较复杂，而且在变量个数不是太多的情况下，其计算的平均速度未必比单纯形算法好，所以本书对这些新的算法省略了。本章重点地介绍了单纯形算法、修正的单纯形算法、对偶单纯形算法和原始对偶算法。实际上只要掌握了单纯形算法及其原

3、理，其它几个算法就容易理解了。本章最后提到了椭球算法，其目的是说明线性规划问题是有多项式时间算法的。本章的内容与线性代数有关，对代数不太熟悉的读者，可以先复习一下线性代数的基本知识。11 线性规划的基本概念要回答什么是线性规划，先看几个线性规划的例子：例111(运输问题) 设某种产品有m个产地：A1，A2，Am，其产量分别为a1，a2，am。该产品有n个需求地：B1，B2，Bn，其需求量分别为b1，b2，bn。已知从第i个产地Ai运单位产品到第j个需求地Bj的费用为Cij元。如何对产品进行调配，使在满足供需要求的情况下，使总的运费最小？这里我们假定，即供需平衡。这一问题可化为下述数学模型： (

4、111) (112) (113)xij0，i1，2，m，j1，2，n (114)其中xij表示自产地Ai运往需求地Bj的产品数量；式(111)表示总的运费要求取最小值；式(112)表示从产地Ai运出去的数量等于Ai产地的产量；式(113)表示需求地Bj的需求量，等于运往Bj的数量；式(114)表示运送的数量非负。这个模型表示在满足供需关系式求(112)(114)条件下，求一组xij，使式(111)达到最小，这就是例111所要求的调运方案。例112(资源分配) 某工厂现有m种资源，第i种资源的数量为bi，i1，2，m。用这m种资源可以生产n种产品。已知生产单位第j种产品需第i种资源的数量为aij

5、，i1，2，m，j1，2，n。从中可获利cj元。问题是在现有资源的条件下，各种产品各生产多少才可能使总的利润最大？若用xj表示第j种产品生产的数量，那么上述问题可表示为 (115)，i1，2，m (116)xj0，j1，2，n (117)上述两个例子，虽然问题不同，但其数学模型的实质是相同的，都是在一组线性等式和（或）不等式约束下，求一个线性函数的极值（最大或最小值），这就是所谓的线性规划。从外形上看，线性规划可以是各种各样的，我们把下述的线性规划称为标准形式：，i1，2，mxj0，j1，2，n我们称xj为变量，为目标函数，而bi和xj0，i1，2，m；j1，2，n为约束条件。任何一个线性规划

6、问题都可以化为标准形式。比如，若某个约束条件为，则可以引进一个非负变量yi，用和yi0代替；同样，对，可用和yi0代之。我们称这样的yi为松弛变量。若线性规划中某个变量xj不要求非负，则可做一个代换，用代入目标函数和约束条件中，并增加约束和。若目标函数为求最小，则改为求最大并把目标函数的系数变号，即求改为。为表述简单，通常我们用向量形式表示：max CTX(LP) AXbX0其中C（c1，c2，cn），b（b1，b2，bm）T，A（P1，P2，Pn）且P（a1j，a2j，amj）Tx0表示x的每一分量xj0，j1，2，n。这c，bi和aij通常取自于实数域；但在实际中经常取自于有理数域或整数集

7、。有时为方便，把线性规划也写成下述形式：max CTXxj0，j1，2，n或 max CTXAiXbi (i1，2，m)其中Ai(ai1，ai2，ain) 表示A的第i行。满足约束条件的X称为可行解，使目标达到最大的可行解，称之为最优解，最优解对应的目标值，称之为最优值。我们始终假定A是mn阶矩阵，nm且A的秩为m。由A的m个线性无关的列组成的矩阵，如B(PJ1，PJ2，PJm)，称为A的一个基，基中的列称为基列，基列对应的变量称为基变量；不在基里的列称为非基列，非基列对应的变量称为非基变量。对于A的任一个基B（PJ1，PJ2，PJm），那么A分为两部分：A=（B，N），相应地X和C也分为两部

8、分XT(，)，CT(，)。其中N表示非基列部分，XB和XN分别表示基变量向量和非基变量向量，因此，给定一个基B，（LP）可重写为Max+BXB+NXNbXB0，XN0对于基，那么方程组BXBb有唯一的解XBB1b，若B1b0，则称B为可行基，那么对应的解XBB1b和XN0称为基可行解。在所有基可行解中使目标值达到最大的基可行解称为基最优解，而对应的基称为最优基。设是可行基，那么由约束条件BXBNXNb可以得 XBB1bB1NXN。将它代入目标函数，则有 (11)（）称为关于基的检验数向量。由些可见，当Pj为基B中的列时，则检验数，显然，对应可行基B的基可行解的目标值为。由最优解和基最优解的定义

9、可知，最优解对应的目标值，不小于基最优解对应的目标值，进而，我们将证明二者相等。为此需要如下的一些基本概念。引理111 设Xo是线性规划问题（LP）的一个可行解，则Xo是基可行解，当且仅当Xo的非零分量所对应A的列线性无关。证明 必要性由基可行解的定义立即可得。充分性：不失一般性，设0，0，0；而对一切jk，0。由假设知，P1，P2，Pk是线性无关的。因为A的秩为m，所以km。当km，（P1，P2，Pm）就是一个基，而Xo1，Xo2，Xom就是的唯一解，从而由基可行解的定义知Xo为基可行解。当k0，令定义则x*是（LP）的一个可行解。事实上，由的选取保证了对一切j1，2，k，其次，因此x*是可

10、行解。进而，由的选取知，必有某一下标r，使，从而，即可行解x*比xo的正分量的个数至少小1。这与xo的假设矛盾。这就证明了xo是基可行解。由引理12可见，一个线性规划问题若有最优解，则必有基最优解。下面的定理告诉我们基最优解一定是最优解。定理113 一个线性规划，若有最优解，则最优解一定能在基可行解中找到。证明 设Xo是一最优解，并且它是所有最优解中含有非零分量个数最小的最优解。我们将证明Xo就是基可行解。假如Xo不是基可行解，设它的非零分量为xo1，xo2，xok，那么由引理11知P1，P2，Pk线性相关，即存在非全为零的数1，2，k，使首先我们证明对这组j必有 （1110）事实上，对充分小

11、的正数，令 （1111）则显然X（1）和X（2）是两个可行解，从而由此可得式（1110）。然后，模仿引理12的证明，不妨设有某个j0，取，则由式（110）定义的X(1)是可行解，并且X(1)的非零分量的个数比Xo的非零分量的个数至少小1。另一方面，由式（1110）得即X(1)也是最优解，由于X(1)比Xo的非零分量个数少，故与X(0)的假设矛盾。这个定理说明，求（LP）的最优解，只需在（LP）的基可行解中找即可，而（LP）的可行基的个数最多为个，因此（LP）的最优解可在有限个可行解中找到。然而，当n较大时，很大，实质上它是一个指数函数，因此，用遍数可行基的方法找出（LP）的最优解是不可行的。基

12、于定理113，GBDantzig 于1947年提出了搜索基最优解的方法单纯形算法。12单纯形算法单纯形方法分两个阶段，第一阶段是寻求一个可行基及基可行解；第二阶段是从一个可行基出发进行迭代，即从一个可行靠基迭代到下一个可行基，使其基可行解的目标函数值逐步增加，直到某一个可行基B，使其检验数向量为止。我们先叙述单纯形算法的第二阶段，然后再讨论如何寻求第一个可行基。假如已知B(PJ1，PJ2，PJm)是（LP）的一个可行基，那么相应地A，C和X被划分为A（B，N）CT（CTB，CTN）XT（XTB，XTN）。对A的每一列Pj，令， bojCTBB1Pjcj，j1，2，n而，booCTBB1b， 单

13、纯形方法计算步骤：Step1 若对一切j1，2，n，boj0，则步骤终止。XBB1b，XN0为（LP）的最优解，否则选取下标S，使Sminj|boj0，b3161，故而Jr5，r3(一般Ji表示第i个约束方程中基变量的下标，如J35表示第3个约束方程中基变量为x5)，用Pi列替换B中列P5，得到新的可行基为（P3，P4，P1），它对应的单纯形表为0007010001100Step1 b020时，则bos0。这样每次得到的基可行解都是不同的。由于基可行解的个数，所以单纯形算法在有限步内结束。然而当0时，即某些bio0，基可行解可能不变，也就是说几个可行基可能确定同一个基可行解。此时基可行解称为是

14、退化的。由于单纯形算法是从一个可行基迭代到下一个可行基，而不是从一个基可行解迭代到下一个基可行解，所以当问题退化时，可能出现可行基循环，而循环过程中目标值不变，这样永远也得不到最优解，但是在我们的上述算法中，使用了Bland的最小下标法则，从而避免了可行基循环的发生，因此这个单纯形算法在有限步内是能找到最优解，或者判定无有界最优解。定理（121） 上述单纯形算法能在有限步内结束，或者找出最优解，或者判定无有界最优解（证明见BlandRG1977）。上述单纯形算法是从可行基开始的，有的问题（如上述例子）有明显的可行基，但这仅是个别情形。一般地说，必须设法找出一个可行基，下面介绍寻求第一个可行基的

15、两个种方法：人造基方法和大M方法。为叙述方便，假设标准形（LP）中约束条件的右端常数向量b0，因为若有某个分量bi0，则在该式两端乘以1便可。所谓人造基方法，是先解（LP）的一个辅助问题：（LPS）其中e是每个分量都为1的m维列向量；y是新引进的一个m维的变量向量，也称为人造变向量，Im是mxm的单位矩阵。由于b0，显然Im是（LPS）的一个可行基，因此可以用上述单纯形方法求解。设其最优解为（），若其对应的最优值小于0，那么原问题（LP）无解，因为若（LP）有可行解，那么（LPS）的最优值必为0。因此，基最优解（）的目标值必为0，此时必有0，而（，0）为（LPS）的基最优解。这里有两种可能：所

16、有的都是非基变量；此时为原问题（LP）的基可行解，即有了（LP）的一个可行基，从而可以用单纯形算法求解（LP）；另一种情形是某些是基变量，此时由于0，可用所在的方程中的任一个非基变量xs简换，从而得到（LP）的新的基可行解，其目标值仍为0，用这样的方法可得到不含的基可行解，从而可利用单纯形算法开始求解（LP）。例12 maxx1x2x3x1x26x32x1x22x31xj0，j1，2，3先解辅助问题maxx4x5x1x26x3x42x1x22x3x51xj0，j1，2，3，4，5显然B(P4，P5)为可行基，对应的单纯形表为-20-800-302-402-10001101-161020-241

17、-1101112011112011120此时辅助问题已得最优解: ，并且x4和x5均为非基变量，从而是原问题的基可行解，而B(P3，P1)是原问题的可行基。对应于可行基B(P3，P1)的原问题单纯形表为0000010112010至此已求出原问题的解。上述过程的前三个表是求解辅助问题，称之为第一阶段，后两个表是在前一阶段找出的可行基的基础上，求解给定的问题，称之为第二阶段。这就是所谓的单纯形算法的两阶段方法。上述两阶段方法也可合在一起去做，称之为大M方法。设M是充分大的正数，所谓大M方法是用单纯形算法直接求解问题：maxCTxMeTyAxImybx，y0由于M足够大，所以当（LP）有解时，y必须

18、为0，即得到的最优解（）中，0，从而就是（LP）的最优解。如果的某些分量不为0，则原（LP）问题无解，算法就结束了。上述的单纯形算法是列表计算的，因此要存储一个（m1）（n1）的一个表。实际上，我们从单纯形算法可看出；我们只要保存一个逆矩阵B1，那么整个这张表中的元素均可计算出来，如：目标值为B1b，检验数bojCTBB1Pjcj，表中第j列（b1j，b2j，bmj）TB1Pj，j1，2，n（b10，b20，bm0）TB1b因此，当需要哪一列时，很快就会计算出来，关键问题是当有一个可行解B和B1时，如何导出下一个可行基的逆矩阵。若能简单地计算出，那么就可以减少许多不必要的计算，而又不增加太多的

19、计算，同时减少了存储量。我们先看一下如何由导出能简单地计算出，假设有可行基B(PJ1，PJ2PJm)，当用Ps列替换PJr列后的基为，即（PJ1PJr1，PS，PJr1，PJm）。设则有因此，若已知，则很容易求出。现在把单纯形表的表上算法，可改为逆矩阵形式的算法，也称之为修正的单纯形算法。修正的单纯形算法：设B（PJ1，PJ2PJm）是可行基，B1(bij)Step1 计算T1：CTBB1Step2 若对一切j1，2，n，若有T1PjCj0则算法终止，XBB1b XN0，为最优解，否则，取bosT1PSCS0且对一切j0 b130Step4 计算求 Jr5，r3Step5 求 置BStep1

20、其中(0，0，2)Step2 bo1T1P1C10 bo2T1P2C2 0有cj证明 必要性。 由X和Y分别为（LP）和（DLP）的最优解，所以由定理15有OYTbCTXYTAXCTX。由于Y是（DLP）的可行解，故YTPjcj0。又因xj0。所以对每一个j1，2n，由（YTPjcj）xj0可知，若xj0，则必有YTPjcj。充分性 由xj0推出YTPjcj，从而有，故由定理131知，X和Y分别是（LP）和（DLP）的最优解。14 对偶单纯形算法（LP）的一个基B，若满足B1ACT0，则称B是（LP）的对偶可行基。显然，若在（DLP）中令YTB1，则YT是（DLP）的可行解。单纯形算法是从一个

21、可行基开始，由一个可行基迭代到另一个可行基，直到某一个可行基，而也是对偶可行基为止。对偶单纯形算法从一个对偶可地基开始，从一个对偶可行基迭代到另一个对偶可行基，直到某一个对偶可行基，而也是可行基为止。由此可见，单纯形算法和对偶单纯形算法是从两条不同的路线到达了同一终点。具体算法如下：假如已有（LP）的一个对偶可行基B，那么与单纯形算法类似，A，C和x被划分为A(B，N)，CT(，)，XT(，)，对A的每一列Pj，令， B1PjCjboj，booB1b，记B（，）。由于B是对偶可行基，所以检验数boj0，j1，2，n。有了第一个对偶可行基后，对偶单纯形算法可叙述如下：Step1 若对一切i1，2

22、，m，bio0，则得最优解，算法结束。Step2 设Jrmin Jio| bio 0，若对一切j1，2，n有brj0，则问题无解，算法结束。Step3 计算取，用Ps替换对偶可行基B中的列，这就得到了一个新的对偶可行基。如此同时计算： j0，1，2，n，0irm，0jn置B bijij，0im，0jn，返回Step1对偶单纯形算法也分为两个阶段，第一阶段也是寻找第一个对偶可行基，第二阶段就是上述所表明的对偶可行基的迭代。关于如何寻求第一个对偶可行基，稍后再说明。这儿先用一个数值例子，具体地说明该对偶单纯形算法第二阶段的具体操作。max2x1x23x1x2x334x13x2x46x12x2x52

23、xj0 j1，2，5显然，由约束条件的系数矩阵的第3，4，5列可构成该问题的一个对偶可行基B(P3，P4，P5)，对应于对偶可行基B的对偶单纯形表为：210000311003430106120012由表可见，由于对基B而言，所有检验数非负，所以B是对偶可行基。Step 1 由于b103，b206，b302均小于0，而基变量下标最小者在第一行，即r1，Jr3。Step 2 由于b11和b12分别为3和1，均小于0，故执行1。Step 3 。用P1替换B中的P3列，得新的对偶可行基对应的对偶单纯形表为0002100101020011类似地计算可知，下一步是用P2列替换中的第4列，得新的对偶可行基为

24、（P1，P2，P5）。再计算所对应的对偶单纯形表000100010001111此时所有的bio0，从而得最优解：，x3x40，x51，最优值为。下面说明如何找出初始对偶可行基，首先找出（LP）的一个基（比如用高斯消除法找出A的一个基）B，不妨设为B（P1，P2，Pm），则（LP）可变换为： i1，2，mxj0 j1，2，n其中xi，i1，2，m，为基变量，xj，jm1，n，为非基变量，若对jm1，n，均有boj0，则B不是对偶可行基，故可用对偶单纯形法直接求解，当存在boj0时，我们引进一个新的变量xn+1和一个新的约束条件：，构造一个新的线性规划（其中M为充分大的数）：（ELP） i1，2，

25、mxj0 j1，2，n，n1显然（ELP）有一个基，基变量为x1，xm及xn1。设bokminboj|jm1，n，则bok0。在（ELP）中用xk替换基变量xn1得一组新的基，而这组新的基为（ELP）的对偶可行基，因此可以用对偶单纯形算法求解（ELP）。解的结果必是下述三种可能性之一：1 （ELP）无解，此时原（LP）也必无解事实上，若（LP）有解，则取，则即为（ELP）的解。2（ELP）的最优解中，xn1是基变量此时在最优解中去掉分量xn1即得（LP）的最优解。3 （ELP）的最优解中，xn1为非基变量。此时有几种可能的情形：（a） 目标函数值与M有关且随M增大目标值增大。此时（LP）无有界

26、最优解。（b） 目标值与M无关，此时（LP）的最优解可按下法得到：设（ELP）的最优解中非零分量的值为xJiiiM i1，2，m1由于是最优解，所以i0。若存在i0，则取M为于是所有xi0，并且也是（LP）的最优解。（c） 其余情形取M0。现举一个例子，用以说明情形（a）和（b）：例如max2x16x2引入松弛变量x3和x4得相应的（LP）：max2x16x2x1x2x32x13x2x43x1，x2，x0显然有一个基B（P3，P4），但它不是对偶可行基，为此构造相应的（ELP）：max 2x16x2x1x2x32x13x2x43x1x2x5Mxj0 i1，2，5。于是（P3，P4，P5）是它的

27、一个基，并由此按上法可得它的一个对偶可行基（P3，P4，P1）。即用x1替换基变量x5。对应的对偶单纯形表为：080022M001012M040113M11000M显然已达到了最优解，最优值为2M，随M的增加而趋于无穷，最优解对应的可行域顶点如下图中的A（M，0）图141如果在上例中把目标函数改为max 2x16x2那么对应的最优对偶单纯形表为000206001012M100010最优值与M无关，且它的最优解为，x32M，x4x50，即对应顶点C，当取M2时，x3x4x50，即对应顶点D。它就是所给问题的最优解。前面介绍的单纯形算法和对偶单纯形算法都是行运算的，即某行乘上一个倍数加到另一行里。

28、有时为了方便，我们可以把行操作变为列操作。例如给定线性规划Max x0CTX(LP) AXBX0的一个可行基B（，），令N（，）那么（LP）改写为：或者写成分量形式： i1，2，m jm1，n j1，2，n一般地可表示为下述形式：max x0 i1，2，m(LP) im1，n xj0 j1，2，n其中bio0，im1，n；0，当ij且im1，n；而1，im1，n。我们将单纯形算法在这张表上实施就变为列的操作：当某个0使然后更新单纯形表：即从方程中解出 将的表示式代入到目标涵数和其它方程中。亦即在下一个单纯形表中的元素为： ，i0，1，2，n j0，m1，n且jr ，i0，1，2，n列举一个数值

29、例子说明单纯形算法的列操作为过程：max x0x23x32x5，x13x2x32x572x24x3x4124x23x38x5x610xj0其中基变量为x1，x4，x6，非基变量为x2，x3，x5biox2x3x5x2x4x5x0013292x17312100x201000100x3001030x4122400010x500010001x61043818xibiox1x4x5x011x10100x24x35x40010x50001x611110最优解为：x1x4x50x24x35x611目标值x011同样，对偶单纯形算法也可以仿此进行列操作形式。为了书写方便和后续需要，我们把（VLP）写为向量形

30、式。max x0（VLP） xj0 j1，2，n其中X(x0，x1， ，xn)T， 而kjm，jm1，n。用tk表示非基变量；dnm保证单纯形和对偶单纯形算法的收敛性，还有字典序技术。这儿只介绍字典序对偶单纯形算法。首先介绍一下字典序的概念设（0，1，n）是一个实向量，若的第一个非零分量为正的，则称为字典序正的，记为；若，则称为字典序负的。若两个向量1和2，当，则称1字典序大于2，并记为；若，那么对任意的0，则。若1，2，m为m个向量，当，j1，2，m且ji，则记；若，并且，那么现在描述字典序的对偶单纯形算法：Step 0 设B是（LP）的一个基，那么由B可得（LP）的表示形式为（VLP），求

31、出若，则转step 1 ；否则令由这个方程解出ts，即把ts的表示式代入（VLP）的其它方程后，再把ts还原为原来的，并记，这样就得到（VLP）的新的表示式，（此时的基必是对偶可行基，即有，j1，2，d）。Step 1 计算若bro0，则算法结束，X0为所求。（注意：与行操作的对偶单纯形算法一样，要讨论目标函数中是否含有M的情况）。Step 2 若bro0，当对一切j1，2，n，均有brj0，则算法结束。（LP）问题无可行解。否则计算Step 3 从中解出ts，然后代入其系方程，得新的（VLP），记为其中， ks；，ks（注意：由s的选取及，则可推出，k1，2，d。而由bro0及brs0，可推

32、出）然后置 k0，1，d； ，k1，2， d，返回Step 1。容易看出，每次迭代0是字典序地严格减小，所以不会出现循环现象，从而算法必在有限步内终止下面用一个例子进一步说明算法：max x0x0x13x23x3x442x1x2x3x524x13x2x633x12x2x3xj0 j1，2，6列表如下：x4x2x3x1x2x3x001333M263x101000100x200100010x30001M111x442114M321x524302430x633213M411x7M1110001现在已得到对偶可行基，即j0，j1，2，d。故转入Step 1，计算brominbio | i1，2，nb6

33、03M再计算： 用x1替换x6，即执行Step3，得下表。再迭代一次即得最优解x6x2x7x6x2x5x0143x10x200100010x31x41x55M1210001x601000100x700015M121此时所有bio0，i1，2，n，故得最优解x12/4 x39/2，x415/2，x2x5x60，目标值为x014。15 原始对偶算法对某些类型的线性规划，如运输问题或网络问题等，很易得到原问题或其对偶的可行解，对这样的问题，可利用定理16的结论导出一个算法，称之为原始对偶算法假设已经知道线性规划（P）以及（P）的对偶问题（D）如下:MinCTx Max b（P）AXb （D）ACTx

34、0这儿假设是m维的行向量，假如已知（D）的一个可行解。令Jj|PjCj其中Pj为A的第j列，j1，2，n。那么由定理16知，如果下述不等式组有解，则它就是问题（P）的最优解，而为（D）的最优解：显然（）比（P）要简单，因为它有若干变量已固定为0。求解（）等价于求解下述的线性规划（RP）：AXYb设最优解为（x*，y*），若最优值为0，即y*0，则x*为（）的解，也是（P）的最优解。否则，设（RP）的对偶（DRP）的最优解为h*。由于，我们可以构造（D）的一个新的可行解：其中0待定。显然，对有，从而是（D）的可行解，那么对应的目标值为由于，所以随增大而增大，即（D）无有界最优解，故（D）无解。若

35、存在使，则选取此时是（D）的可行解，并且好于，即 。这样用代替，重复上述过程。具体计算步骤如下：原始对偶算法：Step 1 任取（D）的一个可行解；Step 2 确定Step 3 求解（DRP），设最优解为，若最优值为0，则（RP）的最优解（x*，y*）中的x*即为（P）的最优解，算法终止。Step 4 若对一切有，则原问题（P）无解，否则取置，返回Step 2。下面用网络中最短路问题的一个简单的例子，说明上述算法的操作过程。给定一个有向网络（V，A;C），其中V1，2，n为网络的节点或顶点之集合，A是V上有序对的集合，也称为弧的集合；C是弧集A上的非负实函数，即对每一弧有一长度Cij。从顶点

36、1点到顶点n的一条路P，就是弧的一个序列（1，i1）（i1，i2）（ik1，ik），（ik，n），P的长度定义为P上弧的长度之和。目标是求中自顶点1到顶点n长度最短的路。最短路问题的线性规划模型为 其中，（P1）的对偶为Max 1易见，xij是弧（i，j）上的变量，而i则是顶点i的变量。（P1）的最优基可行解x*中，的分量所对应的弧（i，j）是在顶点1到顶点n的最短路上；而（D1）的最优解*中的分量表示顶点i到顶点n的最短路长度，例如给定网络如下：图151对应的（P1）和（D1）为Min2x12x133x233x24x352x543x465x56x12x131x12x23x240x13x23x350x24x54x460x35x54x560xij0和Max 11221312332433514524355为简单起见，取（5，5，5，3，5）（实际上，由于Cij0，可以取0，i