深圳大学期末测试习题

学院专业姓名学院专业姓名学号(密封线内不答题)……………………密………………封………线……线………_____________________…开/闭卷闭卷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）下表给出运输问题的产销平衡表及运价：销地运价（元/吨）产地产量（吨）15182282125167销量（吨）456求使运费最小的方案可用方法求解。首先用伏格尔法求初始调运方案，数字格为，此时，空格处的检验数为，再用方法调整得最优方案为，最小运费为。（2）指派问题属于问题，可以用方法求解，当任务数比人数少时，可以采取方法处理。（3）在图中找一条经过每边的最短路问题是。三、（25分）某车间生产甲、乙、丙三种产品，每件所消耗劳动力、原料及可供使用资源量如下表：单位产品消耗资源量产品甲产品乙产品乙现有资源量劳动力原料63534545（单位）30（单位）单位产品利润（元）315用单纯形法确定使总利润达到最大的生产计划。分别求出劳动力和原材料的影子价格。若产品乙的单位利润变为2元，其它条件不变，原最优计划是否发生改变？若原材料不够，可到市场上购买，市场价格为0.8元/单位,问是否要购进,最多购进多少?四、（20分）最大流问题如下图所示，图中弧旁数字为容量，求下图网络中到的最大流量。要求：（1）建立该问题的数学模型；（2）用标号法求解上述问题。（写出每条增广链及其调整流量、最小截集和总流量）ssv4v1v3v2vtv343155212sv4v1v3v2vtv34355212svsv4v4v1v1v3v3v2v2vtvtv343155212svsv4v4v1v1v3v3v2v2vtvtv34355212五、（10分）给定目标规划问题：用图解法找出该目标规划问题的满意解。六、证明题（5分）线性规划问题，设为问题的最优解。若目标函数中用代替C后，问题的最优解变为，求证：附加题（30分）分析用位势法求检验数的问题：（1）、（10分）表述一