武汉科技大学本科历年运筹学试题

1、2002 级(A)参考答案1.写岀下述线性规划模型的标准型。(10 分)max wx|yzst.xy12xz 3解：令x x x ,y y y7zz z原问题标准化为：max wxxy y zzs.t.xxy yu 12x2xzz3x ,x,y ,y ,z,z 02.有线性规划模型： max z 10x.| 5x2（ 10 分）s.t.3x-i4x295x12x28%0X0(1)用图解法求解；(2)用单纯形法求解；(3)指岀每个单纯形表的可彳亍域顶点。解：（1 ）用图解法求解;X24|c 5x计2x =83（2）用单纯形法求解；原模型标准化为：min z10x1 5x2s.t.3x-| 4x2

2、 x395x1 2x2x48X10, X20,X30,X4则求解过程为：/ X*= (1 , 1/2 ) T; Z=35/20Cj-10-500bCbXbX1X2X3X40X3341090X45*2018o j-10-50000X3014/51-3/524/5-10X112/501/58/5o j0-10216-5X2015/14-3/143/2-10X110-1/72/71o j005/1425/1435/23.求解：min z 5x12X24X3st.3x1x22x346 x-i 3x25x310X1,X2, X30解:原问题标准化为：min z5x12x24x3s.t. 3x1X2 2x

3、3 X46x13x25x3/ X*= (1 , 1/2 ) T; Z=35/2(3)指岀每个单纯形表的可行域顶点。T 0表对应0点；Ti表对应B点；T2表对应A点，也是最优点（10 分）4X510用对偶单纯形法求解Xi,X2, X3, X4,X50为：C52400bGXbX1X2X3X4X50X4-3-1-210-40X5-6-3*-501-10o j5240000X4-1*0-1/31-1/3-2/32X2215/30-1/310/3o j102/302/320/3-5X1101/3-11/32/3-10X20112-12o j001/311/322/3 X = (2/3 , 2, 0) T

4、; Z =22/3(注：用大M法、两阶段法求解均可)4.写岀线性规划问题：max z 6x1 4x2 x3 7x4 5x5s.t. 3xi 7x2 8x3 5x4 X522xi X2 3x3 2x4 9x56Xj的对偶规划。解：原问题的对偶规划为：0 （j 1,2,3,4）; x5为自由变量（10 分）min w 2y1 6y23y12 y267y1y248y13y215y12 y27y19y25y , y2为自由变量（10 分）5.有一最小化指派问题的系数矩阵如下，试求其最优解。21097154148C13 14 16 11415139解：用匈牙利算法求解为：2109720875154148

5、4110104C变换后：C113141611112350415139401195-50325060313054再变换为IIP4、C2再变换：C20004300厶uu01452092300 10*01 00X00 01Z*=2810 002 26.写出函数f (X) x12x1x2 3x2的梯度和海赛矩阵，并判断其凹凸性。(10 分)2 2解：f(X) x-i2x1x2 3x2的梯度矩阵为：f(X)(空2 丄凶)T (2x1 2X2,2X1 6X2)Tx-1x22 2f(X) x1 2x1x2 3x2的海赛矩阵为:2f(X) 2f(X)22H f (X)XiXi X2222f(X) 2f(X)2

6、X2 XiX2这里H矩阵的各阶主子式均大于 0,所以f (X)22X1 2x1x2 3x2为严格凸函数。7.某厂有4台设备，拟分给3个用户(工厂)使用，各用户利用设备提供的盈利如下表。问 如何分配设备才能使总盈利最大？试建立其动态规划求解模型(可不求解) (10 分)用户设备台数、12300001423265537674788解：根据题意，原问题用动态规划求解模型为：(1) 按用户分为3阶段，K=( 1, 2, 3, 4)，k=4为终了阶段；(2) Xk :第k阶段初拥有待分配设备台数；xi=4，0 X2 4，0 X3 4，X4=0;(3) uk :第k阶段分配给第k用户的设备数，有：U1=0

