运筹与优化模型资料整理
1. 数学模型是可以详细地描述为对于现实世界的一个特定对象，为了一个特定的目的，根据特有的内在规律，作出一些必要的简化假设，运用适当的数学工具得到的一个数学结构。 （1）建模没有唯一正确的答案。模型没有绝对的对与错，评价的唯一标准是实践检验。 （2）有不同的建模方法。比较常见的是机理分析法、测试分析法、计算机模拟法等，要按照某种确定的准则在某一类模型中选出一个与数据拟合得最好的模型。 （3）模型与建模目的有关。在建立数学模型之前要明确目的，对于同一个实际对象，建模的目的不同将导致建模时考虑的出发点和侧重点都不同，当然作出的模型就不同。 （4）模型具有可移植性。模型是现实对象抽象化、理想化的产物，因此它并不为对象的所属领域所独有，它可以移植到其它领域，描述其它的实际问题。 （5）建模与建模者的灵性、经验和数学素质有关。
数学建模过程是有一定阶段性的。我们对现实世界的问题进行分析、提炼，用数学语言做出描述，用数学方法进行分析、研究，最后回到现实世界，应用于解决、解释实际问题。一般来讲，建模的流程可描述为：问题分析、数据处理、建立数学模型、模型分析与检验。 2. 港作拖轮费用数据处理 （1）营运费用的综合分类。 （2）数据可比性处理。 （3）数据有效性处理。
3. 为了把握模型的整体结构，我们所做的工作如下：
a. 找出与问题有关的各实体（对象）。 b. 列出与每个实体有关的因素（属性）。
c. 按建模目的描述出个实体之间的关系，根据合理的假设略去影响不大的实体。
d. 将实体之间的关系用实体的因素表示出来，即建立数学关系式。
e. 如果满足关系的解有多个，则应考虑合理的评价标准求出最优解。
f. 对模型加以检验、分析和评价。 4. 设备更新问题的数学模型
劣化数值法模型、最小平均成本法更新模型、最大总收益法、效益分析法、费用方程法更新模型、MAPI 法更新模型。①T =sqrt （2k 0/入）T 为经济使用寿命k 0为设备原值入为各种影响因素的费用低劣化增长速度③y (t )=y1(t )-y2(t )- k 0分别为设备t 年内的总收益函数、总收入函数、总维持费用函数 5. 最优价格模型
为使利润U(P)达到最大，可令dU/dP=0，即可求得p*，p = p*时，DR/dP= Dc/dP，在数量经济学中，DR/dP称为边际收入，它是价格变动一个单位时，收入的改变量；Dc/dP是边际成本，他是价格变动一个单位时成本的改变量。结论：最优经济效益在边际收入等于边际成本时达到。
整个供销过程中，q 不变，需求函数为f (p )=a -bp ，试制定一个不变的最优价格：代入得U (p )=(p -q )(a -bp ) ，容易得到最优价格为p *=(a +bp )/2b 6. 泛函
变分法：求泛函极值的方法
欧拉方程作用：转换作用，将原来的泛函极值问题转换为求普通函数的极值问题。欧拉方程是泛函极值的必要条件，只要解出欧拉方程，就可以得到泛函的极值。 7. 灵敏度分析
在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。 8. 整数规划 1、分支定界法：适用于纯整数规划问题和混合整数规划问题。设有最大化的整数规划问题A 与它相应的线性规划问题B 。从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数比为A 的最优目标函数Z*的一个下界Z ，分支定界法就是将B 的可行域分成子区域的方法，逐步减小上界和增大下界，最终得到Z*。
2、割平面法。不考虑变量x i 是整数这一条件，但增加线性约束条件使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解，使切割后最终得到这样的可行域。
3、穷举法。适合0-1整数规划，检查变量取值为0或者1的每一种组合，比较目标函数值以求得最优解，需要检查变量取值的各个组合。 分支定界法适用于解决纯整数规划和混合整数规划问题，其基本思想是将整数规划转化为线性规划问题，如果其最优解不符合整数条件，则求出整数规划的上下界，增加约束条件的办法，把可行域分成若干子区域，再求解子区域上的线性规划问题，不断缩小整数规划的上下界，最后得到整数规划的最优解。
割平面法适用于解决纯整数规划问题。
我们将求解的整数规划问题称为A ，将与其相对应的线性规划问题称为B ：
第一步：求解问题B ，可得以下情况之一： 1. B 没有可行解，则A 也没有可行解，求解过程停止。
2. B 有最优解，且符合问题A 的整数条件，则B 的最优解即为A 的最优解，求解过程停止。 3. B 有最优解，但不符合A 的整数条件，记其目标函数值为z1。 第二步：确定A 的最优目标函数值z*的上下界，其上界即为z1, 再用观察法找到A 的一个整数可行解，求其目标函数值作为z*的下界，记为z 。
第三步：判断是否等于z 。若相等，则整数规划最优解即为其目标函数值等于z 的A 的那个整数可行解；否则进行第四步。
第四步：在B 的最优解中选一个最远离整数要求的变量，不妨设此变量为xj ，以[bj ]表示小于bj 的最大整数，构造以下两个约束条件，并加入问题B ，得到B 的两个分枝B1和B2。 xj ≤[bj ]和xj ≥ [bj ]+1 第五步：求解B1和B2 。修改A 问题的最优目标函数值z*的上下界， 和z 。
第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z 者，则剪掉这枝（用打Х表示），即以后不再考虑了。若大于，则不符合整数条件，则重复第三步至第六步，直至=z，求出最优解为止。
对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。
9. 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法 基本步骤：编码（产生初始种群）、适用度函数、遗传算子（选择交叉变异）、运行参数
特点：①群体搜索，易于并行化处理②不是盲目穷举，而是启发式搜索③适用度函数不受连续、可微等条件的约束，适用范围广
搜索机制：遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每一次迭代中都保留一组候选解，并按某种指标从候选解中选取较优的个体，利用遗传算子（选择、交叉、变异）对这些个体进行组合，产生新一代候选解
三种主要操作：选择、交叉、变异。遗传算法使用选择运算来实现对种群中的个体进行优胜劣汰的操作，适用度高的个体被遗传到下一代群体中的概率大，适用度低的个体被遗传到下一代群体中的概率小，选择操作的任务就是按某种方法从父代个体中选取一些个体，遗传到下一代群体；交叉运算是遗传算法区别于其它算法的重要特征，是产生新个体的主要方法；变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。
10. 启发式算法是一种具有全局优化性能、通用性强且适合于并行处理的算法。优点①有可能比简化数学模型解的误差小②对有些难题，计算时间可接受③可用于某些最优化算法之中的估界④直观易行⑤速度较快⑥程序简单易修改缺点①不能保证求得全局最优解②解的精度不稳定，有时好有时坏③算法设计与问题、设计者经验、技术有关，缺乏规律性④不同算法之间难以比较
11. 线性规划模型的基本结构是目标函数与约束条件。目标函数就是决策者要求达到的目标的数学表达式，是一个极值问题，其形式是一个线性函数。约束条件是指实现目标的资源和内部、外部条件的限制因素，其数学形式是一组线性等式或不等式。四个特征①目标最大化②约束为等式③决策变量均非负④右端项非负 12. 运输问题数学模型的约束矩阵特点：①对应于变量x ij 的系数向量Pij 中除第i 个和第m+j个为1以外，其余的都为0②系数矩阵的秩小于等于m +n -1③是m +n 阶的方阵
13. 求最大支撑树方法破圈法①在给定赋权的连通图上任找一个圈②在所找的圈中去掉一个权数最小的边③如果余下的图已不包含圈，则计算结束，所余下的图即为最大支撑树，否则返回①避圈法①在给定图上找权值最小的边并标记②继续找未标记的权数最小的边，与标记过的边不构成圈即可③如果所有点都连通且再任意标记一条边都会构成圈，则结束算法，否则返回② 1. 数学模型是可以详细地描述为对于现实世界的一个特定对象，为了一个特定的目的，根据特有的内在规律，作出一些必要的简化假设，运用适当的数学工具得到的一个数学结构。 （1）建模没有唯一正确的答案。模型没有绝对的对与错，评价的唯一标准是实践检验。 （2）有不同的建模方法。比较常见的是机理分析法、测试分析法、计算机模拟法等，要按照某种确定的准则在某一类模型中选出一个与数据拟合得最好的模型。 （3）模型与建模目的有关。在建立数学模型之前要明确目的，对于同一个实际对象，建模的目的不同将导致建模时考虑的出发点和侧重点都不同，当然作出的模型就不同。 （4）模型具有可移植性。模型是现实对象抽象化、理想化的产物，因此它并不为对象的所属领域所独有，它可以移植到其它领域，描述其它的实际问题。 （5）建模与建模者的灵性、经验和数学素质有关。
数学建模过程是有一定阶段性的。我们对现实世界的问题进行分析、提炼，用数学语言做出描述，用数学方法进行分析、研究，最后回到现实世界，应用于解决、解释实际问题。一般来讲，建模的流程可描述为：问题分析、数据处理、建立数学模型、模型分析与检验。 2. 港作拖轮费用数据处理 （1）营运费用的综合分类。 （2）数据可比性处理。 （3）数据有效性处理。
3. 为了把握模型的整体结构，我们所做的工作如下：
a. 找出与问题有关的各实体（对象）。 b. 列出与每个实体有关的因素（属性）。
c. 按建模目的描述出个实体之间的关系，根据合理的假设略去影响不大的实体。
d. 将实体之间的关系用实体的因素表示出来，即建立数学关系式。
e. 如果满足关系的解有多个，则应考虑合理的评价标准求出最优解。
f. 对模型加以检验、分析和评价。 4. 设备更新问题的数学模型
劣化数值法模型、最小平均成本法更新模型、最大总收益法、效益分析法、费用方程法更新模型、MAPI 法更新模型。①T =sqrt （2k 0/入）T 为经济使用寿命k 0为设备原值入为各种影响因素的费用低劣化增长速度③y (t )=y1(t )-y2(t )- k 0分别为设备t 年内的总收益函数、总收入函数、总维持费用函数 5. 最优价格模型
为使利润U(P)达到最大，可令dU/dP=0，即可求得p*，p = p*时，DR/dP= Dc/dP，在数量经济学中，DR/dP称为边际收入，它是价格变动一个单位时，收入的改变量；Dc/dP是边际成本，他是价格变动一个单位时成本的改变量。结论：最优经济效益在边际收入等于边际成本时达到。
整个供销过程中，q 不变，需求函数为f (p )=a -bp ，试制定一个不变的最优价格：代入得U (p )=(p -q )(a -bp ) ，容易得到最优价格为p *=(a +bp )/2b 6. 泛函
变分法：求泛函极值的方法
欧拉方程作用：转换作用，将原来的泛函极值问题转换为求普通函数的极值问题。欧拉方程是泛函极值的必要条件，只要解出欧拉方程，就可以得到泛函的极值。 7. 灵敏度分析
在实际生产过程中，上述三类因素均是在不断变化的，如果按照初始的状况制订了最佳的生产计划，而在计划实施前或实施中上述状况发生了改变，则决策者所关心的是目前所执行的计划还是不是最优，如果不是应该如何修订原来的最优计划。更进一步，为了防止在各类状况发生时，来不及随时对其变化作出反应，即所谓“计划不如变化快”，企业应当预先了解，当各项因素变化时，应当作出什么样的反应。 8. 整数规划 1、分支定界法：适用于纯整数规划问题和混合整数规划问题。设有最大化的整数规划问题A 与它相应的线性规划问题B 。从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数比为A 的最优目标函数Z*的一个下界Z ，分支定界法就是将B 的可行域分成子区域的方法，逐步减小上界和增大下界，最终得到Z*。
2、割平面法。不考虑变量x i 是整数这一条件，但增加线性约束条件使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解，使切割后最终得到这样的可行域。
3、穷举法。适合0-1整数规划，检查变量取值为0或者1的每一种组合，比较目标函数值以求得最优解，需要检查变量取值的各个组合。 分支定界法适用于解决纯整数规划和混合整数规划问题，其基本思想是将整数规划转化为线性规划问题，如果其最优解不符合整数条件，则求出整数规划的上下界，增加约束条件的办法，把可行域分成若干子区域，再求解子区域上的线性规划问题，不断缩小整数规划的上下界，最后得到整数规划的最优解。
割平面法适用于解决纯整数规划问题。
我们将求解的整数规划问题称为A ，将与其相对应的线性规划问题称为B ：
第一步：求解问题B ，可得以下情况之一： 1. B 没有可行解，则A 也没有可行解，求解过程停止。
2. B 有最优解，且符合问题A 的整数条件，则B 的最优解即为A 的最优解，求解过程停止。 3. B 有最优解，但不符合A 的整数条件，记其目标函数值为z1。 第二步：确定A 的最优目标函数值z*的上下界，其上界即为z1, 再用观察法找到A 的一个整数可行解，求其目标函数值作为z*的下界，记为z 。
第三步：判断是否等于z 。若相等，则整数规划最优解即为其目标函数值等于z 的A 的那个整数可行解；否则进行第四步。
第四步：在B 的最优解中选一个最远离整数要求的变量，不妨设此变量为xj ，以[bj ]表示小于bj 的最大整数，构造以下两个约束条件，并加入问题B ，得到B 的两个分枝B1和B2。 xj ≤[bj ]和xj ≥ [bj ]+1 第五步：求解B1和B2 。修改A 问题的最优目标函数值z*的上下界， 和z 。
第六步：比较和剪枝。各分枝的最优目标函数值中若有小于z 者，则剪掉这枝（用打Х表示），即以后不再考虑了。若大于，则不符合整数条件，则重复第三步至第六步，直至=z，求出最优解为止。
对于求目标函数值最小的整数规划的求解步骤与上述步骤基本相似。
9. 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法 基本步骤：编码（产生初始种群）、适用度函数、遗传算子（选择交叉变异）、运行参数
特点：①群体搜索，易于并行化处理②不是盲目穷举，而是启发式搜索③适用度函数不受连续、可微等条件的约束，适用范围广
搜索机制：遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每一次迭代中都保留一组候选解，并按某种指标从候选解中选取较优的个体，利用遗传算子（选择、交叉、变异）对这些个体进行组合，产生新一代候选解
三种主要操作：选择、交叉、变异。遗传算法使用选择运算来实现对种群中的个体进行优胜劣汰的操作，适用度高的个体被遗传到下一代群体中的概率大，适用度低的个体被遗传到下一代群体中的概率小，选择操作的任务就是按某种方法从父代个体中选取一些个体，遗传到下一代群体；交叉运算是遗传算法区别于其它算法的重要特征，是产生新个体的主要方法；变异是指依据变异概率将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。
10. 启发式算法是一种具有全局优化性能、通用性强且适合于并行处理的算法。优点①有可能比简化数学模型解的误差小②对有些难题，计算时间可接受③可用于某些最优化算法之中的估界④直观易行⑤速度较快⑥程序简单易修改缺点①不能保证求得全局最优解②解的精度不稳定，有时好有时坏③算法设计与问题、设计者经验、技术有关，缺乏规律性④不同算法之间难以比较
11. 线性规划模型的基本结构是目标函数与约束条件。目标函数就是决策者要求达到的目标的数学表达式，是一个极值问题，其形式是一个线性函数。约束条件是指实现目标的资源和内部、外部条件的限制因素，其数学形式是一组线性等式或不等式。四个特征①目标最大化②约束为等式③决策变量均非负④右端项非负 12. 运输问题数学模型的约束矩阵特点：①对应于变量x ij 的系数向量Pij 中除第i 个和第m+j个为1以外，其余的都为0②系数矩阵的秩小于等于m +n -1③是m +n 阶的方阵
13. 求最大支撑树方法破圈法①在给定赋权的连通图上任找一个圈②在所找的圈中去掉一个权数最小的边③如果余下的图已不包含圈，则计算结束，所余下的图即为最大支撑树，否则返回①避圈法①在给定图上找权值最小的边并标记②继续找未标记的权数最小的边，与标记过的边不构成圈即可③如果所有点都连通且再任意标记一条边都会构成圈，则结束算法，否则返回②