数学建模常用技巧

数学建模常用技巧第1页，共30页，2023年，2月20日，星期六常用技巧计算复杂性分析算法设计

精确算法近似算法算法计算量估计、算法优劣比较第2页，共30页，2023年，2月20日，星期六比较算法的好坏，从不同的角度出发，有各种不同的标准。在这里，我们仅就算法的计算速度作一个十分粗略的比较。

例1

（整理问题）给定n个实数a1,a2,…,an，要求将它整理成由小到大排列（或由大到小排列）的顺序：b1,b2,…,bn，b1≤b2≤…≤bn。（算法1）取出a1,a2,…,an中的最小者，令其为b1。从a1,a2,…,an中去除b1，在余下的n—1个数中选出最小者，令其为b2，…，直至得到b1,b2,…,bn。容易看出，为了排出b1,b2,…,bn，算进行了n(n-1)/2次比较。（算法2）步0b1←a1

步1设已有b1,…,bk(1≤k<n)，将按两分法比较的方式把ak+1排入其中：若b1≤…≤bi≤ak+1≤bi+1≤…≤bk，令（b1,b2,…,bk,bk+1）←（b1,…,bi,ak+1,bi+1,…,bk）。若k+1<n，令k←k+1，返回步1。计算复杂性第3页，共30页，2023年，2月20日，星期六我们来分析一下算法2的计算量：排出b1不必作比较，排出b2只需作一次比较，…，一般，在排ak+1时，设2r－1≤k＜2r，则只需作r次比较即可将ak+1安排在它应排的位置上。例如在排a8时，k=7，先和b4比，若a8>b4，可再和b6比（若a8<b4则和b2比），易见，只要比3次即可排入a8，由于r≤log2k+1，算法的比较次数不超过令，，设计算机每秒可作C次比较，则算法1与算法2整理a1,a2,…,an所用的时间分别为

若n=100万，C=100万次/秒，则t1≈5.8天，而t2≈20秒。可见在较大规模的整理问题时，算法2明显优于算法1。

第4页，共30页，2023年，2月20日，星期六现设一台每小时能作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可解问题的规模只增加了log2100<7。前者可解问题的规模成倍成倍地增加而后者则几乎没有什么改变，今天无法求解的问题将来也很少有希望解决。由于这一原因，人们对算法作了如下的分类：第5页，共30页，2023年，2月20日，星期六（多项式算法）设A是求解某一问题D的一个算法，对D的一个规模为n的实例，用fA(D,n)表示用算法A求解这一实例所作的初等运算的次数。若存在一个多项式P(n)和一个正整数N，当n≥N时总有fA(D,n)≤P(n)（不论求解D的怎样的实例，只要其规模为n），则称算法A为求解问题D的一个多项式时间算法，简称多项式算法。（指数算法）设B是求解某一问题D的一个算法，fB(D,n)为用算法B求解D的一个规模为n的实例时所用的初等运算次数，若存在一个常数k>0，对任意正整数N，总可找到一个大于N的正整数n及D的一个规模为n的实例，对这一实例有fB(D,n)=O(2^kn)，则称B为求解问题D的一个指数算法。多项式算法被称为是“好”的算法即所谓有效算法，而指数算法则一般被认为是“坏”算法，因为它只能求解规模极小的实例。第6页，共30页，2023年，2月20日，星期六下面的表1列出了在规模大约为n时各类算法的计算量，而表2则反映了当计算机速度提高10倍、100倍时，各类算法在1小时内可求解的问题的模型的增长情况，（前三个是多项式时间的，后两个是指数时间的）表1几个多项式和指数时间复杂性函数增长情况算法要求的计算量规模n的近似值101001000n101001000nlogn336649966n31031061092n10241.27×10301.05×10301n!3628800101584×102567第7页，共30页，2023年，2月20日，星期六表21小时内可解的问题实例的规模算法要求的计算量用现在计算机用快10倍计算机用快100倍计算机nN110N1100N1nlognN28.2N267N2n3N32.15N34.64N32nN4N4+3.32N4+6.64n!N5≤N5+2≤N5+3由上可知4n2与2n2都是O(n2)，nlogn+3n是O(nlogn)，我们在以后分析时间复杂性函数时也往往忽略常系数和增长速度较慢的项，因为前者可通过提高计算机速度来提高效率，而后者增长速度最快的项才是决定效率的关键因素。下面介绍六个最初的NP难问题第8页，共30页，2023年，2月20日，星期六（1）（3—满足问题，简记3—SAT问题）每一个句子都是一个三项式的SAT问题，称为3—SAT问题。例如，就是3—SAT的一个实例。命题逻辑中合取范式(CNF)的可满足性问题(SAT)是当代理论计算机科学的核心问题,是一典型的NP完全问题.考虑CNF：A=C1∧⋯∧Ci∧⋯∧Cn(1)子句Ci具有如下形式：Pi,1∨Pi,2∨⋯∨Pi,ki∨┐Pri,1∨┐Pri,2∨⋯∨┐Pri,kri,其中Pi,1,Pi,2,⋯,Pi,ki,┐Pri,1,┐Pri,2,⋯,┐Pri,kri是两两不同的文字,Pi,j为命题变元集{P1,P2,⋯,Pm}中的一个变元,文字┐Pi表示变元Pi的非,m表示命题变元的个数,n表示子句的个.一个SAT问题是指:对于给定的CNF是否存在一组关于命题变元的真值指派使得A为真.下面介绍六个最初的NP难问题第9页，共30页，2023年，2月20日，星期六（1）（3—满足问题，简记3—SAT问题）每一个句子都是一个三项式的SAT问题，称为3—SAT问题。例如，就是3—SAT的一个实例。下面介绍六个最初的NP难问题如果A为真,则CNF的每个子句中必有一个命题变元为1(真),将每个子句中的每个命题变元取反,则CNF的每个子句中必有一个命题变元为0(假),然后将∧看成加,将∨看成乘,将变元Pi看成实参数xi,则SAT问题就可以转换为一个求相应实函数最小值的优化问题.令T表示这种转换,它可递归地定义为T:A→Rm→R,T(C1∧⋯∧Ci∧⋯∧Cn)=T(C1)+⋯+T(Ci)+⋯+T(Cn),T(Ci)=T(Pi,1∨Pi,2∨⋯∨Pi,ki∨

┐Pri,1∨┐Pri,2∨⋯∨┐Pri,kri)

