线性规划与计算复杂性简介(全部).ppt

《线性规划与计算复杂性简介(全部).ppt》由会员分享，可在线阅读，更多相关《线性规划与计算复杂性简介(全部).ppt（82页珍藏版）》请在金锄头文库上搜索。

1、线性规划与计算复杂性简介线性规划与计算复杂性简介浙江大学数学建模实践基地浙江大学数学建模实践基地1上一页上一页下一页下一页8.1 8.1 线性规划问题线性规划问题一一、线性规划的实例与定义线性规划的实例与定义二、线性规划的标准形式二、线性规划的标准形式三、线性规划的图解法三、线性规划的图解法四、基本可行解与极点的等价定理四、基本可行解与极点的等价定理五、求解线性规划的单纯形法五、求解线性规划的单纯形法六、初始可行解的求法六、初始可行解的求法两段单纯形法两段单纯形法8.2 8.2 运输问题运输问题一一、运输问题的数学模型运输问题的数学模型三、最优性判别三、最优性判别二、初始可行解的选取二、初始可

2、行解的选取8.3 8.3 指派问题指派问题一、指派问题的数学模型一、指派问题的数学模型二、求解指派问题的匈牙利算法二、求解指派问题的匈牙利算法8.4 8.4 计算复杂性问题的提出计算复杂性问题的提出一、一、P P类与类与NPNP类，类，NPNP完全性完全性二、有关离散问题模型及其算法的几点附加说明二、有关离散问题模型及其算法的几点附加说明2上一页上一页下一页下一页8.1 线性规划问题在人们的生产实践中，经常会遇到如何利用现有资源来安排生产以取得最大经济效益的问题，此类问题构成了运筹学的一个重要分支数学规划，而线性规划（Linear Programming, 简记LP）则是数学规划的一个重要部分

3、。自从1947年GBDantzig提出求解线性规划的单纯形方法以来，线性规划在理论上日趋成熟 ，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。3上一页上一页下一页下一页一.线性规划的实例与定义例例8.18.1 某机床厂生产甲、乙两种机床，每台销售后的利某机床厂生产甲、乙两种机床，每台销售后的利润分别为润分别为40004000元与元与30003000元。生产甲机床需用元。生产甲机床需用A A、B B机器加工，机器加工，加工时间分别为每台加工时间分别为每台 2 2小时和小时和1 1小时；生产乙机床需用小时；生产乙机床需用A A、B B、C C三种机器加工，加工时间为每台各一小时。若每天

4、可三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为用于加工的机器时数分别为A A机器机器1010小时、小时、B B机器机器8 8小时和小时和C C机器机器7 7小时，问该厂应生产甲、乙机床各多少台，才能使小时，问该厂应生产甲、乙机床各多少台，才能使总利润最大？总利润最大？4上一页上一页下一页下一页例1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则 x1 、x2应满足 max 4max 4x x1 + 3 + 3x x2 s.ts.t 2 2x x1 + + x x2 10 10 x x1 + + x x2 8 (8.1) 8 (8.1) x x2 7 7

5、 x x1 , , x x2 0 0（8.1）式中 4x1+ 3x2 表示生产x1 台甲机床和x2 台乙机床的总利润，被称为问题的目标函数，当希望使目标函数最大时，记为max；反之，当希望使目标函数最小时，记为min。（8.1）中的几个不等式是问题的约束条件，记为S.t（即Subject to）。由于（8.1）式中的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限止下，求一线性目标函数最大或最小的问题。5上一页上一页下一页下一页二、线性规划的标准形式例例8.28.2 min min S.tS.t i=1,m xj0,j=1,n线性规划的目标函数可

6、以是求最大值，也可以是求最小值，约束条件线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为来的不便，规定线性规划的标准形式为利用矩阵与向量记为利用矩阵与向量记为min min z z = = CT x x S.tS.t A Ax x = = b bx x0 0 （8.38.3）其中其中C C 和和x x 为为n n

7、 维列向量，维列向量，b b为为m m 维列维列向量，向量，b0b0，A A为为m mn n矩阵矩阵,mn,mn且且rank(Arank(A)=m)=m。或更简洁地或更简洁地6上一页上一页下一页下一页如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式：（1 1）若目标函数为若目标函数为max max z z = =C CT T x x，可将它化为，可将它化为minminz z = =C CT T x x（2 2）若第若第i i个约束为个约束为a ai i1 1x x1 1+ + +a aininx xn nb bi i，可增加一个松驰变，可增加一个松驰变量量y yi

8、i，将不等式化为，将不等式化为a ai i1 1x x1 1+ + +a aininx xn n+y+yi i = = b bi i，且，且y yi i00。若第若第i i个约束为个约束为a ai i1 1x x1 1+ + +a aininx xn nb bi i，可引入剩余量，可引入剩余量y yi i，将，将不等式化为不等式化为a ai i1 1x x1 1+ + +a aininx xn n y yi i = = b bi i，且，且y yi i00。（3 3）若若x xi i为自变量，则可令为自变量，则可令 , ,其中其中 、 00例如例如例18.1并非标准形式，其标准形式为min 4

9、x13x2s.t 2x1 + x2 + x3 = 10x1 + x2 + x4 = 8x2 + x5 = 7x1 , x2 , x3 , x4, x507上一页上一页下一页下一页图8.1对于例8.1，显然等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，本例的最优解为x*=(2,6)T ，最优目标值z*=26 。三、线性规划的图解法为了了解线性规划问题的特征并导出求解它的单纯形法，我们先应用图解法来求解例8.1。满足线性规划所有约束条件的点称为问题的可行点（或可行解），所有可行点构成的集合称为问题的可行域，记为R。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线

10、，当z变动时，我们得到一族平行直线（图8.1）。8上一页上一页下一页下一页上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足一线性等式aix=bi的点集被称为一个超平面，而满足一线性不等式aixbi （或aixbi ）的点集被称为一个半空间（其中ai为一n维行向量，bi为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域R必为多胞形（为统一起见，空集也被视为多胞形）。（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时，它必定是若干个半平面的交集（ 除非遇到空间维数的退化）。R既可能是有界区域，也

11、可能是无界区域。（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”。从上面的图解过程可以看出并不难证明以下断言：9上一页上一页下一页下一页在一般n维空间中，要直接得出多胞形“顶点”概念还有一些困难。在图8.1中顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。定义定义8.18.1 称n 维空间中的区域R为一凸集，若x1 , x2 R及 (0, 1)，有 x1 +（1）x2 R。定义定义8.28.2 设R为n维空间中的一个凸集，R中的点

12、x被称为R的一个极点，若不存在x1 、x2 R及(0, 1)，使得x = x1 +（1）x2 。定义8.1说明凸集中任意两点的连线必在此凸集中；而定义8.2说明，若x是凸集R的一个极点，则x不能位于R中任意两点的连线上。不难证明，多胞形必为凸集。同样也不难证明，图8.1中R的顶点均为R的极点（R 也没有其他的极点）为此，我们将采用另一途径来定义它。10上一页上一页下一页下一页三、基本解与基本可行解给定一个标准形式的线性规划问题（8.3），其中A=(aij)mxn ，m 0 ，则称x=（B-1b ，0）为（8.3）的一个非退化的基本可行解，并称B为非退化的可行基。由于基矩阵最多只有 种不同的取法

13、，即使A的任意m解均线性无关，且对应的基本解均可行，（8.3）最多也只能有个不同的基本可行解。11上一页上一页下一页下一页四、基本可行解与极点的等价定理在线性规划的求解中，下列定理起了关键性的作用。在这里，我们不加证明地引入这些定理。定理定理8.18.1 （基本可行解与极点的等价定理）设A为一个秩为m的mn矩阵（nm）b为m维列向量，记R为（8.3）的可行域。则x为R的极点的充分必要条件为 x 是 的基本可行解。定理8.1既提供了求可行域R的极点的代数方法，又指明了线性规划可行域R的极点至多只有有限个.对定理证明有兴趣的读者可以参阅 D.G.鲁恩伯杰著的“线性与非线性规划引论”一书第二章12上

14、一页上一页下一页下一页（线性规划基本定理） 线性规划（8.3）具有以下性质：（1）若可行域R，则必存在一个基本可行解。（2）若问题存在一个最优解 ，则必存在一个最优的基本可行解。定理8.2并非说最优解只能在基本可行解（极点）上达到，而是说只要（8.3）有有限最优解，就必定可在基本可行解（极点）中找到。定理定理8.28.2从模型本身讲，线性规划显然应属连续模型。但定理 2表明，如果线性规划有有限最优解，我们只需比较各基本可行解上的目标函数值即可找到一个最优解，而问题的基本可行解至多只有有限个，从而问题化为一个从有限多个点选取一个最优点 的问题。正是基于这样一种思路，DantzigDantzig提

15、出了求解线性规划的单纯形法。也正因为如此，我们把线性规划列入了离散模型，因为求解它的单纯形法更具有离散模型问题的算法特征。13上一页上一页下一页下一页五、求解线性规划的单纯形法（步1）取一初始可行基B（一般取法见后面的两段单纯形法），再用高斯约当消去法求出初始基本可行解x0，编制成所谓的初始单纯形表；（步2）判断x0是否最优解，如果x0是最优解，输出x0，停，否则到步3；（步3）按一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量。这相当于交换B与N的一个列，同样可用高斯约当消去法，运算可以通过单纯形表上的“转轴运算”实现。Dantzig单纯形法的基本步骤如下：14上一页上一

16、页下一页下一页设B为一非退化的可行基，x=（B-1b，0）为其对应的基本可行解。现在，我们先来讨论如何判别x0是否为最优解。为此，考察任一可行解 。由Ax=b可得 （8.5）代入目标函数，得到定理定理8.3 （最优性判别定理） 令 。（1）若rN0，则x0必为（8.3）的一个最优解。（2）记 。若 ，rj0 ， 根据（7.15）式知，当且充分小时，仍有xB0 。此时对应的x仍 为可行解，但由（8.6），其目标函数值：故x0必非最优解。 定理8.3不仅给出了判别一个基本可行解是否为最优解的准则，而且在x0非最优解时还指出了一条改进它的途径。由于rN在判别现行基本可行解是否为最优解时起了重要作用，

17、所以rN被称为x0处的检验向量，而rj (jN)被称为非基变量xj的检验数。16上一页上一页下一页下一页有趣的是上述过程完全可以在以下的单纯形表上进行。先将CT、A、b及数0写在一个矩阵中，在表上用高斯约当消去法解方程组Ax=b 高斯-约当消去法 （第一行不变） 利用单位矩阵I消第一行的为零向量，则 被消成 ，而0则被消成 。将消去后的行向量写到最后一行，删去原来的第一行，得到一张被称为单纯表的表格：xBxNIB1NB1b0rNZ0(8.7)表格（8.7）以极为简洁明了的方式表达了我们需要的全部信息。从其前m行可看出哪些变量是基变量并可直接读出对应的基本可行解x0=（B1b，0）。其最后一行又

18、给出了非基变量的检验数及x0处目标函数值的相反数。 17上一页上一页下一页下一页例8.1的标准形式为（8.4），容易看出它的一个初始基B=I（以x3、x4、x5为基变量），且CB已经为零，故我们已有了一张初始的单纯形表表8.1： 表表8.18.1x1x2x3x4x5基变量x3110010x4110108x5010017rj430000x0=(0,0,10,8,7)Tz0=CTx0=0rN=(r1,r2)=(4，3)现在，我们以例现在，我们以例8.18.1为例，来看一下单为例，来看一下单纯形法是如何工作纯形法是如何工作的。的。18上一页上一页下一页下一页由于存在着负的检验数且由于存在着负的检验数

19、且x x0 0非退化，非退化，x x0 0非最优解。非最优解。r r1 1，r r2 2均为负，均为负，x x1 1，x x2 2增大（进基）均能改进目标函数值。增大（进基）均能改进目标函数值。 例例如如，取取x x1 1进进基基仍仍令令x x2 2=0=0（x x2 2仍仍为为非非基基变变量量），此此时时由由（8.58.5）式式及及（8.68.6）式有）式有 且且z z = = C CT Tx x = = 4 4x x1 1x x1 1增增加加得得越越多多，目目标标函函数数值值下下降降得得越越多多，但但当当x x1 1 =5=5时时x x3=03=0，x x1 1再再增增大大则则x x3 3

