运筹学期末试题

2008─2009学年 第 2学期 《 运筹学 》课程考试试卷( A卷)

专业：管理大类年级：2007考试方式：闭卷 学分：3 考试时间：120 分钟

题号 一 二 三 四 五 六 七 总分 阅卷人 得分

一、某厂生产甲、乙两种产品，需要A、B两种资源，有关资料如下：（共25分）

单位消产品

资源 甲 乙 资源最大供应 量

A 2 1 40 B 1 3 30

单位产品利润 3 4

（1） 利用单纯性法求使工厂获利润最大的生产计划。（10分）

（2） 资源A、B的影子价格是多少？（5分）

（3） 若决策者要求 a） 利润尽量高（第一目标）

a) A材料要充分利用，能不买就尽量不买（第二目标）

b) 甲乙产品的生产量尽量保持1：1的比例（第三目标）

试列出该目标规划问题的模型。（10分）

二、已知如下的运输问题（20分）

用表上作业法求该运输问题的最优调运方案

销地 单位运价 甲 乙 丙 丁 产量 产地 6 4 2 8 7 5 9 6 5 10 7 5 8 8 3 5 8 9 7 24 1 2 3 销量

三、已知线性规划问题（15分）

max z ＝3x1＋4x2 －x1＋2x2≤8 x1＋2x2≤12 2x1＋ x2≤16 x1, x2≥0

（1）写出其对偶问题

**

(2)若其该问题的最优解为，x1=20/3, x2=8/3，试用对偶问题的性质，求对偶问题的最优解。

四、 求如下图网络的最大流，并找出最小截集和截量。每弧旁的数字是（Cij ,fij）(15分)

v1 （7，4） v3

（8，8） （3，1） （8，6）

vs （3，3） （3，0） vt

（9，4） （2，2） （9，6）

v2 （5，5） v4

五、用动态规划方法求解下列非线性规划问题(15分)

max z ＝x1 x22 x3

x1＋x2＋x3 =8

xj≥0 （j＝1,2,3）

六、用匈牙利法求解下列指派问题（10分）

有四份工作，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们每人做各项工作所需时间如下表所示，问若每份工作只能一人完成，每人只能完成一份工作，如 何分派任务，可使总时间最少？

任务 人员

A B C D

4

5

9

8

甲

乙

7

8

11

2

丙

5

9

8

2

丁

3

1

11

4

《运筹学》A卷标准答案

一、解：(1)单纯形法 （10分）

建立模型：max z = 3x1+4x2

2x1+x2 ≤ 40 x1 +3x2≤30

xj≥ 0 j = 1,2

首先，将问题化为标准型。加松弛变量x3，x4，得

maxz3x14x22x1x2x340 stx13x2x430x0,j1,...,4j

其次，列出初始单纯形表，计算最优值。 CB 0 0 σj 0 4 σj 4 3 σj XB x3 x4 x3 x2 x1 x2 3 x1 2 1 3 [5/3] 1/3 5/3 1 0 0 4 x2 1 [3] 4 0 1 0 0 1 0 0 x3 1 0 0 1 0 -2 3/5 -1/5 -1 0 x4 0 1 0 -1/3 1/3 -4/3 -1/5 2/5 -1 b 40 30 30 10 18 4 θ 40 10 18 30 由单纯形表一得最优解为x(18,4)T,z*70.

(2)有（1）的最有表可知，线性规划问题的对偶问题的最优解为：Y*=（1，1），即 A材料的影子价格为1元，B材料的影子价格为1元。 （5分） （3）目标规划问题的模型： （10分） minzP1d1P2(d2d2)P3(d3d3)3x14x2d1d1702x1x2d2d240 stx1x2d3d30x1,x20,di,di0,(i1,2)

二、解：该问题为运输供需平衡问题。 （20分）

 甲 销地 乙 丙 丁 产量 1 单位运价 产地 6 4 2 7 5 9 5 10 7 8 8 3 8 9 7 24 供应量 8 9 7 24 8 6 5 5 用最小元素法找出初始基本可行解： 甲 乙 丙 丁 1 （6） （7） 5（5） 3（8） 2 3 销量 2 3 1（4） 7（2） 8 6(5) (9) 6 (10) (7) 5 2 (8) (3) 5 需要量 用闭回路法求非基变量的σij,