=T(Pi,1)T(Pi,2)⋯T(Pi,ki)T(┐Pri,1)T(┐Pri,2)⋯T(┐Pri,kri),i=1,⋯,n.T(Pi)=1-xi,T(┐Pi)=xi,xi∈[0,1],i=1,⋯,m,

T(T)=1,T(F)=0.

第10页，共30页，2023年，2月20日，星期六（1）（3—满足问题，简记3—SAT问题）每一个句子都是一个三项式的SAT问题，称为3—SAT问题。例如，就是3—SAT的一个实例。下面介绍六个最初的NP难问题例如,

T((P1∨┐P2)∧(┐P1∨┐P2))=T(P1∨┐P2)+

T(┐P1∨┐P2)=T(P1)T(┐P2)+T(┐P1)T(┐Pv2)=(1-x1)x2+x1x2,用E(x1,x2,⋯,xm)表示T(A)在点(v(P1),⋯,v(Pm))的值,则有下面定理.定理1.赋值v为使A可满足的充要条件是E(x1,x2,⋯,xm)达到最小值0.

于是一个SAT问题可以转化为优化模型求解:minE(x1,x2,⋯,xm)ST:xi=0,或1第11页，共30页，2023年，2月20日，星期六2）（三维匹配问题——3DM）X、Y、Z是三个不相交的集合，|X|=|Y|=|Z|=q，。问：M中是否包含一个匹配M，使得（等价问题是求最大三维匹配）。注：这里给出的是标准形式，一般可不必要求|X|=|Y|=|Z|，表示笛卡尔乘积。三维匹配问题是二维匹配（2DM）问题的推广，2DM是P问题而3DM是NP完全的。一个匹配是指M的一个子集合{(xi,yi,zi)}，xi∈X，yi∈Y，zi∈Z，且当下标不同时，它们分别取三个集合中的不同元素。3DM可作如下形象的解释：记一单身男人集合为X，一单身女人集合为Y，此外还有一个住房集合Z。其间存在一相容关系（例如有些人之间不愿组成家庭，或不愿住某一住房），这样就给出了一个集合，M是由问题给出的，表示了所有可能组合。所求的匹配即组成的一组家庭（包括住房），其中不能有重婚，也不能让不同的两个家庭住进同一住房。下面介绍六个最初的NP难问题第12页，共30页，2023年，2月20日，星期六（3）（划分问题）给定一正整集合A={a1,a2,…,an}，问是否存在A的一个子集A’,使得，即是否可将A中的数分成总和相等的两部分。（4）（顶点复盖问题——VC）给定一个图G=（V，E）及一个正整数K≤|V|，问G中是否有不超过K个顶点的复盖。（一个顶点的子集称为G的一个复盖，若它至少包含G中任一边的两个端点之一）。下面介绍六个最初的NP难问题找出所有满足xi=0或1，f=∑ai*xi=（∑A）/2的解练习：用MATLAB或LINGO实现划分问题（5）（团问题,控制集问题）给定图G=（V，E）及一正整数K≤|V|，问是否存在图G中的一个团V’，|V’|≥K。（G的一个顶点的子集V’称为G的一个团，若V’中任意两点间都有E中的边相连）。

