2010上《运筹学IA》考试题(A卷)

更新时间:2023-11-02 14:36:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

线订装封密线 订装 名封 姓密号线订 装学封级密 班西南交通大学2009-2010学年第(二)学期考试试卷

课程代码0244522课程名称运筹学AI考试时间120分钟

题号 一 二 三 四 五 六 七 八 九 十 总成绩 得分 阅卷教师签字:

一 填空题(共20分,每题2分) 1.线性规划模型转化为标准型,若约束条件方程是≥型,可在方程左边减去一个非负的变量,该变量称为多余变量。 2若原问题存在最优解,则原问题的目标函数值和对偶问题的目标函数值是 相等的。

3.线性规划模型中约束条件方程右端的bi增加一个单位时,最优目标函数z的变化量称为资源i的影子价格 。

4.对偶单纯形法的算法思路是每次迭代时的基变量都满足最优检验,但不一定满足非负约束。 5.在线性规划模型中,如果不是所有的变量都限制为整数约束,则称此线性规划模型为混合整数规划。 6.线性规划模型的标准型中,bi (i=1,2,…m)一定是 大于等于零 。 7.对Max型线性规划问题,若单纯形表中没有正检验数,并且检验数为0的个数大于基变量个数,则该模型存在 多重解。

8.原问题约束条件方程右端的值和对偶问题目标函数的系数对应。 9.在m个产地n个销售地的运输问题中,基变量的个数为m+n-1个,那么非基变量的个数为m*n-(m+n-1)个。

10.单纯形法寻找初始基本可行解的方法是构造 单位矩阵 。 二 选择题(共15分,每题3分)

1.若目标函数为Max型,当所有非基变量的检验数Cj-Zj都小于0时,不管将哪一个非基变量作为换入变量,都会使Z(X(k+1))AZ(X(k))。 A小于B大于C等于D小于等于

2.若对偶问题有最优解,则原问题 A最优解。 A一定有 B不一定 C无法确定 D一定没有 3.在灵敏度分析中,在不改变原来最优解基变量及其取值的前提下而求出参数的允许变动范围,这主要指AC灵敏度分析。

Aaij灵敏度分析 Bbi灵敏度分析 Ccj灵敏度分析 D任意一个 4.求解运输问题检验数的方法有CE。

A分枝定界法 B大M法 C位势法 D两阶段法 E闭回路法 5.在线性规划的模型中,如果存在自由变量,可以断定该自由变量也一定是E。

A基变量 B人工变量 C松弛变量 D多余变量 E决策变量

三 判断对错(在括号内打×或√,在横线上说明错误原因,每题3分,

共18分,不说明错误原因不得分。)

1.对偶单纯形法计算过程中,每次迭代的基本解都满足最优检验,可以断定此基本解一定为最优解。( × ) 必须同时满足非负约束时才是最优解。 2. 对偶问题的对偶一定是原问题。( √ )

3.用单纯形法求解时,检验数为零的变量一定是基变量。( × ) 如果存在多重最优解时,也存在检验数为零的非基变量。

4.在表上作业法中,按最小元素法能确定出基变量,那么每一个非基变量 都能和这些基变量构成唯一的闭回路。( √ )

5.运输问题一定有最优解,但不一定有可行解。( × ) 任何运输问题都有最优解,所以一定有可行解。

6.用单纯形法求解标准型线性规划问题时,与检验数大于零相对应的变量 均可作为换入变量。( × )

检验数大于零相对应列中的aij值必须全部为大于零。 四 简答题(共12分)

1.表上作业法和单纯形法在求解过程中有一定的差别,请从初始基本可行解确定、检验数确定、解的调整三个方面论述二者的差别。(8分) 答:(1)单纯形法通过构造单位矩阵确定基本可行解,表上作业法通过

西北角法、最小元素法或差值法确定基本可行解。(2)单纯形法通过求Cj-Zj值确定检验数,表上作业法通过闭回路法或位势法确定检验数。(3)单纯形法通过选择检验数最大的变量为换入变量、

