运筹学试题5论述题

1、运筹学试题5一（40分） 某工厂生产甲、乙、丙三种产品，需消耗A，B两种原料。已知每件产品对这两种原料的消耗，这两种原料的现有数量和每件产品可获得的利润如下表产品单件消耗原料甲乙丙原料限制A63545B34530单件利润（元/件）314（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、巡逻队数预期损失ABCD218382434314352231410312125四动态规划（20分）某厂和公司订了试制某种新产品的合同，如果三个月生产不出一个合格品，则要罚款2000元，每次试制的个数不限，试制周期为一个月，制造一个产品的成本为100元，每一个试制品合格的概率为0.4，生产一次的装配费为200元，问如何安排试制，每次生产几个，才能使期望费用最小？运筹学试题解答和评分标准（若解题步骤正确仅仅数字计算错误可给此题的6090%的分数）一解（1）设甲、乙、丙三种产品的产量为Max Z=3 s.t 化为标准型：Max Z=3 s.t 45306 3 5 1 03 4 5 0 1960 3

4、1 4 0 0取 为入基变量 为出基变量化为标准型 1563 -1 0 1 -13/5 4/5 1 0 1/5-24 3/5 -11/5 0 0 -4/5取 为入基变量 为出基变量化为标准型 531 -1/3 0 1/3 -1/30 1 1 -1/5 2/5-27 0 -2 0 -1/5 -3/5最优值为27，最优解为-10分（2）Min W=s.t -15分（3） A 种原料每增加一个单位对利润为0.2元， B 种原料每增加一个单位对利润为0.6元 所以 B 种原料每增加一个单位对利润大-18分（4） 因为0.40.6所以值得购进原料进行生产，由于将最优解代入第一个不等式可知等式成立，所以A

5、原料已用完所以，B原料购进数为0-20分（5） 求C1的变化范围 -25分（6）值得生产。-30分 （7）求的变化范围 得-35分（8） 20-61 -1/3 0 1/3 -1/30 1 1 -1/5 2/5-36 0 -2 0 -1/5 -3/5为出基变量，为入基变量， 10301 4/3 5/3 0 1/30 -5 -5 1 -2-30 0 -3 -1 0 -1最优解-40分二 （1）迭代法一般步骤：. 选取初始点，. 构造搜索方向. 根据方向确定. 令. 若已满足某终止条件，停止迭代，输出近似最优解。否则令，转向第步。-10分（2）可行方向下降的代数条件：， 。-15分由泰勒公式： 当为

6、的积极约束时，有。只要足够小，和同号，于是当时有。当为的非积极约束时，有。由的连续性，当足够小时，由保号性知。所以只要，就可保证，于是为点处的一个可行方向。称， 为在点处是可行方向的代数条件。由泰勒公式： 。当足够小时，只要，有。称为在点处的一个下降方向的代数条件。-20分（3）可行下降方向代数条件的几何解释：对于，由 ，即与该点处目标函数负梯度向量之间夹角为锐角。同理说明与该点处积极约束的梯度向量之间的夹角成锐角。因此，若，使得和及均为锐角，则为可行下降方向。 -25分三解：把12支巡逻队往4个部位派遣看成依次分四个阶段（用k表示，k=1，2，3，4），sk表示派遣给第k个部位至第4个部位的

7、巡逻队数，uk表示派往第k部位的巡逻队数。 2uk4 允许决策集合：Dk（sk）=2uksk k=1，2，3，4状态转移方程：sk+1 = sk - ukpk(uk) 表示uk个巡逻队派往第k个部位的预期损失值，fk(sk) 表示sk个巡逻队分配给第k个部位至第4个部位所得到的最小预期损失值。 -5分先给D部位派巡逻队，即：k=4 因问题中只有4个要害部位，故第5阶段初拥有的未派出的巡逻队数对前4个部位的预期损失不再有影响，故边界条件f5(s5) =0， 因此， 有。 因D4（s4）= 2u4s4 ，又s4的可能值为2s46，u4s4p4（u4）f4（s4）u4*234234342334313

8、13434312525453431252546343125254k=3 ， 4s38， u3s3p3（u3）+ f4（s3- u3）f3（s3）u3*234424+34=58582524+31=5522+34=56552624+25=4922+31=5321+34=55492724+25=4922+25=4721+31=52473824+25=4922+25=4721+25=46464k=2 ，8s210， u2s2p 2（u2）+ f3（s2- u2）f2（s2）u2*234838+49=8735+55=9031+58=89872938+47=8535+49=8431+55=86843103

9、8+46=8435+47=8231+49=80804 k=1 u1s1p1（u1）+ f2（s1- u1）f1（s1）u1*2341218+80=9814+84=9810+87=97974 回代可得 s1=12， u1*=4； s2=8， u2*=2；s3=6， u3*=2； s4=4， u4*=4 总预期损失最小为97单位。-15分四根据题意，最多能安排三次生产，把三次试制当作三个阶段，每次生产的个数作为决策变量u，每次试制前是否已有合格品作为状态变量sk，有合格品时，记sk =0，无合格品时记sk =1，fk（sk）为第k次试制前的状态为sk时，以后均采取最优策略时的最低期望成本。（为简化

10、数字，以百元为单位）。由假设当sk =0，即已有合格品，试制已完成，于是fk(0) =0，即不生产，也不罚款，就没有费用，又若三次试制后无合格品，则罚款20，即f4(1) =20，以C（uk）表示生产成本及装配费用，则由每次装配费200元，每件成本100元，得： 由生产一件合格品的概率为0.4，得不合格品的概率为0.6，所以生产uk件均不合格的概率为至少有一件合格品的概率为（1-），这里uk=0，1，2，于是递推关系为：=-10分其中 ，Dk（1）= 0，1，2， 于是有：k=3 ， 对u3的不同取值计算得u3s3f3（s3）u30123456700？001201511.29.328.598.568.938.565k=2 ， 对u2的不同取值计算得表u2s2f2（s2）u20123400001