数学建模中的NP问题.pptVIP

涉及组合优化的数学建模竞赛题 美国，扫雪问题、平板车装车 1993年，足球队排名 1994年，锁具装箱问题 1997年，截断切割问题 1998年，灾情巡视路线 2000年，钢管的订购与运输 1990 MCM B: Snowplow Routing The solid lines of the map (see Figure 1) represent paved two-lane county roads in a snow removal district in Wicomico County, Maryland [figure omitted]. The broken lines are state highways. After a snowfall, two plow-trucks are dispatched from a garage that is about 4 miles west of each of the two points (*) marked on the map. Find an efficient way to use the two trucks to sweep snow from the county roads. The trucks may use the state highways to access the county roads. Assume that the trucks neither break down nor get stuck and that the road intersections require no special plowing techniques. 1988 B - Packing Railroad Flatcars Two railroad flatcars are to be loaded with seven types of packing crates. The crates have the same width and height but varying thickness (t, in cm) and weight (w, in kg). Table 1 gives, for each crate, the thickness, weight, and number available [table omitted]. Each car has 10.2 meters of length available for packing the crates (like slices of toast) and can carry up to 40 metric tons. There is a special constraint on the total number of C_5, C_6, and C_7 crates because of a subsequent local trucking restriction: The total space (thickness) occupied by these crates must not exceed 302.7 cm. Load the two flatcars (see Figure 1) so as to minimize the wasted floor space [figure omitted]. 目的：设计有效算法解决NP困难问题特点：条件较明确 1.4 计算复杂性的概念 TSP (Traverling Salesman Problem)等许多问题至今没有找到多项式时间算法,但尚未证明其不存在 定义1.5 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问题集记为P(Polynomial). 同样道理, 可以定义强多项式问题,伪多项式问题等. TSP是否存在多项式时间算法? ---- 这是21世纪数学和计算机科学的挑战性问题之一 1.4.3 多项式问题 网 络 优 化 第 1 章 概 论 (第2讲) Network Optimization 1.5 NP,NPC和NP-hard概念(计算复杂性理论） 运筹学的ABC -- A2B2C2 （至少是组合优化、理论计算机科学的ABC） Approximation Algorithm (近似算法)；Heuristic Branch and Bound （分枝定界） Computational Complexity （计算复杂性） 口莫开，开口常说错。 ＮＰ理论在监督， 众目睽睽难逃脱。 计