运筹学复习手册课程：《运筹学（1）》课程号：20250013课序号：2授课老师：王焕刚授课学期：秋季学期基于材料：《运筹学基础》，张莹著，清华大学出版社《运筹学（1）》课件2007年秋，王焕刚编辑记录：第一次：王诚，starlit@zzxy，自46，2008年1月完成手册初样，待完善、更正、补充。
目录第1章线性规划的数学模型 (1)1.1 标准型 (1)1.2 线性规划标准型的基本假定, 基与解 (2)1.3 基本定理 (3)第2章单纯形法 (3)2.1 普通单纯形法 (3)2.2 退化问题的求解 (4)2.3 改进单纯形法 (4)第3章线性规划的对偶原理 (5)3.1 对偶问题 (5)3.2 对偶单纯型法 (6)第4章灵敏度分析 (6)4.1 改变价值向量C (6)4.2 改变限定向量b（变为b’） (6)4.3 改变初始约束矩阵的一列P j（变为P j’） (6)4.4 增加一个新约束 (6)4.5 增加一个新变量 (6)第5章整数规划 (7)5.1 分枝定界法 (7)5.2 求解0-1规划的隐枚举法 (7)5.3 求解指派问题的匈牙利法 (8)第6章目标规划 (8)6.1 基本概念和数学模型 (8)6.2 图解法 (10)6.3 序贯式算法 (10)6.4 单纯型法 (10)第7章非线性规划的基本概念和基本原理 (11)7.1 数学模型和基本概念 (11)7.2 凸函数和凸规划 (11)7.3 无约束条件的极值条件 (12)第8章单变量函数的寻优方法 (12)8.1 黄金分割法 (12)8.2 牛顿法 (13)第9章无约束条件下变量函数的寻优方法 (14)9.1 牛顿法 (14)9.2 单纯型搜索法 (14)9.3 最速下降法 (14)第10章约束条件下多变量函数寻优 (14)10.1 约束极值问题的最优性条件 (14)10.2 罚函数法 (16)第11章动态规划的基本概念和基本原理 (18)11.1 基本概念和模型组成 (18)11.2 基本原理和基本方程 (18)11.3 递推方法 (19)第12章确定性决策过程 (19)12.1 生产与存储问题 (19)12.2 资源分配问题（一维） (20)12.3 不定期最短路径问题 (20)第13章图与网络分析 (21)13.1 图与网络的基本知识（略） (21)13.2 最短路问题 (21)13.3 最大流问题 (21)第14章决策分析 (23)14.1 概述 (23)14.2 风险性决策 (23)14.3 效用理论 (24)14.4 不确定型决策 (25)第15章对策论 (27)15.1 概述 (27)15.2 矩阵对策 (27)第16章排队论 (30)16.1 基本知识 (30)16.2 生灭过程的稳态解 (31)第1章 线性规划的数学模型1.1 标准型繁写形式及缩写形式： 变量≥0（假设n 个）约束条件是等式（假设m 个） 目标函数求min矩阵形式：min 0z CX AX b X ==≥，其中A 为约束条件的系数矩阵（m ×n ）Pj 为矩阵A 的第j 列，系数列向量（xj ） b 为限定向量（标准型中要求b ≥0） C 为价值向量（成本或利润向量）X 为决策变量向量（标准型中要求X ≥0） 1.1.1. 任意模型化为标准型 max 化为minmax(CX)=-[min(-CX)] 约束不等式化为等式当左端≥右端：左端－剩余变量＝右端（剩余变量≥0） 当左端≤右端：左端＋松弛变量＝右端（松弛变量≥0） 剩余变量与松弛变量统称附加变量。
✧ 实质：增加维数，但在目标函数里附加变量权值设为0。
x k 自由变量化为非负变量令'''('0,''0)k k k k k x x x x x =-≥≥ ✧ 实质：增加维数，替代即可。
x j有上下界化为非负变量当x j≥u j（有下界）即x j－u j≥0，令x j’＝x j－u j（x j’≥0），用（x j’＋u j）代替x j；当x j≤t j（有上界）即t j－x j≥0，令x j”＝t j－x j（x j”≥0），用（t j－x j）代替x j；✧实质：变量的线性变换1.1.2.图解法（适用于二阶情况）1、由全部约束条件作图求出可行域✧以x1为横轴，x2为纵轴；2、作出一条目标函数的等值线✧化为x2为x1的一次函数的形式；3、平移目标函数等值线，作图得最优点，最后再算出最优值。
✧一般使得等值线斜率最大✧如有解，通常为顶点或一条边，分别对应唯一最优解和无限最优解情况；1.2 线性规划标准型的基本假定, 基与解1.2.1.代数上的基本概念基：已知A 是约束条件的m×n 系数矩阵，其秩为m，若B是A 中m×m 非奇异子矩阵(即可逆矩阵, 有|B|≠0)，则称B 是线性规划问题的一个基，B是由A 中m个线性无关的系数列向量组成的；✧只要是可逆的都可以做基基向量：B中一列P i (共m个) 基变量x i非基向量：x中不是基向量的组成非基向量AX＝b ①X≥0 ②min z ＝CX ③可行解：①+②的解最优解：=可行解+③基本解：令所有非基变量=0，求出的满足①的解基本可行解：=基本解+②(非负条件)最优基本可行解：=基本可行解+③退化的基本解：有基变量=0 的基本解退化的基本可行解退化的最优基本可行解一般这里假设不出现“退化”。
1.2.2.几何上的基本概念凸集：任两点连线于集合边界没有有限个交点。
顶点：该点不能用集合内的任意两个点的线性组合来表示，即该点不在任意两点连线上（不含端点）。
凸组合：两点连线上的任意一点，为该两点的凸组合。
n维下即n个点的线性组合。
1.3 基本定理定理一：若线性规划问题存在可行域，则其可行域是凸集。
✧基本定理，实际应用中基本都满足。
定理二：线性规划问题的基本可行解对应于可行域的顶点✧在求解过程中关注顶点即可。
定理三：如果线性规划问题有有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到✧如果存在两顶点都满足，则意味着该两点形成的边都满足，存在无限最优解。
第2章单纯形法2.1 普通单纯形法1、化为标准型将b化为非负，加入附加变量2、构造初始可行基根据情况选定或构造初始可行基，然后列表，如表2.1。
✧在标准型下，如果经过线性变换后，可以找到一组原变量满足初始可行基条件，即解得满足不等式且非负，则直接利用即可。
如表 2.1中的x1，x2就可以直接作为初始可行基；✧如果不满足，则引入人工变量，以M为罚因子在目标函数中体现，即大M法。
✧归根结底的目的是：取到一组基，它的系数为单位阵，它的值非负。
以上两种方法目的都是这个。
表 2.13、求出基本可行解（实际求解中不需要）令非基变量为0，基变量取等式求解，然后计算目标函数值4、最优性检验（求min）最优性检验的依据——检验数σj表 2.25、✧取σj最小的换入6、确定换入变量✧去除换入变量的列中大于0的元素，如表2.1中x3列✧ 最小非负比值规则：分别计算θ=该行b/换出变量列的该行系数，取θ最小的行为换入变量。
7、 线性变换系数表✧ 使得目前的可行基对应系数矩阵为单位阵。
如表 2.1化为表 2.3 ✧ 返回4表 2.3✧ 关于检验数和比值θ，解释如下：检验数实际上是在现有函数z 的情况下，每个变量对于z 的影响的系数，选取检验数最小就是为了让z 最快地向着小的方向变化。
θ采取最小非负比值定理，起目的是为了保证留下来的基都是非负的。
2.2 退化问题的求解退化：基本解、基本可行解、最优基本可行解中有基变量变为0的情况。
问题：导致求解循环 方法：勃兰特方法：法则1：在极小化问题中，如有几个检验数(c j －z j )都是负的，那么选其中下标最小的非基变量作换入变量。
法则2：在极小化问题中，根据最小非负比值规则确定换出变量时，如果有几个比值同时达到最小比值，那么选其中下标最小的基变量作为换出变量。
2.3 改进单纯形法2.3.1. 单纯型法的矩阵形式min 0z CX AX b X ==≥，假设初始可行基B 集中于A 的首m 列，把A 、C 、X 分别按"基”与“非基”分成两块：A ＝(B,N) C ＝(CB ,C N )，X=[X B X N ]T min z ＝C B X B ＋C N X N ① BX B ＋NX N ＝b ② X B ≥0 X N ≥0则X B ＝B -1b ，z ＝C B B -1b ，单纯型乘子Y= C B B -1。
2.3.2. 求解步骤 1、 化为标准型 2、 构造初始可行基3、 计算相应矩阵A ，b 0，B 0（一般为I ）4、 计算检验数1111Ni Ni i i C Y N σ++++=-，判断是否结束；5、 确定换入向量（方法同普通单纯形法）6、 计算换入列(1)1()1i i ki k P B P +-+=，计算常数列(1)1(0)1i i b B b+-+=，得出换出向量（方法同普通单纯形法） 7、 回到4。
✧ 基本上改进单纯型法就是普通单纯型法的矩阵表达形式，其优点在于不用做表，但缺点是不直观。
从计算量来说，普通单纯型法和改进单纯型法没有基本没有差别。
第3章 线性规划的对偶原理3.1 对偶问题3.1.1. 数学模型min 0z CX AX b X =≥≥<=>max 0T TTw b YA Y CY =≤≥m 个约束 n 个约束 n 个变量 m 个变量 基本上的性质入下表✧ 3.1.2. 基本性质及基本定理 对称性（基本用不上）弱对偶定理：(两问题的目标函数值的关系) CX (0)≥b T Y (0)✧ 非最优下原问题目标函数值小于对偶问题目标函数值 ✧ 直接推出了对偶定理，为对偶单纯型法打下了基础 对偶定理：在最优下，有CX (0)=b T Y (0)； 最优性定理：若CX (0)=b T Y (0)，则最优；✧ 推论（原问题=>对偶问题）：有限最优解=>有限最优解，无可行解=>无可行解或无界解单纯型乘子Y 的定理（基本用不上） 互补松弛定理（原问题=>对偶问题）：约束大于0=>变量为0，变量大于0=>约束取到等号 （原问题=>对偶问题）：约束小于0=>变量为0，变量大于0=>约束取到等号✧ 在计算对偶问题时可以简化计算量，得到原问题解后，令对偶问题相应变量为0，解多元不等式即可。
最优对偶变量（影子价格）的经济解释✧y n相当于原问题b n增加1的情况下目标函数z的变化3.2 对偶单纯型法✧实质：在非可行域内逼近最优解，目的还是为了求原问题的最优解（不是用对偶单纯型法求对偶问题的最优解）✧几个对应：实质上是由于b和C的互换造成的表 3.2构造初始可行基时，保证检验数大于0，通常在单纯型法的标准型约束上乘-1即得对偶问题的标准型。