江苏大学运筹学样卷2

1、江苏大学运筹学期末考试任课老师:张怀胜考试日期:2012-06-06；班级:工业09；学号:3090804013；姓名：孙鹏飞；上机IP:202.195.169.161；上机总得分：93题目填空 题判断 题选择 题计算 题1计算 题2计算 题3计算 题4计算 题5计算 题6计算 题7计算 题8应用 题总分题分510108988888810100得分478898888871093一、填空题（每题1分，共5分；孙鹏飞得分:4分）1、 若线性规划有无穷多最优解，则其最优表格中至少有一个非基变量的检验 数等于零。V +1分2、设 max Z=3x +4x +x ,x +2x +x 10,2x +2x

2、+x 16,x ,x ,x NO,则在最优基123123123123不变时，请用区间表示b1的允许取值范围10,16。X!参考答案：8,163、用分枝定界法求解最大化的纯整数规划问题，某分枝得到整数可行解，则其 目标值可作为其它分枝的目标值的下界。V +1分4、 一个无圈并且连的无向图称为树。V +1分 5、采用（s,S）存贮策略的模型时，若检查出的存贮量x=s时，则订货量为S-xV +1分二、判断题（每题1分，共10分；孙鹏飞得分:7分）1、人工变量一旦出基就不会再进基。（正确）V +1分2、若X*、Y*分别是原问题与对偶问题的最优解，则X*二Y* （正确）X3、求最大值问题的目标函数值是各

3、分枝函数值的上界（错误）X4、运输问题中的位势就是其对偶变量。（正确）V +1分5、最大流问题是找一条从发点到收点的路，使得通过这条路的流量最大。（错 误）V +1分6、将指派问题的效率矩阵每行分别加上一个数后最优解不变（正确）+1分7、在不允许缺货，边生产边供应的存储模型要比瞬时供应的存储模型下的经济 批量要小（错误）V +1分8、LP问题的基本可行解对应可行域的顶点。（正确）V +1分9、若某种资源影子价格为零，则该资源一定有剩余。（正确）X10、在其他费用不变的条件下，随着单位缺货费用的增加，最优订货批量将相 应增加（错误）V +1分三、单项选择题（每题1分，共10分；孙鹏飞得分：8分）

4、1、线性规划具有无界解是指正确1）、存在某个检验数0,且此检验数所在的列上的系数均不0选择X 2）、可行解集合无界3）、有相同的最小比值4）、最优表中所有非基变量的检验数非零2、两个互为对偶问题的线性规划，（LP）为原问题，（DP）为对偶问题，以下论断 中错误的是：选择正确1）、若（LP）有可行解，则（DP）也必有可行解V +1分2）、若（LP）和（DP）都有可行解，则（LP）和（DP）目标函数最优值相等3）、若（LP）有最优解，则（DP）也必有最优解4）、若（LP）无界，则（DP）无可行解3、max z=3x +x ,4x +3x 7,x +2x 5,x ,x =0 或 1，最优解是1)、(

5、0，1)2)、(1，0)3)、(0,0)选择正确 4）、(1，1) V +1 分121212124、为建立运输问题的改进方案，在调整路线中调整量应为选择X 1）、负号格的最大运量正确2）、负号格的最小运量3）、正号格的最小运量4）、正号格的最大运量5、连通图G有n个点，其生成树是T,则有1）、T的长度等于G的每条边的长度之和2）、T有n个点n条边选择正确3）、T有n个点n-1条边V +1分4）、T有n-1个点n条边6、下列结论正确的有选择正确1）、运输问题的运价表第r行的每个c同时加上一个非零常数k,其最优调运方案不变V +1分1J2）、运输问题的运价表第p列的每个ci,同时乘以一个非零常数k

