数学文化之运筹学

数学文化之运筹学刘丙强山东大学数学学院知新楼B835;88363455bingqiangsdu@2013-11-13 (2)1运筹学理论内容：2数学规划线性规划整数规划内容组合优化图与网络网络优化算法分析算法复杂性近似算法非线性规划组合优化综述组合最优化：解决离散结构上的优化问题；主要包括：组合数学；数学规划（线性规划）；算法理论与方法；图论中的优化问题；本节内容：组合优化化问题与算法；算法复杂性；近似算法3算法理论算法：解决问题的步骤；输入与输出；流程与语言；复杂性：时间、空间复杂性；准确性的衡量；计算机与算法；算法思想：精确算法；贪婪算法；启发式算法；近似算法；确定性算法、非确定性算法；4算法理论：复杂性时间复杂性（算法可行性与扩展性）：算法运行时间的快慢；与输入数据规模有关；上界：函数f(n)和g(n)都是整数到正实数的函数，如果存在正整数n0和正常数c，使得对所有n≥n0，都有f(n)≤cg(n)，就称f(n)的阶至多是O(g(n))。下界：函数f(n)和g(n)都是整数到正实数的函数，如果存在正整数n0和正常数c，使得对所有n≥n0，都有f(n)>cg(n)，就称f(n)的阶至少是Ω

(g(n))。准确界：函数f(n)和g(n)都是整数到正实数的函数，如果存在正整数n0和正常数c1和c2

(c1≤

c2)，使得对所有n≥n0，都有c1

g(n)≤f(n)≤c2g(n)，就称f(n)的阶至多是Θ

(g(n))。1≺loglogn≺logn≺n1/2≺n3/4≺n≺nlogn≺n2

≺2n≺n!≺2n^2多项式与非多项式；5算法理论：复杂性例：排序问题：遍历排序

：O(n2)；分组排序：O(nlogn)；多项式时间与指数时间：6计算量规模n

的近似值101001000n101001000nlogn336649966n31031061092n10241.27*10301.05*10301n！3628800101584*102567算法理论图灵（AlanMathisonTuring，1912-1954）数学家、逻辑学家、密码学家，被称为计算机科学之父、人工智能之父；师从数学家哈代；二战中有巨大贡献；图灵机；图灵奖：

姚期智（2000）7Itisn‘ttrue,butGod,wewishitwas！算法理论：复杂性图灵机与判定性问题：判定性问题：用“是”和“否”回答的问题。确定性图灵机；非确定性图灵机；（带神谕的图灵机）8

有限状态控制器1111110000000BBB1…………算法理论：复杂性P与NP问题：P：所有可以用确定性图灵机在多项式时间内求解的判定问题。NP：所有可以用非确定性图灵机在多项式时间内求解的判定问题。通俗定义：P：存在多项式时间算法的判定问题。NP：多项式时间内可以验证的判定问题。P属于NP；P=？NP2000年巴黎法兰西学院宣布：对七个“千僖年数学难题”每一个悬赏一百万美元。P=？NP为第一个难题。9算法理论：复杂性如何比较难易？Karp归约（1972）：问题A

多项式时间内转化为问题B

的特殊情况，则称A

可多项式归约于B，记为转化时间为多项式；对于A

的输入I

的回答与其对应的B

的输入f(I)一致；例：TSP归约为整数规划10算法理论：复杂性NPC（NP完全）问题：NP中最难的问题；

；可满足问题(SatisfiabilityProblem,SAT)；Cook（1971）证明了SAT问题为NPC问题。SAT：布尔变量集合：布尔式：，形如问是否存在的赋值使得f=1；计算复杂度：O(2n)；NP-hard问题：与NPC一样难或者更难的问题；11算法理论：复杂性第一个NP完全问题（Cook定理1971）可满足问题（SAT）是NP完全问题六个NP完全问题（Karp1972)3可满足问题：3SAT；图的点覆盖问题：VC；图的k