7、,1,2,3,4 ，U2=0,1,2,x 2，U3=X3;(4) 状态转移方程：xk 1 xk uk;(5) 阶段指标：见表，如：d2(3,2) 5 ； d3(2,1) 3 ;(6) 递推方程：fk(xQ maxdk(Xk，uQ fk1(XkJuk Uk(7) 边界条件：f4(x4)0。8.证明下图所示V1至V6流为最大流。弧边数字为 (5,冷)。(10 分)证明：对原流图用标号法找可扩充路有:(vi,3,maxQ=5。标号过程进行不下去，即不存在V1-V6的可扩充路，根据可扩充路定理，图示流即为最大流9.下图为求v1至V5的最小费用最大流时得到的某一流图，弧边数字为（Cj, fj, aj），

8、试构造其费用有向图（流增量图）W(fjjk)。( 10分)10.某商行夏季订购一批西瓜，根据以往的经验，西瓜销售量可能为 元/kg，商行支出成本为 0.25元/kg。（1）建立益损矩阵；（2）分别用悲观法、乐观法、等可育能法和后悔值法确定西瓜订购数量0.3510000、15000、20000、25000kg。假定西瓜售价为（3分）（7分）解：（1）原问题的益损矩阵为；a iS j10000100015000-25020000-150025000-27501000015000 20000 2500010001000100015001500150025020002000-10007502500悲观

9、准则：maxmpdjmax 1000,250, 1500, 27501000乐观准则： max max dijmax 1000,1500,2000,25002500dj等可能准则：maxjmax1000,1062.5,687.5, 1251062.5n*2后悔值准则：050010001500125005001000后悔值矩阵为：2500125005003750250012500则 min max dj min 1500,1250,2500,37501250j（答题毕）2002 级（B）参考答案1. 求解线性规划问题:MaxZ 4x-i 3x2st. 3x1 4x2122x1 x24（15 分）

10、3x-| 2x22x1, x2 0的最优解解：图解过程如下:|x2443T23x10344x22x1 x2A（4,12 5 5124 12 t 祐）52（15 分）2. 写岀下述线性规划的对偶规划MinZ 5x1 6x2 7x3 4x4S.t. Xi2X2X3X476x1 3x2 x37X41428x117 x24x32x43x1, x20 ； x3,x4 无限制。解：对偶规划为 MaxZd=-7wi+14w2 +3was.t. w i +6W2+28W6 52w-3w2+17w3 0。3. 某一求目标函数极小值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下。问ai、a?、a3、c、

11、d各为何值以及变量x属哪一类性质变量时，（1）现有的解为唯一最优解；（2）现有解为最优，但最优解有无穷多个；（3）存在可行解，但目标函数无界；（4） 此线性规划问题无可行解。（15分）基变量XiX2X3X4X5bX3-131004X4ai40101X5a2a3001dCj-Zjc2000解：（1） d 0，c0， X3，X4，X5为非人工变量;（2） d 0，c=0，ai，a2中至少一个大于零，X3，X4，X5为非人工变量;（3）d 0，c0，ai 0，a20，c0，ai 0，a2 0 ，日3=0，x 5 为人工变量。4. 用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间缩小多少倍？

12、若要将区间缩小至原区间的10%以下，则至少要多少次迭代？（ 10分）解：用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间是原区间的0.618倍。经n次迭代后，区间长度为：Sn=0.618 nS0o若要将区间缩小至原区间的10%以下，即Sn/s 05)，U3=X3。(4) 状态转移方程：Xk 1Xk Uk ;(5) 阶段指标：见表，如：d2(3,2) 14 ； d3(2,1) 12 ;(6) 递推方程:fk(Xk) mxdk(Xk,Uk) fk1(XkJUk Uk(7) 边界条件：f4(X4)0 0(15 分)7.写岀求解网络最小费用最大流问题的算法步骤。解：设(Cjj, fjj ,a

13、jj)分别表示(容量，流量，费用)，最小费用最大流问题的算法步骤为:0，迭代后得fjjg ； ,k)，设 W(fj(k) 中弧得权(0) ij(2)构造费用有向图(流增量图)(1)给定初始可行流W(fjwij 为:wjajijCjijCjWjiaijijij其中Wjj的弧可以去掉；(3)求 W(fij(k) 中V1至Vn的最小费用路(可扩充路)P；P上调整流量(k 1) ij(k)ij(k) ij fj(k)ij(Vi, Vj)(Vi,Vj)(Vi,Vj)P的正向弧；P的反向弧；(4) 在最小费用路(可扩充路)式中min min(cfij(k),min(f,)pp（5）重复（2）（4）步，找不

14、到vi至vn的最小费用路（可扩充路）P时，则得到最小费用最大流，迭代结束。8.某农场需决定种植农作物的种类：A、A、A。种植不同作物的收益（元）主要取决于天气（见下表），要求：（1） 用不确定型决策方法，决定种哪一种作物。（5分）（2） 如天气预报给出好天气的概率为0.3，中等天气的概率为0.4，坏天气的概率为0.3，用风险型决策方法决定种哪一种作物。（5分）策略自然状态收益好天气中等天气坏天气A250001800010000A30000120008000A200001600012000解：（1）用不确定型决策方法d“ij等可能准则：max -max 17666,16666,16000 176

15、66n乐观准则：maxmaxdjmax 25000,30000,2000030000* A2悲观准则：maxmin dq max 10000,8000,12000 12000二 * A3后悔值准则：500002000后悔值矩阵为：D0600040001000020000则 min max diq min 5000,6000,100005000j* A1（2）用风险型决策方法（最大期望收益）的决策树为：好天气0.3177001177002AiA2162003A3160004中等天气0.4坏天气0.3好天气0.3中等天气0.4坏天气0.3好天气0.3中等天气0.4坏天气0.3 25000 1800

16、0 10000 30000 12000 8000 20000 16000 12000* A , E(A1)17700（答题毕）2003 级(B)参考答案1. 证明，若线性规划问题有两个不同的最优解，则它有无穷多最优解。(10分)证明：设X、X(2)是线性规划问题:min ZCX, AX b,X 0的两个不同最优解，则有CX(1)CX*ZAXb , AX b从而，对(01)有:A X(1)b，A(1)X(2) (1)b两式相加有：AX(1)(1)X(2)X(1)(1)b b由此可知X(1)X(2)0是线性规划问题的可行解。而 C x(1)(1)XCX(2) * * *(1)CX ()Z (1)Z

17、 Z所以X (：1)(1)X (01)也是线性规划问题的最优解。故线性规划问题有无穷多最优解。2. 有甲、乙、丙三种类型的煤，每种煤的含硫量、发热量及价格如下表。现将三种煤混合使用，混合后要求每公斤煤的发热量不低于21X4.19 X10 3J，含硫量不超过0.025%，问如何混合才能使成本最低？试建立其数学模型(10 分)类型含硫量(%发热量(4.19 X10 3J/kg )价格(元/t )甲0.012020乙0.052416丙0.032218.5解：设每吨混合煤分别使用甲、乙、丙三种煤x1, x2 ,x3吨，混合煤的成本为 乙则有： min z 20x116x218.5x3s.t. 0.01

18、x10.05x20.03x30.02520x124x222x321X1,X2,X303. 某一极小化线性规划问题在单纯形法计算时得到下表，其中a，b，c，d，e，f是未知数，原问题中要求各变量均非负，问a, b, c, d, e, f应满足什么条件，有下面各解成立？( 10分)XbX1X2X 3X4X5X 6bX32c1 0e0fX4-1-50 1 -102Xa-300-413(T jbd0030(1) 是唯一最优解；(2) 有无穷多最优解；(3) 无界解；(4) 是可行解但非最优解，只有 X1可以进基且出基变量必为第 3个变量。解：(1)当现行解为可行解，且对应的非基变量的检验数均大于0时，

19、LP问题才有唯一最优解，即 f 0, b0, d0。X3,X4, X6非人工变量； a, c, e无限制。(2) 当所有非基变量的检验数都大于等于0，且其中存在一个非基变量 为检验数等于0,而在x的系数列向量中有大于 0的分量时，有无穷多最优解。所以f 0,b=0,d0或f 0,b 0,d=0,c0。X3,X4,X6非人工变量；a,e无限制。(3) 当f 0时现行解为基可行解，当 b0, d 0, c0, b 0, d0, c 0;非最优解且只有 X1可以进基，所以有b 0;只有X6可以出基，所以有2 a故参数应满足：f 3f 0, b 0, d0,。x3, X4, X6非人工变量；c, e无

20、限制。2 a4.分别用图解法和单纯形法求解线性规划问题，并对照指岀单纯形法的每步迭代相当于图解法中可行域的哪一个顶点解：用图解法有:（20 分）max z2x.|X2s.t.X233x1X212X1X25X10, X20X25,4A32xi+x =5D0Cx*=（7/2,3/2）3xi+x =125 x17 3（2,2）17用表格单纯形法求解有:原模型标准化为： mi n z2x1 x2S.t.X2 X33x-iX2X4312X55X1X2X1,X2,X3,X4,X5Cj-2-1000bCBXbX1X2X3X4X50X30110030X43*1010120X5110015-2-100000X3

21、011003-2X 111/301/304-1X502/3*0-1/31160-1/302/30-80X30011/2-3/23/2-2X21001/2-1/27/2-1X1010-1/23/23/20 0 0 1/2 1/2-17/2*7 3 t *17所以：X(-,3)T ； Z 2 2 2其中：表一对应图中 0点；表二对应图中 D点；表三对应图中 C点5.写出求解整数规划(max型)的分枝定界法的基本方法步骤。(10 分)解：求解整数规划(max型)的分枝定界法的基本方法步骤有：(1) 求解原问题的松弛问题，即不考虑整数约束的线性规划问题；(2) 定界，一般令Z为松弛问题的目标函数值，Z

22、为无穷大或明显的整数解的目标函数值;Z的问题适时剪掉，不再进行分枝;Z，将迄今为止所有未被分枝的问题的目标函数值(3) 分枝，选非整数解变量进行分枝，用两个线性规划问题同效表示一个线性规划问题；(4) 求解并剪枝，求解分枝问题，对无解的问题或目标函数值小于(5) 调整上、下界，将迄今为止最好的整数解对应的目标函数值作为作为Z ；(6) 当所有分枝均已查明，有Z = z时，即得到原问题的最优解,Z*Z Z，求解过程结束。6.判断下述函数的凹凸性：4X1X322X2X34X；2X3(10 分)2x1 4x2 4x3f (X) 2X1X20解:因H(x)222 ；42202402|有:an =0 ；

23、A=-4 v 0；A=222=-8 v 022422即函数的海赛矩阵为不定矩阵，故f(X) 为非凸非凹函数。7. 写岀建立动态规划求解模型的基本步骤。(10分)解：建立动态规划求解模型的基本步骤为：(1) 按问题内容划分阶段，K= (1，2,，n), k=n为终了阶段；(2) 确定状态变量xk和允许状态集合用；(3) 确定决策变量uk和允许决策集合U;(4) 写出状态转移方程：xk 1 Tk (xk ,u k )；(5) 明确阶段指标dk(Xk,Uk)；(6) 确定递推方式和递推方程，如逆推方程为：fk(Xk) max dk(xk,Uk) fk1(Xk1)uk Uk(7) 明确边界条件，如 f

24、n(Xn) 0，或fn(Xn) 1等。8. 根据市场预测，某企业其产品的需求量可能为100、150、200或250万t，产品生产成本为 25元/t，而售价为35元/t假设产品生产后不能外销其价值为零，要求：专业技术资料（1）写出该问题的益损值表；（10分）（2 ）分别用等可能准则、乐观准则、悲观准则、后悔值准则，确定企业最优生产数量（10 分）解：（1）根据题意该问题的益损值表为：ijd 等可能准则： max -max 1000,1062.5,687.5, 125 1062.5乐观准则： max max dij max1000,1500,2000,25002500n1000,250,1500,

25、275010000500100015001250050010002500125005003750250012500悲观准则： maxm.in dijmax后悔值准则：后悔值矩阵为：D则 min max dH min 1500,1250,2500,37501250j（答题毕）2用图解法求解max z 2.5x1X2s.t.3x15x2155x12x210X10, X20解：用图解法有:(10 分)Xi2004 级(A)1将线性规划问题max z3x1X22X3s.t.2x1X2X344x1x3x383x12x2X39Xi0：,X20,X3为自由变量化为标准型。（10 分）解：原模型标准化为：mi

26、n z3x1X22X32x3s.t.2x1X2X3X3X444x1X23X33x383x12x2X3X3X59Xi,x：2X3,X3,X4,X50该问题有无穷多最优解5x12x210*T*联立0解得X(2,0)；Z5X2联立5x12x210*2045 t解得X(,)；Z53x15x2151919亠- *220/190所以 X(1)1 ； Z 5045/193用单纯形法求解maxzx1 2x2 x3s.t.X1X22X3X4102x1X24X38X12X24X34Xj0 (j1,2,3,4)（15 分）解：原问题标准化为min zX12X2X3s.t.X1X22X3X4102x1X24X3X58

27、X12X24X3X64Xj0 (j1,234,5,6)用表格单纯形法求解有(15 分)C1-21000bCBXbX1X2X3X4X5X60X411-2100100X52-1401080X6-12-40014o j1-2100000X43/20010-1/280X53/202011/210-2X2-1/21-2001/22o j00-3001-40X43/20010-1/281X33/40101/21/45-2X211001112o j9/40003/27/4-19所以有：X*=(Xi,X2,X3,X4,X5,xjT=(0,12,5,8,0,0)t; Z *=-19还原为原问题有：X*=(0,1

28、2,5,8)t; Z*=194用对偶单纯形法求解线性规划问题：min zX1x2st.2x1 x24解：用对偶单纯形法求解有：x1 7x2x-i , x207C1100bCBXbXiX2X3X40X3-2-110-40X4-1-7*01-7o j110000X3-13/7*01-1/7-31X21/710-1/71o j6/7001/711Xi10-7/131/1321/131X2011/13-2/1310/13o j006/131/1331/13规划问题最优解为X *=(21/13 , 10/13) t; Z*=31/135用隐枚举法求解下列 0-1规划问题min z2x15x23x34x4s.t.4x1X2X3X402x14X22x34x44X1X2X3X41X1,X2,X3,X40或 1。（10 分）解：将原问题变量重新排列有：min z5x24x43x32x1s.t.X2X4X34x104x24x42X32x-i4X2X4X3X11X2,X4,X3,X10或 1。枚举过程如下表:序号X=(X2, X4, X3,x 1)t阀值约束1约束2约束3目标函数