(完整word版)运筹学试卷1

1、第一套一、写出下列线性规划问题的对偶问题：（8分）MIN Z =5X1 -6X2 -7X3-X1 5X2 -3X3 .15共 23 页 第9页约束条件-5X1 -6X2 10X3 <20X1 -X2 -X3 - -5X1 <0,X2至0, X3不受限制 -答案：Max 3 =15Y1+20Y2-5Y3-Y1-5Y2+Y3W -5约束条件5Y1-6Y2-Y3> -6-3Y1+10Y 2-Y3= -7Y1> 0,Y2W 0,Y3不受限制制二、用图解法求解下列线性规划问题：（10分）MAX Z =10X1 5X23X1 4X2 <9 12约束条件5Xi 2X2<8

2、Xi,X2 -0答案：（Xi, %） = （1 , 3/2 ）, Z*=17.5、用沃戈法求下列运输问题的初始基本可行解（12分）产地、甲乙丙丁1412411|_1622 110391038511622销量814121448答案：X13 =12,Xi4 =4X21 =8,X24 =2,X32 =14X34 =8,其他变量的值等于零。四、用对偶单纯形法求解线性规划问题：（12分）MIN Z =4X1 12X2 18X3Xi3X3.3约束条件2X2 2X3 一 5X1 3 -0答案:CX BbXX2X3X4X5-18X 311/301-1/30-12X 23/2-1/3101/3-1/2C-Zj-

3、200-2-6五、某公司安排五名工作人员到五个不同岗位上工作。但必须对上岗人员进行培训。由于五名工作人员的经历不同, 文化水平也有差异，故所需培训时间也不相同。如下表所示A1做B2项工作；A2做B3项工作；A3做B4项工作；A4做B5项工作；A5做Bi项工作六、若某产品中有一外贝件，年需求量为 10000件，单价为100元。由于该件可在市场采购，故定货提前期为零，并10%试求经济定货批量及每年的最设不允许缺货。已知每组织一次采购需2000元，每年每件的存贮费为该件单价的 小存贮加上采购的总费用。（10分）R=10000, C3=2000, C二100X 10%=10= 2000 （件）* ZZ

4、 c = j2GQ3r =12乂10乂 2000M10000 = 20000 （兀）七、某工程项目各项活动的逻辑关系如表所示，试绘制网络图，并确定关键路线。（12分）工序名称紧前工序花费时间（天）A一3B一2C一2D一2EB2FC2GF、D3HA、E、G4（2）四条路线的路长为：（5分）：A+H=3+4=7 （天）：B+E+ H=2+2+4=8 （天）：D+G+H=2+3+4=9 （天） C+F+G+H=2+2+3+4=11 （天）路径活动时间最长，所以是关键路径（计算时间参数较好） 八、已知线性规划问题：（12分）MAX Z =2X1 -X2 X3X1 X2 X3 < 6约束条件-X1

5、-2X2 M 4X1, X2, X3 -0用单纯形法求解得最终单纯形表如下表所示：XiX2X3X4X5X161111OX51003111C-Zj-3-1-2试说明分别发生下列变化时，新的最优解是什么（1）目标函数变为 MAX Z= 2Xi + 3X 2 + X 3，6 、3（2）约束条件右项由变为| |% 一 ,答案：(1) X* =(8/3,10/3,0,0,0) X =(3,0,0,0,7)九、已知赢得矩阵为1 7A = |9 013-2试用图解法求解此对策。（12分）答案：局中人I和n的最优混合策略分别是X* =3,-卜口 Y* = I ,0 1,对策的值义 5 515 155七、某一决

6、策问题的损益矩阵如表所示：其中矩阵元素值为年利润EiE2E3S4020024003603603601000240200（1）若各事件发生的概率是未知的，分别用悲观法、乐观法、后悔值准则作出决策方案（2）若豆是乐观系数，问 支取何值时，方案 &和$3是不偏不倚的。（12分） 答案：1）悲观法：应选 S2。乐观法；应选 Si。后悔值法：应选S2（2） a =0.10256第二套一、用图解法求解下列线性规划问题，并说明解的情况。MAX Z -X1 X28X1 +6X2 >24（10 分）约束条件4X1 6X2 - -122X2 _4X1 -0,X2 -0答案：有可彳T解，但 MAX Z

