运筹学复习笔记

1、运筹学复习笔记Part 1 题型1. 选择题（ 20 分）2. 填空题（ 40 分）3. 建模题（ 40 分）4. 决策问题（ 20 分）5. 运输问题（ 10 分）计算Part 2 需要掌握的知识点Chapter 2 线性规划与单纯型法一、线性规划问题（建模）二、求解两个变量的线性规划模型图解法附：图解法的启示1）图解法求解结果的几种可能情况：唯一最优解无穷多最优解 无界解（并不是说可行域是无界的线性规划问题的解就一定是无界解） 无可行解2）若线性规划问题的可行域非空，则可行域是一个凸集。线性规3）若线性规划问题的最优解存在， 则一定可以在可行域的凸集的某个顶点达到。划问题的基可行解 X 对

2、应于可行域 D 的顶点。）三、单纯形法准备知识标准型1）标准型的四个条件目标函数为极大（ max） 所有的约束条件满足等式 所有的决策变量非负右端常数均为非负数2）化为标准型的方法若要求目标函数实现最大化，即 max z=CX。这时只需将目标函数最小化变换求目 标函数最大化，即令 z=-z，于是得到 max z= CX。这就同标准型的目标函数 的形式一致了。约束方程为不等式。这里有两种情况：一种是约束方程为 不等式， 则可在不等式的左端加入非负松弛变量 xj ，把原不等式变为等式， 0xj ； 另一种是约束方程为不等式，则可在不等式的左端减去一个非负剩 余变量 xk （也可称松弛变量），把不等

3、式约束条件变为等式约束条件,目标函数中加上0xk （松弛变量 ）.若变量约束中： xi 0，则令 xi -xi ，得到 xi 0；若 xj R ，则令xjxj-xj ，其中xj，xj0，用xi、xj 、xj分别代替xi 、 xj后得到线性规划的变量约束均为非负约束。资源限量 bi 0。四、单纯型法准备知识线性规划问题解的概念1） 可行解：满足约束条件式（等式约束、非负约束）的解。2） 最优解：使目标函数达到最大值的可行解。3）基：约束方程组的系数矩阵 Am n的一个满秩的子矩阵 Bm m ，B称为线性规划问题的一个基。附：基向量：B 矩阵中每一个列向量都称为基向量。基变量：选定的向量（基向量）

4、对应的变量xi （可以不止一个）称为基变量，其他的变量称为非基变量。4）基解：有一个基就可以求出一个基解（运用克莱姆法则）。5）基可行解： 满足非负条件式的基解 （基解是根据等式约束条件得到的， 还没有涉及目标 函数和变量非负的约束条件， 相当于对一个非齐次线性方程组求解。 当这样的基解满足 变量非负的约束条件时，我们称它为基可行解。PS：并不一定是最优解。）6）可行基：与基可行解相对应的基称为可行基。7）可行域（可行空间）8）几何性质凸集的概念考题：求基解、判断是否为基可行解、是否为最优解五、线性规划问题的一些性质六、单纯形表（了解，知道如何寻找主元）口诀：最大最小找主元初行变换得新解（新的

5、基可行解）目标函数有改善例题：1. 例 2-1 线性规划问题建模2. 用图解法求解例 2-1 中建立的线性规划模型3. 把例 2-1 中建立的线性规划模型化为标准型4. 指出例 2-1 中建立模型的基、基变量、基解、基可行解和可行基5. 单纯型表相关的题型cj23000iCBXBbx1x2x3x4x50x381210040x41640010-0x512040013c j zi23000进行一轮计算以后得到下表cj23000iCBXBbc j zi6. 一个更为复杂的建模题某工厂明年根据合同， 每个季度末向销售公司提供产品， 有关信息如表， 若当季生产的 产品过多， 季末有积余， 则一个季度每积

6、压一吨产品需支付存贮费万元。 现该厂考虑明年的 最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立线性规划模型。季度（j）生产能力（aj）生产成本（dj）需求量（bj）130152024014203203041010Chapter 3 对偶理论与灵敏度分析（ 4 分）一、影子价格1） 含义：代表在资源最优利用条件下，对第 i 种资源一单位的估价，这种估价不是资源的 市场价格，而是根据资源在生产中做出的贡献而做的估价。2） 经济意义 影子价格反映资源对目标函数的边际贡献，即资源转化成经济效益的效率。 影子价格反映了资源的稀缺程度。影子价格反映了资源的边际使用价值。Chapter

