运筹学计算题复习.doc

运筹学计算题复习一、第一章线性规划及单纯形法1、 下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，为参数，（1） 试完成该表；（2） 若该表中所示的为问题的最优基，试求的取值范围21-4b3101-12101-1000解：21-4b3101-12101-10003-42、 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。 解：在第二个约束条件两边乘以-1，变为标准形式 的系数列向量，的系数列向量，的系数列向量；的系数列向量（1） 因为线性独立，令非基变量得基本可行解（2） 因为线性独立，令非基变量得基本解（3） 因为线性独立，令非基变量得基本可行解（4） 因为线性独立，令非基变量得基本可行解（5） 因为线性独立，令非基变量得基本解（6） 因为线性独立，令非基变量得基本解比较最大值可知为最大值，故最优解为3、 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相应于图形上哪一个顶点？ S.T.解：（1）图解法，作图如下图所示，由图得唯一最优解，对应于图上的点为，其最优值为。X1X2A3A2A1（2） 单纯形法，引入松驰变量，标准型为 S.T.用单纯形法列表，求解过程见下表21000153510502462014210003041-1/23/42411/301/61201/30-1/313/4011/4-1/8215/410-1/125/2400-1/12-7/24因为，故问题的最优解，其最优目标函数值为4、 建模题：某公司有资金3000万元，六年内有A、B、C、D、E五种投资项目可供选择。其中：项目A从第一年到第六年初均可投资，当年末可获利10%；项目B可在第一年到四年初投资，周期为3年，到期可25%；项目C只能在第二年初投资，周期为3年，到期可获利45%，但规定最大投资额不超过1000万元；项目D只能在第四年初投资，周期为3年，到期可获利40%，但规定最大投资额不超800万元；项目E只能在第五年投资，周期为2年，到期可获利35%，但规定最大投资额不超过500万元。又项目A、B、C、D、E的风险指数分别为0.1，0.2，0.4，0.3，0.1，问：如何确定这些项目的每年投资额，使得第六年末公司获得最大利润？解：建模题用表示第i年投入到 j个项目的资金，则有 目标函数：s.t 二、第二章线性规划的对偶理论与灵敏度分析5、写出线性规划问题的对偶问题 S.T.解：要理清原问题的约束条件与对偶问题变量之间的对应关系，以及原问题的变量与对偶问题的约束条件之间的对应关系，具体见P53原问题中：,原问题的对偶问题为，由可知对偶问题为 S.T.三、第三章运输问题6、求解下列产销平衡的运输问题单位价格表 销地B1 销地B2 销地B3 销地B4产量产地A1产地A2产地A310 5 6 7 8 2 7 69 3 4 8 252550销量 15 20 30 35100（1）用西北角法、最小元素法求初始基本可行解；（2）由上面所得的初始方案出发，应用表上作业法求最优方案。解：（1）西北角法z=665 销地B1 销地B2 销地B3 销地B4产量产地A1产地A2产地A315 10 10 15 15 35252550销量 15 20 30 35100（2）最小元素法z=540 销地B1 销地B2 销地B3 销地B4产量产地A1产地A2产地A3 2520 5 15 30 5 252550销量 15 20 30 35100（3）最优方案：z=535 销地B1 销地B2 销地B3 销地B4产量产地A1产地A2产地A3 25 15 1015 5 30 252550销量 15 20 30 35100四、第四章目标规划7、用图解法解下面的目标规划五、第五章整数规划8、已知甲、乙、丙、丁四人完成四项工作所需时间如下表，求最优分配方案。任务 人员ABCD甲215134乙1041415丙9141613丁78119解： 1）变换系数矩阵，增加0元素。 2）试指派（找独立0元素） 独立0元素的个数为4 , 指派问题的最优指派方案即为甲负责D工作，乙负责B工作，丙负责A工作，丁负责C工作。这样安排能使总的工作时间最少，为4491128六、第八章图与网络分析9、图与网络的基本概念10、树的基本概念七、网络计划11、某工地现场施工准备工作关系及持续时间如表1所示，该工程要在26天内完成，其全部直接费用为30000元，间接费用为5000元，每超过1天，间接费用增加600元。表1工作清单序号工作名称工作代号持续时间/天紧后工作1拆迁A5C、D、E2围墙砌筑B10F、G3场地平整C10H4临时水电施工D8-5工棚搭建E11G6临时道路修筑F18-7搅拌站搭建G6H8生活设施搭建H12-要求：（1）先画出双代号网络图，确定关键线路（2）将表2中的各项工作的3列空格内容计算出来，并填入表中。（3）进行工期费用优化，求出计算工期为26天的总费用和与原计划相比节约的费用 表2工作参数表工作代码工作编号作业时间/天费用/元可缩短时间赶工费用赶工费率（元/天）正常赶工正常赶工A1-2538001200B1-310830003360C2-510715001740D2-68624002800E2-411840004450F3-6181456006160G4-56412001440H5-612102000218012、根据表3给出的资料，绘制双代号网络图，找出关键路线，并简要说明如要缩短工期，应首先考虑哪些工作工作紧前工作持续时间工作紧前工作持续时间ABCDEFGHIJ-AAB,CDDDGHD2114143707014111KLMNOPQRSJDLDNOE,F,PQ,I,KM,R17771411113、某分部工程双代号时标网络计划如图1所示，根据该图确定各项工作的时间参数，请将结果直接填写在表4中相应位置。 图1 双代号时标网络计划表4工作时间参数序号 工作名称 工作代号 ESEFLSLFTFFF备注 1A122B233C274D345E366G457H588I689J7910K89