运筹学试题及答案
陕西理工学院考试试卷(B卷答案)
2010— 2011 学年 第一学期
若线性规划的可行域无界,则此线性规划存在无界解。 ( √ ) 求解目标规划问题时,应把绝对约束作为最高优先级考虑。 ( √ )
具有m个产地n个销地的运输问题模型有m+n+1个变量构成基变量。 ( × )任一个图中,奇点的个数为奇数。 ( × )图G连通且无回路,则它的每条边都是割边。 ( √ )
目标规划中若要求不超过目标值,则目标函数应当为____minzf(d
)
*
.写出线性规划问题的对偶问题,已知对偶问题的最优解为y14/5,y*
23/5,z5,(12分)
maxz2x1x25x32x43x5
x1x22x3x43x54
2x
1x23x3x4x53
xi0,i1,2,5解:由原问题可以得到其对偶问题:
maxz4y13y2y1y22y1
y23
2y13y25y1y22
3y1y23
y1,y20 (6 分)
将最优解y*
*
14/5,y23/5
带入,由互补松弛性条件得
x13x542x1x5=3
求解得
x*11,x*51
(6分)
2、用伏格尔法确定下表中的运输问题的初始基可行解。(12分) 解:计算各行、各列的最小运费和次小运费的差额,得
得初始解为 :
3.利用割平面法求解
第 1 页 共 3 页
maxzx2x2x1x21s..t
3x1x24 x1,x20,x1,x2
解:求解其松弛问题P37
10
0,对应的最优解为x0(4,4)T,最优值为z
4
。 (6分) 由于x0不是整数向量,增加割平面条件
34x14x3
344
,利用对偶单纯形法求解其对应的松弛问题P1,得其最优解x1(1
,1)T
,z*2, (6分) 4.运用递推解法求解下列问题
maxf4x222
1x22x312 3x12x2x39
x 1,x2,x30
解:按问题的变量个数划分三个阶段。设状态变量s0、s1、s2、s3,并记s310;取问题中的变量xi为决策变量;各阶段指标函数按加法方式结合。令最优值函数fk(sk)表示第k阶段的初始状态为sk,从1阶段到第k阶段所得的最大值。设s12x1,s14x2s2,
s23x3s39,则有s1x1/2,0x2s2/4,0x3s1/3。(3分)
运用顺推法,有 f1(s1)xmax1s1/2
(4x1)2s1,x1*s1/2 f1
2(s2)0maxx2s2/4
(9x2f3(x3))0maxx2s2/4
(9x22(s24x2)),得x2
4s2
为极大
值点,故f2(s2
)94s2,x2*1
4
s2。 f22
91(s1)0maxx3s3/3(2x3f2(s2))0maxx3s3/3(2x34
(s33x3)),由0s310及二
90次函数的性质, 在x3*0,s310处,f3(s3)
4
s4
1。 故可得最优解为:x13*0,x2*
4s110
s24(100)4,x1*12
0 x33*s3s2x2*
4c12c14
c 最优值为 maxzf3(10)
90
4
(9分) 四、解答题
1.某工厂制造三种产品A,B和C,需要工时和原材料如下表所示:
所能提供的日总工时为45,总材料数为30,试建立线性规划模型,用单纯形法求解该模型。当产品A的单位利润由4元/件变为2元/件,是否要修改生产计划?若不需修改计划,陈述理;若需要修改计划,计算得出修改方案。 解:建立线性规划模型:
maxZ4x1x25x3
6x14x25x345
s.t.
3x (3分) 1x25x330x1,x2,x3
,0其中x1,x2,x3是产品A,B,C的产量,
第 2 页 共 3 页
2
用单纯形法求得最优单纯形表如下:(5分)
当c4变为2,计算可得检验数分别为1
41由21,43,53
不全为零,因此当前
解不是最优解,需要修改生产计划,根据计算得出新的最优表为(6分)
此时应生产B产品5个单位,生产C产品5个单位,不生产A产品。此时的利润为30。
2.用Dijkstra法求a到各顶点的最短路。弧旁的数表示从vi到vj的距离(13分)
解:运用表格实现(8分)
故a到b的最短距离是2;a到c的最短路为:a-b-c,最短距离为2+3=5;a到d的最短路
为:a-b-c- d,最短距离为10;a到e的最短路为:a-b-c-e,最短距离为8;a到f的最短路为:a-b-c-e-f,最短距离为9。 (5分)
第 3 页 共 3 页 3