山东财经大学
优化问题建模
马建华
优化问题建模
优化问题概述 数学规划模型 组合优化模型 优化算法介绍 评价方法

山东财经大学
优化问题建模
马建华
组合优化建模
组合优化问题概述 网络优化设计 流量安排问题 路线选择问题

山东财经大学
优化问题建模
马建华
组合优化问题概述
组合优化问题 常见的组合优化问题 组合优化问题建模方法

山东财经大学
优化问题建模
马建华
组合优化问题


有限个可行方案中选择最优方案 最优解一定存在 可行方案的个数非常多，枚举法不可行，往往是 NP-hard问题
山东财经大学
优化问题建模
马建华
组合优化问题


组合计数问题 最小费用最大流问题 最短路问题 网络设计问题 最优匹配问题 装箱问题 旅游售货员问题 车辆路径问题
山东财经大学
优化问题建模
马建华
组合优化问题建模方法
数学规划方法 图与网络优化方法 组合优化算法

山东财经大学
优化问题建模
马建华
图的基本概念
图与子图 图的连通性 图的计算机表示

山东财经大学
优化问题建模
马建华
无向图的基本概念
无向图G：一个有序二元组(N,E),记为G=(N,E) G的点集合： N=（1，2，3，4）是一个无向图 的点的集合 G 的边集合： E={eij} 且eij={ni,nj} 为 无序二元组称 ni 和 nj 为 eij 的端点，且称eij 连接点 ni和nj
返回
山东财经大学
优化问题建模
马建华
子图
图 G ( N , E ) 的子图 G ( N , E ) ：N N 和 E E ， 对 E 中任意的一条边 eij {ni , n j } ，都有 ni N 和
nj N
G 的子图，且 N N 支撑子图：G 是 N 的一个非空子集N 作为点 点导出子图 G[ N ] ：以 集、以两端点均在N 中的所有边为边集的子图 G [ E ] E E 作为边 边导出子图 ：以 的一个非空子集 集、以E 中边的所有端点作为点集的子图
1
a 2 c d
b 4 e
3
山东财经大学
优化问题建模
马建华
点边关系
关联：一条边的端点称为这条边的关联点，顶点1与边a和b 邻接：与同一条边关联的端点称为是邻接的，如点 1 和 2 ， 同时如果两条边有一个公共端点，则称这两条边是邻接 的，如边a和b。 1 b a
2
c
d 3 e
4
山东财经大学
优化问题建模
马建华
完全图：每一对点之间均有一条边相连的图 二分图 G=(N,E) ：存在的一个二分划 (S,T) ，使得 G 的每条边 有一个端点在S中，另一个端点在T中 完全二分图 G=(S,T,E)：S中的每个点与T中的每个点都相连 的简单二分图 简单图G的补图 :与G有相同顶点集合的简单图，且 G 中的两个 点相邻当且仅当它们在G中不相邻
1, 当弧aik以点i为尾 bik 1, 当弧aik以点i为头 0, 否则
山东财经大学
优化问题建模
马建华
关联矩阵示例
2 1 3 4 5 2 1 3 4
1 1 2 1 3 0 4 0 5 0
返回
1 1 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1
1 2 3 4 5 1 0 2 1 3 1 4 1 5 0 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0
2 1 5
2 4 3
1 2 3 4 1 0 2 0 3 0 4 0 1 1 0 0 1 1 0 0 0 0 1 0
♂
山东财经大学
优化问题建模
马建华
关联矩阵
简单图 G ( N , E ) 的关联矩阵：一个 | N | | E | 阶矩阵 B (bik ) ，其中 1, 当点i与边k关联 bik 0, 否则 简单有向图 G ( N , A) 的关联矩阵：一个| N | | A | 阶 B (bik ) 矩阵 ，其中
♂
山东财经大学
优化问题建模
马建华
Scilab中输入图

命令：
g = make_graph(name,directed,n,tail,head) 其中： name：图的名称，字符串‘graph1’ directes：有向无向，0-无向图，1-有向图 n：顶点个数 tail向量，各边的尾部 head向量，各边的头部
1 1 1 0 0 0 2 1 0 1 1 0 3 0 1 1 0 1 4 0 0 0 1 1
山东财经大学
优化问题建模
马建华
邻接矩阵
简单图 G ( N , E ) 的邻接矩阵：一个| N | | N | 阶矩阵 A ( a ij ) ，其中
山东财经大学
优化问题建模
马建华
例子
2
边 a b c d e f g h i 1 d 3 a c 4 e f b g 5 i
1, 当点i与点j邻接 a ij 0, 否则
| N || N | 简单有向图 G ( N , A) 的关联矩阵：一个 阶 矩阵 A (a ij ) ，其中
1, 当有弧从点i到点j a ij 0, 否则
山东财经大学
优化问题建模
马建华
邻接矩阵示例
1 3 4
返回
完全图
完全二分图
补图 G
山东财经大学
优化问题建模
马建华
有向图与网络
有向图G：一个有序二员组(Fra bibliotek,A)，记为G=(N,A) G的弧集合：A={aij}且aij={ni,nj}为有序二元组 ，若aij={ni,nj}， 则称aij从ni连向nj， ni称为aij的尾， nj为 aij的头，ni称为nj的 先辈，nj称为 ni的后继 有向图G的基本图：对于G的每条弧用一条边代替后得到的无向图 网络G：对（有向）图G的每条边（弧）都赋予一个实数，并称为 边（弧）的权，则连同它边（弧）上的权称为（有向）网络