运筹学复习笔记

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

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

3、约束方程为不等式，则可在不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式约束条件变为等式约束条件,目标函数中加上 (松弛变量).Ø 若变量约束中：，则令，得到；若，则令 ，其中，用 、分别代替、后得到线性规划的变量约束均为非负约束。Ø 资源限量bi 0。4、 单纯型法准备知识线性规划问题解的概念1) 可行解：满足约束条件式（等式约束、非负约束）的解。2) 最优解：使目标函数达到最大值的可行解。3) 基：约束方程组的系数矩阵的一个满秩的子矩阵，B称为线性规划问题的一个基。附：基向量：B矩阵中每一个列向量都称为基向量。基变量：选定的向量（基向量）对应的变量（可以不止

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

5、 例题：1. 例2-1线性规划问题建模2. 用图解法求解例2-1中建立的线性规划模型3. 把例2-1中建立的线性规划模型化为标准型4. 指出例2-1中建立模型的基、基变量、基解、基可行解和可行基5. 单纯型表相关的题型230000812100401640010-01204001323000进行一轮计算以后得到下表230006. 一个更为复杂的建模题某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元。现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立线性规划模型。季度生产

6、能力生产成本需求量1301520240142032015.33041014.810Chapter 3 对偶理论与灵敏度分析（4分）1、 影子价格1) 含义：代表在资源最优利用条件下，对第i种资源一单位的估价，这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而做的估价。2) 经济意义Ø 影子价格反映资源对目标函数的边际贡献，即资源转化成经济效益的效率。Ø 影子价格反映了资源的稀缺程度。Ø 影子价格反映了资源的边际使用价值。Chapter 4 运输问题（10分）1、 确定初始基可行解最小元素法、伏格尔法确定初始可行解的方法考试不要求，但是对于理解最优解的判别

7、很有帮助。单位运价表产地销地B1B2B3B4A1311310A21928A374105产销平衡表产地销地产量B1B2B3B4A17A24A39销地3656-Ø 最小元素法思想：从单价中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。Step 1 产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A17A234A39销地3656-Step 2 产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A17A2314A39销地3656-Step 3 产地销地B1B2B3B4A1311310

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

9、（这一步是对伏格尔法思想的体现）产地销地行差额B1B2B3B4A13113100A219281A3741051列差额2513-产地销地行差额B1B2B3B4A13113100A219281A3741051列差额2512-产地销地行差额B1B2B3B4A13113107A219281A3741051列差额25310-产地销地行差额B1B2B3B4A13113103A219281A3741051列差额25310-产地销地产量B1B2B3B4A1527A2314A3639销地3656- 口诀：行列运价求差额，差额最大找最小（差额最大行、列处找最小的运价），最小运价定方向；需求满足便退出，供给耗尽线划

10、去；余下步骤均相同，直到运价全划去，所得必是可行解。2、 最优解的判别方法闭回路法要求：求检验数、调整方案、往下进行一步（46分）（选填题）最优解的判别方法：计算空格（非基变量）的检验数。当检验数还存在负数时，说明原方案不是最优解，需要继续改进。 例题：用闭回路法检验上一步中最小元素法得到的初始基可行解是否为最优解。产地销地产量B1B2B3B4A1437A2314A3639销地3656-闭回路法计算检验数的经济解释：在已给出初始解的上表中，可以从任一空格出发，如（A1，B1），若让A1的产品调匀一吨给B1。为了保持产销平衡，就要依次做调整：在（A1，B3）处减少一吨，（A2，B3）处增加一吨，

11、（A2，B1）处减少一吨，即构成（A1，B1）空格为起点，其他为数字格的闭回路。检验数调整后运费的增减数本例中的检验数为：，以其他空格为起点可以得到更多的检验数。如果得到的检验数全为正，则说明初始方案无法得到进一步改进，即初始方案为最优解；反之，初始基可行解不为最优，还存在改进的空间。3、 运输问题的一些性质Ø 基变量的个数（上一个知识点中，通过最小元素法得到的初始基可行解的基变量的个数为6） PS：在产销平衡的运输问题中，。Ø 闭回路的顶点数永远是偶数（只有这样才能保证产销的均衡）Chapter 5 整数线性规划（20分）1、 整数规划问题（建模）：把文字描述分析转化为数

12、学模型整数规划问题：是一类特殊的线性规划问题，是指要求部分或全部决策变量的取值为整数的规划问题。其中，重点掌握整数线性规划问题。2、 整数规划问题的决策3、 整数线性规划问题的类型Ø 纯整数线性规划（重点掌握）全部决策变量都必须取整数值Ø 混合整数线性规划决策变量中一部分必须取整数值，另一部分可以不取整数值Ø 0-1型整数线性规划（重点掌握指派问题）决策变量只能取0或1（用于表现分析投资还是不投资这类问题）4、 人力资源的分配问题（选填题）要求：明白求解的逻辑和方法，求解的结果不要求给出Ø 标准指派问题的数学模型 1 指派第 i 个人做第 j 件事 0

13、不指派第 i 个人做第 j 件事PS：一项任务只能由一个人完成，一个人只能完成一项任务。Ø 指派问题的匈牙利解法匈牙利法求最优解的理论依据指派问题最优解的性质：若从系数矩阵（）的一行（列）各元素中分别减去该行（列）的最小元素，得到新的矩阵（），那么以（）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。Step 1 使指派问题的系数矩阵经变换，在各行各列中都出现0元素（只有这样才能保证每个人都被分配到任务）。系数矩阵的每行元素减去该行的最小元素；再从系数矩阵的每列元素中减去该列的最小元素；若某行（列）已有0元素，那就不必再减了。Step 2 进行试指派，以寻求最优解。目标：寻找独