6、,其 最优调运方案不变_3）、运输问题的运价表的所有七同时乘以一个非零常数k,其最优调4）、不平衡运输问题不一定存在最优解7、某单位每年需零件A 5000件。设该零件的单价为5元/件。年存贮费为单价 的20%。不允许缺货。若每组织采购一次的费用为49元，一次购买10002499 件时，给予3%折扣，购买2500件以上时，给予5%折扣。则最佳采购批量为1）、700 件选择正确2）、1000件V +1分3）、 750 件4）、 2500件8、线性规划标准型的系数矩阵Amxn，要求选择正确1）、秩（A）=m并且m忍n V +1分2）、秩（A）=m 并且 mVn3）、秩（A）=m 并且 m=n4）、秩

7、（A）=n 并且 nVm9、以下关系中，不是线性规划与其对偶问题的对应关系的是选择正确1）、约束条件组的不等式反向V +1分2）、一个目标函数的系数行向量为另一个约束条件组的常数列3）、一个约束条件组的常数列为另一个目标函数的系数行向量4）、约束条件组的系数矩阵互为转置矩阵10、某个常数bi波动时，最优表中引起变化的有 选择正确1）、B-1b V +1分2）、CCbB-1N3）、BN1 B4）、B-1N四、计算题 题目1：用图解法求解下列线性规划问题（题分：8,孙鹏飞得分:8）min z=-x1 +3x23x1+8x2244x1+x2 -5w做题记录（见图1）：可行域为空，此LP无可行解。图1

8、：孙鹏飞所作的图答案（见图2）：可行域为空，此LP无可行解。1图2:答案图题目2:用单纯形法求解下列线性规划问题（题分:9,孙鹏飞得分:9）Maxz=-xx2-M-7X+6x2 - + =42-8x1+5x2+ =40-2X+3x2+ =6做题记录（已通过标准化）: 列单纯形表计算如下：c.0-1-1000-MCXbxxxxxxBB123456-Mx642-76-10010 x440-8501000 x56-230010检验数42M-1-7M6M-1-M000-Mx630-30-10-210 x430-14/3001-5/30-1x22-2/31001/30检验数2+30M-5/3-3M0-M

9、01/3-2M0此LP无可行解参考答案，列单纯形表迭代如下:cj0-1-1000-MCBXBbx1x2x3x4x5x6-Mx642-76-10010 x440-8501000 x56-230010检验数-7M-16M-1-M000-Mx630-30-10-210 x430-14/3001-5/30-1x22-2/31001/30检验数-3M-5/30-M0-2M+1/30此LP无可行解题目3:用对偶单纯形法求解下列线性规划问题（题分:8，孙鹏飞得分:8）Maxz=-6x1-3x23x1-2x2+ =-6x1+x2+ =15x1-4x2+ =20做题记录（已通过标准化）: 列单纯形表计算如下：c

10、.0-6-3000CBXBbx1x2x3x4x50 x3-63-21000 x41110100 x5205-4001检验数0-6-3000-3x23-3/21-1/2000 x-25/201/2100 x532-10-201检验数9-21/20-3/200此LP无可行解参考答案，列单纯形表迭代如下:cj0-6-3000CBXBbx1x2x3x4x50 x3-63-21000 x41110100 x5205-4001检验数-6-3000-3x23-3/21-1/2000 x4-25/201/2100 x532-10-201检验数-21/20-3/200此LP无可行解题目4:求解下列运输问题,使总

11、运费最小（题分:8,孙鹏飞得分:8）单位运费与产量销量表运费B1B2B3B4产量A112112097A21317121130A3611688销量226512做题过程（加括号的为检验数，其余为运输量）： 第1次运输方案与检验：表1B1B2B3B4产量A1(1)(-4)(9)77A2196(-1)530A33(1)5(4)8销量226512第3次运输方案与检验:表3B1B2B3B4产量A1(1)6(10)17A214(4)51130A38(5)(1)(4)8销量226512表3所示运输方案为最优，最小总运费为:486答案：.第1次运输方案与检验（加括号的数字为检验数,其余的数字为运输量或产量和销量

