天津大学运筹学考研历年试题分类

1、一、线性规划二、运输问题三、多目标规划四、动态规划五、图论六、网络计划技术七、决策论八、存储论九、排队论十、对策论十一、模拟技术一、线性规划(四)灵敏度分析(-)选择填空题 (二)线性规划建模(三)互补松弛应用(五证明題(-)选择填空題1.下面给出某线性规划问題的单纯形初表和终表(01-3020CbXbB-bX1X2X3心X5心0X171310200*4120-241000*6100-43081OjCb Xb B-bX X2X3心 X5X6X22/501/10 01/513/100X610-1/2 19(1)初表的出基变虽为,进基变虽为(2)最优基逆訂=(3)填完终表。(4)最优解X* =对偶

2、问题最优解h =(6)若原问題増加一个新的非负变虽.则对偶问题的最优目标值将(变大、不变、变小) o (2007)解：1. （1）出基变坦：为2：进基变虽为X3。21 J 0510沪=10o5101-i 12(3)CB Xb B-bX】X：X3X4x5Xft1 x242/510 1/10 4/50-3 x351/5 01 3/10 2/500 111 00 -1/2 10 1Oj1/5004/5 12/50心（45 ll)ry* =G1 0)（6）变小1. 用图解法解线性规划时，以下几种情况中不可能出现的是（）。A. 可行域（约束集合）有界，无有限最优解（或称无解界）B. 可行域（约束集合）无

3、界，有唯一垠优解C. 可行域（约束集合）是空集，无可行解D. 可行域（约束集合）有界，有多重垠优解（2006）解：1. A2. 根据线性规划的互补松弛定理，安排生产的产品机会成本一定（）利润。A. 小于 B. 等于 C.大于D. 大于等于（2006）解：2. B1. 用大M法求解Max型线形规划时，人工变呈在目标函数中的系数均为 ，若最优解的中含有人工变虽，则原问题无解。（2005）解：1、-M 基变虽1.设线性规划问題m ax&|4Yxno有最优解x和影子价格八则线性规划问题nwc&A|4r = bxno的最优解= ,影子价格=。（2004）解：1. x* 2y*3. 某工程公司拟从I、2、

4、3、4四个项目中选择若干项目。若令1, 第i个项目被选中.，X- = 9 z = L41o,第j个项目未选中请用兀的线性表达式表示下列要求：（1）若项目2被选中，则项目4不能被选中：（2）只有项目1被选中，项目3才能被选中：.（2004）解：3.x2+x4 1,X -x3 】 所乘，则改变后的问題也有（也有、不一定有）最优解：若有最优解，其最优解丄 土_（大于、小于、等于）z。2002）1.下列数学模型中a是线性规划模型。（2001）/,、. lx. + 6x, + 8x, 5x. + 9x, + 2.r,7X + 3x2 + 6x3 1504X + 4.r, + 5x3 0(b) max Z

5、 = mi叫一!= !=5X + 5x, + 3X3 3006x, + 9.y2 + 8x3 0解:2.下列图形(阴影部分)中b是凸集。(2001)解：3. 标准形式的线性规划问題，其可行解b是基木可行解.最优解a是可行解,最优 解a能在可行域的某顶点达到。(2001)(a) 一定(b)不一定(c) 一定不解：4. 目标函数取极小(min Z)的线性规划问题可以转化为目标函数取极大的线性规划 问题求解，原问题的目标函数值等于亠一 (2001)(a) max Z (b) max (-Z)(c) -max (-Z)(d) -max Z(a)最小元素法(b)比回路法1. 线性规划单纯形算法的基木步骤

6、是：(】) (2) (3)每次迭代保持解的,改善解值的对偶单纯形法每次迭代保持解的.改善解值的。(2000)解：确定一个初始基可行解：检验一个基可行解是否为最优解：寻找一个更好基可行解： 可行性：最优性。2. 设有线性规划问题minf = CX,XeR=YAX = h,X0,有一可行基B (为A 中的前m列)，记相应基变虽为X”，价格系数为Cb相应于非基变呈为Xn，价格系数为6,则相应于B的基木可行解为X=:用非基变虽來表示基变虽的表达式为Xb=:用非基变虽表示目标函数的表达式为匸. B为最优基的条件解:是o (2000)BWb-NXn，CBBb + (CN -CbBN)Xn, Cn-CbB1

