运筹学期末试题.

1、运筹学试题样卷（一）题号一一三四五六七八九十总分得分、判断题（共计10分，每小题1分，对的打，错的打 X）1 .无孤立点的图一定是连通图。2 .对于线性规划的原问题和其对偶问题，若其中一个有最优解,另一个也一定有最优解。3 .如果一个线性规划问题有可行解，那么它必有最优解。1. > 0 、一j 0对应的变量4 .对偶问题的对偶问题一定是原问题。5 .用单纯形法求解标准形式（求最小值）的线性规划问题时，与都可以被选作换入变量。6 .若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。7.度为0的点称为悬挂点。8.表上作业法实质上就是求解运输问题的单纯形法。一个图G是树的充分

2、必要条件是边数最少的无孤立点的图。9.3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/人日，秋冬季收入为 20元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资 3元。养奶牛时每头需拨出 1.5公顷土地种饲料，并占用人工秋冬季为 100人日，春夏季为50 人日，年净收入 900元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入 2元/每只鸡。农场现有鸡舍允许最多养 1500只 鸡，牛栏允许最多养 200头。三种作物每年需要的人工及收入情况

3、如下表所示：大豆秋冬季需人日数203510春夏季需人日数507540年净收入（元/公顷）300041004600试决定该农场的经营方案，使年净收入为最大。三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中x4 ,x5为松弛变量，问题的约束为形式（共8分）xix2乂3x4x5x35/201/211/20xi5/211/20-1/61/3cj -zj0一 40一 42（1）写出原线性规划问题；（4分）（2）写出原问题的对偶问题；（3分）（3）直接由上表写出对偶问题的最优解。（1分）四、用单纯形法解下列线性规划问题（16分）max Z = 2x1 - x2 x3s. t. 3 X1

4、 + X2 + X3 - 60x 1-x 2 + 2 x 3 - 10x 1 + x 2- x 34 20x 1 , x 2 , x 3 -0五、求解下面运输问题。（18分）某公司从三个产地AA2、A3将物品运往四个销地B1、B2、B3、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小？产地销地B2B3B4产量Ai1056725A2827625A3934850销、灵敏度分析（共 8分）线性规戈U max z= 10x1 + 6x2 + 4x3s.t. x1 + x2 + x3 父 10010x1 +4 x2

5、+ 5 x3 4 6002x1 +2 x2 + 6 x3 三 300x1 , x2 , x3 - 0的最优单纯形表如下:6X2200/305/615/3-1/6010X1100/311/60-2/31/600X6100040-201可06/30-10/3-2/30（1）C1在何范围内变化，最优计划不变？（4分）（2）bl在什么范围内变化，最优基不变？（4分）七、试建立一个动态规划模型。（共8分）某工厂购进100台机器，准备生产pl , p2两种产品。若生产产品 pl，每台机器每年可收入45万元，损坏率为 65%;若生产产品 p2 ,每台机器 每年可收入35万元，损坏率为35% ;估计三年后将有

6、新 的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？八、求解对策问题。（共10分）某种子商店希望订购一批种子。据已往经验，种子的销售量可能为 500, 1000, 1500或2000公斤。假定每公斤种子的订购价为6元，销售价为9元，剩余种子的处理价为每公斤3元。要求：（1）建立损益矩阵；（3分）（2）用悲观法决定该商店应订购的种子数。（2分）（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。（5分）九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8分）工序 代号工序 时间最早开 工时间最早完 工时间最晚开 工时间最晚完 工时间机动 时间1-281-

7、371-462-432-553-423-634-534-674-745-796-78Mo短最的6求 法 号 标 用、 十运筹学试题样卷（二）题号一一三四五六七八九十总分得分一、判断题（对的打 M错白打X.共计io分，答在下面的表格中）1、单纯形法计算中，选取最大正检验数° k对应的变量xk作为换入变量，可使目标函数值得到最快的减少。2、单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个 基变量的值是负的。3、对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。4、应用对偶单纯形法计算时，若单纯形表中某一基变量Xi <0,且xi所在行的所有元