第13页，共30页，2023年，2月20日，星期六问题4,5的应用之一:系统监控模型设图G=(V,E),KV如果图G的每条边都至少有一个顶点在K中,则称K是G的一个点覆盖.

若G的一个点覆盖中任意去掉一个点后不再是点覆盖,则称此点覆盖是G的一个极小点覆盖.

顶点数最少的点覆盖,称为G的最小点覆盖.例如,右图中,{v0,v2,v3,v5,v6}等都是极小点覆盖.{v0,v1,v3,v5},{v0,v2,v4,v6}都是最小点覆盖.第14页，共30页，2023年，2月20日，星期六最大独立点集

定义2设图G=(V,E),IV如果I中任意两个顶点在G中都不相邻,则称I是G的一个独立点集.

若G的一个独立点集中,任意添加一个点后不再是独立点集,则称此独立点集是G的一个极大独立点集.

顶点数最多的独立点集,称为G的最大独立点集.例如,右图中,{v1,v4}等都是极大独立点集.{v1,v3,v5},{v2,v2,v6}是最大独立点集.第15页，共30页，2023年，2月20日，星期六最小控制集

定义3设图G=(V,E),DV如果v∈V,要么v∈D,要么v与D的某个点相邻,则称D是G的一个控制集.

若G的一个控制集中任意去掉一个点后不再是控制集,则称此控制集是G的一个极小控制集.

顶点数最少的控制集,称为G的最小控制集.例如,右图中,{v1,v3,v5}是极小控制集,{v0}是最小控制集.第16页，共30页，2023年，2月20日，星期六系统监控问题之二

假设下图代表一指挥系统,顶点v1,v2,…,v7表示被指挥的单位,边表示可以直接下达命令的通信线路.欲在某些单位建立指挥站,以便可以通过指挥站直接给各单位下达命令,问至少需要建立几个指挥站?

这就是要求最小控制集问题.v2v1v3v7v6v5v4{v1,v3},{v3,v5}等都是最小控制集,所以至少需要在2个单位建立指挥站.

到目前为止,还没有找到求最小控制集的有效算法.一种启发式近似算法.第17页，共30页，2023年，2月20日，星期六最小点覆盖、最大独立点集和最小控制集的关系

定理1设无向图G=(V,E)中无孤立点(不与任何边关联的点),若D是G中极大独立点集,则D是G中极小控制集.

定理2设无向图G=(V,E)中无孤立点,KV,则K是G的点覆盖当且仅当Kc=V\K是G的独立点集.

推论设无向图G=(V,E)中无孤立点,KV,则K是G的最小(极小)点覆盖当且仅当Kc=V\K是G的最大(极大)独立点集.第18页，共30页，2023年，2月20日，星期六若图G中的一个顶点和一条边相互关联，则称它们相互覆盖．覆盖图G的所有边的一个顶点子集，称为图G的一个顶点覆盖．类似，覆盖图G的所有顶点的一个边子集称为图G的一个边覆盖．G的所有顶点覆盖中顶点最少的数目称为图G的顶点覆盖数，或者简称为点覆盖记为α0一个图G的边覆盖、最大边覆盖以及边覆盖数．并用α１来表示一个图G的边覆盖数。分别用β０和β１来表示图G的独立数和匹配数。可知，关于一个阶数为P的非平凡的连通图的覆盖数与独立数具有如下关系：α０＋β０＝α１＋β１＝P由此结果容易看出，求一个图G的最小覆盖数等价于求这个图的最大独立集．而图的最小覆盖问题、图的最小团问题以及图的最大独立集问题两两等价第19页，共30页，2023年，2月20日，星期六设G＝(V,E)是一无向图，其中V是图中顶点集合，E是边的集合．｜V｜表示图中顶点的个数．｜E｜表示图中的边数．顶点覆盖问题是找一V的子集S,找子集S，满足（i,j)∈E,i和j至少有一个属于S,即求解下列规划模型：MINCXxi∈S,ST：∑(i=1..p)∑(j=i+1..P)aij(1-xi)(1-xj)=0C=[1,…1];X=[x1,x2…,xp];(aij)图的邻接矩阵Xi=1(vi∈S)否则为0；第20页，共30页，2023年，2月20日，星期六（6）（哈密顿圈问题——HC）包含G的每个顶点的轨叫做Hamilton(哈密顿)轨;闭的Hamilton轨叫做Hamilton圈或

