赋以一个有理数 f (I, σ). 则实例I的最优解为这样一个可行解 σ* ∈ S(I) ,它使得对于所有σ∈S（I），都有
f (I, σ*) ≤ f (I, σ) （f (I, σ*) ≥f( I, σ)）。
§1.1 组合优化问题与算法 组合优化的数学模型：
Min f(x) s.t. g(x) ≥0
x ∈D
其中x为决策变量 f(x) 为目标函数 g(x)为约束函数
D为决策变量的定义域， D为有限集合。
F={x|x ∈D, g(x) ≥0}——可行域
所以，可由（D，F，f ） 定义一个组合优化问题。
组合优化的描述方法： 1°数学模型（规划模型）
2°文字语言叙述
§1.1 组合优化问题与算法
问题： 一类实际问题的数学模型的总称，如TSP 、LP etc.
否则
i, j ? 1 ~ n i? j
? min
d ij xij
i? j
n
? s.t.
xij ? 1 i ? 1 ~ n
j?1
n
? xij ? 1 j ? 1 ~ n
i?1
为了减少 变量个数
(1)
1
2
(2)
5
? xij ? s ? 1 2 ? s ? n ? 2 s ? ?1,2,? ? n?
(3)
组合优化总存在最优算法，但它以时间为代价
返回
§1.2 计算复杂性问题 在广泛的意义下，执行算法的效率是用执行算法所 用的全部计算资源的多少来衡量 (时间、空间 ),但通常 用时间作为衡量标准，这就是计算 (时间)复杂性问题 .
讨论TSP 问题 设有n个城市(有向图)则有(n-1 )！种可能方案。以计 算机1秒可以完成 24个城市所有路径枚举为单位，则
城市数 24 25 26 27 28 29 30 31
计算时间 1s 24s 10min 4. 3h 4.9d 136.5d 10.8y 325y
4
? ?
C ?? 26 28 7 ??
3. 可以使用穷举法， 但是以时间为代价
贪婪解的结果：
最差解的结果： 3+10+7=20
28+5+1=34
§1.1 组合优化问题与算法
Example 2 背包问题 （KP，Knapsack Problem ）共有27种
假设有人要出发旅行,他考虑要带
可能
7种物品（每件物品的重量与价值如
i, j? s
作用是什么
§1.1 组合优化问题与算法
Note：条件(1)，(2)表示每个城市经过一
次，但不能保证它可行，要求局部不构成
圈，条件(3)就是为了约束这一点。
为什么？
? xij ? s ? 1 2 ? s ? n ? 2 s ? ?1,2,? ? n?
i, j? s
若 |s|=n 则由n个点构成的一个回路是可行方案。 | S |? n ? 1 因为 由前面两个约束条件的限制，不可能
第一章 组合优化问题和计算复杂性
§1.1 组合优化问题与算法 §1.2 计算复杂性问题 §1.3 启发式算法
§1.1 组合优化问题与算法
Example 1 婚姻问题
共有3!=6种 可能
(matching problem )
女儿 追求者
A
3D
5
26
B
10
27 28
E
C
4 7
1
F
如何嫁娶， 使获得的礼 品最多？
遗传算法是随机性算法。
§1.1 组合优化问题与算法
最优算法： 对于一个极小化（极大化）优化问题 π， 如果给定任意一个实例 I，算法A总能找到一个可 行解σ* ∈ S(I) 。 使得 f(I, σ*) ≤ f(I, σ) （f(I, σ*) ≥f(I, σ) ）
启发式算法 （近似算法，在§ 1. 3节中介绍）
得到分配矩阵：
DE F
A ? 3 27 1?
C
?
B
? ?
5
10
4??
C ??26 28 7??
§1.1 组合优化问题与算法
婚姻问题的数学模型 ：
设：
?1 如果第i个人嫁第 j个人
xij ? ??0
否
33
?? Max z ?
cij xij
i?1 j ?1
3
? s.t.
xij ? 1 j ? 1,2,3
实例： （一个问题中总包含了若干个参数）对问题给定一组 参数所得到的例子。
算法： 一个科学的计算过程，指一步步求解问题的通用程 序，它是解决问题的程序步骤的一个清晰描述。
Note： 算法是相对问题而言的，不单单是针对问题的某个实例。
确定性算法： 如果算法从前一步到后一步的运行是由 当时状 态唯一确定的 如：单纯形法，表上作业法。
i?1
i, j ? 1 ~ 3
3
? .
xij ? 1 i ? 1,2,3
j?1
§1.1 组合优化问题与算法
最优解的结果：
Note：
27+4+26=57
1. 贪婪（Greedy) 解 一般不会产生最差 解；
2. 在某些模型中, 贪 婪算法能得到最优 解；EFGA ? 3 2 Nhomakorabea 1 ?
C
?
B
? ?
5
10
由 n-1个点构成回路而留一个点在外面 。
??
x ij ? 1
i? S j? S
§1.1 组合优化问题与算法
? 共同特点：可行方案是有限的 ——组合优化问题
Definition 1 组合优化问题π是一个极小化（或极大化）
的问题，它是由以下三部分组成 ： （1）实例集合 ； （2）对每个实例 I，有一个有穷的可行解集合 S（I） (3) 目标函数 f，它对于每个实例I和每个可行解σ ∈ S（I），
12 12 9 15 90 26 112
§1.1 组合优化问题与算法
共有
Example 3 旅行商问题（ TSP ,Travelling Salesman Problem（)n-1)!
一个商人要到 n
种可能
座城市去做生意，
City 5
设两个城市 i 和j 之
City 1
City 4
间的距离为 dij.如何
表）现在假设他最多带35 kg 物品， 物品
问：该带哪几件物品总价值最大？
1
设：
2
?1 如果带第 j种物品
3
xj
?
? ?
0
否 7
j ?1~ 7 4
5
? Max z ? c j x j
6
j ?1 7
7
? s.t.
a j x j ? 35
j?1
重量 aj(kg)
3 4 3 3 15 13 16
价值 c j
选择一条道路使得
商人每个城市走一
遍后回到起点且所
City 2
City 3
走路程最短
TSP 可分为：对称（dij=dji) 和非对称(dij ≠ dji)距离两种
§1.1 组合优化问题与算法 共有多少
TSP 问题的数学模型 ：
变量？
n(n-1)
设：
?1 表示回路通过第i个城市到第j个城市的边
xij ? ??0