8、素都大于或等于零，则其对偶问题具有无界解。5、用位势法计算检验数时，每一行（或列）的位势的值是唯一的，所以每一个空格的检验 数是唯一的。6、动态规划的最短路问题也可以用图论中求最短路问题的方法求解。7、图论中的图是为了研究问题中有哪些对象及对象之间的关系，它与图的几何形状无关。8、动态规划只是用来解决和时间有关的问题。9、在画网络计划图时，允许有多个起点和多个终点。10、因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列四种情况：有 唯一最优解；有无穷多个最优解；无界解；无可行解。10二、试建立此问题的数学模型。（8分）某工厂I、n、出三种产品在下一年个季度的合同预定数如下表所示，

9、该三种产品第一季度初无库存，要求在在第四季度末每种产品的库存为150件。已知该厂每季度生产工时为15000小时，生产产品I、n、出每件需 3, 4, 3小时。因更换工艺装备，产品I在第二季度无法生产。规定当产品不能按期交货时，产品I、n每件每迟交一个季度赔偿20元，产品出赔偿15元，又生产出来的产品不在本季度交货的，每件每季度的库存费为5元。问应如何安排生产，使总的赔偿加库存费用最小。产品季度i234Ii500i0002000i200ni500i500i200i500mi5002000i5002500三、用单纯形法求解线性规划问题（16分）Max Z = 1500 xi + 2500 X2s.

10、t. 3xi + 2 x2<652 xi + x2 ,403x2三 75xi，x2 -0四、写出下面线性规划的对偶问题（8分）min z = x1 x2 2x3'2x1 +x2 +2x3 < 72xi - 3x2 - x? = 5- 3x1 5x2 -4x3 一 3x1 ,x20,x3无约束.五、求解下面运输问题。 （18分）某公司从三个产地Ai、A2、A3将物品运往四个销地Bi、B2、B3、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示销地产地B1B2B3B4产量A3ii3i07A2i9284A374i059销量365620问：应如何调运，可使得

11、总运输费最小六、灵敏度分析（8分）线性规划 maxz = 4xi . x? 5x3 6x1 +3x2 +5x3 < 453x1 +4x2 +5x3 <30 x1 ,x2 , x3 > 0的最终单纯形表如下：cj41500CBX Bbx1x2x3x4x54X1511/301/3-1/35x33011-1/52/550-8/301 /3-2/3(1) x1的系数Ci在什么范围变化，上述最优解不变？ (4分)(2) b2在什么范围变化，最优基不变？ (4分)七、建动态规划模型。(8分)某公司拥有资金 10万元，若投资于项目i (i=1, 2, 3)的投资额为xi时，其收益分别为g1

12、(x1)=4x1 , g2(x2)=9x2 , g3(x3)=2x32，问应如何分配投资数额才能使总收益最大?八、解决对策问题。(10分)根据已往的资料，一家超级商场每天所需面包数(当天市场需求量)可能是下列当中的某一个：100, 150, 200, 250, 300,但其概率分布不知道。如果一个面包当天卖不掉，则可在当天结束时每个 0.5元处理掉。新鲜面包每个售价1.2元，进价0.9元，假设进货量限制在需求量中的某一个，要求(1)建立面包进货问题的损益矩阵；(3分)(2)用乐观法确定进货量。(2分)(3)建立后悔矩阵，并用后悔值法确定进货量。（5分）九、用双标号法求下列图中 V1到V9的最短

13、路线及其长度。（6分）最后指出关键问题，并画出关键线路。（8分，直接答在下面）十、下图是商业中心建设项目的网络计划图，请用标号法计算出表中的各个参数,工序时间开工时间完工时间机动时间最早最晚最早最晚A (20)B (10)C (8)D (24)E (8)F (14)G (10)H (6)I (12)J (6)运筹学样卷（一）答案判断题。共计10分，每小题1分10XXXXV二、建线性规划模型。共计 8分（酌情扣分）解：用X1, x2，X3分别表示大豆、玉米、麦子的种植公顷数；X4，x5分别表示奶牛和鸡的饲养数；X6，X7分别表示秋冬季和春夏季的劳动力（人日）数，则有maxZ = 3000x141

