运筹学试题4答案

运筹学答案与评分标准（试题4）

一、（30分）给出线性规划问题：

max

z2x13x2x3

111

xx31323x31471

st.x1x2x33

333

x1,x2,x30

用单纯形法求最优解，写出最终单纯形表。 试分析下列各种条件下最优解（基）的变化： （1）目标函数中变量x3的系数变为6 ；

12

（2）约束右端项由变为；

33

1

（3）增加一个新的变量x6，P6, c = 7 ；

1

解：将线性规划问题化为：max z2x13x2x30x40x5

6

111xx31323x3x41471

st.x1x2x3x53 （3分）

333

x1,x2,x3,x4,x50

因此，可得如下初始单纯形表：（5分）

最优解为：（1（1）目标函数中变量x3的系数变为6 时，得如下单纯形表，并用单纯形法求解步骤进行计算，其过程如下： 因3≥2≥125

因5/4≥014

因2≥032

得最优解为：（12

（2）约束右端项由变为；有Δb＝

33

将上述结果反映到单纯形表中得：

411411

0Δb = BΔb1101



411311

（4）增加一个新的变量x6，P6, c = 7 ；P6BP61110 1



6

检验数 c6- z6 = 7 - 3*2 = 1 ，将上述结果反映到单纯形表中得：

因x661

评分标准：1. 单纯形法求最优解15分，若结果不正确，但步骤正确可得10分。2.（1）、（2）（3）小题各5分。3. 其他情况酌情给分。

二、（15分）甲、乙、丙三个城市每年需要煤炭分别为320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量分别为A-400万吨，B-450万吨。由煤矿至各城市的单位运价（万元/万吨）如下表，由于需大于供，经研究平衡决定，甲城市供应量可减少0-30万吨，乙城市需求量应全部满足，丙城市供应量应不少270万吨。试求供应量分配完又能使总运费为最低的调运方案。

评分标准：1. 得运输表5分。2. 运输问题求解8分。3.得出最终结论2分4. 其他情况酌情给分。 三、（10分）写出线性规划问题的对偶问题。

max z5x13x26x3

x12x2x3182xx3x16123st.

xxx10312x1,x20,x3无约束

解：其对偶问题为

minw18y116y210y3

y12y2y35

2yyy3123st. y13y2y36y10,y2,y3无约束

评分标准：写出对偶问题的模型即可得10分。

四、（10分）某科学试验卫星拟从下列仪器装置中选若干件装上。有关数据资料见下表。要求： （1）装入卫星的仪器装置总体积不超过V，总重量不超过W； （2）A1与A3中最多安装一件； （3）A2与A4中至少安装一件；

（4）A5与A6或者都安上，或者都不安。总的目的是装上去的仪器装置使该科学卫星发挥最大的试验价值。试建立这个问题的数学模型。

解：此问题的数学模型为：

maxzcjxj

j1

6

6

vjxjVj16

wjxjWj1

st.x1x31

x2x41

x5x6

x1, 安装Aj仪器j0, 否则



评分标准：模型正确即可得10分，其他情况酌情给分。 五、（15分）用匈牙利法求解典型指派问题，已知效率矩阵如下：

4 9 7 9 10

解：

评分标准：1. 本题主要考察学生指派问题的应用。2.变换系数矩阵得5分，求最优解给8分，得出结论给2分，若结果不正确，但步骤正确可得8分。3. 其他情况酌情给分。

六、（20分）某工厂生产三种产品，每种产品重量与利润关系如下表所示。现将此三种产品运往市场出售，运输能力总重量不超过8t，问如何安排运输使总利润最大？

解：设第i种产品装载的件数为xi(i=1,2,3) 。则问题可表示为： max

9 8 5 5 11

3 3 3 3 7

11 10 8 4 10

4 8 6 6 11

z100x1140x2180x3

2x13x24x38



x1,x2,x30且为整数

建立动态规划模型，由于决策变量取离散值，所以可用列表法求解。 当k=1时，

f1(s2)

max

02x1s2,x1为整数

100x1

计算结果见下表：

当k=2时，

f2(s3)

140x2f1(s33x2)

03x2s3,x2为整数

计算结果见下表

当k=3时，

180x3f2(84x3)=max{400,180+200,360}=400 f3(8)

x30,1,2

此时x3*=0，递推可得全部策略为：x1*= 4 ，x2*= 0 ， x3*= 0 。

评分标准：1. 列出动态规划模型5分，求解15分。2. 结果正确，有简单步骤说明即可得满分。3. 若结果不正确，但步骤正确可得10分。4. 其他情况酌情给分。

