《运筹学概念整理》由会员分享，可在线阅读，更多相关《运筹学概念整理（4页珍藏版）》请在金锄头文库上搜索。
1、运筹学概念整理名解5、简答4、建模与模型转换2、计算56 第1章线性规划与单纯形法（计算、建模:图解法） 线性规划涉及的两个方面：使利润最大化或成本最小化 线性规划问题的数学模型包含的三要素： 一组决策变量：是模型中需要首确定的未知量。一个目标函数：是关于决策变量的最优函数，max或min。 一组约束条件：是模型中决策变量受到的约束限制，包括两个部分：不等式或等式；非负取 值（实际问题）。线性规划问题（数学模型）的特点：目标函数和约束条件都是线性的。1. 解决的问题是规划问题；2 解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；3 解决问题的约束条件是多个决策变量的线性不等
2、式或等式。 图解法利用几何图形求解两个变量线性规划问题的方法。求解步骤：第一步：建立平面直角坐标系； 第二步：根据约束条件画出可行域； 第三步：在可行域内平移目标函数等值线，确定最优解及最优目标函数值。LP 问题的解：（原因） 唯一最优解、无穷多最优解（有2个最优解，则一定是有无穷多最优解） 无界解（缺少必要的约束条件）、无可行解（约束条件互相矛盾，可行域为空集） 标准形式的LP模型特点：目标函数为求最大值、约束条件全部为等式、约束条件右端常数 项bi全部为非负值，决策变量xj的取值为非负 线性规划模型标准化（模型转化）（1）“决策变量非负”若某决策变量xk为“取值无约束”（无符号限制），令:
3、 xk = x，k-x”k， （xk20,x”k 三0）。“目标函数求最大值”如果极小化原问题minZ = CX,则令Z=-乙 转为求maxZ=- CX 。注意：求解后还原。（3）“约束条件为等式”对于“W”型约束，则在“W”左端加上一个非负松弛变量，使 其为等式。对于“三”型约束，则在“三”左端减去一个非负剩余变量，使其为等式。（4）“资源限量非负”若某个bi0）; 确定出基变量（0l=minbi/aikl aik0; 初等变换,求出新的基本可行解4 重复步骤2、3，直到求出最优解。Bland法则最小比值相等时任选一个出基，不用考虑bland法则大M法诵过添加人工变量构成单位基，讲而求解线性
4、规划问题的方法。大M法求解（终止表）的可能结果：线性规划问题有最优解（1）基变量中不含人工变量； 有最优解（2）基变量中含人工变量，但取值为零； 无可行解（3）基变量中含人工变量，但取值不为零。第 2 章 线性规划的对偶问题（计算：互补松弛定理） 对偶模型（模型转化）注：一定要设对偶问题的决策变量。原问题（或对偶问题）目标函数max对偶问题（或原问题）目标函数min决策变量n个约束条件n个约束条件m个决策变量m个价值系数n个资源数量n个资源数量m个价值系数m个系数矩阵A系数矩阵AAT变M0约量W0无约束束“W”“=”约66$,变W 0束660”“=”量$ 0无约束弱对偶定理原问题和对偶问题有最
5、优解的充要条件是它们同时具有可行解。强对偶定理如果原问题和对偶问题中有一个最优解，那么另一个也一定有最优解，并且两个 规划问题的目标函数的最优值相等。互补松弛定理在线性规划问题的最优解中，如果对应某一约束条件的对偶变量取值为非零 则该约束条件为严格等式；反之，如果原问题约束条件为严格不等式，则其对应的对偶变量 一定为零。影子价格原问题中第i项资源每增加一个单位对目标函数的贡献。影子价格=资源成本+影子利润对偶单纯形法：用对偶定理（性质）求解线性规划问题的方法。第3章 运输问题（计算：最小元素法、西北角法、产销不平衡的运输问题） 运输问题的求解方法：表上作业法 求解步骤：（1）找到一个初始调运方
6、案（最小元素法和西北角法）（2）利用检验数判优（闭回路法和位势变量法）（3）若不是最优解，则调整调运方案，即寻找更优的基本可行解（闭回路法） 模型系数矩阵特征：1、决策变量个数m X n；约束条件个数m + n；运输问题有m + n-1个基变量2、每一列中均含有两个“1”分别位于第i行和第m+j行（xij）,其余都为0. 如何将产销不平衡问题转化为平衡问题：（1）产量销量时，增加一个虚拟销地n+1来表示多出的库存（单位运价为0）（2）产地销量时，增加一个虚拟产地m+1来表示没有被满足的需求量（运费为0）第 4 章 目标规划目标函数线性规划目标规划max、minmin约束条件系统约束可以没有系统
7、约束，但必须有目标约束决策变量只有决策变量既有决朿变量，又有偏差变量解最优解满意解偏差变量：用于表示决策值与目标值之间的差异 正偏差变量d+表示决策值超过目标值的部分；负偏差变量 d- 表示决策值低于目标值的部分。 规定：d+, d-三0。d+*d-=0.系统约束：必须严格满足的约束条件，决定了解的可行性，是硬约束。目标约束：有正负偏差变量未表示的约束，是松约束。目标规划的目标函数（达成函数）由各目标约束的偏差变量及相应的优先因子和权系数构 成目标规划图解法第 5 章 整数规划（建模：0-1 整数规划） 整数规划要求全部或部分决策变量的取值为整数的线性规划问题 整数规划的类型：（1）纯整数线性
8、规划：指全部决策变量都必须去整数值的整数线性规划（2）混合整数线性规划：指决策变量中部分必须取整数的整数线性规划。（3）01型整数线性规划：指决策变量只能取值0或1的整数线性规划。 求解方法：分枝定界法、割平面法、隐枚举法、匈牙利法第 6 章 图与网络模型（计算：最短路、最大流（割集与最小割集） 边不带箭头的连线；弧带箭头的连线无向图由点和边的集合所构成 有向图由点和弧的集合所构成（网络图中的连线有规定的方向） 关联边：若 vi 和 vj 是边 e 的两个结点，称 e 是 vi 和 vj 的关联边 链：无向网络中，前后相继点和边的交替序列称为一条链。 圈：闭合的链称为一个圈（首尾相接） 路径：
9、有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。 回路：闭合的路径称为一个回路。环：若一条边 e 的两个结点相重叠，称 e 为环。 多重边：若两结点之间存在两条以上关联边，则称两结点具有多重边。 多重图：含多重边的图称为多重图。简单图：不含环和多重边的图称为简单图。 权：与边或弧相关的数量指标称为权，如距离、费用、流量。 赋权图：点、边、权的总体称为赋权图。网络：规定起点、终点和中间点的连通的赋权图称为网络，次：与某个结点vi关联的边的个数，称为结点vi的次（度），d（vi）。（规定: 一个环计算两个次/度） 悬挂点：次为 1 的结点称为悬挂点，悬挂点的关联边称为悬挂边。完全图对于一
10、个简单图，若图中任意两点之间均有边相连 最小树求解方法：破圈法、避圈法割和流量：一定是前向弧 树无圈的连通图设是从vs到vt的链，方向从vs fvt，则链上的弧分为两类前向弧：弧的方向与链的方向相同，记+ 后向弧：弧的方向与链的方向相反，记- 网络的最大流：网络从发点到收点之间允许通过的最大流量 最短路：无向图最短路的狄克斯屈拉算法、有向图的最短路问题 最小树问题 最大流问题第 7 章 动态规划（简答多） 动态规划是解决多阶段决策过程最优化问题的一种方法。 阶段指一个问题需要作出决策的步骤 状态表示在任一阶段所处的位置 决策当决策者处于某个阶段的某个状态时，面对下一阶段的某一状态做出的选择或决
11、定。 策略是决策者按阶段依次做出的决策序列，又称全策略。状态转移律在第k阶段某一确定的状态Sk下，一旦决策变量xk（Sk）确定，则下一阶段的状 态 Sk+1 也就确定指标函数用于衡量已实现子策略优劣的数量指标 最优函数对某一确定状态，选择最优策略后得到的指数函数值，即对应某一最优子策略的某 种效益量度。贝尔曼最优化原理作为整个过程的最优策略，应具有这样的性质：无论过去的状态和决策如 何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。动态规划问题模型要素（1）阶段变量。（2）状态变量。（3）决策变量。（4）状态转移方程。（5）阶段 函数。 （6）最优函数。 （7）动态规划基本方程。顺序
12、解法和逆序解法的区别1 求解顺序不同2 求解条件：顺 给定结束条件；逆 给定初始条件3 求解结果：顺 求出始点到各点的最短路径/权；逆 求出各点到目的地的最短路径/权；第 8 章 存储论（计算：经济订货批量模型、需求量是离散型随机变量的报童问题） 存储模型的分类1、确定型与随机型存储模型确定型储存模型凡需求率D和提前订货时间t均确定的储存问题 如经济订货批量（EOQ） 模型、分批均匀进货的 EOQ 模型、允许缺货的 EOQ 模型、具有价格折扣优惠的存储模型、 具有约束条件的存储模型随机型储存模型凡需求率 D 或提前订货时间 t 不确定的存储问题2、单品种与多品种库存储模型单品种库：物资的需求量大、体积大、占有资金多、就会单独设立仓库进行保管 多品种库：对多种物资同时保管而设立的仓库，如钢材，电子元件等，这类模型往往存在资 金约束或仓库容积限制约束等。3、单周期与多周期存储模型 单周期的库存模型：在一个周期内只订货一次。若未到期末货已销售，不再补充订货；若发 生滞销，未售去的货物应在期末处理，如报纸。多周期的库存模型：多次进货多次供应。
