运筹学试卷试题和答案

1、 试 题 2009 年 2010 年第 1 学期课程名称： 运筹学基础 专业年级： 信息（电专）0803、0804 考生学号： 考生姓名： 试卷类型： A卷 B卷 考试方式: 开卷 闭卷 一、 填空（每题4分，共20分）1. 线性规划问题MaxZ=CX；AX=b，X0（A为kxl的矩阵，且l>k）的基的最多个数为_，基的可行解的最多个数为_.2.指派问题的最优解的性质_.3.线性规划问题的所有可行解构成的集合是_,它们有有限个_,线性规划问题的每个基可行解对应可行域的_,若线性规划问题有最优解，必在_得到。4影子价格的经济含义_.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时

2、，企业应_该资源，而当某种资源的市场价格高于影子价格时，则企业应_该资源，可见影子价格对市场有_作用。5. 运输问题的产销平衡表中有m个产地n个销地，其决策变量的个数有_个，其数值格有_个二、 计算（共60分）1 对下列线性规划问题 Max z=2x1+x2+3x3 x1+ x2+2x3 5 s.t. 2x1+3x2+4x312x1, x2, x30（1） 写出其对偶问题；（5分）（2） 已知（3，2，0）T是上述问题的最优解，根据互补松弛理论求出对偶问题的最优解；（10分）2. （15分）运用单纯形法求解下面线性规划问题。 3 （15分）已知运输问题的产销平衡表与单位运价表如下表所示 销地产

3、地B1B2B3B4产量A11067124A21610599A35410104销量5246试用运用伏格尔法求出初始运输方案。4 （15分）用匈牙利法求解下列分配问题，已知效益矩阵为 798561274879667810三、 建模（第1题10分，第2题10分，共20分）1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员 （15分）2. 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：

4、应如何下料，可使所用原料最省（15分） 试卷答案 2009 年 2010 年第 1 学期课程名称： 运筹学基础 专业年级： 信息（电专）0803、0804 考生学号： 考生姓名： 试卷类型： A卷 B卷 考试方式: 开卷 闭卷 四、 填空（每空2分，共20分）1:Clk , Clk 2设指派问题的效率矩阵为C= ，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数，得到新的效率矩阵，则以为效率矩阵的新的指派问题与原指派问题的最优解相同。3 凸集，顶点，顶点，顶点4其它条件不变的情况下，单位第i种资源变化所引起目标函数值的变化量。买进，卖出。5 ，五、 计算（每题15分，共60分）1. 解（

5、1）（5分）写出其对偶问题； Minw=5y1+12y2 s.t. y1+2y22 y1+3y21 2y1+4y23 y10， y2 无约束 （2） （10分）已知（3，2，0）T是上述问题的最优解，根据互补松弛理论求出对偶问题的最优解； 由于原问题x1和x2为正，根据互补松弛理论，有对偶问题取最优解时（1）、（2）取严格等式，即为 y1+2y22 y1+3y21解得y2-1 y14故对偶问题最优解为Y*（4，1），w*=82. 解（1）（3分）加入松弛变量，上述模型可转化为（10分） cj3130CBXBbx1x2x3x40x315351050x42462014z031000x33041-0

6、.51.23x1411/301/6-z12000-0.5（2分）最优解，最优值3. （1） （7分）用最小元素法求得初始可行基如下 销地产地B1B2B3B4产量A110 36 ×7 ×12 14 0 A216 ×10 ×5 49 59 -3A35 24 210 ×10 ×4 -5销量5 102 94 86 12（2） （8分）位势方程组为u1+v1=10 u1+v4=12u2+v3=5 u2+v4=9u3+v1=5 u3+v2=4令u10，解得v1=10 v2=9 v3=8 v4=12 u2 =-3 u3 =-5 各非基变量检验数为1

7、26（09）-3137（08）-12116（103）92210（93）43310（85）73410（125）3存在非基变量检验数为负，没有达到最优解4 用匈牙利法求解下列分配问题，已知效益矩阵为 798561274879667810第一步（5分），把Cij转化为Cij, 2410281030210104第二步（5分），求初始分配方案及寻找覆盖所有零元素的最少直线，2410281030210104第三步（5分），调整，求最优解。1300170030220105所以，最优解为六、 建模（第1题10分，第2题10分，共30分）1. 解：设 xi 表示第i班次时开始上班的司机和乘务人员数, （2分）这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 （3分） 约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0（5分）2. 解： 共可设计下列5 种下料方案，见下表（5分）设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。（5分） 目