同济运筹学2007到2008期末试卷B.doc

0708运筹学（一）课程试卷B一、辨析题（本题共5小题，每小题3分，共15分）1、线性规划模型中，设系数矩阵A，则X（0，0，2，3，4，0）T有无可能是A的基可行解？2、m个发点和n个收点的运输问题中，有m+n个相互独立的约束条件。3、一个赋权图的最小生成树是否唯一？为什么？4、用单纯形法求解极大化问题的线性规划问题时，与对应的变量都可以被选为换入变量吗？为什么？5、已知网络上某条链如下图，问：x为何值时，该链是增流链，为什么？ 二、某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。（15分）（1）写出问题的数学模型（2）求获最大利润的方案。甲乙设备能力设备A3265设备B2140设备C0375利润（元/件）15002500三、用图解法找出以下目标规划问题的解。（10分） 四、对于线性规划模型： max f =x1+2x2+3x3+4x4s.t. x1+2x2+2x3+3x420 2x1+x2+3x3+2x420x10，x20，x30，x40已知其对偶问题的最优解U*（6/5，1/5），利用互补松弛性求解原问题的最优解。（10分）五、现在有线性规划问题（15分）max z=-5+5+13的最优单纯形表如下：Cj-551300b5X2-11310200X5160-2-4110r00-2-50100（1）约束条件2的右端常数由90变为了70，对最优基、最优解有何影响？如果有影响请求出最优解。（2）目标函数中的系数由13变为8，对最优基、最优解有何影响？如果有影响请求出最优解。六、若发点，及收点，的有关数据如下表所示。假定，处允许物资存储，（本题共15分） 供应量存储费4 6 86 2 420020054需求量50 100 100（1） 写出运输问题的数学模型；（2） 用最小元素法找出初始基本可行解；（3） 求出初始基本可行解的检验数，找出闭回路，确定调整量；（4） 求出最优运输方案和最小总运费。七、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表1：（10分）表1工作工人ABCD甲乙丙丁15192619182317212122162324181917问指派哪个人去完成哪项工作，可使总的消耗时间为最小？八、用标号法求出图中v1至各点的最短路（10分）运筹学（一）课程试卷B参考答案一、辨析题（本题共5小题，每小题3分，共15分）1、线性规划模型中，设系数矩阵A，则X（0，0，2，3，4，0）T有无可能是A的基可行解？有可能（1分）。基可行解中非零值的个数不超过m，（题中m3），给定解中X有3个非零值分量。（2分）2、m个发点和n个收点的运输问题中，有m+n个相互独立的约束条件。错（1分）。相互独立的约束条件有m+n-1（2分）。3、一个赋权图的最小生成树是否唯一？为什么？不是唯一的。（1分）因为可以该赋权图中边的所赋权可能是相同的，在这种情况下得到的最小生成树可能就不唯一的。（2分）4、用单纯形法求解极大化问题的线性规划问题时，与对应的变量都可以被选为换入变量吗？为什么？答：可以。（1分）因为检验数大于零，把作为换入变量，仍然可以改进目标函数值。（2分）5、已知网络上某条链如下图，问：x为何值时，该链是增流链，为什么？ 答：x0（1分）。此时后向边不为零边，不符合增流链定义（2分）。二、某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。（15分）（1）写出问题的数学模型（2）求获最大利润的方案。甲乙设备能力设备A3265设备B2140设备C0375利润（元/件）15002500解：设甲、乙产品分别生产x1,x2件，线性规划模型为 利用单纯形法进行求解为CBxBx1x2x3x4x5b0x3321006532.50x42101040400x50(3)0017525r1500250000000x3(3)010-2/31550X42001-1/3157.52500X201001/325r1500000-833.381500X1101/30-0.222250X400-2/310.111152500x201001/425r00-5000-500最优解为:X*=(5, 25, 0, 5, 0)T, 目标函数最优值70000.三、用图解法找出以下目标规划问题的满意解。（10分） 满意解为（50，0） d1+=0,d1-=0,d2+=130,d2-=0，d3+=300,d3-=0四、对于线性规划模型：（10分）max f =x1+2x2+3x3+4x4s.t. x1+2x2+2x3+3x420 2x1+x2+3x3+2x420x10，x20，x30，x40已知其对偶问题的最优解U*（6/5，1/5），利用互补松弛性求解原问题的解。解：原问题的对偶问题为min z =20u1+20u2s.t. u1+2u21 （1）2u1+u22 （2）2u1+3u23 （3）3u1+2u24 （4） u10，u20 （5分）将U*（6/5，1/5）代入对偶问题，（1）、（2）式为严格不等式，则有，因为，所以有2x3+3x4203x3+2x420解得，。（5分）五、现在有线性规划问题（15分）max z=-5+5+13的最优单纯形表如下：Cj-551300b5X2-11310200X5160-2-4110r00-2-50-100（1）约束条件2的右端常数由90变为了70,对最优基、最优解有何影响？如果有影响请求出最优解。 对最优基、最优解有影响. Cj-551300b5X2-11310200X5160-2-41-10r00-2-50-1005X22310-53/2513X3-8012-1/25r-1600-1-190X=(0,5,5,0,0) z=90（2）目标函数中的系数由13变为8,对最优基、最优解有何影响？如果有影响请求出最优解。 对最优基、最优解没有影响.六、若发点，及收点，的有关数据如下表所示。假定，处允许物资存储，（本题共15分） 供应量存储费4 6 86 2 420020054需求量50 100 100（5） 写出运输问题的数学模型；（6） 用最小元素法找出初始基本可行解；（7） 求出初始基本可行解的检验数，找出闭回路，确定调整量；（8） 求出最优运输方案和最小总运费。解：设的运输量为，则由新的运输问题可以得到： ， (2)解：该运输问题为产销的问题，虚拟销地，形成新的问题： 供应量4 6 8 56 2 4 4200200需求量50 100 100 150 使用最小元素法得到初始解： 供应量50 100 50 100 100200200需求量50 100 100 150 （3）使用位势法，得到检验数为： 0 3 0 03 0 -3 00-14 3 8 5增加的运输量，得到新的解为： 供应量50 0 150 100 100200200需求量50 100 100 150 （2分）使用位势法，得到检验数为： 0 0 0 06 0 0 30-44 6 8 5（4）因此可知： 供应量50 0 150 100 100200200需求量50 100 100 150为该运输问题的最优解。 F=1050（4分）七、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表1：（10分）表1工作工人ABCD甲乙丙丁15192619182317212122162324181917问指派哪个人去完成哪项