规划模型读书笔记

规划：线性规划，非线性规划，整数规划，动态规划，目标规划，机理分析：微分方程，常微分方程，差分方程图论线性规划：1.运输问题2.指派问题：0-1规划，求解0-1规划的匈牙利算法（约束方程组的系数矩阵） 模型： s.t. 3.对偶理论和灵敏度分析 灵敏度分析:当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。4.例 投资风险和收益 要使净收益尽可能大，总体风险尽可能小，所以是一个多目标规划， 模型简化：（a）固定风险，最大化收益在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a ，使最大的一个风险，可找到相应的投资方案。这样把多目标规划变成一个目标的线性规划。(b)固定盈利水平，极小化风险 设总盈利水平大于K, (c) 对风险、收益分别赋予权重s（0 s 1）和(1 s)，s称为投资偏好系数。 非线性规划1. 对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。 2. 无约束问题 （a）一维搜索：当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：（1）试探法（“成功失败”，斐波那契法，0.618 法等）；（2）插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切线法，二分法等）。 （b）二次差值：对极小化问题，当 f (t)在a,b上连续时，可以考虑用多项式插值来进行一维搜索。它的基本思想是：在搜索区间中，不断用低次（通常不超过三次）多项式来近似目标函数，并逐步用插值多项式的极小点来逼近的最优解。3.约束极值问题 3.1二次规划问题 3.2罚函数法 罚函数法求解非线性规划问题的思想是，利用问题中的约束函数作出适当的罚函数，由此构造出带参数的增广目标函数，把问题转化为无约束非线性规划问题。4.例 飞行管理问题 整数规划1.规划中的变量（部分或全部）限制为整数时，称为整数规划。2.求解方法分类：（i）分枝定界法可求纯或混合整数线性规划。（ii）割平面法可求纯或混合整数线性规划。（iii）隐枚举法求解“0-1”整数规划：过滤隐枚举法；分枝隐枚举法。（iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。（v）蒙特卡洛法求解各种类型规划。3.分枝定界法4.0-1整数规划动态规划1. 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。2.包含要素：阶段，状态，决策，策略，状态转移方程，指标函数和最优值函数，最优策略和最优轨线，递归方程。3.建模步骤：（i）将过程划分成恰当的阶段。（ii）正确选择状态变量，使它既能描述过程的状态，又满足无后效性，同时确定允许状态集合。（iii）选择决策变量，确定允许决策集合，（iv）写出状态转移方程。（v）确定阶段指标，及指标函数的形式（阶段指标之和，阶段指标之积，阶段指标之极大或极小等）。（vi）写出基本方程即最优值函数满足的递归方程，以及端点条件。4.逆序解法框图图的左边部分是函数序列的递推计算，可输出全过程最优值，如果需要还可以输出后部子过程最优值函数序列和最优决策序列。图的右边部分是最优状态和最优决策序列的正向计算， 可输出最优策略和最优轨线多目标规划1. 求解思路（1）加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。（2）优先等级法将各目标按其重要程度不同的优先等级，转化为单目标模型。（3）有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。2. 目标规划的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋于相应的优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是min z = f (d + ,d )。其基本形式有三种：（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时min z = f (d + + d )（2）要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小，这时min z = f (d + )（3）要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时min z = f (d )对每一个具体目标规划问题，可根据决策者的要求和赋于各目标的优先因子来构造目标函数。3.目标规划的一般数学模型 4. 求解目标规划的序贯式算法其核心是根据优先级的先后次序，将目标规划问