7、N03. 线性规划(Min型)问题有多重最优解时，其最优单纯形表上的特征为：(2000)解：所有检验数阿星彷个非基变量检验数耳=0.6.某足球队要从1, 2, 3. 4. 5号五名队员中挑选若干名上场。令J1第i号上场X，= 0 第 i 号不上场，1=1,23,4,5请用出的线性表达式表示下列要求：(1)从1, 2, 3中至多选2名： (2)如果2号和3号都上场，则5号不上场： (3)只有4号上场,1号才上场：(2000)解：Xj + x2 + x3 2, x4-xs 0, X + 兀 lX2X42. 考虑线形规划问题max Z = 5xx+ 2x, + 4x3X + 2x2 + x3 (5)

8、 如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？ (1999)解：2. (1)min Bz = 5y, + 2y2 y2y25 2必-力=12H+3 泌 4ytoty2无符号限制292、(2)Y*=(-,)55292(3)955(2（5）变小1.下而给出某线形规划的单纯形初表（表1）与某一中间表（表2） （Min型）：表22/5617104?5x2X62/501/104/51/513/102/510-1/210O表1CBXBBb0X|1x2-3X30X42X50X60X1713-10200X4120-241000X6100-43081O)1）初表的出基变量为,进基变量为。2）填

9、完表2,该表是否是终表?o若是，最优值Z*=3）此线形规划对偶问题的最优解厂=（1998）解：1下而给出某线形规划的单纯形初表（表1）与某一中间表（表2） （Min型）表1CBXBB-b0X11X2-3X30X42X50X60X1713-10200X4120-241000X6100-4308101-3020O)表21x242/5101/104/50-3X351/50I3/102/500X611100-1/2101Oj1/5004/512/504）初表的出基变量为X4，进基变量为_X,o5）填完表2,该表是否是终表?_是。若是，最优值Z* =_-11此线形规划对偶问题的最优解厂o55解:解:解:

10、 解:解:解:（二）线性规划建模二（20分）、某化学制药厂有m种有害副产品，它们的数址为b, （i=l.，mk按照规 定，必须经过处理，制成n种无害物后才能废弃。设aij为每制成一单位第j（j=l,，n）种无害物可以处理掉第i种有害物的数虽，cj为制成一单位第j种无害物 的费用。1. 现欲求各无害物的产虽xj以使总的处理费用为最小，请写出此问题的线性规划模型：2. 写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（2007）解：1.Kminz=工=i如若+知吃+孤兀巴勺2円 + a22x2 +. + a2nxl,-的a. + 丹 +.+aj. 2耳五,七，, 0 maxz = XyA=

11、i竹川+知升+生仏壬 如开+32+ + %儿 S+ 2丿2 + d初儿=1 y=i工(z = l,2,-,5)1=1f a, (z = l,2r-,6)7=1AO (z = l,-6,y = l,2,-,5) 儿=0 或 1 (j = l,2,-.,5)1某厂使用A、B两种原料生产甲、乙、丙三种产品，有关数据见下表：AB生产成本（万元/吨销售价格（万元/吨）甲1.00.5830乙0.40.6520丙0.60.51835原料成本（万元/吨）57原料可用数虽（吨）350460（1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产虽分别记为X|K2,X3,约束依A,B原料次序)：(2)写出此

12、问题的对偶规划模型(2003)解：1 maxz=30xi+20x2+35x38xi5x218x35(xi+0.4x2+0.6x3)7(0.5xi+0.6x2+0.5x3)目标函数 maxz=13.5xi+8.8x2+10.5x3约束条 X|+0.4X2+0.6X3W350y 0.5x1+0.6x2+0.5x3460x & 0,X2 事 0,X3 N 0J对偶规划模型目标函数 minw=350yi+460y2 约束条件禺+0.5丫2事13.50.4yi+0.6y28.80.6y,+0.5y210.5三、（10%）某服装厂制造大、中、小三种尺寸的防寒服.所用资源有尼龙绸、尼龙棉、劳 动力和缝纫设备

