天大运筹学考研历年试题分类.doc

（一）选择填空题1下面给出某线性规划问题的单纯形初表和终表（Min型）：CB XB B-1b0 1 -3 0 2 0x1 x2 x3 x4 x5 x60 x1 70 x4 120 x6 101 3 -1 0 2 00 -2 4 1 0 00 -4 3 0 8 1 j CB XB B-1bx1 x2 x3 x4 x5 x6 x2 x6 2/5 0 1/10 01/5 1 3/10 01 0 -1/2 1 j (1)初表的出基变量为，进基变量为。(3)填完终表。(6)若原问题增加一个新的非负变量，则对偶问题的最优目标值将（变大、不变、变小）。（2007）1用图解法解线性规划时，以下几种情况中不可能出现的是（ ）。A可行域（约束集合）有界，无有限最优解（或称无解界） B可行域（约束集合）无界，有唯一最优解C可行域（约束集合）是空集，无可行解D可行域（约束集合）有界，有多重最优解 （2006） 2根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润。 A 小于 B 等于 C 大于 D 大于等于 （2006）1用大M法求解Max型线形规划时，人工变量在目标函数中的系数均为_，若最优解的_中含有人工变量，则原问题无解。（2005）1. 设线性规划问题有最优解和影子价格,则线性规划问题的最优解= ，影子价格= 。（2004）3. 某工程公司拟从1、2、3、4四个项目中选择若干项目。若令请用的线性表达式表示下列要求：（1）若项目2被选中，则项目4不能被选中： （2）只有项目1被选中，项目3才能被选中： 。（2004）一、简答（18%） （1）请简述影子价格的定义。 （2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？ （3）写出影子价格的数学表达式并用其定义加以验证 （4）试述运输问题中检验数的经济意义（2003）线性规划原问题中约束的个数与其对偶问题中的 个数相等。若原问题第j个约束为等式，则对偶问题第j个 自由。（2002）1 设线性规划问题max:cx|Axbx0有最优解，且最优解值z0；如果c和b分别被v1所乘，则改变后的问题 （也有、不一定有）最优解；若有最优解，其最优解 (大于、小于、等于)z。（2002）1下列数学模型中 是线性规划模型。(2001)2下列图形（阴影部分）中 是凸集。(2001) （a） （b） （c）3标准形式的线性规划问题，其可行解 是基本可行解，最优解 是可行解，最优解 能在可行域的某顶点达到。(2001)（a）一定 （b）不一定 （c）一定不4目标函数取极小（min Z）的线性规划问题可以转化为目标函数取极大 b 的线性规划问题求解，原问题的目标函数值等于 。(2001)（a）max Z （b）max（-Z） （c）-max（-Z） （d）-max Z（a）最小元素法 （b）比回路法1. 线性规划单纯形算法的基本步骤是：（1） （2） (3) 每次迭代保持解的 ，改善解值的 。对偶单纯形法每次迭代保持解的 ，改善解值的 。（2000）2. 设有线性规划问题，有一可行基B（为A中的前m列），记相应基变量为，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X= ；用非基变量来表示基变量的表达式为XB= ；用非基变量表示目标函数的表达式为f= ，B为最优基的条件是 。（2000）3. 线性规划（Min型）问题有多重最优解时，其最优单纯形表上的特征为： （2000）6. 某足球队要从1，2，3，4，5号五名队员中挑选若干名上场。令请用xi的线性表达式表示下列要求：（1）从1，2，3中至多选2名： （2）如果2号和3号都上场，则5号不上场： （3）只有4号上场,1号才上场：(2000) 1某工程公司拟从四个项目中选择若干项目，若令请用xi的线性表达式表示下列要求：（1）从1，2，3项目中至少选择一个： ，（2）只有项目2被选中，项目4才能被选中 。（1999）2考虑线形规划问题用单纯型法求解，得其终表如下：Cj5 12 4 0 -MCB XB B-1bx1 x2 x3 x4 x512 x2 8/55 x1 9/50 1 -1/5 2/5 -1/51 0 7/5 1/5 2/5j0 0 -3/5 -29/5 -M+其中x4位松弛变量，x5为人工变量。（1）上述模型的对偶模型为 ，（2）对偶模型的最优解为 ，（3）当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ，（4）最优基的逆矩阵（5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？（1999）1下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型）： 表1CB XB B-1b 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x60 x1 70 x4 120 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 表2 x2 x62/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 -1/2 101) 初表的出基变量为_，进基变量为_。2) 填完表2，该表是否是终表?_。若是，最优值_3) 此线形规划对偶问题的最优解_（二）线性规划建模二（20分）、某化学制药厂有m种有害副产品，它们的数量为bi（i=1，m）。按照规定，必须经过处理，制成n种无害物后才能废弃。设aij为每制成一单位第j（j=1，n）种无害物可以处理掉第i种有害物的数量，cj为制成一单位第j种无害物的费用。1 现欲求各无害物的产量xj以使总的处理费用为最小，请写出此问题的线性规划模型；2 写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（2007）二（10%）、某大型企业每年需要进行多种类型的员工培训。假设共有需要培训的需求（如技术类、管理类）为6种，每种需求的最低培训人数为ai，i=1,6, 可供选择的培训方式（如内部自行培训、外部与高校合作培训）有5种，每种的最高培训人数为bj, j=1,5。又设若选择了第1种培训方式，则第3种培训方式也要选择。记xij为第i种需求由第j方式培训的人员数量，z为培训总费用。费用的构成包括固定费用和可变费用，第j种方式的固定费用为hj（与人数无关），与人数xij相应的可变费用为cij（表示第j方式培训第i种需求类型的单位费用）。如果以成本费用为优化目标，请建立该培训问题的结构优化模型（不解）。（2006）1.某厂使用A、B两种原料生产甲、乙、丙三种产品，有关数据见下表： A B 生产成本（万元/吨）销售价格（万元/吨） 甲 乙 丙1.0 0.50.4 0.60.6 0.5 8 5 18 30 20 35原料成本（万元/吨）5 7原料可用数量（吨）350 460（1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为x1,x2,x3,约束依A,B原料次序）: (2)写出此问题的对偶规划模型（2003）三、（10%）某服装厂制造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定）。不考虑固定费用，则每种防寒服售出一件所得利润分别为10、12、13元，可用资源分别为：尼龙绸1500米，尼龙棉1000米，劳动力4000，设备3000小时。此外，每种防寒服不管缝制多少件，只要做都要支付一定的固定费用：小号为100元，中号为150元，大号为200元。现欲制定一生产计划使获得的利润为最大，请写出其数学模型（不解）。(2002) 型号资源小中大尼龙绸161819尼龙棉131516劳动力4455缝纫设备283842（三）互补松弛应用二（8%）、线性规划问题已知其最优解x1，x2 0，而第1，4两种资源（相应于第1，4两约束）均有余量，应用互补松弛定理求出原问题和对偶问题的最优解。（2005）（四）灵敏度分析三（25%）、派公司是一个生产高尔夫器材的小型公司，近期推出了高、中价位的高尔夫袋新产品（标准袋和高档袋），经销商对此产品十分感兴趣，并订购了派公司下3个月的全部产品。该高尔夫袋的生产过程主要包括4道工序：切割并印染原材料、缝合、成型（插入支撑架和球棒分离装置等）、检验和包装。有关数据如表1。派公司须决定标准袋和高档袋各生产多少可使公司的总利润最大。表1时间单耗 产品 （小时）工序标准袋 高档袋3个月内最大生产能力（小时）切割印染7/10 1630缝合 1/2 5/6 600成型 1 2/3 708检验包装 1/10 1/4 135产品单位利润（美元） 10 9 (1) 写出此问题的线性规划模型，约束依表1中次序；(2) 引入松弛变量（依约束次序）后用单纯形法计算得某单纯形表如表2，请填完表中空白，并判断其是否终表，如果是，请写出最优生产计划、最大利润和资源剩余；表2CB XB B-1b10 9 0 0 0 0 x1 x2 x3 x4 x5 x6 9 x2 252 0 x4 12010 x1 540 0 x6 181 1.875 0 -1.3125 00 -0.9375 1 0.15625 00 -1.25 0 1.875 00 -0.34375 0 0.140625 1 -6.9375(3) 写出此问题的对偶问题的模型，及对偶的最优解与最优值；(4) 写出成型时间的影子价格，求使该影子价格不变的成型时间的变化范围；(5) 若标准袋的利润可能发生变化，则其在何范围内变化时，可使原最优计划不改变？图示说明其几何意义。（2005）二（23%）、某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决定进行一次大规模的广告行动。表1给出了公司准备做广告的三种产品名称、估计每做一单位广告（一个广告标准批量）使每种产品的市场份额增加量、公司拟定的广告后每种产品市场份额增加量的最低目标和两种可选的广告方式的单价。表1单位增量 广告种类产品电视印刷媒体广告后市场份额最低增量去污剂0%1%3%液体洗涤剂3%2%18%洗衣粉-1%4%4%广告单位成本（万元）100200其中洗衣粉的市场份额出现负值是由于液体洗涤剂的份额增加会造成洗衣粉份额的减少。现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量（分别记为x1和x2）。1. 请写出此问题的线性规划模型（约束依表1中产品的次序），并将模型化为标准型。2. 用（Min型）单纯形法求解此问题，得单纯形终表如表2.表2CBXBB-1b100200000MMMx1x2x3x4x5x6x7x80x541/3114/3-1/3-1100x14-1/30-2/31/30200x2300100j400/3100/3M-400/3M-100/3M（1）请填完表中空白；（2）由表指出最优广告计划并求出相应的最低广告费用，此最优计划使每种产品的市场份额最低增量目标达成情况如何？3. 写出此问题的对偶问题模型，由表2求出对偶最优解Y*,并解释Y*的实际意义。（2004） (3)考虑线性规划问题 Min z=-4x1+x2+30x3-11x4-2x5+3x6+10x7 -2x1+6x3+2x4-3x6+x7=20 -4x1+x2+7x3+x4-x6=10 -5x3+3x4+x5-x6=60 Xj0(j=1,2,7) 用单纯型法求解,初表及终表如下: 初表CB XB B-1b-4 1 30 -11 -2 3 10X1 x2 x3 x4 x5 x6 x7-2 0 6 2 0 -3 1-4 1 7 1 0 -1 00 0 -5 3 1 -1 0 检验数终表-4 x1 5/4 45/23 x6 15/2-7/24 0 1/24 1/121/12 1 5/12 -1/61/4 0 1/4 -1/2 检验数1.填完初表和终表中各空白,并说明所得最优解是否是唯一的,为什么?2.考虑当b变为时,对最优解有什么影响?当b变为时,对最优解是否有影响?3.对偶问题最优解?（2003）二、（17%）已知线性规划问题 max z = (c1+t1) x1 + c2x2 + c3x3 + 0x4 + 0x5 当t1=t2=0时，用单纯形法求得最终表如下：X1X2X3X4X5X3 5/201/211/20X4 5/211/201/61/3Cj-Zj04042要求：1.确定c1,c2,c3,b1,b2,a11,a12,a13,a21,a22,a23的值； 2当t2=0时，t1在什么范围内变化上述最优解不变； 3当t1=0时，t2在什么范围内变化上述最优基不变。(2002)采用单纯形法求得最优表格如下：C8X8 C8 b X81064000QjX1X2X3X4X5X66X2400/6015/610/6-1/6010X1200/6101/6-4/61/600X5100004-201-Z4400/600-8/3-10/3-2/30qj在向总经理汇报时，总经理提出以下问题：1 公司3中资源的影子价格各是多少？2 若要现行解保持最优，则产品X 1的单位利润不得低于何值？3 若产品X3值得生产的话，它的单位利润应是多少？4 制造部门提出要生产一种新产品，该单位产品要技术服务1小时，劳动力4小时，行政管理3小时。销售部门预测这种产品出售时可获8元的单位利润，管理部门是否考虑应将此新产品投产？现请帮助经理助理回答以上问题。（2001）二（20） 解 1 0 3 -1 0 1 -1 1 12 0 0 -3 -1 -8 设 为引入的松弛变量。得到最优单纯形表如上表，要求： （1）利用最优解求c1,c2. （2）利用最优解求b1,b2 （3） 能变化多少而不至影响最优解；当 时求最优解； （4）假定用b+代替b,其中,求出使最优基保持不变的的范围. （5）求出各资源的剩余量和影子价格。(1997) （五）证明题三（15分）、考虑下面两个线性规划：（2007）三（11%）、考虑线性规划问题（P）1若X1,X2均为（P）的可行解，证明也是（P）的可行解；2写出（P）的对偶模型（仍用矩阵式表示）。（2006） 2对偶模型三（10%）、证明线性规划中的互补松弛定理：设（P）maxz=CX,XX|AXb,X0,(D)minu=Yb,YYAb,Y0,若分别是（P）（D）的可行解，分别是其相应的松弛变量，则是（P），（D）的最优解的充要条件是：；并解释互补松弛定理的经济意义。（2004）四、(21%)试证明线性规划原问题中第J个约束扩大K倍,其对偶规划最优解中第J个变量将缩小K倍（2003）二、（12%）有三个线性规划： 已知：，试证：（1）；（2）。（2000）2.在使用单纯形法求解线性规划问题时，设当前基证明：若为某非基变量，检验数，由此确定为进基变量，则能保证新的基本可行解的目标值得以改善。(1998) （1）请用数学方法证明，当所有非基变量检验数时，当前基本可行解为最优。（2）请从经济含义的角度出发，说明上述判断的正确性。(1997)二、运输问题将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的，在模型中相当于增加若干个变量。（2007）（2004）9运用表上作业法求解运输问题时，计算检验数可以用 b ，确定初始方案可以用 a 。4. 用表上作业法求解m个发点和n个收点的平衡运输问题，其方案表上有数格的个数为 ，空格的个数为 ；若从检验数为-2的某空格调整，调量为2，则调后可使总运费下降 。(2000)3用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经济意义是 ，若从该空格出发进行调整，该调整量为2，则调后可使总运费下降 。（1999）二、（13%）用表上作业法求解下面的平衡运输问题时，计算某方案的空格i,j检验数ij可采用位势法，其主要步骤如下：（1）建立线形方程组Ui+Vj=Cij,其中Cij为所有有数个的运价，Ui，Vj分别称发地i和收地j的位势。（2）令U1=0，求解得位势值Ui，Vj，i=1，m, j=1,n（3）ij= Cij-(Ui+Vj)试证明该方法的正确性，即证明空格i,j的检验数为ij= Cij-(Ui+Vj)（1999）五、图论3下图中节点表示某厂各办公楼或车间，虚线表示相应两楼或车间之间可以架设光缆，虚线旁的数字为架设这段光缆的费用，现需确定一使各楼或车间都能经光缆传输数据且总费用最少的方案。该问题可以看作一个（ ）。A最小费用流问题 B最短路问题 C 最大流问题 D最小支撑树问题 21111177434566251541685（2006）3用标号法求解网络最大流问题，当求的最大流的同时，也得到了最小截集，它是由_点集和_点集构成的点集切割中_（正还是反）向弧组成。（2005）5632353716V4V3V2V5V6V7V12 无权的连通图称为树。求出右图网络的最小部分树（用粗线在图上标出），最小权和为 。(2002)四、（12%）过纽约ALBANY的北-南高速公路，路况通过能力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在哪一组路段上扩充，说明原因。(2002)进入Albany（ 北 ）离开Albany ( 南 )7网络最大流问题中，最大流的流量 是唯一的，最大流 是唯一的。（a）一定 （b）不一定三、（14分）下图为某地区的交通网络图，结点表示城市，箭杆边的数字表示城市间的公路距离，现要求出从S城到T城的最短路线和最短距离。1 以选用哪些运筹学方法求解此问题？（至少举出两种方法）2 选用一种方法求解该问题。（2001）S1234T255316263，11，47.请在下图所示的最短路问题求解过程中进行一步：下一步给 节点标号，标号为 。2，4425342 610，632533，四、（10%）某地区有3个城镇，各城镇每天产生的垃圾要运往该地区的4个垃圾处理厂处理，先考虑各城镇到各处理厂的道路对各城镇垃圾外运的影响，假设各城镇每日产生的垃圾量、各处理厂的日处理能力及各条道路（可供运垃圾部分）的容量（其中容量为0者表示无此直接道路）如有表所示，试用网络流方法分析目前的道路状况能否使所有垃圾都运到处理厂得到处理，如果不能，应首先拓宽哪条道路，请画出相应的网络图，并说明分析的过程。（可不具体求解）（1999）1 2 3 4垃圾量12330 0 10 00 0 20 4050 40 20 50507080处理量60 40 90 30 二（15%）某工厂欲对一新购置设备作一5年工作计划，决定每年初是继续使用还是更新该设备，以使5年的总收益最大。该设备工作的年收入，年维修费，更新费均与设备的年龄有关。设s表示设备年龄，R(s) ，U(s)和C(s)分别表示年收入，年维修费和更新费。1) 用最短路模型来求解此问题（列出模型，不解）四(10%).下图网络弧上的数字为容量，括弧内的数字为该弧的流量。1) 在括号内填上适当的数字，使构成一个可行流。2) 在下表中填出截集与截量。 、3) 用标号法解此网络最大流，并指出最小截集。四（15） 有三个发电站（节点1，2，3）它们的发电能力分别为15，10和40兆赫，经输电网可把电力送到8号地区（节点8），电网的运输电能力如下图所示，求三个发电站输到这地区（节点8）的最大电力。（用最大流标号法）(1997)45201530151040102（艘/周）。 51 4 3 6 7 8七、决策论六（25分）、某服装厂设计了一款新式服装准备推向全国。如直接大批生产与销售，主观估计成功与失败的概率各为0.5，其分别的获利为1200万元与-500万元，如取消生产销售计划，则损失设计与准备费用40万元。为稳妥起见，可先小批生产试销，试销的投入需45万元，根据过去情况大批生产销售为成功的例子中，试销成功的占84%，大批生产的销售失败的事例中试销成功的占36%。试根据期望值准则决定是否要进行试销，如果试销，在试销成功与失败两种情况下的决策各为何？分析过程中要求画出决策树。（2007）5 对于一个多次重复且相互独立的风险性决策问题，应用最大期望收益准则得到一个方案。对此有如下看法，其中正确的是（ ）。A这一方案在任何情况下的收益都是最大的B这一方案的平均收益是最大的C这一方案在任何情况下的收益都等于它的期望收益D这一方案是在充分考虑了决策者对风险的偏好情况下的最佳选择（2006）4设风险型决策问题中，相应于状态的概率为相应于和决策的结局（利润）为则决策问题的完全信息期望值EVPI=_，由于它与最小期望机会损失相等，因此，它的另一种表示形式是：EVPI=_。（2005） EVPI= ,由于它和最小期望机会损失相等，因此，它的另一种表示形式是： EVPI= 。（2004）（2）（10%）一软件公司需要在自主开发一种微机上使用的会计软件和接受其他公司的委托进行办公自动化软件开发之间进行抉择。如果选择自主开发，根据过去的开发经验，开发一个会计软件需要20万元。如果软件开发得很成功（功能好于市场上已经存在的任何类似产品，概率为20%），他们开发的软件可能以100万的价格卖给一个大的软件公司；如果比较成功（好于部分市场产品，概率为60%）价格降为50万元；如果不成功（概率为20%）则无法卖出该产品。公司若决策接受其他公司的委托开发办公自动化软件，则可获得20万元的软件开发费。 （1）根据最大收益期望原则求该软件公司的最优决策（画出决策树） （2）求出本问题的完全信息期望值 （3）该软件公司还可以出2万元聘请一个咨询公司就该产品的开发问题进行咨询，根据以往的统计该咨询公司咨询准确性的概率P如下表： 咨询意见 成功状态很成功 成功 不成功 可以开发 不可开发 0.9 0.5 0.1 0.1 0.5 0.9问该软件公司是否需要咨询？若咨询，相应于各种咨询意见的最优决策为何？（请画出决策树，写出计算过程）（2003）七、（18%）一计算机芯片厂生产的某种芯片是以10个芯片为一个批次通过两道主要工序生产出来的。大量统一表明，一个批次的芯片经过生产的第一道工序的一次加工后会有80%的批次的产品合格率为90%，有20%的批次的产品合格率为50%。合格率为90%的批次下一道工序的加工成本为1000元，而合格率为50%的批次的下一道工序的加工费将高达4000元。为避免质量差的批次进入下一道工序，工厂还可以选择以1000元的成本将芯片重新在第一个工序中再加工一次。经两次加工后的产品的合格率将稳定在90%。（1） 该厂希望每批次的加工成本最小的应如何决策，画出该问题的决策树。（2） 计算本问题的完全信息期望值。（3） 芯片厂还有另外一种选择，即从每批中抽检一个产品，根据抽检结果决定改批次是直接进入下一道工序，还是在第一道工序中再加工一次，抽检一个产品的检查成本为100元。试决定芯片厂是否应当抽检及相关决策。(2002)五、（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（Si/j）P（S1/j）P（S2/j）P（1）=0.30.80.2P（2）=0.70.10.910.设风险型决策问题中，相应于状态i的概率为P(i),i=1,2,m，相应于结局（利润）为uij，i=1,2,m，j=1,2,n，则完全信息期望值EVPI= ，由于它与最小期望机会损失相等，因此，它的另一种表示形式是：EVP1= 。(2000)六（15%）在一台机器上加工制造一批零件共1000个，如果加工完后即逐个进行修整，则全部都可以合