运筹学期中考试试卷

1、大连大学2010/2011 学年第一学期期中考试卷考试科 目： 运 筹 学（考试时间90分钟）（共4页）题号一一总得分121234得分、用图解法求解（10分） 给定下述线性规划问题：max zx12x24x13x23x1x23x1,x2 0画出其可行域并找出其最优解。 解：可行域：适用专业工程管理适用年级08考试形式闭 卷送卷单位任课教师教研室主任最优解为（3,0）,z 3.、模型转换（10分）写出下列线性规划问题的对偶问题23min zCj %i 1 j 1教学院长X1x12x13七4a1x21x22x23x24a2x11x21bix12x22b2x13x23b3“4x24b4一 gJxij

2、0解： max w a1u1 a2u2 b1V1 b2v2 b3v3 b4v4U1V1c11U1v2c12U1v3c13U1v40U2v1c21U2v2c22U2v3c23U2v40u1,u2,v1, v2,v3, v4 无符号限制三、计算题（每小题20分，共80分）1.用单纯形法求解下列线性规划问题（列出计算过程）。 min z3x1 5x2Xi8x1 x3 8解：标准化：2x2 x4 123x1 4x2 x5为“2,乂3,人？5变量变量，第二步标准化2x2 12 3x1 4x2 36 x1,x2 0 MaxW3x1 5x2 0% 0x4 0x5（标准化可分两段，第一步把决策 36 0）列单

3、纯形表计算：基Cb-3-5000bXXX3X41头Xa0-101008X400-201012X0-3-4P 001136cjzj-3-5000最优解 X= (3, 5, 0, 0,0) T,最优值 W=34，故 Z=-342 .用单纯形法中两阶段法求解下述线性规划问题（列出计算过程）。（注意步骤,区分人工变量与松驰变量）min z 4x1 x23xi X234x1 3x2 X36x1 2x2 x44x 0,i 1,2,3,4解：1）标准化； max z4x1 x23x1 x2 3（1）4x1 3x2 x3 6（2）x1 2x2 m 4x 0,i 1,2,3,42）在上约束方程组（1）、（2）中

4、加入人工变量，列出第一阶段线性规划问题 将正文中的问题化成标准型：min w x5 x63x1 x2 4 34K 3x2 & 凡 6x1 2x2 刈4x 0,i 1,2,3,4,5,6max z3）列出上述线性规划问题的初始单纯形表，并求解基CB0000-1-1bXX?X3X4X5X6X-13100103X6-143-10016X401P 201004cjzj74-1000X1011/3001/301&-105/3-10-4/312X4005/301-1/303cjzj0r 5/310-7/30X10101/503/5-1/53/5X2001-3/50-4/53/56/5X40

5、0r 0111-11cjzj0000-1-14）因为第一阶段目标函数值为0,做去掉人工变量，写出第二阶段目标函数为4x1 x2 0x3 0x4,继续用单纯形法求解基CB-4-100bXX>X3X X1-4101/503/5 1X2-101-3/506/5X400r 01 11 1 1cjzj001/510X1-4100-1/52/5X2-10r 10 3/59/5：X3000111 1cjzj000-1/52 917故有唯一最优解 X (-,-,1,0,0,0), Z 5 553 .用对偶单纯形法求解下述线性规划问题（列出计算过程）。（此问题不是加人工 变量，而是根据对偶理论，在保持对偶

6、问题为可行解的基础上，通过迭代，使原 问题也达到可行解，即得到了目标函数的最优解。）min z 4x1 12x2 18x3x1 3x32x2 2x3Xi,X-,X3解：先将问题改写为:max w 4x1 12x218x3 0x4 0x5X 3x3 x4 32x2 2x3 x5 5x 0,i 1,2,3,4,5约束条件两端乘“ -1 ”得:max w4x1 12x218x3 0x4 0x53x3 x4cj-4-12-1800CB基bx1x-X3x4x50x4-3-10-3102x22x3x5xi0,i 1,2,3,4,50X5-50-2-201Cj Zj-4-12-18000X4-3-10-31

7、0-12X25/20110-1/2cj zj-40-60-6-18X311/301-1/30-12X23/2-1/3101/3-1/2cj zj-200-2-6X=(0 3/2 1 0 0), minz=364 .已知某运输问题的产销数量表与单位运价表如表4-1 ,用表上作业法求最优解（列出计算过程）。表4-1、销地AiA2A 3A4入户 J里B291079B213425B384257销量3846解：1.|最小元素法的初始方案肖地AiA 2A3A4入户 J里B549B2325B3347销量3846位势法检验:B1B2B3B4A1(-4)9375A21(-1)(2)20A342(3)01422（注：括弧中的数位检验数，下同）闭回路法调整（调整结果与Vogel法的初始方案一致）产地.一一_销地B1B2B3B4）里A13519A255A3347销量38462. Vogel法的初始方案:产地一一站地B1B2B3B4）里A13519A255A3347销量3846位势法检验:地 销地B1B2B3B4A129(0)71A2(4)(-1)(2)2-4A3(11)42(3)-41866闭回路法调整:产地- 一'期地.一B1B2B3B4）里A1369A2505A3347销量3846位势法检验:地 销地B1B2B3B4A12(1)(4)71A2(4)3(3)2-4A3(10)42(2)-31