点团存在性问题：Clique；图的哈密尔顿圈问题：HC；TSP简化版；正整数集合的划分问题；背包问题简化版；三维匹配问题：3DM；更多的NP完全问题1979年：300多个；1998年：2000多个；12P=?NP（P-NP问题）；

如果，则指数灾难无法避免；P与NPC之外的NP问题，曾经的希望：线性规划问题；图的同构问题；素数判定问题；NP算法理论：复杂性13P=NP NPNPCP算法理论：复杂性如何处理NP难问题？并行计算：以硬件设备换取时间存在着很多种并行计算模型理想模型PRAM可多项式时间解NP完全问题实际中效果不好：处理器数目是受限的，现实的代价：通讯，同步，等；随机算法：判定问题：以较大概率得到正确输出；输出正确，但计算时间不定；优化问题：输出解的性能不稳定；以较大概率得到性能好的解；14算法理论：复杂性近似算法：不要最优，只求较优；时间复杂度较低；结果符合某种保证；启发式算法：基于直观或经验构造的算法，在可接受的代价下给出待解决问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计；通常利用邻域进行局部优化：邻域搜索；贪婪策略通常也属于启发式算法；模拟退火、遗传算法、人工神经网络、蚁群算法等；15组合最优化问题：集合覆盖问题例：有n

个菌株V={v1,v2,…,vn}，m

种药物每种可以抑制菌株集合为S1,S2,…,Sm，成本分别为w1,w2,…,wm，求可以抑制所有菌株的成本最小的药物组合。集合覆盖（SetCover）：输入：集合V={v1,v2,…,vn};子集S1,S2,…,Sm属于V；权重w1,w2,…,wm、或无权；目标：选出{1,2,…,m}的子集I，

需要满足；同时

最小化或|I

|；

16V={v1,v2,…,vn};Sj组合最优化问题：集合覆盖问题无权集合覆盖的贪婪算法1：1.取I

为空集；2.当V

非空的时候，任选vi，将所有包含vi的集合Sj

的序号并入I；然后将所有涉及到的vi从V

中删除；3.如果V

为空集，则停止，输出I。算法1为f近似算法（f

为vi所属子集的个数的最大值）；f

较小时效果尚可：每个菌株被少数药物抑制；无权集合覆盖的贪婪算法2：1.取I

为空集；2.当V

非空的时候，将包含未覆盖的vi最多的集合Sj

的序号并入I；然后将新覆盖到的vi从V

中删除；3.如果V

为空集，则停止，输出I。17组合最优化问题：集合覆盖问题利用线性规划的凑整算法（Rounding）xj=0,1代表是否选取Sj；xj松弛问题的解；对j=1,…,m

执行：输出凑整算法为f

近似算法：18组合最优化问题：集合覆盖问题贪婪算法；线性规划取整算法；对偶规划算法；原对偶规划算法；加权集合覆盖的贪婪算法；问题推广：抑制关系的强弱（元素与集合从属关系加权）；药物拮抗性（集合选择时考虑互斥）；放松要求（尽可能多的抑制细菌，不要求全部）；19组合最优化问题：背包问题背包问题（Knapsake）：物体集合U={u1,u2,…,un},其体积分别为整数s1,s2,…,sn

,价值分别为整数v1,v2,…,vn

,背包容量为整数C，求U的一个子集S（装背包的方案）使得：同为NP-hard问题；考虑近似算法等；松弛为LP分数形式；20组合最优化问题：背包问题背包问题的贪婪算法1：首先将物品按单位价值(vi/si)降序排列，然后按这个顺序将物品装包，直到包满或所有物品已经装完。这个算法不能得到有界近似比：贪婪算法2：211/2近似算法组合最优化问题：背包问题贪婪算法+局部优化：首先将物品按单位价值(vi/si)降序排列，然后按这个顺序将物品装包，直到包满或所有物品已经装完。

在上述结果基础上进行邻域优化？22组合最优化问题：装箱问题装箱问题（Bin-packing）：有n个大小分别为s1,s2,…,sn的物体