2001
一、（20分）选择填空（将所选答案的标号填在空白处，各空填一个标号） 1．下列数学模型中 a 是线性规划模型。
(a)maxZ?4x1?2x2?3x3
?7x1?3x2?6x3?150?s.t.?4x1?4x2?5x3?120 ?x,x,x?0?123?7x?6x2?8x35x1?9x2?2x3?(b)maxZ?min?1?
43???5x1?5x2?3x3?300?s.t.?6x1?9x2?8x3?500 ?x,x,x?0?1232．下列图形（阴影部分）中 b 是凸集。
（a） （b） （c）
3．标准形式的线性规划问题，其可行解 b 是基本可行解，最优解 a 是可行解，最优解 a 能在可行域的某顶点达到。
（a）一定 （b）不一定 （c）一定不 4．目标函数取极小（min Z）的线性规划问题可以转化为目标函数取极大 c 的线性规划问题求解，原问题的目标函数值等于 c 。
（a）max Z （b）max（-Z） （c）-max（-Z） （d）-max Z 5．动态规划问题的研究对象是 b ，其求得的一般方法是 c 。
（a）工程路线问题 （b）多段决策问题 （c）迭代求解 （d）单纯形法
6．网络分析中的最短路问题从发点s到收点t的最短路长 b 是唯一的，最短路线 a 是唯一的。 （a）不一定 （b）一定
7．网络最大流问题中，最大流的流量 a 是唯一的，最大流 b 是唯一的。 （a）一定 （b）不一定
8．M/M/1排队系统指的是顾客流为 b 服务时间为 a 有 d 个服务台的排队系统。 （a）负指数分布 （b）泊松流 （c）定长分布 （d）一个 （e）M个
9．运用表上作业法求解运输问题时，计算检验数可以用 b ，确定初始方案可以用 a 。
二、（18分）某公司生产3种产品：x1,x2,x3,需要3种资源：技术服务，动力和行政管理，公司经理助理根据公司实际情况，建立了使总利润最大的产品产量的线性规划模型，并maxZ?10x1?6x2?4x3)?x1?x2?x3?100(技术服务约束?s.t.?10x1?4x2?5x3?600（劳动力约束）?2x?2x?6x?300（行政管理约束）23?1采用单纯形法求得最优表格如下： C8 6 10 0 X8 C8
10 X1 0 1 0 0 6 X2 1 0 0 0 4 X3 5/6 1/6 4 0 X4 10/6 -4/6 -2 0 X5 -1/6 1/6 0 0 X6 0 0 1 0 Qj qj b X8 X2 X1 X5 -Z 400/6 200/6 100 4400/6 -8/3 -10/3 -2/3 在向总经理汇报时，总经理提出以下问题： 1． 公司3中资源的影子价格各是多少？
2． 若要现行解保持最优，则产品X 1的单位利润不得低于何值？ 3． 若产品X3值得生产的话，它的单位利润应是多少？
4． 制造部门提出要生产一种新产品，该单位产品要技术服务1小时，劳动力4小时，行政管理3小时。销
售部门预测这种产品出售时可获8元的单位利润，管理部门是否考虑应将此新产品投产？ 现请帮助经理助理回答以上问题。 三、（14分）下图为某地区的交通网络图，结点表示城市，箭杆边的数字表示城市间的公路距离，现要求出从S城到T城的最短路线和最短距离。
1． 以选用哪些运筹学方法求解此问题？（至少举出两种方法） 2． 选用一种方法求解该问题。
1 5 2 3 6 S 1 5 2 T 3 2 6 4 3
解：1．最短路问题，动态规划 四、（18分）某工厂有一个半成品加工操作间，内设一个半成品加工操作台和可存放3个待加工半成品的场地。已知半成品按平均每天3个的泊松过程到达该操作间，而完成该半成品加工的必要时间服从平均每个需1/4天的指数分布。若半成品到达操作间时操作间内已没有场地存放，则要运往其它地方。 （1） 需运往其它地方的半成品占到操作间的半成品总数的比例是多少？
（2） 假设每移动一个半成品到它处需200元，为提高效率减少移动费用可采取两种改进方案。方案一：
增加一个空位每天需要10元，方案二：提高加工效率至少每个1/5天每天需要15元。问是否应该采用改进方案，如应该采用改进方案则何种方案最佳？
五、（20分）某公司投资证券市场，现有两种方案。方案A1：投资股市，方案A2：投资证券。公司投资顾问认为：方案A 1在大盘走势好（θ1）时可能获利50万元，在大盘走势弱（θ2）时可能损失10万元。方案A2投资证券基本上无风险，可获利10万元。先验估计P（θ1）=0.3，P（θ2）=0.7。投资顾问认为大盘走势和国家宏观经济形式密切相关。并建议请经济研究所进行预测，预测费用为1万元。根据统计资料，该所预测精度的条件概率如下：
其中S1表示国家宏观经济形式良好，S2表示国家宏观经济形式不好
先验概率 P（θj） P（θ1）=0.3 P（θ2）=0.7 条件概率P（Si/θj） P（S1/θj） 0.8 0.1 P（S2/θj） 0.2 0.9 2002
一、填空（20%）
1． 线性规划原问题中约束的个数与其对偶问题中的 变量 个数相等。若原问题第j个约束为等式，则对偶
问题第j个 变量 自由。
2． 设线性规划问题max:{cx|Ax≤bx≥0}有最优解，且最优解值z>0；如果c和b分别被v>1所乘，则改变
后的问题 也有 （也有、不一定有）最优解；若有最优解，其最优解 大于 (大于、小于、等于)z。 3． 目标规划模型的一个主要特点是引入了偏差变量，模型的目标就是这些变量的极 小 （大还是小化），
模型的约束中也要包括用这些变量表示的目标约束。 4． 无权的连通图称为树。求出右图网络的最V4 2 V5
5 小部分树（用粗线在图上标出），最小权和3 1 6 为 16 。 V1 5 V6
6 5． 网络计划方法中关键路径法的实质是求网V3 3
3 V7
络图中耗时最 长 （长、短）的路径。 V2 7 6． 货船按泊松流到达某港口，平均到达率为
每天50条，平均卸货率为μ。又知船在港口停泊一天的费用为1货币单位，平均卸货费为2μ货币单位，则使总费用最少的平均卸货率μ*= 条/天。
7． 矩阵对策的研究对象是 对策问题。它在纯策略意义下有解的充要条件是：该解是 点；如果
它在纯策略意义下无解，则它在 意义下必有解。 二、（17%）已知线性规划问题
max z = (c1+t1) x1 + c2x2 + c3x3 + 0x4 + 0x5
?a11x1?a12x2?a13x3?x4?b1?3t2?s.t.?a12x1?a22x2?a23x3?x5?b2?t2 ?x?0(j?1，?，5)?j
X1 0
1 0
X2 1/2 -1/2 4
X3 1 0 0
X4 1/2 -1/6 4
X5 0 1/3 2
当t1=t2=0时，用单纯形法求得最终表如下： X3 5/2 X1 5/2 Cj-Zj
要求：1.确定c1,c2,c3,b1,b2,a11,a12,a13,a21,a22,a23的值；
2．当t2=0时，t1在什么范围内变化上述最优解不变；
3．当t1=0时，t2在什么范围内变化上述最优基不变。 三、（10%）某服装厂制造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定）。不考虑固定费用，则每种防寒服售出一件所得利润分别为10、12、13元，可用资源分别为：尼龙绸1500米，尼龙棉1000米，劳动力4000，设备3000小时。此外，每种防寒服不管缝制多少件，只要做都要支付一定的固定费用：小号为100元，中号为150元，大号为200元。现欲制定一生产计划使获得的利润为最大，请写出其数学模型（不解）。 型号 资源 尼龙绸 尼龙棉 劳动力 缝纫设备 小 1．6 1．3 4 2．8 中 1．8 1．5 4．5 3．8 大 1．9 1．6 5 4．2 四、（12%）过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在哪一组路段上扩充，说明原因。 ⑤ ② ④ ⑥ ① 进入Albany 离开Albany （ 北 ） ( 南 ) ③ 五、（10%）某厂计划用220万资金，购买生产同一种产品的四种型号的设备A、B、C、D，这四种型号的设
备设计生产能力和价格如下表所示。每种型号的设备应购买过少台，使总生产能力最大。
设备型号 设计生产能力K（吨/台） i价格Pi（万元/台） A 150 70 B 180 75 C 200 80 D 210 85 建立该问题的动态规划模型：列出阶段变量、状态变量、决策变量、状态转移方程、阶段指标、递推方程（不解）。 六、（13%）某公司生产的产品需要一种配件。原先该公司一直采用不允许却获得经济批量公式确定订货批量，现出于成本原因公司考虑采用允许缺货的策略，已知对该公司产品的需求为R=800件/年，每次对配件的订货费用为C1=150元，存储费为C2=3元/件.年，发生缺货时的损失为C3=20元/件.年。
（1） 计算采用允许缺货的策略较之原先不允许缺货策略带来的费用上的节约；
（2） 如果公司自己规定缺货随后补上的数量不超过总量的15%，任何一名顾客因供应不及时需等下
批货到后补上的时间不超过3周，问这种情况下，允许缺货的策略能否被采用。
七、（18%）一计算机芯片厂生产的某种芯片是以10个芯片为一个批次通过两道主要工序生产出来的。大量统一表明，一个批次的芯片经过生产的第一道工序的一次加工后会有80%的批次的产品合格率为90%，有20%的批次的产品合格率为50%。合格率为90%的批次下一道工序的加工成本为1000元，而合格率为50%的批次的下一道工序的加工费将高达4000元。为避免质量差的批次进入下一道工序，工厂还可以选择以1000元的成本将芯片重新在第一个工序中再加工一次。经两次加工后的产品的合格率将稳定在90%。
（1） 该厂希望每批次的加工成本最小的应如何决策，画出该问题的决策树。 （2） 计算本问题的完全信息期望值。
（3） 芯片厂还有另外一种选择，即从每批中抽检一个产品，根据抽检结果决定改批次是直接进入下
一道工序，还是在第一道工序中再加工一次，抽检一个产品的检查成本为100元。试决定芯片厂是否应当抽检及相关决策。
2003
一、简答（18%）
（1）请简述影子价格的定义。
（2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？ （3）写出影子价格的数学表达式并用其定义加以验证 （4）试述运输问题中检验数的经济意义 二、建模（30%）
1.某厂使用A、B两种原料生产甲、乙、丙三种产品，有关数据见下表： 甲 乙 丙 A B 生产成本（万元/吨） 销售价格（万元/吨） 1.0 0.5 0.4 0.6 0.6 0.5 8 5 18 30 20 35 原料成本（万元/吨） 5 7 原料可用数量（吨） 350 460 （1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为x1,x2,x3,约束依A,B原料次序）:
(2)写出此问题的对偶规划模型
2.某工厂考虑设备n年的更新计划,在每年初需作出设备是更新还是继续使用的决策,设备使用一年产生的利润,设备使用一年的维修费,以及设备的更新费用都与设备已使用的年数(设备年龄t)有关. 设r(t)为t年龄设备使用一年的利润 u(t)为t年龄设备使用一年的维修费用 c(t)为t年龄设备当年更新的费用
用动态规划方法求出n年内每年的最佳决策而使n年总利润最大.试引入0-1变量表示决策变量,并有此统一表示动态规划有关的概念和式子(不必求解):阶段,状态变量,决策变量,状态转移,阶段指标. 三、计算求解 （1）（21%）下图为某工程网络计划图中所有关键路线构成，图中弧表示关键工序，图中弧上数字为各工序压缩工时所需费用（单位：元/天）现该工程需将工期压缩一天，试问在那些工序上压缩工时为最佳 ② 4 ⑤ 2
3 1 3 6 ① ④ ⑥ 6 3
2
③ （2）（10%）一软件公司需要在自主开发一种微机上使用的会计软件和接受其他公司的委托进行办公自动化软件开发之间进行抉择。如果选择自主开发，根据过去的开发经验，开发一个会计软件需要20万元。如果软件开发得很成功（功能好于市场上已经存在的任何类似产品，概率为20%），他们开发的软件可能以100万的价格卖给一个大的软件公司；如果比较成功（好于部分市场产品，概率为60%）价格降为50万元；如果不成功（概率为20%）则无法卖出该产品。公司若决策接受其他公司的委托开发办公自动化软件，则可获得20万元的软件开发费。
（1）根据最大收益期望原则求该软件公司的最优决策（画出决策树） （2）求出本问题的完全信息期望值
（3）该软件公司还可以出2万元聘请一个咨询公司就该产品的开发问题进行咨询，根据以往的统计该咨询公司咨询准确性的概率P如下表： 咨询意见 成功状态 很成功 成功 不成功