13、。缝制一件防寒服所需各种资源的数址如表（单位已适当给定）。不考虑固 定费用，则每种防寒服售出一件所得利润分别为10、12、13元，可用资源分别为：尼龙绸 1500米，尼龙棉1000米，劳动力4000,设备3000小时。此外，每种防寒服不管缝制多少 件，只要做都要支付一定的固定费用：小号为100元，中号为150元，大号为200元。现 欲制定一生产计划使获得的利润为最大，请写出其数学模型（不解）。（2002）资源小中大尼龙绸1. 61. 81. 9尼龙棉1. 31. 51. 6劳动力44. 55缝纫设备2. 83. 84. 2解：三、解：设三种防塞服分别生产x,x2,x3件。z表示获得的利润,y.

14、,y2,y3分别表示01变 呈，=1表示做第人种防塞服（i=l,2,3）max z = 1 Ox, +12x, +13x3 -100” -150y, - 200p31.6X +1.8x, +1.9 15001.3x, +1 .5x2 +1.6x3 10004X + 4.5x, + 5x3 4000 2.8x, +3.8*2 + 4.2x3 3000 10000 j*!x2 lOOOOy, 屯 0 必，儿，儿=0或1（三）互补松池应用max z = 2xx+ 3x22x+2x2i2二（8%）、线性规划问題x+2x2S4 召 164. 0.而第1, 4两种资源（相应于第1, 4两约束）均有余址，应

15、用 互补松弛定理求出原问題和对偶问题的最优解。（2005） 解：二对偶问题min W = 12yt +16y3 +12y42必+儿+4儿，2必+2必+4j沦3yf0,/ = l,2,3,4f。，.其对偶问题取严格等式偿；第幕.第I俩种资源有剩余，即原问题约束（1啊格不等式 对应对偶问题变屋x =0,几=0代入（*）式，y2 + 4y3 = 2, 2y2 =3.炉* = 1）281612 A =14%由*X + 2x2 = 84.x,= 16lX2 =2综上，原问題最优解x = 4 2f,Z*=143 F对偶问題最优解卩=0 - - 0 ,FF*=142 8（四）灵敏度分析三（25%）、派公司是

16、一个生产高尔夫器材的小型公司，近期推出了高、中价位的高尔 夫袋新产品（标准袋和高档袋），经销商对此产品十分感兴趣，并订购了派公司下3个月的 全部产品。该高尔夫袋的生产过程主要包括4道工序：切割并印染原材料、缝合、成型（插入支 撑架和球棒分离装置等）、检验和包装。有关数据如表1。派公司须决定标准袋和高档袋各生产多少可使公司的总利润最大。表1单耗P品工序标准袋高档袋3个月内最大生产能力(小时)切割印染7/101630缝合1/25/6600成型12/3708检验包装1/101/4135产品单位利润(荚元)109(1)写出此问题的线性规划模型，约束依表1中次序：引入松弛变虽(依约束次序)后用单纯形法计

17、算得某单纯形表如表2,请填完表中空白，并判断其是否终表，如果是，请写出最优生产计划、最大利润和资源剩余：表21090000CbXbB-bXiX2X3心x5X69X225211.8750-1.312500心1200-0.937510.15625010Xl5400-1.2501.87500180-0.3437500.14062515-6.9375(3) 写出此问题的对偶问题的模型，及对偶的垠优解与最优值：(4) 写出成型时间的影子价格，求使该影子价格不变的成型时何的变化范围：(5) 若标准袋的利润可能发生变化，则其在何范围内变化时，可使原垠优计划不改变？图示说明其几何意义。(2005)解：三 设标

18、准袋生产旺，高档袋生产兀2(1) max Z = 1 Ox, + 9x,x. +x, 63010 * 2x, 4x, M 6002 1 6 22 x. + x, 0（2）GXbBxb10石9X20屯0斗00兀9X2252011.8750-1.312500心12000-0.937510.15625010X154010-1.2501.87500X61800-0.3437500.140625100-4.3750-6.93750S=Cj7B-Pj1.875-0.9375-1.25= -4.375-0.343750即1.875 x630-1.3125x (708 + Ad)0-0.9375 x 630+

