运筹学计算题复习

运筹学计算题复习运筹学计算题复习一、第一章线性规划及单纯形法1、 下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，为参数，（1） 试完成该表；（2） 若该表中所示的21, xx为问题的最优基，试求的取值范围jC2 1 -4 BcBxb 1x2x3x4x1x3 1 0 1 -1 2 2x1 0 1 -1 0 jjzc0 0 解：jC2 1 -4 BcBxb 1x2x3x4x1x3 1 0 1 -1 2 2x1 0 1 -1 0 jjzc0 0 3--4 432、 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。Max43217432xxxxz0,,,37628432..432143214321xxxxxxxxxxxxts解：在第二个约束条件两边乘以-1 ，变为标准形式Max43217432xxxxz0,,,37628432..432143214321xxxxxxxxxxxxts1x 的系数列向量121p， 2x 的系数列向量232p， 3x 的系数列向量613p；4x 的系数列向量744p（1） 因为21, PP线性独立，令非基变量0,43 xx得2121xx基本可行解8,0,0,2,11)1(ZXT（2） 因为31, PP线性独立，令非基变量0,42 xx得131413451xx基本解TX0,1314,0,1345)2(（3） 因为41, PP线性独立，令非基变量0,32 xx得5753441xx基本可行解5117,57,0,0,534)3(ZXT（4） 因为32, PP线性独立，令非基变量0,41 xx得167164532xx基本可行解16163,0,167,1645,0)4(ZXT（5） 因为42, PP线性独立，令非基变量0,31 xx得297296842xx基本解TX297,0,2968,0)5(（6） 因为43, PP线性独立，令非基变量0,21 xx得3145316843xx基本解TX3145,3168,0,0)5(比 较 最 大 值431,,ZZZ可 知51173Z为 最 大 值 ， 故 最 优 解 为5117,57,0,0,534)3(ZXT3、 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相应于图形上哪一个顶点？Max212xxz S.T.0,24261553212121xxxxxx解：（ 1）图解法，作图如下图所示，由图得唯一最优解TX)43,415(*，对应于图上的点为2A ，其最优值为433*z。155321xxX1 X2 A3A2A1242621xx（2） 单纯形法，引入松驰变量0,43 xx，标准型为Max212xxz S.T.0,,,242615534321421321xxxxxxxxxx用单纯形法列表，求解过程见下表jC2 1 0 0 iBCBXb1x2x3x4x0 3x15 3 5 1 0 5 0 4x24 6 2 0 1 4 j2 1 0 0 0 3x3 0 4 1 -1/2 3/4 2 1x4 1 1/3 0 1/6 12 j0 1/3 0 -1/3 1 2x3/4 0 1 1/4 -1/8 2 1x15/4 1 0 -1/12 5/24 j0 0 -1/12 -7/24 因为4,3,2,10 jj...