7、无界。二、写出下列线性规划问题的对偶问题：（6分）MIN Z =3X1 2X2 -3X3 4X4X-2X2 +3X3 +4X4 <3约束条件X2 3X3 4X4 - -52X1 -3X2 -7X3 -4X4-2I 234X1 -0,X4 一0, X2,X3不受限制答案:MAX =36 -5Y2 2Y3Y +2工 <3-2Y +Y2 -3Y3 =2约束条件3X 3Y2 -7丫3=-34丫1 +4丫2 4丫3 至 4M <0,Y2之0,工不受限制产地、甲乙丙丁12113470三、已知某物资的产量、销量及运价表如图所示，试制定最优调运方案（12分）210359503781270销量

8、20304060最优调运方案是：X1*1 =20,X1*4 =30,X；5 =20,X；2 =30,X；5 =20,X33 = 40,X34 = 30,目标函数值为 Z*=20 X 2+30 X 4+20 X 0+30 X 3+20 X 0+40 X 1+30 X 2=350。第三套一、用图解法求解以下线性规划问题（12分）MAXZ =15X 25X23X1 +2X2 <652X1 +X2 <40st123X2 < 75Xi .0,i =1,2答案：最优解为(X1,X2)=(5,25), MAXZ =700三、已知某物资的产量、销量及运价表如图所示，试制定最优调运方案(16分

9、)甲乙丙丁121134 1702103595037812 170销量20304060最优调运方案是：X1*1 =20,X1*4 =30,X；5 =20,X；2 =30,X；5 =20,_ _ * _ _ _ * _ _X33 = 40,X34 =30,目标函数值为 Z*=20 X 2+30 X 4+20 X 0+30 X 3+20 X 0+40 X 1+30 X 2=350。五、某工厂生产甲、乙、丙三种产品，已知有关数据如表所示：(16分)原品料甲乙丙原料拥有量A63545B34530单件利润415(1)建立线性规划模型，求使该厂获利最大的生产计划；(2)若产品乙、丙的单件利润不变，则产品甲的

10、利润在什么范围内变化时，上述的最优解不变。(1)设Xi,X2,X3分别代表甲、乙、丙产品产量，线性规划模型是：Max Z=4X i+X 2+5X3f 6X+3X2+5X3<45约束条件( 3X1+4X2+5X3< 30I Xi >0 i=1,2,3. - .一 * . . . 一 *用单纯形法解得，X = (5, 0, 3),最大盈利为z =35(2)产品甲的利润变化范围为3, 6第五套一、用图解法求解下列线性规划问题(15分)max z = 3x1 4x2x1 2x2 8x1 2x2 <12 st.2x1x2 M 16x1 - 0 , x2 - 0答案：唯一最优解 z

11、=92/3, Xi=20/3, x2=8/3二、下表为某求极大值线性规划问题的初始单纯形表及迭代后的表,X4、X5为松弛变量，试求表中a到XiX2X3X4X5xmbcd106Xn-13e011%a1-200Xsg2-11/20fXthi11/21407jkll的值及各变量下标m至h的值。(20分)答案：a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0;变量下标：m=4,n=5,s=1,t=6三、用图解法求解矩阵对策g=Si，S2，a,2 4,其中A =5 45 47答案：P =(-,-)Q=(0, 0,一，一)Vg =-9 99 99共

12、23页 第6页!7分51试画出该工程的网络图解:四、（20分）（1）某项工程由8个工序组成，各工序之间的关系为工序abcdefgh紧前工序一一aab,cb,c,db,c,de线路（箭线下的数字是完成该工序的所需时间，单位：天）解：（2）试计算下面工程网络图中各事项发生的最早、最迟时间及关键1010关键线路为：1 “ 2 ' 4 + 6 > 7或 1 >2 - 5 -'句一：7总工期为13天。五、已知线性规划问题max z =10x1 24x2 20x3 20x4 25x5_Lx1 x2 2x3 3x4 5x5 19st. 2x1 4x2 3x3 2x4 x5 三 5

13、7为之 0 (j =1,2,3,4,5)其对偶问题最优解为y1 =4, y2 =5,试根据对偶理论求原问题的最优解。（15分）答：X=（0,14,0,0,1）六、用动态规划法求解下面问题：（15分）M A XZ = x1 x；x3x1x2x3 ; cxj - 0,j =1, 2, 3解：最优解：x, =-c, x2=lc, x3=lc；最优值c44223464七、已知线性规划问题M AXZ =2x1 - x2 x3| x1 x2 x3 <6s.t_x1 +2x2<4x1 , X2, X3 >0 J用单纯形法求得最优单纯形表如下，试分析在下列各种条件单独变化的情况下，最优解将如

14、何变化。(30分)cj2-1100bCBX Bx1x2x3x4x52x11111063x50311110a0-3-1-20(1)目标函数变为 MAX Z =2x1 +3x2 +x3；(2)约束条件右端项由变为,3 1；4 4(3)增加一个新的约束：x1+2x3 >2答：(1)最优解为：x= (8/3, 10/3, 0, 0, 0) T;(2)最优解为：x= (3, 0, 0, 0, 7) T;(3)最优解为：x= (10/3, 0, 8/3, 0, 22/3) T;八、某地区有A、B、C三个化肥厂向甲、乙、丙、丁四个销地供应同一种化肥，已知产地产量、销地 需求量和各产地运往不同销地单位运

15、价如下表，试用最小元素法确定初始调运方案，并调整求最优运输 方案(20分)销地甲乙丙丁)里A41241116B2103910C8511622需求量814121448答：x11=4, x13=12, x21=4, x24=6, x32=14, x34=8最小费用：244第六套一、(20分)已知线性规划问题:min z =2x1 3x2 5x3 6x4x1 +2x2 +3x3 +x4 > 2st-2x1 +x2 -x3 +3x4 < 3xj 20 (j=1,2,3,4)(a)写出其对偶问题；(b)用图解法求对偶问题的解；(c)利用(b)的结果及对偶性质求原问题的解。(a)Max z=2

