深圳大学期末测试习题

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