圈；含Hamilton圈的图叫做Hamilton图。直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。判断某图是否为哈密顿图至今还是一个难题.总结判断某图是哈密顿图或不是哈密顿图的某些可行的方法.1.观察出哈密顿回路.第21页，共30页，2023年，2月20日，星期六（6）（哈密顿圈问题——HC）1.观察出哈密顿回路.下图(周游世界问题)是哈密顿图易知a

b

c

d

e

f

g

h

i

j

k

l

m

n

p

q

r

s

t

a为图中的一条哈密顿回路.第22页，共30页，2023年，2月20日，星期六（6）（哈密顿圈问题——HC）设G是n阶无向简单图，若对于任意不相邻的顶点vi,vj，均有d(vi)+d(vj)

n1()则G中存在哈密顿通路.设G为n(n3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有

d(vi)+d(vj)

n

（）则G中存在哈密顿回路，从而G为哈密顿图.2．满足条件（）的图是哈密顿图.例

完全图Kn(n3)中任何两个顶点u,v，均有

d(u)+d(v)=2(n1)

n（n3），所以Kn为哈密顿图.3．哈密顿回图的实质是能将图中所有的顶点排在同一个圈中.第23页，共30页，2023年，2月20日，星期六例2.（婚姻问题）在遥远的地方有一位酋长，他想把三个女儿嫁出去。假定三个女儿为A、B、C，三位求婚者为X、Y、Z。每位求婚者对A、B、C愿出的财礼数视其对她们的喜欢程度而定,（见下表）：

XYZA3526B271028C147

问酋长应如何嫁女，才能获得最多的财礼（从总体上讲，他的女婿最喜欢他的女儿）。婚姻问题------P问题第24页，共30页，2023年，2月20日，星期六例2.显然是指派问题的实例，但它也可以看成是两分图赋权匹配问题的实例。用三个点表示酋长的三个女儿，将它们放在一边。再用三个点表示求婚者，将它们放在另一边。在有可能结婚的两人之间画一条边，并在边上写上求婚者对这种结婚愿付出的财礼数，得到左图。左图是一个特殊的图，它的顶点可以分成两个子集，只有分属不同子集的点才可能有边相连（但也可以无边），这样的图称为两分图。定义3.(匹配)

图G的一个匹配是指边集E的一个子集M，M中的任意两条边均不具有公共的顶点。容易看出，酋长要解的问题是在上面的两分图中找出一个具有最大权和的匹配，读者不难由此得到一般两分图最大权匹配问题的数学模型。

以上举的是一个P问题，下面来看一个NP难问题第25页，共30页，2023年，2月20日，星期六用三个点表示酋长的三个女儿，将它们放在一边。再用三个点表示求婚者，将它们放在另一边。在有可能结婚的两人之间画一条边，并在边上写上求婚者对这种结婚愿付出的财礼数，得到左图。左图是一个特殊的图，它的顶点可以分成两个子集，只有分属不同子集的点才可能有边相连（但也可以无边），这样的图称为两分图。定义3.(匹配)

图G的一个匹配是指边集E的一个子集M，M中的任意两条边均不具有公共的顶点。容易看出，酋长要解的问题是在上面的两分图中找出一个具有最大权和的匹配，读者不难由此得到一般两分图最大权匹配问题的数学模型。

以上举的是一个P问题，下面来看一个NP难问题第26页，共30页，2023年，2月20日，星期六例3

（装箱问题——Bin—packing）有一批待装箱的物品J={p1,…,pn}，pj的长度为l(pj)。现有一批容量为C的箱子（足够数量），要求找到一种装箱方法，使得所用的箱子数最少。

例3是一个一维的装箱问题。例如，我们有一批具有相同长度的钢材，如果想取出几根已知长度的钢料生产某种设备，当然会希望少用几根原始钢材以减少浪费。此时，我们就遇到了一个一维的Bin—packing问题。当我们想从购买来的三夹板上锯出n块已知长、宽的板来制作家具时，遇到的是二维Bin—packing问题。而当我们真正想把一批已知长、宽、高的物体装入具有相同尺寸的箱子时，又遇到了三维的。下面的定理告诉我们，即使是一维的Bin—packing问题也是NP完全的，故二维和三维的Bin—packing问题更不可能是P问题（它们也是NP完全的）。定理1.

（一维