资源描述：
《数学建模组合优化问题和计算复杂性ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章组合优化问题和计算复杂性§1.1组合优化问题与算法§1.2计算复杂性问题§1.3启发式算法§1.1组合优化问题与算法DEF共有3!=6种可能得到分配矩阵：如何嫁娶，使获得的礼品最多？Example1婚姻问题(matchingproblem)女儿ABC追求者EDF3271510426287§1.1组合优化问题与算法婚姻问题的数学模型：设：§1.1组合优化问题与算法贪婪（Greedy)解一般不会产生最差解；在某些模型中,贪婪算法能得到最优解；3.可以使用穷举法，但是以时间为代价贪婪解的结果：28+5+1=34最优解的结果：27+4+26=57Note：最差解的结果：3+10+7=
2、20§1.1组合优化问题与算法Example2背包问题（KP，KnapsackProblem）假设有人要出发旅行,他考虑要带7种物品（每件物品的重量与价值如表）现在假设他最多带35kg物品，问：该带哪几件物品总价值最大？设：共有27种可能§1.1组合优化问题与算法Example3旅行商问题（TSP,TravellingSalesmanProblem)一个商人要到n座城市去做生意，设两个城市i和j之间的距离为dij.如何选择一条道路使得商人每个城市走一遍后回到起点且所走路程最短TSP可分为：对称（dij=dji)和非对称(dij≠dji)距离两种共有（n-1)!种可能City1Cit
3、y2City5City4City3§1.1组合优化问题与算法设：TSP问题的数学模型：为了减少变量个数作用是什么共有多少变量？25n(n-1)§1.1组合优化问题与算法若
4、s
5、=n则由n个点构成的一个回路是可行方案。因为由前面两个约束条件的限制，不可能由n-1个点构成回路而留一个点在外面。Note：条件(1)，(2)表示每个城市经过一次，但不能保证它可行，要求局部不构成圈，条件(3)就是为了约束这一点。为什么？§1.1组合优化问题与算法共同特点：可行方案是有限的——组合优化问题Definition1组合优化问题π是一个极小化（或极大化）的问题，它是由以下三部分组成：（1）实例集合；
6、（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组合优化问题与算法组合优化的数学模型：Minf(x)s.t.g(x)≥0x∈D其中x为决策变量f(x)为目标函数g(x)为约束函数D为决策变量的定义域，D为有限集合。F={x
7、x∈D,g(x)≥0}——可行域所以，可由（D，F，f）定义一个组合优化问题。组合优化的描述方法：1°数学模型（规划模型）2
8、°文字语言叙述§1.1组合优化问题与算法一类实际问题的数学模型的总称，如TSP、LPetc.（一个问题中总包含了若干个参数）对问题给定一组参数所得到的例子。一个科学的计算过程，指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述。算法是相对问题而言的，不单单是针对问题的某个实例。如果算法从前一步到后一步的运行是由当时状态唯一确定的如：单纯形法，表上作业法。遗传算法是随机性算法。问题：实例：算法：Note：确定性算法：§1.1组合优化问题与算法对于一个极小化（极大化）优化问题π，如果给定任意一个实例I，算法A总能找到一个可行解σ*∈S(I)。使得f(I,σ*)≤f(I,σ
9、)（f(I,σ*)≥f(I,σ)）启发式算法（近似算法，在§1.3节中介绍）组合优化总存在最优算法，但它以时间为代价最优算法：返回§1.2计算复杂性问题在广泛的意义下，执行算法的效率是用执行算法所用的全部计算资源的多少来衡量(时间、空间),但通常用时间作为衡量标准，这就是计算(时间)复杂性问题.设有n个城市(有向图)则有(n-1)！种可能方案。以计算机1秒可以完成24个城市所有路径枚举为单位，则讨论TSP问题城市数2425262728293031计算时间1s24s10min4.3h4.9d136.5d10.8y325y§1.2计算复杂性问题一、如何计算时间1°与实例的输入规模有关，
10、是输入规模的函数（输入规模指的是：一个问题的实例所有参数的二进制表示的长度的总和。可简化为决策变量的个数n，或者顶点的个数m.）f(n),g(m)etc.用初等运算——算术运算、比较、转移等指令的次数，来表示一个算法在假设的计算机上执行时所需的时间。相关因素:§1.2计算复杂性问题2°与实例的参数有关，如LP问题：maxz=c’xs.t.Ax≤bx≥0,c≤0,b≥0算法的时间复杂性是关于实例输入长度的函数，用来表示算法的时间需求。对于每一个可能的输入长度，它是该算法
