《管理运筹学》重点笔记

《管理运筹学》重点笔记第一章绪论1.1管理运筹学的定义与历史管理运筹学（OperationsResearch,OR）是一种通过数学建模、统计分析和其他定量方法来解决复杂决策问题的科学方法。它起源于二战期间，当时盟军为了提高军事行动效率而开始使用数学家们提供的科学建议。战后，这些技术逐渐被应用于商业、工业、政府等多个领域。1.2运筹学在管理中的作用运筹学能够帮助管理者做出更加合理、有效的决策。其主要作用包括：资源优化配置：确保有限资源得到最佳利用。成本控制：通过减少浪费提高经济效益。风险评估：为不确定性环境下的决策提供支持。计划与调度：制定生产计划，优化作业流程。1.3基本概念与术语模型：对现实世界某一部分的抽象表示，用于简化复杂问题。目标函数：衡量方案好坏的标准，通常是一个需要最大化的收益或最小化的成本。约束条件：限制解决方案范围的因素，如预算限制、生产能力等。解：满足所有给定约束条件的可行方案。最优解：在所有可行解中使目标函数达到极值的那个解。1.4运筹学的研究方法定性分析：基于专家意见或经验进行判断。定量分析：运用数学模型求解具体数值结果。仿真模拟：通过计算机程序模拟现实情况以测试不同策略的效果。实验设计：通过控制实验条件来观察变量之间的关系。表1-1运筹学常见研究方法对比方法优点缺点定性分析易于理解和实施；不需要大量数据主观性强；难以精确量化定量分析结果准确可靠；适用于大规模问题需要专业技能；对输入数据敏感仿真模拟可视化效果好；灵活性高计算量大；模型构建复杂实验设计能够直接验证假设实施成本高；可能影响正常运作1.5案例研究：运筹学在实际中的应用供应链管理：优化库存水平，降低物流成本。项目管理：合理安排工期，保证按时完成任务。人力资源管理：合理分配员工工作量，提高工作效率。金融投资：构建投资组合，分散风险同时追求收益最大化。第二章数学规划基础2.1线性规划介绍线性规划（LinearProgramming,LP）是运筹学中最常用的一种优化技术之一。它的目标是在一组线性约束条件下找到使得某个线性目标函数达到极大值或极小值的决策变量值。线性目标函数：Z=c1x1+c2x2+...+cnxnZ=c1​x1​+c2​x2​+...+cn​xn​线性约束条件：ai1x1+ai2x2+...+ainxn≤biai1​x1​+ai2​x2​+...+ain​xn​≤bi​

或

==

或

≥≥其中cj,aij,bicj​,aij​,bi​是已知常数，xjxj​是决策变量。2.2目标函数与约束条件目标函数决定了我们要优化的目标是什么，可以是最小化成本、最大化利润等。约束条件反映了现实中存在的限制因素，比如原材料供应量、工厂产能等。它们确保了所得到的解是实际可行的。2.3可行域与最优解可行域是指所有满足约束条件的点组成的集合。在线性规划问题中，可行域通常是多边形区域。最优解位于可行域内，且对应于目标函数的最优值。如果问题是凸的（对于LP总是成立），那么最优解一定出现在可行域的顶点上。2.4标准形式与非标准形式标准形式通常指目标函数为最大化形式，并且所有的约束都是“小于等于”形式。任何非标准形式的问题都可以转化为标准形式。转换技巧包括引入松弛变量、剩余变量以及人工变量等方法。2.5图解法与代数方法图解法适用于只有两个决策变量的情况。通过绘制各约束条件对应的直线并找出交点来确定可行域，然后根据目标函数的方向找到最优解。代数方法则更通用，特别是当问题涉及更多变量时。它包括了单纯形法等更为复杂的算法。第三章线性规划模型建立3.1模型构建过程建立一个成功的线性规划模型需要经历以下几个步骤：定义决策变量：明确哪些变量是我们想要确定的。确定目标函数：设定我们希望最大化或最小化的数量。列出所有约束条件：识别出所有必须遵守的规则。选择适当的方法求解：根据问题规模和特点选用合适的求解技术。验证结果并作出调整：检查所得解是否符合实际情况，必要时修改模型。3.2实际案例分析考虑一家制造公司需要决定两种产品的生产量以最大化总利润。假设每单位产品A贡献10利润，B贡献10利润，B贡献15利润。公司每天可用于生产的工时为60小时，其中产品A每单位需要2小时工时，B需要3小时工时。另外，由于市场需求限制，产品A的日产量不得超过30单位，B不得超过20单位。决策变量：设xAxA​为产品A的日产量，xBxB​为产品B的日产量。目标函数：Maximize