20、将将变变负负。为为保保证证可可行行性性，x x1 1最最多多只只能能增增加加到到5 5，此此时时x x3 3成成为为非非基基变变量量（退基）。（退基）。 不难看出，上述改进可以在单纯形表上进行。对于不难看出，上述改进可以在单纯形表上进行。对于一般形式一般形式的单纯形表，的单纯形表，记最后一列的前记最后一列的前m m个分量为（个分量为（y yi i0 0），），i i=1,=1, ,m m。若取。若取 进基，记进基，记j j0 0列前列前m m个分量为（个分量为（ ），），i i=1,=1, ,m m。易见，阻碍。易见，阻碍 增大的只可能在增大的只可能在 00的那些约束中。若的那些约束中。若 0

21、 0对一切对一切i i=1,=1, ,m m成立（成立（j j0 0列前列前m m个分量中个分量中不存在正值），则不存在正值），则 可任意增大，得到的均为可行解，但其目标值随可任意增大，得到的均为可行解，但其目标值随之可任意减小，故问题无有限最优解。之可任意减小，故问题无有限最优解。 19上一页上一页下一页下一页否则，令则随着 的增大，将 最先降为零（退出基变量），故只需以 为主元作一次消去法运算（称此运算为一次转轴运算），即可得到改进后的基本可行解处的单纯形表。在本例中，因取x1进基（j=1） 而 ，以y11为主元作第一次转轴，得到 x1=(5,0,0,3,7)T z1=20 rN=(r2,

22、r3)=(1，2)2000210rj710010x5301 -0x45001x3基变量x5x4x3x2x1表8.220上一页上一页下一页下一页表表8.28.2中中r200）最小选定以下最小选定以下 y22 = = 为主元转轴，得到下一基本可行解为主元转轴，得到下一基本可行解x x2 2处的单纯形表表处的单纯形表表8.38.3。表8.3x1x2x3x4x5基基变量量x310102x40106x50011rj00026x2=(2,6,0,0,1)Tz2=26rN=(r3,r4)=(1，2)对于于x2，rN= (1，2)为非非负向量，故向量，故x2为最最优解，最解，最优目目标值为26。于是，原于是，

23、原问题例例1的最的最优解解x*=(2,6)T，最，最优目目标值为26。 21上一页上一页下一页下一页六、初始可行解的求法两段单纯形法 阶段2 若辅助规划的最优目标值不等于零，原规划无可行解。否则我们已求得原问题的一个基本可行解x0。删去阶段1最终单纯表中最后一行及对应人工变量的列，作出原规划对应x0的初始单纯形表。此时又可利用上述单纯形法求解原规划了。阶段1 对第i个约束引入人工变量 yi，yi0，将其改写为ai1x1+ ainxn+yi=bi，i=1,m。作辅助线性规划LP（1），其目标函数为 。容易看出，原规划有可行解（从而有基本可行解）的充分必要条件为辅助规划的最优目标值为零。由于辅助规

24、划具有明显的初始可行基（人工变量对应的列构成单位矩阵I），可利用上述单纯形法逐次改进而求出辅助规划最优解。22上一页上一页下一页下一页例例8.28.2 min 4x1+ x2+ x3 S.t 2x1+ x2+2x3 = 4 3x1+ 3x2+x3 = 3 x1、x2、x30?解解：因为初始可行基不能直接看出，我们采用两段单纯形法因为初始可行基不能直接看出，我们采用两段单纯形法求解。求解。阶段阶段1 1 先求解辅助规划：先求解辅助规划：min x4+ x5S.t 2x1+ x2+2x3 + x4= 4 3x1+ 3x2+x3+ x5 = 3 x1，x3023上一页上一页下一页下一页表表8.48.

25、4x1x2x3x4x5基基变量量x4212104x531013rj543007选取选取x x1 1进基，以进基，以y y2121=3=3为主元转轴（为主元转轴（x x5 5出基），得表出基），得表8.58.5。表表8.58.5x1x2x3x4x5基基变量量x4014/312/32x1111/301/31rj014/305/3224上一页上一页下一页下一页因因r r3 3 0 0 。当。当B1b也存在零分量时，也存在零分量时，我们遇到了一个退化的基本可行解。此时我们遇到了一个退化的基本可行解。此时rN存在负分量不一定说明现行基存在负分量不一定说明现行基本可行解不是最优解，单纯形法也可能会遇到循环

26、迭代。存在着几种避免本可行解不是最优解，单纯形法也可能会遇到循环迭代。存在着几种避免循环的技巧，例如，只要每次在循环的技巧，例如，只要每次在rj00的非基变量中选取具有最小足标者进的非基变量中选取具有最小足标者进基即可。基即可。 在求解线性规划时，首先应将问题化为标准形式。若从标准形式已可看出在求解线性规划时，首先应将问题化为标准形式。若从标准形式已可看出一个初始基，则可直接用单纯法求解：（一个初始基，则可直接用单纯法求解：（1 1）写出初始单纯形表；（）写出初始单纯形表；（2 2）若）若检验向量检验向量 r rN N 0 0，则已得以最优解；（，则已得以最优解；（3 3）任选一负分量）任选一

27、负分量r rj j。以。以 进基，进基，考察考察 所在列。若对所在列。若对i i=1,=1,m,m均有均有 0 0，则问题无有限最优解，停；，则问题无有限最优解，停；否则令否则令 ，以以 为主元转轴，返回（为主元转轴，返回（2 2），直至），直至r rN N0 0求出最优解。若从标准形式无求出最优解。若从标准形式无法看出初始可行基，则需采用两段单纯形法求解。法看出初始可行基，则需采用两段单纯形法求解。变量同时具有上、下界限止的线性规划问题变量同时具有上、下界限止的线性规划问题也可化为标准形式求解，有兴趣的读者可以也可化为标准形式求解，有兴趣的读者可以参阅参阅D.G.D.G.鲁恩伯杰的鲁恩伯杰的

28、“线性与非线性规划引线性与非线性规划引论论”一书的第三章。一书的第三章。 27上一页上一页下一页下一页8.2 运输问题一.运输问题的数学模型 例例8.38.3 某商品有m个产地、n个销地，各产地的产量分别为a1,am各销地的需求量分别为b1,bn。若该商品由i产地运到j销地的单位运价为Cij，问应该如何调运才能使总运费最省? 解解：引入变量引入变量x xijij，其取值为由，其取值为由i i产地运往产地运往j j销地的该商品数量。例销地的该商品数量。例8.38.3的的数学模型为数学模型为min S.t ，i=1,m (8.9) ，j=1,n xij 0（8.98.9）显然是一个线性规划问题，当

29、然可以用单纯形方法求解，但由于）显然是一个线性规划问题，当然可以用单纯形方法求解，但由于其约束条件的系数矩阵相当特殊，求解它可以采用其他简便办法。本节其约束条件的系数矩阵相当特殊，求解它可以采用其他简便办法。本节将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法（简称康将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法（简称康希表上作业法），其实质仍然是先作出一个初始基本可行解，然后用希表上作业法），其实质仍然是先作出一个初始基本可行解，然后用最优性准则检验是否为最优并逐次改进直至最优性准则成立。最优性准则检验是否为最优并逐次改进直至最优性准则成立。 28上一页上一页下一页下一页二、初

30、始可行解的选取不难发现，（8.9）的约束条件中存在着多余方程。容易证明，只要从中除去一个约束，例如最后一个方程，约束条件就彼此独立了。因而，（8.9）是一个具有mn个变量的线性规划，其每一基本可行解应含有m+n1个基变量。记（8.9）约束条件中前m+n1个方程的系数矩阵为A，A为（m+n1）mn矩阵，它的每一列最多只有两个非零元素且非零元素均为1。利用线性代数知识能够判定A中怎样的m+n1个列可以取为基（即怎样的m+n1个变量可以取为基变量），为了判明哪些变量对应的列是线性无关的，先引入下面的定义： 29上一页上一页下一页下一页定义定义8.38.3 （闭回路）（闭回路） xij （i i=1,

31、=1,m m; ; j j=1,=1,n n）的一个子集被称为）的一个子集被称为一个闭回路，若它可以被排成一个闭回路，若它可以被排成其中其中 互异，互异， 也互异。也互异。用下面的方法可以较方便直观地看出用下面的方法可以较方便直观地看出 xij 的一个子集是否为一闭回路：的一个子集是否为一闭回路：作一个作一个m m行行n n列的表格，令格（列的表格，令格（i i,j,j）对应）对应 xij 。将子集中的变量填于相应。将子集中的变量填于相应格中，并将相邻变量（或同行或同列）用边相连，则此子集为闭回路当且格中，并将相邻变量（或同行或同列）用边相连，则此子集为闭回路当且仅当其点按上述连法作出的折线可

32、构成一个闭回路。仅当其点按上述连法作出的折线可构成一个闭回路。例如，当例如，当m m=3,=3,n n=4=4时，时，X X1 1=x x1212,x,x1313, ,x x2323, ,x x2424, ,x x3434, ,x x3232 和和X X2 2=x x1212,x,x1414, ,x x2424, ,x x2121, ,x x3131, ,x x3232 均为闭回路，见表均为闭回路，见表8.98.9和表和表8.108.10。表(8.9)表(8.10)30上一页上一页下一页下一页定理定理8.48.4 X X为为 xij （i i=1,=1,，m m；j j=1=1，n n）的一个

33、子集，）的一个子集，X X中的变中的变量对应的量对应的A A中的列向量集线性无关的充要条件为中的列向量集线性无关的充要条件为X X中不包含闭回路。中不包含闭回路。定量定量8.48.4不难用线性代数知识证明，详细证明从略。根据定理不难用线性代数知识证明，详细证明从略。根据定理8.48.4，要选取，要选取（8.98.9）的一组基变量并进而得到一个基本可行解，只需选取）的一组基变量并进而得到一个基本可行解，只需选取 xijxij 的一个的一个子集子集X X，X=X=m m+ +n n-1-1且且X X中不含闭回路，其中中不含闭回路，其中XX表示表示X X中的变量个数。中的变量个数。 我们从下面的例子

34、来说明如何选取一个基本可行解。我们从下面的例子来说明如何选取一个基本可行解。 例例8.38.3 给定运输问题如表给定运输问题如表8.118.11所示，表中左上角的数字为单位运价所示，表中左上角的数字为单位运价C Cij 。易见，本例是产销平衡的即。易见，本例是产销平衡的即 。表表8.118.116432销量量72 31 48 7 359 25 3 3 310 234 13 11 2 21产量量4321销地产地31上一页上一页下一页下一页现采用现采用“最小元素法最小元素法”求一基本可行解。单位运价最小的为求一基本可行解。单位运价最小的为C C3333=1=1，令，令x x3333=min=min

35、aa3 3,b,b3 3=4,=4,并令并令x x1313= = x x2323=0=0（销地（销地3 3已满足），相应格打已满足），相应格打“”。产地。产地3 3已已运出运出4 4单位，将产量改为剩余产量单位，将产量改为剩余产量3 3。剩余表中单位运价最小的为。剩余表中单位运价最小的为C C1111=2=2（或（或C C3434=2=2），令），令x x1111= min a= min a1 1,b,b1 1=2,=2,并令并令x x2121= = x x3131=0=0，相应格打，相应格打“”，a a1 1改为剩余产量改为剩余产量1 1，直至全部产品分配完毕。注意到除最后一次分配，直至全部

36、产品分配完毕。注意到除最后一次分配外每次只能对一行或一列找外每次只能对一行或一列找“”，表示某销地已满足或某产地产品已，表示某销地已满足或某产地产品已分配完（当两者同时成立时只能打分配完（当两者同时成立时只能打“”行或列之一，将剩余需求量或行或列之一，将剩余需求量或产量记为产量记为0 0，此时基本可行基是退化的）。容易证明：这样分配共选出了，此时基本可行基是退化的）。容易证明：这样分配共选出了m m+ +n n-1-1个变量，且这些变量的集合不含闭回路，从而构成一个基本可行解。个变量，且这些变量的集合不含闭回路，从而构成一个基本可行解。当每一基变量当每一基变量x xijij选取时选取时i i产

