2011级工商管理、12级物流工程专业《运筹学》复习提纲(2013.12).doc

2013-2014学年第一学期11级工商管理12级物流工程专业《运筹学》复习提纲（2013.12）
一、填空题
1. 若L.P问题存在可行域，则其可行域是 ；且其基可行解X对应可行域D的 。
2. 设L.P原问题为：MaxZ=CX；AX≤b；X≥0，其对偶问题为：Minω=Yb；YA≥C；Y≥0。若X*是原问题的可行解，Y*是对偶问题的可行解，根据弱对偶性，则存在 ；当 时X*和Y*是最优解。
3. 若X*，Y*分别是原问题和对偶问题的可行解，那么 和 ，当且仅当X*，Y*为最优解。这就是松弛定理。
4. 对资源向量b进行灵敏度分析，当各bi同时变化为bi+Δbi（i=1，2，…，m）时，则若最优基不变，应使 ≤1（100%）。该规则称为： 。
5. 对于有m个产地、n个销地的产销平衡的运输问题，其数学模型中含有m+n个约束条件、 个决策变量，决策变量中基变量的个数不超过 个。
6. 对于Max L.P问题，若X(0)=(b1’,b2’,…,bm’,0,…,0)T为一基可行解，有一个 ，并且对i=1,2,…,m有 ，那么该L.P问题具有无界解（或称无最优解）。
7. 设原问题是MaxZ=CX；AX+Xs=b；X,Xs≥0其对偶问题是Minω=Yb；YA-Ys=C；Y,Ys≥0则原问题单纯形表的 对应其对偶问题的一个基解,且其符号方向 。
8. 对价值向量C进行灵敏度分析，当各cj同时变化为cj+Δcj（j=1，2，…，n）时，则若最优基不变，应使 ≤1（100%）。该规则称为： 。
9. 有m个产地n个销地的产销平衡的运输问题，对应变量xij的系数列向量Pij= ；其约束方程系数矩阵的秩 。
10. 在目标规划中，正、负偏差变量d+和d-恒有 的关系；含有正、负偏差变量的约束条件称为 ，它们是软约束。
11. 设有最大化的整数规划问题A，与它相应的线性规划为问题B，分枝定界法就是从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数Z*的 ；而A的任意可行整数解的目标函数值将是Z*的一个 。
12. 指派问题的解法引用了匈牙利数学家康尼格一个关于矩阵中0元素的定理：系数矩阵中 的最多个数等于 的最少直线数。
13. 给定一个图G=(V，E)，一个点、边的交错序列，如果满足，则称之为联结和的 ，若其中的点都是不同的，则称之为 。
14. 设图G=(V，E)是一个树，p(G)≥2，则G中至少有 个悬挂点；图G=(V，E)是一个树的充要条件是G不含圈，且恰有 条边。
15. 满足下述条件的流f称为可行流：(1)容量限制条件，对每一弧(vi，vj)ÎA，其流量fij满足 ；(2)平衡条件，对于中间点满足，流出量=流入量，即对每个i (i¹s,t)有 （用公式表达）。
16. 若给定可行流，将网络中使的弧称为 ，使的弧称为 。
17. 若乐观时间为a、最可能时间为m、悲观时间为b，则按平均意义计算的工作持续时间值为 ，这种确定工作持续时间的方法称为 。
18. 工作自由时差（FFi-j）是指在不影响 的前提下，工作所具有的机动时间。其计算方法为 （用公式表达）。

二、判断题
见平时各章作业

三、根据资料回答问题
1. 能根据原问题写出对偶问题
2. 下面是一个求Max问题、约束条件用“≤”连接的L.P问题最优单纯形表格,其中x4、x5、x6为松弛变量。
XB
ｂ
x1
x2
x3
x4
x5
x6
x1
2
1
1
0
2
0
1
x3
3/2
0
0
1
1
0
4
x5
1
0
-2
0
1
1
6
σj
-5
0
0
0
-4
0
-9
要求：(1)写出该问题及其对偶问题的最优解；
(2)如能以代价5/2增添第一种资源一个单位是否值得，为什么？
(3)如有人愿意向你购买第三种资源，应要价多少才合算，为什么？
(4)是否有其它最优解，为什么？
3. 见第二章作业

四、求解下列各题
见平时各章作业及课上例题：
运输问题（表上作业法）、目标规划（图解法）、整数规划（割平面法与指派问题）、图与网络优化（最小树与最大流）、网络计划（时间参数计算及关键路线确定）、存储论（经济订货批量及费用）。

2