?bi?xj?min ?aij?的i行对应的基变量作为换出变量,表上作业法通过 aij?0??*由换入变量和一组基变量组成唯一的一个闭回路,则以换入变量为起点,取此唯一闭回路偶数顶点中基变量取值最小的做为换出变量,调整量即为此基变量的值。判卷标准:每种过程2分,根据答题情况适当调整分数。

2.对整数规划模型的非整数解用凑整方法处理时,模型的解可能会发生哪三种现象?(4分)

答:不是可行解;可能是可行解但不是最优解;可能是最优解。

五 计算题(共30分)

1.(12分)某工厂用钢、橡胶生产3种产品A、B、C,有关资料如下:

单位产品钢消耗量 单位产品橡胶消耗量 2 3 3 3 1 2 资源数量 100 120 产品 A B C 单位产品利润 40 45 24 设X1为A的日产量,X2为B的日产量,X3为C的日产量,每天生产 A、B、C各多少才能使利润最大的线性规划模型为:

Max Z=40X1+45X2+24X3 2X1+3X2+ X3≤100

3X1+3X2+2X3≤120 Xj≥0, 对一切j

下表是用单纯形法对该模型求解时的一次迭代:

Cj→ 40 45 24 0 0 CB XB b X1 X2 X3 X4 X5 45 X2 100/3 2/3 1 1/3 1/3 0 0 X5 20 1 0 1 -1 1 Zj 30 45 15 15 0 Cj-Zj 10 0 9 -15 0

请:(5分) (1)继续迭代求解,请确定产品A、B、C最佳生产方案。

(2)如果将钢和橡胶的资源出让,钢和橡胶的转让价格分别为多少

时,所得收入不低于生产产品A、B、C 所得最佳利润?(2分) (3)如果将钢和橡胶分别以1和14的价格出让出去,是否划算?

为什么?(2分) (4)若多购置30个橡胶,总利润是否会增加?增加多少?产品A、

B、C新的生产方案是多少?(3分) Cj→ 40 45 24 0 0 解:(1) CB XB b X1 X2 X3 X4 X5

45 X2 20 0 1 -1/3 1 -2/3

40 X1 20 1 0 1 -1 1

Zj 40 45 25 5 10

Cj-Zj 0 0 -1 -5 -10

即钢和橡胶的最佳生产方案为20,20。 解:(2)由qi=Zn+k,读出对偶问题的最优解即可,钢的出让价格为5,橡胶的出让价格为10。 解:(3)划算,因为生产产品获得最佳利润为1700,此方案利润为: 1*100+14*120=1780 解:(4)根据性质:某一个单纯形表中第i种资源(bi)的边际值qi

等于该表中第i行约束条件的松弛变量Xn+i的机会费用Zn+i。(1)中的获得最优解的单纯性表中有:q2=10。因此,多购置30个橡胶,总利润会增加,增加值=10*30=300。或:多购置橡胶,对b2灵敏度

分析,根据公式Max{-20/1}≤△b2≤Min {-20/(-2/3) }, -20≤△b2≤30,即b2的灵敏度范围为[100,150]。多购置30个橡胶资源,即△b2=30,在灵敏度范围内, 新的解为XN=XO+△b2*P5=[20 20]+30*[-2/3 1]=[0 50],即新生产方案为A产品日生产量为50,B产品日生产量为0,C产品日生产量为0,新的最大总利润为40*50+45*0+24*0=2000,所以总利润会增加,增加了2000-1700=300。 2.(8分)下表是某一运输问题的综合表。 销地 B1 B2 B3 B4 产量 产地 A1 2 9 10 7 9

A2 1 3 4 2 5

A3 8 4 2 5 7

3 8 4 6 销量

请依次解决以下两个问题:

