1、试卷 A 共（4）页 第（1）页运筹学期末考试试卷(A)学院 班级 姓名 学号 题号 一 二 三 四 五 六 七 八 九 总分得分一、填空题以下是关于目标函数求最大值的单纯行表的一些结论，请根据所表述的意思判断解的情况：1.所有的检验数非正，这时的解是 。2.有一个正检验数所对应的列系数均非正，这时线性规划的解 。3.非基变量检验数中有一个为零时，线性规划的解 。4.在两阶段法中，如果第一阶段的最优表中的基变量中有人工变量，则该线性规划 。6.基变量取值为负时的解为 。7.最优表中的非基变量检验数的相反数就是 。8.已知一个线性规划两个最优解是：（3，2），和（5，9），请写出其他解：9.线性
2、规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。10.在求运费最少的调度运输问题中，如果某一非基变量的检验数为 4，则说明 如果在该空格中增加一个运量运费将增加 4 。11.“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解” ，这句话对还是错？ 错 试卷 A 共（4）页 第（2）页12.如果某一整数规划：MaxZ=X1+X2X1+9/14X251/14-2X1+X21/3X1,X20 且均为整数所对应的线性规划（松弛问题）的最优解为 X1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对 X1进行分枝，应该分为 X11 和 X12 。13.在用逆向解法求动态
3、规划时，f k(sk)的含义是： 从第 k 个阶段到第 n 个阶段的最优解 。14. 假设某线性规划的可行解的集合为 D，而其所对应的整数规划的可行解集合为B，那么 D 和 B 的关系为 D 包含 B 15. 已知下表是制订生产计划问题的一张 LP 最优单纯形表（极大化问题，约束条件均为“”型不等式）其中 X3,X4,X5 为松驰变量。XB b X1 X2 X3 X4 X5X4 3 0 0 -2 1 3X1 4/3 1 0 -1/3 0 2/3X2 1 0 1 0 0 -1Cj-Zj 0 0 -5 0 -23问：（1）写出 B-1= 13/2./(2)对偶问题的最优解： Y（5，0，23，0，
4、0） T 16. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有_某一个非基变量的检验数为 0_；17. 极大化的线性规划问题为无界解时，则对偶问题_ 无解_；18. 若整数规划的松驰问题的最优解不符合整数要求，假设 Xi=bi不符合整数要求，INT（b i）是不超过 bi的最大整数，则构造两个约束条件：XiINT（b i）1 和 XiINT（b i） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。19. 知下表是制订生产计划问题的一张 LP 最优单纯形表（极大化问题，约束条件均为“”型不等式）其中 X4,X5,X6 为松驰变量。XB b X1 X2 X3 X4 X
5、5 X6X1 2 1 1 0 2 0 1试卷 A 共（4）页 第（3）页X3 2/3 0 0 1 1 0 4X5 1 0 -2 0 1 1 6Cj-Zj 0 0 0 -4 0 -9问：(1)对偶问题的最优解： Y(4,0,9,0,0,0) T （2）写出 B-1=6140220. 线性规划问题 MaxZ=CX；AX=b，X 0（A 为 kxl 的矩阵，且 lk）的基的最多个数为_，基的可行解的最多个数为_.21.指派问题的最优解的性质_.22.线性规划问题的所有可行解构成的集合是_,它们有有限个_,线性规划问题的每个基可行解对应可行域的_,若线性规划问题有最优解，必在_得到。23.影子价格的经
6、济含义_.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应_该资源，而当某种资源的市场价格高于影子价格时，则企业应_该资源，可见影子价格对市场有_作用。24. 运输问题的产销平衡表中有 m 个产地 n 个销地，其决策变量的个数有 _个，其数值格有_个二、不定项选择题(每小题 2 分，共 6 分)1线性规划的标准型有特点（ ） 。A、右端项非零； B、目标求最大；C、有等式或不等式约束； D、变量均非负。2一个线性规划问题（P）与它的对偶问题（D）有关系（ ） 。A、 （P）无可行解则（D）一定无可行解；B、 （P） 、 （D）均有可行解则都有最优解；试卷 A 共（4）页 第（
7、4）页C、 （P）的约束均为等式，则（D）的所有变量均无非负限制； D、若（D）是（P）的对偶问题，则（P）是（D）的对偶问题。3关于动态规划问题的下列命题中（ ）是错误的。A、动态规划阶段的顺序与求解过程无关；B、状态是由决策确定的；C、用逆序法求解动态规划问题的重要基础之一是最优性原理； D、列表法是求解某些离散变量动态规划问题的有效方法。4.最早运用运筹学理论的是（ ）A 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署 B 美国最早将运筹学运用到农业和人口规划问题上C 二次世界大战期间，英国政府将运筹学运用到政府制定计划 D 50 年代，运筹学运用到研究人口，能源，粮食，第三世
8、界经济发展等问题上5.下列哪些不是运筹学的研究范围（ ）A 质量控制 B 动态规划 C 排队论 D 系统设计6.对于线性规划问题，下列说法正确的是（ ）A 线性规划问题可能没有可行解 B 在图解法上，线性规划问题的可行解区域都是“凸”区域C 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达D 上述说法都正确7.下面哪些不是线性规划问题的标准形式所具备的（ ）A 所有的变量必须是非负的 B 所有的约束条件（变量的非负约束除外）必须是等式C 添加新变量时，可以不考虑变量的正负性 D 求目标函数的最小值8.在求解运输问题的过程中运用到下列哪些方法（ ）A 西北角法 B 位势法 C 闭回路法
9、D 以上都是试卷 A 共（4）页 第（5）页三、判断题1若某种资源的影子价格等于 k，在其他条件不变的情况下，当该种资源增加 5个单位时，相应的目标函数值将增大 5k 个单位。 （ ）2如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数 k，最优调运方案将不会发生变化。 （ ）3运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解。 （ ）4用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值。 （ ）5如图中某点 有若干个相邻点，与其距离最远的相邻点为 ，则边 必不包iv jv,ij含在最小
10、支撑树内。 （ ）6.用两阶段法求解线性规划时，如果第一阶段的最终表中基变量出现人工变量，则该问题一定无解。【 】7.运输问题一定存在有限的最优解； 【 】8. 如果某种资源的影子价格等于零，说明该种资源一定已经用完 。 【 】9. 单纯形法只适合求解线性规划，对偶单纯形法只适合求解对偶规划 【 】10.分枝定界法求解最大化问题中，如果某个分支的目标值少于已经得到整数解的目标值，则这一分支将被减去而不再往下求解 。 【 】11. 运输问题表上作业法的最优判别标准是所有的检验数应该小于等于 0。【 】试卷 A 共（4）页 第（6）页12.分枝定界法和割平面法一样适用于线性规划的求解 。 【 】1
11、3.如果原规划无可行解，则其对偶规划也必将无可行解 【 】 14.如果原问题最优解的某个分量非零，则其对偶规划对应的约束条件一定是等式【 】15.如果某种资源的影子价格为 4，而该资源的市场价格为 3。则应买进该资源投入生产 【 】16.最优表中如果某个非基变量检验数为零，说明该问题有多重解 【 】17.对偶单纯形法应用的前提是对偶问题可行，原规划不可行 【 】18.线性规划问题的解只有唯一最优解、无解和无界解几种情况 【 】19.连通且有 n-1 条边的图一定是树 【 】20.线性规划原问题和对偶问题都有可行解，则该线性规划问题一定有唯一最优解 【 】21.运输问题表上作业法的最优判别标准是
12、所有的检验数应该大于等于 0。 【 】22.用两阶段法求解线性规划时，如果该线性规划问题存在最优解，则第一阶段最终表中的基变量中一定不会出现人工变量。 【 】23.求解整数规划的分枝定界法中的“定界”的目的是加快解的搜索速度。【 】24. 用闭回路法计算的检验数如果等于 3，表明沿该闭回路调整一个单位运量可以节约 3 个单位成本。 【 】试卷 A 共（4）页 第（7）页四、表中给出的是某极大化问题的单纯型表，试根据下面的问题，确定表中的值或取值范围。（1） 计算 a2的值。（2） 计算目标函数值。（3） 已知 初始，求 d 的值。（4） 该线性规划问题具有无界解，则 a1, C1的取值范围是多
13、少？（5） 表中解为无穷多最优解之一，则表中 C1等于多少？（6） 写出对偶规划的解和第二种资源的影子价格。表 12 1 3 0 0 0CB XB x1 x2 x3 x4 x5 X62 X1 4 1 -5 0 0 2 a23 X3 1 0 -7 1 0 1 00 X4 d 0 a1 0 1 0 4 j 0 C1 0 0 -4 -2五、考虑下列线性规划： 3,21,0 445max1321jxxzj其最优单纯形表为：试卷 A 共（4）页 第（8）页BCBXb1x2x3x4x50 4x6 2 0 -1 1 -25 24 1 1 1 0 1-Z -20 -2 0 -4 0 -51、写出此线性规划的最
14、优解、最优值；2、求线性规划的对偶问题的最优解；3、试求 在什么范围内，此线性规划的最优解不变；2c4、若 变为 9，最优解及最优值是什么？1b例：设线性规划max123064zx123,50,0,.ix求：1.最优解;2.确定 的范围,使最优解不变; 取 ,求最优解;123c3506c3.确定 的范围,使最优基不变, 取 求最优解;b1,b4.引入 求最优解;774,8TxPc解 1.由单纯形方法得试卷 A 共（4）页 第（9）页123456456416216001102630403140526100805526331210048233xxxcxxxx即,原问题的最优解为 1020,.TXz2.因 为非基变量,故当 时,即 时, 最优解不变;3x38c3c为基变量 ,由公式,当 最优解不变, 即12, 1245,4时,最优解不变.2650c现对 最优解改变,此时 原最优表为363815,3试卷 A 共（4）页 第（10）页123456216213060120320634010523257016471002524531xxxcxxxx即相应的最优解为 17,.6TXz3.此时 15203321,600Bb得 最优基不变.即123405,04,1,bbb最优基不变.360当 最优解改变 ,此时1,
