谋学网www.mouxue.com
Smax?2x1?5x2
?x1?4?x?3?2??x1?x2?8??x1,x2?0
第五组：
计算题（每小题25分，共100分）
1、下图为动态规划的一个图示模型，边上的数字为两点间的距离，请用逆推法求出S至F点的最短路径及最短路长。 B1 8 5 A C1 1 10 9 11 7 B2 8 12 F S 14 5 6 4 11 5 C2 A2 9 8 B3
2、自已选用适当的方法，对下图求最小(生成树)。
V2 V4 3
5 6 3 2 V6 5
V1
3 2 3
V3 V5
3、设有某种肥料共6个单位，准备给4块粮田用，其每块粮田施肥数量与增产粮食的关系如下表所示。试求对每块田施多少单位重量的肥料，才能使总的粮食增产最多。
施 肥 1 2 3 4 粮 田 1 20 42 60 75 2 25 45 57 65 3 18 39 61 78 4 28 47 65 74 谋学网www.mouxue.com
5 6 85 90 70 73 90 95 80 85
4、求下面问题的对偶规划 极大化
z?3x1?2x2?5x3?7x 4?2x1?3x2?2x3?7x4??2? ??x1+2x3?2x4??3
??2x1?x2?4x3?x4?8 x1?0,x2
?0,x3?0,x4无非负限制。