7、4 运输问题（ 10 分）一、确定初始基可行解最小元素法、伏格尔法确定初始可行解的方法考试不要求，但是对于理解最优解的判别很有帮助。单位运价表产地销地B1B2B3B4A1311310A21928A374105产销平衡表产地销地产量B1B2B3B4A17A24A39销地3656-最小元素法思想：从单价中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。Step 1产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A17A234A39销地3656-Step 2产地销地B1B2B3B4A1311310A21928A374105产地销地产量B

8、1B2B3B4A17A2314A39销地3656-Step 3产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A1437A2314A3639销地3656-口诀：最小运价定方向， 需求满足便退出， 供给耗尽线划去； 余下运价找最小， 直到运价全划去， 所得必是可行解。伏格尔法最小元素法的缺点：可能开始节省一处的费用，但随后在其他几处要多花几倍的运费。伏格尔法的思想：对差额最大处采用最小运费调运。Step 1 根据单位运价表分别算出各行和各列的最小运费和次小运费的差额。产地销地行差额B1B2B3B4A13113100A219281A3741051列差额

9、2513-Step 2 从行和列差额中选出最大者，选择它所在的行或列中的最小元素，确定供给方向。这一步是对伏格尔法思想的体现）产地销地行差额B1B2B3B4A13113100A219281A3741051列差额2513-产地销地行差额B1B2B3B4A13113100A219281A3741051列差额2512-产地销地行差额B1B2B3B4A13113107A219281A3741051列差额25310-产地销地行差额B1B2B3B4A13113103A219281A3741051列差额25310-产地销地产量B1B2B3B4A1527A2314A3639销地3656-口诀：行列运价求差额，

10、差额最大找最小（差额最大行、列处找最小的运价），最小运价定方向；需求满足便退出，供给耗尽线划去；余下步骤均相同，直到运价全划去，所得必是可行解。二、最优解的判别方法闭回路法要求：求检验数、调整方案、往下进行一步（ 46 分）（选填题）最优解的判别方法：计算空格（非基变量）的检验数。当检验数还存在负数时，说明原方案不是最优解，需要继续改进。例题：用闭回路法检验上一步中最小元素法得到的初始基可行解是否为 最优解。产地销地产量B1B2B3B4A1437A2314A3639销地3656-闭回路法计算检验数的经济解释： 在已给出初始解的上表中， 可以从任一空格出发， 如 （A1，B1），若让 A1 的产

11、品调匀一吨给 B1。为了保持产销平衡， 就要依次做调整： 在（ A1， B3）处减少一吨，（ A2，B3）处增加一吨，（ A2，B1）处减少一吨，即构成（ A1， B1）空 格为起点，其他为数字格的闭回路。检验数 调整后运费的增减数本例中的检验数为： （ 1） 3 （ 1） 3 （ 1） 2 （ 1） 1 1（元 ） ，以其他空格为起点 可以得到更多的检验数。如果得到的检验数全为正，则说明初始方案无法得到进一步改进， 即初始方案为最优解；反之，初始基可行解不为最优，还存在改进的空间。三、运输问题的一些性质基变量的个数 （上一个知识点中， 通过最小元素法得到的初始基可行解的基变量的 个数为 6）

12、PS：在产销平衡的运输问题中， 基变量的个数 产地个数 销售个数 -1 。闭回路的顶点数永远是偶数（只有这样才能保证产销的均衡）Chapter 5 整数线性规划（ 20 分）一、整数规划问题（建模）：把文字描述分析转化为数学模型整数规划问题： 是一类特殊的线性规划问题， 是指要求部分或全部决策变量的取值为整数的规划问题。其中，重点掌握整数线性规划问题。二、整数规划问题的决策三、整数线性规划问题的类型纯整数线性规划（重点掌握）全部决策变量都必须取整数值 混合整数线性规划决策变量中一部分必须取整数值， 另一部分可以不取整数值 0-1 型整数线性规划（重点掌握指派问题）决策变量只能取0 或 1（用于

