四川大学2015-2016学年第二学期课程考试试卷答案(A卷)课程名称

1、试卷答案第1页（共 55 页）四川大学2015-2016学年第二学期课程考试试卷答案（A卷）课程名称：运筹学考试时间：120 分钟 年级：xxx 级专业： xxx题目部分，（卷面共有 56 题，0 分，各大题标有题量和总分）一、判断（38 小题，共 0 分）1、单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；（）答案：对2、 线性规划问题的最优解一定在可行域的顶点达到。（）答案：错3、线性规划模型中增加一个约束条件，可行域的范围一般将缩小；减少一个约束条件，可行域的范围一般将扩大。（）答案：对4、 用单纯形法求解标准形式（求最小值）的线性规划问题时，与二

2、j0对应的变量都可以被选作换入变量。（）答案：对5、 线性规划问题的可行解如为最优解，则该可行解一定是基可行解；（）答案：错6、 线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；（）答案：对7、 对取值无约束的变量xj，通常令xj二Xj- xj，其中Xj_0,x；_ 0,在用单纯形法求得的最优解中有可能同时出现xj_0,Xj_0；（）答案：错8、 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。（）答案：对9、 在线性规划问题的最优解中，如某一变量Xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数Cj或在各约束中的相应系数ajj,反映到最终单纯形表中，除该列

3、数字有变化外，将不会引起其他列数字的变化（）答案：对试卷答案第2页（共 55 页）10、 对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cr?个；（）答案：错11、 单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。（）答案：对12、对偶问题的对偶问题一定是原问题（ ）答案：对1 2 1 213、 若X,X分别是某一线性规划问题的最优解，则X =2X也是该线性规划问题的最优解，其中为正的实数；（）答案：错14、 线性规划的可行解集是凸集。（）答案：对15、 线性规划问题的每一个基解对应可行域的一个顶点；（）答案：错16、 用单

4、纯形法求解标准型式的线性规划问题时，与二j0对应的变量都可以被选作换入变量；（）答案：对17、 线性规划用两阶段法求解时，第一阶段的目标函数通常写为min zxai（xai为人i工变量），但也可写为min z八kxai。只要所有匕均为大于零的常数；（）i答案：对18、若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解（）答案：对19、 单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解；（ ）答案：错20、 根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解（）答案：错21、 如线性规划问题存在最优解

5、，则最优解一定对应可行域边界上的一个点；（）答案：对试卷答案第3页（共 55 页）22、 若线性规划间题中的bj,Cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况（）答案：错23、 已知 才为线性规划的对偶问题的最优解，若y=0,说明在最优生产计划中第i 种资源一定有剩余（）答案：错24、 已知y为线性规划的对偶问题的最优解，若yr0，说明在最优生产计划中第i 种资源已完全耗尽（）答案：对25、一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；（）答案：对26、 单纯形法计算中，选取最大正检验数。二k对应的变

6、量Xk作为换入变量，可使目标函数值得到最快的减少。（）答案：错27、 线性规划问题的每一个基本解对应可行域的一个顶点。（）答案：错28、 若某种资源的影子价格等于k，在其他条件不变的情况下，当该种资源增加5 个单位时，相应的目标函数值将增大5k（）答案：错29、一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。（）答案：对30、线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优。（）答案：对31、若线性规划问题具有可行解、且其可行域有界，则该线性规划问题最多具有有限个数的最优解；（）答案：错32

7、、线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；（）答案：对试卷答案第4页（共 55 页）33、 应用对偶单纯形法计算时，若单纯形表中某一基变量Xi 0又Xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解（）答案：对34、 设？j,?分别为标准形式的原问题与对偶问题的可行解，xj, yi分别为其最优解，则恒 有E Cj?兰无CjX=E byz bi?j 4j 4i 4i 4答案：对35、 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；（）答案：对36、 任何线性规划问题存在并具有惟一的对偶问题（）答案：对37

8、、 如果一个线性规划问题有可行解，那么它必有最优解。（）答案：错38、 单纯形法计算中，选取最大正检验数二k对应的变量Xk作为换入变量，将使目标函数值得到最快的增长；（）答案：错二、填空（6 小题，共 0 分）1、 求目标最大的 LP 中，有无穷最优解的条件是 _ 。答案：判别式j中至少有一个为零。2、 线性规划的所有可行解构成的集合为 _ 集合，也可能为 _集合；它有有限个顶点，每个顶点对应于线性规划问题的 _ ;若它有最优解，则必在集合的_上达到。答案：凸集；无界域；基可行解；某个顶点。3、 LP 的基本可行解与基本解的区别是 _。答案：基本可行解的分量大于或等于0。3x2- 4,lx-!

9、- 3x2x3= 4,4、 如果把约束方程i标准化为彳，则为是_ 变量,2论+ 5x2兰52% + 5x2 x4+ x5= 5x?是_ 变量，x3是_变量， 疋 是_ 变量， 疋 是_ 变量。答案：决策；决策；松弛；剩余；人工。5、 对于平面中的某 LP 的约束集合（见下图），其可行解为 _ ;基本解为 _；基本可行解为_ 。试卷答案第5页（共 55 页）答案：OGEDH 所围阴影区；所有直线及坐标轴的交点；0, G, E, D , H 五个点。答案：都有一组决策变量，X =（Xi,X2,，Xn）T，其值代表某一个具体方案，一般为非负且连续；都有一组约束条件，这些约束条件可以用一组线性等式或线