(1)给定一组解(x11, x12, x14, x24, x32, x33)=(3,5,1,5,3,4),请问此解是否为最优解?为什么?若不是最优解,请求出最优解。(7分) (2)求出的最优解是不可行性、退化、多重解、无界限解的哪一种情况?为什么?(3分) 解:(1)将给出的基本可行解用闭回路法或位势法求出检验数,如下表:

销地Bi

运价 产地Ai

A1 A2 A3 销量

2 3 1 4 8

11 3

9 3 4

5

B1 B2 B3 3 2

4

B4

1

产量 9 5 7 21

10 4 2 7

-1

3

2 5 5 3 6

8 4

评分标准:以上过程4分。

(2)X22的检验数为负数,没有达到最优,进行调整,求出另外一组基本可行解,如下表:

销地Bi

运产地Ai

A1 A2 A3 销

2

3

B1 B2 ×

5 3 B3 × ×

4

B4

6 产9 5 7 21

9 3 4

10 4 2 7

1 × 8 × 3

2 0 5 × 6

8 4

评分标准:以上过程4分。

(3)用闭回路法或位势法继续求检验数,如下表:

销地Bi

运价 产地Ai

A1 A2 A3 销量

B1 2 3 1 4 18

0 3

B2 1

5 3 B3 4 3

4 B4

6 产量 9 5 7 21

9 3 4

10 4 2

7

2 0 5 2 6

8 4

评分标准:以上过程1分。

(4)没有检验数为负数,达到最优,最优解为: (x11, x14, x22, x24, x32, x33)=(3,6,5,0,3,4)

最优目标函数值为:z=2×3+7×6+3×5+2×0+4×3+2×4=83 评分标准:以上过程1分。

解(2)为退化情况,因为最优解中有一个基变量的取值为0。

3.(8分)有一个目标函数为Max型的线性规划问题,下表是用单纯形法求解时的最优解单纯形表,现在增加一个新的约束条件:x1+x2≥10,请用对偶单纯形法求新的最优解。 Cj→ 6 3 2 0 x1 x2 x3 x4 CB XB b 3 x2 1 0 1 -5 -1 6 x1 8 1 0 3 2

Zj 6 3 3 9

Cj -Zj 0 0 -1 -9

解:(1)原有的解(8,1,0,0)不满足新的条件,将新条件变为:-x1-x2+x5=-10,加

入最优表中:

Cj→ 6 3 2 0 0 CB XB b x1 x2 x3 X4 X5 3 x2 1 0 1 -5 -1 0

6 x1 8 1 0 3 2 0

0 X5 -10 -1 -1 0 0 1

评分标准:以上过程2分。 (2)用对偶单纯形法求解,结果如下表:

Cj→ 6 3 2 0 0 CB XB b x1 x2 x3 X4 X5

3 x2 1 0 1 -5 -1 0

6 x1 8 1 0 3 2 0

0 X5 -1 0 0 -2 1 1

Zj 6 3 3 9 0

Cj-Zj 0 0 -1 -9 0 ???b**i??min j为换入变量所在的列,X??j为换入变量的取值。xj*?a*ij? aij?0??评分标准:以上过程4分。

*

(3)从上表看出不可行,继续进行迭代:

Cj→ 6 3 2 CB XB b x1 x2 x3 3 x2 7/2 0 1 0 6 x1 13/2 1 0 0 2 X3 Zj Cj-Zj 1/2 0 6 0 0 3 0 1 2 0 0 0 X4 X5 -7/2 -5/2 7/2 3/2 -1/2 -1/2 19/2 1/2 -19/2 -1/2 已达到最优。评分标准:以上过程2分。

六 建模题(5分)

某物流公司有甲乙两种类型运输车各一辆,有效容积分别为24m3和16m3, 所运输货物的体积和运费收入如下表,在甲乙两种类型运输车容积限制下,选择收入最多的货物运输,要求一类货物最多只能选择一种类型运输车, 另外货物6必须运走,货物1、4不能混装,请建立线性规划模型。