σ11=2, σ12=2,σ23=5, σ32=6, σ33=4, σ34=-3,

对闭回路：x34- x24- x21- x31做运量调整，调整量为2，得 1 甲 （6） 3（4） 5（2） 8 乙 （7） 6(5) (9) 6 丙 5（5） (10) (7) 5 丁 3（8） (8) 2(3) 5 供应量 8 9 7 24 2 3 需要量 σ11=-1, σ12=-1,σ23=8, σ24=2, σ32=6, σ33=7, 对闭回路：x11- x14- x34- x31做运量调整，调整量为3，得 1 甲 3（6） 3（4） 乙 （7） 6(5) 丙 5（5） (10) 丁 （8） (8) 供应量 8 9 2 3 2（2） (9) (7) 5(3) 7 需要量 8 6 5 5 24 求得所有检验数σij≥0,且σ12=0，所以该问题有多重最优方案。 所以，最终的运量表即为此运输问题的一个最优方案， 其最小运输成本为：104元。

三、解：

（1）对偶问题模型

Min w = 8y1+12y2+16y3

-y1 + y2 +2 y3 ≥ 3 2y1 +2 y2 +y3 ≥ 4

yj≥ 0 j = 1,…, 3

（5分） （2）将x1*=20/3,x2*=8/3 代入原问题约束条件，得（1）为严格不等式，xs1>0,由互补松弛性YXs*=0得y1=0；

*

又因为x1, x2>0，由互补松弛性 YsX=0，得Ys1=Ys2=0，即 原问题约束条件应取等号，故 -y1 + y2 +2 y3 = 3

2y1 +2 y2 +y3 = 4 y1 = 0

解之得 y1=0

y2=5/3 y3=2/3

T

所以对偶问题最优解为Y*=(0, 5/3, 2/3)，目标函数最优值为 Z*=92/3。

（10分） 四、最大流问题（参考）

v1 （7，4） v3

（8，8） （3，1） （8，6）

vs （3，3） （3，0） vt

（9，4） （2，2） （9，6）

v2 （5，5） v4

v1 （7，6） v3 （8，8） （3，2） （8，8）

vs （3，0） （3，0） vt

（9，7） （2，2） （9，7） v2 （5，5） v4

最大流为15。 （10分） 最小截集为{（vs, v1）,(v2, v3), (v2 , v4) }的弧集，最小截量为15。 （5分）

五、解：该问题的阶段数为：3，设状态变量为s1、s2、s3，取问题的变量x1、x2、x3为决策变量；

各阶段指标函数按乘积方式结合。令最有函数f k（sk）表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。

设： s3= x3 ，s3+ x2= s2 ，s2+ x1= s1

得： 0≤x3≤s3 ，0≤x2≤s2 ，0≤x1≤s1=8

用逆推法求解： 当k=3时， f3（s3）=当k=2时，f2（s2）=

max0x3s3（x3）= s3及最优解x3= s3 ，

2

2

*

max0x2s2max0x1s1[x2 f3（s3）]= s3[x2 (s2- x2)]，解得

f2（s2）=4/27 * s23最优解x2*= 2s2 /3， 当k=1时，f1（s1）=

[x1 f2（s2）]=

max0x1s1[x1* 4/27*（s1- x1）3]

解得f1（s1）=1/64 * s14最优解x1*= s1 /4， 又已知：s1=8

所以得：x1*= s1 /4=2，f1（s1）=64.

*

由：s2= s1- x1=8-2=6，得：x2= 2s2 /3= 4，f2（s2）=32 ； 由：s3= s2- x2=6-4=2，得：x2*= s3= 2，f3（s3）=2 ；

***

得到最优解为：x1= s1 /4=2，x2= 2s2 /3= 4，x2= s3= 2 最优值为：max z = f1（s1）=64

（15分） 六 解：

475305325891167091181104154 802 2532 2- =41 2167059610400 3

再减去每列最小元素得：

400用最少直线数覆盖0元素，得 3010456403710未覆盖元素减去1，直线交叉点元素加1得 2053020546302700找出独立0元素，如图圈中元素。 1043

所以得到最有指派方案：甲做A；乙做D；丙做C；丁做B。

最工作时间为：15

10分）（