37、地的剩余商品量与产地的剩余商品量与j j销地的剩余需求量总不相销地的剩余需求量总不相等，选出的基本可行解是非退化的。等，选出的基本可行解是非退化的。初始基本可行解也可按其他方初始基本可行解也可按其他方式式选取，如取，如“左上角法左上角法”等，其等，其方法与原理是方法与原理是类似的，左上角似的，左上角法每次法每次选取剩余表格中位于最取剩余表格中位于最左上角的左上角的变量，其余均相同。量，其余均相同。32上一页上一页下一页下一页三、最优性判别类似单纯形法，可计算非基变量的检验数，存在多种求检验数的方法类似单纯形法，可计算非基变量的检验数，存在多种求检验数的方法（求得的结果是相同的），下面介绍计算简

38、便且计算量也较小的（求得的结果是相同的），下面介绍计算简便且计算量也较小的“位势位势法法”。引入。引入m m+ +n n个量（被称为位势）个量（被称为位势）u u1 1，u um m；u u1 1，u un n。对每一变量。对每一变量x xijij，引入，引入r rijij, ,令令x xijij= =ijij- - u ui i- -v vj j( (事实上，这一公式与单纯形法求检验数的事实上，这一公式与单纯形法求检验数的公式是相同的公式是相同的) )。对基变量。对基变量x xijij，令，令r rijij=0=0，得到，得到C Cijiju ui iv vj j=0 (=0 (x xiji

39、j为基变量为基变量) ) （8.10)8.10) 齐次次线性方程性方程组（8.10）共有）共有m+n个独立方程，但含有个独立方程，但含有m+n个个变量。量。任取一任取一变量，例如量，例如u1作作为自由自由变量，便可解出方程量，便可解出方程组。容易看出，。容易看出，u1的取的取值不同不同虽会改会改变位位势的取的取值但不会改但不会改变非基非基变量的量的检验数。数。为方便起方便起见，只要令只要令u1即可。事即可。事实上，我上，我们甚至不必去解方程甚至不必去解方程组（8.10），而只需），而只需令令u1，对所有基所有基变量令量令uivjc cijij，即，即= =ijij- - ui- -v vj j

40、，在表上逐次，在表上逐次求出所有位求出所有位势，进而再而再对非基非基变量量x xijij计算其算其检验数数r rijij= =ijij- - ui- -v vj j33上一页上一页下一页下一页例如例如，对表，对表8.118.11中取定的基，我们求出位势及非基变量的检验数，中取定的基，我们求出位势及非基变量的检验数，列于表列于表8.128.12中，表中不带圈的数为基变量取值，带圈的数为非基中，表中不带圈的数为基变量取值，带圈的数为非基变量检验数，右上角的数为单位运价变量检验数，右上角的数为单位运价ijij。u1=02 211 133 04 1u1=510 3 35 39 2u3=-210 8 1

41、21 42 31 1 = 2= 2 = =2 23 3 = 3= 34 4 = 4= 4利用线性代数知识可以证明下列各定理利用线性代数知识可以证明下列各定理( (证明从略证明从略) )：定理定理8.58.5 任取一非基变量任取一非基变量 ，将其加入基变量集合中，则在所得，将其加入基变量集合中，则在所得变量集合中存在唯一的闭回路变量集合中存在唯一的闭回路 。易见闭回路中含有偶数个变量，若易见闭回路中含有偶数个变量，若 令进基，令令进基，令 = =，为保持平，为保持平衡条件，位于偶数位置的变量衡条件，位于偶数位置的变量 必须减少必须减少，而位于，而位于奇数位置的变量奇数位置的变量 则必须增加则必须

42、增加（注：（注： ）。）。表表8.128.1234上一页上一页下一页下一页定理定理8.68.6 设设 是非基变量是非基变量 与基变量集合的与基变量集合的并集中唯一的闭回路，若令并集中唯一的闭回路，若令 = =并在闭回路上调整基变量取值使并在闭回路上调整基变量取值使之平衡，得一可行解之平衡，得一可行解x x，则，则x x处的目标值与原基本可行解上的目标值之处的目标值与原基本可行解上的目标值之差为差为 。根据定理根据定理8.68.6，若存在检验数，若存在检验数 的非基变量的非基变量 ，取进基，取进基 （取（取正值）并令正值）并令 （8.128.12）则原取值为则原取值为的位于偶数位置的基变量退基，

43、得到一新的基本可行解，的位于偶数位置的基变量退基，得到一新的基本可行解，其目标值减少其目标值减少 。 定理定理8.78.7 设设 为（为（8.98.9）的一个基本可行解，若）的一个基本可行解，若x x0 0所有非基变所有非基变量的检验数均非负，则量的检验数均非负，则x x0 0必为（必为（8.98.9）的一个最优解。当）的一个最优解。当x x0 0非退化时，此非退化时，此条件还是必要的。条件还是必要的。证明证明 由定理由定理8.68.6知，当知，当x x0 0所有非基变量的检验数均非负时，任一非基变所有非基变量的检验数均非负时，任一非基变量进基均不会使目标值减小，由于（量进基均不会使目标值减小

44、，由于（8.98.9）是一线性规划，此性质表明）是一线性规划，此性质表明x x0 0已为最优基本可行解。反之，则只要令具有负检验数的非基变量进基即可。已为最优基本可行解。反之，则只要令具有负检验数的非基变量进基即可。 35上一页上一页下一页下一页综上所述，康综上所述，康希表上作业法可如下操作：希表上作业法可如下操作：（步（步1 1） 按最小元素法（或右上角法等）求一初始基本可行解。按最小元素法（或右上角法等）求一初始基本可行解。（步（步2 2） 按（按（8.108.10）求出位势）求出位势u ui i, ,j j（i i=1,=1, ,m m; ; j j=1,=1, ,n n）。进）。进而按

45、（而按（8.118.11）求出非变量的检验数）求出非变量的检验数r rijij。若一切。若一切r rijij0 0，则已求得一最，则已求得一最优解。优解。（步（步3 3） 任取一任取一00，找出进基后形成的唯一闭回路。在找出的闭回，找出进基后形成的唯一闭回路。在找出的闭回路上调整，按（路上调整，按（8.128.12）取）取，得出新的基本可行解，返回步，得出新的基本可行解，返回步2 2。直至。直至找到最优解。找到最优解。 36上一页上一页下一页下一页对于例对于例8.38.3，表，表8.128.12已给出非基变量的检验数。因已给出非基变量的检验数。因r r232300，令，令x x2323进基，得

46、进基，得闭回路闭回路x x2323, , x x2424, , x x3434, , x x3333取取=min =min x x2424, , x x3333 =2 =2，调整后得一新的基本可行解。求出新的基本，调整后得一新的基本可行解。求出新的基本可行解、对应的位势及非基变量检验数，列成表可行解、对应的位势及非基变量检验数，列成表8.138.13。表表8.138.13u1=02 211 113 4 1u1=310 3 35 29 u3=17 8 1 23 51 1 = 2= 2 = 0= 03 3 = 3= 34 4 = 4= 4现在，非基变量检验数均已非负，故已求得最优解：现在，非基变量

47、检验数均已非负，故已求得最优解：x x1111=2=2，x x1414=1=1，x x2222=3=3，x x2323=2=2，x x3333=2=2，x x3434=5=5，其余，其余 =0=0（非基变量）。（非基变量）。若运输问题是产销不平衡的，则应先将其转化为产销平衡的，然后再求若运输问题是产销不平衡的，则应先将其转化为产销平衡的，然后再求解。例如，若产大于销，可虚设一销地（剩余产量存贮），将单位运价解。例如，若产大于销，可虚设一销地（剩余产量存贮），将单位运价取为零即可。取为零即可。37上一页上一页下一页下一页一、指派问题的数学模型8.3 指派问题 例例8.48.4 拟分配拟分配n n

48、人去干人去干n n项工作，每人干且仅干一项工作，若分配第项工作，每人干且仅干一项工作，若分配第i i人人去干第去干第j j项工作，需化费项工作，需化费C Cijij单位时间，问应如何分配工作才能使工人化单位时间，问应如何分配工作才能使工人化费的总时间最少？费的总时间最少？容易看出，要给出一个指派问题的实例，只需给出矩阵容易看出，要给出一个指派问题的实例，只需给出矩阵C C= =（C Cijij）, ,C C被称被称为指派问题的系数矩阵。为指派问题的系数矩阵。引入变量引入变量x xijij，若分配，若分配i i干干j j工作，则取工作，则取x xijij =1=1，否则则取，否则则取x xiji

49、j =0 =0。上述指派。上述指派问题的数学模型为问题的数学模型为 S.tS.t （8.138.13） x xijij=0=0或或1 138上一页上一页下一页下一页（8.138.13）的可行解既可以用一个矩阵表示，其每行每列均有且只有一）的可行解既可以用一个矩阵表示，其每行每列均有且只有一个元素为个元素为1 1，其余元素均为，其余元素均为0 0，也可以用，也可以用1,1, ,n n中的一个置换表示。中的一个置换表示。 （8.138.13）的变量只能取）的变量只能取0 0或或1 1，从而是一个，从而是一个0 01 1规划问题。下一章将指规划问题。下一章将指出出 ，一般的，一般的0 01 1规划问

50、题的求解极为困难。但指派问题（规划问题的求解极为困难。但指派问题（8.13 8.13 ）并）并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵或不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵或全幺模矩阵，其各阶非零子式均为全幺模矩阵，其各阶非零子式均为1 1），其非负可行解的分量只能），其非负可行解的分量只能取取0 0或或1 1，故约束，故约束“x xijij=0=0或或1 1”可改写为可改写为x xijij0 0而不改变其解。此时，而不改变其解。此时，（8.138.13）被转化为一个特殊的运输问题，其中）被转化为一个特殊的运输问题，其中m m= =n n, , a ai

51、 i= =b bi i=1=1。39上一页上一页下一页下一页二、求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家由于指派问题的特殊性，又存在着由匈牙利数学家KonigKonig提出的更为简提出的更为简便的解法便的解法匈牙利算法。算法主要依据以下事实：如果将系数矩阵匈牙利算法。算法主要依据以下事实：如果将系数矩阵C C= =（C Cijij）中一行（或一列）的每一元素都加上或减去同一个数，得到一）中一行（或一列）的每一元素都加上或减去同一个数，得到一个新矩阵个新矩阵B B= =（b bijij），则以），则以C C和和B B为系数矩阵的指派问题具有相同的最优为系数矩阵的指派问

52、题具有相同的最优指派。指派。 例例8.58.5 求解指派问题，其系数矩阵为求解指派问题，其系数矩阵为 40上一页上一页下一页下一页解解 将第一行元素减去此行中的最小元素将第一行元素减去此行中的最小元素1515，同样，第二行元素减，同样，第二行元素减去去1717，第三行元素减去，第三行元素减去1717，最后一行的元素减去，最后一行的元素减去1616，得，得再将第再将第3 3列元素各减去列元素各减去1 1，得，得以以B B2 2为系数矩阵的指派问题有最优指派为系数矩阵的指派问题有最优指派由等价性，它也是例由等价性，它也是例2 2的最优指派。的最优指派。有时问题会稍复杂一些，见下面的例有时问题会稍复

53、杂一些，见下面的例8.68.641上一页上一页下一页下一页例例8.68.6 求解下面的系数矩阵为求解下面的系数矩阵为C C的指派问题的指派问题解：先作等价变换如下解：先作等价变换如下容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但但n n=5=5，最优指派还无法看出。此时等价变换还可进行下去，最优指派还无法看出。此时等价变换还可进行下去 。 42上一页上一页下一页下一页步骤如下：步骤如下：（1 1）对未选出）对未选出0 0元素的行打元素的行打；（2 2）对）对行中行中0 0元素所在列打元素所在列打；（3 3）对）

