运筹学 第三章 - 图文

1、运筹学 第三章 - 图文 西安邮电学院试题库管理系统试题表 专业代码 11 专业名称 信息管理与信息系统 课程代码 18 课程名称 运筹学 试题类型代码 08 试题类型名称 计算题 出题人 管理员 出题 日期 难度系数 xxxx年内有五项工程可以考虑投资 设xj?1,投资j项目?0，不投资j项目 最优解x(1,1,1,0,1)，z=110万元。 maxz?30x1?40x2?20x3?15x4?30x5?5x1?4x2?5x3?7x4?8x5?30?x?7x?9x?5x?6x?252345?1?8x1?2x2?6x3?2x4?9x5?30?xj0或1,j?1,5? 求最优解和投资的最大收益 用

2、分枝定界法求解下列整数规划问题 max z=3x1+2 x2 最优解z=14, x1=4, x2=1; ?2x1?3x2?14?st. ?x1?0.5x2?4.5 ?x,x?0且为整数?12 用分枝定界法求解下列整数规划问题 max z=2x1+3 x2 最优解z=14, x1=4, x2=2; ?5x1?7x2?35?4x1?9x2?36?x,x?0且为整数st. ?12 用分枝定界法求解下列整数规划问题 max z=x1+ x2 最优解z=5, x1=5, x2=0;或x1=4, x2=1 ?2x1?5x2?16?st. ?6x1?5x2?30 ?x,x?0且为整数?12 用分枝定界法求下

3、列整数规划。 最优解和最优值如下： maxz?2x1?x2?x1?x2?5?x?x?0 ?12?6x1?2x2?21?x1,x2?0且为整数 用分枝定界法解下列整数规划： x*?(3,1)t,z*?7 最优解和最优值如下： maxz?2x1?3x2?x1?x2?2?47x?8x?188 ?12?3x1?2x2?19?x1,x2?0且为整数 用割平面法求解下列整数规划问题 max z=7x1+9 x2 x*?(3,5)t,z*?21 最优解z=55, x1=4, x2=3; ?x1?3x2?6?st. ?7x1?x2?35 ?x,x?0且为整数?12第 3 页 共 8 页 西安邮电学院试题库管理

4、系统试题表 用割平面法求解下列整数规划问题 max z=4x1+5 x2 最优解z=13, x1=2, x2=1; ?3x1?2x2?7?x?4x?5?12st. ? 3x?x?22?1?x1,x2?0且为整数 用割平面法求解下列整数规划问题 max z=4x1+6 x2+2 x3 最优解z=26, x1=2, x2=1, x3=6; ?4x1?4x2?5?x?6x?5?12st. ? ?x?x?x?523?1?x1,x2,x3?0且为整数 用割平面法求解下列整数规划问题 max z=11x1+4x2 最优解z=34, x1=2, x2=3; ?x1?2x2?4?5x?2x?16?12st.

5、? 2x?x?42?1?x1,x2?0且为整数 分别用割平面法求解以下整数规划问题 maxz?x1?4x2?14x1?42x2?196 ?s.t.?x1?2x2?5?x,x?0且为整数?12 先求解相应的线性规划的最优解： z x1 x2 z x3 x4 z x3 x2 z x1 x2 z 1 0 0 x1 0 1 0 x2 0 0 1 z 1 0 0 x1 -3 35 -1/2 x2 0 0 1 1 0 0 -1 14 -1 -4 42 2 x3 0 1 0 x3 0 1 0 x3 3/35 1/35 1/70 x4 0 0 1 x4 2 -21 1/2 x4 1/5 -3/5 1/5 rh

6、s 0 196 5 rhs 10 91 5/2 rhs 89/5 13/5 19/5 线性规划的最优解为x1=13/5，x2=19/5，max z=89/5。 对于x2=19/5， b2=19/5，i2=3，f2=4/5 y23=1/70，i23=0，f23=1/70；y24=1/5，i24=0，f24=1/5 构造附加的切割约束： 4/5-（1/70x3+1/5x4）0 即 1/70x3+1/5x44/5 z x1 x2 x3 x4 x5 z x1 x2 x5 z x1 x2 x4 用割平面法解下列整数规划： z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 1/14 3

