运筹学知识点总结

运筹学：应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。线性规划的图解法基本概念线性规划：是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。线性规划的三要素：变量或决策变量、目标函数、约束条件。目标函数：是变量的线性函数。约束条件：变量的线性等式或不等式。可行解：满足所有约束条件的解称为该线性规划的可行解。可行域：可行解的集合称为可行域。最优解：使得目标函数值最大的可行解称为该线性规划的最优解。唯一最优解、无穷最优解、无界解（可行域无界）或无可行解（可行域为空域）。凸集：要求集合中任意两点的连线段落在这个集合中。等值线：目标函数z，对于z的某一取值所得的直线上的每一点都具有相同的目标函数值，故称之为等值线。松弛变量：对于“≤”约束条件，可增加一些代表没使用的资源或能力的变量，称之为松弛变量。剩余变量：对于“≥”约束条件，可增加一些代表最低限约束的超过量的变量，称之为剩余变量。线性规划的标准形式约束条件为等式（=）约束条件的常数项非负（bj决策变量非负（xj灵敏度分析：是在建立数学模型和求得最优解之后，研究线性规划的一些系数的变化对最优解产生什么影响。目标函数中的系数ci目标函数的斜率在形成最优解顶点的两条直线的斜率之间变化时，最优解不变。约束条件中常数项bi对偶价格：约束条件常数项中增加一个单位而使最优目标函数值得到改进的数量。当某约束条件中的松弛变量（或剩余变量）不为零时，这个约束条件的对偶价格为零。线性规划问题在工商管理中的应用人力资源分配问题（P41）设xi为第i班次开始上班的人数生产计划问题（P44）套材下料问题（P48）下料方案表（P48）设xi为按各下料方式下料的原材料数量配料问题（P49）设xij为第i种产品需要第j投资问题（P53）设xij为第i年初投资于项目j运输问题产销平衡问题（P133）产销平衡运价表产大于销：假想仓库，转化为产销平衡问题求解（P141）对于货物必须运出的产地，假想仓库的单位储存费用为M（是一个足够大的正数），对于货物非必须运出的产地，假想仓库的单位储存费用为给定值。对于货物非必须全部运出的销地，需将其拆分为“货物必须运出”和“货物非必须运出”两个产地。销大于产：假想产地，转化为产销平衡问题求解（P139）对于需求必须满足的销地，假想产地的单位运价为M（是一个足够大的正数），对于需求非必须满足的销地，假想产地的单位运价为0。对于需求非必须全部满足的销地，需将其拆分为“需求必须满足”和“需求非必须满足”两个销地。生产与储存问题（P142）法一：线性规划，设xij为第i时间点生产的第j时间点交货的产品数目法二：转化为运输问题（M的作用：迫使运量为0）转运问题（P146）法一：线性规划（约束条件：起点节点的约束、转运节点的约束、终点节点的约束）法二：转化为扩大的运输问题（P148）对扩大的运输问题建立运价表，将表中不可能的运输方案用M代替。将原产地、销地、中转站的产量和销量同时加上原产量或销量的值。计算机求解运输问题的方法是表上作业法，其实质是单纯形法。整数规划整数规划的分类纯整数规划：如果所有的变量都为非负整数，则称为纯整数规划。混合整数规划：如果只有一部分变量为非负整数，则称为混合整数规划。0-1规划：如果所有变量都是0,1变量，则称为0-1规划。整数规划的性质任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。整数规划的图解法（P173）、整数规划的计算机求解（P175）投资场所的选择（P177）0-1规划固定成本问题（P178）产品的固定费用只有生产该产品时才投入，为说明固定成本的性质，需引入0-1变量yi为避免不投入固定费用就生产，有约束条件xi≤yi指派问题（P179）每项任务均有一人担任，有约束条件i每人承担的任务不超过自己的承担能力（ai是第i个人至多承担的任务数）j人少任务多且一人只能担任一项任务时，需假设一人，其完成所有任务的时间为0。分布系统设计（P181）附带选址问题的运输问题，需引入0-1变量yi，有j投资问题（P183）当项目有最低投资额要求时，需引入0-1变量yij最低投资额要求其他约束条件为“第i年投资额=可动资产”。目标规划目标规划：是解决存在多个目标的最优化问题的方法，它把多目标决策问题转化为线性规划来求解。偏差变量：实际值与目标值的差距。偏差变量的作用是允许约束条件不被精确满足。有优先权的目标规划，首先考虑优先权高的目标（P206）目标规划模型的标准化（P208）复杂情况下的有优先权的目标规划（P209）加权目标规划（P211）罚数权重：表示偏离各目标的严重程度。基本方法是通过量化的方法分配给每个目标偏离的严重程度一个罚数权重，建立总的目标函数，该目标函数表示的目标是要使每个目标与各自目标的加权偏差之和最小。动态规划基本概念动态规划：是解决多阶段决策过程最优化问题的一种方法。阶段：根据时间与空间的自然特征划分阶段。状态si：指每个阶段开始时所处的自然状况或客观条件决策xi：某一阶段内的抉择指标函数ri(si,xi)：表示指标函数是衡量全过程策略或k子过程策略优劣的数量指标，指标函数的最优值称之为最优指标函数，记作fi状态转移方程s动态规划表sfxrfx0123012最优化原理：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。也就是说最优策略的任一子策略都是最优的。最短路径问题（P217）si为阶段初始位置，xi为阶段决策资源分配问题（P222）sk为阶段初始剩余量，x设sk=分配给第k个目标到第n设xi背包问题（P225）法一：动态规划（si为阶段初始剩余量，x法二：整数规划生产与储存问题（P230）si为阶段初始储存量，xi为阶段决策生产量，d机器负荷分配问题（235）设sk=第k阶段初拥有的设xi=第k图与网络模型无向图：G由点和边构成，V是点的集合，E是边的集合。链：(v1,圈：(连通图：对一个无向图G，若任意两个不同点之间，至少存在一条链，则称G是连通图。有向图：D由点和弧构成，V是点的集合，A是弧的集合。路：(v回路：v赋权图对于无向图G的每一条边(vi,vj)，如果相应的有一个数wij，则称这样的图G为赋权图对于有向图D的每一条弧(vi,vj)，如果相应的有一个数cij，则称这样的图D为赋权图网络在赋权的有向图D中指定一点，称为发点（记为vs），指定另一点为收点（记为vt），其余的点称为中间点，并把D中的每一条弧的赋权数cij称之为弧(viDijkstra算法（P249）I={sij=l最小生成树问题：在一个赋权的连通的无向图G找出一个生成树，并使得这个生成树的所有边的权数之和为最小。树：无圈的连通图。生成子图：给了一个无向图G=(V,E)，我们保留G的所有点，而删除部分G的边或者说保留一部分G生成树：如果图G的一个生成子图是一个树，则称这个生成子图为生成树。破圈算法（P257）最大流问题：给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。（P261）最小费用最大流问题（P264）排序与统筹方法一台机器、n个零件的排序问题（求使各零件平均停留时间最少的加工次序）各零件平均停留时间为1即按照加工时间排出加工顺序，加工时间越短的零件排在越前面，加工时间越长的零件排在越后面，可使各个零件的平均停留时间为最少（按加工时间升序排列）。两台机器、n个零件的排序问题加工时间的延长主要是由于第二台机器的停工待料造成的为减少第二台机器的停工待料，应把在第一台机器上加工时间越短的零件越早加工，把在第二台机器上加工时间越短的零件越晚加工。步骤（P278）计划网络图点表示一个事件，是一个工序的开始或结束，是相邻工序在事件上的分界点。弧表示一个工序，在弧的上面标工序代号，在弧的下面标权数。紧前工序：紧接某项工序的先行（前道）工序。紧后工序：紧接某项工序的后续工序。虚工序计划网络图中不能有缺口和回路。关键路线：计划网络图中最长的路线，用双线