max cT x
s Z n
c为n维列向量，A为m×n矩阵、b为m 维列向量，x 为n维决策变量，Zn表示n 维整数向量的集合 系数A、b和c的元素都是整数
• 例1.1.2和1.1.3的数学模型都具有(IP) 的形式 •一些组合优化问题可以写成整数线 性规划问题 •IP与LP形式非常相似，不同之处是 前者的决策变量部分或全部取整数
包的能力限制
(1.2)
xi
i=1
∈ {0,1},
i
=
1,",
xi＝1:装第i个物品
n
(1.3)
D={0,1}n，F为D中满足(1.2)的可行解．f为目标函数
例1.1.2 旅行商问题 (TSP，traveling salesman problem)
一个商人欲到n个城市推销商品，每两 个城市i和j之间的距离为dij，如何选择 一条道路使得商人每个城市走一遍后 回到起点且所走路径最短 TSP还可以细分为: 对称(dij =dji)和非对称距离两大类问题
决策变量
t = 1,",T
(1.12)
xit＝1表示第t时段加工产品i 、T:时段数
组合优化问题的表示形式
• 组合优化问题通常可以用整数规划模型 的形式表示，如例1.1.1和1.1.2
• 有些组合优化问题用IP模型表示则比较 复杂且不易被理解，不如对问题采用直 接叙述更易理解，如例1.1.2,1.1.4和1.1.5
1．1 组合最优化问题
1.组合最优化(combinatorial optimization) 是通过对数学方法的研究去寻找离散事 件的最优编排、分组、次序或筛选等， 是运筹学中的一个经典且重要的分支， 所研究的问题涉及信息技术、经济管理、 工业工程、交通运输、通信网络等诸多 领域
2.该问题可用数学模型描述为：
对 一般的TSP
∑ min dij xij i≠ j
n
∑ s.t. xij = 1, j =1
n
∑ xij = 1,
i =1
(1.4)
从城市i出来1次
i = 1,2,", n
走入城市j只1次
j = 1,2,", n
∑ xij ≤| s | −1, 2 ≤| s |≤ n − 2,
i, j∈s
s ⊂ {1,2,", n}, 城市子集 xij ∈{0,1}, i, j = 1,", n, i ≠ j xij=1:经过城市i→j的路径
minT
(1.9) 加工所用的时段数最少
T
∑ s.t.
xit = 1, i = 1,2 ,", n (1.10)
t=1 产品i一定在某个时段加工
n
∑ di xit ≤ ct , t = 1,2 ,",T (1.11)
i=1
每个时段的加工量不超过能力的限制
xit ∈{0,1}, i = 1,", n;
•这些算法涉及生物进化、人工智能、数 学和物理科学、神经系统和统计力学等概
念 •都是以—定的直观基础而构造的算法， 也称之为元启发式算法(meta-heuristics) •启发式算法的兴起与计算复杂性理论的 形成有密切的联系 •现代优化算法自80年代初兴起，至今发 展迅速
•这些算法同人工智能、计算机科学和运 筹学相融合
例1.1.2的非对称距离TSP问题耗时
• 可以用另一个方法来表示它的可行解： 用n个城市的—个排列表示商人按这个排 列序推销并返回起点
• 若固定一个城市为起终点，则需要 (n—1)！个枚举
• 设计算机1秒可以完成24个城市所有路径 枚举为单位
(1.5) (1.6)
(1.7) (1.8)
共n×(n-1)个决策变量 D={0,1}n× (n-1)
一条回路是由k(1≤k ≤ n)个城市和k条弧 组成，因此，(1．7)约束旅行者在任何一 个城市真子集中不形成回路，其中|S|表 示集合S中元素个数
例1.1.3 整数线性规划 (integer linear programming)
现代优化计算方法
第一章 概 论
现代优化算法包括:
• 禁忌搜索(tabu search) • 模拟退火(simulated annealing) • 遗传算法(genetic algorithms) • 蚁群优化(ant colony optimization algorithm) • 人工神经网络(artificial neural networks) • 拉格朗日松弛等算法
例1.1.1 0-1背包问题(knapsack problem)
设有一个容积为b的背包，n个尺寸分别为
ai(i＝l,2,…,n)，价值分别为ci(i＝1,2,…,n)的 物品，如何以最大的价值装包?
n
∑ max ci xi (1.1) 包内所装物品的价值最大
i =1
∑ s.t.
n
ai xi ≤ b
min f(x) s.t. g(x)≥ 0 ,
x∈D 其中，f(x)为目标函数，g(x)为约束函 数，x为决策变量， D为决策变量的定
义域 3.一个组合最优化问题可用三参数(D， F，f)表示，F={x|x ∈D, g(x)≥ 0}表示可 行解集, 为有限点集，D通常也为有限点 集，f表示目标函数
4.满足f(x*)＝min{f(x) | x∈F}的可行解 x*称为该问题的最优解． 5.组合最优化的特点是可行解集合为 有限点集 6.例
例1.1.4 装箱问题(bin packing)
设有n个一维尺寸不超过１的物品集合{a1, a2,…, an},如何以个数最少的一维尺寸为 １的箱子装进这n个物品？（一维装箱问 题）
例1.1.5约束机器排序问题 (capacitated machine scheduling)
n个加工量为{ di | i ＝l，2，…，n}的 产品在一台机器上加工，机器在第t 个时段的工作能力为ct ，求完成所有 产品加工的最少时段数
• 根据对解的精度要求和分析的需要，有 大量的组合优化问题是通过文字语言叙 述的
1．２计算复杂性的概念
• 计算复杂性的概念是为评估算法的计算 耗时和解的偏离程度等指标而提出的
• 这套理论产生于70年代 • 是评估算法的基础
计算耗时的实例
• 每一个组合最优化问题都可以通过枚举 的方法求得最优解
• 枚举是以时间为代价的，有的枚举时间 还可以接受，有的则不可能接受