16、y1-3y2Y1-2Y2422Y1+Y2 <3约束条件3丫1-丫2< 5Y1+3Y2<6Y1 I > 0,Y2 < 0(b) Y= (8/5 , 1/5);(c) X= (7/5 , 0, 1/5 , 0)二、(20分)已知运输表如下:.7肖地 产通、,B1B2B3B4供应量A13_2_7650A2匕5_2360A32_5_4525需求量60402015(1)用最小元素法确定初始调运方案；(2)确定最优运输方案及最低运费。初始解：x11=10,x12=40,x21=25,x23=20,x24=15,x31=25最优解：x11=35,x12=15,x22=25,x2

17、3=20,x24=15,x31=25三、(35分)设线性规划问题maxZ=2x1 +x2 +5x3+6x4工2x1 x3 x4 -82x1 2x2 x3 2x4 -12x1, x2, x3, x4 -0的最优单纯形表为下表所示共 23 页 第15页XbbX1X 2 X3X4 X 5X 6X342-2 102-1X440201-11叼-8-1 00-4-1利用该表求下列问题:(1)(3)(4)要使最优基保持不变，C3应控制在什么范围；要使最优基保持不变，第一个约束条件的常数项 b1应控制在什么范围;当约束条件中X1的系数变为 12 时，最优解有什么变化；1如果再增加一个约束条件 3X1+2X2+

18、X3+3X4< 14,最优解有什么变化。11（1） 3<C3<-2（2） 6 MbM12（3）最优解不变*（4）最优解 X1=0, X2=0, X3=5, x4=3 最优值 Z =43四、（20分）需要指派5人去做5项工作，每人做各项工作所消耗的时间如下表:作 人心、ABCDE甲382103乙8729 171丙64275丁8423 15戊9106910问指派哪个人去完成哪项工作，可使总的消耗时间最小?五、（20分）X15=X23=X32=X44=X51=1 (甲-E,乙-C,丙-B, 丁-D,戊-A)最小时间 21用图解法求解矩阵对象 G=（Si,S2,A）,其中P= (0,

19、4/5,1/5,0)一681151972Q= (2/5,3/5) Vg=43/5工序紧前工序工序时间（天）工序紧前工序工序时间（天）工序紧前工序工序时间（天）a-60gb, c7mj, k5ba14he, f12ni, l15六、（20分）已知资料如下表:Vk（Xk）IV4（X4）其中X 1910Xk30Uk（8分）ca20if60on2da30jd, g10Pm7ea21kh25qo, P5fa10lj, k10(1)绘制网络图；(2)确定关键路线，求出完工工期。答：关键路线为a-f-n-o-q,总工期为152天七、(15分)某工厂有100台机器，拟分四个周期使用，在每一周期有两种生产任务。

