发布时间 : 星期五 文章运筹学更新完毕开始阅读f18033cf89eb172ded63b7b6
考试安排在1月18~20日连续三天,上、下午各考一门。
每名研究生都要提出希望自己每天最多只参加一门课程考试。已知要求C课程安排在19日上午,D课程必须安排在下午考,F课的考试必须安排在B、E考试之后。要求排出一张满足上述所有要求的考试日程表。
1月18日 1月19日 1月20日 上午 下午
五、见以下有向图,图中数字为两点间距离(16分)。
要求:(1)用动态规划的方法求出A→D的最短路(8分)
(2)若f2(B1)为从B1出发至D点的最短距离,写出f2(B1)的动态规划递推方程的一般表达
式,并具体说明递推方程中每个符号的意义(8分)。
六、选择填充题(每题4分,共20分) (1) (1) 线性规划问题 min z=3x1+5x2
?x1?4??2x2?12??3x1?2x2?18?x,x?0?12对偶变量y1y2y3
已知其最优解为x1=2,x2=6,z*=36,则其对偶问题的最优解为 .。.(①y1=3,y2=2,y3=0;②y1=0,y2=3/2,y3=1;③y1=0,y2=1,y3=4/3;④y1=3,y2=1,y3=2/3)
(2)已知某个含10个节点的树图,其中9个节点的次(线度)为,1,1,3,1,1,1,3,1,3,则另一节点的次为 。(①1;②4;③3;④2)
(3)用标号法寻找网络最大流时,发生标号中断。这时若用V表示已标号的节点集合,
???V→V方向的弧上有 。用V表示未标号的节点集合,则在网络中所有V→V方向的弧上有 ,
(①f≥0;②f≤c;③f=c;④f=0)
注:f为流量,c为弧的容量。
运筹学习题(5)
一、一、某投资者有30000元可供为期四年的投资。现有下列五项投资机会可供选择:
A:四年内,投资者可在每年年初投资,每年每元投资可获到0.2元,每年获利后将本利重新投资。
B:在四年内,投资者应在第一年年初或第三年年初投资,每两年每元投资可获利润0.5元,两年后获利。然后可将本利再重新投资。
C:在四年内,投资者应在第一年年初投资,三年后每元投资可获利0.8元。获利后可将本利重新投资。这项投资最多不超过20000元。
D:在四年内,投资者应在第二年年初投资,两年后每元投资可获利0.6元。获利后可将本利重新投资。这项投资最多不超过15000元。
E:在四年内,投资者应在第一年年初投资,四年后每元投资可获利1.7元。这项投资最多不超过20000元。
投资者在四年内应如何投资,使他在四年后所获利润最大?写出这个问题的线性规划模型,不用求解。
二、现要在五个工人中确定四个人来分别完成四项工作中的一项工作。由于每个工人的技术特长不同,他们完成各项工作所需的工时也不同。每个工人完成每项工作所需的工时如下表所示:
试找出一个工作分配方案,使总工时最小。 三、
采用变量代换,试把非线形0-1整数规划 max z=x1?x2x3?x1x2x3
2
s.t. –3x1+4x2+x3≤3 x1、x2、x3为0或1
转换成一个线形0-1整数规划。
五、设某公司拟将五台设备分配给下属的甲、乙、丙三个工厂。各工厂获得这种设备后,可以为公司带来的盈利如下表所示:
问分配给各工厂多少台这种设备,可以为公司带来盈利的总和为最大。用动态规划方法求解。