数学建模中 NPC问题 的NPC问题
1
涉及组合优化的数学建模竞赛题
• • • • • • 美国，扫雪问题、平板车装车 1993年，足球队排名 1994年，锁具装箱问题 1997年，截断切割问题 1998年，灾情巡视路线 2000年，钢管的订购与运输
2
1990 MCM B: Snowplow Routing
13
1.2 图与网络 – 例
a5
a2 v1
a1
a3
v2
a4
v3 a6
v4
v5
图G=(V，A)，其中顶点集V= {v1 , v 2 , v3 , v 4 , v5 } 弧集A= {a1 , a 2 , a3 , a 4 , a5 , a 6 } 弧 a1 = ( v1 , v 2 ) a = ( v , v ) a = ( v , v )
•运筹学（Operatio运筹学
6
运筹数学（ 运筹数学（Mathematics of OR） ）
最优化( 最优化 数学规划)
•
连续优化(数学规划) 连续优化(数学规划)：
数学规划（线性规划、非线性规划）、非光滑优化、 数学规划（线性规划、非线性规划）、非光滑优化、 ）、非光滑优化 全局优化、 全局优化、锥优化等 • 离散优化：网络优化、组合优化、整数规划等 离散优化：网络优化、组合优化、 • 不确定规划：随机规划、模糊规划等 不确定规划：随机规划、
• 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.
10
1.1网络优化问题的例子 网络优化问题的例子
稳定婚配问题( 例 稳定婚配问题(Stable Marriage Problem) ) 假设有n个男人和 个女人 每人都希望从n个异性中选择一位 假设有 个男人和n个女人 每人都希望从 个异性中选择一位 个男人和 个女人, 自己的配偶. 假设每人都对n个异性根据自己的偏好进行了排 自己的配偶 假设每人都对 个异性根据自己的偏好进行了排 以此作为选择配偶的基础. 当给定一种婚配方案(即给每人 序, 以此作为选择配偶的基础 当给定一种婚配方案 即给每人 指定一个配偶)后 指定一个配偶 后 , 如果存在一个男人和一个女人不是互为配 但该男人喜欢该女人胜过其配偶, 偶, 但该男人喜欢该女人胜过其配偶 且该女人喜欢该男人也 胜过其配偶, 则该婚配方案称为不稳定的. 胜过其配偶 则该婚配方案称为不稳定的 安排稳定的婚配方 案的问题称为稳定婚配问题 稳定婚配问题。 案的问题称为稳定婚配问题。
11
1.1网络优化问题的例子 网络优化问题的例子
•特点： 特点： 特点 有关， （1）与图形有关，或易于用 ） 图形有关 图形方式表示 （2）优化问题：从若干可能 问题： ）优化问题 的安排或方案中寻求某种意义 下的最优安排或方案 •《网络优化》或《网络流》（Network Flows) 《网络优化》 网络流》 或《网络规划》（Network Programming) 网络规划》 • 与图论课程的联系与区别
3
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].
指派问题(Assignment Problem) 例1.4 指派问题 一家公司经理准备安排N名员工去完成 项任务，每人一项. 一家公司经理准备安排 名员工去完成N项任务，每人一项 名员工去完成 项任务 由于各员工的特点不同， 由于各员工的特点不同 ， 不同的员工去完成同一项任务时 所获得的回报是不同的. 所获得的回报是不同的 如何分配工作方案可以使总回 报最 大？
8
1.1网络优化问题的例子 网络优化问题的例子
运输问题(Transportation Problem) 例1.3 运输问题 某种原材料有M个产地，现在需要将原材料从产地运往N个 某种原材料有 个产地，现在需要将原材料从产地运往 个 个产地 使用这些原材料的工厂. 假定M个产地的产量和 个产地的产量和N家工厂的 使用这些原材料的工厂 假定 个产地的产量和 家工厂的 需要量已知， 需要量已知 ， 单位产品从任一产地到任一工厂的的运费已 那么如何安排运输方案可以使总运输成本最低？ 知，那么如何安排运输方案可以使总运输成本最低？
a 4 = (v 3 , v 4 )
a5 = (v 4 , v1 )
2
1
2
a 6 = (v 3 , v 3 )
3
2
3
14
1.2 图与网络 – 基本概念
•弧的端点(Endpoint)，尾(Tail)，头(Head)； •顶点相邻(Adjacent)，邻居(Neighbor)； •弧与顶点关联 (Incident)，出弧(Outgoing Arc)，入弧 (Incoming Arc)； •弧相邻 (Adjacent)； •环 (Loop)，孤立点(Isolated Vertex)； •图的阶(Order) •顶点的度（Degree），出度，入度，奇点，偶点 没有环、且没有多重弧的图称为简单图(Simple Graph)
4
目的：设计有效算法解决 NP困难问题 特点：条件较明确 建立不同类型的模型 针对建立的模型，设计有效的算 法进行求解
5
组 合 优 化
• 网络：数学模型、数学结构 ---- 图 网络：数学模型、 •网络优化就是研究与（赋权）图有关的最优化问题 网络优化就是研究与 赋权） 网络优化就是研究
从若干可能的安排或方案中寻求某种意义下的最优安排或方 数学上把这种问题称为（ 案，数学上把这种问题称为（最）优化 (Optimization) 问题
9
1.1网络优化问题的例子 网络优化问题的例子
中国邮递员问题(CPP-Chinese Postman Problem) 例1.5 中国邮递员问题 一名邮递员负责投递某个街区的邮件. 如何为他( 一名邮递员负责投递某个街区的邮件 . 如何为他 ( 她 ) 设计 一条最短的投递路线(从邮局出发， 一条最短的投递路线(从邮局出发，经过投递区内每条街道 至少一次，最后返回邮局) 由于这一问题是我国管梅谷 管梅谷教 至少一次，最后返回邮局)？由于这一问题是我国管梅谷教 1960年首先提出的 所以国际上称之为中国邮递员问题. 年首先提出的， 授1960年首先提出的，所以国际上称之为中国邮递员问题. 旅行商问题/货郎 货郎（ 例1.6 旅行商问题 货郎（担）问题 (TSP-Traveling Salesman Problem) 一名推销员准备前往若干城市推销产品. 如何为他( 一名推销员准备前往若干城市推销产品 . 如何为他 ( 她 ) 设 计一条最短的旅行路线(从驻地出发， 计一条最短的旅行路线(从驻地出发，经过每个城市恰好一 最后返回驻地) 这一问题的研究历史十分悠久， 次，最后返回驻地)？这一问题的研究历史十分悠久，通常 称之为旅行商问题. 称之为旅行商问题.
12
1.2 图与网络 – 定义
•定义 一个有向图 定义1.1 一个有向图(Directed Graph 或 Digraph) G是由一个 定义 是由一个 非空有限集合V(G)和V(G)中某些元素的有序对集合 中某些元素的有序对集合A(G)构成 非空有限集合 和 中某些元素的有序对集合 构成 的二元组，记为有向图G=(V(G)，A(G)). 其中 其中V(G) 称为图 称为图G 的二元组，记为有向图 ， 的顶点集(Vertex Set)或节点集 或节点集(Node Set)，V(G)中的每一个 的顶点集 或节点集 ， 中的每一个 元素称为该图的一个顶点(Vertex)或节点 或节点(Node)； A(G)称为 元素称为该图的一个顶点 或节点 ； 称为 的弧集(Arc Set)，A(G)中的每一个元素 即V(G)中某两个 中的每一个元素(即 图G的弧集 的弧集 ， 中的每一个元素 中某两个 元素的有序对) 元素的有序对 称为该图的一条从到的弧 (Arc). 在不引起混 淆的情况下，记号V(G)和A(G)中也可以省略 ，即分别记顶 中也可以省略G， 淆的情况下，记号 和 中也可以省略 点集、弧集为V和 ，而记有向图G=（ ， ） 点集、弧集为 和A，而记有向图 （V，A）. 如果对有向图G中的每条弧赋予一个或多个实数， 如果对有向图 中的每条弧赋予一个或多个实数，得 中的每条弧赋予一个或多个实数 到的有向图称为赋权有向图或有向网络, 到的有向图称为赋权有向图或有向网络 简称为网络 (Network).