《运筹学》期末复习及答案

《运筹学》期末复习及答案运筹学是一门应用数学学科，旨在通过建立数学模型、运用优化方法来解决实际生活中的复杂决策问题。以下为你呈现运筹学期末复习的详细内容及答案。线性规划部分基本概念线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。线性规划问题通常由目标函数和约束条件组成，目标函数是决策者希望最大化或最小化的线性函数，约束条件则是对决策变量的一系列线性不等式或等式限制。例：某工厂生产甲、乙两种产品，生产甲产品需用A原料2千克、B原料1千克；生产乙产品需用A原料1千克、B原料3千克。每生产一件甲产品可获利30元，每生产一件乙产品可获利40元。工厂现有A原料10千克，B原料12千克。问应如何安排生产计划，才能使工厂获得最大利润？设生产甲产品\(x_1\)件，生产乙产品\(x_2\)件。目标函数：\(Z=30x_1+40x_2\)（求最大值）约束条件：\(\begin{cases}2x_1+x_2\leq10\\x_1+3x_2\leq12\\x_1\geq0,x_2\geq0\end{cases}\)求解方法-单纯形法单纯形法是求解线性规划问题的常用方法。其基本思路是从可行域的一个顶点出发，通过迭代的方式逐步找到使目标函数最优的顶点。步骤：1.将线性规划问题化为标准型。对于上述例子，引入松弛变量\(x_3\)和\(x_4\)，将不等式约束化为等式约束：\(\begin{cases}2x_1+x_2+x_3=10\\x_1+3x_2+x_4=12\\x_1\geq0,x_2\geq0,x_3\geq0,x_4\geq0\end{cases}\)目标函数变为\(Z=30x_1+40x_2+0x_3+0x_4\)2.建立初始单纯形表。|\(x_1\)|\(x_2\)|\(x_3\)|\(x_4\)|\(b\)||----|----|----|----|----||2|1|1|0|10||1|3|0|1|12||-30|-40|0|0|0|3.进行迭代计算。选择进基变量（目标函数系数绝对值最大的负系数对应的变量）和出基变量（根据最小比值法则确定），不断更新单纯形表，直到所有检验数非负。经过计算，得到最优解\(x_1=4.8\)，\(x_2=2.4\)，最大利润\(Z=30\times4.8+40\times2.4=240\)元。对偶理论每一个线性规划问题都存在一个与之对偶的线性规划问题。原问题和对偶问题在最优解和最优值方面存在一定的关系。原问题：\(\maxZ=CX\)\(\begin{cases}AX\leqb\\X\geq0\end{cases}\)对偶问题：\(\minW=Yb\)\(\begin{cases}YA\geqC\\Y\geq0\end{cases}\)对偶问题的经济解释是影子价格，它反映了资源的边际价值。运输问题基本概念运输问题是一类特殊的线性规划问题，主要研究如何将某种物资从若干个产地运往若干个销地，在满足各产地供应量和各销地需求量的前提下，使总运输费用最小。例：有三个产地\(A_1\)、\(A_2\)、\(A_3\)，产量分别为50吨、60吨、70吨；有四个销地\(B_1\)、\(B_2\)、\(B_3\)、\(B_4\)，销量分别为30吨、40吨、50吨、60吨。已知各产地到各销地的单位运输费用如下表所示，求总运输费用最小的运输方案。||\(B_1\)|\(B_2\)|\(B_3\)|\(B_4\)||----|----|----|----|----||\(A_1\)|3|1|7|4||\(A_2\)|2|6|5|9||\(A_3\)|8|3|3|2|求解方法-表上作业法1.初始调运方案的确定-西北角法：从运输表的左上角（西北角）开始，依次分配物资，直到满足所有产地的供应量和销地的需求量。-最小元素法：优先选择单位运输费用最小的格子进行分配。以最小元素法为例，首先选择单位运输费用最小的\(A_1B_2\)，分配40吨；然后依次进行分配，得到初始调运方案。||\(B_1\)|\(B_2\)|\(B_3\)|\(B_4\)|产量||----|----|----|----|----|----||\(A_1\)|0|40|10|0|50||\(A_2\)|30|0|30|0|60||\(A_3\)|0|0|10|60|70||销量|30|40|50|60||2.最优性检验采用闭回路法或位势法检验当前调运方案是否最优。如果存在负的检验数，则需要进行调整。3.方案调整根据闭回路法确定调整量，对调运方案进行调整，直到所有检验数非负，得到最优调运方案。图与网络分析图的基本概念图是由顶点和边组成的一种数学结构，用于表示事物之间的关系。无向图中边没有方向，有向图中边有方向。最小支撑树问题最小支撑树是一个连通无向图中权值之和最小的树。常用的求解方法有Prim算法和Kruskal算法。Prim算法：从一个顶点开始，每次选择与已选顶点集合相连的边中权值最小的边，将对应的顶点加入已选顶点集合，直到包含所有顶点。例：有一个无向图，顶点集合\(V=\{v_1,v_2,v_3,v_4,v_5\}\)，边集合\(E\)及边的权值如下表所示，求该图的最小支撑树。|边|权值||----|----||\((v_1,v_2)\)|2||\((v_1,v_3)\)|4||\((v_2,v_3)\)|1||\((v_2,v_4)\)|7||\((v_3,v_4)\)|3||\((v_3,v_5)\)|5||\((v_4,v_5)\)|6|采用Prim算法，从顶点\(v_1\)开始：-第一步：选择边\((v_1,v_2)\)，权值为2。-第二步：在与\(\{v_1,v_2\}\)相连的边中选择权值最小的边\((v_2,v_3)\)，权值为1。-第三步：在与\(\{v_1,v_2,v_3\}\)相连的边中选择权值最小的边\((v_3,v_4)\)，权值为3。-第四步：在与\(\{v_1,v_2,v_3,v_4\}\)相连的边中选择权值最小的边\((v_3,v_5)\)，权值为5。得到最小支撑树的权值为\(2+1+3+5=11\)。最短路问题最短路问题是求图中某一顶点到其他顶点的最短路径。常用的算法有Dijkstra算法（适用于边权非负的情况）和Floyd算法（可处理有负权边但无负权回路的情况）。Dijkstra算法步骤：1.初始化：将起点的距离标记为0，其他顶点的距离标记为无穷大。2.选择距离起点最近且未确定最短路径的顶点，更新其邻接顶点的距离。3.重复步骤2，直到所有顶点的最短路径都确定。整数规划基本概念整数规划是要求决策变量取整数值的线性规划问题。如果所有决策变量都要求取整数，则称为纯整数规划；如果部分决策变量要求取整数，则称为混合整数规划。例：某公司拟投资两个项目\(A\)和\(B\)，项目\(A\)需要投资50万元，预计收益80万元；项目\(B\)需要投资30万元，预计收益50万元。公司现有资金100万元，问应如何选择项目，才能使总收益最大？设选择项目\(A\)为\(x_1\)（\(x_1=0\)或1），选择项目\(B\)为\(x_2\)（\(x_2=0\)或1）。目标函数：\(Z=80x_1+50x_2\)（求最大值）约束条件：\(\begin{cases}50x_1+30x_2\leq100\\x_1,x_2\in\{0,1\}\end{cases}\)求解方法-分支定界法：将整数规划问题分解为一系列子问题，通过对每个子问题的求解和界限的确定，逐步缩小搜索范围，最终找到最优整数解。-割平面法：通过增加线性约束（割平面）来缩小可行域，使得非整数最优解被排除，最终得到整数最优解。对于上述例子，通过枚举法可得：当\(x_1=1\)，\(x_2=1\)时，\(Z=80+50=130\)万元；当\(x_1=1\)，\(x_2=0\)时，\(Z=80\)万元；当\(x_1=0\)，\(x_2=1\)时，\(Z=50\)万元；当\(x_1=0\)，\(x_2=0\)时，\(Z=0\)万元。所以最优方案是选择项目\(A\)和项目\(B\)，最大收益为130万元。排队论基本概念排队论是研究排队系统（又称随机服务系统）的数学理论和方法。排队系统由顾客、服务台、排队规则等要素组成。排队模型通常用符号\(X/Y/Z/A/B/C\)表示，其中\(X\)表示顾客到达间隔时间的分布，\(Y\)表示服务时间的分布，\(Z\)表示服务台的数量，\(A\)表示系统的容量，\(B\)表示顾客源的数量，\(C\)表示排队规则。常见排队模型及指标计算-\(M/M/1\)模型：顾客到达间隔时间服从指数分布，服务时间服从指数分布，单服务台。主要指标：-平均到达率\(\lambda\)：单位时间内到达的顾客数。-平均服务率\(\mu\)：单位时间内服务完的顾客数。-系统的利用率\(\rho=\frac{\lambda}{\mu}\)。-系统中顾客的平均数\(L_s=\frac{\lambda}{\mu-\lambda}\)。-队列中顾客的平均数\(L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}\)。-顾客在系统中的平均逗留时间\(W_s=\frac{1}{\mu-\lambda}\)。-顾客在队列中的平均等待时间\(W_q=\frac{\lambda}{\mu(\mu-\lambda)}\)。例：某银行有一个服务窗口，顾客到达间隔时间服从指数分布，平均每小时到达10人；服务时间也服从指数分布，平均每小时服务15人。求该排队系统的各项指标。\(\lambda=10\)人/小时，\(\mu=15\)人/小时，\(\rho=\frac{\lambda}{\mu}=\frac{10}{15}=\frac{2}{3}\)\(L_s=\frac{\lambda}{\mu-\lambda}=\frac{10}{15-10}=2\)人\(L_q=\frac{\lambda^2}{\mu(\mu-\lambda)}=\frac{10^2}{15\times(15-10)}=\frac{4}{3}\)人\(W_s=\frac{1}{\mu-\lambda}=\frac{1}{15-10}=0.2\)小时\(W_q=\frac{\lambda}{\mu(\mu-\lambda)}=\frac{10}{15\times(15-10)}=\frac{2}{15}\)小时决策论基本概念决策论是研究在不确定或风险情况下如何进行决策的理论和方法。决策问题通常由决策者、决策方案、自然状态和损益值等要素组成。决策准则-乐观准则：决策者对未来持乐观态度，选择在最好自然状态下收益最大的方案。-悲观准则：决策者对未来持悲观态度，选择在最坏自然状态下收益最大的方案。-后悔值准则：先计算每个方案在不同自然状态下的后悔值（该自然状态下的最大收益与该方案收益之差），然后选择最大后悔值最小的方案。例：某企业拟生产一种新产品，有三种生产方案可供选择：\(A_1\)、\(A_2\)、\(A_3\)。市场需求有三种可能状态：畅销、一般、滞销，对应的损益值如下表所示。|方案|畅销|一般|滞销||----|----|----|----||\(A_1\)|80|50|-20||\(A_2\)|60|40|10||\(A_3\)|30|30|30|采用乐观准则，选择方案\(A_1\)（因为在畅销状态下\(A_1\)的收益最大）。采用悲观准则，选择方案\(A