运筹学试题

2006级《运筹学》课程试题（A卷）

1、若线性规划问题有最优解，一定存在一个基可行解是最优解。 （ ）

2、增加约束条件时, 线性规划模型的可行域的范围一定会缩小。 （ ）

3、若某种资源的影子价格等于k,在其他条件不变的情况下，当该种资源增加5个单位时

候，相应的目标函数将增加5k。 （ ）

4、对于m 个产地、n个需求地的产销平衡运输问题，基可行解中基变量个数一定小于m+n。

5、如果产销平衡运输问题的单位运价表的某一行元素都加上常数k，最优调运方案将发生

（ ）

6、分支定界法可以求解纯整数规划问题，但不能求解混合整数规划问题。 （ ）

7、标准形式的指派问题是特殊的0-1规划问题，也是特殊的运输问题。 （ ）

8、建立动态规划模型时，必须正确选取状态变量，使其具有可知性和无后效性。（ ）

9、任何图中，顶点次数的总和等于顶点个数的

（ ）

10、若图G=（V,E）是一个树，则G是连通图，但去掉任何一边就不连通。 （ ）

1、原问题无可行解，

题 。 则对偶问2倍。 变化。

2、目标规划中，通常用示决策值和目标值之间的差异，用 和 表示不同目标主次轻重的差别。

3、对于求极大化的整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：

则对应的割平面约束（或方程）为 。

4、可行流是f是最大流的充分必要条是 。

5、下图为某网络图中发点vs到收点vt之间的一条链（括号中数字前者表示边的容量，后

14x16x295x1x23x35

10x14x26x32

xj 0,j1,2,3

2已知线性规划问题：

maxz2x1x24x3

3x12x24x35 x1x2x33

x1x2x34

xj0,j1,2,3

引入松弛变量x4，x5，x6后，用单纯形法求得其最优单纯形表如下：

试在此单纯表基础上，分别对下述情况进行灵敏度分析：

（1）x1的价值系数c1在什么范围变化时，问题的最优解不发生变化。（5分）

10

（2）改变右端常数为4，最优解如何改变。 （8分） 

2

3某公司下属三个生产厂，即一厂、二厂、三厂，每年需要取暖和生活用煤分别为3000t、1000t和2000t，按协议由甲矿和乙矿两个煤矿负责供应。已知甲矿年产量为4000t，乙矿为1500吨，由煤矿至各个厂区的单位运价见下表。由于需大于供，经公司决定，一厂供应量可减少0~200t，二厂需求量应全部满足，三厂供应量不少于1700t。试确定总运费最低的调运方案。

4用Dijkstra法求解下图中v1到v7的最短路。

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、某工程公司拟从四个项目中选择若干项目，若令

1, 第i个项目被选中xi 第i 个项目未被选中0，i1,2,3,4

用xi的线性表达式表示下列要求：

（1）从1，2，3项目中至少选2个： ；

（2）只有项目2被选中，项目4才能被选中： 。

4、图G=（V,E），G有生成树的充分必要条件为G是 图。若图G是树，则必有G无圈，且边数m与顶点个数n之间的关系为 ：m= 。

1已知纯整数线性规划问题如下所示：

maxz5x112x24x3

x12x2x3b12x1x23x32

x1,x2,x30

用单纯形法求解，得其终表如下（x4为松弛变量，x5为人工变量）：

（1）确定原模型中字母b1的值；

（2）写出上述模型的对偶模型；

（3）确定对偶模型的最优解。

2某公司下属四个商店（Ⅰ、Ⅱ、Ⅲ、Ⅳ）需要到三个厂家（甲、乙、丙）采购服装。四个商店的需求量分别为Ⅰ——1500套，Ⅱ——2000套，Ⅲ——3000套，Ⅳ——3500套；三个厂家的供应量为甲——2500套，乙——2500套，丙——4000套。由于厂家提供的服装质量、运价和商家销售情况不同，因此出售后所获得的利润也各不相同（见下表）。试为该公司确定一个商品采购方案，使总利润最大。

3已知纯整数线性规划问题如下所示

maxz11x14x2

x12x24

5x12x216



2x1x24

x、x0且为整数21

其松弛问题的最优单纯形表为：

（1）求问题的最优解；

（2）写出割平面约束在平面直角坐标系（x1,x2）中所表示的区域。

4求下图所示的网络的最大流与最小割集，每个弧旁的数字表示该弧的容量和流量。

2007级《运筹学》课程试题（A卷）

一、计算题：（共11分）下表为某求极大值线性规划问题的初始单纯形表及跌代后的单纯形表，试求表中a ~ l的值及各变量下标m ~ t的值。

二、计算题：（共11分）已知线性规划问题模型如下，其最优解为x1= -5，x2=0，x3= -

1。

（1）求k的值。

（2）写出对偶问题的模型并求出最优解。

minz2x1x22x3

x1x2x34

x1x2kx36

x10,x20,x3无约束

三、计算题：（共13分）已知线性规划问题模型如下所示：

maxz2x1x2x3

x1x2x36x12x2 4

x,x,x0123

用单纯形法求得最终单纯形表为：

（1）目标函数变为maxz2x13x2x3，新的最优解是什么？

（2）约束条件右端项由变为，新的最优解是什么？

4

463

（3）增添一个新的约束x12x32，新的最优解是什么？

四、计算题：（共13分）由产地1、2、3向销地A、B、C供应物资，由产地运往销地的单位物资运费、各产地产量、各销地销量如下表所示。若产地 i 有一个单位物资未运出，则将发生存储费用。假定1，2，3产地单位物资存储费用分别为5，4，3。又假定产地 2 的物资至少运出 38 个单位，产地 3 的物资至少运出 27 个单位，试求解此运输问题的最优解。