试题1答案

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

一、（30分）已知线性规划问题：

max

z?2x1?x2?x3

?x1?x2?x3?6?st.??2x1?2x2?4

?x,x,x?0?123先用单纯形法求出最优解，再分析在下列条件单独变化的情况下最优解的变化。 （1）目标函数变为 max

z?2x1?3x2?x3 ；

?6??2?（2）约束右端项由??变为??；

?4??4?????（3）增添一个新的约束条件x1?2x3?2。

解：先将问题改写为： max

z??2x1?x2?x3?0x4?0x5

?x1?x2?x3?x4?6?st.??2x1?2x2?x5?4（3分）

?x,x,x,x,x?0?12345列出单纯形表，并用单纯形法求解步骤进行计算，其过程如下：（5分）

cj CB 0 0 基 x4 x5 cj- zj cj CB 2 0 基 x1 x5 cj- zj （1）目标函数变为 max

b 6 16 b 6 4 2 x1 1 -2 2 2 x1 1 0 0 -1 x2 1 2 -1 -1 x2 1 4 -3 1 x3 1 0 1 1 x3 1 2 -1 0 x4 1 0 0 0 x4 1 2 -2 0 x5 0 1 0 0 x5 0 1 0 因2≥1≥0，所以选x1进基，因0≤1，故选x4出基，则得（5分） 得最优解为：（6，0，0），代入目标函数得z = 12。（2分） z?2x1?3x2?x3 时，直接反映到最终单纯形表中得：

cj 2 b 6 16 x1 1 0 0 3 x2 1 4 1 1 x3 1 2 -1 0 x4 1 2 -2 0 x5 0 1 0 基 x1 x5 CB 2 0 cj- zj 得

cj CB 2 基 x1 b 2 因x2的检验数1≥0，所以原最优解已经不是新问题的最优解；选x2进基，因10/3≤6/1，故选x5出基，则

2 x1 1 3 x2 0 1 x3 1/2 0 x4 1/2 0 x5 -1/4

3 x2 cj- zj 4 0 0 1 0 1/2 -3/2 1/2 -5/2 1/4 -1/4 得最优解为：（8/3，10/3，0），代入目标函数得z = 16 。（5分） （2）约束右端项由?Δb? =

??4??6??2??变为??时；有Δb＝??0?? ?4??4????????10???4???4??1BΔb????0????8?

21??????cj CB 2 0 基 x1 x5 cj- zj b 2 8 2 x1 1 0 0 -1 x2 1 4 -3 1 x3 1 2 -1 0 x4 1 2 -2 0 x5 0 1 0 将上述结果反映到单纯形表中得：

此时，上表中的解仍为可行解，故最优解为：（3，0，0），代入目标函数得z = 6 。（5分） （3）增添一个新的约束条件x1?2x3?2。

?2x3?2。 ，得知：原最优解满足新的约束条件，

将原最优解（6，0，0）代入新的约束条件x1所以原最优解还是此时的最优解。（5分）

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

二、（15分）某地区有三个化肥厂，记为A、B、C，其年产量分别为7万吨, 8万吨和3万吨。有四个产粮区需要该种化肥，记为甲、乙、丙、丁，其化肥需求量分别为6万吨, 6万吨, 3万吨和3万吨。已知从各化肥厂到各产粮区的每吨化肥的运价如下表所示(表中单位：元/吨)，试求使总运费最小的运输方案。

产粮区 化肥厂 A B C

解：由题意知：该问题为产销平衡的运输问题，其运输表如下表。（5分）

产粮区 化肥厂 A B C 需量 甲 5 4 8 6 乙 8 9 4 6 丙 7 10 2 3 丁 3 7 9 3 产量 7 8 3 18 甲 5 4 8 乙 8 9 4 丙 7 10 2 丁 3 7 9 由最小元素法求得上述运输问题的初始基可行解，并使用位势法计算非基变量的检验数（括号内），得下表。（8分）

产粮区 化肥厂 A (2) 4 (1) 3 甲 5 乙 8 丙 7 丁 3 7 产量

B 6 C 需量

4 8 (9) 6 2 0 6 9 4 3 10 (3) 2 3 7 8 (3) 9 3 (10) 3 18 在表中，由于所有检验数均大于等于 0 ，所以表中的解就是最优解，其最小运费为 89万元 。即化肥分配计划为：化肥厂A的化肥4单位运往面产粮区乙，化肥厂A的化肥3单位运往产粮区丁，化肥厂B的化肥6单位运往产粮区甲，化肥厂B的化肥2单位运往产粮区乙，化肥厂C的化肥3单位运往产粮区丙，其总费用最小，为89万元 。（2分）

评分标准：1. 得运输表5分。2. 运输问题求解8分。3.得出最终结论2分4. 其他情况酌情给分。 三、（10分）已知某实际问题的线性规划模型为：

max z?100x1?50x2

?10x1?16x2?200 (资源 1)?st.?11x1?3x2?25 (资源 2) ?x,x?0?12

假定重新确定这个问题的目标为：P1：z的值应不低于1900；P2：资源1必须全部利用。将此问题转化为目标规划问题，列出数学模型。 解：

评分标准：模型正确即可得10分，其他情况酌情给分。

四、（15分）需要分派5人去做5项工作，每人做各项工作的能力评分如表所示。应如何分派，才能使总的得分最大？

业务 人员 A1 A2 A3 B1 1.3 0 1.0 B2 0.8 1.2 0 B3 0 1.3 0 B4 0 1.3 1.2 B5 1.0 0 0

A4 A5 0 1.0 1.05 0.9 0 0.6 0.2 0 1.4 1.1 解：首先将求“总的得分最大”问题变为“总的得分最小”问题。选择上表中最大的分数1.4，用1.4减去表中的能力评分得下表：

