试题五 试题代码:453试题名称:运筹学 考生注意 1.本试题共七题,共3页,请考生认真检查 2.请务必将答案写在答卷纸上,写在试卷上的谷案无效 总分 得分 签字 对约束条件(20分) 8xatxs+x 13 2 +x+3x7=-4 x1-4x2 19 3x3+3x4 x≥0j=1,…,7 说明解Ⅹ=(1,2,1,1,0,0,0)T是不是基可行解,假定不是,试找出一个基可行解。 、某极小化线性规划的最优单纯形表为(25分) B x x 3 -1/2 1/6 其中x4,x5为松驰变量,问题的约束为≤形式 1.写出原线性规划问题 2.写出原问题的对偶问题 3.直接由最优表写出对偶问题的最优解 三、考虑四种不同类型的机器和五项任务的分配问题,可利用的四种类型机器的台数是25, 30,20和30,五项任务的工作量是20,20,30,10和25,不能把第4类机器分配到第4 项工作上,单位成本如下表所示,求各类机器分到各项任务上的最优分配。(20分)
试题五 试题代码：453 试题名称：运筹学 考生注意∶ １．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一、对约束条件（20 分） x x x x x x x x x x x x x x x x x j j 1 2 4 5 6 3 4 6 7 1 2 4 7 3 4 6 3 8 13 2 2 3 4 4 10 2 19 3 3 6 0 1 7 − − + + = − − − + + = − − − − + = − + + = = ,, 说明解 X=（1,2,1,1,0,0,0）T是不是基可行解，假定不是，试找出一个基可行解。 二、某极小化线性规划的最优单纯形表为（25 分） XB x1 x2 x3 x4 x5 b x3 0 1/2 1 1/2 0 5/2 x1 1 -1/2 0 -1/6 1/3 5/2 c z j − j 0 -4 0 -4 -2 其中 x4 ， x5 为松驰变量，问题的约束为≤形式∶ 1．写出原线性规划问题； 2．写出原问题的对偶问题； 3．直接由最优表写出对偶问题的最优解。 三、考虑四种不同类型的机器和五项任务的分配问题，可利用的四种类型机器的台数是 25， 30，20 和 30，五项任务的工作量是 20，20，30，10 和 25，不能把第 4 类机器分配到第 4 项工作上，单位成本如下表所示，求各类机器分到各项任务上的最优分配。（20 分）
务 机 2 2 类3 5 7 型 8 四、有A、B、C三种资源可用来生产甲、乙、丙三种产品。资源量、单位产品利润和单位 产品资源消耗量、各种产品生产的固定费用如下表所示。现在要求制定一个生产计划,使总 收益最大,试建立数学模型 (20分 单位产品 资源消耗量 资源限量 B 2 C 2 84360 100 单件利润 4 固定费用 100 五、动态规划方法是解决 →,它是在明确_条件的基础上,建 立 ,最终应求出 (20分 A、动态问题 B、多阶段决策过程的问题 C、阶段和阶段数 D、无后效性 E、最优性原理 F、基本方程(递推关系式) G、决策变量与允许决策集合 H、阶段指标与指标函数 I、状态转移方程 J、逆序解法和顺序解法 K、最优决策序列和最优目标值 L、状态与状态变量 六、有3个电站t,t,ts,每月每个电站各需6okt煤,有2个煤矿S1,S2,每月每个煤矿 可提供100kt煤。煤矿向电站每月的最大运输能力 (25分) 运输量/kt 线路的千吨运费为 运价/千元 t t t S1 5 5 5 试用网络分析方法给出供煤方案,使总运费最小 七、什么是线性规划问题的灵敏度分析?(20分)
任 务 类 型 1 2 3 4 5 机 1 10 2 3 15 9 器 2 5 10 15 2 4 类 3 15 5 14 7 15 型 4 20 15 13 — 8 四、有 A、B、C 三种资源可用来生产甲、乙、丙三种产品。资源量、单位产品利润和单位 产品资源消耗量、各种产品生产的固定费用如下表所示。现在要求制定一个生产计划，使总 收益最大，试建立数学模型。 （20 分） 单位产品 产品 资源消耗量 甲 乙 丙 资源限量 资源 A 2 4 8 500 B 2 3 4 300 C 1 2 3 100 单件利润 4 5 6 固定费用 100 150 200 五、动态规划方法是解决 ，它是在明确 条件的基础上，建 立 ，最终应求出 。 （20 分） A、动态问题 B、多阶段决策过程的问题 C、阶段和阶段数 D、无后效性 E、最优性原理 F、基本方程（递推关系式） G、决策变量与允许决策集合 H、阶段指标与指标函数 I、状态转移方程 J、逆序解法和顺序解法 K、最优决策序列和最优目标值 L、状态与状态变量 六、有 3 个电站 t1，t2，t3，每月每个电站各需 60kt 煤，有 2 个煤矿 S1，S2，每月每个煤矿 可提供 100kt 煤。煤矿向电站每月的最大运输能力： （25 分） 运输量/ kt t1 t2 t3 S1 40 40 30 S2 40 20 50 各线路的千吨运费为 运价 / 千元 t1 t2 t3 S1 4 5 8 S2 5 5 6 试用网络分析方法给出供煤方案，使总运费最小。 七、什么是线性规划问题的灵敏度分析？（20 分）
试题五答案 30-8 A 1-40-10 A4=0,列向量线性相关,不是基可行解 选取x2x2,x3.,x7作为基变量, 300 A 1-402 0030 线性无关 解出X=(,号,2.00 由题可知C4=c3=0, C3+6C1 得C=6,c2=10 此外,C2-e3+=+4得c2 0 0 b=B b b=B“b=(203)(5 3人(10 200 12 A= BA A=BA mnz=-6x1+2x2-10xy3 原问题为 x2+2x3≤5 x1-x2+x3≤10 1.x2.x3≥0 mnw=5y;+10 3y2≥6 y1-y2 2y1+y2≥10 2、对偶问题为(y,y2≥0
试题五答案 一、 解： − − − − − − − = 0 0 3 3 1 4 0 10 0 0 2 2 1 3 0 8 A A = 0 ，列向量线性相关，不是基可行解 选取 1 2 3. 7 x , x , x , x 作为基变量， − − − − = 0 0 3 0 1 4 0 2 0 0 2 3 1 3 0 0 A 线性无关。 解出 T X ' ( , ,2,0,0,0,0) 7 32 7 5 = 二、 解： 1、 由题可知 0, c4 = c5 = 而 0 2 0 4 3 1 1 6 1 1 2 3 1 − = − − + = − c c c 得 c1 = 6,c2 =10 此外， 4, 2 1 1 2 3 1 c2 − c + c = − 得c2 = −2 − = − 3 1 6 1 2 1 1 0 B − = 1 0 0 1 2 1 2 1 ' A b B b ' −1 = = = = − 10 5 1 3 2 0 2 5 2 5 1 ' b B b A B A ' −1 = − = − = = 3 1 1 0 1 2 1 0 0 1 1 3 2 0 2 1 2 1 ' A BA − + + = − + − 1, 2, 3 0 3 10 2 5 min 6 2 10 1 2 3 2 3 1 2 3 x x x x x x x x Z x x x 原问题为 2、 对偶问题为 + − − = + , 0 2 10 2 3 6 min 5 10 1 2 1 2 1 2 2 1 2 y y y y y y y w y y
3、由于对偶问题的最优解是最终单纯形表中检验数的相反数 则y*=(y1,y2)=(42) 解:利用表上作业法求解: 4 机器 机器 25 -6 10 15 0 6 10 8 14 4 30 4 任务 20 105 9 2 4 检验数20,此方案最优2*=75+100+20+100+65+200=560 1,生产第i种产品 四 解:设x代表第种产品的生产数量,(0,不生产第种产品=123 naxz=4x1+5x2+6x3-100y-150y2-200y3 2x,+4x,+8x,≤500 2x1+3x2+4x3≤300 x1≤M1y1 x2≤M2y2 M x≥0,y2≥0或1,i=123 其中4可取上界 五、 解:B,CGL,H,K 六 解:建立网络图得:图中数字分别为最大流量和费用
3、 由于对偶问题的最优解是最终单纯形表中检验数的相反数， 则 T T y* (y , y ) (4,2) = 1 2 = w*= 40 三、 解：利用表上作业法求解： 任务 机器 1 2 3 4 5 机器 i u 1 10 11 2 0 3 25 15 19 9 11 25 -6 2 5 20 10 2 15 6 2 10 4 0 30 0 3 15 13 5 20 14 8 7 8 15 14 20 -3 4 20 11 15 3 13 5 M 8 25 30 4 任务 20 20 30 10 25 105 j v 5 8 9 2 4 检验数 0 i j r ，此方案最优 Z* = 75+100+ 20+100+ 65+ 200 = 560 四、 解：设 i x 代表第 i 种产品的生产数量， ，不生产第 种产品 生产第 种产品 i i 0 1, i =1，2，3 + + + + + + = + + − − − 3 3 3 2 2 2 1 1 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 2 100 2 3 4 300 2 4 8 500 max 4 5 6 100 150 200 x M y x M y x M y x x x x x x x x x Z x x x y y y xi 0, yi 0或1，i =1,2,3 其中 Mi 可取上界 3 100 1 2 3 M =100,M = 50,M = 五、 解：B，CGL，H，K 六、 解：建立网络图得：图中数字分别为最大流量和费用
分别找出各步最小费用流,然后在此基础上增加流量得 60.60.0 此时已满足需求量达到最优, Z*=40×4+40×5+10×8+20×5+20×5+50×6=940 七 解:灵敏度分析是指:当A,b,C的系统中一个或几个发生变化时,已求得 的最优解会有什么变化:这些系数在什么范围内改变时,规划问题的最优解或最优基 不变:若最优解变化,如何用最简单的方法找到新的最优解
100,0 100,0 s S1 S2 t2 t1 t t3 40,4 40,5 30,8 40，5 50,6 40,5 60,0 60,0 60,0 分别找出各步最小费用流，然后在此基础上增加流量得： 100,90,0 100,90,0 s S1 S2 t2 t1 t t3 40,40,4 40,40,5 30,10,8 40,20,5 50,50,6 20,20,5 60,60,0 60,60,0 60,60,0 此时已满足需求量达到最优， Z* = 404+ 405+108+ 205+ 205+506 = 940 七、 解：灵敏度分析是指：当 A，b，C 的系统中一个或几个发生变化时，已求得 的最优解会有什么变化；这些系数在什么范围内改变时，规划问题的最优解或最优基 不变；若最优解变化，如何用最简单的方法找到新的最优解