运筹学试卷及参考答案

运筹学试卷B及参照答案（本题20分）一、考虑下面的线性规划问题：Minz=6X1+4X2约束条件：2X1+X2≥13X1+4X2≥3X1,X2≥0用图解法求解,并指出此线型规划问题是具有惟一最优解、无穷多最优解、无界解或无可行解；写出此线性规划问题的原则形式；求出此线性规划问题的两个剩余变量的值；(4)写出此问题的对偶问题。解：（1）阴影部分所示ABC即为此线性规划问题的可行域。其中，A（0，1），B（1，3/4），C（1/5，3/5）。显然，C（1/5，3/5）为该线性规划问题的最优解。因此，该线性规划问题有唯一最优解，最优解为：。X2X2BX10BX10AL1AL1CCL2L2——8分。阐明：画图对的3分；求解对的3分；指出解的状况并写出最优解2分。（2）原则形式为：——4分（3）两个剩余变量的值为：——3分（4）直接写出对偶问题如下：——5分（本题10分）二、前进电器厂生产A、B、C三种产品，有关资料下表所示：产品材料消耗/（kg/件）台时消耗/（台时/件）产品利润/（元/件）市场容量/件A2.028200B1.51.510250C5.01.212100资源限制3000kg1000台时在资源限量及市场容量容许的条件下，怎样安排生产使获利最多？（只建立线性规划数学模型，不求解）解：设生产A、B、C三种产品的数量分别为x1，x2和x3，则有：——1分 ——14分，目的函数和每个约束条件2分（本题10分）三、某电子设备厂对一种元件的年需求为件，订货提前期为零，每次订货费为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）1500I1500I1（不合格），P(I1)=0.815001500SS1I2I2（不合格），P(I2)=0.2检验1500检验1500决决策I1I1（不合格），P(I1)=0.81500210015002100不检查不检查SS2II2（不合格），P(I2)=0.245004500由图阐明应选择不检查。——7分（本题15分）六、某工厂生产三种产品，多种产品重量与利润关系如下表所示。现将此三种产品运往市场发售，运送能力总重量不超过10吨，问怎样安排运送使总利润最大？（背包问题,用动态规划的措施求解）产品重量与利润的关系种类重量（吨/件）利润（元/件）121002314034180单位：万元解：将问题按产品种类分为三个阶段设sk＝分派给第k种产品到第三种产品的总重量（k＝1，2，3）；Xk＝分派给第k种产品的数量S1＝10，s2＝s1－2x1S3＝s2－3x2S3＝4x3基本方程为：——3分（1）当k＝3时，s3＝4x3X3S3*01200——0010——0020——0030——0040180—180150180—180160180—180170180—18018018036036029018036036021001803603602——3分（2）当k＝2时，X2S2＋*012300+0=0———0010+0=0——0020+0=0———0030+0=0140+0=140——140140+180=180140+0=140——180050+180=180140+0=140——180060+180=180140+0=140280+0=280—280270+180=180140+180=320280+0=280—320180+360=360140+180=320280+0=280—360090+360=360140+180=320280+0=280420+0=4204202100+360=360140+180=320280+180=460420+0=4204601——3分（3）当k＝1时，X1S1＋*012345100+460=460100+360=460200+280=480300+180=480400+0=400500+0=5005005——3分当*=5时，，*=0，，*=0，即运送第一种产品5件，最优值为500元。——3分(本题15分)七､如下图，从V0派车到V8中间可通过V1，V2，V3，V4，V5，V6，V7各站，若各站间道路旁的数字表达单位时间内此路上所能通过的最多车辆数，问应怎样派车才能使单位时间抵达V8的车辆最多?解：此为一种网络的最大流问题，用麦克逊标号法求解。首先需要对网络的标号进行改善。（1）选择路为v0—v2—v5—v8010V010V5010V010V2101001010010V8v10V8v0（2）选择途径v0—v3—v7—v820V820V8v0v0202003025303020V7V320V7V330V8（3）选择途径v0—v3—v6—v7—v30V840150