运筹学复习笔记

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

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

3、程为不等式，则可在不等式的左端减去一个非负剩余变量xk （也可称松弛变量），把不等式约束条件变为等式约束条件，目标函数中加上Oxk （ 松弛变量 ）.? 若变量约束中：xi 0 ,则令xi -xi，得到xi 0 ;若xj R，则令Xj Xj -Xj ,其中Xj , Xj 0，用Xi、Xj、Xj分别代替Xj、Xj后得到线 性规划的变量约束均为非负约束。? 资源限量bi > 0。四、单纯型法准备知识线性规划问题解的概念1）可行解：满足约束条件式（等式约束、非负约束）的解。2）最优解：使目标函数达到最大值的可行解。3）基：约束方程组的系数矩阵 Amn的一个满秩的子矩阵 Bm m，B称为线性规划

4、问题的一个基。附：基向量:B 矩阵中每一个列向量都称为基向量。基变量：选定的向量（基向量）对应的变量xi （可以不止一个）称为基变量，其他的变量 称为非基变量。4）基解：有一个基就可以求出一个基解（运用克莱姆法则）。5）基可行解： 满足非负条件式的基解 （基解是根据等式约束条件得到的， 还没有涉及目标 函数和变量非负的约束条件， 相当于对一个非齐次线性方程组求解。 当这样的基解满足 变量非负的约束条件时，我们称它为基可行解。 PS:并不一定是最优解。）6）可行基：与基可行解相对应的基称为可行基。7）可行域（可行空间）8）几何性质凸集的概念考题:求基解、判断是否为基可行解、是否为最优解五、线性规

5、划问题的一些性质六、单纯形表（了解，知道如何寻找主元）口诀:最大最小找主元初行变换得新解（新的基可行解）目标函数有改善例题:1.例2-1线性规划问题建模翔2-1 /M匸厂帆计划期内要妥排生产两冲产品已知牛.产单位产品所需的设*日两种原材料的消耗如丧2 1所示.产阳产品I. 1产胡Dk设»1會时衔za白时皿材料A4kg/韩0叫原材料H0 .12Uh2. 用图解法求解例2-1中建立的线性规划模型3. 把例2-1中建立的线性规划模型化为标准型4. 指出例2-1中建立模型的基、基变量、基解、基可行解和可行基5. 单纯型表相关的题型Cj23000CbXbbX1X2X3X4X5i0x381210

6、040X41640010-0X512040013Cj Z23000进行一轮计算以后得到下表Cj23000iCbXbbCj z6. 一个更为复杂的建模题某工厂明年根据合同， 每个季度末向销售公司提供产品， 有关信息如表，若当季生产的 产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费 0.2万元。现该厂考虑明 年的最佳生产方案， 使该厂在完成合同的情况下， 全年的生产费用最低。 试建立线性规划模 型。季度（j）生产能力佝）生产成本（dj）需求量（bj）1301520240142032015.33041014.810Chapter 3对偶理论与灵敏度分析（4分）、影子价格1）含义：代表在资

7、源最优利用条件下，对第i种资源一单位的估价， 这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而做的估价。2）经济意义? 影子价格反映资源对目标函数的边际贡献，即资源转化成经济效益的效率。? 影子价格反映了资源的稀缺程度。? 影子价格反映了资源的边际使用价值。Chapter 4运输问题（10分）一、确定初始基可行解最小元素法、伏格尔法确定初始可行解的方法考试不要求，但是对于理解最优解的判别很有帮助。厂乡公司经销甲产品"它卩设三个加工厂.每日的产哥分别是：人为7吨. f已为9吨。该公冈把这些产磊分别运往四个销售点。各销宿点毎日销賦为: Bi为3吨民为6吨，風为5吨.艮为6吨.

8、已知从各工厂到各销督点的单位产品的运 价如我4-3所示。问该公司应如何调运产品，在满足各带点的需要量的前提下，便总运矍 为最少.'单位运价表产地销地B1B2B3B4A1311310A21928A374105产销平衡表产地销地产量B1B2B3B4A17A24A39销地3656-?最小元素法思想：从单价中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。Step 1产地销地B1B2B3B4A1311310A21928A374105产地销地产量B1B2B3B4A17A234A39销地3656-Step 2产地销地B1B2B3B4A1311310A21928A374105产地销

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

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

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

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

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

14、问题（选填题）要求：明白求解的逻辑和方法，求解的结果不要求给出? 标准指派问题的数学模型i指派第i个人做第j件事XijW0 I 不指派第i个人做第j件事min Zn ncij xiji 1 j 1Xij 1,i1,2,.ni 1 ns.tXij 1, j 1,2,.nj i%o或iPS: 项任务只能由一个人完成，一个人只能完成一项任务。? 指派问题的匈牙利解法匈牙利法求最优解的理论依据 指派问题最优解的性质：若从系数矩阵（Cj ）的一行（列）各元素中分别减去该行（列）的最小元素，得到新的矩阵（bij）,那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。Step 1使指派问题

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

