课程名称： 运筹学（ⅱ）课程编号课程类型：√学位课、非学位课考试方式： 闭卷
学科专业、领域： 管理科学与工程所在学院： 经济管理任课教师： 刘俊娥
河北工程大学研究生2007～ 2008学年第二学期考试试卷（ ）卷。
1、求解无约束极值问题的下降类一般步骤有哪些？试例举三种你所了解的下降类算法名称。
2、任选一种一维搜索的算法，请写出关于极值点求解的过程。
3、某工厂生产k种不同花色和款式的衬衣，在一定时期内生产量y相同，但根据经验或**，投入市场后顾客对不同品种的需求量qi却不同；有的畅销，有的滞销，过去工厂对产品**均按边际销售成本定价，即， 其中c=c(q1,q2,……qk)是销售成本。现工厂考虑；为了获得最大利润，应不应该将畅销品种的**提高？若要提高，提高多少为宜？
建立数学型并用k—t条件求解。
4、某种货物由2个仓库a1，a2运送到3个配送中心b1，b2，b3。a1，a2的库存量分别为每天13吨、9吨；b1，b2，b3每天的需求分别为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(k0
上，通过选定步长（因子）λ=k，得下一个迭代点
x(k+1)=x(k)+λkp(k)
使得。f(x(k+1))=f(x(k)+λkp(k)) 4）检验得到的点是否为要求的极小点或者近似极小点，如满足要求，迭代停止。否则，令k:=k+1返回第二步继续迭代。 下降类算法包括：（1）梯度法（最速下降法）（2）牛顿法（3）共轭梯度法（4）变尺度法。 2、解：斐波那契算法。 1）确定试点个数n 根据缩短率δ≥ 1/ fn得到fn 或区间精度η, fn ≥ b0-a0)/ 查表得n。 或迭代得到n，迭代的算法如下： 计算fn ≥ b0-a0)/ 或fn ≥ 1/ δ得fn' n=1， f0=f1=1转 ② n=n+1, fn=fn-2+fn-1转③ 若fn< fn'，则转②否则停止，得到n k=1 2）选取前两个试点的位置。 3）计算函数值f(xk')f(xk")并比较其大小。 若f(xk')并令。 或。否则，取ak=xk',bk=bk-1,xk+1'=xk"并令。 k=k+14)若k≠n-2,则转（3），否则。 若f(xk')若f(xk')>f(xk"),则ak=xk',bk=bk-1 比较函数值f(xk+1'),f(xk+1" )的大小，得到函数y=f(x)的极小值和极小点，从而得到最终区间[ak,xk+1" ]或[ak,xk+1"] 3、解： 转化为。 设k-t点为，各函数的梯度为： 对k个约束条件分别引入广义拉格朗日乘子，则该问题的k-t条件如下： 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）构造赋权有向图，求最小费用流，cij表示由ai到bj的流量（i=1,2；j=1,2,3）,则令cij为∞，将该问题转化为最小费用最大流问题。最小费用为：9×3+2×11+3×7+4×6=94 3）构造赋权有向图，求最小费用最大流。弧旁数字为（bij,cij）。 取f(0)=0为初始可行流。 构造赋权有向图w(f(0))，并求出从vs到vt的最短路（vs，a1，b1，vt）。 在原网络图中，与这条最短路相应的增广链为=（vs，a1，b1，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。 5、解：（1）设搅拌点的坐标为（x，y），则搅拌点各工点的距离为。 i表示到第i个工点） 建立该问题的数学模型为： 2）设搅拌点的坐标为（x，y），则搅拌点到各工点的距离为。 建立该问题的数学模型为： 6、解：看做求网络最大流，令已有的弧上的数据为容量。 1）首先给网络赋予初始可行流。方法不唯一，但不同的初始可行流对应的增广链不同。 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），（v4，v2），（v4，v5），（v3，v6），（v4，v6）｝是最小截集。 则压缩总工期1天的压缩方案为：将工序①-②工序③-⑥工序④-⑤工序④-⑥同时压缩1天，此时的最小费用为2+1+3+2=8. 注 1 教师命题时题目之间不留空白 2 考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请另附该试题图。3 请在试卷类型 考试方式后打勾注明。第 1 页 注 1 教师命题时题目之间不留空白 2 考生不得在试题纸上答题，教师只批阅答题册正面部分，若考生须在试题图上作解答，请... 中国计量学院200 200 学年第一学期。运筹学 课程。试卷 e 参 及评分标准。开课二级学院 经管学院 学生班级教师 一 填空题 20分，每题2分 1 ica 2 f 3 abcdefghij 4 ihfe 5 x4 6 x2 x3 x4 7 x1 x5 8 x3 x5 9 y3 10 y1 y2... 一 解 1.20分 用两阶段法解该问题，第一阶段，先求解下述辅助规划问题 max w x6 2x1 4x2 x3 x4 8 2x1 x2 2x3 x5 x6 4 xj0,j 1,6 列单纯形表求解 x1换入 x6 换出 j0，且基变量中不含非零人工变量，得到原问题的一个基可行解。转第二阶段。第二阶段...运筹学试卷和答案
运筹学试卷E答案
《运筹学》试卷10 答案