19、lx 600 - 0.15625 x (708 + AZ)0-1.25x 630 +1.875 x (708 + A/)0-0.34375 x 630 + 0.140625 x (708 + A/) + lxl350（5）q变化，可能影响检验数，故令(y.=C.-CBB-xP.=C.- 0 10 + AC1.875cr3=C3-Cfl5_,=0-9 0 10 + AC0-0.9375-1.250-0.34375-13125(ys=Cs-CBBlP,=0-) 0 10 + ACo- 0 15625J 1.8750 解得 -3.75 MAC 3 3X + 2x2 18-X + 4x, 4标准型：*

20、2一小=3-3x, + 2x2 -x4 = 18一 X + 4x2 -xs =4 0, x, 0,x3 0,x4 0,x5 0 2.CBXBB-b100Xl200X20X30X40x5M心MX7MXu0X5400-14/31/3114/3-1/31100X】4102/3-1/30-2/31/30200X230I00100J00400/3100/30M-400/3M-100/3M最优广告计划x = （4,3/.即电视广告数虽为4,印刷广告数址为3,最低费用：W=1000达成情况为去污剂增加3%.恰好达标洗衣剂增加18%,恰好达标洗衣粉增加8%,超额4%完成对偶模型为：max f = 3y +18

21、y2 + 4y33儿-儿1+2, =4y3 0,y20,y30对偶最优解为:y=(400/3,100/3,0)经济意义：代表三种产品的广告的投资.3, 18. 4为每种产品广告单位投资后的于机， 100, 200代表用于电视及卬刷品的投资额，故该模型的含义为用每种产品的头则使其在不 超过约束的条件下达到利润最大化。(3X30%)考虑线性规划问题Min z=-4xi+X2+30x3-1 1x4-2x5+3x6+10x7-2x 1 +6x3+2x43x6+x7=20-4x +x2+7x3+x4x6= 10-5x3+3x4+x5-x6=60XjO0=l,2,-7)用单纯型法求解，初表及终表如下: 初

22、表CbXBB-b-4130-11 -2310X.X2X3X4XsX7-20620-31-417100005310检验数终表-4X5/47/2401/241/1245/21/1215/12-1/63X615/21/401/4-1/2检验数1填完初表和终表中各空白，并说明所得最优解是否是唯一的，为什么？2考虑当b变为F =両1360时，对垠优解有什么影响?当b变为b =18-1460时，对最优解是否有影响？3对偶问题最优解？(2003)解:3.CbXbB-b-4130-2310XX2 X3XsX6X710X720-20620-311X210-41710-10-2X56000531-10检验数200

23、-47-260320 =Cj.CBB-】Pj-2、51 =-4-(10 1 -2) -4 =-4+24=205-3、56 =3=(10 12) -1 =32-I(6a3 =30-( 10 1 -2) 7=-47a4 =-11-(10 1 -2)=-26-4X5/41-7/24-7/401/2401/12X445/201/12-5/215/120-1/63心15/201/4-5/201/41-1/2检验数0030201021/12-7/241/24、B-=B-*AN=-1/61/125/12-1/21/41/41/12 -7/24 1/24、%、=7/4、b-*p3=-1/61/125/127=

24、-5/2-1/21/41/4-5-5/2(-7/24、2=1-(-4-11 3) 1/12=0J/4 不唯一，因为存在非基变址检验数为零，则有多个最优解1/12 B)b= -1/61/2-7/241/121/41/24、5/121/4丿18、13 =g5/2423丄12 9丄4 .无影响H/12 -7/24B-b= -1/61/121/21/4S8、=1/12、14=-1/1260 z1/12.1/245/121/4/0有影响 0(j = 1,.,5)当tl=t2=0时，用单纯形法求得虽终表如下:Xix2x3X4X5X3 5/201/211/20X4 5/211/201/61/3CrZi040

25、42要求:1.确定 Ci, C2, C3, b|, b2, an, ai2 &i3 a?】，a22 23 的值:2. 当t2=0时，D在什么范围内变化上述最优解不变：3. 当1产0时，S在什么范围内变化上述最优基不变。(2002)八叫；就:H爲咸二又由-4 = C2-(C3C.-4 = 0-(C3C.)屮/2 1-1/2.1/2 ) 、-1/6 丿C,=6Q=-2k=io1/211/20 1fo1 21-1/20-1/61/3丿6-3 0-12丿01 21 11210)2 20 2)-1 i 0 1J0初表:12-11对应卅到an=0,ai2= 1山门二彳念尸彳山二1,833= 12. h变化