2008─2009学年 第 2学期 《 运筹学 》课程考试试卷( B卷)

专业：管理大类年级：2007考试方式：闭卷 学分：3 考试时间：120 分钟

题号 一 二 三 四 五 六 七 总分 阅卷人 得分

二、某厂生产甲、乙两种产品，需要A、B两种资源，有关资料如下：（共25分）

单位消耗 产品

资源 甲 乙 资源最大供应 量

A 2 1 40 B 1 3 30

单位产品利润 3 4

（4） 利用单纯性法求使工厂获利润最大的生产计划。（10分）

（5） 资源A、B的影子价格是多少？（5分）

（6） 若决策者要求 a） 利润尽量高（第一目标）

a) A材料要充分利用，能不买就尽量不买（第二目标）

b) 甲乙产品的生产量尽量保持1：1的比例（第三目标） 试列出该目标规划问题的模型。（10分）

二、已知如下的运输问题（20分）

用表上作业法求该运输问题的最优调运方案

销地 单位运价 甲 乙 丙 丁 产量 产地 6 4 2 8 7 5 9 6 5 10 7 5 8 8 3 5 8 9 7 24 1 2 3 销量

三、已知线性规划问题（15分）

Min z = 8x1+12x2+16x3 -x1 + x2 +2 x3 ≥ 3 2x1 +2 x2 + x3 ≥ 4

xj≥ 0 j = 1,…, 3

(1) 写出其对偶问题

(2) 若对偶问题的最优解为Y★=(20/3,8/3) ，试用对偶问题的性质，求原问题的最优解。

四、求如下图网络的最大流，并找出最小截集和截量。每弧旁的数字是（Cij, fij）(15分)

v1 （7，4） v3

（8，8） （3，1） （8，6）

vs （3，3） （3，0） vt

（9，4） （2，2） （9，6） v2 （5，5） v4

五、用动态规划方法求解下列非线性规划问题(15分)

max z ＝x1 x22 x3

x1＋x2＋x3 =8

xj≥0 （j＝1,2,3）

六、用匈牙利法求解下列指派问题（10分）有四份工作，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们每人做各项工作所需时间如下表所示，问若每份工作只能一人完成，每人只能完成一份工作，

如何分派任务，可使总时间最少？

任务 人员

A B C D

4

5

9

8

甲

乙

7

8

11

2

丙

5

9

8

2

丁

3

1

11

4

一、解：(1)单纯形法 （10分）

建立模型：max z = 3x1+4x2

2x1+x2 ≤ 40 x1 +3x2≤30

xj≥ 0 j = 1,2

首先，将问题化为标准型。加松弛变量x3，x4，得

maxz3x14x22x1x2x340 stx13x2x430x0,j1,...,4j

其次，列出初始单纯形表，计算最优值。 CB 0 XB x3 3 x1 2 4 x2 1 0 x3 1 0 x4 0 b 40 θ 40 0 σj 0 4 σj 4 3 σj x4 x3 x2 x1 x2 1 3 [5/3] 1/3 5/3 1 0 0 [3] 4 0 1 0 0 1 0 0 0 1 0 -2 3/5 -1/5 -1 1 0 -1/3 1/3 -4/3 -1/5 2/5 -1 30 30 10 18 4 10 18 30 由单纯形表一得最优解为x(18,4)T,z*70.

(2)有（1）的最有表可知，线性规划问题的对偶问题的最优解为：Y*=（1，1），即 A材料的影子价格为1元，B材料的影子价格为1元。 （5分） （3）目标规划问题的模型： （10分） minzP1d1P2(d2d2)P3(d3d3)3x14x2d1d1702x1x2d2d240 stx1x2d3d30x1,x20,di,di0,(i1,2)

二、解：该问题为运输供需平衡问题。 （20分）

 甲 销地 单位运价 乙 丙 丁 产量 产地 1 6 4 2 7 5 9 5 10 7 5 8 8 3 5 8 9 7 24 供应量 8 9 7 24 8 6 用最小元素法找出初始基本可行解： 1 2 3 销量 甲 （6） 1（4） 7（2） 乙 （7） 6(5) (9) 丙 5（5） (10) (7) 5 丁 3（8） 2 (8) (3) 5 2 3 需要量 8 6 用闭回路法求非基变量的σij,

