2017年南京航空航天大学824运筹学真题答案

南京航空航天大学2017年硕士研究生入学考试初试试题参考答案科目代码:824满分:150分科目名称:运筹学注意:答案仅供参考，建议以批判性的思维进行研读，对比自己所做的答案来思考自己在哪方面是可以改进的，或者寻求更优的解法。一、简要回答下述问题。每小题5分，共30分。1、影子价格在一对线性规划问题和对偶规划问题中，若线性规划问题的某个约束条件右端项常数bi增加一个单位时，所引起的目标函数最优值Z的改变量yi称为第i个约束条件的影子价格，又称为边际价格。互补松弛性若X*,Y*分别是原问题和对偶问题的可行解，则X*,Y*是原问题和对偶问题的最优解的充分必要条件是：Y*Xs=0，YsX*=0(其中Xs,Ys分别是原问题和对偶问题的松弛变量向量)。简述大M法的思想对于加入人工变量的线性规划问题，我们希望人工变量对目标函数取值不受影响，因此只有在迭代过程中，把人工变量从基变量中换出，让它成为非基变量。假定人工变量在目标函数中的价值系数为（—M）（对于极大化目标），M为充分大的正数。这样，只要在基变量中还存在人工变量，目标函数就不可能实现最大化。悲观决策准则悲观准则又称最大最小准则，是一种避险型决策准则，决策者对未来持悲观态度，认为未来将出现最差的自然状态。决策者确定每个方案在最差自然状态下的收益值，然后选择在最差自然状态下带来最多收益的方案。最小生成树设有一个连通图G=(V,E),每一边e=[vi,vj]有一个权w(e)=wij,如果T=(V,E')是G一个支撑树,称E'中所有边的权之和为支撑树T的权，记为w(T):w(T)=连加wij,如果支撑树T'的权w(T')是G所有支撑树中权最小的,则称T'是G最小支撑树。线性规划的基本可行解满足非负条件的基解，即B^-1b>=0时，称X为线性规划的基可行解。二、用单纯形法求解下述线性规划的最优解，并回答下列问题。本题20分。（1）当目标函数中x1的系数在何范围变化时，该问题的最优解不变。（2）当第一个约束条件的右端项系数在范围变化时，目标函数最优值如何变化。解：（1）X1X2X3X4bθj基变量CB2410X3121014040/2X4013103030/1Zj210140Cj-Zj031-1X1210.500.52020/0.5X4002.51-0.51010/2.5Zj210140Cj-Zj031-1X1210-0.20.618X24010.4-0.24Zj241.20.452Cj-Zj00-0.2-0.4最优解为：X=（18,4,0）x1的系数在何（1.33,3）范围变化时，该问题的最优解不变。第一个约束条件的右端项系数在范围变化时，将影响最优解和最优目标函数值。目标函数最优值，Z’在（44,60）范围内变化。三、WL公司的某产品有4个生产基地，现将4个生产基地的产品运往3个城市销售，每件产品统一加价80元进行销售，单位产品的运价如表1所示。4个生产基地甲、乙、丙、丁的产量分别为8万个、16万个、10万个和4万个。3个销售基地A、B、C的需求量为10万个、8万个和16万个。请问如何安排调运方案使其获利最大。本题15分。解：ABCD产量甲88乙1616丙6410丁44销量108164四、某公司4名员工完成任务A、B、C、D的时间见表2，请用匈牙利法求解如何指派方能使总花费时间最小。本题15分。解：五、求解下述问题的最大流和最小截集（图1箭线括号内前面数字为容量，后面数字为流量）。本题15分。解：用求解最大流的标号法进行求解，得到以下增广链：1）A→B→E→I，流量为20；2）A→C→F→G→I，流量为5；3）A→B→D→E→I，流量为5；3）A→C→B→D→E→I，流量为25；4）A→C→B→D→H→I，流量为5；5）A→C→B→F→G→I，流量为10；网络的最小截集为：（E,I）,（D,H）,（F,G）网络的最大流为85+20+30=135。六、某投资公司拟投资建一工厂，初步建设方案有2种，大规模方案为投资300万，小规模方案为投资160万。两个方案的生产期均为10年，每年的损益值及销售状态如表3。请用决策树分析方法选择最优方案。为了适应市场变化，投资公司又考虑了第3种方案，即先小规模投资（投入160万）生产3年，如果销路差则不再追加投资，继续生产7年。如果销路好，再做决定是否投资140万扩建至大规模的方案（总投资300万），生产7年。前3年和后7年的销路状态概率见表4。大小规模的投资损益值见表3。请用决策树分析方法选择最优方案。本题20分。解：七、某公司每月需某种化学品2000瓶，每瓶成本150元，每次订购费为125元，每瓶化学品每年存储费为成本的16%。试求1）若不允许缺货，求最优订货量及最小费用；2）若允许缺货，缺货费为每瓶101元，求最大库存量及最大缺货量。本题15分。解：（1）=144瓶=3464元最优订货量为144瓶，最小费用为3464元。（2）=130=161最大库存量为130瓶，最大缺货量为161-130=31瓶。已知某项目的各工作正常工时、极限工时及相应直接费用如表，网络如图。求：1）计算在正常工时下每个工作的最早开始时间、最迟结束时间、总时差；2）设正常工时下，任务总间接费用为18000元，工期每缩短一天，间接费用可节省330元，求最低成本日程。本题20分。解：（1）工序最早开始最早结束最晚开始最晚结束总时差A→B024103410A→C0300300B→D2446345610C→D305630560C→E305432562D→F567456740E→F547256742（2）A→BA→CB→DC→DC→ED→FE→F正常费用（元）50009000400010000800054006400极限费用（元）7000102004800103009000