54、对列中选中的列中选中的0 0元素所在行打元素所在行打；重复（重复（2 2）、（）、（3 3）直到无法再打）直到无法再打为止。为止。可以证明，若用直线划没有打可以证明，若用直线划没有打的行与打的行与打的列，就得到了能够复盖住的列，就得到了能够复盖住矩阵中所有零元素的最少条数的直线集合。找出未复盖的元素中的最小矩阵中所有零元素的最少条数的直线集合。找出未复盖的元素中的最小者，令者，令行元素减去此数，行元素减去此数，列元素加上此数，则原先选中的列元素加上此数，则原先选中的0 0元素不元素不变，而未复盖元素中至少有一个已转变为变，而未复盖元素中至少有一个已转变为0 0，且新矩阵的指派问题与原，且新矩阵

55、的指派问题与原问题也等价。上述过程可反复采用，直到能选出足够的问题也等价。上述过程可反复采用，直到能选出足够的0 0元素为至。例元素为至。例如，对例如，对例8.68.6变换后的矩阵再变换，第三行、第五行元素减去变换后的矩阵再变换，第三行、第五行元素减去 2 2，第一，第一列元素加上列元素加上 2 2，得，得现在已可看出，最优指派为现在已可看出，最优指派为（注：相应定理从略）（注：相应定理从略）43上一页上一页下一页下一页8.4 计算复杂性问题的提出离散模型的实质是从有限多个候选值中选取一个最佳取值。例如离散模型的实质是从有限多个候选值中选取一个最佳取值。例如8.18.1中中的线性规划，虽然可行

56、解一般有无穷多个，但线性规划基本定理指出，的线性规划，虽然可行解一般有无穷多个，但线性规划基本定理指出，只要存在有限最优解，就必可在基本可行解中找到，而基本可行解总共只要存在有限最优解，就必可在基本可行解中找到，而基本可行解总共只有有限多个。只有有限多个。DantzigDantzig的单纯形法正是利用了这一性质，在基本可行解的单纯形法正是利用了这一性质，在基本可行解中选取最优解。中选取最优解。在有限多个候选者中选择其中之一，通常不存在连续模型中备受关注的在有限多个候选者中选择其中之一，通常不存在连续模型中备受关注的解的存在性问题，因为有限个值中选取最佳取值，解的存在性不成问题。解的存在性问题，

57、因为有限个值中选取最佳取值，解的存在性不成问题。解的唯一性问题也不再被人们重视。例如，在用单纯形法求得一最优基解的唯一性问题也不再被人们重视。例如，在用单纯形法求得一最优基本可行解后，我们认为问题已被解出，它是否还有其他的最优解，我们本可行解后，我们认为问题已被解出，它是否还有其他的最优解，我们一般不再感兴趣。一般不再感兴趣。44上一页上一页下一页下一页也许有人会想，从有限种可能方案中挑选一种，这总是比较容易的。也许有人会想，从有限种可能方案中挑选一种，这总是比较容易的。如果一一比较下去，最后总可以得出满意的结果。然而，事实并非如如果一一比较下去，最后总可以得出满意的结果。然而，事实并非如此简

58、单，关键在于问题的规模和求解时的计算量。随着电子计算机的此简单，关键在于问题的规模和求解时的计算量。随着电子计算机的出现，人们对问题可解性的认识在观念上发生了根本改变。一个在理出现，人们对问题可解性的认识在观念上发生了根本改变。一个在理论上可解的问题如果在实际求解时需要化费不合理的时间（如几百年、论上可解的问题如果在实际求解时需要化费不合理的时间（如几百年、几千年甚至更长时间），我们不能心安理得地认为它已被解决，而应几千年甚至更长时间），我们不能心安理得地认为它已被解决，而应当去寻找更好、更实用的算法。当去寻找更好、更实用的算法。从本章开始，我们将区分问题与问题的实例。由于篇幅的限止，我们不准

59、从本章开始，我们将区分问题与问题的实例。由于篇幅的限止，我们不准备给出严格的定义。问题是一类实际问题的数学模型的总称，如线性规划备给出严格的定义。问题是一类实际问题的数学模型的总称，如线性规划问题、运输问题、指派问题等等。在一个问题中一般总包含着若干个参数，问题、运输问题、指派问题等等。在一个问题中一般总包含着若干个参数，给定这些参数，就给出了这一问题的一个实例。容易想到，单纯形法解一给定这些参数，就给出了这一问题的一个实例。容易想到，单纯形法解一个有几百个变量的线性规划实例一般总比解一个只有几十个变量的线性规个有几百个变量的线性规划实例一般总比解一个只有几十个变量的线性规划实例化费更多的时间

60、。因而，在估算一个算法的计算量时显然应当同时划实例化费更多的时间。因而，在估算一个算法的计算量时显然应当同时考虑到实例的规模。严格地讲，一个实例的规模应当用其输入数的二进制考虑到实例的规模。严格地讲，一个实例的规模应当用其输入数的二进制长度的总和来表示。但粗略地讲，变量的多少常常也能在一定程度上反映长度的总和来表示。但粗略地讲，变量的多少常常也能在一定程度上反映出实例规模的大小。在本书中，如无特别说明，我们将以变量个数来表示出实例规模的大小。在本书中，如无特别说明，我们将以变量个数来表示实例的规模，虽然这样做是不够严格的，但比较方便。实例的规模，虽然这样做是不够严格的，但比较方便。45上一页上

61、一页下一页下一页比较算法的好坏，从不同的角度出发，有各种不同的标准。在这里，比较算法的好坏，从不同的角度出发，有各种不同的标准。在这里，我们仅就算法的计算速度作一个十分粗略的比较。我们仅就算法的计算速度作一个十分粗略的比较。 例例8.78.7 （整理问题）给定（整理问题）给定n n个实数个实数a a1 1, , a a2 2, a an n，要求将它整理成由小到，要求将它整理成由小到大排列（或由大到小排列）的顺序：大排列（或由大到小排列）的顺序：b b1 1, , b b2 2, b bn n，b b1 1 b b2 2 b bn n。（算法（算法1 1） 取出取出a a1 1, , a a2

62、 2, a an n中的最小者，令其为中的最小者，令其为b b1 1。从。从a a1 1, , a a2 2, a an n中中去除去除b b1 1，在余下的，在余下的n n1 1个数中选出最小者，令其为个数中选出最小者，令其为b b2 2，直至得到，直至得到b b1 1, , b b2 2, b bn n。容易看出，为了排出容易看出，为了排出b b1 1, , b b2 2, b bn n，算法工作了，算法工作了 次比较。次比较。（算法（算法2 2）步步0 0 b b1 1a a1 1 步步1 1 设已有设已有b b1 1, , ,b bk k (1 (1knkn) )，将按两分法比较的方式

63、把，将按两分法比较的方式把a ak k+1+1排入其中：排入其中：若若b b1 1b bi ia ak+1k+1b bi i+1+1b bk k，令（，令（b b1 1, , b b2 2, , ,b bk k , , b bk k+1+1）（b b1 1, , , b bi i, , a ak k+1+1, , b bi i+1+1, , , , b bk k）。若）。若k k+1+1 b b4 4，可再和，可再和b b6 6比（若比（若a a8 8 b b4 4则和则和b b2 2比），易见，只比），易见，只要比要比3 3次即可排入次即可排入a a8 8，由于，由于r rloglog2 2

64、k k+1+1，算法的总经较次数不超过，算法的总经较次数不超过令令 ， ，设计算机每秒可作，设计算机每秒可作C C次比较，则算法次比较，则算法1 1与与算法算法2 2整理整理a a1 1, , a a2 2, a an n所用的时间分别为所用的时间分别为 若若n n=100=100万，万，C=100C=100万次万次/ /秒，则秒，则t t1 15.85.8天，而天，而t t2 22020秒。可见在较大规模的秒。可见在较大规模的整理问题时，算法整理问题时，算法2 2明显优于算法明显优于算法1 1。 47上一页上一页下一页下一页现设一台每小时能作现设一台每小时能作M M次运算的计算机，并设求解某

65、一问题已有了两个不次运算的计算机，并设求解某一问题已有了两个不同的算法。算法同的算法。算法A A对规模为对规模为n n的实例约需作的实例约需作n n2 2次运算而算法次运算而算法B B则约需作则约需作2 2n n次运次运算。于是，运用算法算。于是，运用算法A A在一小时内可解一个规模为在一小时内可解一个规模为 的实例，而算法的实例，而算法B B则则只能解一个规模为只能解一个规模为loglog2 2M M的实例。两者的差别究竟有多大呢？让我们来对的实例。两者的差别究竟有多大呢？让我们来对比一下。假如计算机每秒可作比一下。假如计算机每秒可作100100万次运算，则算法万次运算，则算法A A一小时大

66、约可解一个一小时大约可解一个规模为规模为n n=60000=60000的实例，而算法的实例，而算法B B在一小时内只能解一个规模在一小时内只能解一个规模 的实的实例且例且n n每增加每增加1 1，算法，算法B B求解时所化的时间就将增加求解时所化的时间就将增加1 1倍。例如算法倍。例如算法B B求解一求解一个个n n=50=50的实例将连续运算的实例将连续运算357357年多。年多。现设计算速度提高了现设计算速度提高了 100100倍，这对计算机来讲已是一个相当大的改进。此倍，这对计算机来讲已是一个相当大的改进。此时算法时算法A A可解问题的规模增大了可解问题的规模增大了1010倍，而算法倍，

67、而算法B B可解问题的规模只增加了可解问题的规模只增加了loglog2 2100710000，对任，对任意正整数意正整数N N，总可找到一个大于，总可找到一个大于N N的正整数的正整数n n及及D D的一个规模为的一个规模为n n的实例，对的实例，对这一实例有这一实例有fBfB( (D D, ,n n)=)=O O (2 (2knkn) )，则称，则称B B为求解问题为求解问题D D的一个指数算法。的一个指数算法。 多项式算法被称为是多项式算法被称为是“好好”的算法即所谓有效算法，而指数算法则一般被的算法即所谓有效算法，而指数算法则一般被认为是认为是“坏坏”算法，因为它只能求解规模极小的实例。

68、算法，因为它只能求解规模极小的实例。49上一页上一页下一页下一页下面的表下面的表8-148-14列出了在规模大约为列出了在规模大约为n n时各类算法的计算量，而时各类算法的计算量，而表表8-158-15则反映了当计算机速度提高则反映了当计算机速度提高1010倍、倍、100100倍时，各类算法倍时，各类算法在在1 1小时内可求解的问题的模型的增长情况，（前三个是多项小时内可求解的问题的模型的增长情况，（前三个是多项式时间的，后两个是指数时间的）式时间的，后两个是指数时间的） 表表8-14 8-14 几个多项式和指数时间复杂性函数增长情况几个多项式和指数时间复杂性函数增长情况算法要求的算法要求的计

69、算量算量规模模n的近似的近似值101001000n101001000nlogn336649966n31031061092n10241.2710301.0510301n!362880010158410256750上一页上一页下一页下一页表表8-15 18-15 1小时内可解的问题实例的规模小时内可解的问题实例的规模算法要求的算法要求的计算量算量用用现在在计算机算机用快用快10倍倍计算机算机用快用快100倍倍计算机算机nN110N1100N1nlognN28.2N267N2n3N32.15N34.64N32nN4N4+3.32N4+6.64n!N5N5+2N5+3由定义由定义8.48.4知知4 4

70、n n2 2与与2 2n n2 2都是都是O O( (n n2 2) )，n nloglogn n+3+3n n是是O O( (n nloglogn n) )，我们在以后分析，我们在以后分析时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效通过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效率的关键因素。率的关键因素。51上一页上一页下一页下一页一、P类与NP类，NP完全性 这样看来，对一个问题，只有在找到求解它的多项式算法后我们才能较为放心。假如我

71、们遇到了一个规模很大的实例今天无法求解它，但我们仍可寄希望于将来。通过计算机的改进，在将来求解它仍然是可能的。而对指数算法，你就不会有这种信心。然而，十分可惜的是，对于许然而，十分可惜的是，对于许许多多具有十分广泛应用价值许多多具有十分广泛应用价值的离散问题，人们至今尚未找的离散问题，人们至今尚未找到求解它们的有效算法。到求解它们的有效算法。 52上一页上一页下一页下一页定义定义8.68.6 （P P问题与问题与P P类）类） 存在多项式算法的问题被称为存在多项式算法的问题被称为P P问题，所有问题，所有P P问题构成的问题类被称为问题构成的问题类被称为P P类，简记为类，简记为P P。根据定

