《管理运筹学》阶段测试Ⅰ
一. 填空题（共15分）
1. （5分）如果把约束方程121234
255x x x x +≤⎧⎨
+≥⎩标准化为123124534255
x x x x x x x ++=⎧⎨+-+=⎩，1x 是变量，2x 是
变量，3x 是变量，4x 是变量，5x 是变量。 2. （2分）LP 的基本可行解与基本解的区别是
3. （2分）求目标函数最大化的LP 中，判别数，说明该LP 有无穷最优解。
4. （6分）如图1所示，对于平面中的某LP 的约束集合，其可行
解为，基本解为，基本可行解为。
二. 判断题（每题2分，共30分）
1. 当LP 问题的最优解多于一个时，最优解必有无穷多个 。（ ）
2. 当LP 问题有可行解时必有最优解 。（ ）
3. 当LP 问题有最优解时必有在可行集顶点达到的最优解。（ ）
4. 当LP 问题有可行解时必有可行基解 。（ ）
5. LP 问题的可行解如为最优解，则该可行解一定是基可行解。（ ）
6. 若LP 问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。（ ）
7. 若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解。（ ）
8. 若1
X ，2
X 分别是某一线性规划问题的最优解，则12
12X X X λλ=+也是该线性规划问题的最优解，
其中12,λλ可以为任意实数。
9. 对一个有n 个变量，m 个约束的标准型的线性规划问题，其可行域的顶点恰好为m
n C 个。（） 10. LP 问题的每一个基解对应可行域的一个顶点。（ ）
11. LP 问题的任一可行解都可以用全部基可行解的线性组合表示。（ ） 12. 若树T 有n 个点，则其边数为n-1。（ ） 13. 树中若多出一边，必出现圈。（ ） 14. 树中点与点可以不连通。（ ） 15. 树中若除去一边，必不连通。（ ）
三. 把下列线性规划化为标准形式（每题5分，共10分）
⎪⎪⎩⎪⎪⎨
⎧≥≤=-++-≥-+≤-+-+-=无约束43214321
3
214313210,,01 32 21 2 min )1(x x x x x x x x x x x x x x x x x z ⎪⎪⎩⎪⎪⎨⎧≤≤≥+-≤++=无约束21121212
1,02 1 8
2 32 max )2(x x x x x x x x x z 四. 计算题（共45分）
1. （25分）用两阶段法求解如下线性规划问题：
121212
1212max 3227120,0
z x x x x x x x x x x =--≤⎧⎪+≥⎪
⎨-≥⎪⎪≥≤⎩
2. （10分）用Dijkstra 法求图2中v 1到v 7的最短路。
图2
3. （10分）用Floyd 法求图3中v 1到v 6的最短路。
图
3
《管理运筹学》阶段测试Ⅰ答案
五. 填空题（共15分）
5. （5分）如果把约束方程121234
255x x x x +≤⎧⎨
+≥⎩标准化为123124534255
x x x x x x x ++=⎧⎨+-+=⎩，1x 是决策变量，2x 是
决策变量，3x 是松弛变量，4x 是剩余（松弛）变量，5x 是人工变量。 6. （2分）LP 的基本可行解与基本解的区别是基本可行解的分量均大于或等于0
7. （2分）求目标函数最大化的LP 中，判别数有 1个或1个以上为0，说明该LP 有无穷最优解。 8. （6分）如图1所示，对于平面中的某LP 的约束集合，其可行
解为OGEDHO 所围阴影区域，基本解为所在直线及坐标轴的交点（A 、B 、C 、D 、E 、F 、G 、H 、O 以及GF 延长线与纵轴交点共10个点），基本可行解为 O 、H 、D 、E 、G 共5个点。
六. 判断题（每题2分，共30分）
16. 当LP 问题的最优解多于一个时，最优解必有无穷多个 。（ √ ） 17. 当LP 问题有可行解时必有最优解 。（×）
18. 当LP 问题有最优解时必有在可行集顶点达到的最优解。（√ ） 19. 当LP 问题有可行解时必有可行基解 。（ √ ）
20. LP 问题的可行解如为最优解，则该可行解一定是基可行解。（×）
21. 若LP 问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解。（ × ） 22. 若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解。（ × ）
23. 若1
X ，2
X 分别是某一线性规划问题的最优解，则12
12X X X λλ=+也是该线性规划问题的最优解，
其中12,λλ可以为任意实数。（×）
24. 对一个有n 个变量，m 个约束的标准型的线性规划问题，其可行域的顶点恰好为m
n C 个。（×）
25. LP 问题的每一个基解对应可行域的一个顶点。（ × ）
26. LP 问题的任一可行解都可以用全部基可行解的线性组合表示。（ √ ） 27. 若树T 有n 个点，则其边数为n-1。（ √ ） 28. 树中若多出一边，必出现圈。（√ ） 29. 树中点与点可以不连通。（ × ） 30. 树中若除去一边，必不连通。（ √ ）
七. 把下列线性规划化为标准形式（每题5分，共10分）
⎪⎪
⎩⎪⎪⎨
⎧≥≤=-++-≥-+≤-+-+-=无约束432143213214313210,,01 32 21 2 min )1(x x x x x x x x x x x x x x x x x z ⎪⎪⎩⎪⎪⎨⎧≤≤≥+-≤++=无约束2112
1212
1,02 1 8
2 32 max )2(x x x x x x x x x z 八. 计算题（共45分）
4. （25分）用两阶段法求解如下线性规划问题：
121212
1212max 3227120,0
z x x x x x x x x x x =--≤⎧⎪+≥⎪
⎨-≥⎪⎪≥≤⎩
5. （10分）用Dijkstra 法求图2中v 1到v 7的最短路。
