2010 至 2011 学年第 2 学期

运筹学 试卷B参考答案

（本题20分）一、考虑下面的线性规划问题：

Min z=6X1+4X2

约束条件： 2X1+X2 ≥1 3X1+4X2≥3 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）为该线性规划问题的最优解。因此，该线性规划问题有唯一最优解，最优解为：x1

?1/5,x2?3/5,z*?18/5。

X2

A

L1

C

L2

X1 0 B

——8分。说明：画图正确3分；求解正确3分；指出解的情况并写出最优解2分。

（2）标准形式为：

minz?6x1?4x2?2x1?x2?x3?1 ??3x1?4x2?x4?3?x,x,x,x?0?1234

1

——4分

?x3?0（3）两个剩余变量的值为：?

?x4?0 ——3分

（4）直接写出对偶问题如下：

maxz'?y1?3y2?2y1?3y2?6??y1?4y2?4?y,y?0?12

——5分

（本题10分）二、前进电器厂生产A、B、C三种产品，有关资料下表所示： 产品 A B C 资源限制 材料消耗/（kg/件） 2.0 1.5 5.0 3000 kg 台时消耗/（台时/件） 2 1.5 1.2 1000台时 产品利润/（元/件） 8 10 12 市场容量/件 200 250 100 在资源限量及市场容量允许的条件下，如何安排生产使获利最多？（只建立线性规划数学模型，不求解）

解：设生产A、B、C三种产品的数量分别为x1，x2和x3，则有：——1分

maxz?8x1?10x2?12x3?2.0x1?1.5x2?5.0x3?3000?2.0x?1.5x?1.2x?1000123?? ?x1?200??x2?250?x3?100???x1,x2,x3?0

（本题10分）三、某电子设备厂对一种元件的年需求为2000件，订货提前期为零，每次

订货费为25元。该元件每件成本为50元，年存储费为成本的20%。如发生供应短缺，可在下批货到达时补上，但缺货损失费为每件每年30元。要求： （1）经济订货批量及全年的总费用；

（2）如不允许发生供应短缺，重新求经济订货批量，并同（1）的结果进行比较。

2

——14分，目标函数和每个约束条件2分

解：（1）求出允许缺货的经济订购批量为：

Q*??2Dc3c1c1?c2c22*2000*2510?301030?116TC?(Q?S)DSc1?c3?c22QQ2Q22

8724000292?*10?*50?*302*1161162*116?2199 ——6分

（2）不允许发生供应短缺的经济订购批量为：

Q*??2Dc3c12*2000*25 10?100比较（1）和（2），允许发生缺货一般比不允许发生缺货有更大的选择余地。

——4分

（本题15分）四、已知某运输问题的产量、销量及运输单价如表。又知B地区需要的115单位必须满足 运输单价 产地 甲 乙 丙 销量 销地 A B C D E 产量 10 20 30 25 15 40 35 115 20 15 40 60 20 30 55 30 40 30 25 70 50 100 130 要求：（1）列出该运输问题的产销平衡及单位运价表； （2）用最小元素法求出此运输问题的初始解。

解：（1）根据题意，需大于供，需要增加一个假想的产地丁，列出产销平衡及单位运价表如下：

3

销地 产地 甲 乙 丙 丁 销量 A 10 20 30 0 25 B 15 40 35 M 115 C 20 15 40 0 60 D 20 30 55 0 30 E 40 30 25 0 70 300 产量 50 100 130 20 300 ——8分

（2）用最小元素法求得初始解（因计算过程中最小元素有多个，可任选其一计算，计算的初始解不唯一）如下： 销地 产地 甲 乙 丙 丁 销量 A 5 20 25 B 45 10 60 115 C 60 60 D 30 30 E 70 70 300 产量 50 100 130 20 300 ——7分

（本题15分）五、某制造厂加工了150个机器零件，经验表明由于加工设备的原因，这一批零件不合格率p不是0.10就是0.30，且所加工的这批量中p等于0.10的概率是0.8，这些零件将被用来组装部件，制造厂可以在组装前按每个零件10元的费用来检验这批零件的每个零件，发现不合格立即更换，也可以不予检验就直接组装，但发现一个不合格品进行返工的费用是100元。

（1）写出这个问题的收益矩阵；

（2）用期望值法求出该厂的最优检验方案； （3）用决策树方法解此题。 解：（1）列出收益矩阵为：

自然状态 方案 S1（检验） S2（不检验） ——4分

4

N1（0.8） 1500 1500 N3（0.2） 1500 4500

（2）

E（S1）=1500*0.8+1500*0.2=1500 E（S2）＝1500*0.8+4500*0.2=2100 故为S1（检验）最优方案。

——4分

（3）

I1（不合格），P(I1)=0.8 1500 1500 S1 I（不合格），P(I2)=0.2 2 1500 检 验 决 策 I（不合格），P(I1)=0.8 1 1500

2100 不检验 S2 I（不合格），P(I2)=0.2 2 4500

由图说明应选择不检验。 ——7分

（本题15分）六、某工厂生产三种产品，各种产品重量与利润关系如下表所示。现将此三种产品运往市场出售，运输能力总重量不超过10吨，问如何安排运输使总利润最大？（背包问题,用动态规划的方法求解）

产品重量与利润的关系

种类 1 2 3 重量（吨/件） 2 3 4 利润（元/件） 100 140 180 单位：万元

解：将问题按产品种类分为三个阶段

设sk＝分配给第k种产品到第三种产品的总重量（k＝1，2，3）； Xk＝分配给第k种产品的数量 S1＝10，s2＝s1－2x1 S3＝s2－3x2 S3＝4x3

基本方程为：

5