10、性不等式来表示； 都有一个要求达到的目标，它可用决策变量及其价值系数构成的线性函数（简称目标函 数）来表示，且根据不同问题，可要求其实现最大化或最小化。三、问答（3 小题，共 0 分）1、在单纯形法迭代中，任何出基的变量在紧接着的下一次迭代中会不会立即再入基。 答案：不会2、会不会发生在一次迭代中刚进入基变量的变量在紧接着的下一次迭代中立即被替换出 来？什么情况下有这种可能，试举例说明。答案：若变量Xk和Xk的检验数均大于零，当选入基变量时，主元素分别为aik和aik.若有C日若选了X1为进入基的变量，则有可能在紧接着的下一次迭代中被替换出来3、在单纯形法迭代中，任何从基变量中替换出来的变量在

11、紧接着的下一次迭代中会不会 立即再进入基变量，为什么？答案：不可能，因刚从基中被替换出来的变量在下一个单纯形表中，其检验数一定为负四、证明（9 小题，共 0 分）1、若线性规划问题min z =CX，约束于AX二b，X一0，具有最优解，试应用对偶性质 证明下述线性问题不可能具有无界解，min z=CX，约束于AX二d, X一0,d是可以取任意值的向量。答案：分别写出两个问题的对偶问题见Li和L2: max =YbL2:max = Yd6、线性规划数学模型具有_ _等三个共同特征。试卷答案第 6 页(共 55 页)YA _CSt.Y _0YA_CSt.Y _0显然L1的最优解是L2的可行解，由此

12、L2的原问题具有下界。2、线性规划问题maxz二CX,AX二b,X_0,设X为问题的最优解，若目标函数中用C*代替 C 后，问题的最优解变为X*，求证：(C*-C)(X*- X ) _0答案：CX_CX.C(X X ) 0( 1)又C X _ C X有C (X -X )0(2)(2)-( 1)得(C C)(X -X ) _03、已知线性规划的原问题与对偶问题分别为：(P)原问题：maxz=CX (D)对偶问题：min二Ybst *bX - 0st. YAM丫- 0若Y”为对偶问题最优解，又原问题约束条件右端项用b替换之后其最优解为X，试证明有CX Y b。答案：P : maxz =CZD :

13、max =YbIAZ汀st.Z - 0YA岂C st.丫_0设D的最优解为丫，因有CZ =Yb，有Y”是D的可行解，故有YY b，由此CZ Y b。4、已知线性规划问题:max z =3为2x2试卷答案第7页（共 55 页）-x- +2x243为+2x2兰14st彳X- x?兰3Xr,X2王0要求：（b）应用对偶理论证明原问题和对偶问题都存在最优解。答案：（b）容易看出原问题和其对偶问题均存在可行解，据对偶理论，两者均存在最优解5、已知线性规划问题：maxz =% x2I -x-ix2x3_ 2st. 2捲+ x2- x3兰1x-,x2，x0试应用对偶理论证明上述线性规划问题无最优解。答案：该

14、问题存在可行解，如X =（0,0,0）;又上述问题的对偶问题为：min - 2y-屮yi一2%王14% + yist.y- y0y0由第一个约束条件知对偶问题无可行解，由此可知其原问题无最优解。6、已知线性规划问题：maxz =4咅7%2%x-i2X2x3虫0st. 2xi3x23x2二10.xi, x2, x-0应用对偶理论证明该问题最优解的目标函数值不大于25。答案：写出其对偶问题，容易看出Y =（1,1.5）是一个可行解，代入目标函数得 =25。试卷答案第 6 页(共 55 页)因有maxz _，故原问题最优解不超过 25。7、证明当用对偶单纯形法求解线性规划问题时，若有则该对偶问题具有

15、无界解。br:0，而aj-0 (j =1/ ,n)，试卷答案第9页（共 55 页）答案：设为迭代前对偶问题的目标函数值，用Xk替换Xr后，新解的目标函数值为有 -也- v（-br）日=li n ! _ aj0【j arjJ因arj- 0,故 v 可任意增大不受限制，又（-br） 0，故可无限制减小。8、已知线性规划问题：maxz二x2x3Xi-X3_4st.为x22x3_3Xi,X2,X30应用对偶理论证明上述线性规划问题无最优解。答案：该问题存在可行解，如X =（4,0,0），写出其对偶问题，容易判断无可行解，由此原问题无最优解。9、已知线性规划问题：nmaxz二、CjXjj壬n aXj-b

16、i（i “ ,m）stj壬0 （j =1,，n）若（y：y2,y；）为其对偶问题的最优解。又若原问题约束条件的右端项b变换为$，这nm CjXjbyj =1i =1答案：原问题右端项变为b后，其对偶问题为:mmin z =、biyii =1m时原问题的最优解变为（X；，乂），试证试卷答案第10页（共 55 页） aj%一（j=1/,n）st. yyi-0（i=1, ,m）由于约束条件不变，（y,，ym）必为上述问题的可行解。根据对偶理论有:nmCjXjbj 4i 4五、计算解答（50 小题，共 0 分）1、分析下列参数规划问题中当二变化时最优解的变化情况:（a）maxz（巧=（3 2巧Xi（5