σ11=2, σ12=2,σ23=5, σ32=6, σ33=4, σ34=-3,

对闭回路：x34- x24- x21- x31做运量调整，调整量为2，得 甲 乙 丙 丁 供应量 1 （6） 3（4） 5（2） 8 （7） 6(5) (9) 6 5（5） (10) (7) 5 3（8） (8) 2(3) 5 8 9 7 24 2 3 需要量 σ11=-1, σ12=-1,σ23=8, σ24=2, σ32=6, σ33=7, 对闭回路：x11- x14- x34- x31做运量调整，调整量为3，得 甲 乙 丙 丁 1 供应量 8 9 7 3（6） 3（4） 2（2） （7） 6(5) (9) 5（5） (10) (7) （8） (8) 5(3) 2 3 需要量 8 6 5 5 24 求得所有检验数σij≥0,且σ12=0，所以该问题有多重最优方案。 所以，最终的运量表即为此运输问题的一个最优方案， 其最小运输成本为：104元。

三、解：

（1）对偶问题模型 （5分）

max w ＝3y1＋4y2 st. －y1＋2y2≤8 y1＋2y2≤12 2y1＋ y2≤16 y1, y2≥0

（2）将y1*=20/3,y2*=8/3 代入约束条件，得（1）为严格不等式，即ys1>0,由互补松弛性YsX*=0得x1*=0；又因为y1, y2>0，

由互补松弛性 Y*Xs=0，得Xs1=Xs2=0，即 原问题约束条件应取等号，故 -x1 + x2 +2 x3 = 3

2x1 +2 x2 +x3 = 4

解之得 x1=0,x2=5/3, x3 =2/3

所以原问题最优解为X*=(0, 5/3, 2/3)T，目标函数最优值为 Z*=92/3。

（10分）

四、最大流问题（参考）

v1 （7，4） v3

（8，8） （3，1） （8，6）

vs （3，3） （3，0） vt

（9，4） （2，2） （9，6）

v2 （5，5） v4

v1 （7，6） v3 （8，8） （3，2） （8，8）

vs （3，0） （3，0） vt

（9，7） （2，2） （9，7）

v2 （5，5） v4

最大流为15。 （10分） 最小截集为{（vs, v1）,(v2, v3), (v2 , v4) }的弧集，最小截量为15。 （5分）

五、解：该问题的阶段数为：3，设状态变量为s1、s2、s3，取问题的变量x1、x2、x3为决策变量；各阶段指标函数按

乘积方式结合。令最有函数f k（sk）表示为第k阶段的初始状态为sk，从k阶段到3阶段所得到的最大值。 设： s3= x3 ，s3+ x2= s2 ，s2+ x1= s1

得： 0≤x3≤s3 ，0≤x2≤s2 ，0≤x1≤s1=12

用逆推法求解： 当k=3时， f3（s3）=当k=2时，f2（s2）=

max0x3s3（x3）= s3及最优解x3= s3 ，

2

2

*

max0x2s23

*

[x2 f3（s3）]= s3[x2 (s2- x2)]，解得

f2（s2）=4/27 * s2最优解x2= 2s2 /3， 当k=1时，f1（s1）=

max0x1s14

[x1 f2（s2）]=

*

max0x1s1[x1* 4/27*（s1- x1）3]

解得f1（s1）=1/64 * s1最优解x1= s1 /4， 又已知：s1=12

*

所以得：x1= s1 /4=3，f1（s1）=324.

由：s2= s1- x1=12-3=9，得：x2*= 2s2 /3= 6，f2（s2）=108 ；

*

由：s3= s2- x2=9-6=3，得：x2= s3= 3，f3（s3）=3 ；

得到最优解为：x1*= s1 /4=2，x2*= 2s2 /3= 4，x2*= s3= 2 最优值为：max z = f1（s1）=324

（15分） 六 解：

7435

85191191182 254 8024- =1 22 3610795106043 0再减去每列最小元素得：

564001042053用最少直线数覆盖0元素，得 3710564001042053未覆盖元素减去1，直线交叉点元素加1得 3710463002051043找出独立0元素，如图圈中元素。 2700

所以得到最有指派方案：甲做D；乙做A；丙做B；丁做C。

最工作时间为：15

10分）（