清华846运筹学历年真题 .pdfVIP

清华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写出线性规划的对偶问题：maxCX

ST.{a≤AX≤b

l≤X≤u}

2（本题20分）某一线性规划的目标函数表达式为max

z=ax1+x2+2x3,其约束条件均为≤型的不等式。且已知x4,x5,x6为松

弛变量，某一步的单纯形表如下

Cj

CbXbB-1bX1X2X3X4X5X6

X32

-4/3

X555/2

3

2

X10001/3

Z=4-10

（1）

补充该单纯形表使之成为完整的单纯形表格。（不用逐次迭代的

方法）

（2）

写出当前的B-1b

（3）求a的取值范围，使该表格的最优解不变

（4）当a的取值不为该表最优解时，下一步迭代会使目标函数值

改进吗？说明理由？

3（本题20分）某单位在未来四年内使用一台机器,该种机器的年

收入为R,年运行费用为U,更新费用为C,随机器的役龄变化如下表所示,

0123

R54.543.5

U0.511.52.2

C0.51.52.23

试制订最优的更新计划,以使四年内的总利润最大(不计五年期末时

机器的残值).试用动态规划计算该问题，并写出状态转移方程和损益方

程。

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。设在这些

粮食仓库的整个使用寿命期间内，各城