运筹学试题6

《运筹学》期终试题6一．（10分）用动态规划求解)3,2,1(010342294max3212321jxxxxstxxxzj二．（15分）整数规划某公司打算在三个不同的地区设置5个销售点，根据市场预测，在不同地区设置不同数量的销售点，每月可得的利润如下表，试问在各地区应如何设置销售点，才能使每月获得的总利润最大？其最大利润为多少？销售点地区01234510671115182071215232430914192123三．（10分）用共扼梯度法求下面问题2212121252),(minxxxxxf取初始点Tx)2,2(0,终止误差为610四．（10分）用外点法求解下列问题2221)1()(minxxxf..ts12x五．（15分）如下表已知三个产地A、B、C，四个销售地点D、E、F、G，产销量及单位运价表如下表，a)求使总运费最小的调运方案，b)C32为何值时有无穷多最优调运方案？c)C33为何值时最优调运方案不变？销地产地DEFG产量A2237500B4359600C1678300销量300200500400六．（40分）某工厂生产甲、乙、丙三种产品，需消耗A，B两种原料。已知每件产品对这两种原料的消耗，这两种原料的现有数量和每件产品可获得的利润如下表甲乙丙原料限制A14248产品单件消耗原料B12460单件利润（元/件）61413（1）如何安排生产计划，使总利润最大。试建立线性规划模型，并用单纯形法求最优生产计划。（2）写出对偶问题，写出对偶问题的解。（3）最优生产计划中哪一种原料每增加一个单位对利润的贡献大，为什么？（4）现在原料B的市场价格为5，问是否值得购进原料扩大生产？（5）求最优计划不变，产品（甲）单件利润的变化范围。（6）保持最优基不变，求A原料现有数量的变化范围。（7）若A原料的数量为68求最优生产计划。《运筹学》期终试题解答和评分标准（如果计算错误而方法正确可给60—90%的分数）一．解：有三个变量划分三个阶段，kx表示K个阶段得决策变量ks表示第K个阶段到第四个阶段的产品消耗的资源数kkkkkkkasxxass0,10)(,)()()(44110maxsfsfxgsfkkkksxkkkk-------------------3分3k时，232330339202)(max33sxsfsx，333sx，2234xss2k时，4,49929)(2222324/022max22sxssxsfsx1k时0,49)(4)(112212/011max11xssfxsfsx01x，2/45)10(,0,2/5132fzxx为最优解和最优值-----------10分二．解：有三个地区划分三个阶段，kx表示K个阶段的销售点个数ks表示第K个阶段到第四个阶段的销售点个数之和kkkkksxxss0,10)(,)()()(44110maxsfsfxgsfkkkksxkkkk---------------------------------5分3k时f3x3s)()(4433sfxg)(33sf*3x4s012345012345000000999991414141419191921212309141921230123450000002k时f2x2s)()(3322sfxg)(22sf*2x3s0123450123450+00+90+140+190+210+237+07+97+147+197+2112+012+912+1412+1915+015+915+1423+023+924+009162126320011、21、240112、13、211k时f1x1s)()(2211sfxg)(11sf*1x2s01234550+326+267+2111+1615+918+0320、15、4最优解为)3,1,1(*x或)2,2,1(*x或)1,4,0(*x，最优值为32------------------------------------------------15分三、解：TTxxxfxfxf)50,22(),()(2121Tx)2,2(0Txf)100,2()(0取Tp)100,2(0由10022210022200px4)22(2)1002(25)22()(2200pxf得0)1002(5000)22(4ddf020007679.05000081000800007679.0959984642.11002020007679.0220001pxx---------------------4分Txf)038395.0,919969284.1()(1000368628.010004687756228.3||)(||||)(||20210xfxf0015322.092070654.11002000368628.0038395.0919969284.1)(0011pxfp0015322.00007679.092070654.1959984642.111px0378228399.7687703443.3)(11dpxdf499808794.0101000002092.0999998622.00015322.0499808794.00007679.0)92070654.1(499808794.0959984642.11112pxx0||)(||2xf,最优解012*xx-------------------------10分四．解．定义惩罚函数222221))1(,0(min(1)1(),(xrxxrxG1,)1(1)1(1,)1(222222122221xxrxxxxx-----------------------------------7分令0,021xGxG得111rxr，0r时11x为最优解------------15分五．（1）用最小元素法求得初始基本可行解为20012x，20013x，20023x，40024x，30031x，034x81953,2431342323121vuvuvuvuvuvu得73101204321321vvvvuuu因为1222222cr得闭回路12132322xxxx得调整后基本可行解为20022x，50013x，023x，40024x，30031x，034x由位势法知为最优解。----------------------------------------------------------------------10分（2）0113232cr知232c时有无穷多最优解------------------------------12分（3）因为33x不是基变量，所以0133333cr即433c时最优解不变。---15分六．解（1）设甲、乙、丙三种产品的产量为321,,xxxMaxZ=32113146xxxs.t0,,60424824321321321xxxxxxxxx化为标准型：Z=32113146xxxs.t0,,,,604248245432153214321xxxxxxxxxxxxxBxb1x2x3x4x5x4x5x4860142101240106141300Bxb1x2x3x4x5x1x361602-13x60-11-1/21/2-2940-90-11/2-1/2最优值为294，最优解为Tx)6,0,36(*------------------------------------------------------10分（2）MinW=216048yys.t0,13421424621212121yyyyyyyyTy)2/1,2/11(------------------------------------------------------------15分（3）A种原料每增加一个单位对利润为11/2元，B种原料每增加一个单位对利润为1/2元所以A种原料每增加一个单位对利润大------------------18分（4）因为1/25所以不值得购进原料进行生产，-------------20分（5）求C1的变化范围016)13,(1412122cpBccrB02/12)13,(014144cpBccrB02/11)13,(015155cpBccrB2/132/91c---------------------------------------------------------------25分（6）求1b的变化范围0602/12/11211bbB得60301b----------------------30分（7）Bxb1x2x3x4x5x1x3x76-41602-10-11-1/21/2-4040-90-11/2-1/2Bxb1x2x3x4x5x1x2x524106-1201-11/2-1/2-36800-9-1-5最优解Tx)0,4,52(*-----------------------------------------------------------------------40分