16、任务可指派。然后划去圈圈所在列的其他0元素，记作。这表示这列所代表的任务已经指派完，不需要再考虑其他人了。Step 2.2 给只有一个0元素列的 0元素加圈圈。这表示这列所代表的这项任务，只有 一个人做。然后划去圈圈所在行的其他 0元素，记作 。这表示这行所代表的人已经被只 拍了任务，对其他的任务不再考虑。Step 2.3 反复进行step 2.1和step 2.2，直到所有的0元素都被圈出和划掉为止。Step 2.4（这一步太复杂，等以后慢慢研究吧）Step 2.5 若画圈圈元素的数目m等于矩阵（方阵）的阶数，那么指派问题的最优解已得到。例题1整数线性规划问题的建模与求解某厂利用集装箱托运甲

17、、乙两种货物，每箱体积重量、可获利润及托运限制如下:体积重量利润甲5220乙4510托运限制2413-两种货物各托运多少箱使利润最大?例题2建模一一人力资源的分配问题（指派问题）有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G R。现有甲、乙、丙、丁 4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？效率矩阵（系数矩阵）Cij人员任务EJGR甲2151314乙1041415丙9141613丁78119例题3指派问题的求解匈牙利解法（有难度）人员任务ABCDE甲127979乙89666丙71712149丁15146610戊

18、4107109Chapter 8 & 9 图与网络分析（ 10 分）一、了解一些图的基本的概念结合图形理解下列概念：? 边、弧：把两点之间不带箭头的连线称为边，带箭头的连线称为弧。? 无向图：如果一个图是由点及边所构成的，则称之为无向图（也简称为图），记为G（ V， E）。? 有向图：如果一个图是由点及弧所构成，则称为有向图，记为D（V， A）。? 无向图的一些名词和记号：（边的）端点、 （点与点）相邻、 （边是点的）关联边、环（两个端点相同的边）、 多重边 （两个点之间有多余一条的边）、 简单图 （无环无多重边的图）、 多重图 （一个 无环，但允许有多重边的图）、次 ：以点 v 为端

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

20、分图 （简称分图)。支撑子图：给一个图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,E)是一个树，p(G) 2，则G中至少有两个悬挂点。PS :图G或图D的点数记为p(G)或p(D)，边(弧)数记为 q(G)或

21、q(D) 图G (V, E)是一个树的充分必要条件是G不含圈，且恰有 p 1条边 图G (V, E)是一个树的充分必要条件是任意两个顶点之间恰有一条链(无论去掉哪一条边，都会变成一个不连通图)三、图的支撑树? 支撑树的定义：设图 T (V,E )是图G (V, E)的支撑子图，如果 T (V, E )是一个树，则称T是G的一个支撑树。? 寻求连通图的支撑树的方法一一破圈法、闭圈法这两种方法的理论支持：图 G有支撑树的充分必要条件是图G是连通的。破圈法:任取一个圈，从圈中去掉一边，对余下的图重复这个步骤， 直到不含圈时为止，即得到一个支撑树。闭圈法:四、最小支撑树问题? 知识准备一一赋权图? 最

22、小支撑树：在所有的支撑树中权最小的树? 最小支撑树的求法避圈法破圈法五、最短路问题? 知识准备一一最短路*1L埼；4(击&経路理论基础：假定(1 , 2) , (2 , 3) , (3 , 4)是点1到4的最短路，则(1,2) , (2 , 3)是点1到3的最短路；(2 , 3) , (3 , 4)是点2到4的最短路。最短路的算法一一双标号(T标号、P标号)算法，也叫狄克斯拉算法Chapter 10 存储论（4分）（选填题）、模型一：不允许缺货、备货时间很短要求：计算最佳经济订购批量、模型的运用条件（假设条件）模型的假设条件1. 缺货费用无穷大；2. 当存储降至零时，可以立即得到补充（

23、模型中不考虑缺货费用）；3. 需求是连续的、均匀的，设需求速度R （单位时间的需求量）为常数，则时间段t内的需求量为Rt ；4. 每次订货量不变，订购费不变；5. 单位存储费不变。衡量存储策略优劣的指标一一总平均费用 最佳的订购时间间隔、经济订购批量、最佳费用1. 最佳的订购时间间隔t2C30,CiR2. 经济订购批量Q曆3. 最佳费用Co2CGR其中，C1是单位时间内单位物品的存储费用，C3是订购费（除了商品价款外的其它费用），R是单位时间的需求量。推导过程如下：总平均费用平均采购费用平均存储费用PS:由于时间t是相同的，所以上式的表达是正确的。采购费用货物价款订购费用KRt C3平均采购费

24、用 KR C3tPS:其中K是货物的单价1 t1平均存储费用 G- RTdT - GRtt 02总平均费用 KR C3 -C-Rtt 2对总平均费用关于t求一阶导，令其为0，得C3 -t：2C3h 2C-R 0，即0 - C-R为最佳订购时间间隔。其他变量的推导相同。PS:由于经济订购批量和最佳订购时间间隔均和货物的单价K无关，所以我们在总费平均用函数中不考虑含有 K的项。即总平均费用¥2C-Rt，代入最佳订购时间间隔均可得最佳费用。? 例题1某厂按合同每年需提供 D个产品，不许缺货。假设每一周期工厂需装配费 C3元，存储费每年每单位产品为 。“元，为全年应分几批供货才能使装配费，存储费两者之和最少? 例题 2 某轧钢厂每月按计划需产角钢 30000