运筹学试卷及答案

运

筹

学

考

卷

考试时间: 第 十六 周 题 一 二 三 四 五 六 七 八 九 十 分 总学 院： 专 业： 学 号： 姓 名： 号 评卷得分 一、 单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确答案的字母写这答题纸上。（10分, 每小题2分） 1、使用人工变量法求解极大化线性规划问题时，当所有的检验数j0，在基变量中仍含有非零的人工变量，表明该线性规划问题（ ） A. 有唯一的最优解； 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0 5、下列说法正确的为（ ） A．如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解 B．如果线性规划的对偶问题无可行解，则原问题也一定无可行解 C．在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数 D．如果线性规划问题原问题有无界解，那么其对偶问题必定无可行解

二、判断下列说法是否正确。正确的在括号内打“√”，错误的打“×”。（18分，每小题2分） 1、如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。（ ） 2、单纯形法计算中，如不按最小比列原则选取换出变量，则在下一个解中至少有一个基变量的值为负。 （ ） 3、任何线性规划问题存在并具有惟一的对偶问题。 （ ） 4、若线性规划的原问题有无穷多最优解，则其最偶问题也一定具有无穷多最优解。 （ ） 5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有惟一最优解，有无穷多最优解，无界解，无可行解。 （ ） 6、如果运输问题的单位运价表的某一行（或某一列）元素再乘上那个一个常数k，最有调运方案将不会发生变化。 （ ） 7、目标规划模型中，应同时包含绝对约束与目标约束。 （ ） 8、线性规划问题是目标规划问题的一种特殊形式。 （ ） 9、指派问题效率矩阵的每个元素都乘上同一常数k，将不影响最优指派方案。（ ） 三、解答题。（72分） maxz3x13x2x1x24分）用单纯形法求解x1x226x2x1812x10,x201、（20；并对以下情况作灵敏度分析：（1）

5求c2的变化范围；（2）若右边常数向量变为b2，分析最优解的变化。 202、 （15分）已知线性规划问题： maxzx12x23x34x4x12x22x33x420 s..t2x1x23x32x420x1,x2,x3,x40其对偶问题最优解为y11.2,y20.2，试根据对偶理论来求出原问题的最优解。

3、 （15分）用表上作业法求下表中给出的运输问题的最优解。 销地 甲 产地 Ⅰ Ⅱ Ⅲ 销量 4、（12分）求下表所示效率矩阵的指派问题的最小解， 工作 工人 甲 乙 丙 丁 戊 乙 2 5 5 40 丙 7 2 4 20 丁 6 3 5 15 产量 50 60 25 3 7 2 60 A B C D E 12 8 7 15 14 7 9 17 14 10 9 6 12 6 7 7 6 14 6 10 9 6 9 10 9 minzx11.5x2s.t.x3x3125、（10分）用大M法求解 xx212x10,x20

参考答案及评分标准 ( A卷 ) 课程名称: 运筹学 考试时间: 2 (第 16周 一、单项选择题： 1-5 CDABD （每题 2 分） 二、判断题： 1-5 √√√√× 6-10 ××√×√ （每题 2 分） 三、解答题： 1、解： 加入人工变量，化问题为标准型式如下： maxz3x13x20x30x40x5x1x2x34xxx2124s.t6x12x2x518x1,x2,x3,x4,x50(3分) 下面用单纯形表进行计算得终表为： cj CB 3 3 x2 0 x3 0 x4 0 x5 基 x3 b 1 x1 0 0 2/3 1 0 -1/6 0 x4 5 0 4/3 0 1 1/6 3 x1 3 1 1/3 0 0 1/6 cjzj 0 0 0 0 -1/2 （5分） 5、解：将问题标准后，构造辅助为： minzx11.5x2M(x5x6) s..tx13x2x3x53x1x 2x4x62x10,,x60以x5,x6为初始基变量，列单纯形表计算如下： c1.j 1 0 0 M M 5 CB 基 b x1 x2 x3 x4 x5 x60 x5 3 1 3 -1 0 1 0 x-3 6 2 1 1 0 0 1 1 c1-21.jzj M M 0 0 M 5-4M 0 x2 1 1/3 1 -1/3 0 1/3 0 -0 x6 1 2/3 0 1/3 -1/3 1 1 c0.5-0.54M/jzj 0 M 0 2M/3 -M/3 3-0.5 11-0 x20 1 -1/2 1/2 /2 /2 1/2 x3-33 1 1 0 1/2 -1/2 /2 3/2 /2 c3M-1/Mjzj 0 0 1/4 /4 4 -3/4 由于所有系数都为正，所以此为最优解，x3/21/20000 最优目标函数值为：z9/4。