广工09运筹学(A)试题及答案

广东工业大学期中考试试卷（A）课程名称： 运筹学 考试时间：第十六周星期二（12月17日）题号-一一-二二三四五六七八九十总分评卷得分一、单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确答案的字母写这答题纸上。（10分，每小题2分）1、 使用人工变量法求解极大化线性规划问题时，当所有的检验数b<0，在j基变量中仍含有非零的人工变量，表明该线性规划问题（）有唯一的最优解；B.有无穷多个最优解；C.无可行解；D.为无界解2、 对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（）A.b列元素不小于零 B.检验数都大于零C.检验数都不小于零 D.检验数都不大于零3、 在产销平衡运输问题中，设产地为m个，销地为n个，那么基可行解中非零变量的个数（）A.不能大于（m+n-1）；B.不能小于（m+n-1）；C.等于（m+n-1）；D.不确定。4、如果要使目标规划实际实现值不超过目标值。则相应的偏离变量应满足艾A.d+>0 B.d+=0 C.d-=0 D.d->0,d+>05、下列说法正确的为（）如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解如果线性规划的对偶问题无可行解，则原问题也一定无可行解在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解

二、判断下列说法是否正确。正确的在括号内打“V”，错误的打“X”。（18分，每小题2分）TOC\o"1-5"\h\z1、 如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ）2、 单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 （）3、任何线性规划问题存在并具有惟一的对偶问题。 （ ）4、 若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。（）5、 运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。 （ ）6、 如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数k，最有调运方案将不会发生变化。 （ ）7、目标规划模型中，应同时包含绝对约束与目标约束。 （ ）8、线性规划问题是目标规划问题的一种特殊形式。 （ ）9、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（ ）三、解答题。（72分）maxz=3x+3x121、（20分）用单纯形法求解■<X1+X2<41、（20分）用单纯形法求解■<一x+x<2126x+2x<1812x>0,x>012c2c2的变化范围；⑵若右边常数向量变为B二5220，分析最优解的变化。（15分）已知线性规划问题:maxz=x+2x+3x+4x12 3 4”x+2x+2x+3x<20J2X+x+3x3+2x<20

I1 2 3 4-XXXX>0I 1'2'3'4—其对偶问题最优解为Y二1.2,Y二0.2，试根据对偶理论来求出原问题的最优解。12

3、（15分）用表上作业法求下表中给出的运输问题的最优解。销地产地甲乙丙丁产量I327650II752360III254525销量604020154、（12分）求下表所示效率矩阵的指派问题的最小解,'、、工作工人'、、、ABCDE甲127979乙89666丙71712149丁15146610戊14107109minz=x+1.5x12/八、er、rr、—S..X+3x>35、（10分）用大M法求解4 1 2x+x>2

12x>0,x>0v12广东工业大学期中考试试卷参考答案及评分标准（A卷）课程名称:运筹学课程名称:运筹学考试时间:单项选择题：1-5CDABD2009年12月17日（第16周星期四）考试时间:单项选择题：1-5CDABD2009年12月17日（第16周星期四）（每题2分）二、判断题:二、判断题:6-10XXVXV（每题26-10XXVXV三、解答题：1、解：加入人工变量，化问题为标准型式如下：maxz=3x+3x+0x+0x+0xTOC\o"1-5"\h\z1 2 3 4 5x+x+x=41 2 3—x+x+x=2 （3分）s.“ 1 2 46x+2x+x=181 2 5x,x,x,x,x>0V1 2 3 4 5下面用单纯形表进行计算得终表为：cj33000CB基bx1x2x3x4x50x3102/310-1/60x4504/3011/63x1311/3001/6czj-j0000-1/2TOC\o"1-5"\h\z（5分）所以原最优解为X*=（3,0,1,5,0）t （2分）

I459II44III31138销量35463（5分）用位势法检验得：销地产地甲乙丙丁戊UIQ450IIQ4Q30Q-9III31131V019593所有非基变量的检验数都大于零，所以上述即为最优解且该问题有唯此时的总运费：minz二4x5+5x9+4x10+3x1+1x20+1x10+3x4二14、解:系数矩阵为：「12 7 9 7 9_8 9 6 6 67 17 12 14 915 14 6 6 10[4 10 7 10 9 _（3分）「5 0 2 0 22 3 0 0 0从系数矩阵的每行元素减去该行的最小元素，得：0 10 5 7 29 8 0 0 40 6 3 6 5（7分）最优解。50。（2分）

"702"702430经变换之后最后得到矩阵：0831180_041-01000-00010相应的解矩阵：0000100100_10000_0200500443（13分）由解矩阵得最有指派方案：甲一B,乙一D,丙一E,丁一C,戊一A或者甲一B,乙一C,丙一E,丁一D,戊一A （2分）所需总时间为：Minz=32所需总时间为：Minz=32（2分）5、解：将问题标准后，构造辅助为：minz=x+1.5x+M(x+x)TOC\o"1-5"\h\z1 2 5 6s.tx+3x-x+x=3V 1 2 3 5x+x-x+x=212 4 6x>0, ,x>0J1 6以x,x为初始基变量，列单纯形表计算如下:5 6cj11.500MMCB基bx1x2x3x4x5x60x5313-10103x62110-101czj-j1-2M1.5-4MMM000x211/31-1/301/30

0x612/301/3-1-1/31czj-