上海电机学院运筹学期末考试试题及答案

用Dijkstra算法求下图中v1到v8的最短路。（可在原图上标号）

解：评分标准，表错一个扣一分。

八、（共10分）

用图解法找出下面目标规划问题，并写出简要步骤。

minZ?P???1d3?P2(d1?d?1)?P3d2?x??1?x2?d1?d?1?0(1)? 2x?d??1? 2x2 ?d2?2?12(2)?? 2x1?3x2 ?d?3?d?3?12(3) ?x1?4(4)?? x2 ?3(5)??x??1,2?0,dl,dl?0 (l?1.2.3)解：

X2 （2） d+ 2 （4） （3） d+- 3 d1（1） d- + 2d1 3 d-3 A C E （5） D

B

5 / 6

10分??

0 4 6 X1

解：如上图，可行域为图中剖面线部分； ??4分

-P1d3:满意解在AB以上，即三角形ABE； ??6分

-+

P2(d1+d1):满意解在线段CD上； ??8分

+

P3d2:满意解在线6C以下，即最优解为C点； ??10分

6 / 6