《运筹学》习题集(一)
班级_____________姓名_____________
一、
断下列说法是否正确(在题号前打上“?”即正确或“?”即错误):
(1)、图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的。
(2)、线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。
(3)、线性规划的每一个基本解对应于可行域的一个顶点。
(4)、如线性规划问题存在最优解,则最优解一定对应可行域边界上的一个点。 (5)、线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。
(6)、对一个有n 个变量、m 个约束条件的标准形的线性规划问题,其可行域的顶点恰好为m
n C 个。
二、 线性规划问题是否可算作条件极值问题,它与微积分中讲的条件极值问题有何不同?
解:
三、判别下列数学模型是否线性规划模型。(模型中a ,b ,c 为常数;θ为可取某一常数值的参变量;x ,y 为变量。在题号前打上“?”即是或“?”即否):
1、??
?
????≥=+≤++≥-+++=01243208586275331213213213
21x x x x x x x x x x x x x z , max 2、()()?????=≥=≤=∑∏==n j x m i b x a x c z j n j i j ij n j j
j ,,, ,,, min 2102111 3、
()
n j m i c y x y b x a z ij j i m i n
j j
j i i ,,,;,,, min 21212
1
1
22
==≤++=∑∑==
4、
()()??
???=≥=θ+≤=∑∑==n j x m i a b x a x c z j n
j i i j ij n
j j
j ,,, ,,, max 210211
1
四、 将下列线性规划问题变换成标准形(答案写在下面的空白处): 1、 第1题:
2、 第2题:
五、 已知线性规划问题
??????
?≥=+=++=++=(4)(3)(2)(1)
,,
max 04102535152421312
1x x x x x x x x x x x z 表1中所列的解(a )—(f )均满足约束条件(1)(2)(3),试指出表中哪些解是可行解,哪些是基本解,哪些是基本可行解。
解:
六、 判断下列集合是否为凸集(在题号前打上“?”即是或“?”即否): 1
、
[]{
0030212121≥≥≥=x x x x x x X , , , 2
、
表 1
??????
?≤≥≥+--=+-≤++++++=无约束
0 012285327 32max 423143132143214321x x x x x x x x x x x x x x x x x x z ,,,?????≥≤≤-+-=++-+-=无约束 006
4 22min 3
213213213
21x x x x x x x x x x x x z ,,
[]{
}0032121221≥≥≤-=x x x x x x X , , , 七、 对线性规划问题 它的可行域见图1,讨论c 、d 的值如何变化,才使该问题可行域的每个顶点依次使目标函数达到
最优值。
解:
八、 建立模型
1、某机加工车间用一台钻床和五台铣床加工甲、乙两种配套使用的零件。这两种零件需要的加工工时(分钟)如下表2所示。现在要求在所有的机床上保持均衡负荷。假定五台铣床的工作是平均分配的,希望各台机床之间的运行时间相差最多不超过30分钟。设每
天工作8小时,试建立一个模型来确定每天应生产这两种零件各多少,使完工的配套件组数最大。
解:
?????≥≤+≤++= 08
25943 max 2
121212
1x x x x x x dx cx z ,
2、某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如表3。设司机和乘务人员分别在各时间区段一开始时上班,并连续工作八小时,问该公交线路至少配备多少名司机和乘务人员。
解:表3