- 最优化方法/数学规划，是运筹学的一个分支
- 怎样建立最优化问题的数学模型
- 决策变量和函数
- 约束或限制条件
- 目标函数
连续变量优化模型
线性规划
标准形式的线性规划模型
线性规划问题转为标准形式
max w=7x+12y
s.t 9x+4y<=360
4x+5y<=200
3x+10y>=300
x>0,y>0
x_4=x,x_5=y,引入松弛变量 x1,x2>=0和剩余变量x3>=0,上述问题化为
max w=7x+12y
s.t x_1+ 9x_4+4x_5=360
x2+ 4x_4+5x_5=200
-x_3+3x_4+10x_5=300
x1,x2,x3....x5>=0
- 对于不等式约束，通过引入松弛变量和剩余变量总可以化为等式约束
- 对于bi<0 的情况，在该式两边同乘以-1
- 对于自由变量(不要求取非负的值)，如x1，有两种方法
- 令x1=u1-v1,u1>=0,v1>=0
- 从约束方程之一解出x1，带入其他的约束方程及目标函数
- 考虑标准形式的线性规划问题：基本可行解
- min c^T x s.t. Ax=b,x>=0
- A的秩为m，可从A的n列中选出m列，使他们线性无关。此处我们设A的前m列线性无关，令其组成的矩阵为B
- 矩阵B是非奇异的，因此方程组 Bx_b=b，有唯一解，x_B=B-1b 其中x_B是一个m维列向量，令xT=(x_B,0)T 我们就得到一个解x
- B称为基/基底 称这样得到的x 为关于基底B的基本解，而与B的列相应的x的分量称为基本变量，当基本解中有一个或一个以上的基本变量xi为零时，则称为退化的基本解
- 当一个可行解x又是基本解，则称为基本可行解。
- 线性规划维数：变量的个数n
- 线性规划阶数：等式约束方程数目m
- 基本可行解个数不超过
C
n
m
C^m_n
Cnm
- 最优可行解：使得目标函数达到最大/小值
线性规划的基本定理
非线性规划
离散变量优化模型
- 选址问题
- 布点问题
- 指派问题
- 最优化问题的一般数学模型
- 整体最优解与局部最优解
- 优化的分类
组合优化与NP理论
- 组合最优化问题(离散最优化问题)：通过对数学方法的研究取寻找离散事件的最优编排、分组、次序或筛选等
- 特点：大多数情况下可行域为有限点集。
- 直观求解方法：枚举法
- 背包问题
- 旅行商问题TSP
- 整体线性规划问题
- 装箱问题(BP)
- 约束机器排序问题
- 衡量算法好坏看基本运算总次数(计算时间) C(I) 同实例I在计算机计算时的二进制输入数(输入规模/长度L(I))的大小来度量
- C(I) =f(L(I)) 该函数关系称为算法的计算复杂性(度)
- C(I) <=ag(L(I)) (其中a为常数) 问题规模的多项式函数为上界 ，该式成立，则称该算法为解决该问题的多项式(时间)算法
- 不存在多项式g(x)时，称相应的算法是非多项式时间算法/指数(时间)算法
- 多项式问题类P。(存在多项式算法的问题集合，计算时间存在上界)
- 非确定多项式问题类(NP)
- 背包、TSP、整数线性规划、0-1、装箱、约束机器排序
NP理论
- NP完全问题类(NPC)-一定是NP问题
- NP难问题类(NPH)-不知道是不是NP
启发式算法
图论与最短路模型
- 图的概念
- 图的矩阵表示
- 关联矩阵：横纵分别表示边与点
- 无向图 1关联 0不关联
- 有向图 1是起点，-1是终点，0 不关联
- 邻接矩阵 横纵分别表示点与点
- 无向图 1相邻 0不相邻
- 有向图 1存在，0不存在
- 有向赋权图： w存在，0：i=j，无限，不存在
最短路径及其算法
固定起点的最短路
- 路径上权值之和最小
- Dijkstra算法：求G中从固定顶点到其余顶点的最短路
每对顶点之间的最短路
图的遍历问题
边的遍历
- 欧拉图：存在欧拉回路
- G为连通无向图
- 欧拉回路：经过G的每边正好一次的巡回 必须回原点
- 欧拉道路：经过G的每边正好一次的道路
- 中国邮递员问题
点的遍历
- 哈密尔顿图
- G为连通无向图
- 哈密尔顿路径：经过G的每个顶点正好一次的路径
- 哈密尔吨圈/H圈：经过G的每个顶点正好一次的圈
- 含H圈的图称为哈密尔顿图或H图
- 旅行推销员问题
- 加权图中
- 权值最小的哈密尔顿圈称为最佳H圈
- 经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路
- 两者不一定一致
- 但如果任意三点距离满足三角边不等式，则两者一致
- 推销员问题的近似算法，二边逐次修正法
- 最佳灾情巡视路线
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
