深圳大学期末考试试卷 开闭卷闭卷 AB卷 课程编号22040103、22040605 课程名称运筹学 学分 命题人(签字) 审题人(签字) 年月日 题号 三四五|六七八九|十 基本题附加题 总分 得分 评卷人 基本题(100分) 一、判断题:(每小题2分,本题共20分) (1)基本可行解中的非零变量的个数小于约束条件数时,该问题可求得退化解() (2)若x,是一个非基变量,则x,的检验数必定不是0。() 写(3)如果运输问题单位运价表中的某一行(或某一列)元素分别乘上一个常数k,最 优调运方案将不会发生变化。() (4)求图的最小支撑树以及图中一点到另一点的最短路问题,都可以归结为求解整数 长 规划问题。( 5)用分枝定界法求解一个极大化的整数规划问题,当得到多于一个可行解时,通常 可任取其中一个作为下界,再进行比较剪枝。() (6)在报童问题中,报童每天总的损失期望值为报纸售剩而遭到的损失期望值与因失去 销售机会而少赚钱的损失期望值之和() 字:(7)指派问题数学模型的形式与运输问题十分相似,故也可以用表上作业法求解。() (8)若图T是树,则T中任意两点有唯一连相连。() (9)在其它费用不变的条件下,随着单位存贮费用的增加,最优订货批量也相应增大。 (10)在大M法的目标函数中,人工变量的系数为任意大的正数M。() 、填空题(每空2分,本题共20分) (1)下表给出运输问题的产销平衡表及运价 销地 价(元/吨 BI B B,产量(吨) 15 A 18 8 A 销量(吨) 求使运费最小的方案可用 方法求解。首先用伏格尔法求初始调运方案, 数字格为 ,此时,空格处的检 验数为 再用 方法调整得最 《运筹学》试卷A卷第1页共5页
《 运筹学 》试卷 A 卷 第 1 页 共 5 页 深圳大学期末考试试卷 开/闭卷 闭 卷 A/B 卷 A 课程编号 22040103、22040605 课程名称 运筹学 学分 3 命题人(签字) 审题人(签字) 年 月 日 题号 一 二 三 四 五 六 七 八 九 十 基本题 总分 附加题 得分 评卷人 基本题（100 分） 一、判断题：（每小题 2 分，本题共 20 分） （1）基本可行解中的非零变量的个数小于约束条件数时，该问题可求得退化解（ ） （2）若 j x 是一个非基变量，则 j x 的检验数必定不是 0。（ ） （3）如果运输问题单位运价表中的某一行（或某一列）元素分别乘上一个常数 k，最 优调运方案将不会发生变化。（ ） （4）求图的最小支撑树以及图中一点到另一点的最短路问题，都可以归结为求解整数 规划问题。（ ） （5）用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常 可任取其中一个作为下界，再进行比较剪枝。（ ） （6）在报童问题中,报童每天总的损失期望值为报纸售剩而遭到的损失期望值与因失去 销售机会而少赚钱的损失期望值之和（ ） （7）指派问题数学模型的形式与运输问题十分相似，故也可以用表上作业法求解。（ ） （8）若图 T 是树，则 T 中任意两点有唯一连相连。（ ） （9）在其它费用不变的条件下，随着单位存贮费用的增加，最优订货批量也相应增大。 （ ） （10）在大 M 法的目标函数中，人工变量的系数为任意大的正数 M。（ ） 二、填空题（每空 2 分，本题共 20 分） （1）下表给出运输问题的产销平衡表及运价： 销 地 运价（元/吨） 产地 B1 B2 B3 产量（吨） A1 15 18 22 8 A2 21 25 16 7 销量（吨） 4 5 6 求使运费最小的方案可用 方法求解。首先用伏格尔法求初始调运方案， 数字格为 ，此时，空格处的检 验数为 ，再用 方法调整得最 _____________ ________ … 学院 专业 姓名 学号 ( 密 封 线 内 不 答 题 ) … … … …… … …… … …… …… … …… … …… … 密… … …… … …… … …… … …… …… … …… 封 …… … … …… … …… … …… …… … 线… … …… … …… … …… … …… … 线………………………………………
优方案为 _,最小运费为 (2)指派问题属于 问题,可以用 方法求解,当任务数比人数少 时,可以采取 方法处理。 (3)在图中找一条经过每边的最短路问题是 、(25分)某车间生产甲、乙、丙三种产品,每件所消耗劳动力、原料及可供使用资源 量如下表: 单位产品消耗资源量产品甲。产品乙。产品乙现有资源量 劳动力 6 45(单位) 原料 30(单位) 单位产品利润(元)3 (1)用单纯形法确定使总利润达到最大的生产计划。 (2)分别求出劳动力和原材料的影子价格。 (3)若产品乙的单位利润变为2元,其它条件不变,原最优计划是否发生改变? (4)若原材料不够,可到市场上购买,市场价格为0.8元/单位,问是否要购进,最多 购进多少? 运筹学》试卷A卷第2页共5页
《 运筹学 》试卷 A 卷 第 2 页 共 5 页 优方案为 ，最小运费为 。 （2）指派问题属于 问题，可以用 方法求解，当任务数比人数少 时，可以采取 方法处理。 （3）在图中找一条经过每边的最短路问题是 。 三、（25 分）某车间生产甲、乙、丙三种产品，每件所消耗劳动力、原料及可供使用资源 量如下表： 单位产品消耗资源量 产品甲 产品乙 产品乙 现有资源量 劳动力 原料 6 3 5 3 4 5 45（单位） 30（单位） 单位产品利润（元） 3 1 5 （1） 用单纯形法确定使总利润达到最大的生产计划。 （2） 分别求出劳动力和原材料的影子价格。 （3） 若产品乙的单位利润变为 2 元，其它条件不变，原最优计划是否发生改变？ （4） 若原材料不够，可到市场上购买，市场价格为 0.8 元/单位,问是否要购进,最多 购进多少?
四、(20分)最大流问题如下图所示,图中弧旁数字为容量,求下图网络中v,到v的最 大流量。要求 (1)建立该问题的数学模型; 2)用标号法求解上述问题。(写岀每条增广链及其调整流量、最小截集和总流量) 《运筹学》试卷A卷第3页共5页
《 运筹学 》试卷 A 卷 第 3 页 共 5 页 四、（20 分）最大流问题如下图所示，图中弧旁数字为容量，求下图网络中 s v 到 t v 的最 大流量。要求： （1）建立该问题的数学模型； （2）用标号法求解上述问题。（写出每条增广链及其调整流量、最小截集和总流量） vs v4 v1 v3 v2 vt 3 4 1 3 5 5 2 1 2 vs v4 v1 v3 v2 vt 3 4 3 5 5 2 1 2 vs v4 v1 v3 v2 vt 3 4 1 3 5 5 2 1 2 vs v4 v1 v3 v2 vt 3 4 3 5 5 2 1 2
五、(10分)给定目标规划问题: 2P(d1+d)+P2(d2+d2) d1+d1=2 2x1-3x2+d2+d2=6 x1≤6 x1,x2≥0,d7,d#+≥0,(=1,2) 用图解法找出该目标规划问题的满意解 六、证明题(5分) 线性规划问题maxz=CX,AX=b,X≥0,设X°为问题的最优解。若目标函数中用C'代 替C后,问题的最优解变为ⅹ',求证 《运筹学》试卷A卷第4页共5页
《 运筹学 》试卷 A 卷 第 4 页 共 5 页 五、（10 分）给定目标规划问题： = − + + = + + + = = + + + − + − + − + − + − + , 0, , 0,( 1,2) 6 2 3 6 2 2 . min 2 ( ) ( ) 1 2 1 1 2 2 2 1 2 1 1 1 1 1 2 2 2 x x d d i x x x d d x x d d st z P d d P d d i i 用图解法找出该目标规划问题的满意解。 六、证明题（5 分） 线性规划问题 max z = CX, AX = b, X 0 ，设 0 X 为问题的最优解。若目标函数中用 * C 代 替 C 后，问题的最优解变为 * X ，求证： ( )( ) 0 * * 0 C −C X − X
附加题(30分) 分析用位势法求检验数的问题: (1)、(10分)表述一般的运输问题,写出该运输问题的数学模型及其对偶问题的模型; (2)、(10分)证明对偶变量法(也称位势法)求检验数的合理性 (3)、(10分)结合本试题中基本题二(1)的运输问题,用位势法求初始表格中空格处 的检验数。 《运筹学》试卷A卷第5页共5页
《 运筹学 》试卷 A 卷 第 5 页 共 5 页 附加题（30 分） 分析用位势法求检验数的问题： （1）、（10 分）表述一般的运输问题，写出该运输问题的数学模型及其对偶问题的模型； （2）、（10 分）证明对偶变量法（也称位势法）求检验数的合理性； （3）、（10 分）结合本试题中基本题二（1）的运输问题，用位势法求初始表格中空格处 的检验数
