运筹学计算题复习

运筹学计算题复习一、第一章线性规划及单纯形法1、下表是某求极大化线性规划问题时得到的单纯形表，表中无任何松驰变量，为参数，（1）试完成该表；（2）若该表中所示的21,xx为问题的最优基，试求的取值范围jC21-4BcBxb1x2x3x4x1x3101-122x101-10jjzc00解：jC21-4BcBxb1x2x3x4x1x3101-122x101-10jjzc003--4432、在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。Max43217432xxxxz0,,,37628432..432143214321xxxxxxxxxxxxts解：在第二个约束条件两边乘以-1，变为标准形式Max43217432xxxxz0,,,37628432..432143214321xxxxxxxxxxxxts1x的系数列向量121p，2x的系数列向量232p，3x的系数列向量613p；4x的系数列向量744p（1）因为21,PP线性独立，令非基变量0,43xx得2121xx基本可行解8,0,0,2,11)1(ZXT（2）因为31,PP线性独立，令非基变量0,42xx得131413451xx基本解TX0,1314,0,1345)2(（3）因为41,PP线性独立，令非基变量0,32xx得5753441xx基本可行解5117,57,0,0,534)3(ZXT（4）因为32,PP线性独立，令非基变量0,41xx得167164532xx基本可行解16163,0,167,1645,0)4(ZXT（5）因为42,PP线性独立，令非基变量0,31xx得297296842xx基本解TX297,0,2968,0)5(（6）因为43,PP线性独立，令非基变量0,21xx得3145316843xx基本解TX3145,3168,0,0)5(比较最大值431,,ZZZ可知51173Z为最大值，故最优解为5117,57,0,0,534)3(ZXT3、分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相应于图形上哪一个顶点？Max212xxzS.T.0,24261553212121xxxxxx解：（1）图解法，作图如下图所示，由图得唯一最优解TX)43,415(*，对应于图上的点为2A，其最优值为433*z。155321xxX1X2A3A2A1242621xx（2）单纯形法，引入松驰变量0,43xx，标准型为Max212xxzS.T.0,,,242615534321421321xxxxxxxxxx用单纯形法列表，求解过程见下表jC2100iBCBXb1x2x3x4x03x153510504x2462014j210003x3041-1/23/421x411/301/612j01/30-1/312x3/4011/4-1/821x15/410-1/125/24j00-1/12-7/24因为4,3,2,10jj，故问题的最优解TX)0,0,43,415(*，其最优目标函数值为433*z4、建模题：某公司有资金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，问：如何确定这些项目的每年投资额，使得第六年末公司获得最大利润？解：建模题用ijx表示第i年投入到j个项目的资金，则有61555144424132312322211211654321xxxxxxxxxxxxxEDCBA目标函数：5544426135.14.125.11.1maxxxxxzs.t055442323325161224155511231444241213231112322211211600800,100045.125.11.125.11.125.11.11.11.13000ijxxxxxxxxxxxxxxxxxxxxxxxxxx二、第二章线性规划的对偶理论与灵敏度分析5、写出线性规划问题的对偶问题Max321326xxxzS.T.0,,4422232131321xxxxxxxx解：要理清原问题的约束条件与对偶问题变量之间的对应关系，以及原问题的变量与对偶问题的约束条件之间的对应关系，具体见P53原问题中：3,2,6C,401212A,42b原问题的对偶问题为min21214242,yyyyYb211212142,,2401212,yyyyyyyYA，由3,2,6C可知对偶问题为min2142yyS.T.0,3422622121121yyyyyyy三、第三章运输问题6、求解下列产销平衡的运输问题单位价格表销地B1销地B2销地B3销地B4产量产地A1产地A2产地A31056782769348252550销量15203035100（1）用西北角法、最小元素法求初始基本可行解；（2）由上面所得的初始方案出发，应用表上作业法求最优方案。解：（1）西北角法z=665销地B1销地B2销地B3销地B4产量产地A1产地A2产地A3151010151535252550销量15203035100（2）最小元素法z=540销地B1销地B2销地B3销地B4产量产地A1产地A2产地A32520515305252550销量15203035100（3）最优方案：z=535销地B1销地B2销地B3销地B4产量产地A1产地A2产地A325151015530252550销量15203035100四、第四章目标规划7、用图解法解下面的目标规划五、第五章整数规划8、已知甲、乙、丙、丁四人完成四项工作所需时间如下表，求最优分配方案。任务人员ABCD甲215134乙1041415丙9141613丁78119解：1）变换系数矩阵，增加0元素。2）试指派（找独立0元素）独立0元素的个数为4,指派问题的最优指派方案即为甲负责D工作，乙负责B工作，丙负责A工作，丁负责C工作。这样安排能使总的工作时间最少，为4＋4＋9＋11＝28六、第八章图与网络分析9、图与网络的基本概念10、树的基本概念七、网络计划794291187131614915144104131522424104750111006211130001023509606071300010235096060713011、某工地现场施工准备工作关系及持续时间如表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给出的资料，绘制双代号网络图，找出关键路线，并简要说明如要缩短工期，应首先考虑哪些工作工作紧前工作持续时间工作紧前工作持续时间ABCD-----AAB,C2114143KLMNJDLD1777EFGHIJDDDGHD707014111OPQRSNOE,F,PQ,I,KM,R1411113、某分部工程双代号时标网络计划如图1所示，根据该图确定各项工作的时间参数，请将结果直接填写在表4中相应位置。图1双代号时标网络计划表4工作时间参数序号工作名称工作代号ESEFLSLFTFFF备注1A1—22B2—33C2—74D3—45E3—66G4—57H5—88I6—89J7—910K8—9