1、共 页 第 页课程名称： 运筹学（） 课程编号： 课程类型：学位课、非学位课 考试方式： 闭卷 学科专业、领域： 管理科学与工程 所在学院： 经济管理 任课教师： 刘俊娥 河北工程大学研究生 2007 2008 学年第 二 学期考试试卷（ ）卷1、求解无约束极值问题的下降类一般步骤有哪些？试例举三种你所了解的下降类算法名称。2、任选一种一维搜索的算法，请写出关于极值点求解的过程。3、某工厂生产 K 种不同花色和款式的衬衣，在一定时期内生产量 y 相同，但根据经验或预测，投入市场后顾客对不同品种的需求量 qi却不同；有的畅销，有的滞销，过去工厂对产品价格均按边际销售成本定价，即， 其中 C=C(
2、q1,q2,qk)是销售成本。现工厂考虑；iiqcp为了获得最大利润，应不应该将畅销品种的价格提高？若要提高，提高多少为宜？建立数学型并用 KT 条件求解。4、某种货物由 2 个仓库 A1，A 2运送到 3 个配送中心 B1，B 2，B 3。A 1，A 2的库存量分别为每天 13 吨、9 吨；B 1，B 2，B 3每天的需求分别为 9 吨、5吨、6 吨。各仓库到配送中心的运输能力、单位运费如表，求：运程 运量限制（吨） 运费（百元/吨）A1 B1 8 3A1 B2 7 11A1 B3 5 10A2 B1 6 8A2 B2 3 7A2 B3 5 4（1）运量最大的运输方案。 （2）运费最省的运输
3、方案。 （注：不能不使用该网络） ；（3）考虑到运费和运量，使运费最省的调运方案。5、某工地有 4 个工点，各工点的位置及对混凝土的需要量列入下表，现需建一中心混凝土搅拌站，以供给各工点所需要的混凝土，要求混凝土的总运输量（运量*运距）最小，试决定搅拌站的位置(建立数学型)。试分别考虑以下两种情况：（1）搅拌站到各工点的道路均为直线。 （2）道路为相互垂直或平行的网格。工点的位置 (X1,Y1) (X2,Y2) (X3,Y3) (X4,Y4)混凝土需要量 Q1 Q2 Q3 Q46、某工程所有关键工序组成的网络如下图，图中弧上数字为各关键工序压缩工时所需的费用（单位：百元/天） 。现该工程需将工
4、期压缩一天，试求出使总压缩费用最小的压缩方案，以及该最小的压缩费用。请详细写出确定过程。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上，通
5、过选定步长（因子）= k，得下一个迭代点 243562436313621共 页 第 页X(k+1)=X(k)+ kP(k)使得f(X(k+1)=f(X(k)+ kP(k)f(xK“),则 aK=xk,bK=bK-1比较函数值 f(xK+1),f(xK+1“ )的大小，得到函数 y=f(x)的极小值和极小点，从而得到最终区间a K,xK+1“ 或a K,xK+1“ 。3、解：12121(,.)ax() (,.)0,2,.kkki i kiii CqMfXpqqqy转化为12121(,.)in() (,.)0,2,.kkki i kiiii CqMfXpqqgy设 K-T 点为 ，各函数的梯度为：
6、iq)(111“1 KKnnKabFax)(21kKnbFbx)(21kna“1kKnKabFax )(21kKbax)(5.0“1 ka共 页 第 页； ；1(),12,.kki iiiCfqqk()1,2,.igqyik对 K 个约束条件分别引入广义拉格朗日乘子 ，则该问题的 K-T 条件如下：12,.k1212 .0()0.kki kiikqqy4、解：（1）添加两个新点 Vs，Vt，构造赋权有向图如下A1A2B1B2B3875635VS139Vt956(,+)(Vs,13)(B1,8) 1=8A1A2B1B2B38,875635VS13,89Vt9,856(,+)(Vs,5)(A1,5
7、) (B2,5) 2=5A1A2B1B2B38,87,55,56,135VS13,139,1Vt9,95,56(,+)(Vs,8)(A2,3) (B2,1) 3=1A1A2B1B2B38,87,55,56,135VS13,139,1Vt9,95,56(,+)(Vs,9)(B3,5) 4=5(A2,5)共 页 第 页A1A2B1B2B38,87,55,56,135,5VS13,139,6Vt9,95,56,5(2) 看做运输问题，用表上作业法求解，由于是产销不平衡问题，虚拟销地 B4，销量为 2.B1 B2 B3 B4A1311 10 M13A28 7 4 M99 5 6 2第一步，用最小元素法
8、给出初始运量表。B1 B2 B3 B4A13911210 M2 13A28 7346M99 5，2 6 2用闭回路法计算检验数。B1 B2 B3 B4A13911210 M2 13A28 7346M99 5，2 6 221=8-7+11-3=9，13=10-11+7-4=2，42=M-M+11-7=4；所有非基变量的检验数大于零，则初始调运方案为最优调运方案，此时的运费为c=39+112+73+46=94（2）构造赋权有向图，求最小费用流,c ij表示由 Ai到 Bj的流量（i=1,2；j=1,2,3）,则令 cij为，将该问题转化为最小费用最大流问题。最小费用为：93+2 11+37+46=
9、94VSA1A2B1B2B3Vt0,130,90,90,60,53,c1111,c1210,c138,c217,c224,c23共 页 第 页VSA1A2B1B2B3Vt0000031110874W(f(0)aVSA1A2B2B390900900000Vtv(f(1)=9bVSA1A2B1B2B3Vt0000031110874W(f(1)cVSA1A2B2B396960900006Vtv(f(2)=15dVSA1A2B1B2B3Vt0000031110874W(f(2)eVSA1A2B2B399963900036Vtv(f(3)=18f-3VSA1A2B1B2B3Vt0000031110874
10、W(f(3)gVSA1A2B2B3119965920036Vtv(f(4)=20h-3共 页 第 页VSA1A2B1B2B3Vt0000031110874W(f(4)i-3（3）构造赋权有向图，求最小费用最大流。弧旁数字为（b ij,cij） 。VSA1A2B1B2B3Vt0,130,90,90,60,53,811,710,58,67,34,5取 f(0)=0 为初始可行流。构造赋权有向图 W(f(0)，并求出从 Vs 到 Vt 的最短路（Vs，A 1，B 1，Vt） 。在原网络图中，与这条最短路相应的增广链为 =（Vs，A 1，B 1，Vt） 。在 上进行调整，=8，得 f(1)（图 b）
11、。按照上述算法依次得 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，此时的最小费用为：38+112+110+18+37+54=105。VSA1A2B1B2B3Vt0000031110874W(f(0)aVSA1A2B2B380800800000Vtv(f(1)=8bB1共 页 第 页VSA1A2B1B2B3Vt0000031110874W(f(1)cVSA1A2B2B385850800005Vtv(f(2)=13d-3VSA1A2
12、B1B2B3Vt0000031110874W(f(2)eVSA1A2B2B388853800035Vtv(f(3)=16f-3-4VSA1A2B1B2B3Vt0000031110874W(f(3)gVSA1A2B2B389953800135Vtv(f(4)=17h-3-4-7VSA1A2B1B2B3Vt0000031110874W(f(4)iVSA1A2B2B399963801135Vtv(f(5)=18j-3-4-7共 页 第 页VSA1A2B1B2B3Vt0000031110874W(f(5)kVSA1A2B2B3119965821135Vtv(f(6)=20l-3-4-7VSA1A2B1
13、B2B3Vt0000031110874W(f(6)m-3-4-75、解：（1）设搅拌点的坐标为（X，Y） ，则搅拌点各工点的距离为（i 表示到第 i 个工点）22)()(iii YXd建立该问题的数学模型为： )4,321( )()( s.t n2241 iYXdQf iiiii（2）设搅拌点的坐标为（X，Y） ，则搅拌点到各工点的距离为iii Yd建立该问题的数学模型为： )4,321( s.t mn41 iYXdQfiiii6、解：看做求网络最大流，令已有的弧上的数据为容量。（1）首先给网络赋予初始可行流。 方法不唯一，但不同的初始可行流对应的增广链不同。共 页 第 页1234562，26
14、，43，04，23，0 2，23，31，1 6，33，2（2）用标号法求增广链，开始给 v1 标号（, +） ；于是检查 v2，弧（v1，v2）上，f12=c12 ；检查 v3，给 v3 标号（v1, 1） ；检查 v4，给v4 标号（v3，1） ，由于弧（v4，v2）上，f42=0，弧（v4，v5） 、弧（v4，v5）上可行流等于流量，标号无法继续下去，算法结束。此时的可行流即为最大流。同时可以找到最小截集（ ） ， =， ， =， ，于是（ ）=（v1，v2） ，1,V1V1,V（v4，v2） ， （v4，v5） ， （v3，v6） ， （v4，v6） 是最小截集。则压缩总工期 1 天的压缩方案为：将工序-，工序-，工序-，工序-同时压缩 1 天，此时的最小费用为 2+1+3+2=8.1234562，26，43，04，23，0 2，23，31，1 6，33，2（, +）（v1, 1）（v3, 1）
