2006级运筹学B卷(7.30)
- 格式：doc
- 大小：91.00 KB
- 文档页数：3
共 3 页
第 1 页 2006级《运筹学》课程试题（B卷）
1、若X1，X2分别是某一线性规划问题的最优解，则X=λ1X1 +λ2X2一定是该线性规划问题的最优解，其中λ1，λ2为正的实数。 （ ）
2、线性规划问题的某可行解若为最优解，则该可行解一定是基可行解。 （ ）
3、若原问题具有无界解，可推出其对偶问题无可行解；若原问题无可行解，则不能确定其对偶问题具有无界解。 （ ）
4、用西北角法求出的运输问题的初始基可行解一定不会是最优解。 （ ）
5、运输问题不会出现无可行解的情况。 （ ）
6、目标规划模型中，应同时包含绝对约束和目标约束。 （ ）
7、指派问题的系数矩阵C的某一列元素都减去常数k，得到的新的系数矩阵C′，则以C和C′为系数矩阵的指派问题具有相同的最优解。 （ ）
8、多阶段决策问题通常用动态规划的方法来求解，其最优解是惟一的。 （ ）
9、任何一个连通图，都有且仅有一个生成树（支撑树）。 （ ）
10、Dijkstra算法不适合求解有负权的网络的最短路问题。 （ ）
1、用单纯形法求解目标函数极大化的线性规划问题，当
时，说明该线性规划问题具有无穷多最优解。
2、动态规划中，状态变量应具有 性和 性。通常本阶段的状态取决于上一阶段的状态和上一阶段的 。
3、某工程公司拟从四个项目中选择若干项目，若令
个项目未被选中第，个项目被选中第 i 0i ,1ix4,3,2,1i
用ix的线性表达式表示下列要求：
（1）从1，2，3项目中至少选2个： ；
（2）只有项目2被选中，项目4才能被选中： 。
4、图G=（V,E），G有生成树的充分必要条件为G是 图。若图G是树，则必有G无圈，且边数m与顶点个数n之间的关系为 ：m= 。
共 3 页
第 2 页 1已知纯整数线性规划问题如下所示：
0,,23224125max3213211321321xxxxxxbxxxxxxz
用单纯形法求解，得其终表如下（4x为松弛变量，5x为人工变量）：
cj 5 12 4 0 -M
CB XB b x1 x2 x3 x4 x5
12 x2 8/5 0 1 -1/5 2/5 -1/5
5 x1 9/5 1 0 7/5 1/5 2/5
cj-zj 0 0 -3/5 -29/5 -M+2/5
（1）确定原模型中字母b1的值；
（2）写出上述模型的对偶模型；
（3）确定对偶模型的最优解。
2某公司下属四个商店（Ⅰ、Ⅱ、Ⅲ、Ⅳ）需要到三个厂家（甲、乙、丙）采购服装。四个商店的需求量分别为Ⅰ——1500套，Ⅱ——2000套，Ⅲ——3000套，Ⅳ——3500套；三个厂家的供应量为甲——2500套，乙——2500套，丙——4000套。由于厂家提供的服装质量、运价和商家销售情况不同，因此出售后所获得的利润也各不相同（见下表）。试为该公司确定一个商品采购方案，使总利润最大。
商店
厂家 Ⅰ Ⅱ Ⅲ Ⅳ
甲 10 5 6 7
乙 8 2 7 6
丙 9 3 4 8
3已知纯整数线性规划问题如下所示
共 3 页
第 3 页 且为整数、042162542411max2121212121xxxxxxxxxxz
其松弛问题的最优单纯形表为：
cj 4 11 0 0 0
CB XB b x1 x2 x3 x4 x5
0 x3 4 0 0 1 -1/3
4/3
4 x2 4/3 0 1 0 2/9 -5/9
11 x1 8/3 1 0 0 1/9 2/9
cj-zj 0 0 -1/2 -19/9 -2/9
（1）求问题的最优解；
（2）写出割平面约束在平面直角坐标系（x1,x2）中所表示的区域。
4求下图所示的网络的最大流与最小割集，每个弧旁的数字表示该弧的容量和流量。
(7,7)
(9,4) (3,1) (8,5) (6,6)
(3,3)
(3,2) (5,4)
(8,5) (12,11) (10,5)
v4 vs v1 v3
v2 vt
v5 (4,1
