2008采矿05运筹学试题(B)解答

（第1页）1用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。（10分）2165maxxxz0,23222..212121xxxxxxts解：图解过程见下图由图可见，该问题具有无界解。2将下列线性规划问题化为标准形式，并列出初始单纯形表。（10分）32153minxxxz无约束，321321321321,0105163262..xxxxxxxxxxxxts解：原问题标准化为：332153maxxxxxz0,,,,,,,10551633262..765433217332163321543321xxxxxxxxxxxxxxxxxxxxxxxxts其初始单纯形表为：Cj-3-5-110000Xjx1x2x/3x//3x4x5x6x7000x5x6x761610121211135-1-3-5-100100010001cj-zj-3-5-1100003写出下列线性规划问题的对偶问题。（10分）njj1jxczmax01234x1x23212221xx23221xx（第2页）),,1(),,2,1(0),,2,1(),,2,1(..1111111nnjxnnjxmmmibxammibxatsjjinjjijinjjij无约束解：原问题的对偶规划为：mii1iybwmin),,1(),,2,1(0),,1(),,2,1(..111111mmiymiynnjcyanjcyatsiijmiiijjmiiij无约束4用对偶单纯形法求解下列线性规划问题。（10分）321425minxxxz0,,10536423..321321321xxxxxxxxxts解：用对偶单纯形法求解有：Cj-5-2-400bCBXBx1x2x3x4x50x4-3-1-210-40x5-6-3*-501-10σj-5-2-4000x4-1*0-1/31-1/3-2/32x2215/30-1/310/3σj-10-2/30-2/320/35x1101/3-11/32/32x20112-12σj00-1/3-1-1/322/3∴规划问题最优解为X*=(2/3，2，0)T；Z*=22/35已知运输问题的产销平衡表与单位运价表如表所示，试用Vogel法求出其近似最优解。（10分）销地产地B1B2B3B4产量A1A2A3A491081081091012121111131412121824612销量614355解：该问题用Vogel法求其近似最优解为：（第3页）销地产地B1B2B3B4产量A1A2A3A49108108109101212111113141212182461210103231-231-211销量61435511001-002-00--006求解整数规划问题：（10分）21maxxxz且为整数0,30561652..212121xxxxxxts解：用图解法有：∴X*=(5，0)T或X*=(4，1)T或X*=(3，2)T；Z*=57用单纯形求解下述目标规划问题：（10分）)5.1()(min4342312431ddPdPdPddPz)4,3,2,1(0,,,153010040..2144233122211121iddxxddxddxddxxddxxtsii解：用单纯形法求解有jc000P2P30P4P11.5P4P1BC基bx1x2d1-d1+d2-d2+d3-d3+d4-d4+0P3P41.5P4d1-d2-d3-d4-40100301511[1]011011000-100001000-100001000-100001000-1jjzcP100000001010426486x18x22305621xx165221xx●●●414224475（第4页）P20001000000P3-1-100010000P4-1-1.500000101.50P301.5P4d1-d2-x1-d4-107030150010[1]1011000-100001000-100-1-11011-100001000-1jjzcP10000000101P20001000000P30-100011100P40-1.500001001.50P301.5P4x2d2-x1-d4-1060305001010001-10-1-110[1]01000-100-101110-1-10001000-1jjzcP10000000101P20001000000P3001-1011100P4001.5-1.500-0.51.501.50P30P2x2d2-x1-d1+155530500101000000-1000101000-1000-11[1]01-1-11-101-110-1jjzcP10000000101P2001000-11-11P30000011-11-1P4000000101.500P30P4x2d2-x1-d3-1560255001010000-11-101-1101000-1000001000-110-11-101-1jjzcP10000000101P20001000000P3001-1010000P4001-100010.51∴X*=(25，15)T8用Ford-Fulkerson的标号算法求下图中所示各容量网络中从vs到vt的最大流。图中各弧旁数字为容量cij，括弧中为流量fij。（10分）解：用Ford-Fulkerson方法求解。（1）根据初始流，则寻找可扩充路（增广链）的标号过程如下：vsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)（第5页）（2）调整流量，继续标号有：（3）由图所示，标号过程进行不下去，即不存在vs-vt的可扩充路（增广链），根据可扩充路（增广链）定理，图示流即为最大流，maxQ=13。9某项工程有三个设计方案。据现有条件，这些方案不能按期完成的概率分别为0.40，0.60，0.80，即三个方案均完不成的概率为0.40×0.60×0.80=0.192。为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元投资，当使用追加投资后，上述方案完不成的概率见下表。问应如何分配追加投资，使其中至少有一个方案完成的概率为最大。（只建模型）（10分）追加投资（万元）各方案完不成的概率1230120.400.200.150.600.400.200.800.500.30解：(1)阶段：每个设计方案为一阶段，K={1,2,3,4}，k=4为结束阶段。(2)状态变量sk：k阶段初待分派的资金；S1={2}、S2={0,1,2}、S3={0,1,2}。(3)决策变量xk：k阶段分派给k设计方案的资金；D1(s1)={0,1,2}、D2(s2)={0,1,2}、D3(s3)={s3}。(4)状态转移方程：sk+1=sk-xk(5)阶段指标函数：vk(sk,xk)见表所示。(6)递推方程：(采用逆推法))(),(min)(11)(kkkksDxkksfxsvsfkkk(7)边界条件：1)(44sf10有一块海上油田进行勘探和开采的招标。根据地震资料的分析，找到大油田的概率为0.3，开vsv5v4v3v2v1vt3(3)3(2)5(5)6(4)3(3)2(0)4(4)2(2)5(4)2(0)6(6)8(6)（-，∞）（+vs，2）（-v5，1）（+v2，1）（-v3，1）（+v1，1）（+v4，1）vsv5v4v3v2v1vt3(2)3(3)5(5)6(5)3(3)2(0)4(4)2(1)5(5)2(0)6(6)8(7)（+vs，1）（-，∞）（第6页）采期内可赚取20亿元；找到中油田的概率为0.4，开采期内可赚取10亿元；找到小油田的概率为0.2，开采期内可赚取3亿元；油田无工业开采价值的概率为0.1，按招标规定，开采前的勘探等费用均由中标者负担，预期需1.2亿元，以后不论油田规模多大，开采期内赚取的利润中标者分成30%。有A、B、C三家公司，其效用函数分别为：A公司U(M)=(M+1.2)0.9-2B公司U(M)=(M+1.2)0.8-2C公司U(M)=(M+1.2)0.6-2试根据效用值，并用期望值法确定每家公司对投标的态度。（10分）解：决策树见下图：计算效用期望值见下表。大油田中油田小油田无开采价值EMV0.30.40.20.1A公司3.01580.6872-1.0905-20.7615B公司2.19300.4089-1.0802-20.4054C公司0.9302-0.0668-1.0613-2-0.1560结论为A公司和B公司愿参加投标，C公司不参加投标。4.80-1.2-0.31.80.10.20.40.3中油田小油田无开采价值大油田不投标或未中标投标并中标