Z=10xA+15xBMaximize

Z=10xA​+15xB​约束条件：工时限制：2xA+3xB≤602xA​+3xB​≤60产品A需求上限：xA≤30xA​≤30产品B需求上限：xB≤20xB​≤20非负性要求：xA,xB≥0xA​,xB​≥03.3建模技巧与注意事项明确目标：清晰地定义你希望通过模型实现什么。合理假设：基于实际情况做出合理的简化假设。数据准确性：确保使用高质量的数据作为输入。灵活性：设计模型时留有一定的余地以便日后调整。可解释性：最终模型应该容易被非专业人士理解。3.4多目标线性规划简介在许多情况下，决策者可能面临多个相互冲突的目标。例如，在企业运营中既想降低成本又想提高服务质量。此时就需要用到多目标线性规划（Multi-ObjectiveLinearProgramming,MOLP）。MOLP允许同时考虑多个目标函数，通过引入权重系数或者设置优先级等方式来平衡各个目标之间的关系。加权和方法：将多个目标合并成单一目标，每个目标赋予不同的权重。ε-约束法：选定一个主目标进行优化，其余目标作为约束条件处理。层次分析法：根据决策者的偏好构造层次结构，逐层比较各个目标的重要性。第四章单纯形法4.1单纯形算法原理单纯形法（SimplexMethod）是由GeorgeDantzig在1947年提出的一种用来求解线性规划问题的有效算法。该方法基于这样一个观察：线性规划问题的最优解（如果存在的话）必定位于可行域的一个顶点上。因此，单纯形法从一个初始的基本可行解开始，通过一系列迭代逐步移动到相邻的顶点，直到找到最优解为止。基变量与非基变量：在任一时刻，系统中的变量被分为基变量和非基变量两部分。基变量取正值，而非基变量则固定为零。基解：当非基变量均为零时，基变量的值构成了一个基解。基本可行解：如果基解满足所有约束条件（即非负性），则称其为基本可行解。4.2初始基本可行解的选择为了启动单纯形法，我们需要找到一个初始的基本可行解。这可以通过以下几种方式实现：人为添加松弛变量：对于“小于等于”形式的约束条件，加入松弛变量使其变为等式。大M法或两阶段法：当原始问题中没有显而易见的初始基本可行解时采用。表4-1初始基本可行解选择方法比较方法描述适用情况松弛变量法为每个“小于等于”约束添加一个非负松弛变量，使原不等式变成等式。问题自然具有非负约束。大M法在目标函数中引入一个足够大的正数M，与人工变量相关联，以惩罚这些变量的存在。适用于任何形式的约束条件。两阶段法第一阶段寻找一个基本可行解；第二阶段在此基础上求解原始问题。当问题较为复杂时推荐使用。4.3表格形式的单纯形法表格形式的单纯形法（也称为单纯形表）提供了一种直观的方式来展示每次迭代的过程。一个典型的单纯形表包括目标函数的系数、约束条件的系数以及右侧常数项。表格结构：每一行代表一个约束方程，最下面一行表示目标函数。转轴操作：通过选取合适的主元元素进行行变换，使得当前的非基变量进入基集，而相应的基变量退出基集。停止准则：当所有检验数（即目标函数对非基变量的偏导数）都非正时，表明已达到最优解。4.4特殊情况处理退化解：当迭代过程中出现两个或多个基变量同时取零的情况时，称为退化解。这可能导致算法陷入循环。无界解：如果在某次迭代中发现存在检验数大于零且相应列的所有元素均非正，则说明问题无界。多重最优解：当最终单纯形表中某些非基变量的检验数为零时，可能存在无穷多个最优解。第五章对偶理论与灵敏度分析5.1对偶问题的概念对于每一个线性规划问题，都可以构造一个与其相对应的对偶问题。原问题（称为主问题）与其对偶问题之间存在着紧密联系，其中一个问题的最优解可以直接给出另一个问题的信息。弱对偶定理：对偶问题的任意可行解的目标函数值不大于主问题的任意可行解的目标函数值。强对偶定理：如果主问题有最优解，那么其对偶问题也有最优解，并且两者的目标函数值相等。5.2影子价格的意义影子价格是指增加一个单位资源所带来的额外收益。它可以帮助管理者了解每种资源的价值，从而做出更好的资源配置决策。影子价格可以从对偶问题的最优解中直接读取出来。5.3参数变化下的灵敏度分析灵敏度分析旨在研究当问题参数发生变化时，最优解如何随之改变。常见的参数变化包括：目标函数系数的变化：分析目标函数中各变量系数的变动如何影响最优解。约束条件右侧值的变化：探究约束条件右端项的增减对最优解的影响。新增变量或约束：考察新引入变量或约束对现有最优解的冲击。第六章整数规划6.1整数规划的特点与挑战整数规划（IntegerProgramming,IP）是线性规划的一种扩展形式，要求部分或全部决策变量取整数值。这类问题比普通线性规划更为复杂，因为它涉及到离散决策空间。混合整数规划：允许某些变量为连续值，而其他变量必须是整数。0-1整数规划：所有变量仅能取0或1。6.2分枝定界法分枝定界法是一种常用的求解整数规划问题的方法。其核心思想是通过递归地将原问题分解成更小的子问题来搜索整个解空间，同时利用边界估计剔除不可能包含最优解的部分。分支：选择一个未满足整数约束的变量，将其分为两个子问题，分别对应于该变量取值的最大整数部分和最小整数部分。界定：利用线性规划松弛问题的解作为下界，不断更新全局最优解的估计值。6.3割平面法割平面法通过向松弛问题中添加新的有效不等式（即割平面）来逐渐缩小解空间，直至获得整数解。这种方法特别适用于解决具有特殊结构的整数规划问题。Gomory割平面：基于线性规划松弛解的分数部分生成割平面。混合整数割平面：针对混合整数规划问题设计的一类更高效的割平面。6.4应用实例：分配问题、背包问题等分配问题：给定n个人和n个工作岗位，如何分配才能使得总的分配成本最低。这是一个经典的0-1整数规划问题。背包问题：有一系列物品，每个物品都有一定的重量和价值，在不超过背包容量的前提下，如何选择物品才能使总价值最大。这也是一个典型的整数规划问题。第七章动态规划7.1动态规划的基本思想动态规划（DynamicProgramming,DP）是一种通过将复杂问题分解为更小的子问题来求解的技术。其核心在于避免重复计算，通过保存子问题的解来提高效率。动态规划适用于那些具有重叠子问题和最优子结构性质的问题。重叠子问题：大问题可以被分解成一些相同的小问题。最优子结构：一个问题的最优解可以通过其子问题的最优解来构造。7.2状态转移方程状态转移方程描述了如何从前一个状态转移到下一个状态。它是动态规划算法的核心部分，通常以递推公式的形式给出。通过状态转移方程，我们可以逐步构建出整个问题的解。状态：问题在某一时刻的具体状况。决策：从当前状态到下一状态所做的选择。7.3最优子结构性质最优子结构性质意味着一个问题的最优解可以通过其子问题的最优解来构建。这个性质是动态规划得以成功应用的关键。例如，在最短路径问题中，从起点到终点的最短路径必然是由起点到中间点的最短路径加上从中间点到终点的最短路径构成。7.4应用领域概述生产与库存控制：确定每个时期的生产量和库存量，以最小化总成本。资源分配：如何在多个项目之间分配有限的资源，以最大化总收益。网络优化：如在通信网络中选择最优路由，以最小化传输延迟或成本。生物信息学：如DNA序列比对、蛋白质折叠等问题。表7-1动态规划典型应用应用领域问题描述解决方法生产与库存控制确定每个时期的生产量和库存量使用动态规划建立状态转移方程，最小化总成本资源分配在多个项目之间分配有限资源通过动态规划求解，最大化总收益网络优化选择最优路由以最小化传输延迟动态规划算法，如Floyd-Warshall算法生物信息学DNA序列比对动态规划算法，如Smith-Waterman算法7.5典型例子：最长公共子序列最长公共子序列（LongestCommonSubsequence,LCS）问题是动态规划的经典应用之一。给定两个序列X和Y，LCS问题就是要找到一个最长的子序列，使得这个子序列既是X的子序列，又是Y的子序列。状态定义：设dp[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度。状态转移方程：如果X[i]==Y[j]，则dp[i][j]=dp[i-1][j-1]+1否则，dp[i][j]=max(dp[i-1][j],dp[i][j-1])第八章网络分析8.1图论基础图论是研究图（由节点和边组成的数据结构）性质及其应用的一门学科。在运筹学中，图论提供了强有力的工具来解决各种网络优化问题。节点（Vertices）：图中的基本单元，通常表示实体。边（Edges）：连接节点的线段，表示实体间的关系。有向图：边有方向的图。无向图：边没有方向的图。加权图：边带有权重的图。8.2最短路径问题最短路径问题是要找到从一个节点到另一个节点的最短路径。这个问题在运输、通信等领域有着广泛的应用。Dijkstra算法：适用于非负权重的图，通过贪心策略逐步扩展最短路径。Bellman-Ford算法：可以处理负权重的图，但时间复杂度较高。8.3最大流最小割定理最大流问题是要找到从源节点到汇节点的最大流量。最小割是指将图分成两部分，使得从源到汇的流量最小的割。Ford-Fulkerson方法：通过不断寻找增广路径来增加流值，直到找不到增广路径为止。Edmonds-Karp算法：是Ford-Fulkerson方法的一种改进，使用广度优先搜索来寻找增广路径。8.4旅行商问题及其变种旅行商问题（TravelingSalesmanProblem,TSP）是要找到一条经过每个城市恰好一次并返回出发城市的最短路径。这是一个NP难问题。完全图：每一对节点之间都有一条边。近似算法：如最近邻算法、贪心算法等。精确算法：如分支定界法、动态规划等。第九章决策分析9.1不确定性下的决策在现实世界中，许多决策是在不确定性条件下做出的。决策分析提供了一套系统的方法来处理这种不确定性，帮助决策者在不确定环境中做出理性选择。决策树：一种图形化工具，用于表示决策过程中的各种可能性及其结果。期望值：在概率分布下，各种结果的加权平均值。9.2风险态度与效用理论不同的决策者可能对风险有不同的态度。效用理论通过引入效用函数来量化决策者的偏好，从而更好地反映他们的风险态度。风险厌恶：偏好确定性收益而不是预期收益较高的不确定收益。风险中立：对风险无偏好，只关注期望值。风险偏好：偏好高风险高回报。9.3决策树分析决策树是一种树状结构，用于表示决策过程中的各种可能性及其结果。它可以帮助决策者可视化各种选项，并通过计算期望值来选择最优策略。节点类型：决策节点：表示决策者可以选择的行动。机会节点：表示不确定性事件的结果。终端节点：表示最终的结果。反向归纳法：从决策树的末端开始，逐步向根节点回溯，计算每个节点的期望值。9.4贝叶斯决策分析贝叶斯决策分析是一种基于贝叶斯统计的方法，用于在信息不完全的情况下进行决策。它通过先验概率和新信息来更新后验概率，从而改进决策。先验概率：在获取新信息之前的概率估计。似然函数：新信息对先验概率的影响。后验概率：结合先验概率和似然函数得到的新概率估计。第十章排队论10.1排队系统的基本组成部分排队论（QueuingTheory）是研究服务系统中顾客到达和服务时间的随机性对系统性能的影响。排队系统主要由以下几个部分组成：顾客源：产生顾客的源头，可以是人、车辆或其他对象。到达模式：顾客到达系统的规律，可以用到达率（λ）来描述。排队规则：顾客等待服务的方式，如先到先服务（FCFS）、后到先服务（LCFS）等。服务台：提供服务的设施，可以有一个或多个。服务模式：服务时间的分布，通常用服务率（μ）来表示。10.2常见排队模型M/M/1模型：单服务台系统，顾客到达和服务时间均服从泊松分布。M/M/c模型：多服务台系统，顾客到达和服务时间均服从泊松分布。M/G/1模型：单服务台系统，顾客到达时间服从泊松分布，服务时间服从一般分布。G/M/1模型：单服务台系统，顾客到达时间服从一般分布，服务时间服从泊松分布。表10-1常见排队模型及其特性模型到达分布服务分布服务台数量特性M/M/1泊松泊松1简单易分析，广泛应用于实际M/M/c泊松泊松c(c>½)多服务台系统，适用于银行、超市等M/G/1泊松一般1服务时间具有更广泛的分布G/M/1一般泊松1到达时间具有更广泛的分布10.3排队指标的计算平均队长（Ls）：系统中平均的顾客数量。平均等待时间（Ws）：顾客在系统中的平均停留时间。平均队列长度（Lq）：队列中的平均顾客数量。平均等待时间（Wq）：顾客在队列中的平均等待时间。对于M/M/1模型，这些指标可以通过以下公式计算：利用率（ρ）：ρ=λ/μ平均队长：Ls=ρ/(1-ρ)平均等待时间：Ws=1/(μ-λ)平均队列长度：Lq=ρ^2/(1-ρ)平均等待时间：Wq=ρ/(μ-λ)10.4排队系统的优化服务台数量的优化：通过增加服务台数量来减少顾客等待时间。到达率的控制：通过调整顾客到达率来平衡系统负载。服务时间的改进：通过提高服务效率来缩短服务时间。排队规则的优化：选择合适的排队规则以提高系统效率。第十一章存储论11.1库存控制的重要性库存控制是企业管理中的一个重要环节，旨在确保企业在满足客户需求的同时，最小化库存成本。良好的库存控制可以带来以下好处：减少资金占用：降低库存水平，减少资金占用。提高服务水平：及时响应客户需求，提高客户满意度。减少库存损失：避免过期、损坏等导致的损失。11.2经济订购批量模型经济订购批量（EconomicOrderQuantity,EOQ）模型是一种经典的库存控制模型，旨在找到最优的订购批量，以最小化总库存成本。总成本：包括订购成本、持有成本和缺货成本。EOQ公式：Q∗=2DSHQ∗=H2DS​​Q∗Q∗：最优订购批量DD：年需求量SS：每次订购成本HH：单位持有成本11.3安全库存策略安全库存是为了应对需求波动和供应不确定性而设立的额外库存。其目的是防止因缺货而导致的损失。安全库存水平：SS=z⋅σ⋅LTSS=z⋅σ⋅LT​SSSS：安全库存水平zz：服务水平因子（通常取1.65对应95%的服务水平）σσ：需求的标准差LTLT：提前期11.4多阶段存储问题多阶段存储问题是指在多个时间阶段内进行库存决策的问题。这类问题通常需要考虑不同阶段的需求预测、订货成本、持有成本等因素。动态规划方法：通过动态规划方法，可以有效地解决多阶段存储问题，找到最优的库存策略。滚动计划：定期更新库存计划，以适应需求和供应的变化。第十二章预测技术12.1时间序列分析时间序列分析是一种统计方法，用于分析随时间变化的数据，以揭示数据中的趋势、季节性和周期性特征。平稳性：时间序列数据在统计特性上保持不变。趋势：数据随时间的长期变化方向。季节性：数据在特定时间间隔内的重复模式。周期性：数据中非固定的重复模式。12.2平滑技术平滑技术用于消除时间序列中的短期波动，从而更容易识别出数据的趋势和季节性特征。移动平均法：通过计算一段时间内的平均值来平滑数据。简单移动平均：SMAt=1n∑i=0n−1xt−iSMAt​=n1​∑i=0n−1​xt−i​加权移动平均：WMAt=∑i=0n−1wixt−iWMAt​=∑i=0n−1​wi​xt−i​指数平滑法：通过赋予近期数据更高的权重来平滑数据。简单指数平滑：Ft=αxt−1+(1−α)Ft−1Ft​=αxt−1​+(1−α)Ft−1​双指数平滑：用于处理趋势性数据。三指数平滑：用于处理季节性和趋势性数据。12.3趋势预测方法趋势预测方法用于预测时间序列中的长期趋势。线性回归：通过拟合一条直线来预测未来的趋势。多项式回归：通过拟合多项式曲线来预测未来的趋势。指数平滑法：通过指数平滑法来预测未来的趋势。12.4因果关系预测模型因果关系预测模型用于预测一个变量如何受到其他变量的影响。回归分析：通过建立因变量与自变量之间的关系来预测未来的值。多元回归：考虑多个自变量对因变量的影响。时间序列回归：结合时间序列数据和回归分析来预测未来的值。第十三章模拟技术13.1模拟的重要性与局限模拟技术（Simulation）是一种通过建立系统模型并在计算机上运行该模型来研究系统行为的方法。模拟在运筹学中具有重要作用，尤其是在处理复杂、动态和不确定性的系统时。重要性：可视化与理解：帮助决策者直观地理解系统的运作机制。风险评估：通过模拟不同情景来评估风险和不确定性。优化与改进：通过多次模拟来优化系统性能。培训与教育：用于培训和教育目的，帮助用户熟悉系统操作。局限：计算成本：复杂的模拟可能需要大量的计算资源。模型准确性：模拟结果依赖于模型的准确性和输入数据的质量。时间消耗：开发和调试模拟模型可能需要较长时间。13.2随机变量的生成在模拟中，随机变量用于表示系统中的不确定性。生成随机变量的方法主要有：伪随机数生成器：通过算法生成看似随机但实际上可预测的数列。逆变换法：通过累积分布函数（CDF）的逆函数生成随机变量。接受-拒绝法：通过一个易于生成的分布来生成目标分布的随机变量。复合方法：结合多种方法生成复杂分布的随机变量。13.3离散事件模拟离散事件模拟（DiscreteEventSimulation,DES）是一种模拟技术，用于研究系统在离散时间点发生的事件。这种模拟方法特别适用于处理队列、生产系统、交通网络等。基本概念：事件：系统中发生的具体动作或变化。状态：系统在某个时刻的状态。时钟：跟踪模拟的时间。事件列表：按时间顺序排列的事件列表。模拟步骤：初始化：设置初始状态和事件列表。事件处理：从事件列表中取出下一个事件并处理。状态更新：更新系统状态。事件调度：将新事件加入事件列表。终止条件：检查是否满足终止条件，否则返回步骤2。表13-1常见离散事件模拟软件软件名称特点适用场景Arena图形界面友好，易于使用生产系统、物流Simul8快速建模，支持动画制造业、服务业AnyLogic支持多范式建模，灵活性高复杂系统、多学科FlexSim三维可视化，交互性强制造业、物流SimPy开源Python库，编程灵活自定义模拟、研究13.4结果解释与验证统计分析：通过对多次模拟结果进行统计分析，提取有用信息。置信区间：通过置信区间来评估结果的可靠性。敏感性分析：研究输入参数变化对输出结果的影响。验证与确认：确保模型正确反映了现实系统的行为。第十四章多准则决策14.1多属性效用理论多属性效用理论（Multi-AttributeUtilityTheory,MAUT）是一种用于处理多准则决策问题的方法。它通过将多个属性的效用综合起来，形成一个整体效用函数，从而帮助决策者做出最优选择。效用函数：表示决策者对每个属性的偏好程度。加权和：将各个属性的效用值加权求和，得到总效用值。归一化：将不同属性的效用值标准化，以便进行比较。14.2层次分析法层次分析法（AnalyticHierarchyPro