26、，将影响各检验数的变化，检验各非基变虽:检验数，若6jW0则最优解不变=-2-(10 6 + ；2卜=0-(10 6 + (Y：6)s =“8=0-(10 6 + r,)J0.因为Bx =1/2-1/601/3丿 = f1/2 V +1-1/6 1/3 人 10 + q 丿l/2(5 + 3r,)0=-5/3z, 15-1/6(5+ 3q) +1/3(10 + 0)巴0-二、（18分）某公司生产3种产品：兀,七,小,需要3种资源：技术服务，动力和行政 管理，公司经理助理根据公司实际情况，建立了使总利润最大的产品产量的线性规 划模型，并max Z = 1 Ox+ 6x2 + 4x3-v, + x

27、2 + x3 100（技术服务约束）si.- IO.y, +4x2+5x3 600（劳动力约束）2兀+ 2x, + 6屯 300（行政管理约束）采用单纯形法求得最优表格如下:V1064000Qjq*8Xix2x3治x5Xe6X2400/6015/610/6-1/6010X1200/6101/6-4/61/600x5100004-201-Z4400/600-8/3-10/3-2/30q在向总经理汇报时，总经理提出以下问题：1. 公司3中资源的影子价格各是多少？2. 若要现行解保持最优，则产品X】的单位利润不得低于何值？3. 若产品X3值得生产的话，它的单位利润应是多少？4. 制造部门提出要生产一

28、种新产品，该单位产品要技术服务1小时，劳动力4小时，行 政管理3小时。销售部门预测这种产品出售时可获8元的单位利润，管理部门是否考 虑应将此新产品投产？现请帮助经理助理回答以上问題。（2001）解：1公司3种资源的影子价格分别为：技术服务:，劳动力弓2. 对于第1种产品，产品壬，石的单位利润为G.看是基变量G变化将影响各非基变量检验数在保持巧，6, 60（內情况下，现行解保持最优，则：t3 = 4 -1 6C.06丄64(Q6_46-2牛=0-6= -10 + -C, 6C, 186亠沖。同理的：对于c 疋为基变量,q变化将影响各非基变量检验数CT, =C, 0336 2只要使：cr4=C,+

29、4C210,现行解保持最优6 -3-6 =丄0 - 05 6 2 6对于心,.*是非基变量,变化只对6有影响，只要保证O-3 0.现行解保持最优36.(T3=C3-610 oj | =c3-y C3 0,即G至少应为守4.设新产品为心则6=8- 61006_46-2_16 丄 60=2=8-60应将新产品投产3. 若产品耳值为生产，则X3应为基变量,在单纯性表中0,即C3至少应为丁4.设新产品为曲，则6=8-（6106丄64二(20%)有一线性规划为 Maxz = qX + c,x,s.t aHX| +aI2x, b,a21X! +a2，x2 0设X3,%4为引入的松弛变呈。得到最优单纯形表如

30、上表，要求：（1）利用最优解求5,C2.（2）利用虽优解求b.XbXt X, X,解10311%20I-1 12500-31-8（3） C,能变化多少而不至影响最优解：当时求最优解:(4)假定用b+XZ*代替b,其中7/20x2X3解x.10311X2011200-3-1-86=CCbB-Pa-l=0-(C.C2)C,=2,C,=3(3) G的变化影响检验数.设C?的变化址为ACt3=0-(2,3 + AC)3-10-2 +(3 + AC)0-1AC03-1302 2(5) X,=1,J=2Max = 2Xl+3X2丄兀+丄%,-2 * 2 2 2sJ X. HX-) 0第一种资源剩余为0第二

31、种资源剩余为0 影子价格分别为-3. -1解:解:解:解:(五)证明题三(15分)、考虔下面两个线性規划：(7) Minz = CX()Min z*= CX约束条件4T = b约束条件= hX0%0已知疋是(/)的最优解，炉是()的垠优解，试证：(CY)(X/O (2007) 解:三、因为 CXCX所以c(x-0)no(I)又因为CXCX9所以CXe-X)0(2)(2)-(1)得(CC)(X*-X)01. 若Xi*均为(P)的可行解，2g0,1,证明Zi + (1-2)X2也是(P) 的可行解：2. 写出(P)的对偶模型(仍用矩阵式表示)。(2006)三、1证明：令AXi + (l-A)X2

32、= X3,若*3是(P)的可行解，则应满足AXz = h(1)%30(2)因为购颯)的函行解,AXx =bX,0AX2=hX20所以九 = AAX + (1-2)%, = AAXx +(1-A)AX2=Ab + ( A)b = b即満足(1).又因为 20,1,0,%20,故有科A 0,(1-必“，所 13=+(1-2)%20,即溺足(2).所以也是确昭解刃*2(卩)2. 对偶模型min w = hTYAtYCty无限制三(10%)、证明线性规划中的互补松弛定理：设(P) (maxz=CX,XeX|AX0,(O) minu=Yb,YG YAb,Y0,?X Y分别是(P(D)的可行解，疋，忆分别

33、是其相应 的松弛变虽，则疋歹是(P),(D)的最优解的充要条件是：YXs = YxX = 0,并解释互补松弛定理的经济意义。(2004) 解：三、互补松弛定理的经济意义是：资源有剩余，则其影子价格为0,反之，影子价格为0说明 资源恰好用完。四、(21%)试证明线性规划原问题中第J个约束扩大K倍，其对偶规划最优解中第J个变虽 将缩小K倍(2003)解：四、设原问题为maxZ=CXAX=b对偶i/ 2/65、/、叭/ 、 XI*、(kajuka, kajn)Xj=kbj0z=CX 约束条件AX=bX0(/)Minz=CX 约束条件忒bX0已知：X是(I)的最优解，X是(II)的最优解，尸是(I)的

34、对偶问题的最优解, 试证：(1) (C-C)(X-X)MO： (2) C(X 无) 丫(方一了)。(2000)解：(1)因为 CX0(1)又因为CXnCX所以 cxx-xo-得 (cyxQ-xgo设迅的时偶问题的最优解C(X,-X) = CX,-CX = YTj-Yh 0 J时，设当前基B =)证明：若兀为某非基变量，检验数(yk=ck CbB Pk 0 ,由此确左人为进基变屋，则能保证新的基本可行解的目标值得以改善。(1998)2.证明: 令 A = (B,N)C = (Cb，CJ= hBXB + NXN=b=XB=Blb-BxNXy令当前即 f ) Xn =(o,o-.o)r带入目标函数

35、= CbXb + CKv = CBB-h + (Cn-CbBN)Xn ：. = CBBbx&入基后即xk=A0O= CBBxh +(CN - CbBN)A00=C詔祁+ G20= CBB-lb + (ck-CBB-Pk)A= +(rtA g(14%)对某线性规划问题MaxZ = CXAX=bX0已确定一可行基本说鱷变量价格系数向量,（1）请用数学方法证明，当所有非基变址检验数ai=cj-CBBxPi 0时，当前基本可 行解为最优。（2）请从经济含义的角度出发，说明上述判断的正确性。（1997）解：（一）确定换出基的变虽因为总存在0的令br = min （勺），其对应变虽为换出基的变虽Cb基bGS100%GXbr010r.nX00105+1J00C+l -m+1C宀Cn-zn（二）确定换入基变虽（1）为了使下一个表中第r行基变虽为正值，因而只有对应的非基变址才可以考虑作为换入基的变址