20、据经验，把机器1X1台投入第一种生产任务，则在一个生产周期中将1 X1台机器作废；余下的机器全部投入第二种生产3任务，则有 工机器作废。如果干第一种生产任务每台机器可收益10,干第二种生产任务每台机器可收10益7,问怎样分配机器，使总收益最大？解：设Xk为第k周期末机器完好数，uk为第k+1周期安排干第一种生产任务的机器数。Q(Xk)=u k|0 < Uk< Xk= maX10Uk 7区 -7）Vk1（Xk1）0 Uk Xk=0 （k = 3、2、1、0）用逆推法求得：最优决策为第一、二周期机器全部投入第二种生产任务，第三、四周期机器全部投入第一种生产任务。最大收益为2680。第七

21、套一、（15分）用图解法求解下列线性规划问题max z = 3x14x2-x12x2 M 8x12x2 m 12st. 122x1 + x2 M 16L. X1 - 0 , X2 - 0答：唯一最优解 z=92/3, X1=20/3, X2=8/3、(30分)已知线性规划问题共 23 页 第17页m a)Z = 2x1 - x2 x3x1 + x2 + x3 M 6- x1 2x2 M 4xi,x2,x3 > 0用单纯形法求的最终表如下表所示:Xbbx1x2x3x4x 5x2611110x51003111a j =Cj1 _-CbB Pj0-3-1-20试说明分别发生下列变化时，新的最优

22、解是什么？(1)目标函数变为 max Z =2x1 +3x2+x3 ;(2)约束条件右端项由：1变为3 '|(3)增添一个新的约束-x1 +2x3之2。/、*/、 T(1) x = (8/3 , 10/3,0 , 0, 0)/ 一 */、 T(2) x = (3, 0, 0, 0,7)(3) x*= (10/3 , 0, 8/3 , 0,22/3 ) T三、(20分)(1)某工程由9项工作组成，它们之间的逻辑关系为:工 作紧前工作A D, LGB, FHL_-C, H要求画出该工程的网络图。(2)某工程的网络图为1 A5B 3C E3 B第12页HF-H-®J3箭线下的数字表

23、示完成该项工作所需天数。试求a）各个事项所发生的最早、最迟时间;关键线路为共 23 页 第22页总工期为28天。四、（15分）写出下列线性规划问题的对偶问题MIN Z -2X1 3X2 -5X3 X4X +X2 -3X3 +X4 之52X1十 2X3X4 M4s.t.«X2 + X3 +X4 = 6X1 <0,X2 >0,X3 0,X4不受限制max = 5y1 4y2 6y3'y1 +2y2之 2y1+ y3 < 3st, -3y1 +2y2 +y3 15y1 - y2 + y =1y1至0,y2 E0 ,y3无约束五、（20分）矩阵对策G=S1,S2，A

24、,其中局中人I的赢得矩阵为:A,04-3012试用图解法求解2 1P =（-，-）3 3六、（25分）设有物资从A1, A2, A3处运往B1, B2, B3, B4处，各处供应量、需求量及单位运价见下 表。问应如何安排运输方案，才能使总运费最少？地 产地B1B2B3B4供应量A137645A224322A343853需求重323210初始解:x11 =1 ,Xi3 = 2 ,X14 2 ， X21 = 2 ，X32 2 2 ， X33 1 （10 分）最优解:总运费：36元X14 = 2 ，X23 2 2 , X32 = 2 ,X31 = 11000台设备，甲方承担其余义务，生七、（25分）