13、表现分析投资还是不投资这类问题）四、人力资源的分配问题（选填题） 要求：明白求解的逻辑和方法，求解的结果不要求给出 标准指派问题的数学模型1 指派第 i 个人做第 j 件事xij0 不指派第 i 个人做第 j 件事nnminZcij xiji 1 j1nxij 1,i 1,2,.ni1ns.txij 1, j 1,2,.nj1xij 0或1PS：一项任务只能由一个人完成，一个人只能完成一项任务。 指派问题的匈牙利解法匈牙利法求最优解的理论依据指派问题最优解的性质：若从系数矩阵（cij ）的一bij ），那么以（ bij ）行（列）各元素中分别减去该行（列）的最小元素，得到新的矩阵（ 为系数矩阵

14、求得的最优解和用原系数矩阵求得的最优解相同。Step 1 使指派问题的系数矩阵经变换，在各行各列中都出现 0 元素（只有这样才能保 证每个人都被分配到任务）。系数矩阵的每行元素减去该行的最小元素； 再从系数矩阵的每列元素中减去该列的最小 元素；若某行（列）已有 0 元素，那就不必再减了。Step 2 进行试指派，以寻求最优解。目标： 寻找独立的 0 元素 （位于不同行不同列的 0 元素） ，独立的 0 元素的位置便是需 要安排人的地方，这样的安排所需要的总时间最少（总耗费最低）。目标的实现方法：当 n（任务数或者人数）较小时观察法、试探法（重点掌握）； 当 n 较大时采用以下步骤寻找 0 元素

15、：Step 从只有一个 0 元素的行开始， 给这个 0 元素加圈圈。 这表示对这行所代表的人， 只有一种任务可指派。然后划去圈圈所在列的其他0 元素，记作 。这表示这列所代表的任务已经指派完，不需要再考虑其他人了。Step 给只有一个 0 元素列的 0 元素加圈圈。这表示这列所代表的这项任务，只有一 个人做。然后划去圈圈所在行的其他 0 元素，记作 。这表示这行所代表的人已经被只拍 了任务，对其他的任务不再考虑。Step 反复进行 step 和 step ，直到所有的 0 元素都被圈出和划掉为止。Step （这一步太复杂，等以后慢慢研究吧）Step 若画圈圈元素的数目 m 等于矩阵（方阵）的阶

16、数，那么指派问题的最优解已得 到。例题 1 整数线性规划问题的建模与求解某厂利用集装箱托运甲、乙两种货物，每箱体积重量、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413-两种货物各托运多少箱使利润最大例题 2 建模人力资源的分配问题（指派问题）有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、 J、G、R。现有甲、乙、丙、丁 4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何 人去完成何种工作，使所需总时间最少效率矩阵（系数矩阵） cij人员任务EJGR甲2151314乙1041415丙9141613丁78119例题 3 指派问题的求解匈牙

17、利解法（有难度）人员任务ABCDE甲127979乙89666丙71712149丁15146610戊4107109Chapter 8 & 9 图与网络分析（ 10 分）一、了解一些图的基本的概念结合图形理解下列概念： 边、弧：把两点之间不带箭头的连线称为边，带箭头的连线称为弧。无向图：如果一个图是由点及边所构成的，则称之为无向图（也简称为图），记为 G（V， E）。有向图：如果一个图是由点及弧所构成，则称为有向图，记为D（ V，A）。无向图的一些名词和记号：（边的）端点、 （点与点）相邻、 （边是点的）关联边、环（两个端点相同的边）、 多重边 （两个点之间有多余一条的边）、 简单图 （无环无多重

18、边的图）、 多重图 （一个 无环，但允许有多重边的图）、次 ：以点 v 为端点的边的个数称为点 v 的次，记为 d（v）。要求：会计算（数）端点 的次、特别注意有环存在时的次（记两次）。悬挂点、悬挂边 ：次为 1 的点称为悬挂点、悬挂点的关联边称为悬挂边。 孤立点：次为零的点称为孤立点。奇点、偶点：次数为奇的点称为奇点，次数为偶的点称为偶点。链、中间点、圈 初等链：中间点均为不同点的链称为初等链（一个点不经过两次）； 初等圈：中间点均为不同点的圈称为初等圈。简单链（圈）：链（圈）中含有的边均不相同（同一个边不经过两次）。 连通图、不联通图 ：任何两个点之间至少有一条链的图，否则称为不连通图。

