运筹学试题库

1、运筹学试题库、多项选择题1、下面命题正确的是（）。A、线性规划的标准型右端项非零；B、线性规划的标准型目标求最大；C、线性规划的标准型有等式或不等式约束；D、线性规划的标准型变量均非负。2、下面命题不正确的是（）。A、线性规划的最优解是基本解；B、基本可行解一定是基本解；C、线性规划有可行解则有最优解；D、线性规划的最优值至多有一个。3、设线性规划问题（P）,它的对偶问题（D）,那么（）。A、若（P）求最大则（D）求最小;解；C、若（P）的约束均为等式，则（D、（P）和（D）互为对偶。4、课程中讨论的运输问题有基本特点（A、产销平衡；BC、是整数规划问题；D5、线性规划的标准型有特点（A、右端

2、项非零；BC、有等式或不等式约束；DR （P）、（D）均有可行解则都有最优D）的所有变量均无非负限制；、一定是物品运输的问题;、总是求目标极小。）。、目标求最大；、变量均非负。6、下面命题不正确的是（A、线性规划的最优解是基本可行解； B、基本可行解一定是基本解；C 、线性规划一定有可行解；D 、线性规划的最优值至多有一个。7、线性规划模型有特点（） 。A 、所有函数都是线性函数；B 、目标求最大；C 、有等式或不等式约束；D 、变量非负。8、下面命题正确的是（） 。A、线性规划的最优解是基本可行解；B、基本可行解一定是最优；C 、线性规划一定有可行解；D 、线性规划的最优值至多有一个。9、一

3、个线性规划问题（P）与它的对偶问题（D）有关系（）。A、（P）有可行解则（D）有最优解；R （P）、（D）均有可行解则都有最优解；C、（P）可彳T （ D）无解，则（P）无有限最优解；D （P） （D）互为对偶 10、运输问题的基本可行解有特点（） 。A、有mi+ n 1个基变量；B 、有m+n个位势；C 、产销平衡；D 、不含闭回路。二、简答题（ 1 ）微分学求极值的方法为什么不适用于线性规划的求解（ 2）线性规划的标准形有哪些限制如何把一般的线性规划化为标准形式（ 3）图解法主要步骤是什么从中可以看出线性规划最优解有那些特点（ 4）什么是线性规划的可行解，基本解，基可行解引入基本解和基可行

4、解有什么作用（ 5）对于任意基可行解，为什么必须把目标函数用非基变量表示出来什么是检验数它有什么作用如何计算检验数(6)确定换出变量的法则是什么违背这一法则，会发生什么问题(7)如何进行换基迭代运算(8)大M法与两阶段法的要点是什么两者有什么共同点有什么区别(9)松弛变量与人工变量有什么区别试从定义和处理方式两方面分析。(10)如何判定线性规划有唯一最优解，无穷多最优解和无最优解为什么(11)如何在以B为基的单纯形表中，找出 B 1该表是怎样由初始表得到的(12)对偶问题的构成要素之间，有哪些对应规律(13)如何从原问题最优表中，直接找到对偶最优解(14)叙述互补松弛定理及其经济意义。(15)

5、什么是资源的影子价格它在经济管理中有什么作用(16)对偶单纯形法有哪些操作要点它与单纯形法有哪些相同，哪些地方有区别(17)灵敏度分析主要讨论什么问题分析的基本思路是什么四种基本情况的分析要点是什么三、模型建立题(1)某厂生产A, B, C三种产品，每件产品消耗的原料和设备台时如表3-1所示:表3-1产品ABC资源数量原料单耗2352000机时单耗362600利润101420另外，要求三种产品总产量不低于65件，A的产量不高于 B的产量。试制定使总利润最大的模型。(2)某钻井队要从以下 10个可供选择的井位中确定 5个钻井探油，使总的钻井费用最小。若10个井位的代号为S1,S2,S3L乳，相应

6、的钻井费用为 C1,C2,L ,00,并且井位选择上要满足下列限制条件：或选择S1和S7 ,或选择钻探S8 ；选择了 S3或S4就不能选S5,或反过来也一样；在S5,S6,S7,S8中最多只能选两个；试建立这个问题的整数规划模型。(3)某市为方便学生上学，拟在新建的居民小区增设若干所小学。已知备选校址代号及其能覆盖的居民小区编号如表3 - 2所示，问为覆盖所有小区至少应建多少所小学，要求建模并求解。表3 -2备选校址代号覆盖的居民小区编号A1, 5, 7B1, 2, 5C1, 3, 5D2, 4, 5E3, 6,F4, 6,(4) 一货船，有效载重量为24吨，可运输货物重量及运费收入如表3-3