7、/35 0 1/14 x4 0 0 0 1 x5 1 -3 1 -5 1 0 0 0 0 1 0 0 0 0 1 0 3/35 1/35 1/70 1/5 -3/5 0 0 0 1 rhs 89/5 13/5 19/5 -4/5 rhs 17 5 3 4 1/5 -1/5-1/70 得到整数解：x1=5，x2=3，x3=0，x4=4，x5=0，max z=17。 最优解和最优值如下： maxz?x1?x2?2x1?x2?6 ?4x?5x?20?12?x,x?0且为整数?12x*?(2,2)t,z*?4 第 4 页 共 8 页 西安邮电学院试题库管理系统试题表 用割平面法求解以下整数规划 先求相

8、应的线性规划问题，得到最优单纯形表 z x1 x2 z 1 0 0 x1 0 1 0 x2 0 0 1 x3 -2/5 -2/5 1/5 x4 -9/5 1/5 -3/5 rhs 44/5 4/5 8/5 minz?3x1?4x2?3x1?x2?4 ?s.t.?x1?2x2?4?x,x?0且为整数?12 选择一个非整数的基变量，例如x2=8/5，构造约束条件（3.4），其中 b2=8/5=1+3/5，i2=1，f2=3/5 y23=1/5=0+1/5，i23=0，f23=1/5 y24=-3/5=-1+2/5，i24=-1，f24=2/5 附加的约束条件fr?nj?m?1?frjxj?0为 3

9、/5-（1/3x3+2/5x4）0 即 1/5x3+2/5x43/5 将这个约束加到线性规划的最优单纯形表中，并增加一个松弛变量x5，得到 z x1 x2 x5 z 1 0 0 0 x1 0 1 0 0 x2 0 0 1 0 x3 -2/5 -2/5 1/5 -1/5 x4 -9/5 1/5 -3/5 -2/5 x5 0 0 0 1 rhs 44/5 4/5 8/5 -3/5 用对偶单纯形法，x5离基，x3进基 已获得整数的最优解。 z z x1 x2 x3 x1 0 1 0 0 x2 0 0 1 0 x3 0 0 0 1 x4 -1 1 -1 2 x5 -2 -2 1 -5 rhs 10 2

10、 1 3 1 0 0 0 用割平面法解下列整数规划： 最优解和最优值如下： maxz?4x1?3x2?4x1?4x2?17 ?2x?17?1?x,x?0且为整数?12 用割平面法解下列整数规划： x*?(3,1)t,z*?15 最优解和最优值如下： maxz?2x1?x2?x1?x2?6 ?x1?4x2?2?x,x?0且为整数?12 用割平面法解下列整数规划： x*?(5,1)t,z*?11 最优解和最优值如下： maxz?4x1?5x2?3x1?2x2?10 ?x1?4x2?11?x,x?0且为整数?12 用分枝定界法求下列整数规划。 x*?(2,2)t,z*?18 最优解和最优值如下： m

11、axz?5x1?x2?2x37?2x?x?x?x?1234?2?2x?x?x?x?2 ?1235?x1,x2,x3,x4,x5?0?x3和x5为整数 用分枝定界法求下列整数规划。 x*?(0,2,0,1.5,0)t,z*?2 最优解和最优值如下： maxz?5x1?x2?2x3?3x1?10x2?50?7x?2x?28?12?x1,x2?0?x3为整数 x*?(4.857,3)t,z*?18.71429 11180303 设xj为投资第j个点的状态，xj=1或0，j=1,2,12 maxz?400x1?500x2?450x3?400x12最优解：x1x5=x12=0，其余xj=1,总收益z=3870万元，实际完成投资额8920万元 ?900x1?1200x2?1000x3?850x11?1000x12?9000?44771212 ?x?2,x?3,x?1,x?2,x?3,x?4?j?jjjjjj?1j?1j?5j?5j?8j?8?x?1或0，j?1,12?j 求最优解和总收益及实际完成的投资额。 用隐枚举法求解01规划问题 max z=3x1+2 x2-5 x3-2 x4+3 x5 最优解x1= x2=1, x3=x4= x5=0, z=5 ?x1?x2?x3?2x4?x5?4?7x?3x?4x?3x?8345?1st.