2018年12月12日下午，应K8凯发邀请中国科K8凯发数学与系统科学研究院胡旭东研究员在中财大厦二层报告厅做了题为“运筹学–组合优化方法”的学术报告并与K8凯发教师交流🤞🏻。

胡旭东🎓，中国科K8凯发数学与系统科学研究院研究员👨‍👧，中国运筹学会理事长。1985年毕业于清华大学🙊，获应用数学专业学士学位👌🏻，1989年毕业于中国科K8凯发应用数学研究所，获运筹与控制论专业博士学位。自1989年始，一直在中科院从事运筹学的理论研究和教学工作，主要研究方向为组合优化、近似算法、网络博弈🖐🏻。

运筹学是自二十世纪三四十年代发展起来的一门交叉学科。它主要研究人类对各种资源的运用及筹划活动🤸，以期了解和发展其中蕴含的数学规律和计算方法，发挥出有限资源的最大效益，达到总体最优的目标。胡老师通过介绍和分析实际生活中的若干经典组合优化问题，讲解现代运筹学的研究方法🕙，并分享运筹学的教学经验。

胡老师首先概述了运筹学的发展历史，从宏观的角度给出了现代运筹学的研究方法，将其概括为“模型——理论——算法”三个部分。接着通过实际生活中的一个具体问题🛌🏿，将运筹学研究的方法进行了详尽分析说明。

模型👩🏿‍🦲🧑🏽‍🍳：胡老师通过一个实际生活中的例子，交通路口安装探头问题，建立了相应的数学模型，将这个实际生活中的问题转化成图论领域中的最小顶点覆盖数问题。又在之后的讲解中进一步根据实际需要，不同路口需要安装探头数目或者价格不同，将问题转化成更为一般的最小赋权顶点覆盖问题👨‍🎤。

理论：计算复杂性理论是当前计算机界和数学界最核心的理论之一📫。千禧年七大问题之一的P与NP问题便是计算复杂性理论中的尚未解决的最关键问题。胡老师简单概述了计算复杂性理论，P与NP问题🧏🏻‍♂️👨🏽‍🎨，并且指出最小顶点覆盖数问题是非常著名的NP-C问题之一🖌。这意味着如果最小顶点覆盖数问题具有多项式时间的精确算法，则P等于NP,反之，则P不等于NP，从而说明了多项式时间内精确求解最小顶点覆盖数问题基本是不可能完成的任务🕒👩🏻‍🦽‍➡️。

算法：既然精确求解最小顶点覆盖数问题是不可能的，只能退而求其次寻求近似算法🧎‍➡️。胡老师讲解了多种求解最小顶点覆盖数问题的近似算法，包括贪婪算法，基于最大匹配的算法，整数规划算法，随机算法等等🫳🏼，并且对于每一种算法，从理论上进行了相应的分析：举出一个具体例子，说明贪婪算法的近似比可能很差🙆🏽👩🏿‍🎨，数学证明了基于最大匹配的算法和整数规划算法都是2-近似算法，随机算法是期望意义下的2-近似算法等等。

最后👩🏻‍🔧🧒，胡老师又简要介绍了在线算法，举了实际生活中的股票问题🚣🏻‍♀️，滑雪问题加以说明💨⚂，并和现场老师们进行了有趣的互动。胡老师的报告内容丰富🧑🏽‍🦲，深入浅出✮，讲解幽默生动🥿，受到了K8凯发老师们的广泛好评。