2008-2009学年第二学期《运筹学》期末考试试题B答案

济南大学2008-2009学年第二学期考试试卷（B卷）答案

课程 运筹学 授课教师 常相全,彭伟华 考试时间： 2009年 7月 6日 一、写出下列问题的对偶问题（共10分，每小题5分）

(1).maxz 30y1 20y2 4y3(2).minz 5y1 7y2 4y3

s.t. 2y1 y2 y3 1 2y1 y2 y3 1 y 1 4y2 2y3 33y1 y2 y3 4 y1 2y2 y3 5

s.t. y1 6y2 3y3 2 yy y1 0,2 0,y3 0 1 y2 1

y1

0,y2

0,y3

无约束

二、模型题（20分）

1、建立下列问题的线性规划模型：（10分）

答案：设xij为第i年把资金作第j项投资的资金额。据题意可得： 目标函数：

maxz 0.2x0.5x 11 12 0.2x21 0.6x23 0.2x31 0.4x34

x31 x34 40000 1.5x12 1.2x21

x21 x23 20000 1.2x11x34 10000

x23 30000x12 40000

xij 0

i 1,2,3j 1,2,3,4

（设变量2分，目标函数2分，每个条件1分，非负约束1分）。 2、建立下列问题的整数规划模型：(10分)

（设变量1分，目标函数1分，每个条件1分，0-1约束1分）

当选择 si时令xi=1,否则令xi=0。

10 xi 5

i 1

10

minz

cx1 x7 2 x8Mixi

i 1

x1 x7 (1 x8)M x3 x4 1 x9 x

2

x5 x6 x7 x8 3xi 0or1,i 1,...,10

三、计算题（45分）

1、用单纯形法求解下列线性规划问题：（15分）

答案：X=（4，2，0，0，4）T maxz =14

化标准形3分；初始单纯形表3分；中间转化表3分；最终单纯形表3分；结果说明3分。 2、已知如下线性规划问题及其最优单纯形表，求下列条件单独出现的情况下最优解的变化：（15分）

(1) x*=(9/2,1/2,25/2,0,0)（5分） (2) –1<= c1<=1（5分） (3) x*=(4,0,15,0,1)（10分）

3、用匈牙利求解下列系数矩阵的最小化指派问题（10分）

答案：（计算过程5分，结果3分，目标函数值2分）

0010 0100

0001 最小值为48

100

0

四、图表题（25分）

1、用动态规划顺序解法（标号法）求从A 到E的最短路线及其长度。(10分)

最优路线为：A1—B2—C1—D1—E 长度为19。（图上标注或计算过程8分，最终结果2分。）

3、求下列运输问题的最优解：（15分）

最小元素法解（6分，每个1分）为：x12=10；x14=5；x21=18；x31=2；x33=15；x34=13 检验数为（9分，每个1.5分）：z11=0；z13= 3；z22=2；z23=2；z24=2；z42=3。