河北工业大学土木工程学院863运筹学（Ⅰ）专业硕士考研题库

2017年河北工业大学土木工程学院863运筹学（I）［专业硕士］考研题库（一）说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。一、判断题TOC\o"1-5"\h\zI■在任一图G中，当点集、确定后，树图是（；中边数最少的连通图。（ >【答案】x【解析】连通且不含圈的无向图称为树。2.指派问题效率矩阵的每个元素乘以同一大于0的常数k,将不影响最优指派方案。（ ）【答案】V【解析】效率矩阵每个元素乘以同一大于0的常数k,即目标函数的系数同时増大k倍，不会影响最优基的变化，故不影响最优指派方案。.结点最早时间同最迟时间相等的点连接的线路就是关键路线。（ ）【答案】V［解析】关縫路线是指总时差为零的工作链，而该工作链是由一系列最早时间同最迟时间相等的点连接而成的。.若X、X2分别是某一线性规划问题的最优解,则X顼的也是该线性规划问题的最优解'其中*入2为正实数。（ ）【答案】x［解析］入I入不但应该是正实数，还应该满足入L入2=1。.如果线性规划问题有最优解，则它一定是基可行解。（ ）【答案】V［解析】基解且可行才倒能是最优解。二、计算题已知下列资料。表r.fr紧arrir工序时向工序«I»X序工序时间工序紧前匸序工序时间AG,M3Ec51A.L2BH4FA.E5KF.lIcrGB,C2LB.C7DL3H—3MC3

要求:（1）绘制网络图;（2）用图上计算法计算各项时间参数（『除外）；（3）确定关键路线。【答案】（I）由题意绘制网络图如图所示。图（3）总时差为零的工序为关键工序，所以关键路线为①一③一④-⑤一⑥一⑦一⑩一⑪，对应的工为H—B—G—A—F—K。某厂生产A、B两种产品，需经过金工和装配两个车间加工，有关数据如表所示.产品B无论生产批量大小，每件产品生产成本总为400元。产品A的生产成本分段线性第1件至第70件,每件成本为200元；从第71件开始,每件成本为190元。试建立线性整数规划模型’使该厂生产产品的总利润最大。表r时定额（小时/件）产品廠有效「吋A B金「车间 装配4 32 5480500售价（元/件）【答案】设XI，X2为产品A300 520'B的个数岩则建立线性整数规划模型如下：maxz=$x[70*(300-200)+(300-190)*(丐-70)]+(!-<?)♦(300-200吊+(520-400)与4玉+3工2《480SJ2x,+5x2<500SJx,>0,x2>0且均为整数