72、义，整理问题是一个根据定义，整理问题是一个P P问题，存在求解它的问题，存在求解它的O O（n nloglog2 2n n）算法。在下）算法。在下一章中，我们还将讨论一些一章中，我们还将讨论一些P P问题并介绍求解它们的有效算法。我们将会问题并介绍求解它们的有效算法。我们将会发现，发现，P P问题从某种意义上讲是性质较好从而较易求解的问题。问题从某种意义上讲是性质较好从而较易求解的问题。由于线性规划在现实生活中有着极其广泛的应用，人们自然会问：单纯形由于线性规划在现实生活中有着极其广泛的应用，人们自然会问：单纯形法是不是有效算法？线性规划是不是法是不是有效算法？线性规划是不是P P问题？问题？

73、19721972年，年，KleeKlee和和MintyMinty以下面的著名例子证明单纯形法是指数算法而不是以下面的著名例子证明单纯形法是指数算法而不是多项式算法。多项式算法。例例8.88.8max max x xn nS.tS.t x x1 11 1x xj j1 1x xj j1 1x xj j1 1，（，（j j=2,=2, ,n n）其中其中是一个充分小的正数。是一个充分小的正数。 53上一页上一页下一页下一页图图8.28.2给出了给出了n n=3=3时的可行域，它是三维空间中单位立方体的一个微小摄时的可行域，它是三维空间中单位立方体的一个微小摄动。在确定的进基原则下（如检验数最负者进

74、基），若以动。在确定的进基原则下（如检验数最负者进基），若以x x0 0= =（, ,2 2, ,3 3）为初始基本可行解，在单纯形法迭代改进时，将经过）为初始基本可行解，在单纯形法迭代改进时，将经过每一基本可行解，最终到达最优解每一基本可行解，最终到达最优解x x* *= =（, ,2 2,1,13 3），其路径已用），其路径已用箭线画在图上，故迭代中共经过箭线画在图上，故迭代中共经过2 23 3个极点。对于规模为个极点。对于规模为n n的一般问题的的一般问题的实例，迭代步数为实例，迭代步数为2 2n n，故单纯形法为指数算法。，故单纯形法为指数算法。 54上一页上一页下一页下一页单纯形法自

75、单纯形法自19471947年被提出以来经历了无数次的考验，被证明是一种实用效年被提出以来经历了无数次的考验，被证明是一种实用效果极佳的算法。但果极佳的算法。但KleeKlee的例子又无可争辨地证明了它事实上是一个指数算的例子又无可争辨地证明了它事实上是一个指数算法，这两者是否予盾呢？其实两者并不矛盾。指数算法的定义规定，只要法，这两者是否予盾呢？其实两者并不矛盾。指数算法的定义规定，只要存在着存在着fBfB ( ( D D, ,n n) = ) = O O( (2kn) )的例子，算法的例子，算法B B就是指数算法，它并没有涉及到就是指数算法，它并没有涉及到我们遇到这样的例子的机会究竟有多大。

76、几十年来，人们在实际应用单纯我们遇到这样的例子的机会究竟有多大。几十年来，人们在实际应用单纯形法时，一次也没有碰到过例形法时，一次也没有碰到过例8.88.8那样的情况，（那样的情况，（KleeKlee的例子是人为构造的例子是人为构造的），可以证明，遇到例的），可以证明，遇到例8.88.8这样的例子的概率为这样的例子的概率为0 0。于是，人们自然会从。于是，人们自然会从另一角度另一角度算法的平均执行情况的角度去评价一个算法，有兴趣的读者算法的平均执行情况的角度去评价一个算法，有兴趣的读者可以参阅相应的书籍与文献。可以参阅相应的书籍与文献。既然单纯形法是指数算法，那么是否存在求解线性规划问题的多项

77、式算法既然单纯形法是指数算法，那么是否存在求解线性规划问题的多项式算法呢？或者换句话讲，线性规划问题是呢？或者换句话讲，线性规划问题是P P问题吗？问题吗？ 在长达七年的时间里这一引人注目的问题一直悬而未决，存在着两种完全在长达七年的时间里这一引人注目的问题一直悬而未决，存在着两种完全对立的观点。直到对立的观点。直到19791979年，前苏联的数学家年，前苏联的数学家L.G.KhachinaL.G.Khachina提出求解线性规提出求解线性规划问题的椭球算法，才证明线性规划是一个划问题的椭球算法，才证明线性规划是一个P P问题。他的方法与以前的方问题。他的方法与以前的方法截然不同，甚至完全不用

78、线性规划基本定理法截然不同，甚至完全不用线性规划基本定理 ，以意想不到的方式解决，以意想不到的方式解决了这个较长时间解决不了的难题，在当时引起了全球性的轰动。了这个较长时间解决不了的难题，在当时引起了全球性的轰动。 对椭球算法有兴趣的读者可以对椭球算法有兴趣的读者可以参阅参阅C.H.PapadimitriouC.H.Papadimitriou等著等著的的“组合最优化，算法和复杂组合最优化，算法和复杂性性”一书第八章或姚恩瑜等编一书第八章或姚恩瑜等编著的著的“数学规划与组合优化数学规划与组合优化”一书第六章。一书第六章。 55上一页上一页下一页下一页椭球算法虽然是多项式算法，但其实用效果却赶不上

79、单纯形法，这一事椭球算法虽然是多项式算法，但其实用效果却赶不上单纯形法，这一事实又吸引众多数学家去寻找实用效果也比单纯形法好的有效算法。实又吸引众多数学家去寻找实用效果也比单纯形法好的有效算法。19841984年，美国贝尔实验室的数学家年，美国贝尔实验室的数学家KarmarkarKarmarkar提出了以他名字命名的算法，其提出了以他名字命名的算法，其实用效果也相当不错。寻找实用效果更好的求解线性规划的有效算法，实用效果也相当不错。寻找实用效果更好的求解线性规划的有效算法，至今仍是一个十分活跃的研究课题。至今仍是一个十分活跃的研究课题。对于众多至今尚未发现多项式算法的离散问题，是否也会在将来的

80、某对于众多至今尚未发现多项式算法的离散问题，是否也会在将来的某一天突然找到有效算法呢？至今对其中的大多数问题，数学家们目前一天突然找到有效算法呢？至今对其中的大多数问题，数学家们目前抱有怀疑的态度，即认为抱有怀疑的态度，即认为P P类之外存在着非类之外存在着非P P问题。由于计算机输入、问题。由于计算机输入、输出及运算中使用的数均为有理数，我们可以假定问题的参数取值为输出及运算中使用的数均为有理数，我们可以假定问题的参数取值为有理数，甚至，等价地，可假定其取值均为整数。此外，问题也可等有理数，甚至，等价地，可假定其取值均为整数。此外，问题也可等价地描述为判定问题，即解答时只需回答价地描述为判定

81、问题，即解答时只需回答“是是”或或“否否”的问题。的问题。 56上一页上一页下一页下一页例例8.98.9 （哈密顿圈问题（哈密顿圈问题简记简记HCHC）给定一个图）给定一个图G=G=（V V，E E），其中），其中V V为顶为顶点集合，点集合，E E为图的边集。问为图的边集。问G G中是否存在着哈密顿圈。中是否存在着哈密顿圈。 所所谓哈密哈密顿圈是指由一个圈是指由一个顶点出点出发，经过所有所有顶点一次而回到出点一次而回到出发点的点的闭回路。哈密回路。哈密顿圈圈问题是一个判定是一个判定问题，因，因为它只要求回答是或者否。它只要求回答是或者否。 非判定非判定问题可以可以转化化为等价的判定等价的判定

82、问题，所，所谓等价是指是否存在多等价是指是否存在多项式算式算法法这一意一意义下的等价。下的等价。为此，我此，我们需要用到以下多需要用到以下多项式式时间转化的概念。化的概念。定义定义8.78.7 （多项式转化）设（多项式转化）设D D1 1、D D2 2为两个判定问题，若存在求解两问题的为两个判定问题，若存在求解两问题的算法算法 A A1 1和和A A2 2，其中求解，其中求解D D2 2的算法的算法A A2 2是多项式次地调用求解是多项式次地调用求解D D1 1的算法的算法A A1 1而实而实现的，则称问题现的，则称问题D D2 2可以多项式转化为可以多项式转化为D D1 1，简记为，简记为D

83、 D2 2D D1 1 容易看出，若容易看出，若D D2 2可多项式转化为可多项式转化为D D1 1，又，又D D1 1是是P P问题，则问题，则D D2 2也是也是P P问题，因为求问题，因为求解解D D2 2的有效算法可以通过多项式次地以求解的有效算法可以通过多项式次地以求解D D1 1的有效算法为子程度调用而的有效算法为子程度调用而作出，（从某种意义上讲，作出，（从某种意义上讲，D D1 1不比不比D D2 2容易）。容易）。57上一页上一页下一页下一页例例8.108.10 （旅行商问题（旅行商问题简记简记TSPTSP）设有）设有n n个城市个城市1,2,1,2, ,n n ，城，城i

84、i到城到城j j的距离的距离 C Cijij已知（注：已知（注：C Cijij与与C Cjiji可以不相等），某商人准备从城可以不相等），某商人准备从城1 1出发，去出发，去其余各城推销商品，若所有城市均必需去且仅去一次，最后返回出发城市，其余各城推销商品，若所有城市均必需去且仅去一次，最后返回出发城市，问该商人应如何安排旅行，才能使所走的总路程最短。问该商人应如何安排旅行，才能使所走的总路程最短。TSPTSP实际上是要求从一有向图实际上是要求从一有向图G=G=（V V，A A）中寻找出一条具有最小总长度的）中寻找出一条具有最小总长度的HCHC，其中，其中V=1,2,V=1,2, ,n n ，

85、A=( A=( i i, , j j ) | ) | i i, , j j V V, , i ij j ，作有向图的，作有向图的原因是原因是C Cijij与与C Cjiji可能不相等。如果可能不相等。如果C Cijij为由城为由城i i到城到城j j的旅费，则的旅费，则TSPTSP要求的是要求的是一个具有最小费用的一个具有最小费用的HCHC。与与TSPTSP等价的判定问题可如下叙述：给定一正整数等价的判定问题可如下叙述：给定一正整数K K，问是否存在总长度不，问是否存在总长度不超过超过K K的的HCHC。TSPTSP与其相应的判定问题是等价的，一方面，若存在求解相应与其相应的判定问题是等价的，

86、一方面，若存在求解相应判定问题的算法判定问题的算法A A，我们可以先找出，我们可以先找出G G的的HCHC总长度的一个上界（例如最大边总长度的一个上界（例如最大边长度的长度的n n倍），记为倍），记为K K。然后反复对。然后反复对K K使用两分法并调用判定问题的算法使用两分法并调用判定问题的算法A A以以判定是否存在总长不超过判定是否存在总长不超过K K的的HCHC，调用的次数不超过输入数据总长度的一，调用的次数不超过输入数据总长度的一个多项式界。另一方面，若存在个多项式界。另一方面，若存在TSPTSP的一个算法的一个算法A A，在求得，在求得G G的具有最小总的具有最小总长度的长度的HCHC

87、后，其对应判定问题的答案自然立即可以得出。所以，后，其对应判定问题的答案自然立即可以得出。所以，TSPTSP与其与其相应的判定问题（在是否为相应的判定问题（在是否为P P问题这一点上）是等价的。问题这一点上）是等价的。58上一页上一页下一页下一页可以证明，可以证明，HCHCTSPTSP。事实上，若。事实上，若TSPTSP存在一算法存在一算法A A，就可构造如下求解，就可构造如下求解HCHC的算法：对的算法：对G=G=（V V，E E）i i、j jV V且且i ij j，若（，若（i i, , j j）E E令令C Cijij=1=1，若（，若（i i, , j j）E E，补充边（，补充边（