7、所示，现货物2、4中优先运2,货物1、5不能混装，试建立运费收入最多的运输方案。表3-3货物123456重量(吨)59871023收入(万元)144357(5)运筹学中著名的旅行商贩(货朗担)问题可以叙述如下：某旅行商贩从某一 城市出发，到其他几个城市推销商品，规定每个城市均需到达且只到达一次，然后回到 原出发城市。已知城市i和城市j之间的距离为dij问商贩应选择一条什么样的路线顺序 旅行，使总的旅程最短。试对此问题建立整数规划模型。四、计算及分析应用题(1)某公司打算利用具有下列成分(见表4-1 )的合金配制一种新型合金 100公斤,新合金含铅，锌，锡的比例为 3: 2: 5。表4-1合金品

8、种12345含铅3010501050含锌6020201010含锡1070308040单价(元/ kg)如何安排配方，使成本最低(2)某医院每天各时间段至少需要配备护理人员数量见表4-2表4-2班次时间最少人数16:00 10:0060210:00 14:0070314:00 18:0060418:00 -22:0050522:00 -2:002062:00 6:0030假定每人上班后连续工作 8小时，试建立使总人数最少的计划安排模型。能否利用初等数学的视察法，求出它的最优解(3)某工地需要30套三角架，其结构尺寸如图4-1所示。仓库现有长 6.5米的钢材。如何下料，使消耗的钢材最少图4-1(4

9、 )用图解法求下列线性规划的最优解:(1) min z 4xi 6x2 x1 2x214xi 3x21.5x1 2x24x1，x20(3) max z 6x1 9x2 2x1 3x2222x1 x2 4(2) max z 4x1 4x22x1 3x2 10x x25x1 2x2 8x1, x20(4) max z x1 3x24x1 3x212(2) max z 2x1 3x2x1 2x2 8x1 x2 1x12x1 0, x2无约束4x1 5x2 0x1 x2 1x2 6x1，x2 0x1，x20(5 )把下列线性规划化为标准形式：(1) min zx1 2x2 x3Xx3 x4 12x1

10、x2 x323x1 x2 x3 x4 1x10, x2, x3 0x4无约束(6 )求出下列线性规划的所有基本解，并指出其中的基可行解和最优解。max z 3x1 5x2x1x3482x2x4123x12x2x518xj0, j 1,57 求下列线性规划的解：1max z 3x1 5x22x18x263x1 2x218x1, x203max z 2x1 x2x1 2x22x1 x21x1, x202max z 2x1 4x2x1 2x24x1 x21x1, x204max z 2x1 x2 x33x1 x2 x360x1 x2 2x3 10x1 x2 x3 20x10, x20, x308 利

11、用大M 法或两阶段法求解下列线性规划：1max z 3x1 2x2x1 2x27x1 x21x1 x22x1, x20max z 2x1 x2 x33x1 2x2 x3182x1 x24x1 x2 x35x1,x2,x30max zx1 x2min z x1 3x2 4x3 3x4 4x1 3x2123x1 6x2 x3 2x4153x1 x26x 26x1 3x2 2x3 x4 12x1,x2(9)对于问题20x1,x2,x3,x4 0max z CXAX bX 0设最优解为X,当c改为C时，最优解为X,则(C C)(x* x) 0。(2)如果X1, X2均为最优解，则对于a C 0, 1,

12、 aX+(1 a) X2均为最优解。(10).表4-2是一个求极大值线性规划的单纯形表，其中x4, x5, x6是松弛变量。表4-2Cj22。XbbX1X2X3X4X5X6Xs212-12x21-11-2X142a-1-a+8CT j-1(1)把表中缺少的项目填上适当的数或式子。(2)要使上表成为最优表，a应满足什么条件(3)何时有无穷多最优解(4)何时无最优解(5)何时应以x3替换x14-3,请把表中空白处的(11)已知某线性规划的初始单纯形表和最终单纯形表如表数字填上，并指出最优基 B及BT1。表4-3Cj2-11000CbXbbX1X2X3X4X5X60X43111000X51-1201