8.判断表1和表2中给出的调运方案能否作为用表上作业法求解时的初始解?为什么?表1 表2、、、知他产地、'、、、知他产地、'、、、134，顼10151521525355钥*515151012345顼!15025。400220030050035030049021030058020100的駁24041055033070【答案】表1中有5个基格，而要作为初始解，应有m+n・l=3+4»l=6个基格，所以表给出的调运方案不能作为表上作业法的初始解；表2中，有1()个数基格’而理论上只应有m+n・l=9个，多出了—,所以表2给出的调运方案不能作为表上作业法的初始解。9.—个小型计算机服务系统’处理外来任务’平均每项任务的处理时间是20分钟，外来任务按泊松流到达，平均每小时到达21页任务，设处理任务的时间服从负指数分布，先来先服务。求：(I)系统内空闲和系统内任务数超过3项(>3)的概率。(2)系统内彳壬务的平均数和任务在系统内的平均逗留时间。(3)若规定每项任务到系统，在1小时之内处理完毕’贝!］收费50元。在1至2小时内处理完毕，收费40元。处理时间超过2小时则收费20元。回该系统平均1天(以8小时计算)可收费多少？212Px=p(y-p)=-x-=-宀2(顷专)4=寿5*)=眾=§.財捞艘过三项的概率为：(2)Ls=—^—=—=2吧=丄=丄=1s”人3-2I3-2(3)任务在系统内逗留时间服从参数为〃一2=I的负损数分布,分布函数为:F(w)=\-e~w:.P(w<l|=F(l)=l-e_,=0.632P{w<2}=F(2)=1-广=0.865P{wv2}=l-P{wv2}=l-0.865=0.135/.P(1<vp<2)=I-P{w>2)-P{h^<1)=1-0.135-0.632=0.233.・.每天可收斐用为：8x2x(0.632x50+0.135x20+0.233x40)=697.9(元)10.某厂生产三种产品I，II.HIo每种产品要经过A,B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A”A2表示:有三种规格的设备能完成B工序，它们以B（,B2,B3表示。产品I可在A，B任何一种规格设备上加工。产品II可在任何规格的A设备上加工，但完成B工序时，只能在Bi设备上加工;产品III只能在A2与设备上加工。已知各种设备的单件工时,原材料费，产品销售价格，各种设备有效台时以及满负荷操作时设备的费用如表所示。要求安排最优的生产计划，使该厂利润最大。表设备产品设备有效台时满负荷时的设备费用《元）1IIIDA,5106000300A>7912[(XXX)321B>684000250&4117000783&740CX)200顷料費（元/件〉0.250.350.50单价（兀/件）1.252.002.80【答案】设旳，X2分别为用A|,A2加町品I的件数，X3,X4,X5分别用0,B2,B3加工产品I的件数；X6,幻分别为用A|,A2加工产品II的件数’则X6+X7为用0加工产品II的件数;X8为用I及％加工产品m的件数。由题意’可建立数学规划模型：maxz=(L25-0.25)(X|+上)+(2-0.35)(.匕+.七)+(2.8-0.5).上—膘(5*“0・门)一識(7“一-—(6志+8a-6+8a7)一-—(x4+llx8)一-—x7x5TOC\o"1-5"\h\z4000 3 6 7 7000' 8 4000 35x>+ 0007x24 4-12X.C1O0006x3+«(+工。顽0005.t.-4x.3II.r. 000得X；=1200.x：=230,A-；=0,x：=859,x；=571,兄=0,*=500,*=324;得=1147。即用A[加工产品11200件，用A?加工产品I230件，用Bi加工产品10件，用B?加工产品1859件，用B3加工？23品】571件，用Ai加工产品II。件，用A?加工?^品11500件，用B|加工产品11500件，用A2及B?加工产品III324件，可获得最大利润1147元。11.某公司有五台新设备，将有选择地分配给三个工厂，所得的收益如表所示11.某公司有五台新设备，将有选择地分配给三个工厂，所得的收益如表所示表表【答案】将问题按工厂的个数分为3个阶段，设火表示为分配给第k个工厂到第n个工厂的新设备数目,冷表示为分配给第k个工F的新设备数目，则=邕寸为分配给第k+1个工厂至第n个工厂的设备数目，4(叫)表示为Xk个新设备分配给第k个工厂所得的收益,fk(%)表示为sk个设备分配给第k个工厂到第n个工厂时所得到的最大收益。因而可写出逆推关系式为A(s*)=max[Pt(玉戚h(&叫)],k=3,2,1Z.(s4)=o下面从最后一阶段开始向前逆推计算：第三阶段：第二阶段:

\以七）X；0123410+4—4020+75+07030+10—5+47+01004——5+77+49+01225——5+107+79+4152第一阶段:得到最优分酉己方案为:分配给工厂I两台新设备;工T3三台新设备，可得最大收益为16。mP455初始偵T(vp0oooo8oooo第1次选代P<v()+wu0+10+20+oo0+80+-oo卩怫号[]T(vPrn2CO8第2次迭代P<v,)+wQ1+31+314-001+7〃标号[]T(v,>⑵4co8第3次迭代p(u)+w.,2+22+22+8卩标号[]TCwJC4]48第4次送代PS+w„4+do4+3卩标号[]T(v,>U37第5次送代/>(u)+4+6P妹号】1TtvPm从表可以得出任意一点到另外任一点的最短路。（1）从V|开始到各点的最短路。d（v\,血）=1，最短路为（5,辺）；

d（s,阴）=1,最短路为（m*v3）；d（功，以）=4,最短路有2条、分别为（功，s,%）或（功，防，叫）；d（5泓）=4,最短路为e»Vj»u5）«d（功g）=7,最短路为（叫，％,以泓）.（2） 从V2开始到Vj的最短路。dSs）=3,最短路为S"d（m，山）=3,最短路为（"2，％）；，咨）=5,最短路为（此，明»Vs）id（巧，W）=6,最短路为（巧，叩外）./不能到达V，故对V2而言，叫为不可达点。（3） MV3M发到各点的最短路。d（S，辺）=2,最短路为3•以）$d（巧，外〉=2.最短路为E」（巧，W）=5,最短路为（勺，明，强）.V3不能到达M和V2,故V|,V2为V3的不可达点。（4）从V4出发，只有一^路（％V6）,且d（v4,v6）=3。（5）从V5岀发,只有一^路（v5,V6）,且d（V5,v6）=6O（6）从V6出发，则无路。13.举例说明，当运输问题的最优解中所有的基变量均大于零时，该运输问题有无穷多最优解;【答案】举例如下：、^地B.、^地B.B?A,311a2L3764销量36Bi瓦产最532107l2IZ141035956对非基变量求检验数，如表所示:如表中空格（1,I）的检验数是0,其他检验数都大于0,表明有无穷多最优解。2017年河北工业大学土木工程学院863运筹学（I）［专业硕士］考研题库（二）说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。一、判断题•如果线性规划问题无最优解，则它也一定没有基可行解。（ ）【答案】x【解析】当问题的解为为无界时’此时该规划问题无最优解,但存在基可行解。.若需将某工程项目工期缩短到了10天,简单可行的方法是任意找出该项目网络中一条关键路线，采取必要措施将其缩短到10天即可。【答案】V［解析】若网络计划图的计算工期大于上级要求的工期时，必须根据要求计划的进度，缩短工程项目的完工工期。主要采取以下措施，增加对关键工作的投入，以便離关键工作的持续时间，实现工期缩短。①采取技术措施’提高工效，缩短关键工作的持续时间，使关键线路的时间缩短；②采取组织措施，充分利用非关縫工作的总时差，合理调配人力、物力和资金等资源。.绷4规划问题的每一个基解对应可行域的一个顶点。（ ）【答案】x【解析】基解不一定是可行解,基可行解对应着可行域的顶点。对于一个有n个变量,m个约束方程的标准线性规划SLP,其基可行解的数目恰好是（个。（）【答案】x【解析】其基解的个数最多是个，且一般情况下，基可行解的数目小于基解的个数。目标规划问题的日标函数都是求最大化问题的。（ ）【答案】x【解析】当每一目标值确定后’决策者的要求是尽可能缩小偏离目标值，因此目标规划的目标函数只能是最小化的。二、计算题6.在图中,(1)用Dijkstra方法求从、倒各点的最短路；(2)指出对v来说.哪些顶点是不可到达的。图【答案】(1)P(片)=0,(小=+00(丿=2.3,・・・,8)计算从引到各点的最短路的步骤如下：V1已经获得P标号，(卩|,卩2)，(片，卩5)，(卩1，卩7)€丹，修改\2v5,v7的T标号T(s)=P3)+心2=0+4=4,T()=P(vi)4~wI5=0+1=1T(v7)=P(vl)+wi7=0+3=3因为min{T(v2),T(v5)♦T(v7))=1=T(v5),所以有p(v<)=i0v5已经获得P标号，(v5,v6)eA,改写v6的T标号为丁(卩6)=户(的)+使6=7，因为rnin{7'(衫)，丁(％)，丁(S)>=3=丁(s)，所以有P(v7)=3。*已经P标号，因^min{T(v2),T(v6)}=T(v2)=4,所以有P(*)=4°％己经P标号，所以有P(v6)=7o*己经P标号，(*,*)仕人，改写卩8的T标号为「(*)=户伉)+%T°，故P(V8)=10。于是，有V|到各点V2,V5,V7'V6.V8的最短路为d(切,/)=?(/)=4,d(趴，捲)=P(p5)=l，dWi,e)=F(功)=34(凹，P6)=P(t0=7,d(5,s)=P(0)=l。(2)V|不能到达V3及V4。7-已知图表示7个城市间拟建一条连接各个城市的通信线路，各边的权数表示两个城市之间的修建费用，求连接各城市通信线路最小修建费用方案。B52图CB52图C【答案】最优方案为:

4242可使修建费用为最少。x.试用步长加速法(模矢法)求下述函数/•京)=药+2成一x.试用步长加速法(模矢法)求下述函数/•京)=药+2成一4勾一2七血的极小点，初

050始点对=(3,1/，步长禹=~00.50并绘图表示整个迭代过程。【答案】按照题目要求，采用步长加速法进行迭代，迭代过程如表所示。

表kB./(Bt)八曷+4“河一AQ111/(Th+3：)/(Tu-Az)B：=Ti2f(B:)](3.1)T-76.75-6.75(3.I)T-7.5—(3.I.5)T-7.5k孔/CT.o+di)叫码f)=乌/(B*4-1)2(3,2)丁-7-7.75(3.5.2),-6.75-7.75(3.5,1.5),-7.753(4.1.5)T一7.5—6.75一7.75(3.5,1.5)T-7.75—《3.5,2)1-7.754(3.5,2.5)T-7(4.2.5P-6-8(4.2>T5-7.75—8(4.2)r-7.75-7.5(4,2)T-8注：表中的叩‘表示其值不必计算。B6= =(4,2卩，此时应在点B6=B5=(4.2)1附近搜索，缩小步长以求得符合精度要求的结果。所以，最优解为(4,2)丁其迭代过程如图所示。9.企业A是位于南京路的一家专供某类零部件的加工企业，生产产品DXF,正常生产条件下可生产12百件/天，每百件定价8万元。根据供货合同，需按9百件/天供货。存贮费每百件0.16万元/天,允许缺货’缺货费为每件0.65万元/天,每次生产准备费为80万元。要求：(1)绘出存储状态图，并说明存储过程；(2)求最优存储策略。

【答案】由题意可知，P=12.R=9,Q=0.16.G=0.65,C3=8O,K(Q)二8,订购费为C‘+K(Q)最优存贮策略各参数为：最优存贮周期:「 2x80x0.81=12V0.16x0.65x9经济生产批量:。・=肝=108歹时间";備E最大存贮量:AJ金;J87最大缺货量：£=卢当/=22C]+02平均总费用为：b=专=14存贮状态图如图所示。10.(1)每月需要某种机械零件2000件，每件成本150元，每年的存储费用为成本的16%,每次订购费100元’求E.O.Q及最小费用。(2)在题(1)中如允许缺货，求存储量s,及最大缺货量，设缺货费为C2=200元。【答案】(1)用"不允许缺货，生产时间很短”的模型求解。已知C广100,R=2000x12=24000,C,=150xl6%=24oX100X24000=447（件）24X100X24000=447（件）24最小费用为( (% 声=24X岑十100X号釋eio733(元)所以，最佳批量为447件，最小费用约为10733元。(2)用“允许缺货,生产时间很短“的模型求解。己知0=24,@=200,C3=100,R=24000,故2C2CsRs・2C2CsR最大缺货量为Q—S=2RQGG（G+G）1最大缺货量为Q—S=2RQGG（G+G）12x24000x24x100V200x（24+200）所以库存量S为423件，最大缺货量为50件。II.某公司要将一批货从二个产地运到四个销地，有关数据如表所示。表B.&耳H,供应量A|7379560A?265II400A36425750需求最320240480380现要求制定调运计划，且依次满足：(1)B3的供应量不低于誕量；(2)其余销地的供应量不低于85%;A3给母的供应量不低于200;A2尽可能少给所;(5)销地B2、B.,的供应量尽可能保持平衡。(6)使总运费最小。试建立该问题的目标规划数学模型。【答案】设乂讦为A到耳的运量，数学模型为ninz=Pxdx+P2(d2+</3+£)++乙"；4(〃7+』；)+SJ.<Xl3+工23+*33+4 d；=480x11+x2I+x31+J2--J：=274SJ.<X\2+x22+X32+d；-d；=204玉4+如+知+d；-d；=323x33+d；-d；=200知-d；=02xn+2x2I+2x31_丹2一x22一血+d；-d；=0內一瓜=°J=l七20= …,8）;B3保证供应Bi需求的85%B?需求的85%需求的85%A3对B3A?对BiB2与B3的平衡运费最小12.某公司从两个不同的仓库向三个客户提供某种产品，由于在计划期内供不应求，公司决定重点保证某些客户的需要，同时又使总运输费用最低’现已知各仓库的供应量（吨），各客户的需求量（吨）及从各仓库到每一客户的单位运费（元濺>相关娜如表所示。根据供求关系和公司经营的条件,公司确定了以下目标变量：Pi表示客户几的需要；R表示至少满足各客户75%的需要；P3表示使总运费最少；P4表示从仓库I至客户B|,只能用船运货，最小运量为1000吨：P5表示从仓库A2至客户B],从仓库戊至客户残之间的公路正在大修，运货量应尽量少；P6表示平衡用于B和B?之间的供货满意水平。试建立该问题的目标规划模型。【答案】设Xij为仓库i到用户j的运输量（i=I,2；j=l,2,3）;d「，d：为第i个目标约束条件中，未达到规定目标的负偏差变量和超过目标的正偏差变量。由题意可建立如下的目标规划模型：minZ=*邳+与（右+邳+邳）+乌尤+£打+乌（1.2/£+端）+丛（弗+端）xn+xn+m+d「=3000x31+x22+如=4000xn+勺1+邳=2000xl2+x22+d\=1500xn+x»=5000%+d；-d；=1000亦11+5+邳一d；=1500s£<x12+也+応一邳=1125x13+工23+邳一邳=3750知=o工勾-苟=03曲-4如+3叫】-4闩+端-吨=010xn+4x12+12xb+8冷］+10x22+3^23一d占=0%"J=12丿=1,2,3邳，邳N0J=12…,1313.某公司预计下3个月对某种产品的需要量分别为150件、250件和300件。下3个月各月生产能力和生产费用等有关数据如表所示。产品的存储费为20元/件。试回答如下问题：表月份生产能力(件)费用(元/件)第1月29050第1月加班10080弟2月24050第3月20060(1)将其看作运输问题，画出其网络图；(2)建立使总费用最小的生产与存储方案的数学模型；(3)写出该问题的运输问题调运表,并用最小元素法列出问题的初始基可行解。【答案】(1)看作运输问题时，其网络图见图：产地销地产地销地SJ3月生产图(2)根据(1)中的网络图，令产地i的产量为ah销地j的销量为顷产地i到销地j的运输量为临、单位运费为c*由于该问题为产大于销的运输问题，于是可建立如下数学模型：43minx=££c內1=1>1£七Kq(i=l,2,3,4)史易珀(J=123)瑚七20(3)该问题的运输问题调运表为由于该问题为产大于销的运输问题，所以增加一个虚拟的销地4,其销量为130,各产地到宝抓稣返的单位运价为0。得到产销平衡表为：

用最小元素法列岀问题的初始基可行解为：表X1234产殴11501013029021001003240240470130200销量1502503001302017年河北工业大学土木工程学院863运筹学(I)［专业硕士］考研题库(三)说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。一、 判断题•己知V为线性规划的对偶问题的最优解，若yi=o,说明在最优生产计划中第i种资源一定还TOC\o"1-5"\h\z有剩余。( )【答案】X【解析】在生产过程中,如果某种资源乓未得到充分利用时，该种资源的影子价格为零。但是影子价格为零并不单表该种资源一定有剩余。.网络图中任何一个结点都表示前一工序的结束和后一工序的开始。( )【答案】x［解析】网络图的起始点只表示一工序的开始，结束点只表示一工序的结束。.假如到达排队系统的顾客为普阿松流，则依次到达的两名顾客之间的间隔时间服从负指数分布。( )【答案】V【解析】设N(t＞为时间［0,t］内到达系统的顾客数，贝!J{N(t),20}为参数入的普阿松流的充要条件是：相继到达时间间隔服从相互独立的参数为入的负指数分布。.整数规划问题最优解的目标函数值一定优于其相应线性规划问题最优解的目标函数值。()【答案】x［解析】因为附加了整数条件，其可行域比其相应线性规划问题的可行域减小，故整数规划问题最优解的目标函数值一定不优于其相应线性规划问题最优解的目标函数值。.如果图T是树，则T中一定存在两个顶点，它们之间存在两条不同的链。( )【答案】x［解析】连通且不含圈的无向图称为树。因此任意两点间必定只有一条链。二、 计算题.国内某电缆公司利用包括5个分销中心、8个客户区域的分销系统来销售其产品。配给每个客户区域一个专门的资源供应商•且其所有电缆产品都来自同一分销中心。为了能平衡分销中心的客户需求和雇员的工作量，公司负责物流的副总裁特别指明一个分销中心最多负责3个客户区。如下表就是从5个分销中心到8个客户区域的供给成本(单位:1000美元、求：(I)使总成本最小的分销中心一§户区域的组合方式；

如果有’哪一》销中心没有任务分派；若进一步规定每个分销中心最多只能负责2个区域，那么新的分配方案又是什么?【答案】(I)由题意知该题为指派问题，添加虚拟的人,【答案】(I)由题意知该题为指派问题，添加虚拟的人,用匈牙利解法，具体过程如下:(2)由上一小题可知,第二(2)由上一小题可知,第二2、5、7没有修7047225398212713、(5134940868140、75381958903440265619039711521715783782111402932063226796251417602383982363245 V521503174282437454029758625II37—>3429186475140260000000000000000000000000000000000000000,00000000?0000000r001000001000000000010000->00000010010000000000\000k0000010u6、(3)表弋域中客户区域1客户区域2客户区域3客户区域4客户区域5客户区域6客户区域7客户区域8中心I7047225398212713中心27538195890344026中心315783782111402932中心4602383982363245中心54540297586251137.将下列线性规划问题变换成标准型，并列出初始单纯形表。(1)min-=一3小+4.弓-2玉+5x44jv,-x2+眼3_龙1=一2.V)+寻+3.q <14sJ.<-—2x1+3.r,一也+2x4>2.v(,x2・20,也无约束(2)maxs=zk!pk，imS.!.<=T(i=1,2,•••,〃)S.!.<k=\xik>0(7=12?・〃:k=L2.・・・m)【答案】(1)乩=x/-x4,•.且J”20；在第一个约束条件两边同时乘以-1后引入人工变量X5,在第二个约束条件右端加上松弛变量X6；在第三个约束条件右端减去剩余变量X7,同时加入人工变量細将目标函数最小化变换为最大化，得该线性规划的标准型maxz'=3x(-4.1,+2x,-5(.r4'-x4")-Mxs-Mvs一4与+x2-2x3+.v4 n+x5=2x+x2+3x.-x.*+"+x=14sJA一2.%+3x2-Xj+2,v4一2.q‘一七+玉=2xpx2,xv.r4'，七”,与,七,与，必20其中，M为充分大的正数，对应的初始单纯形表如表所示。表_42-55-M00-MCBXrbZ|XIXiXixiX5XTXlxi 2—4I-21-110000X6 H113—110100-Mxa2-232-20071-6M+34M—4-3M+23M-5一3M+500一M0(2)在上述约束条件两边同时乘以-1,然后分别引入人工变量X|,X2，…,Xn，得该线性规划的标准型maxs=—££aikxik-Mx}-Mx2 MxnPk»=i*=i其中’M为充分大的正数。对应的初始单纯形表如表所示。表-M•••-Ma\\/f>ba\^/pk•••5/ph侦/phChxubXlXl丁・工n•••X|M•••X„|•••1—_M110―01100-M工2101000•••.••:••••一M-Tr100100•••116nM0…0a\\/ph+M…a\」p./M•••a^\/pk+M•••8.某季节性商品必须在销售之前进行产品的生产决策。当需求量是D时，生产X件商品的利润(元)为：|2x DfiX)=[2D-xx>D设D只有4个可能的值，100、200、300和400件，且它们的概率均为0.25。(I)列出该决策问题的决策表；(2)若要求利润最大，生产者应该如何生产？(3)若生产的产量只有100,250和400件三种可能，请用后悔值法作出决策；(4)在第(3)问的基础上，若要求润大于等于500元的概率最大，生产者应该如何生产?【答案】(1)表决策收益表收\需'益\求1002003004000.250.250.250.251002002002002002000400400400300-KX)1006006004002000200800(2)当策略为生产100件时,期望收益为200x0.25+200x0.25+200x0.25+200x0.25=2000当策略为生产200件时，期望收益为0x().25+4(X)x0.25+400x0.25+4()0x0.25=300。当策略为生产300件时’期望收益为-100x0.25+100x0.25+6()0x0.25+600x0.25=300当策略为生产400件时，期望收益为-200x0.25+0x0.25+200x0.25+800x0.25=200(3)当生产的产量只有100,250和400件三种可能时，决策收益表如表所示。表决策收益表收\需1002003004000.250.250.250.2510020020020()200250-50150500500400-200020()800韻直表如表林表后悔值表

故在后悔值准则下的决策为生产250件。(4)由(3)中的决策收益表知当策略为生产100件时’利润大于等于500元的概率为0;当策略为生产250件时，利润大于等于500元的概率为0.5;当策略为生产400件时，利润大于等于500元的概率为0.2。所以，此时的决策为生产250件。9.设有线性规划LP：mixz=cixl+c2x2s.t.+al2x2^b}在第一二约束电分别加入松弛变量X"由(》0)，并用单纯形法求解，得到最优单纯形表如表基变量Xl基变量XlXjXi10X201-z(crq)00x3X4常数项4/5-1/531/51/51-21/5-1/5-17%【答案】(1)宀%%腐)=卩03)%呸4%【答案】(1)宀%%腐)=卩03)%呸4丿>I丿原规划为Lp:maxZ=4.r+5.r,(2)LD.minw=4.V］十处C=4(1)求出原规划LP。(2)写出LP的对偶规划LD。(3)求LD的最优解最优目标值。X〔+.弓至4x^x2>0其_力24SJ-yl+4v2>5凹_丹20(3)Lp的最优解为(3,1)T,最优目标值为4x3+5x1=17由强对偶性minw=max<=174 21凹一力=4Ji=y凹+4力=5y2=|10.试用可行方向法求解minf(X)=2xf+2妨—2刀火—4工【一6再俨i+舟W2s.t.J+5工2<5(xl［答案］原非线性规划问题可改写为：min/(X)=2xi+2药一2耳Xj—4xi—6x2Xi(.¥)=~<X|+x：)+220s.t.k：(X)=—6+5心)+5N0可,飞2。0取精度气0=勺=°丄初始可行点泌‘二(0,0)「。则」工1r4xi—2x»—41W(X)= *= *a/ L4x?—2j|—6J"x)=(n)T,女m-ipr因为⑷)=2・g：(X>=5>0,所以J(x(°>)为空集。而IW(X)I；=16+36=52>ex©不是近似极小点。取搜索方向D^=-Vf(X'°»)=(4.6)\贝iJ|r,=X<0,4-AD<0,=(4A.6A)T，将其代枱束条件，并令⑴)=G彳争”=0.2;令饥(*⑴)=0,彳事2=5/34<0.2。又f(X(l>)=32人2+72A2-4822-162-36A=56A2一522,令堂零12=0,即56X2』一52=0,解得人=崩>芸因此為=人=5'34,X"=(10/17,15/17)、/(Xa,)=-1860/289=—6.436Vf(X)(-58/17■-62/17)。赢(X"')=9/17>0,g」X⑵)=0

则构成下述线性规划问题:minv1-58

u为便于用单纯形法求解，令yi=4+1，北=』2+1，、3=一），从而得到min(—y3)s.1.58.62 ，、120心'少2。引入剩余变量y，，松弛变量ys，*，y?及人工变量加，得线性规划问题:mm(—*十My.)58»/17+62“/17—y,—y+^8=120/17、+5、2+乂+，5=6s.t.yi+>6=2>：+)7=2其最优解为:力=2,>2=2449,y=76/49,乂=为=乂=0,以=74/49,少=0?=一”=一76/49,而»|=76/49>&。搜索方向为刀2」L北一1」L—25/49.所以rz,=ru+AO,,>-（10/17,15/17）t+A（1,-25/49）t心卜2（卽）、2借噎）T即俏嗚）-4（即）一6（书一斜令四W，贝以=0.551。（IX于是= .2953.耳一爵X0.2953）'=（0.8835.0.7317）T因为&（X⑵）=0.26〉0,82（X⑵）=0.856a0,所以W为可行点,/（x⑵）=-6.583。11.试用牛顿法求解max了0)=/+，+2,取初始点X'°)=(4,0)「，用最佳步长进行迭代。然后采用固定步长入二1，观察迭代情况’并加以分析说明。【答案】令F(X)=—=云+£+2,要求f(X)的极大点即求F(X)的极小点。仿照的J\^)解法，可得「201VF(X(8,O)LfHro,)=,/£(^0>)_,=Lo2Jx=嵌-心r [彳i/2][o]=[o]即极大点为x・=(o,o)‘‘=由上可知，步长入=1。故采用固定步长入=1与采用最佳步长情形一致。。12.写出下列线性规划问题的对偶问题。（1）minz=2Xj+2x2+4x32玉+3x2+5x3>2s.f.<3玉+x?+7x3<3s.f.<-V|+4.y2+6.q<5（2）maxw=玉+2x2+3x3+4x4+x2-Xy-3x4=56.v,+7x,+3x}-5x4>812x,-9x2一9x3+9x4<20>0,Aj<0,土无约束■ mn（3）minZ=££q內7尸1（丿=1.2,・・.〃）（j=1・（丿=1.2,・・.〃）（j=1・2,・••.，〃：丿=1.2,・••.〃）maxSJ.4<-%"Z-用2.£勺丐=4(j=SJ.4<-%"Z-用2./-IXj>0(J=l.2.-,nl;nl^n)x无约束(/="]+顷+2,…•〃)［答案］(1)设对应于各约束条件的对偶变量为刃，y2,y3,则其对偶问题为:max6j=2y,+3y,+5j3•〃)2凹+3巧+又《23凹+、2+4必《25y,+7v2+6y3<4y\no,力，为二o(2)设对应于各约束条件的对偶变量为无，y2,y3,则其对偶问题为：min口=50+8*+20y,-乂+6力+12丹21凹+7力-9%22sj.-乂+3)，2-9丹<3-3^-5刈+9%=4凹无约束，为丁0,为20为:(3)设对应于各约束条件的对偶变量为皿=12・・・,冲，刈仃=1.2,・・・,〃)，则其对偶问题为:max/= 丿/=ij=iX+y^j*(i=1,2,・••,/n;J=12••,〃)sy,,无约束«=1,2,・・m；J=1,2,••m)(4)设对应于各约束条件的对偶变量为\;(i=1,2,・・・.，”)，则其对偶问题为:所min("=£b,y,/•I心sj.\Eauyi=ci(/=%+1,外+2,・••,〃)M叫20(/=1,2,-••,?«])其无约束 。=叫+1,吧+2,・••,，〃)

13.用破圈法和避圈法求下列图中各图的最小树。（al）采用避圈法。首先从图（al）中选取最小边e13=l,以后每一步从未选出的边中选出一个边上权最小的边，并使之与前面己选的边不构成圈（若在某一步中，有两条或两条以上的最小权的边时，贝！J从中任选取T＞直到不能选出为止。于是’以｛阳eI5,e3,e9,e10,%w｝为边构成的图恰好就是—支撑树,如图（a2）所示,其权为16。（a2）采用破圈法。在图（汨）中任取一个圈，例如（V”V2,V3）,从中去掉权最大的边（此处

去掉边e2=8）,在余下的图中，重复上述步骤，直到此图不再含圈为止。其具体过程如下:取圈（V[,V2，V3）,去掉最大边。2=8；取圈（V[,V2，V3,v4）..去掉最大边ei=7;取圈（V2，V3,V7）,去掉最大边。8=2；取圈（V2，v4,v6）,去掉最大边e?=7;⑤取圈（V3,v7»V8⑤取圈（V3,v7»V8）,去掉最大边en=3;⑥取圈（V|,V4,V5），去掉最大边E；⑦取圈(V6,V7,V8）,去掉最大边ei2=5:⑧取圈（⑧取圈（V2，V4,V6，V8，V7,V3>去掉最Xifiei6=4；⑨取圈（⑨取圈（V|,V4,V5,V6）,去掉最大边e（,=4;⑩取圈V5,V6，V8）,去掉最大边ei4=6。在图（al）中通过10次破圈后留下来的图仍然还是（a2）,这就是一个最小支撑树。(bl)(bl)（2）给图（b）中的顶点和边编号v,和勺，如图（bl）所示。①采用避圈法。类似于（1）的避圈法’最后’由边集合｛。3,e2,e5,e”％,e®｝构成的子图（见图（b2））是f最小支撑树，其权为12。②采用破圈法。与（1）中的破圈思路相同，通过破去图中帰e4,e6,ei。和叫;这五条边以后余下的边集｛也，。3,e5,e7,e9,电构成的子图就是原图的一个最小支撑树’此最小支撑图正是先前的图（b2I（3）给图（c）中的顶点和边编号H和印如图（cl）所示。(cl)（c2）采用避圈法。按照图中的边的权的大小，依次从小到大逐步选取边,并使之不构成圈，直到不能选取时’经过九次选取后，得至啲边集合｛e“e2,e5,e6,e8,e9,e!0,eM,e、｝构成的图即为图c的fB小支撑树，如图（c2）所示，此支撑树的权为19。采用破圈法。应用破圈原理,经过七次破圈’去掉了权数较大的七条边:。3,e4,”，％,ei4»e”和eg。而余下的边集合B，e2,e5,e6,e7,e8,e,0,e,He^｝构成了一个无圈的图即为图4（c）的另一个最小支撑树,如图（c3）所示。此支撑树的权仍然为19,这说明，图（c）的最小支撑树不惟一’但其总权均为19。（d2）（4）给图（d）中的顶点和边编号V和勺如图（dl）所示。采用避圈法。依照图的边的权从小到大依次选取,并与先前选出的边不构成圈的原则，逐次选边，直到不能再选为止。经过六次选边，得到的边集合｛5,e2,eI0,e8,e6,e’｝构成了如图（d2）所示的最小支撑树,此支撑树的权为17。采用破圈法。应用破圈法的原理，经过六次破圈，共破去图中边。3,S臨%,E和余下的边集合｛ei，e2,e10,e8,e6,功构成的图即为原图的最小支撑树，（d2）其总权为17。2017年河北工业大学土木工程学院863运筹学（I）［专业硕士］考研题库（四）说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。一、 判断题•运输问题按照最小元素法给出的初始基可行解，从每一空格出发可以找出且仅能找出惟_的闭合回路。（ ）【答案】V【解析】从每一空格出发一定存在和可以找到惟一的闭回路。因（m+n-1）个数字格（基变量）对应的系数向量是一个基。任一空格（非基变量）对应的系数向量是这个基的线性组合。而这些向量构成了闭回路。TOC\o"1-5"\h\z.如果线性规划问题无最优解，贝!1它的对偶问题也一定没有最优解。（ ）【答案】V【解析】它的对偶问题可能无解，也可能有无界解。3.已知神为线性规划问题的对偶问题的最优解•若y/>0,则说明在最优生产计划中第i种资源己经完全耗尽。（ ）【答案】V【解析】对偶问题互补松弛性质中才內d：W>。时，有£。內=如表明在最优生产计划加 万1中第j种资源已经完全耗尽。4.用动态规划方法求最优解时，都是在行进方向规定后・均要顺着这个规定的行进方向，逐段找出最优途径。（ ）【答案】V［解析】用递推法求解动态规划问题，首先将过程分成几个相互联系的阶段，选取状态变量和决策变量并定义最优值函数，然后写出基本的递推关系式?口基本方程。其行进方向的规定，即选择用逆推法还是JI厕®去。因为动态规划的状态具有无后效性，所以必须按规定的行进方向逐段找出最优途径。5.如果线性规划问题有最优解，则它对偶问题也一定有最优解。（ ）【答案】V【解析】由对偶定理知’原命题为真’且线性规划问题与它的对偶问题的最优值相等。二、 计算题

6.对表所示的运输问题(表内的数字表示单位货物从供应地i运到需求地j的运价，表右面和下面的数字分别表示供应量和需求量X(I)用西北角法计算初始耕岀可行解；(2)从这个基础可行解出发，求出这个问题的最优解；表jZTrnj91-isjZZ1jZTrnj91-isjZZ1--sJ.工|7T110152031【答案】(1)地1234产段11515302531945350504252515203i84150(2)用位势法计算初始可行解的检验数为：表地1234U|11011-697150221312169I3-111-58-1071024-114-313-812135V10II158用闭回路法对上述初始解进行改进，得到表yi234产量1151530254045331195042525销位势法计算可行解的检验数为:

用闭回路法对上述解进行改进，得到表\锵地1234产量1151530245453531145042525销位势法计算可行解的检验数为:用闭回路法对上述解进行改进，得到产1234产量115153()2454532016145042525销位势法计算可行解的检验数为：表产航、＞\1234Ui1101II93150261351210169-333118710-24314213212131V)1010912上述得到的解中所有非基变量的检验数均不为负数，故得到最优解，见上表。7.某建筑公司最近几年的发展重点是承接中东等地区的建筑项目。公司需要一种大型的建筑设备’该设备今后4年的购买价格(预测值)分别为(5.0,5.3,5.7,6.0)(万元)(产品购买价+运输到工地的费用］L如该设备连续使用，其第i年的使用费及维修费分别为(1，1.7,2,5.3.3)(万元>由于路途遥远•淘汰后的设备就在当地折价处理了,使用满i年的设备处理价格为(33.2.5,1.5,0.8)(万元).公司在制定一个4年的设备购买计划，你有什么建议？(限用图论理论.写出算法，计算过程，最终结论,最佳总费用)【答案】可以把这个问题转化为最短路问题，根据题意绘制如下赋权有向图。图采用Dijksra算法计算图1中的最短路为：(I)对起点1进行P标号’即P(I)=0；对其余点进行T标号，alHJ)=+<X)(J=2.3，•…5)0检查点1，进行T标号：r(2)=2.7;T⑶=5.2;7\4)=8.7;T(5)=12.7点2获得P标号，.且P(2)=2.7检查点2,修改T标号：r(4)=8.2；r(5)=11.7。点3获得P标号，旦P(3)=5.2检查点3,修改T标号：7(5)=11.1,点4获得P标号，且P(4)=8.2检查点4,无需修改T标号。(5)点5获得P标号，)且P(5)=11.1,求解结束。上图中的最短路为1—3->5。即第一年初购进一台设备,第三年初淘汰掉并购置新设备，直至第四年末淘汰掉。最佳总费用II-1万元。8.一个办事员核对登记的申请书时，必须依次检查8张表格，核对每份申请书需1min。顾客到达率为每小时6人，服务时间和到达间隔均为负指数分布.试求：(I)办事员空闲的概率；(2)匚七,叱,吧。［答案］因为该办事员核对登记的申请书时，必须依次检查8张表格，且核对每张表格花费的服务时间服从负指数分布,则总的服务月眦Ek分布，此排队系统为M/EV1排队系统。&=8,〃=60人/h,=6人/h，P=十=£=佥(I)办事员空闲的概率为："o=l_p=l_&=O・9

（2）L=p+以-W（2）L=p+以-W2虹l_p）L8+E（*）' -・1017160=0.105. irn=0.00532X8（f）麗。,3+W_（8+l）X（£）. irn=0.00532X8（f）麗。“2奴l_p）W,=3=Vh=0.0025h叭=牛=快里h=0.0009hA 0.建立数学模型一家汽车制造商有5家过时的工厂’管理层考虑更新这些工厂以生产一种新型轿车的发动机组、变速器和一种主要配件A。更新每个工厂的成本和更新后的生产能力如表所示:表工厂成本（万元）发动机组（万个）变速器（万个）配件A（万个）1250503070235080 ・40903370408010044009060905240403050工厂可用于更新的资金为1300万元,工厂3和工厂4位于同一地区，最多只能更新一个工厂,此夕卜工厂I与工厂5具有相关性，工厂5所需要的某些零件必须由工厂1生产。现计划需要180万个发动机、150万个变速器及200万个配件A,管理层应决定更新哪些工F以达到计划生产需要，并使总成本最小。试建立该问题的数学模型。［答案］设Xi=l表示更新工厂i,Xj=0表示不更新工厂i。根据题意，可建立如下数学模型:minz=250x,+350x2+370x3+400x4+240x5250x,+350旦+370賜+400心+240賜<1300x3+x4<1X\—SJ.<50可+80x2+40x3+90x4+40a5>180SJ.<30、+40x2+80%+60x4+30x5>15070%!+90x2+100x3+90x4+50x5>200x.=0,1;/=1,2,3,4.5.解下列0-1规划问题。（I）minz=4.V,+3x,+2x32x,-5x2+3x3<4.VJ.4.r,+x2+3a:,>3.VJ.x2+Xj>1X|.x2.x3=0或1(2)minc=2.r,+5x2+3.%+4x4-4x)+x2+x3+x4>0-2%+4a\+2xy+4.r424A,+x2-Xj+x421xpx2,x3,x4=0或1【答案】(1)通过观察可知(o,o,1)「为可行解’相应的z=2,故增加约束条件4a;+3x2+2x,<2◎进行枚举及选择，如表所示。表点、条 作H标值rOCD(0.0.1)v/*✓5/2(0.1.U)X(0.1.1)X(1.0.0)X<1.0.0X<1.1.0)Xci.1.1)X(0.0,0)>/X由表可判定，最优解为x'=(0,0,1)。3=2(2)通过观察可知(0,0,0,1)丁为可行解，相应的z=4,故增加约束条件,2玉+5x2+3.q+4.v4<4 ◎进行枚举及选择，如表所示。■C.ri,力i•瑜}： j巻、&二件<o»Q,a«xi:x.'x/'..4：T^v-■XCOHE..X-一:X：(C.1.4.釦!?•-•.,tou4.*i.X...一•—厂 一-~•幻^<?,€•-；..>''ci.i,>.o>',,}"一"I由表可判定最优解为X•=(0,0.0,1)「・f=4.用图解法找出以下目标规划问题的满意解。⑴minz=x,-10x,+<-d；=503多+5心+d；一d；=20'〔8叫+6.弓+/-d；=100.rt.x2,d(・d；^O.i=1.2.3(2)minm=a(d；+d：)+p.d+p3d:+p4(£+1.5/)-v,+x2+d「—d：=40為+JC,+d；-d；=100aJ.j：, +d；_d；=30x2-J/=15xl,x2,dl.d,'>()./=1.2.3,4(3)minz=A(4+d；p2d2+p遥'j,+x2+或_d；=103玉+4x2+d；_d；=50'.8叫+10旦+打_"；=300§,.弓0 20J=1,2.3【答案】(1)令各偏差变量为0,作岀所有的约束直线，并标示出各偏差量增加对约束直线的影响，如图所示。图从图中可以看到，在考虑具有“的目标实现后，Xi,X2的取值在直线土-l().q=5()及电20上;考虑P2的目标要求实现时，因为+的权系数大于过的权系数，故考虑mindd2+,所以点A为满意解，其坐标为(50,0),即满意解是(50,0)\(2)令各偏差变量为0,作岀所有的约束直线，并标示出各偏差量增加对约束直线的影响，如图所示。图从图中可以看到’在考虑具有pi的目标实现后,"X2的取值范围为OADFO;考虑P2的目标要求实现后’xi，X?的取值范围为OABEFO;考虑P3的目标要求实现后，阳，X2的取值范围为BE;考虑囚的目标要求实现时，因为山一不的权系数大于d3一的权系数，故考虑mind/,所以点E为满意解’其坐标为(25,15),即满意解是(25,15)\(3)令各偏差变量为0,作岀所有的约束直线，并标示岀各偏差量增加对约束直线的影响，如图所示。图从图中可以看到，在考虑具有Pl的目标实现后，"X2的取值范围为直线AB；考虑P2的目标要求实现时，要实现mindn从图中可以看出，只有B点可使d?最小，所以B点为满足目标规划问题的满意解，其坐标为(10,0)，即满意解是(10,0)\

12.某省农业主管部门为了满足本省对某种农副产品的需求，决定建立生产基地，初步有四个地点A】、A,A3、A,可供选择，他们的产量分别是"恥a*a4.它们的建设费用分别为dC2、C3、％有五个地点Bi、B2%BkB4%B5需要这种农副产品，它们的需求量分别为也、b2.b"%、b5.从产地八需求地马的单位运费为Cij。(1)试决定选择建场的基地与各生产基地到各需求地的运量，使得既满足各地的需求又使得建设和运输的总费用最小，这里假定如>i>,••I >1(2)若在(1)的基础上要求A和A?不能同时入选为生产基地，1、侃、Z、人中至少有两个入选，且若么I被选中则A4也一定要入选，则相应的数学模型又是什么？【答案】(1)设句=<【答案】(1)设句=<1 选择第代个地点建生产基地yij为第人个基地运送到马个地点的运量4二号minz=Yx'ci+£耳匂•为°l<-<-灰.>-fs;1/I5Erl4z:£;E:Er=l4z-«-l°l<-<-灰.>-fs;1/I5Erl4z:£;E:Er=l4z-«-l>-x-1如~>-2yr如>-y/4O>-为(2)设耳=]何不选择第A.个地点建生产基地

选择第(2)设耳=]4 1=4^3minz二〉＞£"EWiej=i0<-yu5Z/=I2<-0<-yu5Z/=I2<-奶<-<->->-改^/J/1X2hs£-:z-iu4l.:£z-iz〔>-43>-X-4>-15x（+x2<1.vl+x2+x3+x4>2土二0或]为"13.某厂每年需要某种元件5000个,每次订购费C3=50元,保管费每件每年0=1元,不允许缺货’元件单价k随采购数量的不同而变化’问公司每次应该订购多少？总的采购成本是多少？[2.0元，QV1500"）=7一]1.9兀，2>1500【答案】利用E.O.Q公式计算分别计算每次订购707个和1500个元件，平均单位元件所需费用：C（707）=lx1x^51+—+2.0^2.1414（元/个）' 72 5000707C（1500）=-xlx—+—+1.9^2.0833（元/个）2 50001500因为C（1500）<C（707），所以，最佳订购量为1500。一年内总的采购成本为1500x2.1414=3212.1元。2017年河北工业大学土木工程学院863运筹学(I)［专业硕士］考研题库(五)说明：①本资料为VIP包过学员内部使用资料。涵盖了历年考研常考题型和重点题型。一、 判断题•运输问题是一种特殊的线性规划模型，因而其求解结果也可能出现四种情况之_：有惟一Bffi解，有无穷多最优解・无界解，无可行解。( )【答案】X【解析】运输问题是一种特殊的线性规划模型’它总存在可行解,或是存在惟一最优解，或是有无穷ft｛尤解。.利用破圈法求赋权图的最小支撑树时，每次都是任取一个圈并去掉其中权最小的边，直到该TOC\o"1-5"\h\z赋权图不再含圈时，便得到最小支撑树。( )【答案】x［解析］利用破圈法求最小支撑树时，每次任取一个圈，去掉圈中权最大的边。.对自由变量Xk，通常令！=xA其中xk>0.xk>0在用单纯型法求得的最优解中不可能同时出现x>0.x；>0o( )【答案】V【解析】因为払=•.-•«,所以知虹'不能同时为基变量，则至少有一个为0。故最优解中不可能同时出现%>0，x；>0。.任一图G=(V,E)都存在支撑子图和支撑树。( )【答案】x【解析】当图中存在一个顶点，其次为。时’则该图不存在湖树。若线性规划问题的可行解为最优解’则该可行解必定是基可行解。( )【答案】x［解析］基解且可行才倒能璧优解。二、 计算题某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如表所示。设司机和乘务人员分别在各时间区段一开始时上班’并连续工作8h,问该公交线路至少需配备多少名司机和乘务人员。列出这个问题的线性规划模型。聲修韻囲顆浪丄用5¥《刼争困冷坦*t/OI=（切0=｛（。）。，（£）9化）0，（【）"u叫实留Mt(.2)3(3)3Mt(.2)3(3)3-<1)3-（b'£'乙（b'£'乙’l=!）’V孝草垓冴:刼噩明区m'却弟逐翘实d，却車喜臨孩混区1印【孝另】（空旦）砲'峯（空旦）砲'峯。生详4,现累翊王囹。峑世喜職象混毋推蠶目姓三善9殖冴G63罠’亦手&一碑柬。-L0V".・・・"x()£5+*0乙W&+*OS<^+顷rs09衣+*0Z.^:r+'r09<政+丫9r+?x+*x+zx+he=2uiiu:实瓶誕凉不鬟回m'瀚y関曽岩mm/怛囲sn刼ifMBS!齢y区（9，…z，【=!）成溟【孝易】0£00:9—00'290ZOO*2—OO'ZZc^0G(XPZ”-00*81I-09OO*R1--00*H£0ZOO*VI—OO'OlZ0900101--00,9IY/XfY骅的nvXi iff

8.给出如下线性规划问题的最优单纯型表如表所示，其中$、S2分别为两个约束条件的松弛变量maxZ=6xi+2x2+12xj4-r, +3x3<242%|+6x2+3x3<30[ME%2°表cl6 212oOc«Xa—bX,X?x?S,s.12Xj84/31/3I1/3o0S,6-250-11-96-10-2o-4o要求：(1)求出使最优基不变的也的变化范围;(2)求出使最优解不变的C2的变化范围；(3)在原线性规划的约束条件上，增加约束条件:xi+2xi+2X3^12,其最优解是否变化?如变化，试求岀最优解。【答案】(1)假设加变化后的最优解为Xb,只要XrNO,因最终表中检验数不变’故最优基不变，但最优解的值发生了变化。设b2变化了入，贝！| =所以当b>o时问题最优基不变’解得入20故b2N30(2)由题意知C2-420得C2*(3)约束条件可变为x1+2x2+2x3+S3=I2列出单纯形表cBXb-b621200012x384/31/311/30120s26-250-110012122001-10-20-40-1012X.84/31/311/30120S26-250-1100-4-5/34/30-21301-10-20-40-1()12Xj24/507/51-1/504/50S36/5017/50-1/51-6/56XI12/51-4/502/50-3/50-10000-48/5最优解(12/5,0,24/5)

9.设有三个电视机厂生产同一种彩色电视机，日生产能力分别是50,60.50(台)，供应三个门市部，日销售量分别是60,40.60(台)•从各分厂运往个门市部的单位运费如表所示，试安排一个运费最低的运输计划。若工厂1到门市部I的运价由9减为6,试寻求最优运输计划。表门市部1门市部2门市部3产量工厂1912950工厂273760工厂365950需求童604060【答案】(I)此问题是运输平衡问题。第一步，用伏格尔法寻找得到初始基可行答:表门市1门市2门市3产量工厂15050工厂210401060工厂35050需求量604060160第二步，用位势法计算各空格处的检验数为:从所有非基变量的检验数可以看出都是非负数，其中存在f0的检验数，说明该题有多重最优解。(2)若工厂1到门市部1的运价由9减到6时，代入计算得第一步，用伏格尔法寻找得到初始基可行表门市1门市2门市3产量工厂15050工厂2402060工厂3104050需求敏60406()16()第二步，用位势法计算各空格处的检验数为:

从所有非基变量的检验数可以看出都是非负数，其中存在两个0的检验数，说明该题有多重最优解。10.有一运输问题’它有3个重载点和2个车场’其运输表如表所示。表中小方框内的数字为两点间的车辆空驶距离•L2和3三项运输业务的重载里程（己将装卸车时间折算在内）分别为7,8和9,其他有关情况如表中所示。此外，要求车辆的每条行车路线总长度（包括重驶、空驶及装卸车所用时间的折算长度）L在45~60之间。试用本章给出的车辆优化调度启发式算法，求出其满意的可接受可行解，并据此«出行车路线。发空堂、、敝裁点车场发车数12345重点111F—K109■"EItTc63FLi11nsH7车场4FH|M<45T3~E<6收1E敦106<8W7【答案】（1）首先只考虑重载点的情况’利用伏格尔法进行求解，并且用位势法进行检验,得到只考虑重载点的最优解为器=10..*=6..輩=6忑）=1逑=*；」湾=专二階=0(2)解的扩展支艾一4。"=4.瓦■=务一=6—0=6b\=b\ ;80«8.65=b\— =7—0=7=min(c,h-0}?min，,丨占；>0}—=rnin(6・14)+min(8.10}—4=6+8・4=10.6=41/=4dji=min'、<h.-0♦nun,b\>0}—c:l=min(6.8}+niin{6t10}—80itrnm(Ci,I>0)r0itrnm(Ci,I>0)ry-~min{4*2}Imini14»2>—44C«<1=2+2-4 ... _8”™mm<c.b.>0*jnm(ch|6；>0}=min(6»8}+min(14f2)—€按照^由小到大顺序对进行调整Ijx'<；—min<工；？，屋,及}=6—min(6・6,7}=0«/："+min(jr；；',S-，及}=0+min(6,6,7}=6■ x,-'+nun(zt；,$，片;)=0+min(6,6,7}=66-=0；—£了"=&—x5s*=7—6=1MH=1,；min()0；)=1—min(1,4.1}=0•r； 瓦0；}=O+min(l・4,l}=l■x.-C：+min〈a；.B；}=6+jnin(l,4,l)=7h=b,—£]：；'=板一勇;’=4—1=3rZi=工；：—miNz；；',万：)=6—min{6,3,8}=3"=*；十0)=l+min(6,3,8}=4z.=无； )=0+min{6・3.8}=3&=M—支h：：‘=如一乂；>=4—4=0方；=0；_X-*D；—£?=•8—3—5> .7J—mini.*'.Z»<.64}=10—mini10.0,5}=10:.r,-i：?4niinlx；；1,b,，方：>=04-min(10,0,5}=0•1rii*imini*'・R0：)i()+min(10,0,5)=0(3)解的收缩因为S史式」工:？+ =4+6=10<4+6=10l|Atj5方■"xf"+■ ==3+7=]。<4