组合最优化——期中总结
一、基本概念：
1、组合最优化：又称为离散最优化通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。可用数学模型表述为：
min f(x)
s.t. g(x)≥0,
x ∈ D
2、组合最优化问题：在给定有限集合的所有具备某些特性的子集族中，寻找使某种指标达到最优的子集的问题。
3、组合最优化问题的目标通常是从组合问题的可行解集中求出最优解
4、算法：一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述
5、定型算法：算法从前一步到后一步的运行是由当时状态唯一确定的
6、算法能解决问题：一个算法，它对问题任意一个给定实例，在有限步之后，一定能得到该实例的答案
7、近似算法：对于一个优化问题，给定任意一个实例，算法总能找到一个可行解
8、最优算法：对于一个优化问题，给定任意一个实例，算法总能找到一个可行解，且这个可行解的目标值总等于最优解值
9、计算复杂性：用算法中的加、减、乘、除和比较等基本运算的总次数（计算时间）C（I）同实例I在计算机计算时的二进制输入数据(输入规模/长度d（I）)的大小关系：C(I) = f(d(I))
10、判定问题：一个问题的每一个实例只有“是”或“否”两种答案
11、多项式转换（变换）：通过一个算法将两个问题的两个实例之间实现了转换，使实例的解一一对应，即将输入转换为输入，并且得到的结果相对应
12、多项式归约：在多项式时间内，将问题1的输入转换为问题2的输入，则成问题1归约为问题2
13、NP难问题：对于判定问题A，若NP中的任何一个问题可在多项式时间归约为判定问题A，则称A为NP困难问题
14、cook定理的NPC证明：NP中的任何一个问题可在多项式时间内归约为SAT
15、不确定一维搜索：
对于一元函数φ(α),精确一维搜索的条件为φ ’(αk)=0
不精确一维搜索的条件φ ’(αk)≈0,或 |φ ’(αk) | ≤ σ
实际计算中上式不好控制,一般的方法是|φ ’(αk) / φ ’(0) | ≤ σ
二、问题
1、0-1背包问题
可化为：
求最大的Σcixi
条件是Σaixi≤h，即背包容量
且xi∈{0,1}，表示物体只能装入或者不装入
2、平行机排序问题
可化为：
求最小的ΣΣcijtj，tj为任务完成所需要的时间
条件是Σcij=1且Σcij=1，即每个任务仅执行一次
且cij∈{0,1}，表示任务要么执行要么不执行
3、运输问题
可化为
求最小的ΣΣcijxij
条件是Σxij=ai，即提供数量
Σxij=bj，即使用数量
xij≥0
4、生产计划问题
求最大的Σcjxj
条件是Σaijxj≤bi，即资源需要够用
xj≥dj，即不少于bj的量
5、指派问题
求最小的ΣΣcij*xij
条件是Σxij=1且Σxij=1，即每个人只负责一个任务
xij∈{0,1}，即要么负责要么不负责
三、常用算法
1、迭代算法：选取一个初始可行点，从此出发，以此产生一个可行点列
2、下降算法：在迭代算法中要求f(x+1)<f(x)
3、黄金分割法：想要求得峰值所在的区间，所以每次求得的假设区间端点是x1=a+0.382(b-a)和x2=a+0.618(b-a)，要么选择区间[a,x2]，要么是[x1,b]，要么是[x1,x2]，具体看f(x1)和f(x2)的取值，如果f(x1)<f(x2)，说明x1更靠近最低点，但由于x1不能保证在左侧还是右侧，所以选择x2，即区间变化为[a,x2]；如果f(x1)>f(x2)，说明x2更靠近最低点，但由于x2不能保证在左侧还是右侧，则选择x1，即区间变化为[x1,b]；如果f(x1)=f(x2)，说明峰值在x1和x2之间，即区间变化为[x1,x2]。直到区间长度小于精度的时候，终止。
4、fibonacci法：通过fibonacci数列逼近0.618的特性，从1，2，3开始，每次都取n1=f(n-2)/f(n)，n2=f(n-1)/f(n)作为新区间的两端，然后和黄金分割法一样进行分析。每次求得的假设区间端点是x1=a+n1(b-a)和x2=a+n2(b-a)，要么选择区间[a,x2]，要么是[x1,b]，要么是[x1,x2]，具体看f(x1)和f(x2)的取值，如果f(x1)<f(x2)，说明x1更靠近最低点，但由于x1不能保证在左侧还是右侧，所以选择x2，即区间变化为[a,x2]；如果f(x1)>f(x2)，说明x2更靠近最低点，但由于x2不能保证在左侧还是右侧，则选择x1，即区间变化为[x1,b]；如果f(x1)=f(x2)，说明峰值在x1和x2之间，即区间变化为[x1,x2]。直到区间长度小于精度的时候，终止。注意，每次需要找到下一个fibonacci数，对n1和n2进行更新。
5、进退法：
注意，进退法不是用来在单峰函数中找最小值得方法，而是在多峰函数中找到单峰区间的方法！！
通过确定步长，然后不断迈步，直到得到一个区间[x0,x2]，由于需要直到峰值在区间内，所以需要设定一个x1，让f(x1)<f(x0)且f(x1)<f(x2)。具体可以看我的另一篇博客：进退法
6、二分法：
每次将区间缩小为原来的1/2，每次取c=(a+b)/2，对f( c )求导数，
如果f ’( c )>0,则以[a,c]代替[a,b]作为新区间
如果f ’( c )<0,则以[c,b]代替[a,b]作为新区间