运筹学复习笔记.doc

WORD格式可编辑运筹学复习笔记Part1题型1. 选择题（20分）2. 填空题（40分）3. 建模题（40分）4. 决策问题（20分）5. 运输问题（10分）计算Part2需要掌握的知识点Chapter2线性规划与单纯型法一、线性规划问题（建模）二、求解两个变量的线性规划模型图解法附：图解法的启示1)图解法求解结果的几种可能情况：唯一最优解无穷多最优解无界解（并不是说可行域是无界的线性规划问题的解就一定是无界解）无可行解2)若线性规划问题的可行域非空，则可行域是一个凸集。3)若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点达到。（线性规划问题的基可行解X对应于可行域D的顶点。）-1-专业知识 整理分享三、单纯形法准备知识标准型1)标准型的四个条件目标函数为极大（max）所有的约束条件满足等式所有的决策变量非负右端常数均为非负数2)化为标准型的方法若要求目标函数实现最大化，即maxz=CX。这时只需将目标函数最小化变换求目标函数最大化，即令z=-z，于是得到maxz=CX。这就同标准型的目标函数的形式一致了。约束方程为不等式。这里有两种情况：一种是约束方程为不等式，则可在不等式的左端加入非负松弛变量xj，把原不等式变为等式，0x；j另一种是约束方程为不等式，则可在不等式的左端减去一个非负剩余变量x（也可称松弛变量），把不等式约束条件变为等式约束条件,目标函数中加上k0x(松弛变量).k若变量约束中：xi0，则令xi-xi，得到xi0；若xjR，则令xjx-x，其中xj，xj0，用xi、xj、xj分别代替xi、jjx后得到线j性规划的变量约束均为非负约束。资源限量bi0。四、单纯型法准备知识线性规划问题解的概念1)可行解：满足约束条件式（等式约束、非负约束）的解。2)最优解：使目标函数达到最大值的可行解。3)基：约束方程组的系数矩阵Amn的一个满秩的子矩阵Bmm，B称为线性规划问题的一个基。-2-附：基向量：B矩阵中每一个列向量都称为基向量。基变量：选定的向量（基向量）对应的变量x（可以不止一个）称为基变量，其他的变量i称为非基变量。4)基解：有一个基就可以求出一个基解（运用克莱姆法则）。5)基可行解：满足非负条件式的基解（基解是根据等式约束条件得到的，还没有涉及目标函数和变量非负的约束条件，相当于对一个非齐次线性方程组求解。当这样的基解满足变量非负的约束条件时，我们称它为基可行解。PS：并不一定是最优解。）6)可行基：与基可行解相对应的基称为可行基。7)可行域（可行空间）8)几何性质凸集的概念考题：求基解、判断是否为基可行解、是否为最优解五、线性规划问题的一些性质六、单纯形表（了解，知道如何寻找主元）口诀：最大最小找主元初行变换得新解（新的基可行解）目标函数有改善-3-例题：6. 例2-1线性规划问题建模7. 用图解法求解例2-1中建立的线性规划模型-4-8. 把例2-1中建立的线性规划模型化为标准型9. 指出例2-1中建立模型的基、基变量、基解、基可行解和可行基10. 单纯型表相关的题型c23000jiCBXbBxx2x3x4x510x812100430x1640010-40x120400135cjz23000i-5-进行一轮计算以后得到下表c23000jiCBXbBcjzi11. 一个更为复杂的建模题某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0.2万元。现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立线性规划模型。季度（j）生产能力（a）生产成本（d）需求量（）bjjj1301520240142032015.33041014.810-6-Chapter3对偶理论与灵敏度分析（4分）一、影子价格1)含义：代表在资源最优利用条件下，对第i种资源一单位的估价，这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而做的估价。2)经济意义影子价格反映资源对目标函数的边际贡献，即资源转化成经济效益的效率。影子价格反映了资源的稀缺程度。影子价格反映了资源的边际使用价值。Chapter4运输问题（10分）一、确定初始基可行解最小元素法、伏格尔法确定初始可行解的方法考试不要求，但是对于理解最优解的判别很有帮助。单位运价表销地产地B1B2B3B4A1311310A21928A374105-7-产销平衡表销地产地产量B1B2B3B4A17A24A39销地3656-最小元素法思想：从单价中最小的运价开始确定供销关系，然后次小，一直到给出初始基可行解为止。Step1销地产地B1B2B3B4A1311310A21928A374105销地产地产量B1B2B3B4A17A234A39销地3656-Step2销地产地B1B2B3B4A1311310A21928A374105-8-销地产地产量B1B2B3B4A17A2314A39销地3656-Step3销地产地B1B2B3B4A1311310A21928A374105销地产地产量B1B2B3B4A1437A2314A3639销地3656-口诀：最小运价定方向，需求满足便退出，供给耗尽线划去；余下运价找最小，直到运价全划去，所得必是可行解。伏格尔法最小元素法的缺点：可能开始节省一处的费用，但随后在其他几处要多花几倍的运费。-9-伏格尔法的思想：对差额最大处采用最小运费调运。Step1根据单位运价表分别算出各行和各列的最小运费和次小运费的差额。销地产地行差额B1B2B3B4A13113100A219281A3741051列差额2513-Step2从行和列差额中选出最大者，选择它所在的行或列中的最小元素，确定供给方向。（这一步是对伏格尔法思想的体现）销地产地行差额B1B2B3B4A13113100A219281A3741051列差额2513-销地产地行差额B1B2B3B4A13113100A219281A3741051列差额2512-销地产地行差额B1B2B3B4A13113107A219281A3741051列差额25310-10-销地产地行差额B1B2B3B4A13113103A219281A3741051列差额25310-销地产地产量B1B2B3B4A1527A2314A3639销地3656-口诀：行列运价求差额，差额最大找最小（差额最大行、列处找最小的运价），最小运价定方向；需求满足便退出，供给耗尽线划去；余下步骤均相同，直到运价全划去，所得必是可行解。二、最优解的判别方法闭回路法要求：求检验数、调整方案、往下进行一步（46分）（选填题）最优解的判别方法：计算空格（非基变量）的检验数。当检验数还存在负数时，说明原方案不是最优解，需要继续改进。-11-例题：用闭回路法检验上一步中最小元素法得到的初始基可行解是否为最优解。销地产地产量B1B2B3B4A1437A2314A3639销地3656-闭回路法计算检验数的经济解释：在已给出初始解的上表中，可以从任一空格出发，如（A1，B1），若让A1的产品调匀一吨给B1。为了保持产销平衡，就要依次做调整：在（A1，B3）处减少一吨，（A2，B3）处增加一吨，（A2，B1）处减少一吨，即构成（A1，B1）空格为起点，其他为数字格的闭回路。检验数调整后运费的增减数本例中的检验数为：(1)3(1)3(1)2(1)11(元)，以其他空格为起点可以得到更多的检验数。如果得到的检验数全为正，则说明初始方案无法得到进一步改进，即初始方案为最优解；反之，初始基可行解不为最优，还存在改进的空间。三、运输问题的一些性质基变量的个数（上一个知识点中，通过最小元素法得到的初始基可行解的基变量的个数为6）PS：在产销平衡的运输问题中，基变量的个数产地个数销售个数-1。闭回路的顶点数永远是偶数（只有这样才能保证产销的均衡）Chapter5整数线性规划（20分）一、整数规划问题（建模）：把文字描述分析转化为数学模型整数规划问题：是一类特殊的线性规划问题，是指要求部分或全部决策变量的取值为整-12-数的规划问题。其中，重点掌握整数线性规划问题。二、整数规划问题的决策三、整数线性规划问题的类型纯整数线性规划（重点掌握）全部决策变量都必须取整数值混合整数线性规划决策变量中一部分必须取整数值，另一部分可以不取整数值0-1型整数线性规划（重点掌握指派问题）决策变量只能取0或1（用于表现分析投资还是不投资这类问题）四、人力资源的分配问题（选填题）要求：明白求解的逻辑和方法，求解的结果不要求给出标准指派问题的数学模型1指派第i个人做第j件事xij0不指派第i个人做第j件事nnminZcijxiji1j1nxij1,i1,2,.ni1ns.tx1,jij1,2,.nj1xij01或PS：一项任务只能由一个人完成，一个人只能完成一项任务。指派问题的匈牙利解法匈牙利法求最优解的理论依据指派问题最优解的性质：若从系数矩阵（c）的一ij行（列）各元素中分别减去该行（列）的最小元素，得到新的矩阵（bij），那么以（bij）为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同。-13-Step1使指派问题的系数矩阵经变换，在各行各列中都出现0元素（只有这样才能保证每个人都被分配到任务）。系数矩阵的每行元素减去该行的最小元素；再从系数矩阵的每列元素中减去该列的最小元素；若某行（列）已有0元素，那就不必再减了。Step2进行试指派，以寻求最优解。目标：寻找独立的0元素（位于不同行不同列的0元素），独立的0元素的位置便是需要安排人的地方，这样的安排所需要的总时间最少（总耗费最低）。目标的实现方法：当n（任务数或者人数）较小时观察法、试探法（重点掌握）；当n较大时采用以下步骤寻找0元素：Step2.1从只有一个0元素的行开始，给这个0元素加圈圈。这表示对这行所代表的人，只有一种任务可指派。然后划去圈圈所在列的其他0元素，记作。这表示这列所代表的任务已经指派完，不需要再考虑其他人了。Step2.2给只有一个0元素列的0元素加圈圈。这表示这列所代表的这项任务，只有一个人做。然后划去圈圈所在行的其他0元素，记作。这表示这行所代表的人已经被只拍了任务，对其他的任务不再考虑。Step2.3反复进行step2.1和step2.2，直到所有的0元素都被圈出和划掉为止。Step2.4（这一步太复杂，等以后慢慢研究吧）Step2.5若画圈圈元素的数目m等于矩阵（方阵）的阶数，那么指派问题的最优解已得到。例题1整数线性规划问题的建模与求解某厂利用集装箱托运甲、乙两种货物，每箱体积重量、可获利润及托运限制如下：体积重量利润甲5220乙4510托运限制2413-两种货物各托运多少箱使利润最大？-14-例题2建模人力资源的分配问题（指派问题）有一份中文说明书，需译成英、日、德、俄四种文字，分别记做E、J、G、R。现有甲、乙、丙、丁4人，他们将中文说明书翻译成不同语种的说明书所需的时间如下，问应指派何人去完成何种工作，使所需总时间最少？效率矩阵（系数矩阵）cij人员EJGR任务甲2151314乙1041415丙9141613丁78119-15-例题3指派问题的求解匈牙利解法（有难度）任务人员ABCDE甲127979乙89666丙71712149丁15146610戊4107109-16-Chapter8&9图与网络分析（10分）一、了解一些图的基本的概念结合图形理解下列概念：边、弧：把两点之间不带箭头的连线称为边，带箭头的连线称为弧。无向图：如果一个图是由点及边所构成的，则称之为无向图（也简称为图），记为G（V，E）。有向图：如果一个图是由点及弧所构成，则称为有向图，记为D（V，A）。无向图的一些名词和记号：（边的）端点、（点与点）相邻、（边是点的）关联边、环（两个端点相同的边）、多重边（两个点之间有多余一条的边）、简单图（无环无多重边的图）、多重图（一个无环，但允许有多重边的图）、次：以点v为端点的边的个数称为点v的次，记为d(v)。要求：会计算（数）端点的次、特别注意有环存在时的次（记两次）。悬挂点、悬挂边：次为1的点称为悬挂点、悬挂点的关联边称为悬挂边。孤立点：次为零的点称为孤立点。奇点、偶点：次数为奇的点称为奇点，次数为偶的点称为偶点。链、中间点、圈初等链：中间点均为不同点的链称为初等链（一个点不经过两次）；初等圈：中间点均为不同点的圈称为初等圈。简单链（圈）：链（圈）中含有的边均不相同（同一个边不经过两次）。连通图、不联通图：任何两个点之间至少有一条链的图，否则称为不连通图。连通分图：若G是不连通图，它的每个连通的部分称为G的一个连通分图（简称分图）。支撑子图：给一个图G(V,E)，如果图G(V,E)，使VV及EE，则称G为G的一个支撑子图。有向图的一些名词和记号基础图：设给了一个有向图D(V,A)，从D中去掉所有弧上的箭头就得到一个-17-无向图，称之为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)或q(D)图G(V,E)是一个树的充分必要条件是G不含圈，且恰有p1条边图G(V,E)是一个树的充分必要条件是任意两个顶点之间恰有一条链（无论去掉哪一条边，都会变成一个不连通图）三、图的支撑树支撑树的定义：设图T(V,E)是图G(V,E)的支撑子图，如果T(V,E)是一个树，则称T是G的一个支撑树。寻求连通图的支撑树的方法破圈法、闭圈法这两种方法的理论支持：图G有支撑树的充分必要条件是图G是连通的。破圈法：任取一个圈，从圈中去掉一边，对余下的图重复这个步骤，直到不含圈时为止，即得到一个支撑树。-18-闭圈法：四、最小支撑树问题知识准备赋权图最小支撑树：在所有的支撑树中权最小的树最小支撑树的求法避圈法破圈法五、最短路问题知识准备最短路最短路的算法双标号（T标号、P标号）算法，也叫狄克斯拉算法理论基础：假定(1，2)，(2，3)，(3，4)是点1到4的最短路，则(1，2)，(2，3)是点1到3的最短路；(2，3)，(3，4)是点2到4的最短路。-19-Chapter10存储论（4分）（选填题）一、模型一：不允许缺货、备货时间很短要求：计算最佳经济订购批量、模型的运用条件（假设条件）-20-模型的假设条件12. 缺货费用无穷大；13. 当存储降至零时，可以立即得到补充（模型中不考虑缺货费用）；14. 需求是连续的、均匀的，设需求速度R（单位时间的需求量）为常数，则时间段t内的需求量为Rt；15. 每次订货量不变，订购费不变；16. 单位存储费不变。存储量变化图衡量存储策略优劣的指标总平均费用最佳的订购时间间隔、经济订购批量、最佳费用1. 最佳的订购时间间隔t02C3CR12. 经济订购批量Q02CR3C13. 最佳费用C02C1C3R其中，C1是单位时间内单位物品的存储费用，C3是订购费（除了商品价款外的其它费用），R是单位时间的需求量。推导过程如下：总平均费用平均采购费用平均存储费用PS：由于时间t是相同的，所以上式的表达是正确的。-21-采购费用货物价款订购费用KRtC3平均采购费用KRC3tPS：其中K是货物的单价平均存储费用C11tt0RTdT12CRt1总平均费用C13KRC1Rtt2对总平均费用关于t求一阶导，令其为0，得C13CR21t202C3t0，即CR1为最佳订购时间间隔。其他变量的推导相同。PS：由于经济订购批量和最佳订购时间间隔均和货物的单价K无关，所以我们在总费平均用函数中不考虑含有K的项。即总平均费用C3t12CRt1，代入最佳订购时间间隔均可得最佳费用。例题1某厂按合同每年需提供D个产品，不许缺货。假设每一周期工厂需装配费C3元，存储费每年每单位产品为C元，为全年应分几批供货才能使装配费，存储费两者之和最少？1-22-例题2某轧钢厂每月按计划需产角钢30000吨，每吨每月存储费53元，每次生产需调整及其设备等，共需装配费250000元。现在该厂每月生产角钢一次，生产批量为30000吨。问：是否还有更优的生产批次（批量）？Chapter11&12对策与决策（3040分）一、决策树要求：了解方案枝、状态枝的概念，会用决策树进行决策问题分析；期望值的计算从右往左，决定选择哪个方案-23-二、决策的准则（方法）（一）不确定型决策1)悲观主义（坏中求好）决策准则2)乐观主义（好中求好）决策准则3)等可能性准则4)最小的机会损失（最小的最大后悔值）准则Step1找出各种情况下收益最大的策略；Step2分别计算每一策略下各种情况对应的后悔值（机会损失值），找出其中的最大者为各种策略对应的最大后悔值；Step3比较各个策略的最大后悔值，最大后悔值最小的策略为决策者应该采取的策略。5)折中主义（系数）准则PS：系数越大，越乐观分别用乐观系数和悲观系数对每种策略下对应的最好和最差的得益加权，将各个策略加权得到的得益进行比较，加权得益最大的策略为决策者应该选择的策略。（二）风险型决策1)最大期望收益决策准则用概率对同一种策略下的各种情况的收益加权，对各个策略的期望收益进行比较，期望收益最大的策略为决策者应该选择的策略。2)最小期望机会损失（相对比较复杂）这个方法本质上和最大期望收益决策是一样的，得到的结果也相同。Step1计算每种策略下每种情况对应的机会损失值，机会损失为；供需平衡时的得益与实际供需状况下的得益的差额（必然为正）Step3对上一步得到的差额用概率加权；Step4比较各个策略的加权后得到的期望机会损失，期望机会损失最小的策略为决策者应该选择的策略。-24-（三）贝叶斯决策（后验概率决策）三、决策的分类（按决策的环境分类）确定型风险型不确定型-25-