运筹学期末考试复习题及解析

运筹学期末考试复习题及解析各位同学，运筹学作为一门应用性极强的学科，其核心在于运用科学的方法优化决策过程。期末考试临近，本文整理了若干典型复习题，并附上详细解析，希望能助大家梳理知识脉络，巩固学习成果。请务必在理解原理的基础上进行练习，切忌死记硬背。一、线性规划基础例题1：某工厂生产A、B两种产品，需消耗甲、乙两种原材料。已知生产单位A产品需甲材料a单位、乙材料b单位，可获利c元；生产单位B产品需甲材料d单位、乙材料e单位，可获利f元。该厂现有甲材料总量G，乙材料总量H。问如何安排生产，才能使总利润最大？解析：这是一道典型的线性规划建模题。解决此类问题，首先需明确决策变量、目标函数和约束条件。1.决策变量：设生产A产品的数量为x₁，生产B产品的数量为x₂。这里需注意，在实际问题中，若产品不可分割，x₁、x₂应为非负整数，但在建模初步阶段，可先按连续变量处理，后续根据问题要求调整。2.目标函数：总利润最大化。即MaxZ=cx₁+fx₂。3.约束条件：*原材料甲的消耗限制：ax₁+dx₂≤G*原材料乙的消耗限制：bx₁+ex₂≤H*非负约束：x₁≥0,x₂≥04.求解思路：对于两个变量的线性规划问题，可采用图解法直观求解，找到可行域的顶点并计算目标函数值进行比较。对于多变量问题，则需运用单纯形法。在单纯形法中，需准确理解基、基变量、非基变量、检验数等概念，并掌握表格的迭代方法。特别注意，当目标函数求最大值时，检验数均小于等于零时达到最优；若存在无界解或无可行解的情况，也需能从单纯形表中识别。例题2：简述线性规划问题的标准形式及其特点。在将非标准形式转化为标准形式时，针对不同情况（如目标函数为极小化、约束条件为“≥”或“=”、存在自由变量）应如何处理？解析：线性规划的标准形式是求解各类线性规划问题的基础，必须熟练掌握。1.标准形式的特点：*目标函数为最大化（MaxZ）。*所有约束条件均为等式（“=”）。*所有决策变量均为非负（x_j≥0）。*约束条件右端常数项（资源限量）均为非负（b_i≥0）。2.转化方法：*目标函数为极小化（MinZ）：可令Z'=-Z，将问题转化为MaxZ'。*约束条件为“≥”：在不等式左端减去一个非负的松弛变量（也称为剩余变量），将其转化为等式。*约束条件为“≤”：在不等式左端加上一个非负的松弛变量，将其转化为等式。*约束条件为“=”：直接保留，无需添加松弛或剩余变量。*存在自由变量（无符号限制的变量x_k）：可令x_k=x_k'-x_k''，其中x_k'≥0,x_k''≥0，将其代入目标函数和约束条件中替换原自由变量。*若b_i<0：只需将该约束条件两端同时乘以-1，此时不等号方向也需相应改变（若原为“≤”则变为“≥”，反之亦然），然后再按上述方法处理。二、整数规划与目标规划例题3：什么是整数规划？它与线性规划的主要区别是什么？请列举至少两种求解整数规划的常用方法，并简述其中一种方法的基本思想。解析：整数规划是解决实际问题中变量必须取整数值的优化工具。1.定义与区别：整数规划是指决策变量（全部或部分）要求取整数值得线性规划问题。其模型结构与线性规划基本相同，主要区别在于对决策变量的整数约束。这一约束使得整数规划问题的可行域不再是连续的凸集，而是离散的点集，因此求解难度显著增加。2.常用求解方法：*分支定界法：基本思想是将原整数规划问题分解为两个子问题（通过对某个非整数解的变量增加上下界约束，即“分支”），然后分别求解这两个子问题的线性规划松弛问题。通过不断比较各子问题的目标函数界（“定界”），剪去不可能包含最优解的子问题（“剪枝”），逐步缩小搜索范围，最终找到整数最优解。*割平面法：基本思想是在整数规划问题的线性规划松弛问题中，逐步增加一些新的线性约束条件（即“割平面”），这些条件能切割掉松弛问题最优解中不符合整数要求的部分，但不切割掉任何整数可行解。通过不断添加割平面，使松弛问题的最优解最终成为整数解。*0-1整数规划的特殊解法：如隐枚举法，利用变量只能取0或1的特性，通过加入过滤条件等技巧减少枚举的组合数。例题4：某公司拟在若干个候选地点中选择开设分店，每个地点的投资成本和预期年利润不同，且受总预算限制。同时，公司希望至少在A区域和B区域各开设一家，且C地点和D地点不能同时开设。请建立此问题的0-1整数规划模型。解析：0-1整数规划在选址、指派等问题中有广泛应用。*决策变量：设x_j为0-1变量，x_j=1表示选择在第j个地点开设分店，x_j=0表示不选择。*目标函数：MaxZ=Σ(预期年利润_j*x_j)*约束条件：*Σ(投资成本_j*x_j)≤总预算*(A区域地点1的x+A区域地点2的x+...)≥1（A区域至少一家）*(B区域地点1的x+B区域地点2的x+...)≥1（B区域至少一家）*x_C+x_D≤1（C和D不能同时开设）*x_j∈{0,1}建模时，关键在于准确理解并将文字描述的约束条件转化为数学表达式。三、动态规划例题5：简述动态规划的基本思想和基本概念（如阶段、状态、决策、状态转移方程、指标函数、最优值函数等）。动态规划方法的优缺点是什么？解析：动态规划是解决多阶段决策过程最优化问题的有效方法，其核心思想是“最优化原理”。1.基本思想：将一个复杂的多阶段决策问题分解为若干相互关联的单阶段子问题，通过求解这些子问题的最优解来得到原问题的最优解。其理论基础是贝尔曼（Bellman）提出的最优化原理：“一个过程的最优策略具有这样的性质，即无论其初始状态和初始决策如何，其今后诸决策对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。”通俗地说，就是“最优路径的任何子路径都是最优的”。2.基本概念：*阶段：将整个决策过程按时间或空间顺序划分为若干个相互联系的阶段。*状态：描述每个阶段开始时所处的自然状况或客观条件，它应能描述过程的特征并且具有无后效性（即某阶段的状态一旦确定，则此后过程的演变不再受此前各阶段状态及决策的影响）。*决策：在某一阶段，当状态确定后，从该状态出发可选的行动方案。*状态转移方程：描述从一个阶段的某一状态，经过决策后转移到下一阶段某一状态的规律，通常表示为s_{k+1}=T_k(s_k,u_k)。*指标函数：用来衡量决策过程优劣的数量指标，分为阶段指标函数和过程指标函数（包括全过程指标函数和k后部子过程指标函数）。*最优值函数：指从第k阶段的状态s_k出发，采用最优策略到过程结束时所得到的指标函数的最优值，记为f_k(s_k)。3.优缺点：*优点：能够得到全局最优解；可以将一个n维决策问题转化为n个一维决策问题，大大简化计算；能提供一族最优解（即不仅得到全过程的最优解，还能得到各子过程的最优解）。*缺点：没有统一的标准模型和通用的求解方法，需根据具体问题进行具体分析；状态变量的维数不能太高，否则会出现“维数灾难”，导致计算量急剧增加，难以求解。例题6：用动态规划方法求解下面的资源分配问题：某工厂有某种资源总量R，可分配给两个项目。若分给第一个项目数量x，则可获利g(x)；分给第二个项目数量y，则可获利h(y)，其中x+y≤R，x,y≥0，且x,y均为整数。问如何分配资源才能使总利润最大？（请写出详细的建模步骤，包括阶段划分、状态变量、决策变量、状态转移方程、指标函数、基本方程等，并给出求解思路）解析：资源分配问题是动态规划的经典应用。1.阶段划分：将资源分配给两个项目，可划分为两个阶段。第1阶段为分配资源给第一个项目，第2阶段为分配剩余资源给第二个项目。2.状态变量s_k：s_k表示第k阶段初拥有的可分配资源数量。s₁=R，s₃=0（或s₂=R-x₁）。3.决策变量u_k：u_k表示第k阶段分配给第k个项目的资源数量。u₁=x，u₂=y。4.状态转移方程：s₂=s₁-u₁。5.指标函数：阶段指标函数v_k(s_k,u_k)分别为g(u₁)和h(u₂)。过程指标函数采用加法形式，即V₁,₂=v₁(s₁,u₁)+v₂(s₂,u₂)。6.基本方程（最优值函数递归关系式）：*f₂(s₂)=max_{u₂=0tos₂}h(u₂)（边界条件，第二阶段的最优利润）*f₁(s₁)=max_{u₁=0tos₁}[g(u₁)+f₂(s₁-u₁)]（第一阶段的最优利润）7.求解思路：从最后一个阶段（第2阶段）开始向前逆推。对于第二阶段，给定任意可能的s₂，最优的u₂就是使h(u₂)最大的y，此时f₂(s₂)=maxh(y)其中y从0到s₂。然后，回到第一阶段，对于初始状态s₁=R，遍历所有可能的u₁（从0到R），计算g(u₁)+f₂(R-u₁)，取最大值对应的u₁即为分给第一个项目的最优资源量，剩余的s₂=R-u₁即为分给第二个项目的最优资源量。四、图论与网络分析例题7：简述Dijkstra算法的基本思想和步骤，并用其求解一个简单有向图中从某起点到其他各点的最短路径。解析：Dijkstra算法是求解单源最短路径的经典算法，适用于所有边的权值非负的图。1.基本思想：按路径长度递增的顺序，逐步找出从起点v₀到图中其他各顶点的最短路径。算法维持一个已找到最短路径的顶点集合S和一个待确定最短路径的顶点集合T。初始时，S中只包含起点v₀，T中包含其他所有顶点。然后，每次从T中选择一个到v₀路径长度最短的顶点u加入S，并以u为中间点，更新T中剩余顶点到v₀的当前最短路径长度。重复此过程，直至S包含所有顶点。2.具体步骤：*初始化：设起点为v₀。令S={v₀}，T=V\S。对T中每个顶点v，若存在边(v₀,v)，则其距离d(v)=w(v₀,v)；否则d(v)=+∞。d(v₀)=0。*选择与加入：在T中选取一个距离v₀最近的顶点u（即d(u)=min{d(v)|v∈T}），将u加入S。*更新距离：对T中每个顶点v，若存在边(u,v)，且d(v)>d(u)+w(u,v)，则更新d(v)=d(u)+w(u,v)。*重复：重复步骤2和3，直至S包含图中所有顶点，或T中不再有可达顶点。3.示例（此处省略具体图形，同学们可自行绘制一个简单有向图练习）：在解题时，建议列表记录各顶点的当前最短距离、前驱节点，并清晰展示每一步S和T集合的变化以及距离的更新过程。例题8：什么是最大流问题？简述Ford-Fulkerson标号法（增广路算法）的基本思想和步骤。解析：最大流问题是网络流理论的基础。1.最大流问题：在一个具有发点（源点）和收点（汇点）的有向网络中，每条边都有一个最大通过能力（容量），寻求从发点到收点的一条总流量最大的可行流。2.Ford-Fulkerson标号法基本思想：从一个初始可行流（通常为零流）开始，寻找从发点到收点的增广路。增广路是指在当前流的剩余网络中，从发点到收点的一条有向路径。找到增广路后，可沿此路径增加流量，得到一个新的可行流。重复此过程，直至再也找不到增广路，此时的可行流即为最大流。3.标号法步骤（包括标号过程和调整过程）：*标号过程（寻找增广路）：*给发点v_s标号(0,+∞)，前者表示前驱节点，后者表示可增加的最大流量。*对未标号的顶点进行遍历，若存在从已标号顶点u到未标号顶点v的正向边，且边的剩余容量r(u,v)=c(u,v)-f(u,v)>0，则给v标号(u,min(l(u),r(u,v)))，其中l(u)是u的可增流量。*若存在从已标号顶点u到未标号顶点v的反向边，且边的流量f(v,u)>0，则给v标号(-u,min(l(u),f(v,u)))。*若收点v_t被标号，则表明找到一条增广路，转入调整过程。否则，若所有未标号顶点均无法标号，则算法结束，当前流即为最大流。*调整过程（沿增广路增加流量）：*从收点v_t开始，根据标号的第一个数字（前驱节点）反向追踪，找出增广路。*设收点的标号中第二个数字为θ，即增广路的可增流量。*沿增广路对各边的流量进行调整：对正向边，f(u,v)+=θ；对反向边，f(v,u)-=θ。*抹除所有顶点的标号，回到标号过程，对新的可行流继续寻找增广路。五、决策论例题9：什么是不确定型决策？常用的不确定型决策准则有哪些？请分别简述其决策思想，并分析不同准则下决策者的风险偏好。解析：不确定型决