天大历年试题分类

一、线性规划二、运输问题三、多目标规划四、动态规划五、图论六、网络计划技术七、决策论八、存储论九、排队论十、对策论十一、模拟技术一、线性规划（一）选择填空题（二）线性规划建模（三）互补松弛应用（四）灵敏度分析（五）证明题（一）选择填空题1．下面给出某线性规划问题的单纯形初表和终表（Min型）：CBXBB-1b01-3020x1x2x3x4x5x60x170x4120x61013-10200-241000-43081σjCBXBB-1bx1x2x3x4x5x6x2x62/501/1001/513/10010-1/21σj(1)初表的出基变量为，进基变量为。[]=−1*)2(B最优基逆(3)填完终表。=*)4(X最优解=*)5(y对偶问题最优解(6)若原问题增加一个新的非负变量，则对偶问题的最优目标值将（变大、不变、变小）。（2007）解：1．(1)出基变量为x4；进基变量为x3。(2)*12105101305101112B−⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥−⎢⎥⎣⎦。(3)CBXBB-1bx1x2x3x4x5x61x24-3x350x6112/5101/104/501/5013/102/50100-1/2101σj1/5004/512/50(4)*(4511)TX=(5)*14(0)55Y=(6)变小1．用图解法解线性规划时，以下几种情况中不可能出现的是（）。A．可行域（约束集合）有界，无有限最优解（或称无解界）B．可行域（约束集合）无界，有唯一最优解C．可行域（约束集合）是空集，无可行解D．可行域（约束集合）有界，有多重最优解（2006）解：1．A2．根据线性规划的互补松弛定理，安排生产的产品机会成本一定（）利润。A．小于B．等于C．大于D．大于等于（2006）解：2．B1．用大M法求解Max型线形规划时，人工变量在目标函数中的系数均为____________，若最优解的_______________中含有人工变量，则原问题无解。（2005）解：1、-M基变量1.设线性规划问题}{0max≥=bxAxcx有最优解*x和影子价格*y,则线性规划问题}{02max≥=bxAxcx的最优解=，影子价格=。（2004）解：1.x*2y*3.某工程公司拟从1、2、3、4四个项目中选择若干项目。若令4101……=⎩⎨⎧=，，个项目未选中，第个项目被选中，第iiixi请用ix的线性表达式表示下列要求：（1）若项目2被选中，则项目4不能被选中：（2）只有项目1被选中，项目3才能被选中：。（2004）解：3.0,13142≤−≤+xxxx一、简答（18%）（1）请简述影子价格的定义。（2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？（3）写出影子价格的数学表达式并用其定义加以验证（4）试述运输问题中检验数的经济意义（2003）解：一、简答⑴当各资源增加一单位时引起的总收入的增量，影子价格大于零的资源一定没有剩余，有剩余一定为零。⑵松弛变量检验数的负值，对偶问题的最优解。⑶CBB-1B是原问题{maxz=CX∣AX≤b,X≥0}最优基Z*=CBB-1b=Y*bZ*=y1*b1+y2*b2…ym*bm*zbδδ=y3*⑷表明增加一个单位的运量会引起总运输费用的变化1．线性规划原问题中约束的个数与其对偶问题中的变量个数相等。若原问题第j个约束为等式，则对偶问题第j个变量自由。（2002）解：2．设线性规划问题max:{cx|Ax≤bx≥0}有最优解，且最优解值z0；如果c和b分别被v1所乘，则改变后的问题也有（也有、不一定有）最优解；若有最优解，其最优解大于(大于、小于、等于)z。（2002）1．下列数学模型中a是线性规划模型。(2001)⎭⎬⎫⎩⎨⎧++++=32954867minmax)(321321xxxxxxZb321324max)(xxxZa++=⎪⎩⎪⎨⎧≥≤++≤++0,,120544150637..321321321xxxxxxxxxts⎪⎩⎪⎨⎧≥≤++≤++0,,500896300355..321321321xxxxxxxxxts解：2．下列图形（阴影部分）中b是凸集。(2001)（a）（b）（c）解：3．标准形式的线性规划问题，其可行解b是基本可行解，最优解a是可行解，最优解a能在可行域的某顶点达到。(2001)（a）一定（b）不一定（c）一定不解：4．目标函数取极小（minZ）的线性规划问题可以转化为目标函数取极大b的线性规划问题求解，原问题的目标函数值等于c。(2001)（a）maxZ（b）max（-Z）（c）-max（-Z）（d）-maxZ（a）最小元素法（b）比回路法1.线性规划单纯形算法的基本步骤是：（1）（2）(3)每次迭代保持解的，改善解值的。对偶单纯形法每次迭代保持解的，改善解值的。（2000）解：确定一个初始基可行解；检验一个基可行解是否为最优解；寻找一个更好基可行解；可行性；最优性。2.设有线性规划问题[]{}0,|,min≥==∈=XbAXXRXCXf，有一可行基B（为A中的前m列），记相应基变量为πX，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X=；用非基变量来表示基变量的表达式为XB=；用非基变量表示目标函数的表达式为f=，B为最优基的条件是。（2000）解：111111,,(),00NBNBNNBBbBbBNXCBbCCBNXCCBN−−−−−−⎛⎞−+−−≥⎜⎟⎝⎠3.线性规划（Min型）问题有多重最优解时，其最优单纯形表上的特征为：（2000）解：0,0.jkjxσσ≥=所有检验数而某一个非基变量检验数6.某足球队要从1，2，3，4，5号五名队员中挑选若干名上场。令⎩⎨⎧=54321ii0i1，，，，＝号不上场，第号上场第ix请用xi的线性表达式表示下列要求：（1）从1，2，3中至多选2名：（2）如果2号和3号都上场，则5号不上场：（3）只有4号上场,1号才上场：(2000)解：12345142,0,1.xxxxxxx++≥−≥+≤1．某工程公司拟从四个项目中选择若干项目，若令1,1,2,3,4.0,iixii⎧==⎨⎩第个项目被选中第个项目末被选中请用xi的线性表达式表示下列要求：（1）从1，2，3项目中至少选择一个：，（2）只有项目2被选中，项目4才能被选中。（1999）解：1、x1+x2+x3≥1x2≥x42．考虑线形规划问题123123123123max512425..232,,0Zxxxxxxstxxxxxx=++++≤⎧⎪−+=⎨⎪≥⎩用单纯型法求解，得其终表如下：Cj51240-MCBXBB-1bx1x2x3x4x512x28/55x19/501-1/52/5-1/5107/51/52/5σj00-3/5-29/5-M+25其中x4位松弛变量，x5为人工变量。（1）上述模型的对偶模型为，（2）对偶模型的最优解为，（3）当两种资源分别单独增加一个单位时，目标函数值分别增加和，（4）最优基的逆矩阵1B−⎡⎤=⎢⎥⎣⎦（5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？（1999）解：2．（1）1212121212min5225212340,Wyyyyyyyyyy=++≥⎧⎪−≥⎪⎨+≥⎪⎪≥⎩无符号限制（2）Y*=（295，-25）（3）295，-25（4）21551255⎛⎞−⎜⎟⎜⎟⎜⎟⎜⎟⎝⎠（5）变小1．下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型）：表1CBXBB-1b01-3020x1x2x3x4x5x60x170x4120x61013-10200-241000-43081jσ⋮表2x2x62/501/104/51/513/102/510-1/210jσ1)初表的出基变量为__________，进基变量为_________。2)填完表2，该表是否是终表?_________。若是，最优值=*Z________3)此线形规划对偶问题的最优解=*Y_______(1998)解：1.下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型）：表1CBXBB-1b01-3020x1x2x3x4x5x60x170x4120x61013-10200-241000-43081jσ00001111-3-3-3-3000022220000⋮表21111x24444-3-3-3-3xxxx333355550000x6111111112/5111101/104/500001/5000013/102/50000100000-1/2101111jσ1/51/51/51/5000000004/54/54/54/512/512/512/512/500004)初表的出基变量为_____xxxx4444_____，进基变量为___xxxx3333______。5)填完表2，该表是否是终表?____是_____。若是，最优值=*Z__-11-11-11-11______此线形规划对偶问题的最优解=*Y⎥⎦⎤⎢⎣⎡−−,054,51解：解：解：解：解：解：（二）线性规划建模二（20分）、某化学制药厂有m种有害副产品，它们的数量为bi（i=1，…，m）。按照规定，必须经过处理，制成n种无害物后才能废弃。设aij为每制成一单位第j（j=1，…，n）种无害物可以处理掉第i种有害物的数量，cj为制成一单位第j种无害物的费用。1．现欲求各无害物的产量xj以使总的处理费用为最小，请写出此问题的线性规划模型；2．写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（2007）解：1．11111221121122222112212min..,,0njjjnnnnmmmnnmnzcxaxaxaxbaxaxaxbstaxaxaxbxxx==∑++…+≥⎧⎪++…+≥⎪⎪……⎨⎪++…+≥⎪…≥⎪⎩，2．11112121112122222112212max..,,0miiimmmmnnmnmnmzybayayaycayayaycstayayaycyyy==∑++…+≤⎧⎪++…+≤⎪⎪……⎨⎪++…+≤⎪…≥⎪⎩，经济意义：iy为第i种有害副产品不经处理直接废弃的费用。二（10%）、某大型企业每年需要进行多种类型的员工培训。假设共有需要培训的需求（如技术类、管理类）为6种，每种需求的最低培训人数为ai，i=1,…,6,可供选择的培训方式（如内部自行培训、外部与高校合作培训）有5种，每种的最高培训人数为bj,j=1,…,5。又设若选择了第1种培训方式，则第3种培训方式也要选择。记xij为第i种需求由第j方式培训的人员数量，z为培训总费用。费用的构成包括固定费用和可变费用，第j种方式的固定费用为hj（与人数无关），与人数xij相应的可变费用为cij（表示第j方式培训第i种需求类型的单位费用）。如果以成本费用为优化目标，请建立该培训问题的结构优化模型（不解）。（2006）解：二、ijxij设为第种需求由第种方式培训的人员数量，1j0jy⎧=⎨⎩选择培训方式否则565111minjjijijjijzyhcx====+∑∑∑615113(1,2,,5)(1,2,,6)00(1,6,1,2,,5)01(1,2,,5)ijjjiijijijjxbyixaiyyxijyj==⎧≤=∑⎪⎪⎪≥=∑⎪⎪−≤⎨⎪≥==⎪⎪==⎪⎪⎩⋯⋯⋯⋯⋯或1.某厂使用A、B两种原料生产甲、乙、丙三种产品，有关数据见下表：AB生产成本（万元/吨）销售价格（万元/吨）甲乙丙1.00.50.40.60.60.58518302035原料成本（万元/吨）57原料可用数量（吨）350460（1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为x1,x2,x3,约束依A,B原料次序）:(2)写出此问题的对偶规划模型（2003）解：⒈①maxz=30x1+20x2+35x3-8x1-5x2-18x3-5(x1+0.4x2+0.6x3)-7(0.5x1+0.6x2+0.5x3)目标函数maxz=13.5x1+8.8x2+10.5x3约