14、立的0元素（位于不同行不同列的0元素），独立的0元素的位置便是需要安排人的地方，这样的安排所需要的总时间最少（总耗费最低）。目标的实现方法：当n（任务数或者人数）较小时观察法、试探法（重点掌握）；当n较大时采用以下步骤寻找0元素：Step 2.1 从只有一个0元素的行开始，给这个0元素加圈圈。这表示对这行所代表的人，只有一种任务可指派。然后划去圈圈所在列的其他0元素，记作。这表示这列所代表的任务已经指派完，不需要再考虑其他人了。Step 2.2 给只有一个0元素列的0元素加圈圈。这表示这列所代表的这项任务，只有一个人做。然后划去圈圈所在行的其他0元素，记作。这表示这行所代表的人已经被只拍了任务

15、，对其他的任务不再考虑。Step 2.3 反复进行step 2.1 和step 2.2 ，直到所有的0元素都被圈出和划掉为止。Step 2.4 （这一步太复杂，等以后慢慢研究吧）Step 2.5 若画圈圈元素的数目m等于矩阵（方阵）的阶数，那么指派问题的最优解已得到。 例题1 整数线性规划问题的建模与求解某厂利用集装箱托运甲、乙两种货物，每箱体积重量、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413-两种货物各托运多少箱使利润最大？ 例题2 建模人力资源的分配问题（指派问题）有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，

16、他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？效率矩阵（系数矩阵）人员 任务EJGR甲2151314乙1041415丙9141613丁78119 例题3 指派问题的求解匈牙利解法（有难度）人员任务ABCDE甲127979乙89666丙71712149丁15146610戊4107109Chapter 8 & 9 图与网络分析（10分）1、 了解一些图的基本的概念结合图形理解下列概念：Ø 边、弧：把两点之间不带箭头的连线称为边，带箭头的连线称为弧。Ø 无向图：如果一个图是由点及边所构成的，则称之为无向图（也简称为图）

17、，记为G（V，E）。Ø 有向图：如果一个图是由点及弧所构成，则称为有向图，记为D（V，A）。Ø 无向图的一些名词和记号： （边的）端点、（点与点）相邻、（边是点的）关联边、环（两个端点相同的边）、多重边（两个点之间有多余一条的边）、简单图（无环无多重边的图）、多重图（一个无环，但允许有多重边的图）、次：以点v为端点的边的个数称为点v的次，记为d(v)。要求：会计算（数）端点的次、特别注意有环存在时的次（记两次）。悬挂点、悬挂边：次为1的点称为悬挂点、悬挂点的关联边称为悬挂边。孤立点：次为零的点称为孤立点。 奇点、偶点：次数为奇的点称为奇点，次数为偶的点称为偶点。 链、中间点

18、、圈 初等链：中间点均为不同点的链称为初等链（一个点不经过两次）； 初等圈：中间点均为不同点的圈称为初等圈。 简单链（圈）：链（圈）中含有的边均不相同（同一个边不经过两次）。 连通图、不联通图：任何两个点之间至少有一条链的图，否则称为不连通图。 连通分图：若G是不连通图，它的每个连通的部分称为G的一个连通分图（简称分图）。 支撑子图：给一个图，如果图，使及，则称为的一个支撑子图。Ø 有向图的一些名词和记号基础图：设给了一个有向图，从D中去掉所有弧上的箭头就得到一个无向图，称之为D的基础图，记为。“有向图无向化以后得到有向图的基础图”。始点、终点：给D中的一条弧a=(u,v)，称u为a

19、的始点，v为a的终点。路回路Ø 链（P标号、T标号）2、 树Ø 树的定义：一个无圈的连通图称为树Ø 树的性质1 设图是一个树，则G中至少有两个悬挂点。 PS：图G或图D的点数记为或，边（弧）数记为或2 图是一个树的充分必要条件是G不含圈，且恰有条边3 图是一个树的充分必要条件是任意两个顶点之间恰有一条链（无论去掉哪一条边，都会变成一个不连通图）3、 图的支撑树Ø 支撑树的定义：设图是图的支撑子图，如果是一个树，则称T是G的一个支撑树。Ø 寻求连通图的支撑树的方法破圈法、闭圈法这两种方法的理论支持：图G有支撑树的充分必要条件是图G是连通的。破圈法

20、：任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支撑树。闭圈法：4、 最小支撑树问题Ø 知识准备赋权图Ø 最小支撑树：在所有的支撑树中权最小的树Ø 最小支撑树的求法避圈法破圈法5、 最短路问题Ø 知识准备最短路Ø 最短路的算法双标号（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分）（选填题）1、 模型一：不允许缺货、备货时间很短要求：

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

22、程如下：PS：由于时间t是相同的，所以上式的表达是正确的。PS：其中K是货物的单价对总平均费用关于t求一阶导，令其为0，得，即为最佳订购时间间隔。其他变量的推导相同。PS：由于经济订购批量和最佳订购时间间隔均和货物的单价K无关，所以我们在总费平均用函数中不考虑含有K的项。即，代入最佳订购时间间隔均可得最佳费用。Ø 例题1 某厂按合同每年需提供D个产品，不许缺货。假设每一周期工厂需装配费元，存储费每年每单位产品为元，为全年应分几批供货才能使装配费，存储费两者之和最少？Ø 例题2某轧钢厂每月按计划需产角钢30000吨，每吨每月存储费53元，每次生产需调整及其设备等，共需装配费250000元。现在该厂每月生产角钢一次，生产批量为30000