14、00x24600x3900x420x520x625x71234567'x1 +x2 +x3 +1.5x4W100（土地限制）400x4 +3x5<15000（资金限制）20x1 +35x2 +10x3 +100x4 +0.6x5 +x6 <3500 （劳动力限制）50x1 + 175x2 +40x3 +50x4 +0.3x5 +x7 <4000 （劳动力限制）x4< 200（牛栏限制）x5<1500（鸡舍限制）xj >0 （j =1,2，7）三、对偶问题。共计 8分解：（1）原线性规划问题：maxz = 6x1 -2+10x3x2 + 2x2 芸 5

15、« 3x1 - x2 + x3 M10lx1，x2 - 0;4 分（2）原问题的对偶规划问题为：min w = 5y1 10 y23y2 >6j yi - y2 - -22yi y2 -10yl , y2 - 0；3 分(3 )对偶规划问题的最优解为：Y* = ( 4,2 )T。1分四、单纯形表求解线性规划。共计 16分解：引入松弛变量 X4 X5 X6,标准化得，maxZ =2x1 -x2 x3s. t. 3xi + X2 + X3+ X4 = 60x 1 - x 2 + 2 x 3 + X5 = 10x 1 + x 2 x 3 + X6 = 0x 1 , x 2 , x 3

16、, x4 x5 x6 > 03分建初始单纯形表，进行迭代运算： 9分CbXbb，2-110000x1x2x3x4x5x60x460311100200x5101-1201010*0x62011-100120O102*-110000x43004-51-307.52x1101-12010-0x61002-30-115*022001*-30-200x4100011-1-22x115100.500.50.5-1x2501-1.50-0.50.552500-1.50-1.5-0.5由最优单纯形表可知，原线性规划的最优解为：(15,5,0 )T2分最优值为： z*=25。2分五、求解运输问题。共计 1

17、8分解：(1)最小元素法：(也可以用其他方法，酌情给分)设 Xj 为由 Ai 运往 Bj 的运量(i=1,2,3; j=1,2,3,4 ), 列表如下：销地 产地B1B2B3B4产量1252522052531530550销量152030351003分所以，基本的初始可行解为：X14 =25； X22=20 ； X24 =5 ；X31 =15； x33 =30； x34=5其余的Xj=0。3分(2)求最优调运方案：1会求检验数，检验解的最优性：011=2; <512=2; 013=3;021=1 ; 023=5 ; 032= - 13 分2会求调整量进行调整：=52分销地 产地B1B2B3

18、B4产量12525215102531553050销量152030351003分3再次检验 2分4能够写出正确结论解为：x14=25 ； X22 =15 ； X24 =10 X31 =15 X32 =5 X33=30其余的xj=0。1分最少运费为：535 1分。六、灵敏度分析。共计 8分(1) (4 分)'8/3 2/3、1八,'-10/3、max,>< i c, < min/2、1/61/6 ,2 -2/3 ,-4 _ c1 -5 , 6=10-4 -C1c1 -10 5.15-200/31". f-100/3 -1001max一8，><

19、ib1 <min?,->,5/3 ；, -2/3-2 :-40 <山=10七、建动态规划模型。共计 8分解：(1)设阶段变量k表示年度，因此，阶段总数n=3。(2)状态变量sk表示第k年度初拥有的完好机床台数，同时也是第 kT年度末时的完好机床数量。(3)决策变量uk,表示第k年度中分配于生产产品pl的机器台数。于是 sk-uk便为该年度中分配于生产产品pl的机器台数.(4)状态转移方程为Sk 1 =0.355 0.65(Sk -Uk)(5)允许决策集合，在第k段为Uk(sk)=uk 0< uk <sk(6)目标函数。设 gk(sk,uk)为第k年度的产量，则gk

20、(sk,uk) = 45 uk + 35(sk pk),因此，目标函/为Rk = " gk(Sk,uk) i -k(7)条件最优目标而数递推方程。fk(Sk) =mqx(uk(Sk)uk Uk令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第3年度结束这段时间的产品产量，根据最优化原理有以下递推关系：45uk 35(sk - uk) fk 10.35uk 0.65(标-uk) (8).f3 1 (s3 1 ) = 0八、解决对策问题。共 10分(1)益损矩阵如下表所示：3分销售 订购Si500S21000S3 1500S42000Ai 500150015001500150

