运筹学练习.doc

一、 线性规划
3.可行解一定是基本解
4.基本解可能是可行解
5.线性规划的可行域无界则具有无界解
7.xj 的检验数表示变量 xj 增加一个单位时目标函数值的改变量
14.   任何变量一旦出基就不会再进基
15.  人工变量一旦出基就不会再进基
16.普通单纯形法比值规则失效说明问题无界
18.当最优解中存在为零的基变量时,则线性规划具有多重最优解
19.当最优解中存在为零的非基变量时,则线性规划具唯一最优解
20.可行解集不一定是凸集
二 对偶规划
1.任何线性规划都存在一个对应的对偶线性规划
2.原问题(极大值)第i个约束是“≥”约束，则对偶变量yi≥0
3.互为对偶问题，或者同时都有最优解，或者同时都无最优解
11.对偶问题有可行解，原问题无可行解，则对偶问题具有无界解
12.原问题无最优解，则对偶问题无可行解
13.对偶问题不可行，原问题无界解
14.原问题与对偶问题都可行，则都有最优解
17. 如果某资源的影子价格为a, 其他条件不变时,该资源增加2个单位，目标函数将增加2a
18.对偶单纯法换基时是先确定出基变量，再确定进基变量
23.减少一约束，目标值不会比原来变差
24.增加一个变量，目标值不会比原来变好
三、整数规划
1.整数规划的最优解是先求相应的线性规划的最优解然后取整得到
2.部分变量要求是整数的规划问题称为纯整数规划
3.求最大值问题的目标函数值是各分枝函数值的上界
4.求最小值问题的目标函数值是各分枝函数值的下界
5.变量取0或1的规划是整数规划
7.  0－1规划的变量有n个，则有2n个可行解
五、运输问题
4.产地数为3，销地数为4的平衡运输问题有7个基变量
5.m＋n－1个变量组构成一组基变量的充要条件是它们不包含闭回路
6.运输问题的检验数就是其对偶变量
8.运输问题的位势就是其对偶变量
13.若运输问题的供给量与需求量为整数，则一定可以得到整数最优解
14.按最小元素法求得运输问题的初始方案, 从任一非基格出发都存在唯一一个闭回路
17.5个产地6个销地的平衡运输问题有11个变量
18.5个产地6个销地的平衡运输问题有30个变量
六、网络模型
2.最大流问题是找一条从起点到终点的路，使得通过这条路的流量最大
3.容量Cij是弧（i，j）的最大通过能力
4.流量fij是弧（i，j）的实际通过量
10. 若图G是树，则图G的任一对顶点之间一定只有一条链.
11. 求解最短路问题的狄克斯特算法既可解决无向图的最短路问题，也可解决有向图的最短路问题。
12.狄克斯特算法是求最大流的一种标号算法
13.破圈法是：任取一圈，去掉圈中最长边，直到无圈
14.避圈法（加边法）是：去掉图中所有边，从最短边开始添加，加边的过程中不能形成圈，直到连通（n－1条边）
15. 在网络G中从始点到终点的最大流的流量不一定等于分离该始点和终点的最小割的容量。

1 线性规划
3 = "错"
4= "对"
5= "错""
7= "对"
14= "错"
15= "对"
16= "对"
18 = "错"
19= "错"
20 = "错"

2对偶问题
1="对"
2= "错"
3 = "对"
11 = "对"
12= "错"
13 = "错"
14 = "对"
17=错
18= "对" "
23= "对"
24= "错"
3 整数规划
1= "错"
2 = "错"
3 = "对"
4 = "对"
5 = "对"
7 = "错"

5 运输问题
4 = "错"
5= "对"
6 = "错"
8 = "对"
13 = "对"
14 = "对"
17 = "错"
18 = "对"
6 网络模型
2 = "错"
3 = "对"
4 = "对"
10=对
11=对
12 = "错"
13 = "对"
14 = "对"
15=错