数学建模：组合优化问题和计算复杂性

1、1.1 组合优化问题与算法组合优化问题与算法1.2 计算复杂性问题计算复杂性问题1.3 启发式算法启发式算法1.1 组合优化问题与算法组合优化问题与算法3271510426287ACBCDEF共有共有3!=6种种可能可能得到分配矩阵得到分配矩阵：如何嫁娶，如何嫁娶，使获得的礼使获得的礼品最多品最多？Example 1 婚姻问题婚姻问题 (matching problem)女儿女儿ABC追求者追求者EDF32715104262871.1 组合优化问题与算法组合优化问题与算法婚姻问题的数学模型婚姻问题的数学模型：31,01jijixij否个人个人嫁第如果第3131Max ijijijxcz3 ,

2、2 , 11. .31jxtsiij3 , 2 , 11.31ixjij设设 ：1.1 组合优化问题与算法组合优化问题与算法1. 贪婪（贪婪（Greedy) 解解 一般不会产生最差一般不会产生最差 解；解；2. 在某些模型中在某些模型中, 贪贪 婪算法能得到最优婪算法能得到最优 解；解；3. 可以使用穷举法，可以使用穷举法， 但是以时间为代价但是以时间为代价贪婪解的结果：贪婪解的结果：28+5+1=34最优解的结果：最优解的结果： 27+4+26=57Note：最差解的结果：最差解的结果：3+10+7=203271510426287EFGACBC1.1 组合优化问题与算法组合优化问题与算法Ex

3、ample 2 背包问题背包问题（KP，Knapsack Problem） 假设有人要出发旅行假设有人要出发旅行,他考虑要带他考虑要带 7种物品（每件物品的重量与价值如种物品（每件物品的重量与价值如表）现在假设他最多带表）现在假设他最多带35 kg 物品，物品，问：该带哪几件物品总价值最大？问：该带哪几件物品总价值最大？ 物品 重量)(kgaj 价值jc 1 3 12 2 4 12 3 3 9 4 3 15 5 15 90 6 13 26 7 16 112 设：7101jjxj否种物品如果带第jjjxczMax7135. .71jjjxats共有共有27种种可能可能1.1 组合优化问题与算法组

4、合优化问题与算法Example 3 旅行商问题（旅行商问题（TSP,Travelling Salesman Problem) 一个商人要到一个商人要到n座城市去做生意，座城市去做生意，设两个城市设两个城市i 和和j 之之间的距离为间的距离为dij.如何如何选择一条道路使得选择一条道路使得商人每个城市走一商人每个城市走一遍后回到起点且所遍后回到起点且所走路程最短走路程最短TSP可分为：对称（可分为：对称（dij=dji)和非对称和非对称(dij dji)距离两种距离两种共有共有（n-1)!种可能种可能City 1City 2City 5City 4City 31.1 组合优化问题与算法组合优化问

