发布时间 : 星期五 文章运筹学更新完毕开始阅读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整数规划。
五、设某公司拟将五台设备分配给下属的甲、乙、丙三个工厂。各工厂获得这种设备后，可以为公司带来的盈利如下表所示：
问分配给各工厂多少台这种设备，可以为公司带来盈利的总和为最大。用动态规划方法求解。