1．有穷性 对于任意一组合法输入值，在 执行有穷步骤之后一定能结束，即： 算法中的每个步骤都能在有限时间内完成；
2．确定性 对于每种情况下所应执行的操 作，在算法中都有确切的规定，使算法的 执行者或阅读者都能明确其含义及如何执 行。并且在任何条件下，算法都只有一条 执行路径；
3．可行性 算法中的所有操作都必须足够 基本，都可以通过已经实现的基本操作运 算有限次实现之；
11
1.1 组合优化问题
数学模型：
min dij xij i j
(1.4) 总路长
n
s.t. xij 1.i 1, 2,L , n, j 1
(1.5) 只从城市i出来一次
n
xij 1. j 1, 2,L , n,
i 1
(1.6) 只走入城市j一次
xij s 1, 2 s n 1, s 1, 2,L , n, (1.7) 在任意城市子集中不形成回路
(1.1)总价值
n
s.t. ai xi b, i 1
xi 0,1, i 1, , n.
(1.2)包容量限制 (1.3)决策变量
其中xi
1，装第i物品 0，不装第i物品
D 0,1n.
10
1.1 组合优化问题
例2 旅行商问题（TSP,traveling salesman problem） 管梅谷教授1960年首先提出，国际上称 之为中国邮递员问题。 问题描述：一商人去n个城市销货，所有 城市走一遍再回到起点，使所走路程最 短。
最优化理论与方法
（现代优化计算方法）
1
内容
概论 递归、分治、贪心、回溯 禁忌搜索、爬山算法 模拟退火、蚁群算法 遗传算法 神经网络 元胞自动机 随机算法
2
背景
传统实际问题的特点 连续性问题——பைடு நூலகம்要以微积分为基础，且问题规模较小
传统的优化方法 追求准确——精确解 理论的完美——结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整 数规划等；排队论、库存论、对策论、决策论等。
i, js
xij 0,1, i, j 1, 2,L , n, i j.
(1.8) 决策变量
其中
dij:城市i与城市j之间的距离 , s :集合s中元素的个数，
1, 走城市i和城市j之间的路径，
xij
0，不走城市i和城市j之间的路径.
对称距离TSP : dij d ji , i, j
非对称距离TSP : dij d ji , i, j
4．有输入 作为算法加工对象的量值，通 常体现为算法中的一组变量。有些输入量 需要在算法执行过程中输入，而有的算法 表面上可以没有输入，实际上已被嵌入算 法之中；
8
1.1 组合优化问题
例1 0-1背包问题（0-1 knapsack problem）
b :背包容积 ai : 第i件物品单位体积，i 1, , n. ci : 第i件物品单位价值，i 1, , n. 问题：如何以最大价值装包？
9
1.1 组合优化问题
数学模型：
n
max ci xi i 1
传统的评价方法 算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等）
3
传统运筹学面临新挑战
现代问题的特点 离散性问题——主要以组合优化（针对离散问题，定义 见后）理论为基础 不确定性问题——随机性数学模型 半结构或非结构化的问题——计算机模拟、决策支持系 统 大规模问题——并行计算、大型分解理论、近似理论
现代优化方法 追求满意——近似解 实用性强——解决实际问题
现代优化算法的评价方法 算法复杂性
4
现代优化(启发式)方法种类
禁忌搜索（tabu search） 模拟退火（simulated annealing） 遗传算法（genetic algorithms） 神经网络（neural networks） 蚁群算法（群体（群集）智能，Swarm
15
1.1 组合优化问题
16
1.2 算法
评价算法的好坏——计算时间的多少、解的 偏离程度
先看看算法的基本概念
17
1.2 算法
1.定义. 一个有穷规则的有序集合称为一个算法。
2.算法的特征.
输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限。 可行性：执行每条指令的时间也有限。
12
1.1 组合优化问题
例3 装箱问题（bin packing） 尺寸为1的箱子有若干个，怎样用最少的 箱子装下n个尺寸不超过1 的物品，物品 集合为：{a1, a2,...an} 。
13
1.1 组合优化问题
数学模型： min B
B
s.t. xib 1, i 1, 2,L , n, b 1 n ai xib 1, b 1, 2,L , B, i 1 xib 0,1, i 1, 2,L , n; b 1, 2,L , B,
Intelligence） 拉格朗日松弛算法（lagrangean relaxation）
5
1 现代优化计算方法概述
1.1 组合优化问题 1.2 算法 1.3 计算复杂性的概念 1.4 启发式算法
6
1.1 组合优化问题
组合优化（combinatorial optimization）:解决离散问 题的优化问题——运筹学分支。通过数学方法的研究 去寻找离散事件的最优编排、分组、次序或筛选等。
数学模型：
min f (x) s.t.g(x) 0,
x D.
目标函数 约束函数 有限点集, 决策变量
7
1.1 组合优化问题
组合优化问题的三参数表示：
(D, F, f ) D :决策变量定义域
F x | x D, g(x) 0,可行域,有限点集
f :目标函数 x F :可行解（点）
x : 最优解，如果x F, f (x) minf (x) | x F.
其中 B : 装下全部物品需要的箱子， 1, 第i物品装在第b个箱子，
xib 0，第i物品不装在第b个箱子.
14
1.1 组合优化问题
例4 约束机器排序问题（bin packing） n 个加工量为{di|i = 1, 2, ⋯, n} 的产品在
一台机器上加工,机器在第t个时段的工作 能力为ct , 求完成所有产品加工的最少时 段数。