运筹学第三版试卷及答案

运筹学第三版试卷及答案一、单项选择题（每题2分，共20分）1.线性规划问题的标准形式是（）。A.所有变量都非负B.所有约束条件都是等式C.所有变量都非负，所有约束条件都是等式D.所有变量都非负，所有约束条件都是不等式答案：C2.单纯形法中，若引入人工变量后，最优解中人工变量的值为（）。A.0B.正数C.负数D.任意实数答案：A3.动态规划中，状态转移方程的作用是（）。A.确定最优策略B.确定状态的最优值C.确定状态的次优值D.确定状态的可行值答案：B4.整数规划问题中，变量取值限制为（）。A.任意实数B.任意整数C.非负整数D.非负实数答案：B5.运输问题中，若某条线路的运量为0，则称该线路为（）。A.基线路B.非基线路C.退化线路D.非退化线路答案：B6.目标规划问题中，目标函数是（）。A.最小化目标与实际值之间的偏差B.最大化目标与实际值之间的偏差C.最小化目标与实际值之间的绝对偏差D.最大化目标与实际值之间的绝对偏差答案：A7.网络流问题中，最大流问题的目标是（）。A.最小化成本B.最大化流量C.最小化时间D.最大化利润答案：B8.决策树问题中，期望值的计算方法是（）。A.概率乘以结果值的和B.结果值乘以概率的和C.概率乘以结果值的差D.结果值乘以概率的差答案：A9.敏感性分析中，目标函数系数的变化范围称为（）。A.允许值B.影子价格C.灵敏度D.临界值答案：D10.排队论中，M/M/1队列的特点是（）。A.到达服从泊松分布，服务服从指数分布，单服务台B.到达服从指数分布，服务服从泊松分布，单服务台C.到达服从泊松分布，服务服从指数分布，多服务台D.到达服从指数分布，服务服从泊松分布，多服务台答案：A二、填空题（每题2分，共20分）1.线性规划问题中，目标函数的最优解一定在可行域的______上。答案：顶点2.单纯形法中，如果目标函数的最优值为负无穷，则说明该线性规划问题是______。答案：无界3.动态规划问题中，状态的最优值可以通过______方程来确定。答案：贝尔曼4.整数规划问题中，变量的取值限制为______。答案：整数5.运输问题中，若某条线路的运量为0，则称该线路为______。答案：非基线路6.目标规划问题中，目标函数是最小化目标与实际值之间的______。答案：偏差7.网络流问题中，最大流问题的目标是______流量。答案：最大化8.决策树问题中，期望值的计算方法是概率乘以结果值的______。答案：和9.敏感性分析中，目标函数系数的变化范围称为______。答案：临界值10.排队论中，M/M/1队列的特点是到达服从______分布，服务服从指数分布，单服务台。答案：泊松三、计算题（每题10分，共30分）1.已知线性规划问题的标准形式为：MaxZ=3x1+2x2s.t.x1+x2≤102x1+x2≤15x1,x2≥0请使用单纯形法求解该问题，并给出最优解。答案：首先，将线性规划问题转化为标准形式，添加松弛变量x3和x4，得到：MaxZ=3x1+2x2s.t.x1+x2+x3=102x1+x2+x4=15x1,x2,x3,x4≥0然后，使用单纯形法求解，得到最优解为x1=5，x2=5，x3=0，x4=0，Z=25。2.已知动态规划问题的状态转移方程为：V(k)=max{V(k-1)+3,V(k-2)+2}初始状态V(0)=0，V(1)=1，求V(3)的值。答案：根据状态转移方程，可以计算得到：V(2)=max{V(1)+3,V(0)+2}=max{1+3,0+2}=4V(3)=max{V(2)+3,V(1)+2}=max{4+3,1+2}=7所以，V(3)=7。3.已知整数规划问题：MinZ=x1+2x2s.t.x1+x2≥10x1,x2≥0请使用分支定界法求解该问题，并给出最优解。答案：首先，将整数规划问题转化为线性规划问题，忽略整数约束，得到：MinZ=x1+2x2s.t.x1+x2≥10x1,x2≥0求解线性规划问题，得到最优解x1=10，x2=0，Z=10。然后，使用分支定界法，对x1和x2进行分支，得到两个子问题：子问题1：MinZ=x1+2x2s.t.x1+x2≥10x1≥1x1,x2≥0子问题2：MinZ=x1+2x2s.t.x1+x2≥10x1=0x1,x2≥0求解子问题1，得到最优解x1=1，x2=9，Z=11。求解子问题2，得到最优解x1=0，x2=10，Z=20。比较两个子问题的最优值，选择较小的值，即Z=11，对应的解为x1=1，x2=9。所以，整数规划问题的最优解为x1=1，x2=9，Z=11。四、简答题（每题5分，共30分）1.请简述线性规划问题的基本性质。答案：线性规划问题的基本性质包括：1.线性：目标函数和约束条件都是线性的。2.非负性：所有变量都非负。3.凸性：可行域是一个凸多面体。4.有界性：可行域是有界的。5.极点性：最优解一定在可行域的顶点上。2.请简述单纯形法的基本步骤。答案：单纯形法的基本步骤包括：1.将线性规划问题转化为标准形式。2.引入松弛变量，将不等式约束转化为等式约束。3.选择一个初始基本可行解。4.计算目标函数的系数，确定进入基的变量和离开基的变量。5.进行主元变换，更新基本可行解。6.检查是否达到最优解，如果达到，则停止；否则，返回步骤4。3.请简述动态规划问题的基本思想。答案：动态规划问题的基本思想是将复杂问题分解为一系列简单问题，通过求解简单问题来求解复杂问题。具体步骤包括：1.确定问题的状态和决策。2.确定状态转移方程。3.确定初始状态和边界条件。4.根据状态转移方程，从初始状态开始，逐步求解各个状态的最优值。5.根据最优值，确定最优策略。4.请简述整数规划问题的特点。答案：整数规划问题的特点包括：1.变量的取值限制为整数。2.问题求解难度较大，需要使用特殊的算法，如分支定界法、割平面法等。3.整数规划问题可以转化为线性规划问题，但需要添加额外的约束条件。4.整数规划问题在实际应用中具有重要意义，如资源分配、调度等问题。5.请简述运输问题的基本模型。答案：运输问题的基本模型包括：1.供应点：表示货物的供应地，具有供应量限制。2.需求点：表示货物的需求量，具有需求量限制。3.运输成本：表示从供应点到需求点的运输成本。4.运输量：表示从供应点到需求点的运输量。5.目标函数：最小化总运输成本。6.请简述目标规划问题的基本