课程名称: 运筹学(Ⅱ) 课程编号: 课程类型:√学位课、非学位课 考试方式: 闭卷学科专业、领域: 管理科学与工程 所在学院: 经济管理 任课教师: 刘俊娥河北工程大学研究生2007~ 2008学年第 二 学期考试试卷( )卷1、求解无约束极值问题的下降类一般步骤有哪些?试例举三种你所了解的下降类算法名称。
2、任选一种一维搜索的算法,请写出关于极值点求解的过程。
3、某工厂生产K 种不同花色和款式的衬衣,在一定时期内生产量y 相同,但根据经验或预测,投入市场后顾客对不同品种的需求量q i 却不同;有的畅销,有的滞销,过去工厂对产品价格均按边际销售成本定价,即,ii q c p ∂∂=其中C=C(q 1,q 2,……q k )是销售成本。
现工厂考虑;为了获得最大利润,应不应该将畅销品种的价格提高?若要提高,提高多少为宜?建立数学型并用K —T 条件求解。
4、某种货物由2个仓库A 1,A 2运送到3个配送中心B 1,B 2,B 3。
A 1,A 2的库存量分别为每天13吨、9吨;B 1,B 2,B 3每天的需求分别为9吨、5吨、6吨。
各仓库到配送中心的运输能力、单位运费如表,求:(1)运量最大的运输方案。
(2)运费最省的运输方案。
(注:不能不使用该网络); (3)考虑到运费和运量,使运费最省的调运方案。
5、某工地有4个工点,各工点的位置及对混凝土的需要量列入下表,现需建一中心混凝土搅拌站,以供给各工点所需要的混凝土,要求混凝土的总运输量(运量*运距)最小,试决定搅拌站的位置(建立数学型)。
试分别考虑以下两种情况:(1)搅拌站到各工点的道路均为直线。
(2)道路为相互垂直或平行的网格。
6、某工程所有关键工序组成的网络如下图,图中弧上数字为各关键工序压缩工时所需的费用(单位:百元/天)。
现该工程需将工期压缩一天,试求出使总压缩费用最小的压缩方案,以及该最小的压缩费用。
请详细写出确定过程。
1、解:求解无约束极值问题的下降类一般算法步骤:(1)选取某一初始点X (0) 令k:=0( := 为赋值符号,k:=0表示将0赋给变量k)。
(2)确定搜索方向。
若已得出某一迭代点X (k) ,且X (k) 不是极小点。
这时,就从X (k)出发确定一搜索方向P (k),沿这个方向应能找到使目标函数值下降的点。
对约束极值问题,有时(视所用的算法而定)还要求这样的点是可行点。
(3)确定步长。
沿P (k)方向前进一个步长,得新点X(k+1)。
即在由X(k)出发的射线X=X (k)+λP(k)λ≥0上,通过选定步长(因子)λ=λk ,得下一个迭代点X (k+1)=X (k)+λk P (k)使得f(X (k+1))=f(X (k)+λk P (k))< f(X (k))(4)检验得到的点是否为要求的极小点或者近似极小点,如满足要求,迭代停止。
否则,令K:=k+1返回第二步继续迭代。
下降类算法包括:(1)梯度法(最速下降法)(2)牛顿法(3)共轭梯度法(4)变尺度法 2、解:斐波那契算法(1)确定试点个数n根据缩短率δ≥ 1/ Fn 得到F n或区间精度η, F n ≥ (b 0-a 0)/ η,查表得n 。
或迭代得到n ,迭代的算法如下:①计算F n ≥ (b 0-a 0)/ η 或F n ≥ 1/ δ 得F n ' n=1, F 0=F 1=1转 ② ②n=n+1, F n =F n-2+F n-1转③③若F n < F n ',则转②否则停止,得到n K=1 (2)选取前两个试点的位置(3)计算函数值f(X k ')f(X k ")并比较其大小 若f(X k ')<f(X k "),则a K =a K-1,b K =x K ",x K+1"=x K ' 并令或否则,取a K =x K ',b K =b K-1,x K+1'=x K "并令K=K+1(4)若K ≠n-2,则转(3),否则 若f(x K ')<f(x K "),则a K =a k -1,b K =x K "若f(x K ')>f(x K "),则a K =x k ',b K =b K-1比较函数值f(x K+1'),f(x K+1" )的大小,得到函数y=f(x)的极小值和极小点,从而得到最终区间[a K ,x K+1" ]或[a K ,x K+1"] 。
3、解:121211(,...)ax ()(,...)0,1,2,...k k ki i i k i i i i C q q q M f X p q C q C q q q q q y i k==∂⎧⎪=-=-⎨∂⎪≤≤=⎩∑∑ 转化为121211(,...)in ()(,...)0,1,2,...,k k ki i i k i i i i i C q q q M f X p q C q C q q q q g y q i k==∂⎧⎪=-=-+⎨∂⎪=-≥=⎩∑∑ 设K-T 点为i q *,各函数的梯度为:⎪⎪⎩⎪⎪⎨⎧-+=-+=--+--------)()(1111"1111'K K K n K n K K K K n K n K K a b F Fa x ab F F a x )('21k k Kn K n K K b a F F b x -+=---+)('21k k Kn K n K K a b F F a x -+=---+)("11k k Kn K n K K a b F F a x -+=---+)(21'1k K K b a x +=+))(5.0("1k k K K a b a x -++=+ε11(),1,2,...,k k i i i i i i iC C Cq q i k q q q ==∂∂∂=--∙=∂∂∂∑∑; ()1,1,2,...,i i g q y i k ∇=-=; 对K 个约束条件分别引入广义拉格朗日乘子12,,...,k μμμ***,则该问题的K-T 条件如下:121112...0(1)0(1)0..................(1)0k k i k i i ii i k C C C q q q q y y y μμμμμμ***==***∂∂∂⎧--∙----=⎪∂∂∂⎪-=⎪⎪-=⎨⎪⎪-=⎪⎪⎩∑∑ 4、解:(1)添加两个新点Vs ,Vt ,构造赋权有向图如下((((2) 看做运输问题,用表上作业法求解,由于是产销不平衡问题,虚拟销地B4,销量为2.①第一步,用最小元素法给出初始运量表。
②用闭回路法计算检验数。
λ21=8-7+11-3=9,λ13=10-11+7-4=2,λ42=M-M+11-7=4;所有非基变量的检验数大于零,则初始调运方案为最优调运方案,此时的运费为c=3×9+11×2+7×3+4×6=94(2)构造赋权有向图,求最小费用流,c ij表示由A i到B j的流量(i=1,2;j=1,2,3),则令c ij为∞,将该问题转化为最小费用最大流问题。
最小费用为:9×3+2×11+3×7+4×6=94W(f (2))ev(f (3))=18fW(f (1))cv(f (2))=15dW(f (0))av(f (1))=9b V S(3)构造赋权有向图,求最小费用最大流。
弧旁数字为(b ij ,c ij )。
①取f (0)=0为初始可行流。
②构造赋权有向图W(f (0)),并求出从Vs 到Vt 的最短路(Vs ,A 1,B 1,Vt )。
③在原网络图中,与这条最短路相应的增广链为µ=(Vs ,A 1,B 1,Vt )。
④在µ上进行调整,θ=8,得f (1)(图b )。
按照上述算法依次得W(f (1)), W(f (2)), W(f (3)), W(f (4)), W(f (5)), W(f (6)),流量依次为8,13,16,17,18,20,f (6)中不存在最短路,故f (6)为最小费用最大流,最大流量为20,此时的最小费用为:3×8+11×2+1×10+1×8+3×7+5×4=105。
W(f (4))iW(f (3))gv(f (4))=20h V SW(f )v(f (4))=17hW(f )ev(f (3))=16fW(f (1))cv(f (2))=13dW(f (0))av(f (1))=8b5、解:(1)设搅拌点的坐标为(X ,Y ),则搅拌点各工点的距离为22)()(i i i Y Y X X d -+-=(i 表示到第i 个工点)建立该问题的数学模型为:)4,3,2,1( )()( s.t. min 2241=-+-=⨯=∑=i Y Y X X d Q d f i i i i ii(2)设搅拌点的坐标为(X ,Y ),则搅拌点到各工点的距离为ii i Y Y X X d -+-=W(f )mW(f )v(f (6))=20lW(f )v(f (5))=18j建立该问题的数学模型为:)4,3,2,1( s.t. min 41=-+-=⨯=∑=i Y Y X X d Q d f i i i i ii6、解:看做求网络最大流,令已有的弧上的数据为容量。
(1)首先给网络赋予初始可行流。
方法不唯一,但不同的初始可行流对应的增广链不同。
(2)用标号法求增广链,开始给v1标号(△, +∞);于是检查v2,弧(v1,v2)上,f12=c12;检查v3,给v3标号(v1, 1);检查v4,给v4标号(v3,1),由于弧(v4,v2)上,f42=0,弧(v4,v5)、弧(v4,v5)上可行流等于流量,标号无法继续下去,算法结束。
此时的可行流即为最大流。
同时可以找到最小截集(11,V V ),1V ={①,③,④},1V ={②,⑤,⑥},于是(11,V V )={(v1,v2),(v4,v2),(v4,v5),(v3,v6),(v4,v6)}是最小截集。
则压缩总工期1天的压缩方案为:将工序①-②,工序③-⑥,工序④-⑤,工序④-⑥同时压缩1天,此时的最小费用为2+1+3+2=8.(△。