《运筹学》综合复习资料.doc

运筹学综合复习资料一、 判断下述说法是否正确(划 ，)1. LP问题的基本解对应可行域的顶点。2. LP问题若有两个最优解，则它一定有无穷多个最优解。3.目标规划问题不会出现无解的情况。4.线性规划模型中增加一个约束条件，可行域的范围一般将缩小，反之，一般将扩大。5.求解LP问题时,对取值无约束的自由变量，通常令,其中,在用单纯形法求得的最优解中,有可能同时出现.6动态规划的最优性原理保证了从某一状态开始的未来决策独立于先前已作出的决策7对于同一个动态规划问题，逆序法与顺序法的解不一样8PERT计算中，总时差是线路上的时差，可以串用，但单时差是工序的时差，不能串用9在PERT计算中，将最早节点时刻等于最迟节点时刻、且满足节点连接而成的线路是关键线路10在一个随机服务系统中，当其输入过程是一普阿松流时，即有，则同一时间区间内，相继两名顾客到达的时间间隔是相互独立且服从参数为的负指数分布，即有二、建立模型1.靠近某河流有两个化工厂(见附图)，流经第一个工厂的河流流量是每天500万立方米；在两个工厂之间有一条流量为每天200万立方米的支流。第一个工厂每天排放工业污水2万立方米；第二个工厂每天排放工业污水1.4万立方米 。从第一个工厂排出的污水流到第二个工厂之前，有20%可自然净化。根据环保要求，河流中工业污水的含量不应大于0.2%，若这两个工厂都各自处理一部分污水，第一个工厂的处理成本是1000元/万立方米，第二个工厂的处理成本是800元/万立方米。试问在满足环保要求的条件下，每厂各应处理多少污水，才能使总的污水处理费用为最小?建立线性规划模型。工厂2工厂1三、计算回答（一）某LP模型为 单纯形表已解至如下表:9x18x250x319x40s10s2b x424/3012/3-10/3 2 x3-1/2-1/310-1/64/3 1ZjCj - Zj1. 填上表中尚缺数据并回答该问题的最优解,最优目标函数值2. 当模型中第一个约束条件右端常数由18 改为19 时,最优基是否发生变化？(要计算过程)3. 写出该问题的对偶规划并回答对偶问题的最优解。4. 回答是否要购入第一、第二种资源，如购入可接受的最高市场价格是多少？（二）某公司计划制造、两种家电产品，已知各制造一件时分别占用的设备A、B的台时、调试时间及每天可用的设备能力和单件产品的获利情况如下表：每天可用能力设备A（小时）0515设备B（小时）6224调试工序（小时）115利润（元）211.建立获利最大的线性规划模型并求解（可不考虑整数要求，）2.该公司计划推出新型号的家电产品，生产一件所需设备A、B及调试工序的时间分别为3、4、2小时，该产品单件获利3元，试判断且仅判断该产品是否值得生产？ 3.对第一问中获利最大的线性规划模型建立其对偶规划模型，并回答其最优解和说明该公司的短缺资源是哪些？ 四、（一）石油公司所属某仪器厂按合同向勘探单位提供地震勘探仪器，在计划年度内各季度的合同交货量、该厂的生产能力、生产成本及成品库中的维护与保管成本数据如下表，试：建立总成本最低的生产计划模型；并用表上作业法求解一步。季度合同交货（台）生产能力（台）生产成本（千元/台）保管成本（千元/台季）110251031.5215351111.5325301101.5420101131.5（二）甲、乙、丙、丁四人完成下述四项工作的时间各不相同，如下表所示。已知每人能且只能承担一项工作，问应如何分配，方使完成这四项工作总的花费时间最少。 工作人甲791012乙13121617丙15161415丁11121516（三）某工厂使用一台设备，其在不同使用役龄下的维修费、残值及该设备不同年份的购置费如下表，试制定一个使总支出最少的5年更新计划。项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210五、（一）某企业有某种高效率设备3 台，拟分配给所属甲、乙、丙车间，各车间得到设备后，获利情况如下表，试建立最优分配方案 工厂 获利甲乙丙设备台数0000135427106391111（二）某人每天从住处开车至工作地上班，每天早上他总得超速开车；下图是其可能行车路线，各段线路可能遇到警察的概率如下表，试为此公选择一条碰到警察概率最小的行车路线。1234567边概率边概率边概率120.2240.8450.4130.9340.1460.35230.6350.3570.25670.5参考答案：一、判断题号12345678910答案xxx二、1. 设两厂处理的污水量分别为x1,x2三、（一）1.9x18x250x319x40s10s2b19 x424/3012/3-10/3 250 x3-1/2-1/310-1/64/3 1ZjCj - Zj13-426/3-2/3000013/3-13/310/3-10/3882.最优基不变。3. y1=13/3 y2=10/3 4.应该购入，价格上限即y1=13/3 y2=10/3。（二）1.CBXB21000bX1X2S1S2S30s10015/4-15/215/22x11001/4-1/27/21X2010-1/43/23/2机会成本2101/41/217/2检验数000-1/4-1/22. ，故产品值得生产。3. ，短缺资源为设备B与调试工序。四、（一）设xij为i季度生产j季度交货的仪器台数1234虚交生产能力1(10) 103（15） 104.5（0） 106107.50252111112.5