浙大城院数学建模6

MCM1第六章离散优化模型前言6.1算法计算量的比较6.2P问题与NP难问题6.3几个经常遇到而又较为简单的P问题6.4NP难问题举例MCM2在某些优化问题中，变量（或部分变量）只能取自于一个离散的集合，这个离散集合有时是可列无限集（如整数全体等），有时甚至是有限集，此时我们遇到的就是一个离散优化问题。前言MCM36.1算法计算量的比较有人认为，只要计算机好，不怕做不出题目，这种想法对吗？抱有这种想法的人实际上犯了一个常识性的错误，殊不知计算机好只不过是硬件好，要能充分发挥出计算机的作用,还需要有好的软件来配合。没有好的算法，你有再好的计算机也没用。例6.1（整理问题）给定n个实数a1,a2,…,an，要求将它整理成由小到大排列（或由大到小排列）的顺序：b1,b2,…,bn，b1≤b2≤…≤bn。MCM4（算法1）取出a1,a2,…,an中的最小者，令其为b1。从a1,a2,…,an中去除b1，在余下的n—1个数中选出最小者，令其为b2，…，一直进行下去，直至最后得到b1,b2,…,bn。容易看出，为了排出b1,b2,…,bn，算法共作了(1)2nn次比较。MCM5（算法2）（算法用归纳法定义）步0b1←a1步1设已排好b1,…,bk(1≤kn)，将按两分法比较的方式把ak+1排入其中，先与最中间的数（或最中间的两数之一）比较，…，直至确定ak+1应在的位置。若b1≤…≤bi≤ak+1≤bi+1≤…≤bk，令（b1,b2,…,bk,bk+1）←（b1,…,bi,ak+1,bi+1,…,bk）。若k+1n，令k←k+1，返回步1。MCM6我们来分析一下算法2的计算量。先看一个简单例子：设已排好7,654321,,,,,bbbbbbb下一步将插入a8。先比较a8和a4：若a8小于b4，下一步将比较a8与a2，等等若a8大于b4，下一步将比较a8与a6插入a8共需作3次比较。对一般情况，排出b1不必作比较，排出b2只需作一次比较，…，以此类推MCM7在排ak+1时，若2r－，1≤k＜2r，则只需作r次比较即可将ak+1安排在它应排的位置上。由于r≤log2k+1，算法的总比较次数不超过：1112222111122(1)loglog(2)log(2)loglognnnkkknnkkknnn（注：这里我们用到了不等式2baab）MCM8令1(1)()2nnfn，22()logfnnn，设计算机每秒可作C次比较，则算法1与算法2整理a1,a2,…,an所用的时间分别为11()fntC22()fntC若n=100万，C=100万次/秒，则t1≈5.8天，而t2≈20秒。可见在解较大规模的整理问题时，算法2明显优于算法1。MCM9从上面的例1可以看出，在设计算法时，计算量的大小显得非常重要，它关系到计算机科学研究的中心课题之一：计算复杂性问题。在本章中我们将要简单介绍一些相关的知识。为了方便读者理解，我们将不引用严格的定义，而采用一些较为通俗易懂的叙述方法，希望了解进一步知识的读者可以查阅相关的书籍或文献资料。例6.2（酋长嫁女儿）非洲某酋长国的酋长想把自己的三个女儿嫁出去。记他的三个女儿为A、B、C，现设恰有三位求婚者，记他们为X、Y、Z（这是标准形式，在一般模型中女儿数和求婚者人数可以不同）。每位求婚MCM10者对A、B、C愿意支付的财礼数视其喜欢程度的不同而不同，设：ZYX1273410572826ABC（矩阵中的元素cij为求婚者i娶j愿付的财礼数）问酋长应当如何嫁女儿，才能获得最多的财礼（从总体上讲，他的女婿最喜欢他的女儿）。MCM11建模引入变量ijx，本问题的数学模型为：maxijijcx31.1ijistx31ijjix01ijx或（6.1）在（6.1）中，变量只能取0或者1，故被称为0-1（线性）规划问题，0—1规划属于离散优化问题。MCM12让我们先来对上面的例6.2（酋长嫁女儿问题）设计一些求解算法，并对这些算法加以一一比较，以判定这些算法的优劣。（算法1）（贪婪法）如果酋长采用类似于拍卖的方式将女儿一个个地嫁出去，在嫁出每一个女儿时，将她嫁给当前财礼出得最高的求婚者，并遵守一夫一妻制的原则，这一方法被称为贪婪法或贪心法（注：拍卖会上采用的就是贪婪法）。根据这一方法将有：C嫁给Y，B嫁给X，A嫁给Z，酋长得到的总财礼数为34。MCM13分析：算法1的最大缺点是它没有求出最好的结果，事实上，只要将C嫁给X，将A嫁给Y，将B嫁给Z，则酋长可以得到的总财礼数将增加到57。（算法2）（穷举法）不难看出，酋长嫁女儿的不同方法只有六种。比较所有可能的嫁女儿方法，酋长即可找到能获得最多财礼数的嫁法（总财礼数为57），显然，这是穷举法。MCM14分析：读者也许会想，酋长已找到最好的嫁女儿方法，问题已经解决了，其实不然。为什么我们要将此问题称为酋长嫁女儿呢？因为一般人的儿女不多，如何嫁女儿根本不成问题。但非洲的某些酋长就不同了，他们有的有一、两百个儿女，例如，不妨设有100个女儿，此时他如果也采用穷举法，将一一比较100！种不同的嫁法。100！究竟有多大呢？读者不妨找一个计算器（或计算机）来算一下。不算不知道，一算吓一跳。如果酋长真的用穷举法来嫁他的女儿，当他知道该如何嫁法时，他的女儿们早已变成了化石，当然，酋长本人也早已变成了化石，在他的有生之年根本不可能得出答案。MCM15在介绍其他算法之前，我们先来看一下什么是算法，为此，我们得先来区分一下以下的两个不同的概念，即“问题”与“实例”。由于篇幅的限止，我们不准备给出严格的定义。我们所说的问题是指对一类实际问题的数学模型的总称。在问题中一般总包含着若干个参数，给定这些参数，就给出了这一问题的一个实例。为区分起见，今后我们一般将用D来记某一离散模型问题，用I来记离散模型问题的某一实例。例如，酋长嫁女儿问题的标准形式为酋长有n个女儿（含参数n），有n个求婚者前来求婚，求婚者j对女儿i肯支付的财礼数为MCM16），，；，（njnicij......1......,1,（含参数“财礼矩阵”）其数学模型为：maxijcx1,1nijistx11nijjx01x或（6.2）（注：问题的标准形式常被表示为求极小解，而且女儿数和求婚者数相等，非标准形式可以通过等价变换化为标准形式）MCM17（6.2）中包含了一些参数：数n和矩阵nnC。例如，例6.2就是它的一个实例。那么，什么是算法呢？算法是为求解问题而设计的方法，对问题的任意一个实例，算法都应该能求出其相应的解来。在给定n及nnC后我们就得到了问题的一个实例，其实，酋长嫁女儿问题的学名叫MCM18我们称其为酋长嫁女儿只是为了更形象一些而已。标准的指派问题要求矩阵为方阵，其元素0ijc目标为求极小，非标准形式可以十分容易地转化为标准形式。指派问题具有一些特殊的性质，存在着由匈牙利数学家Konig提出的简便解法——匈牙利算法。算法主要依据以下事实：如果系数矩阵C=（Cij）的一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=（bij），则以C和B为系数矩阵的指派问题具有相同的最优指派。MCM19例6.3设系数矩阵为：16151922172119182422181717192216C求次指派问题的一个最优指派（即求矩阵中4个不同行不同列的元素），使总和最小。解：将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得MCM2011047042175101360B再将第3列元素各减去1，得**2**1037041175001350B不难看出，以B2为系数矩阵的指派问题有最优指派：12342134（总和为0，不可能再小）MCM21由等价性，它也是例2的最优指派。有时候，问题会变得稍微复杂一些。例6.4求解系数矩阵为C的指派问题12797989666717121412151466104107106CMCM22解：先作等价变换如下1279798966671712141215146610410710677664****50202230000105759800406362容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，最优指派还无法看出。此时等价变换还可进行下去，步骤如下：MCM23（1）对未选出0元素的行打√；（2）对√行中0元素所在列打√；（3）对√列中选中的0元素所在行打√；重复（2）、（3）直到无法再打√为止。（读者可以想一下为什么要这样做）可以证明，若用直线划出没有打√的行和打√的列，就得到了能够复盖住矩阵中所有零元素的最少条数的直线集合，找出未复盖的元素中的最小者，令√行元素减去此数，√列元素加上此数，则原先选中的0元素不变，而未被复盖的元素中至少会有一个已转变为0（未覆盖元素中的最小者），且新矩阵的指派问题与原问题也有相同的最优指派。MCM24上述过程可反复采用，直到能选出足够的0元素为至。例如，对例6.4变换后的矩阵再作变换，第三行、第五行元素减去2，第一列元素加上2，得到70202430000835311800404140现在已可看出，最优指派为1234524135MCM25为了证明上述算法必能求出最优解，还需要证明几个定理，例如：没有打√的行和打√的列必能覆盖所有的零元素：上述调整步骤最多进行有限次，必可选出最优解等等，由于篇幅的限制，我们不打算再在此处作进一步的讨论。（算法3）（指派问题的匈牙利算法）根据以上实例的求解，读者不难自己归纳出匈牙利算法。算法2的计算量为n!，当n较大时，我们根本不可能用它来求解。一般，如果可以找到一个实例，当算法求解此实例时需要用到的计算量至少为MCM26)1(aan其中，则我们称此算法为并认为它不是好算法，（显然，算法2是指数算法，因为n!大于2n）。可以证明，匈牙利算法的计算量为)(3nO，即使100n，利用计算机也只需要几秒钟就能求出最优解。MCM27如果存在一个多项式P(n)，对问题的任何一个规模为n（例如有n个变量）的实例，求解此实例的计算量均不会超过P(n)，则称此算法为并认为这种算法是好算法（当然，多项式的次数越低越好），匈牙利算法就是一个次数较低的多项式时间算法。为了使读者对指数算法与多项式算法有一个更直观的了解，我们还将对这两类算法再作一些比较。MCM28设我们有一台每小时能作M次运算的计算机，并设求解某一问题已有了两个不同的算法。算法A对规模为n的实例约需作n2次运算，而算法B则约需作2n次运算。于是，运用算法A在一小时内大约可解一个规模为M的实例，而算法B则只能解一个规模为log2M两者的差别究竟有多大呢？让我们用数字来对比一下。假如计算机每秒钟可作100万次运算，则算法A一小时大约可解一个规模为n=60000的实例，而算法B在一小时内只能解一个规模小于28的实例且n每增加1，算法B求解时所化的时间就将增加1倍。例如算法B求解一个n=50的实例将连续运算357年多。MCM29现设计算速度提高了100倍，这对计算机来讲（即硬件）已是一个相当大的改进。此时算法A可解问题的规模增大了10倍，而算法B可解问题的规模只增加了log21007。前者可解问题的规模将会成倍成倍地增加，而后者则几乎没有什么改变，故今天无法求解的问题将来也很少有希望解决。从下面的表6-1中，读者也可得出类似的结论：MCM30表6-1几个多项式时间和指数时间算法的计算时间增长情况算法要求的计算量规模n的近似值101001000N101001000Nlogn336649966N31031061092n10241.27×10301.05×103