88、i i, , j j）且令）且令C Cijij=2=2，得到图，得到图G G= =（V V，E E）并求解）并求解G G对对应的应的TSPTSP（利用算法（利用算法A A）。容易看出，）。容易看出，G G有有HCHC（即回答是），当且仅当（即回答是），当且仅当G G的最小总长度的最小总长度HCHC之长度不超过之长度不超过n n，故，故HCHC可多项式转化为可多项式转化为TSPTSP。从这一意义。从这一意义上讲，至此可以认为求解上讲，至此可以认为求解TSPTSP不会比求解不会比求解HCHC容易，因为如果容易，因为如果TSPTSP是是P P问题，问题，HCHC一定也是一定也是P P问题。虽然问题。

89、虽然HCHC与与TSPTSP是等价的，但仅根据上面的证明，我们是等价的，但仅根据上面的证明，我们还不能得出相反的结论成立。还不能得出相反的结论成立。现在，我们来拓宽视线，把研究范围扩大以一个有可能比现在，我们来拓宽视线，把研究范围扩大以一个有可能比P P类更大的集合。类更大的集合。定义定义8.88.8 （NPNP类）类） 设设D D是一个判定问题，若对是一个判定问题，若对D D的每一个回答的每一个回答“是是”的的实例，它给出的回答均可经多项式界的运算加以检验，则称实例，它给出的回答均可经多项式界的运算加以检验，则称D D为一个为一个NPNP问问题。由全体题。由全体NPNP问题构成的问题类称为问

90、题构成的问题类称为NPNP类，简记为类，简记为NPNP。定义定义8.88.8并非并非NPNP类的严格定义，其严格定义的给出常常要用到非确定型类的严格定义，其严格定义的给出常常要用到非确定型TuringTuring机、非确定型算法等自动机理论方面的知识。机、非确定型算法等自动机理论方面的知识。 59上一页上一页下一页下一页定理定理8.88.8 P NP证明：证明：D DP P，存在着求解问题，存在着求解问题D D的多项式算法。既然的多项式算法。既然D D的任一实例均可在的任一实例均可在一多项式界内解出，其相应的判定问题究意为一多项式界内解出，其相应的判定问题究意为“是是”或或“否否”自然也均自然

91、也均可在多项式界内给出回答。其回答为可在多项式界内给出回答。其回答为“是是”的答案也必可在多项式界内的答案也必可在多项式界内检验，故检验，故D DNPNP。由。由D D的任意性，可知的任意性，可知PNPPNP。 至少在目前看来，至少在目前看来，NPNP是一个比是一个比P P宽广得多的问题类。对于那些宽广得多的问题类。对于那些为数众多的、至今尚未发现多项式算法的问题，其中相当大一为数众多的、至今尚未发现多项式算法的问题，其中相当大一部分可以十分容易地证明是部分可以十分容易地证明是NPNP问题。例如，问题。例如，HCHC和和TSPTSP至今均未至今均未找到求解它们的有效算法，但容易证明，找到求解它

92、们的有效算法，但容易证明，HCHCNPNP及及TSPTSPNPNP。因为验证一个圈是否是哈密顿圈及验证一哈密顿圈的总长是否因为验证一个圈是否是哈密顿圈及验证一哈密顿圈的总长是否不超过不超过K K是十分容易的，计算量不超过一个多项式界。是十分容易的，计算量不超过一个多项式界。 60上一页上一页下一页下一页前面已经谈到，绝大多数数学家猜测前面已经谈到，绝大多数数学家猜测P PNPNP。如果这一猜测是正确的，那。如果这一猜测是正确的，那么哪些问题不在么哪些问题不在P P中的可能性最大（即最不可能有多项式算法）。中的可能性最大（即最不可能有多项式算法）。19721972年，年，加拿大数学家加拿大数学家

93、S.A.CookS.A.Cook发表了一篇十分著名的论文。他指出，存在一类发表了一篇十分著名的论文。他指出，存在一类他称之为他称之为NPNP完全类的问题，这类问题有如下两个性质：（完全类的问题，这类问题有如下两个性质：（1 1）这类问题中）这类问题中的任何一个都不能用任何已知的多项式算法求解（尽管数学家们已作了的任何一个都不能用任何已知的多项式算法求解（尽管数学家们已作了几十年努力，至今仍毫无结果）；（几十年努力，至今仍毫无结果）；（2 2）若其中的任何一个问题有了多项）若其中的任何一个问题有了多项式算法，则该类中的任何一个也就有了多项式算法。式算法，则该类中的任何一个也就有了多项式算法。Co

94、okCook在他的文章中在他的文章中证明，满足问题（简记证明，满足问题（简记SATSAT）是）是NPNP完全的，任一完全的，任一NPNP问题可多项式转化为问题可多项式转化为SATSAT问题。故假如能找到求解问题。故假如能找到求解SATSAT问题的多项式时间算法，则任一问题的多项式时间算法，则任一NPNP问题问题均能找到多项式算法。由于普遍认为均能找到多项式算法。由于普遍认为P PNPNP，故，故SATSAT问题被认为不可能存问题被认为不可能存在多项式算法（否则将得出令人震惊的结果在多项式算法（否则将得出令人震惊的结果P P= =NPNP）。）。 为了说明什么是为了说明什么是SATSAT问题，先

95、引进下面的定义。问题，先引进下面的定义。定义定义8.98.9 （布尔变量与布尔表达式）一个只能取值（布尔变量与布尔表达式）一个只能取值“真真 ”和和“假假”（或者（或者“0 0”和和“1 1”）的变量称为布尔变量。一个由布尔变量通过）的变量称为布尔变量。一个由布尔变量通过“或或”、“与与”、“非非”逻辑运算符号连接而成的表达式称为布尔表达式。逻辑运算符号连接而成的表达式称为布尔表达式。（注：可用（注：可用“+ +”表示表示“或或”，“”表示表示“与与”，“”表示表示“x x非非”）61上一页上一页下一页下一页例例8.108.10 (1)(1)(2) (2) 布尔表达式中每一括号内的子式被称为一

96、个句子。当且仅当每一句子的取布尔表达式中每一括号内的子式被称为一个句子。当且仅当每一句子的取值为真时布尔表达式的值才为真。给定一个布尔表达式，若存在布尔变量值为真时布尔表达式的值才为真。给定一个布尔表达式，若存在布尔变量的一组取值使此表达式的值为真，则称此布尔表达式是可满足的，否则称的一组取值使此表达式的值为真，则称此布尔表达式是可满足的，否则称之为不可满足的。例之为不可满足的。例8.108.10中的（中的（1 1）是可满足的，而（）是可满足的，而（2 2）是不可满足的。）是不可满足的。（1 1）和（）和（2 2）都是布尔表达式。对（）都是布尔表达式。对（1 1），若取），若取x x1 1=

97、=真，真，x x2 2= =真，真，x x3 3= =假，则假，则表达式的值为真，对（表达式的值为真，对（2 2），不论布尔变量怎样取值，布尔表达式（），不论布尔变量怎样取值，布尔表达式（2 2）的）的值均不可能为真。值均不可能为真。62上一页上一页下一页下一页例例8.12 8.12 （SATSAT问题）问题） 给定布尔变量给定布尔变量x x1,1,xnxn的一个布尔表达式的一个布尔表达式c c11c c22cmcm，其中，其中cici为用为用x x1,1,xnxn构成的句子，问此表达式是可满足的构成的句子，问此表达式是可满足的吗？吗？ SATSAT问题是数理逻辑中的中心问题之一，这一点可从计

98、算机的运算方式看出，问题是数理逻辑中的中心问题之一，这一点可从计算机的运算方式看出，故设计一个较好的求解故设计一个较好的求解SATSAT问题的算法具有重要意义。问题的算法具有重要意义。19721972年，年，R.M.KarpR.M.Karp 以多项式转化的方式证明并列出以多项式转化的方式证明并列出2121个个NPNP完全问题。此后，完全问题。此后，大量大量NPNP完全问题一一被证明。短短十几年时间，已知的完全问题一一被证明。短短十几年时间，已知的NPNP完全问题就达到了完全问题就达到了 40004000多个，其中包括前面提到过的多个，其中包括前面提到过的HCHC和和TSPTSP。总之，。总之，

99、NPNP完全类是一个极为庞完全类是一个极为庞大的问题类，其中包含着无穷多个问题。按照目前普遍的看法，这些问题中大的问题类，其中包含着无穷多个问题。按照目前普遍的看法，这些问题中的任意一个都不应当有多项式算法，即求解它的任一算法在遇到最的任意一个都不应当有多项式算法，即求解它的任一算法在遇到最“坏坏”的的实例时都需要化指数时间。实例时都需要化指数时间。 P P类、类、NPNP完全类及完全类及NPNP类的关系如图类的关系如图8.38.3所示，即，所示，即，NPNP完完全类。还有很多离散问题目前尚未搞清它们的计算复全类。还有很多离散问题目前尚未搞清它们的计算复杂性。有些将被证明是杂性。有些将被证明是

100、P P问题，有些将被证明是问题，有些将被证明是 NPNP完完全的。此外，确实存在着全的。此外，确实存在着NPNP以外的问题，其求解更为以外的问题，其求解更为困难。困难。63上一页上一页下一页下一页二、有关离散问题模型及其算法的几点附加说明最近几十年来，有成千上万离散问题的模型得到了广泛而又较为深入的最近几十年来，有成千上万离散问题的模型得到了广泛而又较为深入的研究。因而，当我们研究一个离散型的问题时，首先要搞清遇到的实际研究。因而，当我们研究一个离散型的问题时，首先要搞清遇到的实际课题是否为某一别人已研究过的问题的一个实例。搞清这一点十分重要，课题是否为某一别人已研究过的问题的一个实例。搞清这

101、一点十分重要，否则你的努力完全可能是一种徒劳。否则你的努力完全可能是一种徒劳。例例8.138.13 某工厂在生产一种产品或部件时，需要在一些指桑骂槐定位置某工厂在生产一种产品或部件时，需要在一些指桑骂槐定位置上钻孔。问应按怎样的顺序钻孔，才能使加工速度最快。上钻孔。问应按怎样的顺序钻孔，才能使加工速度最快。 由于生产是连续进行的，钻头将从一钻孔位置出发到各指定点钻孔，最由于生产是连续进行的，钻头将从一钻孔位置出发到各指定点钻孔，最后返回原位置，以便加工下一个产品或部件。显然，这是一个旅行商问后返回原位置，以便加工下一个产品或部件。显然，这是一个旅行商问题。题。然而，是否为某一问题的实例有时并不

102、是一目了然的。然而，是否为某一问题的实例有时并不是一目了然的。64上一页上一页下一页下一页例例8.14 8.14 在轧钢等生产中，为了保持工件的温度，工件在一台机器上在轧钢等生产中，为了保持工件的温度，工件在一台机器上加工以后必需立即转送下台机器加工，中间不允许出现工件等待现象。加工以后必需立即转送下台机器加工，中间不允许出现工件等待现象。现设共有现设共有n n个工件个工件J Ji i( (i i=1,=1, ,n n) )需要进行加工，且加工有以下特点：需要进行加工，且加工有以下特点：（i i）加工不同工件时，使用机器的顺序可以不同。）加工不同工件时，使用机器的顺序可以不同。（iiii）每一

103、工件在每台机器上至少加工一次。）每一工件在每台机器上至少加工一次。（iiiiii）每台机器加工各工件的顺序相同。）每台机器加工各工件的顺序相同。（iviv）工件加工中不允许有中间等待。）工件加工中不允许有中间等待。要求确定要求确定1,1, ,n n （工件编号）的一个排序（工件编号）的一个排序 i i1 1, , ,i in n ，使得总加工时，使得总加工时间最少。间最少。 例例8.138.13是排序（是排序（SchedulingScheduling）问题的一个子问题，这个子问题的计算复杂）问题的一个子问题，这个子问题的计算复杂性如何呢？下面的分析表明，这一子问题实质上就是旅行商问题，从而是性

104、如何呢？下面的分析表明，这一子问题实质上就是旅行商问题，从而是NPNP完全的。完全的。 65上一页上一页下一页下一页图图8.48.4给出了一个三台机器给出了一个三台机器二个工件的实例。工作二个工件的实例。工作J Ji i需需加工加工5 5次，依次使用机器次，依次使用机器2 21 12 25 52 2。工作。工作J Ji i需需加工加工4 4次，依次使用机器次，依次使用机器1 12 23 31 1。该图是设先加。该图是设先加工工J Ji i作出的，图中的点表示作出的，图中的点表示加工活动，旁边的数字为加加工活动，旁边的数字为加工时间，箭线反映加工顺序。工时间，箭线反映加工顺序。由图由图8.48.