25、甲、乙双方合资办厂，根据协议，乙方负责提供全部 产的产品双方共享。5年合同期满后，工厂全部归甲方所有。假定设备可在高低两种负荷下运转，在高 负荷下生产，产品生产量s1与高负荷运转设备数量u1关系为s1=8u1,此时设备折损后年完好率a =0.7;在 低负荷下生产，年产量S2与低负荷下设备数量U2关系为S2=5U2,此时设备折损后年完好率0=0.9。在排除 其它影响前提下，问甲方应如何安排 5年的生产计划，使5年后完好设备台数500台，同时5年总产量 最大？解：设Xk为第k年初完好机器台数，Uk为第k年安排高负荷运转设备台数，R（x k）=u k0 < Uk< Xk'fk（X

26、k） =maX8Uk +5（Xk - Uk） + fk书（Xk书） 0 _ u k xkf6（X6） =0 （k =5、4、3、2、1）其中 Xk1 =0.71 0.9（Xk-Uk）（10 分）用逆推法求得：最大产量f1（x1） =21900最优决策为第前4年所有设备低负荷下生产，最后一年所有设备高负荷下生产 第八套一、（10分）写出下列线性规划问题的对偶问题:MIN Z =3X1 4X2 -6X3 2X4X1 X2 -3X3 X4 -62X约束条件2X3 -X4 < 5X2 X3 X4 = 7X1 <0, X2 之 0,X3 2 0,X4不受限制max = 6y1 5y2 7 y

27、3yi +2y23yi+y3 <4s.tj -3yi +2y2 +y3 M -6yi - y2 + y3 =2yi之0,y2 W0,y3无约束(20分)下表是某线性规划问题的一个单纯形表。已知该线性规划问题的目标函数为max z =5xi +3x2,约束条件均为“ W”型不等式，其中X3和x4为松弛变量，表中解对应的目标函数值z = 10X Bx1x2x3x4b*3c011/52x1de01a5b-1fg(1)求a到g的值；(2)表中给出的解是否为最优解？(1)依次为：2, 0, 0, 1, 4/5 , 0,-5(2)是三、(10分)已知线性规划问题：MAX Z = X1 2X2 3X3

28、 4X4X1 2X2 2X3 3X4 <20 约束条件 2X + X2 +3X3 +2X4 <20 、Xi 之0 , i =1.2.3.4其对偶问题的最优解为Y1* =%, 丫2* =% * =28，试用对偶的互补松弛性求解原问题的最优解。X= (0, 0, 4, 4)四、(20分)已知整数规划问题：MAX Z = 7x1 9x2- x1 +3x2 w 6s.t. 7x1 + x2435凶，x220,且均为整数不考虑其整数规划，利用单纯形法求得其松弛问题最优单纯形表如下:X Bx1x2x3x4b又2017/221/227/2x110-1/223/229/2叼00-28/11-15/

29、11试用割平面法求整数规划问题最优整数解一、71. 1割平面方程（1） ：X3X4 22222一、| , 、164割平面方程（2） ： -7x4 7x5 7最优解：x1=4, X2=3五、（20分）某项研制新产品工程的各个工序与所需时间以及它们之间的相互关系如下表:工序紧后工序工序时间（天）ab,c,d,e60bL45cf10dg,h20eh40fL18gk30hL15kL25L-35（1）绘制该工程网络图;（2）关键路线:a-d-g-k-L六、（20分）已知运输表如下:共 23 页 第23页(1)用最小元素法确定初始调运方案；(2)确定最优运输方案及最低运费；(3)产地Ai至销地B4的单位运

30、价Ci4在什么范围内变化时最优调运方案不变(1)初始方案：x13=4,x14=3,x21=3,x23=1,x32=6,x34=3(2)最优方案：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3(3)最优方案不变：4条闭回路不影响检验数，9<c14< 10 七、(20分)用图解法求解矩阵对策 G= (S1, S2, A),其中235A =1-1 -22 1P =()3 3-21Q =( 一 ,0,0,)33八、(20分)需要指派5人去做5项工作，每人做各项工作所消耗的时间如下表人员、,ABCDE甲4871512乙79171410丙691287丁6714610戊6

31、912106问指派哪个人去完成哪项工作，可使总的消耗时间最小?最优指派：甲一C,乙一B,丙一A , 丁 一 D ,戊一E九、(10分)某批发站每月需某种产品100件，每次订购费为5元。若每次货物到达后存入仓库，每件 每月要付出0.4元存储费。若假设消耗是均匀连续发生的，且不许缺货。求最佳订货周期及最佳订购批 量。第十套用图解法求解下列线性规划问题，并说明解的情况。(10分)MAX Z = X1 X28X1 +6X2 >24“士以 4X1 +6X2 >-12约束条件 122X2 -4X1 -0,X2 -0有可行解，但MAX Z无界。二、已知线性规划问题(10分)MAXZ = X1 2

