深圳大学期末考试试卷 开闭卷闭卷 AB卷 课程编号22040103、22040605课程名称运筹学 学分 命题人(签字) 审题人(签字) 年月日 题号 三四五|六七八九|十 基本题附加题 总分 得分 评卷人 基本题(100分) 、判断题:(每小题2分,本题20分) (1)线性规划问题的每一个基本解对应可行域的一个顶点。() (2)已知y为线性规划的对偶问题的最优解,若y>0,说明在最优生产计划中第i种 资源已完全耗尽。( 图(3)如果运输问题单位运价表中的某一行(或某一列)元素分别加上一个常数k,最 优调运方案将不会发生变化。( (4)用分枝定界法求解一个极大化的整数规划问题时,任何一个可行解的目标函数值 长 是该问题目标函数值的下界。() (5)在任一图G中,当点集V确定后,树图是G中边数最少的连通图。() (6)在单周期随机存贮模型中,损失期望值最小准则和获利期望值最小准则都可以用 来确定最佳订购量,且结果是一样的 ⑦)当所有产地的产量和销地的销量均为整数值时,运输问题的最优解也为整数值 (8)任何有n个节点n条边的简单图中必存在圈。() (9)在两阶段法中,如果第一阶段最优解的目标函数值不为0,表明原线性规划问题 无可行解。() (10)在其它费用不变的条件下,随着单位存贮费用的增加,最优订货批量也相应增大 橱二、填空题(每空2分,本题共20分) (1)已知5个工厂担任4种任务的费用矩阵如下,问应该如何分配任务,使总费用最 少? 3626 C=6437 5243 :这是一个非平衡的分配问题,首先虚设 用 法求 得其最优分配方案为 总费用为 (2)运输问题求初始基本可行解的方法通常有 两 《运筹学》试卷B卷第1页共5页
《 运筹学 》试卷 B 卷 第 1 页 共 5 页 深圳大学期末考试试卷 开/闭卷 闭卷 A/B 卷 B 课程编号 22040103、22040605 课程名称 运筹学 学分 3 命题人(签字) 审题人(签字) 年 月 日 题号 一 二 三 四 五 六 七 八 九 十 基本题 总分 附加题 得分 评卷人 基本题（100 分） 一、判断题：（每小题 2 分，本题 20 分） （1）线性规划问题的每一个基本解对应可行域的一个顶点。（ ） （2）已知 * i y 为线性规划的对偶问题的最优解，若 0 * yi ，说明在最优生产计划中第 i 种 资源已完全耗尽。（ ） （3）如果运输问题单位运价表中的某一行（或某一列）元素分别加上一个常数 k，最 优调运方案将不会发生变化。（ ） （4）用分枝定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数值 是该问题目标函数值的下界。（ ） （5）在任一图 G 中，当点集 V 确定后，树图是 G 中边数最少的连通图。（ ） （6）在单周期随机存贮模型中，损失期望值最小准则和获利期望值最小准则都可以用 来确定最佳订购量，且结果是一样的。（ ） （7）当所有产地的产量和销地的销量均为整数值时，运输问题的最优解也为整数值 （ ）； （8）任何有 n 个节点 n 条边的简单图中必存在圈。（ ） （9）在两阶段法中，如果第一阶段最优解的目标函数值不为 0，表明原线性规划问题 无可行解。（ ） （10）在其它费用不变的条件下，随着单位存贮费用的增加，最优订货批量也相应增大。 （ ） 二、填空题（每空 2 分，本题共 20 分） （1）已知 5 个工厂担任 4 种任务的费用矩阵如下，问应该如何分配任务，使总费用最 少？ = 5 7 6 2 5 2 4 3 6 4 3 7 7 1 4 4 3 6 2 6 C 这是一个非平衡的分配问题，首先虚设 ，用 法求 得其最优分配方案为： ，总费用为 。 （2）运输问题求初始基本可行解的方法通常有 ， 两 _____________ ________ … 学院 专业 姓名 学号 ( 密 封 线 内 不 答 题 ) … … … …… … …… … …… …… … …… … … … … 密… … …… … …… … …… … …… …… … …… 封 …… … … …… … …… … …… …… … 线… … …… … …… … …… … …… … 线………………………………………
种方法,检验数的判断方法通常用 两种方法。 (3)求图G的最小支撑树常用的方法是 、(25分)已知线性规划问题 max 2=2x1-x2+x x1+x2+x3≤6 st 4 x1,x2,x3≥0 (1)先用单纯形法求出其最优解 (2)写出其对偶问题,求各个约束的影子价格(即对偶问题的最优解); (3)分析在下列条件单独变化的情况下最优解的变化; (a)目标函数变为z=2x1+2x2+x3; b)约束右端项由变为 《运筹学》试卷B卷第2页共5页
《 运筹学 》试卷 B 卷 第 2 页 共 5 页 种方法，检验数的判断方法通常用 ， 两种方法。 （3）求图 G 的最小支撑树常用的方法是 和 。 三、（25 分）已知线性规划问题： − + + + = − + , , 0 2 4 6 . . max 2 1 2 3 1 2 1 2 3 1 2 3 x x x x x x x x st z x x x （1） 先用单纯形法求出其最优解； （2） 写出其对偶问题，求各个约束的影子价格（即对偶问题的最优解）； （3） 分析在下列条件单独变化的情况下最优解的变化； （a） 目标函数变为 2 1 2 2 3 z = x + x + x ； （b） 约束右端项由 4 6 变为 4 5
四、(20分)如下图所示,某人从住处①到工作地⑦上班,图中各弧旁的数字为该弧的长 度(单位:公里)。试问该人应选择哪条线路,使从家出发到工作地的路程最短。用 Dj} stra标号法求解上述问题。(要求写出主要过程) 《运筹学》试卷B卷第3页共5页
《 运筹学 》试卷 B 卷 第 3 页 共 5 页 四、（20 分）如下图所示，某人从住处①到工作地⑦上班，图中各弧旁的数字为该弧的长 度（单位：公里）。试问该人应选择哪条线路，使从家出发到工作地的路程最短。用 Dijkstra 标号法求解上述问题。（要求写出主要过程） 1 2 3 4 5 6 7 0.2 0.5 0.35 0.9 0.25 0.6 0.1 0.3 0.4 0.8 1 2 3 4 5 6 7 1 2 3 4 5 6 7 0.2 0.5 0.35 0.9 0.25 0.6 0.1 0.3 0.4 0.8
五、建模题(10分) 某公司下属三个小型煤矿A,A,A3,每天煤炭的产量分别为a,a,as,供应 B,B2,B3,B1四个工厂,需求量分别为b,b,b3,b4。设这是一个产大于销的问题,且c 为从A产地到B厂的单位运价。公司调运时依次考虑的目标优先级为: P1:A产地因库存限制,应尽量全部调出 P2:因煤质要求,B需求最好由A供应; P3:满足各销地需求 P4:调运总费用尽可能不低于m 试建立该问题的目标规划。(不需求解) 六、证明题(5分) 证明产销平衡的运输问题必有最优解。 《运筹学》试卷B卷第4页共5页
《 运筹学 》试卷 B 卷 第 4 页 共 5 页 五、建模题（10 分） 某公司 下属三 个小 型煤矿 A1,A2,A3,每 天煤炭 的产 量分别 为 a1,a2,a3,供 应 B1,B2,B3,B4 四个工厂，需求量分别为 b1,b2,b3,b4。设这是一个产大于销的问题，且 cij 为从 Ai产地到 Bj厂的单位运价。公司调运时依次考虑的目标优先级为： P1:A1产地因库存限制，应尽量全部调出； P2:因煤质要求，B4需求最好由 A3供应； P3:满足各销地需求； P4:调运总费用尽可能不低于 m 。 试建立该问题的目标规划。（不需求解） 六、证明题（5 分） 证明产销平衡的运输问题必有最优解
附加题(30分) (1)(10分)证明对偶问题的互补松弛性 (2)(12分)已知下面的线性规划问题的最优解为x1=-5,x2=0,x3=-1,用互补松弛性 求其对偶问题的最优解 min -=2 x1-x2+2 x+x2+x3=4 x 6 x1≤0,x2≥0,x3无约束 (3)(8分)上述线性规划问题还有其它解法吗?请写出其中一种方法的基本思路 《运筹学》试卷B卷第5页共5页
《 运筹学 》试卷 B 卷 第 5 页 共 5 页 附加题（30 分） （1）（10 分）证明对偶问题的互补松弛性。 （2）（12 分）已知下面的线性规划问题的最优解为 x1 = −5, x2 = 0, x3 = −1，用互补松弛性 求其对偶问题的最优解。 （3）（8 分）上述线性规划问题还有其它解法吗？请写出其中一种方法的基本思路。 − + − − + + = = − + 1 2 3无约束 1 2 3 1 2 3 1 2 3 0, 0, 6 4 min 2 2 x x x x x x x x x z x x x