1、运筹学试题 5一 （40 分） 某工厂生产甲、乙、丙三种产品，需消耗 A，B 两种原料。已知每件产品对这两种原料的消耗，这两种原料的现有数量和每件产品可获得的利润如下表甲 乙 丙 原料限制A 6 3 5 45B 3 4 5 30单件利润（元/件） 3 1 4（1） 如何安排生产计划，使总利润最大。试建立线性规划模型，并用单纯形法求最优生产计划。（2） 写出对偶问题，写出对偶问题的解。（3） 最优生产计划中哪一种原料每增加一个单位对利润的贡献大，为什么？（4） 若现在原料 B 的市场价格为 0.4，问是否值得购进原料扩大生产？按照目前最优生产计划，在 A 资源不变的情况下,购多少原料 B？（5）
2、 求最优计划不变，产品（甲）单件利润的变化范围。（6） 若新产品（丁）的单位消耗为 8、2，单件利润为 3，问产品（丁）是否值得生产？（7） 保持最优基不变，求 A 原料现有数量的变化范围。（8） 若 A 原料变为 90 求最优生产计划。二 （25 分） （1）叙述（MP）问题的迭代法的一般步骤；（2）写出可行下降方向的代数条件，并证明；（3）可行下降方向代数条件的几何解释。三 整数规划 （15 分）某一警卫部门共有 12 支巡逻队，负责 4 个要害部位A，B，C ，D 的警卫巡逻，对每个部位可分别派出 24 支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具
3、体见下表，问该警卫部门应往各部位分别派出多少支巡逻队使总的预期损失为最小？预期损失部位巡逻队数 A B C D2 18 38 24 343 14 35 22 31产品单 件消 耗原 料4 10 31 21 25四 动态规划 （20 分）某厂和公司订了试制某种新产品的合同，如果三个月生产不出一个合格品，则要罚款 2000 元，每次试制的个数不限，试制周期为一个月，制造一个产品的成本为 100 元，每一个试制品合格的概率为 0.4，生产一次的装配费为 200 元，问如何安排试制，每次生产几个，才能使期望费用最小？运筹学试题解答和评分标准（若解题步骤正确仅仅数字计算错误可给此题的 6090%的分数）
4、一解（1）设甲、乙、丙三种产品的产量为 321,xMax Z=3 3214xs.t 0,56321x化为标准型：Max Z=3 3214xs.t 0,5436213xxBb234x545x45306 3 5 1 03 4 5 0 1960 3 1 4 0 0取 为入基变量 为出基变量化为标准型43x5xBxb234x5431563 -1 0 1 -13/5 4/5 1 0 1/5-24 3/5 -11/5 0 0 -4/5取 为入基变量 为出基变量化为标准型5/11x4xBxb2345x13531 -1/3 0 1/3 -1/30 1 1 -1/5 2/5-27 0 -2 0 -1/5 -3/
5、5最优值为 27，最优解为 -Tx)3,5(*-10 分（2）Min W= 213045ys.t 0,362121y-15 分T)5/3,(（3） A 种原料每增加一个单位对利润为 0.2 元，B 种原料每增加一个单位对利润为 0.6 元所以 B 种原料每增加一个单位对利润大 -18 分（4） 因为 0.40.6 所以值得购进原料进行生产，由于将最优解代入第一个不等式可知等式成立，所以 A 原料已用完所以，B 原料购进数为 0-20 分（5） 求 C1 的变化范围013/)4,(22 cpBcr5/),(01414B0/23),(1515 cpcrB-25 分/24/1（6） 3,86cp值0
6、5/143285/1/)4,(616 Br得生产。-30分（7）求 的变化范围1b得 -035/21/1bbB6031b35 分（8） Bxb1x23x45x1320-61 -1/3 0 1/3 -1/30 1 1 -1/5 2/5-36 0 -2 0 -1/5 -3/5为出基变量， 为入基变量，3x4xBb12x34x51410301 4/3 5/3 0 1/30 -5 -5 1 -2-30 0 -3 -1 0 -1最优解 -40 分Tx),(*二 （1）迭代法一般步骤：. 选取初始点 ，0x:k. 构造搜索方向 p. 根据 方向确定kk. 令 x1. 若 已满足某终止条件，停止迭代，输出近
7、似最优解 。否则k 1kx令 ，转向第步。-10 分:（2）可行方向下降的代数条件： ， 0)(pxgTi )(xIi。-15 分f由泰勒公式：|)()()( pxgpxgTiii 当 为 的积极约束时，有 。只要 足够小，)i 0i 和 同号，于是当 时有 (xixTi()(xTi 0)(pxgi。)I当 为 的非积极约束时，有 。由 的连续性，当 足x(gi 0)(xgi )(xi 够小时，由保号性知 。)(pxiI所以只要 ， 就可保证 ，于是 为0)Ti (xi0)(pxi p点处的一个可行方向。x称 ， 为 在点 处是可行方向的代数条件。)(pxgTi )(xIipx由泰勒公式：。|
8、)()()(fff T当 足够小时，只要 ，有 。0px)(xfpxf称 为 在 点处的一个下降方向的代数条件。-0)(pxfT-20 分（3）可行下降方向代数条件的几何解释：对于 ，0)()(pxfxfTT由 ，即 与该点cos|p 09p处目标函数负梯度向量之间夹角为锐角。同理 说明 与该点处积极约束的梯度向量之间的夹角成锐0)(xgTi p角。因此，若 ，使得 和 及 均为锐角，则 为可行下降方pTxf)(Tig)(p向。-25 分三解：把 12 支巡逻队往 4 个部位派遣看成依次分四个阶段（用 k 表示，k=1，2，3，4） ，s k 表示派遣给第 k 个部位至第 4 个部位的巡逻队数
9、，u k 表示派往第 k 部位的巡逻队数。 2u k4 允许决策集合：D k（s k）=2u ks k k=1，2，3， 4状态转移方程：s k+1 = sk - ukpk(uk) 表示 uk 个巡逻队派往第 k 个部位的预期损失值，f k(sk) 表示 sk 个巡逻队分配给第 k 个部位至第 4 个部位所得到的最小预期损失值。-()(min)( 1)( kksDuk sfpsfk-5 分先给 D 部位派巡逻队，即：k=4 )(i)( 54)(44sfsfsDu因问题中只有 4 个要害部位，故第 5 阶段初拥有的未派出的巡逻队数对前 4 个部位的预期损失不再有影响，故边界条件 f5(s5) =
10、0， 因此， 有。 因 D4（s 4）= 2u 4s 4 ，又 s4 的可能值为)(min)(4)(44psfsDu2s 46，p4（u 4）u4s4 2 3 4 f4（s 4） u4*2 34 34 23 34 31 31 34 34 31 25 25 45 34 31 25 25 46 34 31 25 25 4k=3 ， 4s 38， )(min)(43)(33fupsfsDup3（u 3）+ f4（s 3- u3）u3s3 2 3 4 f3（s 3） u3*4 24+34=58 58 25 24+31=55 22+34=56 55 26 24+25=49 22+31=53 21+34=
11、55 49 27 24+25=49 22+25=47 21+31=52 47 38 24+25=49 22+25=47 21+25=46 46 4k=2 ，8s 210， )(min)( 32)(22fupsfSDup 2（u 2）+ f3（s 2- u2）u2s2 2 3 4 f2（s 2） u2*8 38+49=87 35+55=90 31+58=89 87 29 38+47=85 35+49=84 31+55=86 84 310 38+46=84 35+47=82 31+49=80 80 4k=1 )(min)12( 21)2(11sfupfsfDup1（u 1）+ f2（s 1- u1
12、）u1s1 2 3 4 f1（s 1） u1*12 18+80=98 14+84=98 10+87=97 97 4 回代可得 s1=12， u1*=4； s2=8， u2*=2；s3=6， u3*=2； s4=4， u4*=4 总预期损失最小为 97 单位。-15 分四根据题意，最多能安排三次生产，把三次试制当作三个阶段，每次生产的个数作为决策变量 u，每次试制前是否已有合格品作为状态变量 sk，有合格品时，记 sk =0，无合格品时记 sk =1，f k（s k）为第 k 次试制前的状态为 sk 时，以后均采取最优策略时的最低期望成本。 （为简化数字，以百元为单位） 。由假设当 sk =0，
13、即已有合格品，试制已完成，于是 fk(0) =0，即不生产，也不罚款，就没有费用，又若三次试制后无合格品，则罚款 20，即 f4(1) =20， ，以C（u k）表示生产成本及装配费用，则由每次装配费 200 元，每件成本 100 元，得：02)(kk 0ku当 当由生产一件合格品的概率为 0.4，得不合格品的概率为 0.6，所以生产 uk 件均不合格的概率为 至少有一件合格品的概率为（1- ） ，这里 uk=0，1，2，于ku6. ku6.0是递推关系为： )1(kf)1(minkDu)(.)(6.0( 11kukuk ffC= -10 分)1(minkDu)1(6.0kukfC其中 ，D
14、k（1）= 0，1，2 ， 于是有：k=3 ， 6.0)(in3)33 kuDuf 对 u3 的不同取值计算得 3.*2)(3ucu3s3 0 1 2 3 4 5 6 7f3（s 3） u30 0 0 01 20 15 11.2 9.32 8.59 8.56 8.93 ？ 8.56 5k=2 ， 对 u2 的不同取值计算得表.068)(min)( 22)12 uDuCf 2.*5ucu2s2 0 1 2 3 4f2（s 2） u20 0 0 01 8.56 8.14 7.08 6.85 7.11 6.85 3k=1 ， 6.085)(min)( 11) uDuCf 对 u1 的不同取值计算得表 1.*)(1ucu1s1 0 1 2 3f1（s 1） u11 6.85 7.11 6.46 6.48 6.46 2最优策略是第一次生产 2 个，如果都不合格，则第二次生产 3 个，如果再都不合格，则第三次生产 5 个，这样能使期望值费用最小，其期望费用为 646 元（近似值） 。-20 分