105、4可以看出，按可以看出，按J Ji i、J Jj j顺序加工，两工件至少要加工顺序加工，两工件至少要加工1212单位时单位时间，两工件开始加工时间至少相差间，两工件开始加工时间至少相差5 5单位时间，否则必然将出现等待。单位时间，否则必然将出现等待。66上一页上一页下一页下一页对于一般问题，设加工顺序为对于一般问题，设加工顺序为 i i1 1, , ,i in n ，则在此顺序下的最短加工时间，则在此顺序下的最短加工时间T T可按如下方法求得：对每一对工件可按如下方法求得：对每一对工件J Jikik和和J Jjkjk+1+1，先求它们开工时间差的最小，先求它们开工时间差的最小值值 （可用一子程

106、序计算），（可用一子程序计算），令令 其中其中 为最后工件在各机器上加工时间的总和。为最后工件在各机器上加工时间的总和。 的出现使得的出现使得T T的计算公式不够整齐，为此引入一个虚工件的计算公式不够整齐，为此引入一个虚工件J J0 0，它需在各，它需在各机器上加工一次，加工时间均为机器上加工一次，加工时间均为0 0，并记，并记C Ci i0 0为工件为工件i i的总中工时间，的总中工时间，C Coioi=0=0，则有，则有其中其中i i0 0=0=0， i in n+1+1=0=0，问题化为求，问题化为求1,1, ,n n 的一个排序的一个排序 i i1 1, , ,i in n ，使按此，

107、使按此顺序加工，顺序加工， 有最小。显然，这是有最小。显然，这是TSPTSP。 67上一页上一页下一页下一页从上述讨论容易看出，给定了从上述讨论容易看出，给定了 J J1 1, , ,J Jn n ，可在，可在O O( (n n2 2) )步内求出所有步内求出所有C Cijij，从，从而使问题化为而使问题化为TSPTSP，若，若TSPTSP多项式可解，则例多项式可解，则例8.138.13也多项式可解。反之，对也多项式可解。反之，对每一每一TSPTSP的实例，也可在多项式时间内构造出一个不允许等待的排序问题，的实例，也可在多项式时间内构造出一个不允许等待的排序问题，若不允许等待的排序问题多项式可

108、解，则若不允许等待的排序问题多项式可解，则TSPTSP也多项式可解。这样，就搞也多项式可解。这样，就搞清了不允许等待的排序问题多项式可解，则清了不允许等待的排序问题多项式可解，则TSPTSP也多项式可解。故不允许也多项式可解。故不允许等待的机器加工问题是等待的机器加工问题是NPNP完全的，因为它等价于完全的，因为它等价于NPNP完全问题完全问题TSPTSP。不过，。不过，在大多数情况下，找出此类多项式转化关系并不是一件容易的事，它不仅在大多数情况下，找出此类多项式转化关系并不是一件容易的事，它不仅需要对别人已研究过的各类问题有充分的了解，还可能要用到十分精细而需要对别人已研究过的各类问题有充分

109、的了解，还可能要用到十分精细而又巧妙的技巧。又巧妙的技巧。在建立起实际问题的数学模型后，还应考虑一下是否有必要将模型标准化。在建立起实际问题的数学模型后，还应考虑一下是否有必要将模型标准化。也许，适当的标准化会为下一步的研究及算法设计提供方便。先将模型标也许，适当的标准化会为下一步的研究及算法设计提供方便。先将模型标准化，然后再去寻找算法的例子屡见不鲜。在上一章中求解线性规划的单准化，然后再去寻找算法的例子屡见不鲜。在上一章中求解线性规划的单纯形法是针对标准形式设计的，容易看出这种做法避免了众多麻烦。虽然纯形法是针对标准形式设计的，容易看出这种做法避免了众多麻烦。虽然人们至今尚未发现求解人们至

110、今尚未发现求解TSPTSP的好算法，但细心的读者不难看出，一般图的好算法，但细心的读者不难看出，一般图G G（某些顶点之间可以无边相连）上的（某些顶点之间可以无边相连）上的TSPTSP的求解与完全图（任意两顶点间的求解与完全图（任意两顶点间均有边相连）上的均有边相连）上的TSPTSP的求解是等价的。因而，我们只需去寻找完全图的求解是等价的。因而，我们只需去寻找完全图TSPTSP的算法，这样做的好处是我们可以完全不必顾及去检查图中是否存在着旅的算法，这样做的好处是我们可以完全不必顾及去检查图中是否存在着旅行圈（即行圈（即HCHC），而），而HCHC存在性的检验同样是十分困难的。存在性的检验同样是

111、十分困难的。68上一页上一页下一页下一页建立数学模型当然不是我们的最终目的，任一研究实际课题的人早建立数学模型当然不是我们的最终目的，任一研究实际课题的人早晚总会遇到设计求解算法的问题。不论你是否意识到，从你开始着晚总会遇到设计求解算法的问题。不论你是否意识到，从你开始着手设计算法的一刻起，你已站在了一个手设计算法的一刻起，你已站在了一个“十字街口十字街口”。你研究的问。你研究的问题具有求解它的多项式算法吗（即它是一个题具有求解它的多项式算法吗（即它是一个P P问题吗）？如果你研究问题吗）？如果你研究的问题是的问题是P P问题，而你设计的算法却不是多项式算法，它或者不会被问题，而你设计的算法却

112、不是多项式算法，它或者不会被别人接受，或者早晚会被别人推翻。反之，如果你拼全力去寻找多别人接受，或者早晚会被别人推翻。反之，如果你拼全力去寻找多项式算法，又非常可能会一无所获，因为你研究的问题如果不是项式算法，又非常可能会一无所获，因为你研究的问题如果不是P P问问题，例如它是题，例如它是NPNP完全的，你根本不可能找到多项式算法。只要完全的，你根本不可能找到多项式算法。只要P PNPNP，这样的算法是根本不存在的。可是，除非你已经找出了多项式算，这样的算法是根本不存在的。可是，除非你已经找出了多项式算法（从而确立了它是法（从而确立了它是P P问题），你无法知道手头的问题到底属于哪一问题），你

113、无法知道手头的问题到底属于哪一类，你似乎走进了一个怪圈。在这种情况下怎么办才较好吗？据一类，你似乎走进了一个怪圈。在这种情况下怎么办才较好吗？据一些建树卓著的专家们介绍，此时最好采用双向攻关的办法。寻找多些建树卓著的专家们介绍，此时最好采用双向攻关的办法。寻找多项式算法的失败也许会为证明问题的项式算法的失败也许会为证明问题的NPNP完全性提供信息，而证明完全性提供信息，而证明NPNP完全性中遇到的困难又也许会为设计多项式算法开辟新途径。当然，完全性中遇到的困难又也许会为设计多项式算法开辟新途径。当然，毫不奇怪，相当一部分问题会久攻不下，成为悬而未决的问题。毫不奇怪，相当一部分问题会久攻不下，成

114、为悬而未决的问题。 69上一页上一页下一页下一页假如你经过一段时间的研究，倾向于相信你的问题是假如你经过一段时间的研究，倾向于相信你的问题是NPNP完全的，最完全的，最好能证明它，因为否则只能一无所获。证明只能如下进行：从已知好能证明它，因为否则只能一无所获。证明只能如下进行：从已知为为NPNP完全的问题中适当选出一个来（这样的问题有成千上万个），完全的问题中适当选出一个来（这样的问题有成千上万个），证明这一证明这一NPNP完全问题可以多项式转化为你研究的问题。只要能做到完全问题可以多项式转化为你研究的问题。只要能做到这一点，你就可以交差了。然而，其中有很多的困难，最大的困难这一点，你就可以交

115、差了。然而，其中有很多的困难，最大的困难之一是确定选择哪一个问题是最合适的。在这里，经验起了很大的之一是确定选择哪一个问题是最合适的。在这里，经验起了很大的作用。虽然从理论上讲，任意已知的作用。虽然从理论上讲，任意已知的NPNP完全问题均可用于证明一个完全问题均可用于证明一个新问题的新问题的NPNP完全性，但实际上某些问题似乎更合适一些。完全性，但实际上某些问题似乎更合适一些。R.M.KarpR.M.Karp在在19721972年发表的论文中列出了年发表的论文中列出了2121个个NPNP完全问题，下面的六个问题就完全问题，下面的六个问题就包含在其中，并被认为是初学者应当掌握的基本核心，在此基础

116、上包含在其中，并被认为是初学者应当掌握的基本核心，在此基础上再去扩展自己掌握的再去扩展自己掌握的NPNP完全类。只有掌握了已有的一些结果和方法，完全类。只有掌握了已有的一些结果和方法，才有可能去证明新问题的才有可能去证明新问题的NPNP完全性，六个基本的完全性，六个基本的NPNP完全问题为：完全问题为： 70上一页上一页下一页下一页（1 1）（）（3 3满足问题，简记满足问题，简记3 3SATSAT问题）问题） 每一个句子都是一个三项式每一个句子都是一个三项式的的SATSAT问题，称为问题，称为3 3SATSAT问题。问题。例如，例如， 就是就是3 3SATSAT的一个实例。的一个实例。2 2

117、）（三维匹配问题）（三维匹配问题3DM3DM）X X、Y Y、Z Z是三个不相交的集合，是三个不相交的集合，| | X X | = | | = | Y Y | = | | = | Z Z | =| =q q，。，。 问：问：M M中是否包含一个匹配中是否包含一个匹配M M，使得，使得 （等价问题是求最大三维匹配）。（等价问题是求最大三维匹配）。 注：这里给出的是标准形式，一般可不必要求注：这里给出的是标准形式，一般可不必要求| | X X | = | | = | Y Y | = | | = | Z Z | |，表示笛卡尔乘积。，表示笛卡尔乘积。三维匹配问题是下一章中二维匹配（三维匹配问题是下一

118、章中二维匹配（2DM2DM）问题的推广，）问题的推广，2 2DMDM是是P P问题而问题而3 3DMDM是是NPNP完全的。一个匹配是指完全的。一个匹配是指M M的一个子集合的一个子集合(x xi i, , y yi i, , z zi i)，x xi iX X，y yi iY Y，z zi iZ Z，且当下标不同时，它们分别取三个集合中的不同元素。，且当下标不同时，它们分别取三个集合中的不同元素。3DM3DM可作可作如下形象的解释：记一单身男人集合为如下形象的解释：记一单身男人集合为X X，一单身女人集合为，一单身女人集合为Y Y，此外还有，此外还有一个住房集合一个住房集合Z Z。其间存在一

119、相容关系（例如有些人之间不愿组成家庭，。其间存在一相容关系（例如有些人之间不愿组成家庭，或不愿住某一住房），这样就给出了一个集合或不愿住某一住房），这样就给出了一个集合，M M是由问题给出的，表示了所有可能组合。所求的匹配即组成的一组家是由问题给出的，表示了所有可能组合。所求的匹配即组成的一组家庭（包括住房），其中不能有重婚，也不能让不同的两个家庭住进同一住庭（包括住房），其中不能有重婚，也不能让不同的两个家庭住进同一住房。房。71上一页上一页下一页下一页（3 3）（划分问题）（划分问题） 给定一正整集合给定一正整集合A A=a a1 1, , a a2 2, , , , a an n ，问是

120、否存在，问是否存在A A的一个子集的一个子集AA, ,使得使得 ，即是否可将，即是否可将A A中的数分成总和相等中的数分成总和相等的两部分。的两部分。（4 4）（顶点复盖问题）（顶点复盖问题VCVC）给定一个图）给定一个图G G= =（V V，E E）及一个正整数）及一个正整数K K| | V V | |，问，问G G中是否有不超过中是否有不超过K K个顶点的复盖。（一个顶点的子集称为个顶点的复盖。（一个顶点的子集称为G G的一个复盖，若它至少包含的一个复盖，若它至少包含G G中任一边的两个端点之一）。中任一边的两个端点之一）。（5 5）（哈密顿圈问题）（哈密顿圈问题HCHC） 见例见例8.9

