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

2013-2014学年第一学期11级工商管理12级物流工程专业《运筹学》复习提纲(2013.12)

一、填空题

?n1. 若L.P问题存在可行域,则其可行域D??X?Pjxj?b,xj?0,j?1,2,?j?1?,n?是 ;且其?基可行解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),一个点、边的交错序列vi1,ei1,vi2,ei2,?,vik?1,eik?1,vik,如果满足

,vik都

?eit???vit,vit?1???t?1,2,,k?1?,则称之为联结vi1和vik的 ,若其中的点vi1,vi2,是不同的,则称之为 。

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. 若给定可行流f??fij?,将网络中使fij?cij的弧称为 ,使jfij? ic的弧称为 。17. 若乐观时间为a、最可能时间为m、悲观时间为b,则按平均意义计算的工作持续时间值为 ,

这种确定工作持续时间的方法称为 。

18. 工作自由时差(FFi-j)是指在不影响 的前提下,工作所具有的机动时间。其计算

方法为 (用公式表达)。

二、判断题

见平时各章作业

三、根据资料回答问题

1. 能根据原问题写出对偶问题

2. 下面是一个求Max问题、约束条件用“≤”连接的L.P问题最优单纯形表格,其中x4、x5、x6为松弛

变量。

XB x1 x3 x5 σj b 2 3/2 1 -5 x1 1 0 0 0 x2 1 0 -2 0 x3 0 1 0 0 x4 2 1 1 -4 x5 0 0 1 0 x6 1 4 6 -9 要求:(1)写出该问题及其对偶问题的最优解; (2)如能以代价5/2增添第一种资源一个单位是否值得,为什么? (3)如有人愿意向你购买第三种资源,应要价多少才合算,为什么? (4)是否有其它最优解,为什么?

3. 见第二章作业

四、求解下列各题

见平时各章作业及课上例题:

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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4