发布时间 : 星期一 文章清华846运筹学历年真题更新完毕开始阅读
对下列各题做简要回答(每小题5分)
1.1对形如max：{CX|AX≤b,X≥0}线性规划，写出其对偶解与检验数（递减成本）的表达式，并解释它们的经济含义。
1.2比较求解线性规划的单纯形法及内点法的优缺点。 1.3简述互补松弛定理的内容，并解释其经济含义。 1.4写出min{f(x)|g(x)≥0,x≥0}的K—T最优条件。 1.5为什么说运输问题是线性规划的一个特例。 1.6写出线性规划的对偶问题：max CX ST.{a≤AX≤b l≤X≤u}
2（本题20分）某一线性规划的目标函数表达式为max z=ax1+x2+2x3,其约束条件均为≤型的不等式。且已知x4,x5,x6为松弛变量，某一步的单纯形表如下
Cj
X1
Cb Xb B-1b
X2 X3 X4 X5 X6
X3
2 -4/3
X5 5
5/2 3 2 0
X1 0
0 1/3
Z=4
-1 0
（1）
补充该单纯形表使之成为完整的单纯形表格。（不用逐次迭代的方法） （2）
写出当前的B-1b
（3）求a的取值范围，使该表格的最优解不变
（4）当a的取值不为该表最优解时，下一步迭代会使目标函数值改进吗？说明理由？
3（本题20分）某单位在未来四年内使用一台机器,该种机器的年收入为R,年运行费用为U,更新费用为C,随机器的役龄变化如下表所示,
0 5 0.5 0.5
1 4.5 1 1.5
2 4 1.5 2.2
3 3.5 2.2 3
R U C
试制订最优的更新计划,以使四年内的总利润最大(不计五年期末时机器的残值).试用动态规划计算该问题，并写出状态转移方程和损益方程。
4（本题20分）某汽车修理店，来修理的汽车按泊松分布到达，平均每小时4辆，修理时间服从负指数分布，每辆汽车需要修理6分钟。（1）求该汽车店里无汽车修理的概率（2）该汽车修理店里只有一辆汽车修理的概率（3）求该汽车修理店内汽车的数量。
5(25分)已知一计算机厂商开发一种计算机软件，需要一种磁盘驱动器。而该磁盘驱动器需要外包，公司决定采用竟标的方式来选择开发公司，本公司将提供25万元的开发费用给中标的公司作为开发资金。某一开发公司的管理层决定竟标，并初步预算设计一份标书需要5万元，并估计有50%可能赢的合同。赢的合同后，仍然有许多不确定因素，因此公司管理层有三种开发方案：第一种方案为采用机器方案，其成本为12万元，该开发方案一定能成功。第二种方案为电子磁盘方案，其成本为5万元，但是开发成功的希望为50%。第三种方案为电磁磁盘方案，其成本为8万元，开发成功率为70%。该公司有充足的开发时间，如果某种方案失败后可以采用另外一种开发方案（如可以先用电子磁盘方案或者电磁磁盘方案，若失败了，第二次必须采用机械方案以保证开发的成功），同一时间内只能取一种方案，但是两次尝试时间。该公司决定采用决策树方法来决定是否参加竟标，当中标后，采用何种开发方案以使总收益最大？
（1）画出该问题的决策树（2）找出最优策略及期望收益？
（3）最优方案风险（期望表标准差）（4）若该公司赢的合同就直接采用机械方案，计算该策略的风险和收益
6(20分)某省政府计划在所辖地区内新建粮食仓库，从投资预算限制角度出发，考虑最多新建m个粮食仓库。这m个粮食仓库将为n个城市供应粮食，n个城市对粮食的需求分别为D1,D2……Dn。各城市都提出建设粮食仓库的申请，若在第i个城市建仓库，其存储能力上限为Si（允许建设粮食仓库的规模小于Si），建设的固定投资费用为Fi，建设单位存储能力的变动投资为Vi（变动投资与建设规模成正比）此外在i处建设需改造它与其它城市间的运输设施。改造i城市到j城市的运输设施的投资费用为Fij，改造前从第i个城市到第j个城市的最大运输能力为uij，而改造后为Uij。设在这些粮食仓库的整个使用寿命期间内，各城市的单位运价为Cij。问m个粮食仓库建设在何处才能既满足各个城市的粮食供应需求，有可以使总投资和运输费用最省？
7(15分)假设A为m×n矩阵c属于n维向量，b属于m维向量，考虑下面最大-最小问题max min（CTX-YTAX+BTY）
X≥0 Y≥0
证明该问题可以写为一个显性的线形规划问题
2005年试题
一、简单回答以下问题（共6小题，每小题5分，共30分）
1、什么样的解是线性规划的退化解，退化为什么会引起求解过程的循环？
2、用EXCEL求解线性规划并进行敏感性分析时，在敏感性分析表中，可以找到\递减成本\的数据，请解释什么是递减成本，写出其表达式，并解释递减成本的经济含义？ 3、简述求解整数规划的分支定办法中\分支\与\定界\的含义？ 4、简述求最大流问题的最小割-最大流定理。
5、简述求解无约束非线性规划的梯度法与共轭梯度法的异同。
6、a、b、c在什么范围内取值时，以下面矩阵为行对策人的赢得矩阵的二人零和对策问题的矩阵元素（1，1）是该矩阵的鞍点。
二、（20分）某企业使用四种化工原料生产六种化工产品，生产每种产品的投入产出系数见下表： （表中的成本和价格的单位为万元/吨，最大、最小需求数量和原料可用数量的单位为吨）
每种产品的投入产出系数列在表中，例如生产一吨A产品需要0.5吨原料1，0.1吨原料2，0.2吨原料3，0.4吨原料4，其他产品需要的原料数可依此类推。原料的成本和可使用数量列在表的最后两列；产品的销售价格在表的最后一行。产品的产量应该大于最小需求量，同时也要小于最大需求量。构造的求销售利润最大的线性规划模型用EXCEL求解后的敏感性分析报告如下表： 可变单元格： 约束：
（1）该问题的最优解中应该有几个基变量（提示：应包括松弛变量中的基变量），根据敏感性分析表中提供的信息，判断那些变量是基变量？
（2）从表中可知：产品D的单位利润最高（34万元/吨），但它对目标池数的边际贡献却最小（递减成本为-0.1万元/吨）；产品C的单位利润最低（21万元/吨），但它对目标函数的边际贡献却最大（递减成本为12.3万元/吨），为什么会有这样矛盾的现象，请解释其中的原因？
（3）四种原料中哪种原料的影子价格最高，如果企业还可以从市场上获得这种原料，企业可以出的最高价格是多少？
（4）在保持最优基不变的前提下，你建议该企业应继续采购哪种原材料，采购多少可以使企业获得最大的收益？
（5）产品C价格在什么范围内变化时该问题的最优基保持不变？
（6）该企业正考虑生产一种新产品E，该产品计划售价为60万元/吨，需要0.7吨原料1，0.1吨原料2，0.2吨原料3和0.3吨原料4，是否应该生产这种新产品？三、（20分）某工厂要利用m种原料在T个月内生产n种产品。市场第t个月对第j（j=1……n）种产品的最大需求为,j产品的市场销售价格为 ；生产单位j产品需要使用数量为
的第i（i=1......m）种原料，i原料的单位采购成本为 ，每个月可使用的数量不能超过原料供应能力
；工厂需要使用q种设备生产n种产品，生产j产品需要使用数量为
的k(k=1……q)种设备的生产能力。工厂的第k种设备的最大加工能力限制为 ；使用第k种设备单位生产能力的成本为
；当生产能力紧张时，允许工厂利用库存调节各个月份可能出现的供需之间的矛盾，第j种产品的库存费用为
。请为该厂构造一个求销售利润最大的生产优化线性规划模型。（注: , , , , , , ,不随时间变化） 四、（20分）某连锁商业公司主要从事大型家用电器的分销业务，在一个城市设有4个零售商场，每个商场每月平均销售家用电器的数量见下表：
各个商场销售的电器需要由分销中心配送，因此该公司需要决策在什么地方建立分销中心。备选的地点有3个，在每个地点设立分销中心的固定成本见下表：
从各个备选地点供应各个商场的变动分销成本（元/每台）见下表：
该公司希望设计一个使分销成本（固定成本+变动成本）最小的建设方案，并考虑以下限制条件： （1）最多设立两个分销中心；
（2）在地点A和地点B不能同时设分销中心； 请写一个满足上述要求的整数规划模型。
五、（15分）某公司计划用50万投资一项新产品开发，根据技术人员的周密分析，新产品开发成功的概率为90%，成功后每年可获利8万，如果开发失败则会失去全部投资。该公司的另一个选择是将这笔钱存入银行，每年可得利息3万。为降低投资风险，公司可聘请一投资咨询公司进行投资咨询，咨询公司收费为1.2万元。该公司以往200例咨询意见实施结果的统计资料见下表：
1、请画出该公司新产品开发的决策树 2、应用EMV准则分析公司是否应该投资；
3、与咨询相关的样本信息期望值是多少？完全信息期望值是多少？
六、（15分）某银行分理处经理需要确定周末需要的前台营业员人数。统计资料表明，周末的顾客到达时间间隔和营业员为顾客服务的时间都服从负指数分布，平均每分钟有2名顾客到达银行，营业员平均需要2分钟时间为一位顾客服务。银行在周末每增加一名营业员的平均成本为90元/小时。然而银行还需要考虑因排队时间过长而带来的损失，统计数据表明，顾客排队等待时间每增加1分钟会产生0.5元的与服务质量相关的损失（如银行信誉，顾客流失等造成的损失）。请问银行经理应安排多少营业员参加周末服务才可以使总成本最小化。不同服务台数量s和不同服务强度p对应的全部服务台忙的概率（即p（j≥s））见下表：
p s=4 s=5 s=6 s=7 0.40 0.09 0.06 0.04 0.03 0.50 0.17 0.13 0.10 0.08 0.60 0.29 0.24 0.20 0.17 0.70 0.43 0.38 0.34 0.30 0.75 0.51 0.46 0.42 0.39 0.80 0.60 0.55 0.52 0.49 0.85 0.69 0.65 0.62 0.60 0.90 0.79 0.76 0.74 0.72 0.95 0.89 0.88 0.87 0.85
七、（15题）线性回归是一种常用的数理统计方法，这个方法要求用一条直线拟和二维平面上的一系列点 假定拟和直线方程的表达式为y=a+bx，然后用某种准则确定待定系数a和b，通常采用最小二乘法，但也可以采用其他准则。请根据以下准则建立求解待定系数a和b的线性规划模型： 解：线性规划问题为：