17、-巧X2（二_0）Xi42X20 (j=1,，4)(c)maxz(J) =45咅80X2( -:v :-:5x120 x2_ 400二st. 10 x115x1450 5二iX1,X2X0(d)min z = 2% 8x5x-i+3& - x5=3_Ex2_4&+2x5=1+2日X3 - & +3x5 = -1+0、Xj 0 (j =1,，5)试卷答案第11页(共 55 页)答案：(a)0_二_9/7时，捲=2公2=69 / 7_ r _时，为=4公2=3v _5时,为=4,冷=01(b)才访时，Xi皿 “i1时，x = 2,x2= 1, x3= 0, x4- , z

18、= 3二-1时，x= 0, x2= 2, x3= 0, & = 1, z =2 2(c)r : 90 ,无可行解二600 1 80、-90必=0,X2=30,r -2400 -1723600350173“=24,x2=14 ,z =2200 2=80 x2=0,z = 3600 9352(d)J : 0 时，无可行解0 _71_ 1丙=271,x2= 5 271, x3= 0,x4=1 - 6X5 = 0,z =22711乞二空3必=3 X2=1 2X3 =1匕疋=0必=0,z =03一4,為=0,x2=7,x3=8 -2二x4=0必=-3 z二-24 8，-

19、4时，无可行解2、某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100 人，每月白坯纸供应量为 30 000 kg.已知工人的劳动生产率为：每人每月可生产原稿纸130 捆，或生产日记本 30 打，或练习本 30 箱。已知原材料消耗为：每捆原稿纸用白坯纸3-kg,312每打日记本用白坯纸13kg，每箱练习本用白坯纸26kg.又知每生产一捆原稿纸可获利233元，生产一打日记本获利3 元，生产一箱练习本获利 1 元。试确定：(a) 现有生产条件下获利最大的方案；(b) 如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40 元，则该厂要不要招收临

20、时工，招多少临时工最合适？答案：(a)分别用x1, x2,x3代表原稿纸、日记本和练习本的每月生产量。建立线性规划模试卷答案第12页(共 55 页)型并求解得最终单纯形表如表所示。试卷答案第13页(共 55 页)xX2x3x4xx22000017/31/10-10 x1100010-4/3-1/1040c zJj厶j00-10/3-1/10-50(b)临时工影子价格高于市场价格，故应招收。用参数规划计算确定招200 人为最适宜。3、下述线性规划问题：maxz = -x118x2c3x3c4x4x12x23x34x4_15st. * 3论+4x25x36x4兰5 + &、Xj3 0 (j

21、 =1,4)要求：以x1、x?为基变量，列出单纯形表(当 =0时)；(b) 若x1、x为最优基，确定问题最优解不变时，Cs、c4的变化范围；(c) 保持最优基不变时的的变化范围；(d)增加一个新变量，其系数为(Ck,2,3)T，求问题最优解不变时Ck的取值范围。答案：(a)表X1X2x3x4Xs1Xs2x151011/514/52/5-1/5x25012/53/53/101/10Cj-Zj00C3- 5C4- 8-5-2(b)G - 5,C4-8(c)-50 -，-2551试卷答案第14页(共 55 页)(d)q一(2,3)匚兰二q兰164、下表为用单纯形法计算时某一步的表格。已知该线性规划的

22、目标函数为max5x13x2，约束形式为_,x3、人为松弛变量，表中解代入目标函数后得z= 10。表X1X2X3X4X32C011/5X1adE01Cj-Zjb-1fg求a g的值；(b)表中给出的解是否为最优解。答案：a = 2,b = 0,c = 0, d =1,=4/ 5, f = 0, g - -5;表中给出的解为最优解。5、试将下述问题改写成线性规划问题：mmmmaxmin(送a/,迟ai2Xi,正ainXi)Xi丑i：!i =1% X2Xm =1St.Xi-0,i =1, ,mmmm答案：令：-mi n(ai1xiai2x2，ainxn)则问题可化为maxz=：i吕i i =1M瓦

23、ajX Zu (j =1 ,n)I =1mst.：xi= 1i =1Xi0(i =1,，m)6、 求出以下不等式组所定义的多面体的所有基本解和基本可行解(极点)2X13X23X3岂6试卷答案第15页(共 55 页)(1)-2x1+3X2+4X3兰12凶，X2,X3色0试卷答案第16页（共 55 页）x12x23x3=18-2x+3X212Xi,X2,X3Z02x1+ 3x2+3X3+= 6n *2论+3x2+4X3+ X5=12A = (R P2P3巳*2 3 3 1 0、12 3 4 0 1?Xi,X2,X3一001,X2,X3,X4,X_0（23、E=(PB)= l c1-2321、B3N

24、PR)= 0203、B5NP20430B7=(F2斫oq 0)B10=(P4引“，X3=x“0得纠36=X1一3/2I 2x12x2= 12lx2= 3即(-3/2 3 0 0 0fo同理，对应B2的基本解为（-7/6 0 18/7 0对应IB3的基本解为(-6018 00)T。对应B4的基本解为(300 018）T同时又为基本可行解对应B5的基本解为(0-46 00)-0)To答案：（1）2x13X23X3_ 6“ 一2捲+3x2+4X3兰12试卷答案第17页（共 55 页）试卷答案第18页（共 55 页）对应B6的基本解为(040 -60)T对应B7的基本解为(020 06)T同时又为基本

25、可行解对应B7的基本解为(020 06f同时又为基本可行解对应B8的基本解为(003-30J对应B9的基本解为(002 04)T同时又为基本可行解对应B10的基本解为(000612)T同时又为基本可行解x12x23x3=18(2)2X13X2乞12IX1,X2,X3 0 x12x23x3x4=18-2x13x2xs=12X1,X2, x3,X4, xs 0 x-i2x2=18-0得I 2x13x2=12A=(RP2P3P4P5)=BARP2) =23B2= (RP3)二3 B3=(PRDB4=(PP5)二B5R)B6 =(巳Rs)B8=(RR)二3001B9=(R4Rs)f1Si Ciai。1

26、6 月的各个月内该厂正常生产工时及最大允许加班工时数如表月份123456正常生产工时/h120001100013000135001350014000最大允许加班工时/h300025003300350035003800但加班时间内生产的每件产品成本增加CCi元，因生产准备及交货要求， 其中产品 1 最早安排从 3 月份开始生产，产品 3 需在 4 月底前交货，产品 4 最早可于 2 月份起生产，并于5 月底前全部交货。若产品 3 和 4 延期交货，于 6 月底前每拖一个月分别罚款P3和P4元,全部产品必须于 6 月底前交货。请为该厂设计一个保证完成合同又使盈利为最大的生产计 划安排，并建立数学模

27、型。答案：设x为i种产品在j月正常生产时间内产量Xj为i种产品在j月加班时间内生产量j -1/ ,6其数学模型为：56maxz (Sj-cJXjj(q -q -cXj-p3(X35X35) -2p3(x36X36)-p4(X46X46)i i j =17、旭日公司签订了5 种产品（i =1,5）下一年度 16 月份的交货合同、已知这5 种产品试卷答案第20页(共 55 页)min z =2x -x22x3-x X2X3=4st. 0 （j =1,，5）当t1珂2 =0时求解得最终单纯形表见表X1X2X3X4X5X35/201/211/20X15/21-1/20-1/61/3Cj-召0-40-4

28、-2（a）确疋c1,c2,c3, an ,a12,a13,a22,a23和Db的值;(b)当t2=0时，t1在什么范围内变化上述最优解不变;(c)当t1=0时，t2在什么范围内变化上述最优基不变;答案：（a）G=6,Q= -2,Q= 10, aii= 0,a）2= 1, ai3= 2,a2i= 3,a22= -1, a23 =1b| = 5,b2=10试卷答案第22页(共 55 页)(b)-6乞,8(c)-5/ 3空t2空1511、已知某实际问题的线性规划模型为：nmaxz = CjXjj壬n ajXj=bi(i=1/, m)st.j吕Xj0(j =1,n)若第 i 项资源的影子价格为 y，n

29、(a) 若第一个约束条件两端乘以2，变为瓦(2耳)为=2b,刃，是对应这个新约束条件的影j二子价格，求、，与y1的关系；(b) 令x3x1，用(x；/3)替换模型中所有的x1，问影子价格yi是否变化？若x1不可能在最优基中出现，问x；有否可能在最优基中出现；n(c) 如目标函数变为maxz - a 2qXj，问影子价格有何改变？j#1答案：(a) ?1二亍；)影子价格也增大两倍。12、考虑线性规划问题：maxz =2% 4x23x33论+4x2+2x3兰602为 +x2+2x3兰40st彳为+3x2+2x3兰80I Xi, X2,X3X0(a) 写出其对偶问题：(b) 用单纯形法求解原问题，列

30、出每步迭代计算得到的原问题的解与互补的对偶问题的解；试卷答案第23页(共 55 页)(c) 用对偶单纯形法求解其对偶问题， 并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；(d)比较(b)( c)计算结果。答案：(a)其对偶问题为min z =60%40y280y33yi+2y y24% + y3y4st. *2yH2yF2y3、, y2, y0(b)用单纯形法求解原冋题时每步迭代结果：原问题解互补的对偶问题解第一步(0, 0, 0, 60, 40, 80)(0, 0 , 0 , -2 , -4 , -3)第二步(0, 15, 0, 0, 25, 35)(1, 0 , 0 , 1,

31、 0 , -1)第三步(0, 20/3, 50/3, 0, 0, 80/3)(5/6 , 2/3 , 0 , 11/6 , 0 , 0)(c)用对偶单纯形法求解对偶问题时每步迭代结果:对偶问题解对偶问题互补的对偶问题解第一步(0 , 0 , 0 , -2 , -4 , -3)(0, 0, 0, 60, 40, 80)第二步(1 , 0 , 0 , 1, 0 , -1)(0, 15, 0, 0, 25, 35)第三步(5/6 , 2/3 , 0 , 11/6 , 0 , 0)(0 , 20/3 , 50/3 , 0 , 0 , 80/3)(d)对偶单纯形法实质上是将单纯形法应用于对偶问题的求解，

32、又对偶问题的对偶即原 问题，因此(b)、(c)的计算结果完全相同。13、将下列线性规划问题化为标准型。(1)Max z =3x5x2-4x32x4s.t 2% +6x2x3+3x4兰 18捲一 3x22x3-2x4-13-为4X2- 3X3- 5X4=9Xi, X2,X4 _0试卷答案第24页（共 55 页）Min f = -x5X2-2X3s.t 3x2x2-4x3空 62% -3X2X3_5X x2X3=9Xi _0,X2乞 0Min f = 3x1x24x3, 2x4st2 为 3x2-x3-2& - -513% - 2x22x3- x4一 -72x14x2- 3x32X4二 1

33、 5Xi, X20X4兰 0答案：(1)Maxz=3为5X2-4X32x42为+6x2x3+3x4兰18为 一3x2+2x3 2x4兰13s.t.一为+4x2_3x3_5x4=9,X1, X2,X40引入松弛变量：X5,X6;令X3= x3- x3标准型为：Max z=3x15x2-4x34x32x4，2X|+6x2xf+2X4+X5=18捲3x2+2x32x3 2x4 x6=13 s.t.论4X23X33X35X4=9试卷答案第25页（共 55 页）X2，X3, X3，X4，xs，X6一0Min f - -x5x2-2x33x|+2x2-4x3兰62论3x2+ x3K5s.t.% +x2+x

34、3=90兰0, x2兰0令z = - f，贝V Max z = Xi5X22x3引入松弛变量：X4,Xs；令X2 -X2,X3 =X3-X3标准型为：Maxx15x22X3-2X33x,2X24X34x3x4= 62x,3x2x3_ x3_ x5= 5 S.t.F F 捲_X；+x；_X；=9Xi, X2,X3, X3；X4,X5一0Min f =3 X24x32x42 Xi+3X2X32X4兰一513xi 2x?+2X3 X4王一7 st 2x_j+4x23x3+2x4=15/1, x2Z0,x4兰0令z fMax z -3为-x2-4X3-2X4-2凶-3X2x32X4- 51-3为2屜-

35、2x3x4- 7试卷答案第26页（共 55 页）引入松弛变量：人FFIIX5,X6；令X4 -X4,X3 =X3-X3标准型为：Max z = -3xi-X2-4X34X32x4，-2xi-3x2+x3-x3-2x4-X5=513% +2x22x3+2X3 X4+冷=7 St /2为+4x2-3x3+3x3-2x；=15Xi, x2,x3, x：X4；X5,沧AO14、用单纯形法求解以下线性规划问题。(1)Max z =3 2x2st2为一3x2乞3-x1x2_5X1, X3一0Min z =X2-2x3s.tx 3x24X3=122x2-x3-12X1, X2X3- 0答案：(1)Max z

36、 =3% 2x2Max z = 3x2x22x-i3x2三32论3x2x3=3 一为+ x2兰5 n s.t -为 一3x2+X4= 5內，X2-0X1,X2,X3,X4-0CBXB3200X1X2X3X4e0X339】_3101.50X45_1101一_z03200X11.51-3/21/20s.t试卷答案第27页(共 55 页)x46.50-1/ 21/21一z-4.5013/2-3/20因为a2i与a22都小于 0,所以原问题没有最优解。Maxz = x2-2X3Maxz = x2- 2x3x13x24x3=12x 3x24x3=12st 2x2x3兰12 n s.t 0 (j =1,5

37、)用单纯形法求解得最终单纯形表如表所示。(a)求耳1, a12, a13, a21, a22, a23和, b2；(b)求C|,C2,C3表X1%X3X4X5Cl第 i 纸厂第I型设备每月可用的台时数;试卷答案第29页（共 55 页）X33/21011/2-1/2X221/210-12Cj_zj-3000-4答案：a1=91/ a =217、某厂生产三种产品 1,11 , III。每种产品要经过 A, B 两道工序加工设该厂有两种规格的设备能完成 A 工序，它们以A, A2表示；有三种规格的设备能完成B 工序，它们以Bl, B2,B3表示。产品 I 可在 A, B 任何一种规格设备上加工；产品

38、 II 可在任何规格的 A 设备上加工，但完成 B 工序时，只能在B1设备上加工；产品 III 只能在A与B2设备上加工。已知各种设备的单件工时、原材料费、产品销售价格、各种设备有效使用率（台h）以及满负荷操作时设备的费用如表1 所示要求安排最优的生产计划，使该厂利润最大。设备产品设备有效使用率/（台 h）满负荷时的 设备费用/元IIIIIIA15106 000300A2791210 000321B168114 000250B247 000783B374 000200原料费/（元/件）0.250.350.50单价/（元/件）1.252.002.80答案：对产品 I 而言，用Xi,X2分别表示以

39、A,A完成 A 工序的产品件数，转入 B 工序时， 用X3,X4,X5分别表示以B1,B2, B3完成 B 工序的产品件数。对产品 II 而言，用x6,x7分别表 示以A,A2完成 A 工序的产品件数，转入 B 工序时，用X5+X7表示以B完成 B 工序时的 产品件数。对产品 III 而言，用X表示以A2完成A 工序的产品件数，X8也表示以B2完成B 工序的产品件数。试卷答案第30页（共 55 页）根据题意，有数学模型300max z =(1.20.25)(X!x2) (2 -0.35)(沧-x7) (2.8 -0.5)沧(5论10沧)6000321250 “ c、783一 、200“(7x2

40、9x712x8)(6x38x68x7)(4 X411x8)7x5100004000700040005x1+10 x 60007x2+9x7+12x800Ci/ C2A 3QiG g =3Ql,Q21 G/q c3Q2G/Q=1Q2, Q00=0Q3, Q00-Qi00不限Qi0不限Q400=(j h,n)式中Uj为大于零的常数，对应第（1）（2）组约束条件的对偶变量分别为yi和召，如令Im=Cj为aijyii#则问题的最优性条件等价于Xj=0时，Cj=0试卷答案第 28 页(共 55 页)当0：xj: w时q =0Xj二u时，Cj_ 0答案：写出其对偶问题：mnmin国=送b%+瓦UjZyi

41、4j Am aYi- Zj-Cj(j-1,n)St.i4yi无约束,Zj_0m当Xj=0时，有Zj=0，故aijy一cj,一0=1m当0 cXj0，有送丙Yi+Zj=Cji仝m又由Xj :Uj,有Zj=0,故 7aijYi二Cj,Cj=0i旦m当Xj=Uj，有Zj-0，故 7aijYi乞Cj, Cj-0。im20、某医院的护士分四个班次，每班工作12h。报到的时间分别是早上 6 点、中午 12 点、下午 6 点、夜间 12 点。每班需要的人数分别为19 人、21 人、18 人、16 人。问：(1) 每天最少需要派多少护士值班？(2)如果早上 6 点上班和中午 12 点上班的人每月有 120 元

42、加班费，下午 6 点和夜间 12 点上 班的人每月分别有 100 元和 150 元加班费，如何安排上班人数，使医院支付的加班费最少？答案：设X1, X?, x3, X4分别表示早上 6 点、中午 12 点、下午 6 点，夜间 12 点开始上班的人数。则有：(1)Mi nZ = X-!X2X3X4d+疋兰19X+X -21 x2+ x3色18% +x4色16刍，X2,X3,X4-0MinZ = 120(XiX2) IOOX3150 x4试卷答案第33页（共 55 页） +X4 19x1+x221X2X3-18x3+x416冷X2,X3,X4-0解得：(1)z =37,X|=19,X2=2,X3=

43、16,& =0。z = 4120,x0,yij0,zJ0(i,j =1,2,3)试卷答案第35页（共 55 页）23、战斗机是一种重要的作战工具，但要使战斗机发挥作用必须有足够的驾驶员。因此生产出来的战斗机除一部分直接用于战斗外，需抽一部分用于培训驾驶员。已知每年生产的 战斗机数量为aj（j =1; , n），又每架战斗机每年能培训出k 名驾驶员，问应如何分配每年生产出来的战斗机，使在n 年内生产出来的战斗机为空防作出最大贡献？答案：用Xj表示第j年生产来分配用于作战的战斗机数 ；yj为第j年已培训出来的驾驶员 总数；（-Xj）为第j年用于培训驾驶员的战斗机数 ;召为第j年用培训驾驶员

44、的战斗 机总数问题的线性规划模型为：maxz二n （n _1）x2 2xn二xnZ二召丄+佝Zj） （j =1广,n）yj二力丄卄召丄（j =1,n）st. *为+X2 + +XjEyj（j =1,，n）xj, y ,Zj0 （j=1,n）24、用单纯形法求解下列线性规划问题，并指出问题的解属于哪一类：（a）maxz=3xi5x2xi0(d)maxz二 6x24x3一咅+2x2+2x3兰134论一4x2+ x3兰20 st.x+2x2+ x317人KI% A2,X3兰3答案:XiX2X3X4X5X320011/3-1/3x?60i01/20 x2i00-1/31/3Cj-召000-3/2-1(

45、b)X1X2X3X4XXX4100011-1-2X115101/201/21/2X501-3/20-1/21/2Cj_Zj00-3/20-3/2-1/2(c)X1X2X3X4X5X6X7试卷答案第37页（共 55 页）Xe70110012211X25-510210-2X320-601720-3Cj_召7600-66-22034maxz无界（d）令X；=Xi-1,X2=X2- 2,Xa=Xa- 3，代入化简得maxz = x；6X24X325_X| + 2x；+2x3兰44x14x；+x3兰21st.x；+2x2+x3兰9,x；, x2, x30计算得最终单纯形表如表（d）x1x2x3X4X5X

46、6X；1/4010-1/8-1/83/8x340011/21/6-1/6X9/2100-1/41/125/12Cj_zj00-3/2-10-2119有无穷多最优解。其中之一为x； =,x2=,怡=72425、用改进单纯形法求解线性规划问题：（a）maxz =5x；8x27x34x46x52x； 3X23X32X42X5岂20st.3x；+5x2+4x3+2x4+4x5兰30八0 （j =1，5）试卷答案 第 34 页(共 55 页)(b)min z - -x 2x2怡 一x4-4龙2XQN +X2+ X3+ x4+ x5+ x6兰6 2%+X22X3+x44st.x3+ x4+2x5兰4XjK

47、O (j=1 ,6)答案：(a)最优解为Xi= 0,X2= 5,怡=0 凶=5/2, xs= 0,max z =50;(b)最优解为x1=0,X2=4,X3=0,x4= 0,x5= 2,x6i= 0,minz - -1626、用图解法求解下列线性规划问题并指出问题是具有唯一最优解、无穷多最优解、无界 解还是无可行解？(1)maxz=2 为2X2|Xi- X2_,1st 0.5捲+X2兰2Xi, X2-0(2)maxz=为x2论X2-0st 3为一X2乞 一3L.X1,x2王01，目标函数可以增加到无穷大，因此该问题/町图 1(2)该问题的可行域为空集，见图2,因此无可行解，当然就不存在最优解。

48、答案：(1)该问题可行域也为无界域，见图 无最优解或为无界解。试卷答案第39页（共 55 页）27、对某厂 1,11 , III 三种产品下一年各季度的合同预订数如表所示。产品季度1234I1500100020001200II1500150012001500III1000200015002500该 三 种 产 品 1 季 度 初 无 库 存 ， 要 求 在4 季 度 末 各 库 存 15 0 件 。 已 知 该 厂 每 季 度 生 产 工 时 为15 000 h,生产 I，II，III 产品每件分别需时 2，4，3 h。因更换工艺装备，产品 I 在 2 季度 无法生产。规定当产品不能按期交货时

49、，产品I，II 每件每迟交一个季度赔偿 20 元，产品III 赔偿 10 元；又生产出的产品不在本季度交货的，每件每季度的库存费用为5 元。问该厂应如何安排生产，使总的赔偿加库存的费用为最小（要求建立数学模型，不需求解）。答案：设Xij为第j季度生产的产品i的数量，Sij为j季度末需库存的产品i的数量Fij为第j季度末交货的产品i的数量，&为第j季度对产品i的预订数，则有33 3minz=2：（20 +10F2j+5FG+5瓦送sj 1i=1 j=12x1j4x2j3x3j 60% 15% 60% 50%2.001.501.002 0002 5001 200加工费/ （元 /kg）0.

50、500.400.30售价/（元/kg）3.402.852.25问该厂每月应生产这三种牌号糖果各多少，才能使该厂获利最大？试建立这个问题的线性规划的数学模型。答案：设X!,X2,X3分别表示生产甲糖果时， A，B，C 的用量；X4,X5,X6分别表示生产乙糖 果时 A，B，C的用量；X7,X8,X9分别表示生产丙糖果时 A，B，C 的用量，则有模型maxz =(3.4-0.5)(为X2X3)(2.85-0.4)(&X5X6)(2.25-0.3)(X7XSXJ-2(xX4X7) -1.5区X5Xs) -(% X6Xg)% /(X1+x2+x3)亠0.6X3/(Xi+X2+X3)工0.2X4

51、/&4+X5+x6)0.15X6/(X4+X5+冷)兰0.6s.t X9/(X7+X8+X9) H0.5捲+ x4+ x7兰2 000X2+ X5+ Xs兰2 500X3+ X6+ X9兰1 200X1,X2, Xg-029、已知下表是求某极大化线性规划问题的初始单纯形表和迭代计算中某一步的表。试求 表中未知数a l的值。表X1X2X3X4XXX5205-413b10试卷答案第42页（共 55 页）X8j-1kc01X2X3X4XXCj_Zj16-7a00X3d-1/701-2/7F4/7屜el10-3/7-5/7GCj-Zj72/70011/7hJ答案：a=1b=-c = -d= e

52、= f =-，g= h= i=- j=k=2l=- /730、已知线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表如表和（b）所示，请将表中空自处数字填上。表（a）2-11000X1X2X3X4XX0X4603111000卷 101-120100X62011-1001Cj-Zj2-1100010X41-1-22X101/21/2试卷答案第43页（共 55 页）-1x20-1/21/2Cj_Zj表（b）-2-3-20-M0-MXiX2X3X4XX6X7-MX58142-1100-MX7632200-11Cj-Zj-2+4M-3+6M-2+4M-M0-M0*-3x20.3-0.1-2-

53、0.20.4Cj_Zj-M+0.5-M+0.5答案：（a）X1X2X3X4X5X60X4100012X15101/2-1X2501-3/2Cj-Zj00-3/20-3/2-1/2(b)X1X2X3X4X5XX试卷答案第44页（共 55 页）-3X21.8010.4-0.30.1-2X10.8100.40.2-0.45 -弓000-0.5-0.531、某厂生产 1,11 两种食品，现有 50 名熟练工人，已知一名熟练工人可生产10 kg/h 食品 I 或 6 kg/h 食品 II。据合同预订，该两种食品每周的需求量将急剧上升，见表。为此该 厂决定到第 8 周末需培训出 50 名新的工人，两班生产

54、。已知一名工人每周工作 40h，一名 熟练工人用两周时间可培训出不多于三名新工人（培训期间熟练工人和培训人员均不参加生产）。熟练工人每周工资 360 元，新工人培训期间工资每周120 元，培训结束参加工作后工资每周 240 元，生产效率同熟练工人。 在培训的过渡期间，很多熟练工人愿加班工作， 工厂决定安排部分工人每周工作60 h，工资每周 540 元。又若预订的食品不能按期交货，每推迟交货一周每 kg 的赔偿费：食品 I 为 0.50 元，食品 II 为 0.60 元。在上述各种条件下， 工厂应如何作出全面安排，使各项费用的总和为最小（建立模型，不需求解）。表单位：t/周次食品12345678

55、I1010121216162020II67.28.410.810.8121212答案：设xi，yi分别为第i周内用于生产食品 I 和 II 的工人数；zi为第i周内加班工作的 工人数；i为从i周开始抽出来培训新工人的原来工人数；ni为从i周起开始接受培训的新工人数；斤!和Fi2分别为第i周末未能按期交货的食品 I 和 II 的数量；&和R2i分别为第i周内对食品 I 和 II 的需求量，则有877min zL 540z+ 送（0.5已+O.6F2） +瓦240+240（7 k）riki di =1kd试卷答案第45页（共 55 页）400E百+叮=无(t=1,，7)td148400人=

56、116000i二ii240送yt+Fi2=5；R2t(t=1,，7)tdt 8240E yj=79200idXi十yi+国1兰50 +0.5乙x2y2r 2=50 0.5z2i _2K+ 引 丄=50+E nt+0.5乙(3WiW8)时8 =07送n =50n兰3jXi,yi,z,i,口，片丁2匚=032、用图解法求解下列线性规划问题，并指出各问题是具有惟一最优解、无穷多最优解、 无界解或无可行解。(d)maxz =3音-2X2xx2_ 1st. 2x12x2- 4.X1,x2- 0(f)maxz二3x14x2x|+3x2兰22 Xi+2x2兰8ix| +x?兰4(a)min z = 6为4x

57、22xiX2-1st 3Xj4x2-1.5X1,X2-0(b)maxz =4X18X22X12X2-10st：x,x2_8X1, X2- 0(c)maxz = X。X28x1+6X2工244x1+6x2K T2 st2x4*, X2启0(e)maxz =3x19x2试卷答案第46页（共 55 页）xH 2x12st.x2_6st.2为+x2兰162论一5x2兰0 I Xi,X230Xi，X2一0答案：(a)惟一最优解，z =3,x1=1/2,x0;(b)无可行解；(c)有可行解，但maxz无界；（d）无可行解；（e）无穷多最优解Z =66；（f）惟一最优解，* 2z =30-必=20/ 3,

58、X2=8/3333、将下列线性规划问题变换成标准型，并列出初始单纯形表。min z- -3x-i4x2-2x35x44x1 X2+ 2X3 X4 =2禺+ x2+ 3x3 沧兰14s.t /12X1+3X2怡+2X4艺2x, x2, x0, x4无约束答案：令X4= X4- x4，且X4, X4一0；引入松弛变量X6一0,剩余变量X7一0,人工变量X5,X8-0，得线性规划的标准型为maxz =3为一4X22X3-5(x-X4) -MX5-MX8-4为+ x2 2X3+ x4 x；+ x5= 2片+% +3/_拓+x：+ x6=14s.t ”“2% +3x2-x3+2x4_2x4_x7+x8=

59、2iX1,X2,X3，X4,X4,X5,X6,X7, 8_ 0其中，M为充分大的正数，初始单纯形表如下表所示。Cj3-42-55-M00_MCBXBbX1X2X3x4IFX4X5X6X7X-MX52-41-21-11000试卷答案第47页（共 55 页）0X14113-110100-MX2-23-12-200-11-6M +34M -43+23M -5-3M +500-M0z = 0,xi= 0,x2= 0,x3= 4,x4= 0。z =7.08,x1=0,x2= 0, x3= 1.35,X4= 0.21。35、讨论如何用纯形法求解下述线性规划问题：nmaxz=瓦CjXjj壬-nE ajXj

60、=bj(i=1,m)st.jxj取值无约束34、用单纯形法解下列线性规划问题(1)MaxZ =6为X2-x3x4X +2x2+x3=152Xj+5x2=182% 4x2x3x4=10XZXN一0(3) MaxZ =3x2x24x38x4xi2x25x36X4一8-2x(5x23x3-5x二3为，X2,X3,X4-0答案：(1)无可行解。(可用大M 法或两阶段法)。(2)MaxZ= 4为3X2试卷答案第48页（共 55 页）ji0,当Xj- 0当xj:0答案：令Xj二当Xj-0当xj: 0试卷答案第 43 页(共 55 页)nmaxz八 5%xj)j 4n aj(Xj Xj)(i1/,m)st.j 4xjjO这是标准型，可用单纯形法求解。36、试利用两阶段法第一阶段的求解，