19、连通分图：若 G 是不连通图，它的每个连通的部分称为 G的一个连通分图（简称 分图）。支撑子图：给一个图 G （V , E） ，如果图 G （V,E），使V V 及E E，则 称G 为G 的一个支撑子图。有向图的一些名词和记号 基础图：设给了一个有向图 D （V,A），从 D中去掉所有弧上的箭头就得到一个 无向图，称之为 D 的基础图，记为 G ( D) 。“有向图无向化以后得到有向图的基础 图”。始点、终点 ：给 D 中的一条弧 a=(u,v)，称 u 为 a 的始点， v 为 a 的终点。路回路链( P 标号、 T 标号)二、树树的定义：一个无圈的连通图称为树树的性质 设图 G (V ,

20、E)是一个树， p(G) 2，则 G中至少有两个悬挂点。PS：图 G或图 D的点数记为 p(G) 或p(D) ，边(弧)数记为 q(G) 或q(D) 图G (V, E) 是一个树的充分必要条件是 G 不含圈，且恰有 p 1条边 图G (V, E) 是一个树的充分必要条件是任意两个顶点之间恰有一条链 (无论 去掉哪一条边，都会变成一个不连通图)三、图的支撑树支撑树的定义：设图 T (V,E )是图 G (V , E)的支撑子图，如果 T (V,E ) 是 一个树，则称 T 是 G 的一个支撑树。寻求连通图的支撑树的方法破圈法、闭圈法 这两种方法的理论支持：图 G 有支撑树的充分必要条件是图G 是

21、连通的。破圈法： 任取一个圈， 从圈中去掉一边， 对余下的图重复这个步骤， 直到不含圈时为止， 即得到一个支撑树。闭圈法：四、最小支撑树问题知识准备赋权图最小支撑树：在所有的支撑树中权最小的树最小支撑树的求法避圈法破圈法五、最短路问题知识准备最短路最短路的算法双标号（ T标号、 P 标号）算法，也叫狄克斯拉算法理论基础：假定 （1，2），（2，3），（3，4）是点 1到 4的最短路，则 （1，2），（2，3）是点1到 3的最短路； （2，3），（3，4）是点 2 到4的最短路。Chapter 10 存储论（ 4 分）（选填题）一、模型一：不允许缺货、备货时间很短要求：计算最佳经济订购批量、模型

22、的运用条件（假设条件）模型的假设条件1. 缺货费用无穷大；2. 当存储降至零时，可以立即得到补充（模型中不考虑缺货费用）；3. 需求是连续的、均匀的，设需求速度R（单位时间的需求量）为常数，则时间段t内的需求量为 Rt；4. 每次订货量不变，订购费不变；5. 单位存储费不变。衡量存储策略优劣的指标总平均费用最佳的订购时间间隔、经济订购批量、最佳费用1. 最佳的订购时间间隔t0C2C1R32. 经济订购批量3. 最佳费用2C3RC12C1C3R其中， C1是单位时间内单位物品的存储费用，C3 是订购费（除了商品价款外的其它费 用）， R 是单位时间的需求量。推导过程如下：总平均费用 平均采购费用

23、 平均存储费用PS：由于时间 t 是相同的，所以上式的表达是正确的。采购费用 货物价款 订购费用 KRt C3平均采购费用 KR 3 tPS：其中 K 是货物的单价1 t 1平均存储费用 C11 RTdT 1 C1Rt1 t 0 2 1 总平均费用 KR C3 1 C1Rt t 2 1 对总平均费用关于 t 求一阶导，令其为 0，得t23 2C1R 0，2C3C1R 为最佳订购时间间隔。其他变量的推导相同。PS：由于经济订购批量和最佳订购时间间隔均和货物的单价K 无关， 所以我们在总费平均用函数中不考虑含有 K 的项。即总平均费用 t2C1Rt ，代入最佳订购时间间隔均可得最佳费用。例题 1某厂按合同每年需提供 D个产品，不许缺货。假设每一周期工厂需装配费C3 元，存储费每年每单位产品为 C1元，为全年应分几批供货才能使装配费，存储费两者之和最少例题 2某轧钢厂每月按计划需产角钢 30000 吨，每吨每月存