燕山大学里仁学院运筹学考题及答案.doc

第页共NUMPAGES14页
科目运筹学班级姓名学号时间
题号一二三四五总分分数一、（25分）给出下列线性规划的最优单纯形表，如表1所示。其中分别为第一、第二约束方程中的松弛变量。

表1
→58600基()541002－188011－1100－2－2－3
试分析下列各种条件下最优解（基）的变化：
目标函数中变量的系数由6变为10；
约束条件右端项由变为；
在原线性规划的约束条件上，增加约束条件：。其最优解是否变化？如变化，求出最优解。

二、（25分）表2中给出了一个运输问题，回答下列问题：
1、求解运输问题的初始基可行解的方法有哪几种，都是什么？
2、对于已经求得的初始可行解进行最优性检验有几种方法，都是什么？运输规划的基可行解最优的条件是什么？
3、利用最小元素法求下列运输问题的初始基可行解，并检验该初始基可行解的最优性。
表2
销地
产地产量

3
1
711
9
43
2
1010
8
57
4
9销量3656
三、（20分）用Gomory割平面法求解如下整数规划问题，已知该整数规划的松弛问题的最优单纯形表如表3，其中分别为第一、第二约束方程中的松弛变量。

表3
→1100CBXBb13/410－1/41/417/4013/41/400－1/2－1/2
v4
2
v2
四、（10分）应用Dijkstra算法求图1中的网络从到的最短路径（只需在图上标号并指出最短路径）。
v1
v6
v3
v5
3
5
2
4
2
4
2

图1

五、（20分）

图2
要求：（1）用图上计算法计算图2中各事项的时间参数，各工作的时间参数以及时差；
(2)指出该网络图的关键路径。

试题答案
一、（25分）给出下列线性规划的最优单纯形表，如表1所示。其中分别为第一、第二约束方程中的松弛变量。

表1
→58600541002－188011－1100－2－2－3试分析下列各种条件下最优解（基）的变化：
(1)目标函数中变量的系数由6变为10；
约束条件右端项由变为；
在原线性规划的约束条件上，增加约束条件：。其最优解是否变化？如变化，求出最优解。

解：（1）题意即为由6变为10，此时最优单纯形表1变为下表：
→581000541002－18801【1】－11002－2－3这时原方案已不再是最优方案，再经过一次迭代，得到最终单纯形表：
→581000541002－1108011－110－200－5由最终单纯形表可得，此时最优解变为：
，目标函数最优值变为：。

（2）题意即为由12变为30，此时最优单纯形表1中的列向量将变为：
。
最终单纯形表由表1变为下表：（2分）
→586005401002－18－10011【－1】100－2－2－3这时原方案已不是最优方案，用对偶单纯形法再迭代一次，得到最终单纯形表：
→581000520122010100－1－11－10－2－40－5由最终单纯形表可得，此时最优解变为：
，目标函数最优值变为：

（3）增加新约束条件：后，原最优解不满足新约束条件，即16>13不成立，故原最优解会发生变化。（1分）
新约束加入松弛变量标准化：，置于表1得下表：
→586000541002－1088011－11001321300100－2－2－30将基变量，，所对应的列向量变为单位向量，经计算得下表
→586000541002－1088011－1100－3002【－3】1100－2－2－30

再利用对偶单纯形法计算得下表：（3分）
→58600052104/30－1/32/389011/302/3－1/30100－2/31－1/3－1/300－10/30－11/3－2/3用对偶单纯形法求出新的最优解为：
，目标函数最优值变为：。

二、（25分）表2中给出了一个运输问题，回答下列问题：
1、求解运输问题的初始基可行解的方法有哪几种，都是什么？
2、对于已经求得的初始可行解进行最优性检验有几种方法，都是什么？运输规划的基可行解最优的条件是什么？
3、利用最小元素法求下列运输问题的初始基可行解，并检验该初始基可行解的最优性。
表2
销地
产地产量

3
1
711
9
43
2
1010
8
57
4
9销量36561、答：求解运输问题初始基可行解有三种方法：最小元素法、西北角法和沃格尔法。
2、答：初始基可行解的最优性检验有两种方法，它们是：闭回路法以及位势法。最优条件是所有检验数都非负。（3分）
3、解：此问题是一个产销平衡问题，应用最小元素法求得的初始基可行解如下表：
销地
产地产量

3

64
1
3

37
4
9销量3656下面应用闭回路法或位势法计算得各个空格的检验为：
。
此时还存在负检验数，该初始