运筹学试题及答案

1、毕节学院考试试卷A 考试时间:第十九周星期三7月9日题号一二三四五六七八九十总分评卷得分一、单项选择题。以下每题给出的四个答案中只有一个是正确的，将表示正确答案的字母写这答题纸上。10分，每题2分1、使用人工变量法求解极大化线性规划问题时，当所有的检验数j 0，在基变量中仍含有非零的人工变量，说明该线性规划问题A.有唯一的最优解；B.有无穷多个最优解；C.无可行解；D.为无 界解2、对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中A . b列元素不小于零B .检验数都大于零C .检验数都不小于零D .检验数都不大于零3、 在产销平衡运输问题中，设产地为m个，销地为n个，那么基可行解中

2、非零变量的个数2、单纯形法计算中，如不按最小比列原那么选取换出变量，贝y在下一个解中至少 有 一 个 基变量 的 值 为 负( )3、任何线性规划问题存在并具有惟一的对偶问题( )4、假设线性规划的原问题有无穷多最优解，那么其最偶问题也一定具有无穷多最 优解。( )5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现以下四种 情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解( )6、如果运输问题的单位运价表的某一行(或某一列)元素再乘上那个一个常数 k ， 最有调运方案将不会发生变化( )7、 目标规划模型中，应同时包含绝对约束与目标约束。()8、线性规划问题是目标规划问题的一

3、种特殊形式( )9、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。三、解答题。72 分max z3 x13x21、20分用单纯形法求解XlX24；并对以下情况作灵敏度分析:XiX226 x12 x218X10, X20(1)求C2的变化范围；2假设右边常数向量变为b52 ，分析最优解的变化202、 15分线性规划问题:maxzX12x23x34x42x22X33x420st 2为X23x32x420XpX2,X3，X40其对偶问题最优解为yi 1.2, y2 0.2，试根据对偶理论来求出原问题的最优解。3、15分用表上作业法求下表中给出的运输问题的最优解。销地 产地 甲乙丙

4、丁产里I327650n752360出254525销里604020154、 12分求下表所示效率矩阵的指派问题的最小解, 工作 工人、ABCDE甲127979乙89666丙71712149丁15146610戊14107109min z5、10分用大M法求解st. x1Xix11 .5x23x23x220,x20毕节学院期末考试试卷参考答案及评分标准A卷课程名称:运筹学考试时间:7月9日第19周星期三一、单项选择题：1-5 CDABD每题 2 分二、判断题：1-5 WWx 6-10 xxVxV每题 2 分三、解答题:1、解:参加人工变量，化问题为标准型式如下:maxz3% 3x2 0x3 0x4

5、0x5X2 X34s.tX16凶x2 x422x2 x 18,X2,X3,X4,X50(3F面用单纯形表进行计算得终表为:Cj33000CB基bX1X2X3X4X50X3102/310-1/60X4504/3011/63X1311/3001/6Cj Zj0000-1/25分所以原最优解为 X*3,0,1,5,0t2分1 设C2变化，将C2得变化带入最终单纯形表得C2的变化范围为C2 1 ；5分_52假设右边常数向量变为 b 2，将变化带入最终单纯形表得：最优基解不变，最优解的值20由3，0T变为10/3，0To5 分2、解：1该问题的对偶问题为:min w20y120y2Y12y212y1 y

6、225 分s.t 2y13y233y12y24%肆20将yi 1.2, y2 0.2带入约束条件的为严格不等式，由互不松弛性得x； 0, x； 0，因为y,y 0故有：2x3 3x4 203x3 2x4 20 6 分最后求得x*4,x；4最优解：X*0,0,4,4 T 2 分目标函数最优值：z*28 2分3、解：因为销量：3+5+6+4+3=21;产量：9+4+8=21;为产销平衡的运输问题。1分由最小元素法求初始解：销地产地甲乙丙丁戊产里I459n44出31138销量354635 分用位势法检验得:销地产地甲乙丙丁戊UI04500n04000林-9出310131V0195937 分所有非基变

7、量的检验数都大于零，所以上述即为最优解且该问题有唯一最优解。此时的总运费： minz 4 5 5 9 4 10 3 1 1 20 1 10 3 4 150。2 分4、解:系数矩阵为:12797989666717121493 分15146610410710950202从系数矩阵的每行元素减去该行的最小元素，得:2300001057298004063657403经变换之后最后得到矩阵：081180401 00000 010相应的解矩阵：00 00100 10010 000由解矩阵得最有指派方案：甲一B，2 0 20 0 03 5 00 0 41 4 3乙一D,丙一E, 丁一 C,戊一A或者甲一B,乙一C,丙一E, 丁一 D,戊一A2 分13 分5、解：将问题标准后，构造辅助为:minz x 1.5x2 M x5 xjs.tx3x2 x3X53XiX2x4X62Xi0, L,X60以X5, X6为初始基变量，列单纯形表计算如下:Cj100MMCB基bX1X2X3X4X5X60X313-10103X2110-101Cj Zj1-2MMM000X211/31-1/301/300X12/301/3-1-1/31Cj Zj303M