12、）:表1B1B2B3B4产量A1(1)(-4)(10)77A21465530A38(1)(1)(4)8销量226512第2次运输方案与检验:表2B1B2B3B4产量A4(1)6(10)17A514(4)51130A68(5)(1)(4)8销量226512第2次检验数无负数，故第2次运输方案为最优，最小总运费为486题目5:用匈牙利法求解下列指派问题（题分:8,孙鹏飞得分:8）完成任务所需时间表人任务任务1任务2任务3任务4第1人93107第2人1391213第3人2186第4人78137做题记录:9310T6（)44 ,5(0)33 1391213-A-(41(0)421861(）45(0)0

13、34781374:3-e-023（0）最优指派方案为：1一2，23，3一1，4一4,目标函数最小值为24答案：9310 76 (445 (0) 3313 912 13-4(）（。）441 (0) 421861 ()45(0) 0347 813 7 J:3023 (0)最优指派方案为：1一2，2一3，3一1，4一4，目标函数最小值为24题目7:求下图中v1至其它各点的最短路（题分:8,孙鹏飞得分:8）做题过程：以P表示最短路标号，T表示一般路程标号，标号过程如下:P(vs)=0，T(v ) = 14，T(v ) = 13，T(v )=9，P(v )=9， P(v )来自于点 v ; 423331

14、T(v6) = 12，T(v5)=23，P(v6) = 12， P(v6)来自于点 v3;T(v7) = 19，T(v8)=17，T(v5)=21，P(v2) = 13，P(v2)来自于点 vP(v4)=14，P(v4)来自于点 v1;P(v8)=17，P(v8)来自于点 v ;6P(v,=19, P(v7)来自于点 v6;P(v,=21, P(v?来自于点 v6;点；到其它各点的最短路见下图:答案：标号过程如下：P(vi)=0， TOC o 1-5 h z T(v ) = 13，T(v )=9，T(v )=14，P(v )=9， P(v )来自于点 v 234331T(v ) = 13，T(

15、v) = 14，T(v )=23，T(v) = 12，P(v)=12，P(v )来自于点 v 2456663T(v ) = 13，T(v) = 14，T(v )=21，T(v) = 19，T(v8)=17，P(v) = 13，P(v )来自于点 v 2457221T(v4) = 14，T(v5)=21，T(v7) = 19，T(v8) = 17，P(v4)=14，P(v4)来自于点 v1T(v5)=21，T(v7) = 19，T(v8)=17，P(v8) = 17，P(v8)来自于点 v6T(v5)=21，T(v7) = 19，P(v7) = 19，P(v7)来自于点 v6T(v5)=21，P

16、(v5)=21，P(v5)来自于点 v6点v到其它各点的最短路见下图：6 TOC o 1-5 h z 题目8:求下图所示网络中v至v的最大流，并找出一个最小截集(题分:8,孙鹏 飞得分：8)18做题记录：第 1 次标号：s(0,+8),4(s,15),2( -4,6),7(2,6),t(7,6);第1次增广链：vlv4-V2-V7-v8 1次调整后的可行流如下图：(13J)73,3)第 2 次标号：s(0,+8),4(s,9),7(4,1),6(7,1),2( -6,1),3(2,1);已是最大流，最大流量为22,最小截集为：(v ,v ),(v ,v ),(v ,v8),(v ,v8)。25

17、3567答案：第 1 次标号：v (0,+8),v (v ,15),v (-v ,6),v (v ,6),v8(v ,6);14124727第1次增广链：vlv4-V2-V7-v8 1次调整后的可行流如下图：第 2 次标号：v (0,+8),v (v ,9),v (v ,1),v (-v ,1),v (v ,1),v (v ,1)；至此标号中断，收点 v141742767328得不到标号；已无增广链，故调整后的流是最大流，最大流量为22,最小截集为：(v ,v8),(v ,v ),(v ,v8),(v ,v )。 725635题目9:用动态规划方法求解下列资源分配问题(题分:8，孙鹏飞得分:7)分配的资源数01234甲创的效益012161719乙创的效益09111315丙创的效益011151819做题记录:s01234f3(s)011151819u *01234f2(s)011202427u2*00111u101234u1*=1,2s=40+2712+2416+2017+1119+0f 4)=36最优分配方案为：u*=(1,1,2),最大总效益为x答案:s01234f3(s)011151819u *01234f2(s)011202427u2*00111u101234*=1,2s=40+2712+2416