一、线性规划（Linear programming,LP）
1.1简介
目标函数为线性函数，约束条件为线性等式或不等式时称此数学模型为线性规划模型。
从实际问题中建立数学模型一般有以下三个步骤：
1）根据影响因素找到决策变量；
2）由决策变量和所在达到目的之间的函数关系确定目标函数；
3）由决策变量所受的限制条件确定决策变量所要满足的约束条件。
1.2 求解方法：
1.2.1单纯形法（Simplex method）
单纯形法最早由 George Dantzig于1947年提出，单纯形就是很多超平面围成的区域。
基本思想：每次从单纯形上的一个顶点走到一个更好的顶点直到找到最小（大）值。
基本思路是：先找到一个初始的基可行解，判定其是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断优化，一直找到最优解为止。
步骤：
1）确定初始基可行解。
2）最优性检验，判断现行的基可行解是否最优。最优性检验：是指该点比周围所有的临近点要更优
3）转换基可行解，基变换。（进基变量的确定—最大减小原则，选择小于0的最小值对应变量，选择的对应变量由零增至正值时，可使目标函数值最大限度的减小.；出基变量确定-最小比值原则）
4）重复23步骤
使用单纯型法时，如果约束条件含有不等式时需新增变量（松弛变量、人工变量）转化为标准型。转化标准型可参考，【线性规划(一)】线性规划简介 - 知乎，标准型如下：
单纯形求解例题可看：
知识点：
线性规划中的约束条件描述的是一个凸集
圆形上的圆周上每点都是顶点，所以说凸集上顶点可以是有限的，也可以是无限多的
凸集的区域范围可以有界或者是无界的
基本可行解中'基'字指此时可行解基变量不全为0，而非基变量皆为0
凸集中元素x是基本可行解的充分必要条件为x是凸集的顶点
线性规划问题最值有可能是多个
单纯形法上从代数角度是寻找约束条件的每一个基本可行解，从几何意义上来说是遍历凸集的每一个顶点
单纯形法过程就是不断找出基本可行解的过程，基本可行解有一个显著的特征：基变量不为0，非基变量都为0。利用这个特性我们能够很快的找出每一个基本可行解
详细的求解方法可参考，含python代码
解的判别，唯一解，无穷多解，无界解，可参考：【运筹学】线性规划 单纯形法原理 ( 构造初始可行基 | 基变换 | 最优性检验 | 解的判别 | 检验数 | ( 唯一 / 无穷多 ) 最优解判别定理 | 无界解判别定理 )_韩曙亮的博客-CSDN博客
1.2.2 大M法
上面的单纯形例子中在引入松弛变量变成标准型后，系数矩阵A自动有一个单位矩阵，单位矩阵的阶与条件个数一致，A秩为m的Rm*n的矩阵，即A是满秩的。有时加入松弛变量后并不能得到单位矩阵，遇到这种情形时自然不能得到初始基本可行解。如下，加入松弛变量x3,x4,x5后变为等式的标准型，标准型矩阵系数A没有单位矩阵，之前算法在这里无效了，如果此时再引入两个变量x6,x7,同样的要求x6,x7>=0，这时就可以得到标准型了，x5,x6,x7是基变量,A是R3*7的满秩矩阵，x6,x7被称为人工变量。
在线性规划问题的约束条件中加人工变量构造初始可行基，要求在目标函数中相应地添加认为的M或-M为系数的项。在极大化问题中，对人工变量赋于-M作为其系数；在极小化问题中，对人工变量赋于M作为其系数，M为一任意大（而非无穷大）的正数。把M看作一个代数符号参与运算，用单纯形法求解，故称此方法为大M法。
如下目标函数，人工变量前面有系数M，且M>0,这就要求人工变最终必须为0，否则新的目标函数最值与原目标函数是不相等的，M有时也叫做惩罚系数，意味着如果人工变量不为0原函数将永远不能取得最大值。
求解步骤
应用单纯形法在改进目标函数的过程中，如果原问题存在最优解，必然使人工变量逐步变为非基变量，或使其值为零。否则，目标函数值将不可能达到最小或最大。在迭代过程中，若全部人工变量变成非基变量，则可把人工变量所在的列从单纯形表中删去，此时便找到原问题的一个初始基可行解。若此基可行解不是原问题的最优解，则继续迭代，直至所有的检验数都小于等于0，求得最优解为止。
1.2.3 内点法(Interior Point Method)
单纯形算法虽然在实际应用中非常有效，至今占有绝对优势，但在理论上它还不是多项式算法，复杂度为。于是出现了实用上也确实有效的多项式时间算法，内点法，它的计算复杂性是
，目前内点法的算法复杂度被进一步降低, 它是一种求解线性规划或非线性凸优化问题的算法。障碍函数法（Barrier Method）和原始对偶法（Primal-Dual Method）都属于内点法，详细可看内点法介绍（Interior Point Method）_dymodi的博客-CSDN博客_内点法。内点法中有一个惩罚函数，用于描述凸集。与单纯形法不同，它通过遍历内部可行区域来搜索最优解。
内点算法求解线性规划问题具有很好的效果，这是真正可用于求解实际中大规模线性规划问题的算法。
二、非线性规划（Nonlinear programming，NLP）
目标函数或约束函数是优化变量的非线性函数。根据目标函数和约束函数的不同可以分为：二次规划（目标函数有平方和形式）、几何规划（目标函数有多项式形式）。
非线性规划模型：
找一个决策向量，它满足约束条件且使一个向量函数优化，通过优化得到各目标函数最优值。
min/max
s.t.
其中，属于定义域D，满足定义域中约束条件的解为问题可行解。当优化的目标变为多个，目标个数>1,则变为多目标优化问题。目标个数>3，则为高维/超多目标问题。
在求解非线性规划问题模型的方法分类：
无约束优化方法：寻求n元函数f在n维空间上最优值点的方法。
有约束优化方法：一般非线性优化模型求解方法。可转化为若干无约束问题求解。
这里较为特殊的一维最优化方法，它是寻求一元函数在某区间上最优值点的方法。（自变量只有一个）。如，黄金分割法，切线法（牛顿法），插值法，斐波那契法，割线法等。
凸规划，和非凸规划，凸规划里局部最优即为全局最优，非凸规划，有全局最优解和局部最优解。
应用：
在经营管理，工程设计，科学研究等方向应用广泛。如，如何利用有限的人力物力财力，实现利润最大化；如何确定一个自动控制系统的参数，使得系统的工作状态最佳；
三、整数规划（一类要求变量取整数值的数学规划）
纯整数规划（Integer Programming）。要求全部变量取整数值，则称为纯整数规划，简称为整数规划。
混合整数规划（Mixed Integer Programming）。只要求部分变量取整数值，则称为混合整数规划。
线性整数规划，当在线性规划中要求变量取整数时，就是线性整数规划。
0-1整数规划。要求变量为0，1变量，即其值只取0或1时，则称为 0-1规划。
求解的方法：
- 分枝定界法—可求纯或混合整数线性规划
- 割平面法—可求纯或混合整数线性规划
- 隐枚举法—求解“0-1”整数规划：
- 过滤隐枚举法；
- 分枝隐枚举法。
- 匈牙利法—解决指派问题
- 蒙特卡洛法—求解各种类型规划
参考，含有求解方法例题：整数规划 - sgKurisu - 博客园
四、动态规划（Dynamic Programming，DP）
五、面试问题
1、讲讲分支定界法？
把全部可行解空间反复地分割为越来越小的子集，称为分支；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。
主要思路：在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。分支定界法_百度百科
步骤：先不考虑原问题的整数约束，求解相应的松弛问题（如线性规划问题，用单纯形法求得最优解）。对决策变量取整分支，对目标函数值定界。若所有子问题的目标值都差于当前整数最优解，则不需继续分枝。分枝定界法的一般步骤_Zack_Liu的博客-CSDN博客_分支定界
2、检验数含义、影子价格含义？
单纯形法检验数，是迭代后与迭代前目标函数的差值简化，如果检验数>0，说明目标函数值是增大的 , 即目标函数值还有增大的可能性 ;检验数<0 , 说明迭代后目标函数值会变小 , 即目标函数值还有减小的可能性。
影子价格：它是指依据一定原则确定的，能够反映投入物和产出物真实经济价值、反映市场供求状况、反映资源稀缺程度、使资源得到合理配置的价格。影子价格反映了社会经济处于某种最优状态下的资源稀缺程度和对最终产品的需求情况，有利于资源的最优配置。影子价格_百度百科
3、强对偶、弱对偶？
若原始问题(对偶问题)有一个确定的最优解，那么对偶问题(原始问题)也有一个确定的最优解，而且这两个最优解所对应的目标函数值相等，这就是强对偶性。 强对偶性_百度百科
在极大化线性规划问题中，如果X是原问题的任意可行解，Y是对偶问题的任意可行解，那么有CX≤Yb。这就是弱对偶性。弱对偶性_百度百科
4、拉格朗日松弛法系数怎么求？拉格朗日松弛的约束怎么选？
5、互补松弛性怎么理解?
【运筹学】对偶理论 : 互补松弛性 ( 原问题与对偶问题标准形式 | 互补松弛定理 | 互补松弛定理示例说明 )_韩曙亮的博客-CSDN博客_互补松弛性
6、讲讲列生成？
列生成算法主要用途在于求解变量多，但是大部分变量将会取值为0的线性规划问题。总体思路是先忽略大部分变量，构造一个只使用小部分变量的模型（其余变量相当于值为0），这样就能很快求出一个解。然后寻找模型外的变量，找到能够让目标值更优的变量，加入模型再次求解。重复这个过程直至找不到更好的变量。列生成算法原理(单纯形基础)_skycrygg的博客-CSDN博客_列生成
7、元启发式算法（ 遗传算法 ，邻域搜索、模拟退火等）？
各种元启发式算法（Metaheuristics）介绍_D.w_的博客-CSDN博客_元启发式算法
8、单纯形法和内点法，复杂度？
单纯形法复杂度为。内点法，它的计算复杂性是
（不一定是这样，但是是幂次的）。
9、TSP问题？
10、VRP的解法？
用遗传算法解决VRP问题_byx2000的博客-CSDN博客_vrp算法
11、P问题，NP问题，NPC问题，NP-hard问题等相关概念？
P问题(polynomial)：求解一个问题的时间复杂度是多项式级别；
NP问题(nondeterministic polynomial)：可以在多项式时间里验证解是否正确的问题。定义NP问题的意义在于，如果一个问题不能在多项式时间验证，则这个问题一定没有多项式时间的算法。
图中某条路是否是Hamilton回路，可以在多项式时间验证，是NP问题图中
是否不存在Hamilton回路，不可以在多项式时间验证。
NPC问题(nondeterministic polynomial complete)：
定义：
一个问题1）它是NP问题；2）所有的问题都可以约化到它，这样的问题称为NPC问题。
证明：
1）先证明它是NP问题；
2）再证明其中一个已知的NPC问题能约化到它（由约化的传递性，如果A能约化到B，则B的时间复杂度不低于A）。
特点：NPC问题目前没有多项式的有效解法，只能有指数级或阶乘级复杂度的算法搜索
NP-hard问题(nondeterministic polynomial - hard)：满足NPC问题的第2条但是不一定满足第1条。即使NPC问题获得了多项式级别的求解算法，NP-hard问题可能仍然找不到多项式级的算法。
12、各种排序（时间复杂度）
常见排序算法及其时间复杂度_视界IT的博客-CSDN博客_常见排序算法及时间复杂度
其它参考：
运筹优化算法工程师面试汇总_Thomas_Lee_OR的博客-CSDN博客_运筹算法工程师