运筹学案例题目及答案

运筹学案例题目及答案一、选择题（每题3分，共15分）1.线性规划问题中，目标函数和约束条件都是线性的，以下哪项不是线性规划问题的特点？A.目标函数是线性的B.约束条件是线性的C.存在非线性约束D.存在线性约束答案：C2.在运输问题中，如果某一货源点的供应量小于某一销地的需求量，那么该货源点的供应量应该被分配给哪些销地？A.所有销地B.需求量小于或等于该货源点供应量的销地C.需求量大于该货源点供应量的销地D.需求量等于该货源点供应量的销地答案：B3.动态规划问题中，最优子结构性质指的是什么？A.问题的最优解包含其子问题的最优解B.问题的最优解不包含其子问题的最优解C.问题的最优解与子问题的最优解无关D.问题的最优解总是唯一的答案：A4.在排队论中，M/M/1队列模型表示什么？A.到达过程为泊松过程，服务时间为指数分布，一个服务台B.到达过程为泊松过程，服务时间为确定时间，一个服务台C.到达过程为泊松过程，服务时间为指数分布，多个服务台D.到达过程为确定时间，服务时间为指数分布，一个服务台答案：A5.网络流问题中，最大流最小割定理说明了什么？A.网络中的最大流量等于最小割的容量B.网络中的最大流量小于最小割的容量C.网络中的最大流量大于最小割的容量D.网络中的最大流量与最小割的容量无关答案：A二、填空题（每题2分，共10分）1.在线性规划问题中，如果目标函数的系数都是正数，那么该问题是一个______问题。答案：最大化2.单纯形法中，如果所有的检验数都是非负的，那么当前的基本可行解是______解。答案：最优3.在动态规划中，如果一个决策问题可以分解为两个或多个子问题，并且子问题的最优解不影响其他子问题的最优解，那么这个问题具有______性质。答案：最优子结构4.在排队论中，如果服务时间是确定的，那么这种服务规则被称为______。答案：确定服务时间5.网络流问题中，如果网络中存在从源点到汇点的增广路径，那么可以通过这条路径增加流量，这条路径称为______路径。答案：增广三、简答题（每题10分，共20分）1.简述线性规划问题的基本特征。答案：线性规划问题的基本特征包括：-目标函数是线性的，即目标函数可以表示为决策变量的线性组合。-约束条件是线性的，即所有的约束条件都可以表示为决策变量的线性不等式或等式。-决策变量是非负的，即所有的决策变量都大于或等于零。-问题的目标是最大化或最小化目标函数。2.描述动态规划问题的基本步骤。答案：动态规划问题的基本步骤包括：-确定问题的阶段：将问题分解为若干个阶段，每个阶段对应一个决策。-确定每个阶段的状态：确定每个阶段可能的状态，即在该阶段可能面临的所有情况。-确定每个阶段的决策：确定每个阶段可能的决策，即在该阶段可以采取的所有行动。-确定状态转移关系：确定从一个状态到另一个状态的转移关系，即一个阶段的决策如何影响下一个阶段的状态。-确定目标函数：确定问题的最终目标，即在最后一个阶段希望达到的状态。-从后向前求解：从最后一个阶段开始，逐步向前求解，直到第一个阶段，得到最优解。四、计算题（每题15分，共30分）1.某工厂生产A、B两种产品，每生产一个A产品需要3个单位的原料1和2个单位的原料2，每生产一个B产品需要2个单位的原料1和1个单位的原料2。工厂现有原料1为100单位，原料2为80单位。生产一个A产品的利润为5元，生产一个B产品的利润为4元。问工厂应该如何安排生产，以获得最大利润？答案：设x为生产A产品的数量，y为生产B产品的数量。则有以下线性规划问题：MaxZ=5x+4ys.t.3x+2y≤100（原料1的限制）2x+y≤80（原料2的限制）x≥0y≥0通过单纯形法求解，得到最优解为x=20，y=20，此时最大利润为Z=180元。2.某公司需要将3个工厂的产品运输到4个仓库，运输成本如下表所示：|工厂/仓库|仓库1|仓库2|仓库3|仓库4||----------|-------|-------|-------|-------||工厂1|4|6|7|5||工厂2|8|3|5|6||工厂3|5|7|4|2|工厂1、2、3的供应量分别为100、150、200，仓库1、2、3、4的需求量分别为120、130、100、150。问公司应该如何安排运输，以使总运输成本最低？答案：设x11、x12、x13、x14、x21、x22、x23、x24、x31、x32、x33、x34分别表示工厂1、2、3运输到仓库1、2、3、4的数量。则有以下线性规划问题：MinZ=4x11+6x12+7x13+5x14+8x21+3x22+5x23+6x24+5x31+7x32+4x33+2x34s.t.x11+x12+x13+x14=100（工厂1的供应量）x21+x22+x23+x24=150（工厂2的供应量）x31+x32+x33+x34=200（工厂3的供应量）x11+x21+x31=120（仓库1的需求量）x12+x22+x32=130（仓库2的需求量）x13+x23+x33=100（仓库3的需求量）x14+x24+x34=150（仓库4的需求量）xij≥0通过单纯形法求解，得到最优解为：x11=0,x12=100,x13=0,x14=0x21=120,x22=0,x23=30,x24=0x31=0,x32=130,x33=70,x34=100此时最小运输成本为Z=3900元。五、案例分析题（每题25分，共25分）某公司有A、B、C三个车间，分别生产产品1、2、3。公司需要将产品运输到D、E、F三个销售点。运输成本如下表所示：|车间/销售点|D|E|F||------------|---|---|---||A|5|7|6||B|4|3|5||C|6|8|7|车间A、B、C的生产量分别为100、150、200，销售点D、E、F的需求量分别为120、130、150。问公司应该如何安排生产和运输，以使总成本最低？答案：设x1、x2、x3分别表示车间A、B、C生产的产品数量，y1、y2、y3分别表示销售点D、E、F的需求量。则有以下线性规划问题：MinZ=5x1+7x2+6x3+4y1+3y2+5y3+6z1+8z2+7z3s.t.x1+y1+z1=100（车间A的生产量）x2+y2+z2=150（车间B的生产量）x3+y3+z3=200（车间C的生产量）x1+x2+x3=120（销售点D的需求量）x1+x2+x3=130（销售点E的需求量）x1+x2+x3