32、X2 3X3 4X4Ja1 2X2 2X3 3X4 < 20s.t.2X1 +X2 +3X3 +2X4 <20、X j 之 0, j = 1,2,3,4*其对偶问题的最优解为 Y1 =1.2,Y2 =0.2,试用对偶的互补松弛性求解原问题的最优解。原问题的对偶问题为：min w = 20Yi - 20Y2Y1 +2Y2 之 12Y1 +Y2 之 2约束条件22Y1 + 3Y2 >33Y1 + 2Y2 44Yi 0,i =1,2将Yi =1.2,丫2 =0.2代入约束条件，因为对偶问题的约束条件满足绝对不等式，则意味着所对应的原问题的变量等于零，因此，X1 =0,X2 = 0。

33、又因为丫 >0,丫2 >0 ,即对偶变量大于零，则原问题的约束条件取等式。MAXZ =X1 2X2 3X3 4X42X3 3X4 -20由此可得到2士.小34约束条件3X3+2X4 =20Xj 他=1,2,3,4其最优解X* =(0,0,4,4)T ,最优值Z* = 28三、已知生产甲零件分别需要A、B、C三种原料为5kg, 4kg, 2kg,获利12元，生产乙零件分别需要 A、B、C三种原料为4kg, 5kg, 5kg,获利21元，现库存 A、B、C三种原料为24kg, 20kg, 18kg,如何安排生产使获利最大？用 单纯形法求解(10分)项目甲零件(kg)乙零件(kg)库存量

34、(kg)A5424B4520C2518利润(元)1221建模MAXZ =12Xi 21X25Xi 4X2 <24约束条件以鼠或Xi -0,i =1,2转换标准型共 23 页 第26页MAXZ = 12X121X2 0X3 0X4 0X55X1 +4X2 +X3 =24约束条件4X1 5X2 X=202X1 5X2 X5 =18Xi _0,i =1,2,3,4,5Xb =(X3，X4，X5)T ,初始可行解 X =(0Q24,20,18)T列出单纯形表Cj1221000QCBXbbX1X2X3X4X50X3245410060X4204501040X5182500118/512210000X

35、348/517/5010-4/548/170X422001-1121X218/52/51001/5918/5000W1/50X331/5001-17/109/1012X111001/2-1/221X216/5010-1/52/5000-9/5-12/5基可彳T解X =(1,16/5,31/5,0,0)T,代入目标函数得到最优值Z =79.2四、已知以下线性规划问题 (15分)MAXZ = 2X1 -X2 X3X1 X2 X3 < 6s.t-X1 +2X2 <4Xi 之 0,i =1,2,3的最优单纯形表如下，分析下列条件单独变化的情况下，最优解的变化。Cj2-1100CBXBbX

36、1X2X3X4X52X 16111100X 51003111CT ; j0-3-1-20a为讣(1)目标函数变为 MAX Z=2xi +3x2 +X3；(2)约束条件右端项由 (1)目标函数变为 MAX Z =2xi +3X2 +X3列出单纯形表Cj23100CBxbbx 1x2x3x4x52x 16111100x 5100311101-1-20CBxbbx 1x2x3x4x52x 18/3102/32/3-1/33x210/3011/31/31/3500-4/3-7/3-1/3最优解为：x= (8/3, 10/3, 0, 0, 0) T; 最优值 Z* =46/3(7 分)二 1 0 33(2)因为建模b'=3,4,所以Bb'= I I = I |J 1A 7 J列出单纯形表Cj2-1100CBxbbx 1x2x3x4x52x 13111100x 5703111CT . j0-3-1-20因此原问题和对偶问题均为可行解，问题的最优基不变。*T*最优解X =(3,0,0,0,7),最优值Z =6五、已知运输表如下：(20分)地 产威B1B2B3B4供应量A1327650A27523 _60A325 _4525需求量60402015(1)用最小元素法确定初始调运方案；(2)确定最优运输方案及最低运费。x11 = 10,x