5、题与算法 jiijijxdmin设：TSP问题的数学模型问题的数学模型) 1 (11. .1nixtsnjij)2(111njxniij)3(, 2 , 1221,nsnssxsjiijjinjijixij1,01否则个城市的边个城市到第表示回路通过第为了减少为了减少变量个数变量个数作用是什么作用是什么共有多少共有多少变量？变量？1 2 5n(n-1)1.1 组合优化问题与算法组合优化问题与算法若若 |s|=n 则由则由n个点构成的一个回路是可行方案。个点构成的一个回路是可行方案。|1Sn因为因为 由前面两个约束条件的限制，不可能由前面两个约束条件的限制，不可能由由 n-1个点构成回路而留一个

6、点在外面个点构成回路而留一个点在外面。Note：条件条件(1)(1)，(2)(2)表示每个城市经过一表示每个城市经过一次，但不能保证它可行，要求局部不构成次，但不能保证它可行，要求局部不构成圈，条件圈，条件(3)(3)就是为了约束这一点就是为了约束这一点。为什么？为什么？nsnssxsjiij, 2 , 1221,1 SiSjijx1.1 组合优化问题与算法组合优化问题与算法 共同特点：可行方案是有限的共同特点：可行方案是有限的 组合优化问题组合优化问题 Definition 1 组合优化问题组合优化问题是一个极小化（或极大化）是一个极小化（或极大化）的问题，它是由以下三部分组成的问题，它是由

7、以下三部分组成：（1 1）实例集合）实例集合 ；（2）对每个实例）对每个实例 I，有一个有穷的可行解集合，有一个有穷的可行解集合 S（I）(3) 目标函数目标函数 f，它对于每个实例，它对于每个实例I和每个可行解和每个可行解 S（I），）， 赋以一个有理数赋以一个有理数 f (I, ). 则实例则实例I的最优解为这样一个可行解的最优解为这样一个可行解 * S(I) ,它使得对于所有它使得对于所有S（I），都有），都有 f (I, *) f (I, ) （f (I, *) f( I, )）。 1.1 组合优化问题与算法组合优化问题与算法组合优化的数学模型：组合优化的数学模型： Min f(x)s

8、.t. g(x) 0 xD其中其中x为决策变量为决策变量 f(x)为目标函数为目标函数g(x)为约束函数为约束函数D为决策变量的定义域，为决策变量的定义域， D为为有限集合有限集合。F=x|x D, g(x) 0可行域所以，可由所以，可由（D，F，f ） 定义一个组合优化问题定义一个组合优化问题。组合优化的描述方法组合优化的描述方法：1数学模型（规划模型）数学模型（规划模型）2文字语言叙述文字语言叙述1.1 组合优化问题与算法组合优化问题与算法一类实际问题的数学模型的总称，如一类实际问题的数学模型的总称，如TSP、LP etc. （一个问题中总包含了若干个参数）对问题给定一组一个问题中总包含了

9、若干个参数）对问题给定一组 参数所得到的例子参数所得到的例子。 一个科学的计算过程，指一步步求解问题的通用程一个科学的计算过程，指一步步求解问题的通用程 序，它是解决问题的程序步骤的一个清晰描述。序，它是解决问题的程序步骤的一个清晰描述。算法是相对问题而言的，不单单是针对问题的某个实例。算法是相对问题而言的，不单单是针对问题的某个实例。如果算法从前一步到后一步的运行是由如果算法从前一步到后一步的运行是由 当时状当时状 态唯一确定的态唯一确定的 如：单纯形法，表上作业法。如：单纯形法，表上作业法。 遗传算法是随机性算法遗传算法是随机性算法。问题：问题：实例实例：算法：算法：Note：确定性算法：

10、确定性算法：1.1 组合优化问题与算法组合优化问题与算法 对于一个极小化（极大化）优化问题对于一个极小化（极大化）优化问题，如果给定任意一个实例如果给定任意一个实例I，算法，算法A总能找到一个可总能找到一个可行解行解* S(I)。 使得使得 f(I, *) f(I, )（f(I, *) f(I, )）启发式算法启发式算法（近似算法，在（近似算法，在1.1. 3 3节中介绍）节中介绍） 组合优化总存在最优算法，但它以时间为代价组合优化总存在最优算法，但它以时间为代价最优算法：最优算法：返回1.2 计算复杂性问题计算复杂性问题 在广泛的意义下，执行算法的效率是用执行算法所在广泛的意义下，执行算法的

11、效率是用执行算法所用的全部计算资源的多少来衡量用的全部计算资源的多少来衡量( (时间、空间时间、空间),),但通常但通常用时间作为衡量标准，这就是计算用时间作为衡量标准，这就是计算( (时间时间) )复杂性问题复杂性问题. . 设有设有n个城市个城市(有向图有向图)则有则有(n-1)！种可能方案。以计！种可能方案。以计算机算机1秒可以完成秒可以完成24个城市所有路径枚举为单位，则个城市所有路径枚举为单位，则讨论讨论TSP问题问题城市数城市数24 25262728 29 30 31计算时间计算时间1s24s10min4. 3h 4.9d136.5d10.8y325y 1.2 计算复杂性问题计算复

12、杂性问题一、如何计算时间一、如何计算时间 1 与实例的输入规模有关，是输入规模与实例的输入规模有关，是输入规模的函数（输入规模指的是：一个问题的实例所有参数的函数（输入规模指的是：一个问题的实例所有参数的二进制表示的长度的总和。可简化为决策变量的个的二进制表示的长度的总和。可简化为决策变量的个数数n，或者顶点的个数，或者顶点的个数m .）f(n) , g(m) etc. 用初等运算用初等运算算术运算、比较、转移等指令的次算术运算、比较、转移等指令的次数，来表示一个算法在假设的计算机上执行时所需的数，来表示一个算法在假设的计算机上执行时所需的时间。时间。相关因素相关因素: :1.2 计算复杂性问

13、题计算复杂性问题 2 与实例的参数有关与实例的参数有关 ， 如如LP 问题：问题： max z=cx s.t. Axb x0, c 0 , b 0 算法的时间复杂性是关于实例输入长度算法的时间复杂性是关于实例输入长度的函数，用来表示算法的时间需求。对于每一个可能的函数，用来表示算法的时间需求。对于每一个可能的输入长度，它是该算法解此输入长度的最坏可能的的输入长度，它是该算法解此输入长度的最坏可能的实例所需的时间（基本运算步骤）。实例所需的时间（基本运算步骤）。相关因素相关因素: :Definition 2 1.2 计算复杂性问题计算复杂性问题研究计算复杂性问题主要是针对研究计算复杂性问题主要是

14、针对n很大的情形很大的情形1 9n2 与与 2n2 O(n2) 2 f(n) = 12n4 - 8n3 + 5n2 + 2n - 80 f(n) = O(n4) 当当n n无限增大时无限增大时，Ln n , n( 0) , an （a 1）趋向于无穷大的速度如何？趋向于无穷大的速度如何？Note：问：问： 1.2 计算复杂性问题计算复杂性问题二、如何评价算法的好坏二、如何评价算法的好坏（从计算复杂性角度）（从计算复杂性角度）复杂性分析的一个研究方向：对算法进行评价复杂性分析的一个研究方向：对算法进行评价 给定给定n个整数个整数x1，x2，xn，要要求将他们从小到大重新排列求将他们从小到大重新排

15、列 取出取出x1，x2，xn中的最小者（需比较中的最小者（需比较n-1次）令其为次）令其为b1（需（需n赋值次），赋值次），从从x1，x2，xn中去中去掉掉b1，在余下的在余下的n-1个数中选出最小者，令其为个数中选出最小者，令其为b2，直到得到直到得到b1,b2,bn，易知其算法共做了，易知其算法共做了n(n-1)/2次比次比较，至多较，至多n(n+1)/2次赋值，计算复杂性为，次赋值，计算复杂性为，O(n2).Example 4 整序问题：整序问题：比较交换法：比较交换法：1.2 计算复杂性问题计算复杂性问题 先先 将两个单调不减的数列将两个单调不减的数列u1，u2um与与v1，v2vm合

16、并为一个单调不减的数列合并为一个单调不减的数列w1，w2w2m方法为方法为u1与与v1比较比较,若若u1 v1，w1 :=v1。再对。再对u1与与v2进行比较，进行比较， 依次对依次对w2，w3w2m赋值，计算量为赋值，计算量为O(m)。快速算法：快速算法： 将将 x1，x2，xn从小到大重新排列（设：从小到大重新排列（设：n=2p+1如果如果n 不是不是2的幂次可补充若干个很大的数字使之成为的幂次可补充若干个很大的数字使之成为2的幂次的幂次）。）。确定一个确定一个wj需要一次比较一次赋值，共需要一次比较一次赋值，共需要（需要（2m-1）次比较，）次比较，2m次赋值次赋值。 1.2 计算复杂性

17、问题计算复杂性问题将将2p+1个数分成个数分成2p个单调不减的个单调不减的2元组元组,计算量为计算量为O(2p)O(2p)= 2p-1 O(2)计算量为计算量为O（2p）综上，算法总工作量为综上，算法总工作量为： (p+1) *O(2p)=O(n logn)8 1 9 6 7 5 3 2(8 1)(9 6)(7 5)(3 2)1 8 6 9 5 7 2 3(1 8 6 9) (5 7 2 3)1 6 8 9 2 3 5 71 2 3 5 6 7 8 9将将2元组两两合并成元组两两合并成2p-1个单调不减的个单调不减的4元组，计算量元组，计算量为为O(2p)依次类推，最后将两个依次类推，最后将两

18、个2p元组合并成为一个单调不减元组合并成为一个单调不减的的2p+1元组元组2 p+1= n1.2 计算复杂性问题计算复杂性问题设设 机器速度机器速度100万次万次/秒秒快速算法快速算法 O(n logn) 需需20秒秒设设 计算机速度为计算机速度为 M 次次/秒秒 问题问题 D 算法算法A计算复杂性计算复杂性 n2算法算法B计算复杂性计算复杂性2n给定给定1秒的秒的机器时间机器时间 算法算法A可解规模可解规模算法算法B可解规模可解规模MM2logn = 100万万比较交换法比较交换法O(n2) 需需5.8天天M = n21.2 计算复杂性问题计算复杂性问题设设 机器速度机器速度100万次万次/

19、秒秒给定给定1秒的秒的机器时间机器时间 算法算法A可解规模可解规模n =算法算法B可解规模可解规模n =MM2log给定给定1秒的秒的机器时间机器时间 算法算法A可解规模可解规模 n=1000算法算法B可解规模可解规模 n=20设设 机器速度提高机器速度提高100倍倍 为为1亿次亿次/秒秒给定给定1秒的秒的机器时间机器时间算法算法A可解规模可解规模n=100010算法算法B可解规模可解规模 n=20+log2100Log2100 0,称称H是是A的的a-近似算法（近似算法（a-approximation algorithm）,当且仅当当且仅当 | ZH(I)- Zopt(I)| a| Zopt

20、(I)|AI 用启发式概念定义的算法集合包含了近似算法概用启发式概念定义的算法集合包含了近似算法概念定义的算法集合，近似算法强调给出算法最坏情况念定义的算法集合，近似算法强调给出算法最坏情况的误差界限，而启发式算法不需考虑偏差程度。的误差界限，而启发式算法不需考虑偏差程度。 1.3 启发式算法启发式算法算法为算法为: : step1 任选一个初始解任选一个初始解so S ； step2 在在N(so)中按某一规则选一中按某一规则选一s，若，若 f(s) f(so)，则，则 so:= s 返回返回 step 2 ； 否则，否则，N(so) :=N(so) - s ; 若若N(so)=， 停止停止

21、; 否则否则，返回返回 step 2 .Example 10 简单的邻域搜索（简单的邻域搜索（local search）算法）算法 给定组合优化问题，假设其邻域结构已确定，设给定组合优化问题，假设其邻域结构已确定，设S为可行解集合，为可行解集合，f 为为S上的费用函数，上的费用函数，N 为邻域结构。为邻域结构。1.3 启发式算法启发式算法简单的邻域搜索达到一个局部最优点简单的邻域搜索达到一个局部最优点依赖于初始解选依赖于初始解选取、邻域结构、取、邻域结构、邻域选点的规则邻域选点的规则启发式算法的长处：启发式算法的长处： 1）数学模型是实际问题的数学模型是实际问题的简化简化，有可，有可能使最优算

22、法所得解比启发式算法所得解产生更大误差；能使最优算法所得解比启发式算法所得解产生更大误差； 2）不少难的组合优化问题可能还没找到有效的最优算法不少难的组合优化问题可能还没找到有效的最优算法； 3）一些启发式算法可以用在最优算法中，如在分支定界一些启发式算法可以用在最优算法中，如在分支定界算法中，可以用启发式算法估界；算法中，可以用启发式算法估界； 1.3 启发式算法启发式算法 4）简单易行，比较直观，易被使用者接受；简单易行，比较直观，易被使用者接受； 5）速度快，在适时管理中非常重要速度快，在适时管理中非常重要； 6）多数情况下，程序简单，因此易于修改多数情况下，程序简单，因此易于修改。 1

23、）不能保证求得最优解不能保证求得最优解； 启发式算法的不足：启发式算法的不足： 2）表现不稳定表现不稳定 ；3）算法的好坏依赖于实际问题、经验和设计者的算法的好坏依赖于实际问题、经验和设计者的 技术，使不同算法之间难以比较技术，使不同算法之间难以比较。 1.3 启发式算法启发式算法三、常见启发式算法类型三、常见启发式算法类型1、一步算法一步算法 该算法的特点是：不在两个可行解之间选择，在未该算法的特点是：不在两个可行解之间选择，在未终止的迭代中，有可能不是一个可终止的迭代中，有可能不是一个可行解，算法结束时得到一个可行解行解，算法结束时得到一个可行解。 Example 11 最优最优H-回路的

24、路线搜索算法回路的路线搜索算法选最小但可达从PjjidQij, . 2., 2 , 1;,0000StepiiQnPiPPidii重复为空集，停止；否则或若置对应城市为的值Step 1Step 2 1;,2, 1;1inNP123451382352133 Z=15依赖于数据特征和依赖于数据特征和初始点的选取，从初始点的选取，从2开始可得更好的开始可得更好的解解1.3 启发式算法启发式算法 该算法的特点是：从一个可行解到另一该算法的特点是：从一个可行解到另一个可行解的选择，通常通过两个解的比较而选择好的个可行解的选择，通常通过两个解的比较而选择好的解，进而作为新的起点进行新的迭代，直到满足一定解

25、，进而作为新的起点进行新的迭代，直到满足一定的要求为止。的要求为止。2、改进算法改进算法如简单的邻域搜索算法。如简单的邻域搜索算法。 四个城市四个城市1，2，3，4的的TSP问题，两个问题，两个城市城市 i 和和 j 之间的距离之间的距离dij构成的距离矩阵为构成的距离矩阵为Example 12 TSP中简单的中简单的2-opt 方法方法06812607108705121050 ijdf (so)=d12+d23+d34+d41=5+7+6+12=30设初始点为设初始点为 so=(1,2,3,4) 则则1.3 启发式算法启发式算法 so的的2-opt 邻域是对邻域是对so的任两个元素对换，的任

26、两个元素对换，如果固定第一个城市如果固定第一个城市1，即，即06812607108705121050 简单的简单的2-opt 方法是比较邻域中的所有点，选出方法是比较邻域中的所有点，选出最好解。比较可知最好解。比较可知N(so)中最好的解为中最好的解为s1 =(1,2,4,3),目标值目标值 f (s1)=29,下一次迭代是以下一次迭代是以 s1重复以上的计算重复以上的计算过程，直到目标值无法改进为止。过程，直到目标值无法改进为止。N( (so)=(1, ,3, ,2, ,4),(),(1, ,4, ,3, ,2),(),(1, ,2, ,4, ,3) ) 数学规划算法、解空间松弛算法、现代优

27、化算法数学规划算法、解空间松弛算法、现代优化算法1.3 启发式算法启发式算法四启发式算法的性能分析四启发式算法的性能分析 评价启发式算法的性能有不同的角度，主要分为：评价启发式算法的性能有不同的角度，主要分为：（1）对算法复杂性的分析对算法复杂性的分析（2 2）对算法计算效能的分析对算法计算效能的分析对随机算对随机算法还要考法还要考虑稳定性虑稳定性 性能分析的常用方法性能分析的常用方法（1） 最坏情形分析最坏情形分析（2） 概率分析概率分析（3） 大规模计算分析大规模计算分析 每个方法都可每个方法都可以从以上两个以从以上两个角度进行分析角度进行分析1.3 启发式算法启发式算法（1） 最坏情形分

28、析最坏情形分析 从最坏情形分析评价一个算法的计算效果时，其评价从最坏情形分析评价一个算法的计算效果时，其评价的指标是计算解的目标值同最优目标值最坏情形时的差距，的指标是计算解的目标值同最优目标值最坏情形时的差距，这个差距越小，说明算法越好。这个差距越小，说明算法越好。 Definition 10 若若 D 是一个极大化问题，实例是一个极大化问题，实例I的最优值为的最优值为Zopt(I),启发式算法启发式算法H所得的解值为所得的解值为ZH(I)，记，记)()()(IZIZIRoptHH 则启发式算法则启发式算法H的绝对性能比的绝对性能比 RH 定义为定义为rIRrRHIH)(1sup1.3 启发

29、式算法启发式算法如何求（或证明）如何求（或证明）RH= a 寻找（证明）存在常数寻找（证明）存在常数 a 使得对任意的实例使得对任意的实例 I ,有有 ZH(I) aZopt(I) 则则 RH a ；界 构造实例构造实例 I 使使aIZIZoptH)()(或构造一系列实例或构造一系列实例In 使使则则 RH a从而从而 有有 RH = a rIRrRHIH)(1sup)()()(naIZIZnoptnH1.3 启发式算法启发式算法启发式算法启发式算法 H H 的渐近性能比的渐近性能比HRkIZIZIZRoptoptHIkH)()()(suplim 启发式算法的性能比是对算法近似程度的一种最启发

30、式算法的性能比是对算法近似程度的一种最坏情形分析坏情形分析，越接近越接近1 表示启发式表示启发式 解越接近最优解解越接近最优解。一般有一般有HHRRHHRR,1.3 启发式算法启发式算法（2） 概率分析概率分析 最坏情形分析是以最坏的实例来评价一个算法或其解，最坏情形分析是以最坏的实例来评价一个算法或其解，这样不免会只因一个实例而影响对一个算法或其解的总体这样不免会只因一个实例而影响对一个算法或其解的总体评价。评价。 概率分析则是假概率分析则是假设实例的数据服从一定的概率分布，在设实例的数据服从一定的概率分布，在 这个数据概率分布的假设下，研究其算法或解的平均效果这个数据概率分布的假设下，研究其算法或解的平均效果。 概率分析在评价算法方面的一个成功应用是对概率分析在评价算法方面的一个成功应用是对LPLP的单纯的单纯 形法的评价形法的评价。 最坏情形分析和概率分析方法的共同特点，用理论方法分最坏情形分析和概率分析方法的共同特点，用理论方法分 析算法同最优解之间的误差界，要求有较强