13、00X611-1001(T j2-110000X410-1-22X1151/21/2-1X25-1/21/2b j(12).某个线性规划的最终表是表4-4表4-4Cj01-200CbXbbX1X2X3X4X50X113/2100-1/25/21X25/2010-1/23/2-2X31/2001-1/21/2CT j000-1/2-1/2初始基变量是x1， x4，x5。xj0, jn2 1, n（ 1 ）求最优基B=（ P1， P2， P3） ；（ 2）求初始表。（13） . 写出下列线性规划的对偶问题：(1) max z 3x1 x2 x3x12 x2 x 34x1 2x2 4x31x1x1x

14、2 3x3 10,x2 0,x3无约束(2) min z 2x1 x2 3x3 x4x12 x2x3x44x1x2 2x32x1x3 2x4 1x10,x2 0,x3,x4 无约束n(3) max z cjxjj1naijxjbi,i 1,2,m1j1naijxjbi,im1 1,m2j1naijxjbi,im2 1, ,mj1xj0, j1,n1xj无约束，jn1 1, ,n2(4) min zcij xij1j1(14)3)引入人工变量，把问题化为等价模型：nxij j1mi1xij ixij1,aibj,m已知线性规划写出它的对偶问题;1,1,1,min,m,n,nc1x1c2 x2c3

15、 x3a11 x1a21 x1a12x2a13x3a22x2a23 x3b1b2x1, x2, x30引入松弛变量，化为标准形式，再写出对偶问题;引入人工变量，把问题化为等价模型:max z c1x1c2 x2c3x3M ( x6x7 )再写出它的对偶问题。试说明上面三个对偶问题是完全一致的。由此，可以得出什么样的一般结论(15) 利用对偶理论说明下列线性规划无最优解：(16). 已知表 4-5 是某线性规划的最优表，其中a11 x1a21 x1x1,a12 x2a22x2, x70a13 x3x4a23 x3x5x6b1x7b2由此，可以得出什么样的一般结论max z x1x1 x22x1

16、x2x10, x22 x2 x3x342x30, x3X4, X5为松弛变量，两个约束条件表4-5CjCbXbbXiX2X3X4X5x35/201/211/20Xi3/21-1/20-1/61/3(T j0-40-4-2(1)求价值系数Cj和原线性规划;(2)写出原问题的对偶问题；(3)由表4-5求对偶最优解。(17)已知线性规划问题min z 8x1 6x2 3x3 6x4x1 2x2x4 3x2x3 x4x3x42x1x32xj 0, j 1,2,3,4(1)写出对偶问题;(2)已知原问题的最优解为X= (1, 1, 2, 0) T,求对偶问题的最优解。(18)已知线性规划max z x1

17、 4x2 3x32x1 3x2 5x323x1 x2 6x31x1x2x34x1,x20,x3无约束一一 一一 *X=（ 0， 0， 4）1 ）写出对偶问题；2）求对偶问题最优解。19） ) 设线性规划问题nmax zcj xjj1naijxjbi i 1,2, ,mj1xj 0, j 1,2, ,n20） 的 m线性规划_.一， .* * *种资源的影子价格为 yi , y2 ,，ym。nmax zcj xjj1na1 j xjb10j1naijxjbi i 2, ,mj1xj 0, j 1,2, ,n21）与 （ 1） 是等价的，两者有相同的最优解， 一 . . *请说明（2.）的m种资源