运筹学答案与评分标准（试题4）

一、（30分）给出线性规划问题：

max

z2x13x2x3

111

xx31323x31471

st.x1x2x33

333

x1,x2,x30

用单纯形法求最优解，写出最终单纯形表。 试分析下列各种条件下最优解（基）的变化： （1）目标函数中变量x3的系数变为6 ；

12

（2）约束右端项由变为；

33

1

（3）增加一个新的变量x6，P6, c = 7 ；

1

解：将线性规划问题化为：max z2x13x2x30x40x5

6

111xx31323x3x41471

st.x1x2x3x53 （3分）

333

x1,x2,x3,x4,x50

因此，可得如下初始单纯形表：（5分）

最优解为：（1（1）目标函数中变量x3的系数变为6 时，得如下单纯形表，并用单纯形法求解步骤进行计算，其过程如下： 因3≥2≥125

因5/4≥014

因2≥032

得最优解为：（12

（2）约束右端项由变为；有Δb＝

33

将上述结果反映到单纯形表中得：

411411

0Δb = BΔb1101



411311

（4）增加一个新的变量x6，P6, c = 7 ；P6BP61110 1



6

检验数 c6- z6 = 7 - 3*2 = 1 ，将上述结果反映到单纯形表中得：

因x661

评分标准：1. 单纯形法求最优解15分，若结果不正确，但步骤正确可得10分。2.（1）、（2）（3）小题各5分。3. 其他情况酌情给分。

二、（15分）甲、乙、丙三个城市每年需要煤炭分别为320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量分别为A-400万吨，B-450万吨。由煤矿至各城市的单位运价（万元/万吨）如下表，由于需大于供，经研究平衡决定，甲城市供应量可减少0-30万吨，乙城市需求量应全部满足，丙城市供应量应不少270万吨。试求供应量分配完又能使总运费为最低的调运方案。

评分标准：1. 得运输表5分。2. 运输问题求解8分。3.得出最终结论2分4. 其他情况酌情给分。 三、（10分）写出线性规划问题的对偶问题。

max z5x13x26x3

x12x2x3182xx3x16123st.

xxx10312x1,x20,x3无约束

解：其对偶问题为

minw18y116y210y3

y12y2y35

2yyy3123st. y13y2y36y10,y2,y3无约束

评分标准：写出对偶问题的模型即可得10分。

四、（10分）某科学试验卫星拟从下列仪器装置中选若干件装上。有关数据资料见下表。要求： （1）装入卫星的仪器装置总体积不超过V，总重量不超过W； （2）A1与A3中最多安装一件； （3）A2与A4中至少安装一件；

（4）A5与A6或者都安上，或者都不安。总的目的是装上去的仪器装置使该科学卫星发挥最大的试验价值。试建立这个问题的数学模型。

解：此问题的数学模型为：

maxzcjxj

j1

6

6

vjxjVj16

wjxjWj1

st.x1x31

x2x41

x5x6

x1, 安装Aj仪器j0, 否则



评分标准：模型正确即可得10分，其他情况酌情给分。 五、（15分）用匈牙利法求解典型指派问题，已知效率矩阵如下：

4 9 7 9 10

解：

评分标准：1. 本题主要考察学生指派问题的应用。2.变换系数矩阵得5分，求最优解给8分，得出结论给2分，若结果不正确，但步骤正确可得8分。3. 其他情况酌情给分。

六、（20分）某工厂生产三种产品，每种产品重量与利润关系如下表所示。现将此三种产品运往市场出售，运输能力总重量不超过8t，问如何安排运输使总利润最大？

解：设第i种产品装载的件数为xi(i=1,2,3) 。则问题可表示为： max

9 8 5 5 11

3 3 3 3 7

11 10 8 4 10

4 8 6 6 11

z100x1140x2180x3

2x13x24x38



x1,x2,x30且为整数

建立动态规划模型，由于决策变量取离散值，所以可用列表法求解。 当k=1时，

f1(s2)

max

02x1s2,x1为整数

100x1

计算结果见下表：

当k=2时，

f2(s3)

140x2f1(s33x2)

03x2s3,x2为整数

计算结果见下表

当k=3时，

180x3f2(84x3)=max{400,180+200,360}=400 f3(8)

x30,1,2

此时x3*=0，递推可得全部策略为：x1*= 4 ，x2*= 0 ， x3*= 0 。

评分标准：1. 列出动态规划模型5分，求解15分。2. 结果正确，有简单步骤说明即可得满分。3. 若结果不正确，但步骤正确可得10分。4. 其他情况酌情给分。