数学7234。优化和复杂性。(4小时)
提供理论和方法的最大化和最小化解决各种类型的问题。研究组合问题，包括混合整数规划问题(MIP);纯整数规划问题(IP);布尔编程问题;线性规划问题(LP)。主题包括n-空间的凸子集和多面体子集;LP问题与对偶LP问题的关系，对偶定理;单纯形算法和非线性函数最优性的Kuhn-Tucker条件以及网络问题，如最小成本和最大流量-最小切断。还可能涉及算法的复杂性; problem classes P (problems with polynomial-time algorithms) and NP (problems with nondeterministic polynomial-time algorithms); Turing machines; and NP-completeness of traveling salesman problem and other well-known problems.