18、的影子价格为（yi /入，y；,，y：）,并指出这一结果的经济意义。（20）. 已知线性规划min z i2xi 8x2 x3 2x42xi2x2 x3 x43xi x2 x3 2x4xi, x20, x3, x40i ）写出对偶问题，用图解法求最优解；(2)利用对偶原理求原问题最优解。maX z 2X1X2X36(21)线性规划Xi X2 X3X1 2x2Xi,X2,X30的最优单纯形表如表 4-6所示。表4-6Cj2-ii00CbXbXiX2X3X4X52Xi6iiii00X5i003iii(T j0-3-i-20X2的系数C2在何范围内变化，最优解不变若C2=3,求新的最优解;bi在何范

19、围内变化，最优基不变如bi=3,求新的最优解;(3)增加新约束一Xi+2X3>2,求新的最优解;(4)i增加新变量X6,其系数列向量P6=，价值系数C6=i,求新的最优解。2(22)某厂生产甲、乙、丙三种产品，有关资料如表4-7所示。A63545B34530产品价格415(1)建立使总产值最大的线性规划模型；(2)求最优解，并指出原料 A, B的影子价格；(3)产品甲的价格在什么范围内变化，最优解不变(4)若有一种新产品，其原料消耗定额为：A为3单位，B为2单位，价格为单位,求新的最优计划。(5)已知原料B的市场价为单位，可以随时购买，而原料A市场无货。问该厂是否应购买B,购进多少为宜新

20、的最优计划是什么(6)由于某种原因，该厂决定暂停甲产品的生产，试重新制定最优生产计划。(23)分析下列参数规划中，当 t变化时，最优解的变化情况。(1) max z(3Xi3x12x22x22t)x1 (5 t)x241218(2) max z6x1Xi2x15x22x2X2乂21524 tx1, x20x1, x2 0(24)用分支定界法求解下列整数规划问题(1) max z x1 x2951x1 一 x2 一1414-12x1 x2 一3x1,x2 0且为整数(2) max z 2x1 3x25x1 7x2 354x1 9x2 30x1,x2 0且为整数(25)用割平面法求解下列整数规划问

21、题4x1 4x251x1 2x24X 6x255x1 2x2 16x x2x352x1x2 4x1 , x2 , x30且为整数x1,x2 0且为整数(1) max z 4x1 6x2 2x3 max z 11x1 4x2(1) max z3x1 2x25x32 x43 x§xx2x32x4x 47x13x34x43x5 811x16x23x43x5 3xj0或1j=1,2L5(26)用隐枚举法解下列0-1规划问题(2) max z 2x1 x2 5x3 3x4 4x53x1 2x2 7x3 5x4 4x5 6x1 x2 2x3 4x4 2% 0xj 0 或 1 j=1,2 L 5(

22、27)用匈牙利法求解下列指派问题，已知效率矩阵分别如下:382103791012872971312161764275151614158423511121516910691050米)如表4-8所示，请问如(28)已知下列五名运动员各种泳姿的运动成绩(各为何从中选择一个参加 200米混合泳的接力队，使预期比赛成绩最好。赵钱张王周仰泳 蛙泳蝶泳 自由泳表4-8单位：秒(29)分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表4-9所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完 成一项。试确定总花费时间为最少的指派方案。表4-9d人任务一一ABCDE甲252

23、9314237乙3938262033丙3427284032丁2442362345(30) 从甲、乙、丙、丁、戊五个人中挑选四人完成四项工作。已知每人完成各项工作的时间如表4-10所示。规定每项工作只能由一个人单独去完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务,在满足上述条件下，如何分配工作，使完成四项工作总的花费时间最少。表 4 - 10工作甲乙丙丁戊1102315925101524315514715420151368(31)求下列网络图从起点到终点的最短路线及长度。(1)40(2)(32).用破圈法和避圈法求下图的最小生成树(33)求下列

24、各图的最小生成树为5公里,(为(35)用标号法求图42中从v1到各顶点的最短距离问从水源经1号村镇铺设明K河各各村镇连接起来，应如何铺设使输水管道最短便于管理和维修，水管要求在各村镇处分开)。34567(37)用标号法求下面网络的最大流图43(38)求下列网络的最小费用最大流.括号内的两个数字，前一个是单位流量的费用后一个是该弧的流量.(2)(39)求解图45中所示的中国邮递员问题(A点是邮局所在地)2.240(40)如图46,发点Si, S2分别可供应10和15个单位，收点Ti和T2可接收10个和25个单位，求最大流，边上的数为cij 。(41)指出图4-7中所示网络图的错误，若能够改正，试予以改正。1j2b=df(c)图47(42)根据表4-11表412,所示的作业明细表，绘制网络图。表4 11表412工序紧前工序工序紧前工序a一a一b一b一c一cadadaecea , bfdfcgd , bgchf ,g , ehd , e , f（43）已知图4 8所示的网络图，计算各事项的最早与最迟时间。 b .，3）d - qe . 5 g i_6453 丁 6f10图48（44）试画出表413、表414的网络图，并为事项编号。表 413工序工时（d）紧前工序工序工时（d）紧前工序A15一F5D, EB1