业务 人员 A1 A2 A3 A4 A5

使用匈牙利方法求上述指派问题的最优解。 第一步:变换系数矩阵。

0 1.3 0.2 1.4 0.1

第二步:确定独立零元素。

◎ 1.3 0.2 1.4 0.1

第三步:继续变换系数矩阵。

0 1.3 0.2 1.3 0

第四步:确定独立零元素。

◎ 1.3 0.2

0.4 Φ 1.1

1.3 ◎ 1.2

1.3 Φ ◎

0.4 1.4 1.3

0.4 0 1.1 0.15 0

1.3 0 1.2 1.3 0.4

1.3 0 0 1.1 1.0

0.4 1.4 1.3 0 0

0.4 Φ 1.1 0.25 0.1

1.3 ◎ 1.2 1.4 0.5

1.3 Φ ◎ 1.2 1.1

0.3 1.3 1.2 ◎ Φ 0.4 0 1.1 0.25 0.1

1.3 0 1.2 1.4 0.5

1.3 0 0 1.2 1.1

0.3 1.3 1.2 0 0

B1 0.1 1.4 0.4 1.4 0.4 B2 0.6 0.2 1.4 0.35 0.5 B3 1.4 0.1 1.4 1.4 0.8 B4 1.4 0.1 0.2 1.2 1.4 B5 0.4 1.4 1.4 0 0.3

1.3 Φ 0.15 ◎

1.3 0.4

1.1 1.0

◎ Φ 已经找到5个独立的零元素，故可以确定指派问题的最优指派方案。即A1去做B1工作, A2去做B3工作, A3去做B4工作, A4去做B5工作, A5去做B2工作；其总的得分为：1.3 + 1.3 + 1.2 + 1.4 + 0.9 = 6.1

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

max z?3x1?2x2?5x3

?x1?2x2?x3?2?x?4x?x?4123??st. ?x1?x2?3

?4x?x?623???x1,x2,x3?0或1解：求解过程可以列表表示如下：

(x1，x2，x3) (0，0，0) (0，0，1) (0，1，0) (0，1，1) (1，0，0) (1，0，1) (1，1，0) (1，1，1) z值 0 5 -2 3 3 8 1 6 约束条件 1 √ √ √ 2 √ √ √ 3 √ √ √ 4 √ √ √ 过滤条件 z≥0 z≥5 z≥8 所以，最优解为：(1，0，1)，最优值为8 。

评分标准：1. 本题主要考察学生对整数规划概念的理解。2.求出整数规划的最优解得10分。3. 若结果不正确，但步骤正确可得8分。4. 其他情况酌情给分。

六、（20分）某厂根据市场预测，确认今后四个月该厂的一种主要产品每月需求量如下表所示，已知每月生产固定费用b=2千元，若当月不生产，则b=0千元；产品成本为c=1千元/万件；存贮费用为h=0.2千元/万件/月；每月最大生产能力为a=5万件；最大存贮能力w=4万件。若第1月初无库存产品，第4月末也不留库存，则该厂应怎样安排生产，才能使今后四个月的总费用最少？

月 需求量（万件） 解：1. 建立模型

令k = 1、2、3、4表示今后四个月的序号。

设sk为第k月初（或第k -1月末）的库存量，xk为第k月的生产量，用dk表示第k月的需求量；则sk+1=sk+xk-dk。设fk（sk,xk)为第k月初到第四月末的生产费用（在库存sk，生产xk）fk*(sk)为第k月初到第四月末的最低生产费用。由题意知：

1 3 2 2 3 3 4 2

?2?xk?0.2sk当xk?0 k = 4,3,2,1 fk(sk,xk)?f*k?1(sk?1)??0.2sk当xk?0?函数基本方程为 f5 (s5)=0 fk*(sk) =

minxk?Xk { fk（sk,xk) } k = 4,3,2,1

Xk = {xk| 0≤xk≤5}

且对于不同阶段，xk还会增加新的约束。 2．逆序递推求解 （1）k=4

由问题假设知，该月末无库存。故s5=0。由状态转移方程等可得如下表： f4(s4,x4) x4 s4 0 1 2 （2）k=3

由状态转移方程等可得如下表： f3(s3,x3) x3 s3 0 1 2 3 4 （3）k=2

由状态转移方程等可得如下表： f2(s2,x2) x2 s2 0 1 2 （4）k=1

由状态转移方程等可得如下表：

0.2s2+ f*3(s3) 0 7.8 1 10.6 10.0 2+x2+0.2s2+ f*3(s3) f*2(s2) 2 11.4 10.8 10.2 3 11.6 11.0 10.0 4 11.8 10.8 10.4 5 11.6 11.2 11.4 10.6 7.8 2 1 0 x*2 0.2s3+ f*4(s4) 0 4.6 4 1 7.4 6.8 4.2 2+x3+0.2s3+ f*4(s4) f*3(s3) 2 8.2 7.6 5.0 3 9.0 8.4 5.8 4 9.2 6.6 5 7.4 7.4 6.6 5.8 4.6 4.0 5 4 3 0 0 x*3 0.2s4 0 0.4 2+x4+0.2s4 f*4(s4) 1 3.2 2 4 4 3.2 0.4 2 1 0 x*4

f1(s1,x1) x1 s1 3 2+x1+0.2s1+ f*2(s2) f*1(s1) 4 5 x*1 0 16.4 16.6 14.8 14.8 5 3. 顺序递推，得出结论。最有解为：x*1=5，x*2=0，x*3=5，x*4=0，f*1=14.8（千元）

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

本文来源：https://www.bwwdw.com/article/avtr.html