运筹学试卷及参考答案.doc

运筹学 试卷B及参考答案（本题20分）一、考虑下面的线性规划问题： Min z=6X1+4X2 约束条件： 2X1+X2 1 3X1+4X23 X1 , X2 0(1) 用图解法求解,并指出此线型规划问题是具有惟一最优解、无穷多最优解、无界解或无可行解；(2) 写出此线性规划问题的标准形式；(3) 求出此线性规划问题的两个剩余变量的值；(4) 写出此问题的对偶问题。解：（1）阴影部分所示ABC即为此线性规划问题的可行域。其中，A（0，1），B（1，3/4），C（1/5，3/5）。显然，C（1/5，3/5）为该线性规划问题的最优解。因此，该线性规划问题有唯一最优解，最优解为：。X2BX10AL1CL2 8分。说明：画图正确3分；求解正确3分；指出解的情况并写出最优解2分。（2）标准形式为： 4分（3）两个剩余变量的值为： 3分（4）直接写出对偶问题如下： 5分（本题10分）二、前进电器厂生产A、B、C三种产品，有关资料下表所示：产品材料消耗/（kg/件）台时消耗/（台时/件）产品利润/（元/件）市场容量/件A2.028200B1.51.510250C5.01.212100资源限制3000 kg1000台时在资源限量及市场容量允许的条件下，如何安排生产使获利最多？（只建立线性规划数学模型，不求解）解：设生产A、B、C三种产品的数量分别为x1，x2和x3，则有：1分 14分，目标函数和每个约束条件2分（本题10分）三、某电子设备厂对一种元件的年需求为2000件，订货提前期为零，每次订货费为25元。该元件每件成本为50元，年存储费为成本的20%。如发生供应短缺，可在下批货到达时补上，但缺货损失费为每件每年30元。要求：（1）经济订货批量及全年的总费用； （2）如不允许发生供应短缺，重新求经济订货批量，并同（1）的结果进行比较。解：（1）求出允许缺货的经济订购批量为： 6分（2）不允许发生供应短缺的经济订购批量为：比较（1）和（2），允许发生缺货一般比不允许发生缺货有更大的选择余地。 4分（本题15分）四、已知某运输问题的产量、销量及运输单价如表。又知B地区需要的115单位必须满足销地运输单价产地ABCDE产量甲乙丙10203015403520154020305540302550100130销量25115603070要求：（1）列出该运输问题的产销平衡及单位运价表；（2）用最小元素法求出此运输问题的初始解。解：（1）根据题意，需大于供，需要增加一个假想的产地丁，列出产销平衡及单位运价表如下： 销地产地ABCDE产量 甲101520204050乙2040153030100丙3035405525130丁0M00020销量25115603070300300 8分（2）用最小元素法求得初始解（因计算过程中最小元素有多个，可任选其一计算，计算的初始解不唯一）如下： 销地产地ABCDE产量 甲54550乙106030100丙6070130丁2020销量25115603070300300 7分（本题15分）五、某制造厂加工了150个机器零件，经验表明由于加工设备的原因，这一批零件不合格率p不是0.10就是0.30，且所加工的这批量中p等于0.10的概率是0.8，这些零件将被用来组装部件，制造厂可以在组装前按每个零件10元的费用来检验这批零件的每个零件，发现不合格立即更换，也可以不予检验就直接组装，但发现一个不合格品进行返工的费用是100元。（1）写出这个问题的收益矩阵；（2）用期望值法求出该厂的最优检验方案；（3）用决策树方法解此题。解：（1）列出收益矩阵为：自然状态方案N1（0.8）N3（0.2）S1（检验）15001500S2（不检验）15004500 4分（2）E（S1）=1500*0.8+1500*0.2=1500E（S2）1500*0.8+4500*0.2=2100故为S1（检验）最优方案。 4分（3）1500I1（不合格），P(I1)=0.81500S1I2（不合格），P(I2)=0.2检 验1500决 策I1（不合格），P(I1)=0.815002100不检验S2I2（不合格），P(I2)=0.24500由图说明应选择不检验。 7分（本题15分）六、某工厂生产三种产品，各种产品重量与利润关系如下表所示。现将此三种产品运往市场出售，运输能力总重量不超过10吨，问如何安排运输使总利润最大？（背包问题,用动态规划的方法求解）产品重量与利润的关系种类重量（吨/件）利润（元/件）121002314034180 单位：万元 解：将问题按产品种类分为三个阶段 设sk分配给第k种产品到第三种产品的总重量（k1，2，3）；Xk分配给第k种产品的数量S110，s2s12x1S3s23x2S34x3基本方程为： 3分（1）当k3时，s34x3X3S3*012000010002000300040180180150180180160180180170180180180180360360290180360360210018036036023分（2）当k2时，X2S2*012300+0=00010+0=00020+0=00030+0=0140+0=140140140+180=180140+0=140180050+180=180140+0=140180060+180=180140+0=140280+0=280280270+180=180140+180=320280+0=280320180+360=360140+180=320280+0=280360090+360=360140+180=320280+0=280420+0=4204202100+360=360140+180=320280+180=460420+0=42046013分（3）当k1时，X1S1*012345100+460=460100+360=460200+280=480300+180=480400+0=400500+0=50050053分当*=5时，*=0，*=0，即运送第一种产品5件，最优值为500元。3分(本题15分)七如下图，从V0派车到V8中间可经过V1，V2，V3，V4，V5，V6，V7各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达V8的车辆最多?解：此为一个网络的最大流问题，用麦克逊标号法求解。首先需要对网络的标号进行改进。 （1）选择路为v0v2v5v80 10V5010V21010010V8v0 （2）选择路径v0v3v7v820V8v02020030253020V7V330V8（3）选择路径v0v3v6v7v8