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

1,线性规划与计算复杂性简介,浙江大学数学建模实践基地,2,3,8.1线性规划问题,在人们的生产实践中，经常会遇到如何利用现有资源来安排生产以取得最大经济效益的问题，此类问题构成了运筹学的一个重要分支数学规划，而线性规划（LinearProgramming,简记LP）则是数学规划的一个重要部分。自从1947年GBDantzig提出求解线性规划的单纯形方法以来，线性规划在理论上日趋成熟，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。,4,一.线性规划的实例与定义,例8.1某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各多少台，才能使总利润最大？,5,例1的数学模型：设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1、x2应满足,max4x1+3x2s.t2x1+x210 x1+x28(8.1)x27x1,x20,（8.1）式中4x1+3x2表示生产x1台甲机床和x2台乙机床的总利润，被称为问题的目标函数，当希望使目标函数最大时，记为max；反之，当希望使目标函数最小时，记为min。（8.1）中的几个不等式是问题的约束条件，记为S.t（即Subjectto）。由于（8.1）式中的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限止下，求一线性目标函数最大或最小的问题。,6,二、线性规划的标准形式,例8.2minS.ti=1,mxj0,j=1,n,线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有非负要求（称这样的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为,利用矩阵与向量记为minz=CTxS.tAx=bx0（8.3）其中C和x为n维列向量，b为m维列向量，b0，A为mn矩阵,mm）b为m维列向量，记R为（8.3）的可行域。则x为R的极点的充分必要条件为x是的基本可行解。定理8.1既提供了求可行域R的极点的代数方法，又指明了线性规划可行域R的极点至多只有有限个.,对定理证明有兴趣的读者可以参阅D.G.鲁恩伯杰著的“线性与非线性规划引论”一书第二章,13,（线性规划基本定理）线性规划（8.3）具有以下性质：（1）若可行域R，则必存在一个基本可行解。（2）若问题存在一个最优解，则必存在一个最优的基本可行解。定理8.2并非说最优解只能在基本可行解（极点）上达到，而是说只要（8.3）有有限最优解，就必定可在基本可行解（极点）中找到。,定理8.2,从模型本身讲，线性规划显然应属连续模型。但定理2表明，如果线性规划有有限最优解，我们只需比较各基本可行解上的目标函数值即可找到一个最优解，而问题的基本可行解至多只有有限个，从而问题化为一个从有限多个点选取一个最优点的问题。正是基于这样一种思路，Dantzig提出了求解线性规划的单纯形法。也正因为如此，我们把线性规划列入了离散模型，因为求解它的单纯形法更具有离散模型问题的算法特征。,14,五、求解线性规划的单纯形法,（步1）取一初始可行基B（一般取法见后面的两段单纯形法），再用高斯约当消去法求出初始基本可行解x0，编制成所谓的初始单纯形表；（步2）判断x0是否最优解，如果x0是最优解，输出x0，停，否则到步3；（步3）按一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量。这相当于交换B与N的一个列，同样可用高斯约当消去法，运算可以通过单纯形表上的“转轴运算”实现。,Dantzig单纯形法的基本步骤如下：,15,定理8.3（最优性判别定理）令。（1）若rN0，则x0必为（8.3）的一个最优解。（2）记。若，rj0，根据（7.15）式知，当且充分小时，仍有xB0。此时对应的x仍为可行解，但由（8.6），其目标函数值：故x0必非最优解。,定理8.3不仅给出了判别一个基本可行解是否为最优解的准则，而且在x0非最优解时还指出了一条改进它的途径。由于rN在判别现行基本可行解是否为最优解时起了重要作用，所以rN被称为x0处的检验向量，而rj(jN)被称为非基变量xj的检验数。,17,利用单位矩阵I消第一行的为零向量，则被消成，而0则被消成。将消去后的行向量写到最后一行，删去原来的第一行，得到一张被称为单纯表的表格：,(8.7),表格（8.7）以极为简洁明了的方式表达了我们需要的全部信息。从其前m行可看出哪些变量是基变量并可直接读出对应的基本可行解x0=（B1b，0）。其最后一行又给出了非基变量的检验数及x0处目标函数值的相反数。,18,例8.1的标准形式为（8.4），容易看出它的一个初始基B=I（以x3、x4、x5为基变量），且CB已经为零，故我们已有了一张初始的单纯形表表8.1：,表8.1,x0=(0,0,10,8,7)Tz0=CTx0=0rN=(r1,r2)=(4，3),现在，我们以例8.1为例，来看一下单纯形法是如何工作的。,19,由于存在着负的检验数且x0非退化，x0非最优解。r1，r2均为负，x1，x2增大（进基）均能改进目标函数值。,例如，取x1进基仍令x2=0（x2仍为非基变量），此时由（8.5）式及（8.6）式有且z=CTx=4x1x1增加得越多，目标函数值下降得越多，但当x1=5时x3=0，x1再增大则x3将变负。为保证可行性，x1最多只能增加到5，此时x3成为非基变量（退基）。,不难看出，上述改进可以在单纯形表上进行。对于一般形式的单纯形表，记最后一列的前m个分量为（yi0），i=1,m。若取进基，记j0列前m个分量为（），i=1,m。易见，阻碍增大的只可能在0的那些约束中。若0对一切i=1,m成立（j0列前m个分量中不存在正值），则可任意增大，得到的均为可行解，但其目标值随之可任意减小，故问题无有限最优解。,20,否则，令则随着的增大，将最先降为零（退出基变量），故只需以为主元作一次消去法运算（称此运算为一次转轴运算），即可得到改进后的基本可行解处的单纯形表。在本例中，因取x1进基（j=1）而，以y11为主元作第一次转轴，得到,x1=(5,0,0,3,7)Tz1=20rN=(r2,r3)=(1，2),21,表8.2中r20）最小选定以下y22=为主元转轴，得到下一基本可行解x2处的单纯形表表8.3。,表8.3,x2=(2,6,0,0,1)Tz2=26rN=(r3,r4)=(1，2)对于x2，rN=(1，2)为非负向量，故x2为最优解，最优目标值为26。于是，原问题例1的最优解x*=(2,6)T，最优目标值为26。,22,六、初始可行解的求法两段单纯形法,阶段2若辅助规划的最优目标值不等于零，原规划无可行解。否则我们已求得原问题的一个基本可行解x0。删去阶段1最终单纯表中最后一行及对应人工变量的列，作出原规划对应x0的初始单纯形表。此时又可利用上述单纯形法求解原规划了。,阶段1对第i个约束引入人工变量yi，yi0，将其改写为ai1x1+ainxn+yi=bi，i=1,m。作辅助线性规划LP（1），其目标函数为。容易看出，原规划有可行解（从而有基本可行解）的充分必要条件为辅助规划的最优目标值为零。由于辅助规划具有明显的初始可行基（人工变量对应的列构成单位矩阵I），可利用上述单纯形法逐次改进而求出辅助规划最优解。,23,例8.2min4x1+x2+x3S.t2x1+x2+2x3=43x1+3x2+x3=3x1、x2、x30,?,解：因为初始可行基不能直接看出，我们采用两段单纯形法求解。阶段1先求解辅助规划：minx4+x5S.t2x1+x2+2x3+x4=43x1+3x2+x3+x5=3x1，x30,24,表8.4,选取x1进基，以y21=3为主元转轴（x5出基），得表8.5。表8.5,25,因r30。当B1b也存在零分量时，我们遇到了一个退化的基本可行解。此时rN存在负分量不一定说明现行基本可行解不是最优解，单纯形法也可能会遇到循环迭代。存在着几种避免循环的技巧，例如，只要每次在rj0的非基变量中选取具有最小足标者进基即可。,在求解线性规划时，首先应将问题化为标准形式。若从标准形式已可看出一个初始基，则可直接用单纯法求解：（1）写出初始单纯形表；（2）若检验向量rN0，则已得以最优解；（3）任选一负分量rj。以进基，考察所在列。若对i=1,m均有0，则问题无有限最优解，停；否则令，以为主元转轴，返回（2），直至rN0求出最优解。若从标准形式无法看出初始可行基，则需采用两段单纯形法求解。,变量同时具有上、下界限止的线性规划问题也可化为标准形式求解，有兴趣的读者可以参阅D.G.鲁恩伯杰的“线性与非线性规划引论”一书的第三章。,28,8.2运输问题,一.运输问题的数学模型,例8.3某商品有m个产地、n个销地，各产地的产量分别为a1,am各销地的需求量分别为b1,bn。若该商品由i产地运到j销地的单位运价为Cij，问应该如何调运才能使总运费最省?,解：引入变量xij，其取值为由i产地运往j销地的该商品数量。例8.3的数学模型为minS.t，i=1,m(8.9)，j=1,nxij0,（8.9）显然是一个线性规划问题，当然可以用单纯形方法求解，但由于其约束条件的系数矩阵相当特殊，求解它可以采用其他简便办法。本节将介绍由康脱洛维奇和希奇柯克两人独立地提出的表上作业法（简称康希表上作业法），其实质仍然是先作出一个初始基本可行解，然后用最优性准则检验是否为最优并逐次改进直至最优性准则成立。,29,二、初始可行解的选取,不难发现，（8.9）的约束条件中存在着多余方程。容易证明，只要从中除去一个约束，例如最后一个方程，约束条件就彼此独立了。因而，（8.9）是一个具有mn个变量的线性规划，其每一基本可行解应含有m+n1个基变量。,记（8.9）约束条件中前m+n1个方程的系数矩阵为A，A为（m+n1）mn矩阵，它的每一列最多只有两个非零元素且非零元素均为1。利用线性代数知识能够判定A中怎样的m+n1个列可以取为基（即怎样的m+n1个变量可以取为基变量），为了判明哪些变量对应的列是线性无关的，先引入下面的定义：,30,定义8.3（闭回路）xij（i=1,m;j=1,n）的一个子集被称为一个闭回路，若它可以被排成其中互异，也互异。,用下面的方法可以较方便直观地看出xij的一个子集是否为一闭回路：作一个m行n列的表格，令格（i,j）对应xij。将子集中的变量填于相应格中，并将相邻变量（或同行或同列）用边相连，则此子集为闭回路当且仅当其点按上述连法作出的折线可构成一个闭回路。,例如，当m=3,n=4时，X1=x12,x13,x23,x24,x34,x32和X2=x12,x14,x24,x21,x31,x32均为闭回路，见表8.9和表8.10。,31,定理8.4X为xij（i=1,，m；j=1，n）的一个子集，X中的变量对应的A中的列向量集线性无关的充要条件为X中不包含闭回路。,定量8.4不难用线性代数知识证明，详细证明从略。根据定理8.4，要选取（8.9）的一组基变量并进而得到一个基本可行解，只需选取xij的一个子集X，X=m+n-1且X中不含闭回路，其中X表示X中的变量个数。,我们从下面的例子来说明如何选取一个基本可行解。,例8.3给定运输问题如表8.11所示，表中左上角的数字为单位运价Cij。易见，本例是产销平衡的即。,表8.11,32,现采用“最小元素法”求一基本可行解。单位运价最小的为C33=1，令x33=mina3,b3=4,并令x13=x23=0（销地3已满足），相应格打“”。产地3已运出4单位，将产量改为剩余产量3。剩余表中单位运价最小的为C11=2（或C34=2），令x11=mina1,b1=2,并令x21=x31=0，相应格打“”，a1改为剩余产量1，直至全部产品分配完毕。注意到除最后一次分配外每次只能对一行或一列找“”，表示某销地已满足或某产地产品已分配完（当两者同时成立时只能打“”行或列之一，将剩余需求量或产量记为0，此时基本可行基是退化的）。容易证明：这样分配共选出了m+n-1个变量，且这些变量的集合不含闭回路，从而构成一个基本可行解。当每一基变量xij选取时i产地的剩余商品量与j销地的剩余需求量总不相等，选出的基本可行解是非退化的。,初始基本可行解也可按其他方式选取，如“左上角法”等，其方法与原理是类似的，左上角法每次选取剩余表格中位于最左上角的变量，其余均相同。,33,三、最优性判别,类似单纯形法，可计算非基变量的检验数，存在多种求检验数的方法（求得的结果是相同的），下面介绍计算简便且计算量也较小的“位势法”。引入m+n个量（被称为位势）u1，um；u1，un。对每一变量xij，引入rij,令xij=ij-ui-vj(事实上，这一公式与单纯形法求检验数的公式是相同的)。对基变量xij，令rij=0，得到Cijuivj=0(xij为基变量)（8.10),齐次线性方程组（8.10）共有m+n个独立方程，但含有m+n个变量。任取一变量，例如u1作为自由变量，便可解出方程组。容易看出，u1的取值不同虽会改变位势的取值但不会改变非基变量的检验数。为方便起见，只要令u1即可。事实上，我们甚至不必去解方程组（8.10），而只需令u1，对所有基变量令uivjcij，即=ij-ui-vj，在表上逐次求出所有位势，进而再对非基变量xij计算其检验数rij=ij-ui-vj,34,例如，对表8.11中取定的基，我们求出位势及非基变量的检验数，列于表8.12中，表中不带圈的数为基变量取值，带圈的数为非基变量检验数，右上角的数为单位运价ij。,利用线性代数知识可以证明下列各定理(证明从略)：定理8.5任取一非基变量，将其加入基变量集合中，则在所得变量集合中存在唯一的闭回路。易见闭回路中含有偶数个变量，若令进基，令=，为保持平衡条件，位于偶数位置的变量必须减少，而位于奇数位置的变量则必须增加（注：）。,表8.12,35,定理8.6设是非基变量与基变量集合的并集中唯一的闭回路，若令=并在闭回路上调整基变量取值使之平衡，得一可行解x，则x处的目标值与原基本可行解上的目标值之差为。,根据定理8.6，若存在检验数的非基变量，取进基（取正值）并令（8.12）则原取值为的位于偶数位置的基变量退基，得到一新的基本可行解，其目标值减少。,定理8.7设为（8.9）的一个基本可行解，若x0所有非基变量的检验数均非负，则x0必为（8.9）的一个最优解。当x0非退化时，此条件还是必要的。,证明由定理8.6知，当x0所有非基变量的检验数均非负时，任一非基变量进基均不会使目标值减小，由于（8.9）是一线性规划，此性质表明x0已为最优基本可行解。反之，则只要令具有负检验数的非基变量进基即可。,36,综上所述，康希表上作业法可如下操作：,（步1）按最小元素法（或右上角法等）求一初始基本可行解。,（步2）按（8.10）求出位势ui,j（i=1,m;j=1,n）。进而按（8.11）求出非变量的检验数rij。若一切rij0，则已求得一最优解。,（步3）任取一0，找出进基后形成的唯一闭回路。在找出的闭回路上调整，按（8.12）取，得出新的基本可行解，返回步2。直至找到最优解。,37,对于例8.3，表8.12已给出非基变量的检验数。因r230，令x23进基，得闭回路x23,x24,x34,x33取=minx24,x33=2，调整后得一新的基本可行解。求出新的基本可行解、对应的位势及非基变量检验数，列成表8.13。,表8.13,现在，非基变量检验数均已非负，故已求得最优解：x11=2，x14=1，x22=3，x23=2，x33=2，x34=5，其余=0（非基变量）。若运输问题是产销不平衡的，则应先将其转化为产销平衡的，然后再求解。例如，若产大于销，可虚设一销地（剩余产量存贮），将单位运价取为零即可。,38,一、指派问题的数学模型,8.3指派问题,例8.4拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需化费Cij单位时间，问应如何分配工作才能使工人化费的总时间最少？,容易看出，要给出一个指派问题的实例，只需给出矩阵C=（Cij）,C被称为指派问题的系数矩阵。引入变量xij，若分配i干j工作，则取xij=1，否则则取xij=0。上述指派问题的数学模型为S.t（8.13）xij=0或1,39,（8.13）的可行解既可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,n中的一个置换表示。,（8.13）的变量只能取0或1，从而是一个01规划问题。下一章将指出，一般的01规划问题的求解极为困难。但指派问题（8.13）并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵或全幺模矩阵，其各阶非零子式均为1），其非负可行解的分量只能取0或1，故约束“xij=0或1”可改写为xij0而不改变其解。此时，（8.13）被转化为一个特殊的运输问题，其中m=n,ai=bi=1。,40,二、求解指派问题的匈牙利算法,由于指派问题的特殊性，又存在着由匈牙利数学家Konig提出的更为简便的解法匈牙利算法。算法主要依据以下事实：如果将系数矩阵C=（Cij）中一行（或一列）的每一元素都加上或减去同一个数，得到一个新矩阵B=（bij），则以C和B为系数矩阵的指派问题具有相同的最优指派。,例8.5求解指派问题，其系数矩阵为,41,解将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得,再将第3列元素各减去1，得,以B2为系数矩阵的指派问题有最优指派由等价性，它也是例2的最优指派。有时问题会稍复杂一些，见下面的例8.6,42,例8.6求解下面的系数矩阵为C的指派问题,解：先作等价变换如下,容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，最优指派还无法看出。此时等价变换还可进行下去。,43,步骤如下：,（1）对未选出0元素的行打；（2）对行中0元素所在列打；（3）对列中选中的0元素所在行打；重复（2）、（3）直到无法再打为止。,可以证明，若用直线划没有打的行与打的列，就得到了能够复盖住矩阵中所有零元素的最少条数的直线集合。找出未复盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未复盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选出足够的0元素为至。例如，对例8.6变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得,现在已可看出，最优指派为,（注：相应定理从略）,44,8.4计算复杂性问题的提出,离散模型的实质是从有限多个候选值中选取一个最佳取值。例如8.1中的线性规划，虽然可行解一般有无穷多个，但线性规划基本定理指出，只要存在有限最优解，就必可在基本可行解中找到，而基本可行解总共只有有限多个。Dantzig的单纯形法正是利用了这一性质，在基本可行解中选取最优解。,在有限多个候选者中选择其中之一，通常不存在连续模型中备受关注的解的存在性问题，因为有限个值中选取最佳取值，解的存在性不成问题。解的唯一性问题也不再被人们重视。例如，在用单纯形法求得一最优基本可行解后，我们认为问题已被解出，它是否还有其他的最优解，我们一般不再感兴趣。,45,也许有人会想，从有限种可能方案中挑选一种，这总是比较容易的。如果一一比较下去，最后总可以得出满意的结果。然而，事实并非如此简单，关键在于问题的规模和求解时的计算量。随着电子计算机的出现，人们对问题可解性的认识在观念上发生了根本改变。一个在理论上可解的问题如果在实际求解时需要化费不合理的时间（如几百年、几千年甚至更长时间），我们不能心安理得地认为它已被解决，而应当去寻找更好、更实用的算法。,从本章开始，我们将区分问题与问题的实例。由于篇幅的限止，我们不准备给出严格的定义。问题是一类实际问题的数学模型的总称，如线性规划问题、运输问题、指派问题等等。在一个问题中一般总包含着若干个参数，给定这些参数，就给出了这一问题的一个实例。容易想到，单纯形法解一个有几百个变量的线性规划实例一般总比解一个只有几十个变量的线性规划实例化费更多的时间。因而，在估算一个算法的计算量时显然应当同时考虑到实例的规模。严格地讲，一个实例的规模应当用其输入数的二进制长度的总和来表示。但粗略地讲，变量的多少常常也能在一定程度上反映出实例规模的大小。在本书中，如无特别说明，我们将以变量个数来表示实例的规模，虽然这样做是不够严格的，但比较方便。,46,比较算法的好坏，从不同的角度出发，有各种不同的标准。在这里，我们仅就算法的计算速度作一个十分粗略的比较。,例8.7（整理问题）给定n个实数a1,a2,an，要求将它整理成由小到大排列（或由大到小排列）的顺序：b1,b2,bn，b1b2bn。,（算法1）取出a1,a2,an中的最小者，令其为b1。从a1,a2,an中去除b1，在余下的n1个数中选出最小者，令其为b2，直至得到b1,b2,bn。容易看出，为了排出b1,b2,bn，算法工作了次比较。,（算法2）步0b1a1步1设已有b1,bk(1kn)，将按两分法比较的方式把ak+1排入其中：若b1biak+1bi+1bk，令（b1,b2,bk,bk+1）（b1,bi,ak+1,bi+1,bk）。若k+1b4，可再和b6比（若a8b4则和b2比），易见，只要比3次即可排入a8，由于rlog2k+1，算法的总经较次数不超过,令，设计算机每秒可作C次比较，则算法1与算法2整理a1,a2,an所用的时间分别为若n=100万，C=100万次/秒，则t15.8天，而t220秒。可见在较大规模的整理问题时，算法2明显优于算法1。,48,现设一台每小时能作M次运算的计算机，并设求解某一问题已有了两个不同的算法。算法A对规模为n的实例约需作n2次运算而算法B则约需作2n次运算。于是，运用算法A在一小时内可解一个规模为的实例，而算法B则只能解一个规模为log2M的实例。两者的差别究竟有多大呢？让我们来对比一下。假如计算机每秒可作100万次运算，则算法A一小时大约可解一个规模为n=60000的实例，而算法B在一小时内只能解一个规模的实例且n每增加1，算法B求解时所化的时间就将增加1倍。例如算法B求解一个n=50的实例将连续运算357年多。,现设计算速度提高了100倍，这对计算机来讲已是一个相当大的改进。此时算法A可解问题的规模增大了10倍，而算法B可解问题的规模只增加了log21000，对任意正整数N，总可找到一个大于N的正整数n及D的一个规模为n的实例，对这一实例有fB(D,n)=O(2kn)，则称B为求解问题D的一个指数算法。,多项式算法被称为是“好”的算法即所谓有效算法，而指数算法则一般被认为是“坏”算法，因为它只能求解规模极小的实例。,50,下面的表8-14列出了在规模大约为n时各类算法的计算量，而表8-15则反映了当计算机速度提高10倍、100倍时，各类算法在1小时内可求解的问题的模型的增长情况，（前三个是多项式时间的，后两个是指数时间的）,表8-14几个多项式和指数时间复杂性函数增长情况,51,表8-151小时内可解的问题实例的规模,由定义8.4知4n2与2n2都是O(n2)，nlogn+3n是O(nlogn)，我们在以后分析时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效率的关键因素。,52,一、P类与NP类，NP完全性,这样看来，对一个问题，只有在找到求解它的多项式算法后我们才能较为放心。假如我们遇到了一个规模很大的实例今天无法求解它，但我们仍可寄希望于将来。通过计算机的改进，在将来求解它仍然是可能的。而对指数算法，你就不会有这种信心。,然而，十分可惜的是，对于许许多多具有十分广泛应用价值的离散问题，人们至今尚未找到求解它们的有效算法。,53,定义8.6（P问题与P类）存在多项式算法的问题被称为P问题，所有P问题构成的问题类被称为P类，简记为P。,根据定义，整理问题是一个P问题，存在求解它的O（nlog2n）算法。在下一章中，我们还将讨论一些P问题并介绍求解它们的有效算法。我们将会发现，P问题从某种意义上讲是性质较好从而较易求解的问题。,由于线性规划在现实生活中有着极其广泛的应用，人们自然会问：单纯形法是不是有效算法？线性规划是不是P问题？,1972年，Klee和Minty以下面的著名例子证明单纯形法是指数算法而不是多项式算法。例8.8maxxnS.tx11xj1xj1xj1，（j=2,n）其中是一个充分小的正数。,54,图8.2给出了n=3时的可行域，它是三维空间中单位立方体的一个微小摄动。在确定的进基原则下（如检验数最负者进基），若以x0=（,2,3）为初始基本可行解，在单纯形法迭代改进时，将经过每一基本可行解，最终到达最优解x*=（,2,13），其路径已用箭线画在图上，故迭代中共经过23个极点。对于规模为n的一般问题的实例，迭代步数为2n，故单纯形法为指数算法。,55,单纯形法自1947年被提出以来经历了无数次的考验，被证明是一种实用效果极佳的算法。但Klee的例子又无可争辨地证明了它事实上是一个指数算法，这两者是否予盾呢？其实两者并不矛盾。指数算法的定义规定，只要存在着fB(D,n)=O(2kn)的例子，算法B就是指数算法，它并没有涉及到我们遇到这样的例子的机会究竟有多大。几十年来，人们在实际应用单纯形法时，一次也没有碰到过例8.8那样的情况，（Klee的例子是人为构造的），可以证明，遇到例8.8这样的例子的概率为0。于是，人们自然会从另一角度算法的平均执行情况的角度去评价一个算法，有兴趣的读者可以参阅相应的书籍与文献。,既然单纯形法是指数算法，那么是否存在求解线性规划问题的多项式算法呢？或者换句话讲，线性规划问题是P问题吗？,在长达七年的时间里这一引人注目的问题一直悬而未决，存在着两种完全对立的观点。直到1979年，前苏联的数学家L.G.Khachina提出求解线性规划问题的椭球算法，才证明线性规划是一个P问题。他的方法与以前的方法截然不同，甚至完全不用线性规划基本定理，以意想不到的方式解决了这个较长时间解决不了的难题，在当时引起了全球性的轰动。,对椭球算法有兴趣的读者可以参阅C.H.Papadimitriou等著的“组合最优化，算法和复杂性”一书第八章或姚恩瑜等编著的“数学规划与组合优化”一书第六章。,56,椭球算法虽然是多项式算法，但其实用效果却赶不上单纯形法，这一事实又吸引众多数学家去寻找实用效果也比单纯形法好的有效算法。1984年，美国贝尔实验室的数学家Karmarkar提出了以他名字命名的算法，其实用效果也相当不错。寻找实用效果更好的求解线性规划的有效算法，至今仍是一个十分活跃的研究课题。,对于众多至今尚未发现多项式算法的离散问题，是否也会在将来的某一天突然找到有效算法呢？至今对其中的大多数问题，数学家们目前抱有怀疑的态度，即认为P类之外存在着非P问题。由于计算机输入、输出及运算中使用的数均为有理数，我们可以假定问题的参数取值为有理数，甚至，等价地，可假定其取值均为整数。此外，问题也可等价地描述为判定问题，即解答时只需回答“是”或“否”的问题。,57,例8.9（哈密顿圈问题简记HC）给定一个图G=（V，E），其中V为顶点集合，E为图的边集。问G中是否存在着哈密顿圈。,所谓哈密顿圈是指由一个顶点出发，经过所有顶点一次而回到出发点的闭回路。哈密顿圈问题是一个判定问题，因为它只要求回答是或者否。,非判定问题可以转化为等价的判定问题，所谓等价是指是否存在多项式算法这一意义下的等价。为此，我们需要用到以下多项式时间转化的概念。,定义8.7（多项式转化）设D1、D2为两个判定问题，若存在求解两问题的算法A1和A2，其中求解D2的算法A2是多项式次地调用求解D1的算法A1而实现的，则称问题D2可以多项式转化为D1，简记为D2D1,容易看出，若D2可多项式转化为D1，又D1是P问题，则D2也是P问题，因为求解D2的有效算法可以通过多项式次地以求解D1的有效算法为子程度调用而作出，（从某种意义上讲，D1不比D2容易）。,58,例8.10（旅行商问题简记TSP）设有n个城市1,2,n，城i到城j的距离Cij已知（注：Cij与Cji可以不相等），某商人准备从城1出发，去其余各城推销商品，若所有城市均必需去且仅去一次，最后返回出发城市，问该商人应如何安排旅行，才能使所走的总路程最短。,TSP实际上是要求从一有向图G=（V，A）中寻找出一条具有最小总长度的HC，其中V=1,2,n，A=(i,j)|i,jV,ij，作有向图的原因是Cij与Cji可能不相等。如果Cij为由城i到城j的旅费，则TSP要求的是一个具有最小费用的HC。,与TSP等价的判定问题可如下叙述：给定一正整数K，问是否存在总长度不超过K的HC。TSP与其相应的判定问题是等价的，一方面，若存在求解相应判定问题的算法A，我们可以先找出G的HC总长度的一个上界（例如最大边长度的n倍），记为K。然后反复对K使用两分法并调用判定问题的算法A以判定是否存在总长不超过K的HC，调用的次数不超过输入数据总长度的一个多项式界。另一方面，若存在TSP的一个算法A，在求得G的具有最小总长度的HC后，其对应判定问题的答案自然立即可以得出。所以，TSP与其相应的判定问题（在是否为P问题这一点上）是等价的。,59,可以证明，HCTSP。事实上，若TSP存在一算法A，就可构造如下求解HC的算法：对G=（V，E）i、jV且ij，若（i,j）E令Cij=1，若（i,j）E，补充边（i,j）且令Cij=2，得到图G=（V，E）并求解G对应的TSP（利用算法A）。容易看出，G有HC（即回答是），当且仅当G的最小总长度HC之长度不超过n，故HC可多项式转化为TSP。从这一意义上讲，至此可以认为求解TSP不会比求解HC容易，因为如果TSP是P问题，HC一定也是P问题。虽然HC与TSP是等价的，但仅根据上面的证明，我们还不能得出相反的结论成立。,现在，我们来拓宽视线，把研究范围扩大以一个有可能比P类更大的集合。,定义8.8（NP类）设D是一个判定问题，若对D的每一个回答“是”的实例，它给出的回答均可经多项式界的运算加以检验，则称D为一个NP问题。由全体NP问题构成的问题类称为NP类，简记为NP。,定义8.8并非NP类的严格定义，其严格定义的给出常常要用到非确定型Turing机、非确定型算法等自动机理论方面的知识。,60,定理8.8PNP,证明：DP，存在着求解问题D的多项式算法。既然D的任一实例均可在一多项式界内解出，其相应的判定问题究意为“是”或“否”自然也均可在多项式界内给出回答。其回答为“是”的答案也必可在多项式界内检验，故DNP。由D的任意性，可知PNP。,至少在目前看来，NP是一个比P宽广得多的问题类。对于那些为数众多的、至今尚未发现多项式算法的问题，其中相当大一部分可以十分容易地证明是NP问题。例如，HC和TSP至今均未找到求解它们的有效算法，但容易证明，HCNP及TSPNP。因为验证一个圈是否是哈密顿圈及验证一哈密顿圈的总长是否不超过K是十分容易的，计算量不超过一个多项式界。,61,前面已经谈到，绝大多数数学家猜测PNP。如果这一猜测是正确的，那么哪些问题不在P中的可能性最大（即最不可能有多项式算法）。1972年，加拿大数学家S.A.Cook发表了一篇十分著名的论文。他指出，存在一类他称之为NP完全类的问题，这类问题有如下两个性质：（1）这类问题中的任何一个都不能用任何已知的多项式算法求解（尽管数学家们已作了几十年努力，至今仍毫无结果）；（2）若其中的任何一个问题有了多项式算法，则该类中的任何一个也就有了多项式算法。Cook在他的文章中证明，满足问题（简记SAT）是NP完全的，任一NP问题可多项式转化为SAT问题。故假如能找到求解SAT问题的多项式时间算法，则任一NP问题均能找到多项式算法。由于普遍认为PNP，故SAT问题被认为不可能存在多项式算法（否则将得出令人震惊的结果P=NP）。,为了说明什么是SAT问题，先引进下面的定义。,定义8.9（布尔变量与布尔表达式）一个只能取值“真”和“假”（或者“0”和“1”）的变量称为布尔变量。一个由布尔变量通过“或”、“与”、“非”逻辑运算符号连接而成的表达式称为布尔表达式。（注：可用“+”表示“或”，“”表示“与”，“”表示“x非”）,62,例8.10(1)(2),布尔表达式中每一括号内的子式被称为一个句子。当且仅当每一句子的取值为真时布尔表达式的值才为真。给定一个布尔表达式，若存在布尔变量的一组取值使此表达式的值为真，则称此布尔表达式是可满足的，否则称之为不可满足的。例8.10中的（1）是可满足的，而（2）是不可满足的。,（1）和（2）都是布尔表达式。对（1），若取x1=真，x2=真，x3=假，则表达式的值为真，对（2），不论布尔变量怎样取值，布尔表达式（2）的值均不可能为真。,63,例8.12（SAT问题）给定布尔变量x1,xn的一个布尔表达式c1c2cm，其中ci为用x1,xn构成的句子，问此表达式是可满足的吗？,SAT问题是数理逻辑中的中心问题之一，这一点可从计算机的运算方式看出，故设计一个较好的求解SAT问题的算法具有重要意义。,1972年，R.M.Karp以多项式转化的方式证明并列出21个NP完全问题。此后，大量NP完全问题一一被证明。短短十几年时间，已知的NP完全问题就达到了4000多个，其中包括前面提到过的HC和TSP。总之，NP完全类是一个极为庞大的问题类，其中包含着无穷多个问题。按照目前普遍的看法，这些问题中的任意一个都不应当有多项式算法，即求解它的任一算法在遇到最“坏”的实例时都需要化指数时间。,P类、NP完全类及NP类的关系如图8.3所示，即，NP完全类。还有很多离散问题目前尚未搞清它们的计算复杂性。有些将被证明是P问题，有些将被证明是NP完全的。此外，确实存在着NP以外的问题，其求解更为困难。,64,二、有关离散问题模型及其算法的几点附加说明,最近几十年来，有成千上万离散问题的模型得到了广泛而又较为深入的研究。因而，当我们研究一个离散型的问题时，首先要搞清遇到的实际课题是否为某一别人已研究过的问题的一个实例。搞清这一点十分重要，否则你的努力完全可能是一种徒劳。,例8.13某工厂在生产一种产品或部件时，需要在一些指桑骂槐定位置上钻孔。问应按怎样的顺序钻孔，才能使加工速度最快。,由于生产是连续进行的，钻头将从一钻孔位置出发到各指定点钻孔，最后返回原位置，以便加工下一个产品或部件。显然，这是一个旅行商问题。然而，是否为某一问题的实例有时并不是一目了然的。,65,例8.14在轧钢等生产中，为了保持工件的温度，工件在一台机器上加工以后必需立即转送下台机器加工，中间不允许出现工件等待现象。现设共有n个工件Ji(i=1,n)需要进行加工，且加工有以下特点：（i）加工不同工件时，使用机器的顺序可以不同。（ii）每一工件在每台机器上至少加工一次。（iii）每台机器加工各工件的顺序相同。（iv）工件加工中不允许有中间等待。要求确定1,n（工件编号）的一个排序i1,in，使得总加工时间最少。,例8.13是排序（Scheduling）问题的一个子问题，这个子问题的计算复杂性如何呢？下面的分析表明，这一子问题实质上就是旅行商问题，从而是NP完全的。,66,图8.4给出了一个三台机器二个工件的实例。工作Ji需加工5次，依次使用机器21252。工作Ji需加工4次，依次使用机器1231。该图是设先加工Ji作出的，图中的点表示加工活动，旁边的数字为加工时间，箭线反映加工顺序。,由图8.4可以看出，按Ji、Jj顺序加工，两工件至少要加工12单位时间，两工件开始加工时间至少相差5单位时间，否则必然将出现等待。,67,对于一般问题，设加工顺序为i1,in，则在此顺序下的最短加工时间T可按如下方法求得：对每一对工件Jik和Jjk+1，先求它们开工时间差的最小值（可用一子程序计算），令其中为最后工件在各机器上加工时间的总和。,的出现使得T的计算公式不够整齐，为此引入一个虚工件J0，它需在各机器上加工一次，加工时间均为0，并记Ci0为工件i的总中工时间，Coi=0，则有其中i0=0，in+1=0，问题化为求1,n的一个排序i1,in，使按此顺序加工，有最小。显然，这是TSP。,68,从上述讨论容易看出，给定了J1,Jn，可在O(n2)步内求出所有Cij，从而使问题化为TSP，若TSP多项式可解，则例8.13也多项式可解。反之，对每一TSP的实例，也可在多项式时间内构造出一个不允许等待的排序问题，若不允许等待的排序问题多项式可解，则TSP也多项式可解。这样，就搞清了不允许等待的排序问题多项式可解，则TSP也多项式可解。故不允许等待的机器加工问题是NP完全的，因为它等价于NP完全问题TSP。不过，在大多数情况下，找出此类多项式转化关系并不是一件容易的事，它不仅需要对别人已研究过的各类问题有充分的了解，还可能要用到十分精细而又巧妙的技巧。,在建立起实际问题的数学模型后，还应考虑一下是否有必要将模型标准化。也许，适当的标准化会为下一步的研究及算法设计提供方便。先将模型标准化，然后再去寻找算法的例子屡见不鲜。在上一章中求解线性规划的单纯形法是针对标准形式设计的，容易看出这种做法避免了众多麻烦。虽然人们至今尚未发现求解TSP的好算法，但细心的读者不难看出，一般图G（某些顶点之间可以无边相连）上的TSP的求解与完全图（任意两顶点间均有边相连）上的TSP的求解是等价的。因而，我们只需去寻找完全图TSP的算法，这样做的好处是我们可以完全不必顾及去检查图中是否存在着旅行圈（即HC），而HC存在性的检验同样是十分困难的。,69,建立数学模型当然不是我们的最终目的，任一研究实际课题的人早晚总会遇到设计求解算法的问题。不论你是否意识到，从你开始着手设计算法的一刻起，你已站在了一个“十字街口”。你研究的问题具有求解它的多项式算法吗（即它是一个P问题吗）？如果你研究的问题是P问题，而你设计的算法却不是多项式算法，它或者不会被别人接受，或者早晚会被别人推翻。反之，如果你拼全力去寻找多项式算法，又非常可能会一无所获，因为你研究的问题如果不是P问题，例如它是NP完全的，你根本不可能找到多项式算法。只要PNP，这样的算法是根本不存在的。可是，除非你已经找出了多项式算法（从而确立了它是P问题），你无法知道手头的问题到底属于哪一类，你似乎走进了一个怪圈。在这种情况下怎么办才较好吗？据一些建树卓著的专家们介绍，此时最好采用双向攻关的办法。寻找多项式算法的失败也许会为证明问题的NP完全性提供信息，而证明NP完全性中遇到的困难又也许会为设计多项式算法开辟新途径。当然，毫不奇怪，相当一部分问题会久攻不下，成为悬而未决的问题。,70,假如你经过一段时间的研究，倾向于相信你的问题是NP完全的，最好能证明它，因为否则只能一无所获。证明只能如下进行：从已知为NP完全的问题中适当选出一个来（这样的问题有成千上万个），证明这一NP完全问题可以多项式转化为你研究的问题。只要能做到这一点，你就可以交差了。然而，其中有很多的困难，最大的困难之一是确定选择哪一个问题是最合适的。在这里，经验起了很大的作用。虽然从理论上讲，任意已知的NP完全问题均可用于证明一个新问题的NP完全性，但实际上某些问题似乎更合适一些。R.M.Karp在1972年发表的论文中列出了21个NP完全问题，下面的六个问题就包含在其中，并被认为是初学者应当掌握的基本核心，在此基础上再去扩展自己掌握的NP完全类。只有掌握了已有的一些结果和方法，才有可能去证明新问题的NP完全性，六个基本的NP完全问题为：,71,（1）（3满足问题，简记3SAT问题）每一个句子都是一个三项式的SAT问题，称为3SAT问题。例如，就是3SAT的一个实例。,2）（三维匹配问题3DM）X、Y、Z是三个不相交的集合，|X|=|Y|=|Z|=q，。问：M中是否包含一个匹配M，使得（等价问题是求最大三维匹配）。,注：这里给出的是标准形式，一般可不必要求|X|=|Y|=|Z|，表示笛卡尔乘积。,三维匹配问题是下一章中二维匹配（2DM）问题的推广，2DM是P问题而3DM是NP完全的。一个匹配是指M的一个子集合(xi,yi,zi)，xiX，yiY，ziZ，且当下标不同时，它们分别取三个集合中的不同元素。3DM可作如下形象的解释：记一单身男人集合为X，一单身女人集合为Y，此外还有一个住房集合Z。其间存在一相容关系（例如有些人之间不愿组成家庭，或不愿住某一住房），这样就给出了一个集合，M是由问题给出的，表示了所有可能组合。所求的匹配即组成的一组家庭（包括住房），其中不能有重婚，也不能让不同的两个家庭住进同一住房。,72,（3）（划分问题）给定一正整集合A=a1,a2,an，问是否存在A的一个子集A,使得，即是否可将A中的数分成总和相等的两部分。,（4）（顶点复盖问题VC）给定一个图G=（V，E）及一个正整数K|V|，问G中是否有不超过K个顶点的复盖。（一个顶点的子集称为G的一个复盖，若它至少包含G中任一边的两个端点之一）。,（5）（哈密顿圈问题HC）见例8.9。,（6）（团问题）给定图G=（V，E）及一正整数K|V|，问是否存在图G中的一个团V，|V|K。（G的一个顶点的子集V称为G的一个团，若V中任意两点间都有E中的边相连）。,图8.5表达了上述六个问题及SAT问题之间的多项式转化关系，即SAT3SAT，3SAT3DM及3SATVC等等。,73,最后还要说明一点，问题之间有时还会存在包含关系。一问题可能是另一问题的子问题，它也可能是另一问题的推广。问题越一般，其求解常常就越困难。例如，有向图上的HC是无向图上的HC问题的推广。由于无向图HC问题是NP完全的，则有向图上的HC必然也是NP完全的。另外，在例8.9的讨论中，我们事实上已证明HC问题的每一实例均可转化为一个对称的TSP的实例（Cij=Cji），因而对称TSP是NP完全的。不难看出，所得的TSP实例还是满足三角不等式的（即i,j,k，必有Cij+CjkCik），因而，满足三角不等式的TSP也是NP完全的，这样，作为它们的推广，一般的TSP必然也是NP完全的。反之，若一个问题是NP完全的，则其子问题未必一定是NP完全的，它完全可能是一个P问题（当然，也可能是NP完全的）。例如，有人（Kuratowski）已经证明平面图上的团最多只能包含4个顶点，这一结果说明，平面团问题是P问题，尽管团问题是NP完全的。同样，HC问题是NP完全的，但没有人会去研究完全图上的HC问题，因为完全图中必存在着哈密顿圈。,74,习题,1、某饲养场用n种原料配合成饲料喂鸡，为了让鸡生长得快，对m种营养成分有一个最低标准。即对i=1,m，要求第i种营养成分在饲料中的含量不得少于bi，若每单位第j种原料中含第i种营养成分的量为aij，第j种原料的单价为Cj，问应如何配制饲料才能使成本最低？,2、用单纯形法求解：S.tx1+3x2+x442x1+x23x2+4x3+x4