运筹学概念整理

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