21、0A210000300030003000A3 1500-1500150045004500A4 2000 3000030006000(2)悲观法：Ai ,订购500公斤。2分(3)后悔矩阵如下表所示： 3分SiS2S3S4最大后悔值Ai01500300045004500A215000150030003000A330001500015003000A445003000150004500按后悔值法商店应取决策为A2或A3 ,即订购1000公斤或1500公斤。九、求网络计划图的各时间参数。（8分）/14 1-14、 526 01118工序 代号工序 时间最早开 工时间最早完 工时间最晚开 工时间最晚完

22、工时间机动 时间1-28080801-37072921-460651162-4381181102-5581391413-427991123-63710151884-531114111404-671118111804-7411152226115-791423172636-78182618260关键问题是：；2f ； -6; 6f 关键线路是：评分标准：能正确给各顶点标号并填表 4分正确写出关键问题 2分正确画出关键线路2分十、用标号法求V1到V6的最短路。（6分）正确标号：4分；正确写出结论：2分运筹学样卷（二）答案判断题。（共计10分，每小题1分）10XXXXXXX二、建线性规划模型。（8分）

23、（酌情给分）解：设为j为第i个季度生产的产品j的数量；si j为第i个季度末需库存的产品j的数量;ti j为第i个季度不能交货的产品 j的数量；yi j为第i个季度对产品j的预定数量，则有： min Z 二1 20（ti1 ti2） 15ti3 1 5;二 si）'ll I 4 /I jjI jXii+Xi2+Xi3 £15000 (i=1,2,3,4)X21 = 0 44£ " =£ yij +150 (j =1,2,3) iqiii工 Xkj +3 Sj =£ ykj (i =1,2,3,4; j =1,2,3) kqkJ xi j

24、 , si j , ti j - 0三、求解线性规划。(16分)解：引入松弛变量 x3, x4, x5,标准化得，Max Z = 1500X1 + 2500X2s.t. 3 x1 + 2x2 + x3 = 652x1 + x2 + x4 = 403 x2 + x5 =75x1, x2 >0 3分建初始单纯形表，进行迭代运算： 9 分CbXbb，150025001000X1X2X3X4X50X3653210032.50X44021010400X575030012.5*O1015002500*0000X3153010-2/35*0X4152001-1/37.52500X22501001/3-

25、02625001500*000-2500/31500X15101/30-2/90X4500-2/311/92500X22501001/3a37000000-5000-500(5, 25,0, 5,0 )T 2 分由最优单纯形表可知原线性规划的最优解为:最优值为：z*=70000。2分四、解：原问题的对偶规划问题为：（共8分）Max f=7y 1+5y2+3y32yi +2y2 -3y3 W1%-3y2+5丫3<12yi - y2 - 4y3 = 2&i«0,y2无约束,V3±Q五、求解运输问题。（18分）解：（1）最小元素法：设 xj 为由 Ai 运往 Bj

26、的运量（i=1,2,3; j=1,2,3,4 ）, 列表如下：销地 产地B1B2B3B4产量143723143639销量3656203分所以，基本的初始可行解为：x13=4 ； x14 =3 ；X21 =3 X23 =21X32 =6 X34=3其余的Xij=0 3分（2）求最优调运方案：0 11 二 1,C12 = 2,0 22 二 1,1会求检验数，检验解的最优性：仃24 = -1031 =10933 =122会求调整量进行调整：e=1 2分销地 产地B1B2B3B4产量152723143639销量3656203再次检验4能够写出正确结论解为：xi3=5 ； x14 =2 ； x21 =3 x24 =1x32 =6 x34=3其余的xj=0。1分最少运费f =3M5+10M2+1M3+8M1+4M6+5M3 = 85i 分六、灵敏度分析。(8分)(1) (4 分)max 3-1/31/3< A C）< min n-8/3 -2/3-1/3, -1/3-1 _ ：c1 _2 , 3 =4 -1 _c1：c1 _ 4 2 = 6（4分）3C30 , 2/5<ib2 < min一 一5-1/3-7.5 < . ： b2 =15七、建动态规划模型。(8分)1 .分阶段：设阶段变量 k表示依次对第