121、8.9。 （6 6）（团问题）（团问题） 给定图给定图G G= =（V V，E E）及一正整数）及一正整数K K| | V V | |，问是否存，问是否存在图在图G G中的一个团中的一个团VV，| | VV| | K K。（。（G G的一个顶点的子集的一个顶点的子集VV称为称为G G的的一个团，若一个团，若VV中任意两点间都有中任意两点间都有E E中的边相连）。中的边相连）。 图图8.58.5表达了上述六个问题及表达了上述六个问题及SATSAT问题之间的多项式转化关系，即问题之间的多项式转化关系，即SATSAT3SAT3SAT，3SAT3SAT3DM3DM及及3SAT3SATVCVC等等。等等

122、。72上一页上一页下一页下一页最后还要说明一点，问题之间有时还会存在包含关系。一问题可能是最后还要说明一点，问题之间有时还会存在包含关系。一问题可能是另一问题的子问题，它也可能是另一问题的推广。问题越一般，其求另一问题的子问题，它也可能是另一问题的推广。问题越一般，其求解常常就越困难。例如，有向图上的解常常就越困难。例如，有向图上的HCHC是无向图上的是无向图上的HCHC问题的推广。问题的推广。由于无向图由于无向图HCHC问题是问题是NPNP完全的，则有向图上的完全的，则有向图上的HCHC必然也是必然也是NPNP完全的。完全的。另外，在例另外，在例8.98.9的讨论中，我们事实上已证明的讨论中

123、，我们事实上已证明 HCHC问题的每一实例均可问题的每一实例均可转化为一个对称的转化为一个对称的TSPTSP的实例（的实例（C Cijij = = C Cjiji），因而对称），因而对称TSPTSP是是NPNP完全的。完全的。不难看出，所得的不难看出，所得的TSPTSP实例还是满足三角不等式的（即实例还是满足三角不等式的（即i i, , j j, , k k，必有，必有C Cijij + + C CjkjkC Cikik），因而，满足三角不等式的），因而，满足三角不等式的TSPTSP也是也是NPNP完全的，这样，完全的，这样，作为它们的推广，一般的作为它们的推广，一般的TSPTSP必然也是必然

124、也是NPNP完全的。反之，若一个问题是完全的。反之，若一个问题是NPNP完全的，则其子问题未必一定是完全的，则其子问题未必一定是NPNP完全的，它完全可能是一个完全的，它完全可能是一个P P问题问题（当然，也可能是（当然，也可能是NPNP完全的）。例如，有人（完全的）。例如，有人（KuratowskiKuratowski）已经证明）已经证明平面图上的团最多只能包含平面图上的团最多只能包含4 4个顶点，这一结果说明，平面团问题是个顶点，这一结果说明，平面团问题是P P问题，尽管团问题是问题，尽管团问题是NPNP完全的。同样，完全的。同样，HCHC问题是问题是NPNP完全的，但没有人完全的，但没有

125、人会去研究完全图上的会去研究完全图上的HCHC问题，因为完全图中必存在着哈密顿圈。问题，因为完全图中必存在着哈密顿圈。73上一页上一页下一页下一页习题1 1、某饲养场用、某饲养场用n n种原料配合成饲料喂鸡，为了让鸡生长得快，对种原料配合成饲料喂鸡，为了让鸡生长得快，对m m种营养种营养成分有一个最低标准。即对成分有一个最低标准。即对i i=1,=1, ,m m，要求第，要求第i i种营养成分在饲料中的含种营养成分在饲料中的含量不得少于量不得少于b bi i，若每单位第，若每单位第j j种原料中含第种原料中含第i i种营养成分的量为种营养成分的量为a aijij，第，第j j种种原料的单价为原

126、料的单价为C Cj j，问应如何配制饲料才能使成本最低？，问应如何配制饲料才能使成本最低？2 2、用单纯形法求解：、用单纯形法求解： S.tS.t x x1 1 + 3 + 3x x2 2 + + x x4 4 4 42 2x x1 1 + + x x2 2 3 3x x2 2 + 4 + 4x x3 3 + + x x4 4 3 3x xi i0, 0, i i=1,=1,4,43、用两段、用两段单纯形法求解下列形法求解下列线性性规划：划：（1）min 4x1 + 6x2 （2）min 4x1 + x2 + x3 S.t x1 + 2x2 30 S.t 2x1 + x2 + 2x3 = 4

127、2x1 + x2 10 3x1 + 3x2 + x3 = 3 x1，x2 0 x1，x2，x3 074上一页上一页下一页下一页4 4、解表、解表8.148.14给出的运输问题，表中左上角的数为单位运价给出的运输问题，表中左上角的数为单位运价CijCij。表表8.148.14 销地地产地地B1B2B3B4产量量A1289710A212325A375568销售售28465 5、拟分配甲、乙、丙、丁四人去干四项工作，每人干且仅干一项。他们、拟分配甲、乙、丙、丁四人去干四项工作，每人干且仅干一项。他们干各项工作需用天数见表干各项工作需用天数见表8.158.15，问应如何分配才能使总用工天数最少。，问应

128、如何分配才能使总用工天数最少。表表8.158.15 工作工作工人工人1234甲甲10978乙乙5877丙丙5465丁丁234575上一页上一页下一页下一页6 6、某校经预赛选出、某校经预赛选出A A、B B、C C、D D四名学生，将派他们去参加该地区各学四名学生，将派他们去参加该地区各学校之间的竞赛。此次竞赛的四门功课考试在同一时间进行，因而每人只校之间的竞赛。此次竞赛的四门功课考试在同一时间进行，因而每人只能参加一门，比赛结果将以团体总分计名次（不计个人名次）。设表能参加一门，比赛结果将以团体总分计名次（不计个人名次）。设表8.168.16是四名学生选拔时的成绩，问应如何组队较好？是四名学

129、生选拔时的成绩，问应如何组队较好？表表8.168.16 课程课程 学生学生数学数学物理物理化学化学外语外语A A9090959578788383B B8585898973738080C C9393919188887979D D797985858484878776上一页上一页下一页下一页7 7、有甲、乙、丙、丁、戊、己六名运动员报名参加、有甲、乙、丙、丁、戊、己六名运动员报名参加A A、B B、C C、D D、E E、F F六六个项目的比赛。表个项目的比赛。表8.178.17为运动员的报名情况表，打为运动员的报名情况表，打表示运动员报名参表示运动员报名参加该项目比赛。要求设计一个算法来求一比赛项

130、目的顺序安排，使得每加该项目比赛。要求设计一个算法来求一比赛项目的顺序安排，使得每一运动员都不会参加两项连续进行的比赛。一运动员都不会参加两项连续进行的比赛。表表8.178.17ABCDEF甲甲乙乙丙丙丁丁戊戊己己77上一页上一页下一页下一页8 8、习题、习题7 7的一般问题：已有的一般问题：已有m m人报名参加一次共有人报名参加一次共有n n个项目的运动会，报名个项目的运动会，报名情况已知。要定出一个比赛项目的顺序表，使每一运动员都不会参加两项情况已知。要定出一个比赛项目的顺序表，使每一运动员都不会参加两项连续举行的项目。问是否有这样的顺序？连续举行的项目。问是否有这样的顺序？（1 1）根据

131、问题在多项式时间内作出一个图，该图共有）根据问题在多项式时间内作出一个图，该图共有n n个顶点，每一顶点个顶点，每一顶点代表一个项目。两个顶点间有边相连当且仅当任一运动员都未同时报名参代表一个项目。两个顶点间有边相连当且仅当任一运动员都未同时报名参加这两项比赛。加这两项比赛。（2 2）证明问题等价于哈密顿圈问题（）证明问题等价于哈密顿圈问题（HCHC）。由此可见，对于一个规模稍）。由此可见，对于一个规模稍大些的运动会，连想知道是否有这样的顺序一般也是不可能的。大些的运动会，连想知道是否有这样的顺序一般也是不可能的。 78上一页上一页下一页下一页1010、一个图被称为平面图，如果它能被画在平面上

132、而使其所有的边互不相、一个图被称为平面图，如果它能被画在平面上而使其所有的边互不相交。重画图交。重画图8.68.6中的（中的（a a）和（）和（b b），证明它们是平面图。），证明它们是平面图。 9 9、（、（1 1）判断图）判断图 8.68.6中的（中的（a a）、（）、（b b）是否为哈密顿图，即判断图中是否）是否为哈密顿图，即判断图中是否存在哈密顿圈。存在哈密顿圈。（2 2）如果一个图有哈密顿圈，你能想出哪些方式表达它。）如果一个图有哈密顿圈，你能想出哪些方式表达它。（3 3）完全图一定有哈密顿圈，试计算）完全图一定有哈密顿圈，试计算n n个顶点的完全图中共有多少个哈密个顶点的完全图中共

133、有多少个哈密顿圈顿圈 。79上一页上一页下一页下一页1111、KuratowskiKuratowski证明，平面图中的团最多只能包含证明，平面图中的团最多只能包含4 4个顶点。请据此构造个顶点。请据此构造一个求平面图最大团的有效算法。（你的算法也许要一个求平面图最大团的有效算法。（你的算法也许要O O（| | V V |4 |4）计算量，）计算量，但目前最好的算法只需要但目前最好的算法只需要O O（| | V V | |），当然算法是精心设计而比较精细），当然算法是精心设计而比较精细的。）的。）1212、要调配红、蓝、白、黑、黄五种颜色的油漆。清洗工具花费的时间、要调配红、蓝、白、黑、黄五种颜

134、色的油漆。清洗工具花费的时间既和原色彩有关又和拟调什么颜色有关，所化时间（分）见表既和原色彩有关又和拟调什么颜色有关，所化时间（分）见表8.188.18。易。易见这是一个见这是一个TSPTSP。 表表8.188.18 现调现调原色原色红红蓝蓝白白黑黑黄黄红红/ /6 618184 48 8蓝蓝7 7/ /17173 37 7白白4 45 5/ /4 45 5黑黑202019192424/ /2222黄黄8 88 816166 6/ /（1 1）用充分大的正数）用充分大的正数M M代替表中的斜线（注：不必具体写出代替表中的斜线（注：不必具体写出M M），得一矩），得一矩阵阵C C。解。解C C对

135、应的指派问题，你会发现你已解出了这一对应的指派问题，你会发现你已解出了这一TSPTSP。（2 2）比较指派问题与）比较指派问题与TSPTSP两个问题，说出你的所有想法（两问题的区别两个问题，说出你的所有想法（两问题的区别与联系）。与联系）。80上一页上一页下一页下一页1414、证明由、证明由1 1城市出发遍访所有城市（不得重复）城市出发遍访所有城市（不得重复）但最终不必返回原来城市的旅行商问题（称为流但最终不必返回原来城市的旅行商问题（称为流浪的旅行商问题浪的旅行商问题WTSPWTSP）与旅行商问题等价。）与旅行商问题等价。1515、对给定的、对给定的TSPTSP实例，用多项式时间构造一个实例

136、，用多项式时间构造一个不允许等待的加工排序问题的实例。不允许等待的加工排序问题的实例。 1313、某人受单纯形方法启发，拟按如下步骤逐次改进而求出、某人受单纯形方法启发，拟按如下步骤逐次改进而求出TSPTSP的解。的解。（1 1）任取一个初始旅行圈，记为）任取一个初始旅行圈，记为= =（i i1 1, , i i2 2, , , , i in n）。对于一个完全）。对于一个完全图，这是容易办到的，例如（图，这是容易办到的，例如（1, 2, 1, 2, , , n n）就是一个。）就是一个。（2 2）找出）找出中的三条边中的三条边i it ti it t+1+1, , i ik k-1-1i ik k、i ik ki ik k+1+1，满足：，满足：用边用边i it ti ik k、i ik ki it t+1+1、i ik k-1-1i ik k+1+1代替代替中找出的三边，得到一个改进的圈中找出的三边，得到一个改进的圈，见图，见图8.78.7所示。以所示。以代替代替。重复（。重复（2 2）中的做法，直至无法再改进。）中的做法，直至无法再改进。你认为是否应鼓励此人作这样的尝试，为什么？你认为是否应鼓励此人作这样的尝试，为什么？81上一页上一页下一页下一页 下接第六章82