货物 体积(m3) 收入 1 6 4 2 4 5 3 6 3 4 3 4 5 5 2 6 7 3 7 4 6

解:设变量xi表示第i种货物装到甲类型车上,i=1,2,3,4,5,6,7。 ?1, 装载第i种货物在甲类型车上xi??

i种货物?0,甲类型车不装载第

设变量yi表示第i种货物装到乙类型车上,i=1,2,3,4,5,6,7。 ?1, 装载第i种货物在乙类型车上yi??

0,乙类型车不装载第i种货物?

因为同一种货物不可能在两辆车同时装载,有xi+yi≠2,即0≤xi+yi≤1;货物6必须运走,要求货物6至少在一辆车装载,有x6+y6=1;货物1、4不能混装,x1+x4≠2和y1+y4≠2,即0≤x1+x4≤1和0≤y1+y4≤1。 模型为:

目标函数为Max Z=4x1+5x2+3x3+4x4+2x5+3x6+6x7+4y1+5y2+3y3+4y4+2y5+3y6+6y7

6x1+4x2+6x3+3x4+5x5+7x6+4x7≤24

6y1+4y2+6y3+3y4+5y5+7y6+4y7≤16

x6+y6=1

0≤x1+x4≤1 0≤y1+y4≤1 0≤xi+yi≤1 xi=0或1 yi=0或1

i=1,2,3,4,5,6,7

用xi1和一yi2做决策变量也可。

???b**i??min j为换入变量所在的列,X??j为换入变量的取值。xj*?a*ij? aij?0??评分标准:以上过程4分。

*

(3)从上表看出不可行,继续进行迭代:

Cj→ 6 3 2 CB XB b x1 x2 x3 3 x2 7/2 0 1 0 6 x1 13/2 1 0 0 2 X3 Zj Cj-Zj 1/2 0 6 0 0 3 0 1 2 0 0 0 X4 X5 -7/2 -5/2 7/2 3/2 -1/2 -1/2 19/2 1/2 -19/2 -1/2 已达到最优。评分标准:以上过程2分。

六 建模题(5分)

某物流公司有甲乙两种类型运输车各一辆,有效容积分别为24m3和16m3, 所运输货物的体积和运费收入如下表,在甲乙两种类型运输车容积限制下,选择收入最多的货物运输,要求一类货物最多只能选择一种类型运输车, 另外货物6必须运走,货物1、4不能混装,请建立线性规划模型。

货物 体积(m3) 收入 1 6 4 2 4 5 3 6 3 4 3 4 5 5 2 6 7 3 7 4 6

解:设变量xi表示第i种货物装到甲类型车上,i=1,2,3,4,5,6,7。 ?1, 装载第i种货物在甲类型车上xi??

i种货物?0,甲类型车不装载第

设变量yi表示第i种货物装到乙类型车上,i=1,2,3,4,5,6,7。 ?1, 装载第i种货物在乙类型车上yi??

0,乙类型车不装载第i种货物?

因为同一种货物不可能在两辆车同时装载,有xi+yi≠2,即0≤xi+yi≤1;货物6必须运走,要求货物6至少在一辆车装载,有x6+y6=1;货物1、4不能混装,x1+x4≠2和y1+y4≠2,即0≤x1+x4≤1和0≤y1+y4≤1。 模型为:

目标函数为Max Z=4x1+5x2+3x3+4x4+2x5+3x6+6x7+4y1+5y2+3y3+4y4+2y5+3y6+6y7

6x1+4x2+6x3+3x4+5x5+7x6+4x7≤24

6y1+4y2+6y3+3y4+5y5+7y6+4y7≤16

x6+y6=1

0≤x1+x4≤1 0≤y1+y4≤1 0≤xi+yi≤1 xi=0或1 yi=0或1

i=1,2,3,4,5,6,7

用xi1和一yi2做决策变量也可。

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

Top