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

（第1页）1用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。2132minxxz0,424664..212121xxxxxxts解：图解过程见下图有：TTX)5.0,75.0)(1()0,5.1(*3*Z该问题有无穷多最优解。2将下列线性规划问题化为标准形式，并列出初始单纯形表。（10分）32123minxxxz0,,053382412432..321321321321xxxxxxxxxxxxts无约束解：原问题标准化为：322123maxxxxxz0,,,,,,,533824124332..765432217322165322143221xxxxxxxxxxxxxxxxxxxxxxxxts其初始单纯形表为：Cj-3-11-20000Xjx1x/2x//2x/3x4x5x6x7000x4x6x7128524331-1-3-114-2-31000-10010001cj-zj-3-11-200003已知某线性规划问题用单纯形法迭代时得到中间某两步的单纯形表如表所示，试将表中空白处数字填上。（10分）354000x1x2x3x4x5x650x2x58/314/32/3-4/310051/3-2/30100012x1x22166421xx42421xx（第2页）0x629/35/304-2/301cj-zj-1/304-5/300┇┇543x2x3x150/4162/4189/4100110001015/41-6/41-2/418/415/41-12/41-10/414/4115/41cj-zj000-45/41-24/41-11/414已知线性规划问题：21maxxxz0,,122..321321321xxxxxxxxxts试应用对偶理论证明上述线性规划问题最优解为无界。（10分）解：原问题的对偶问题为：212minyyw0,0112..21212121yyyyyyyyts由约束条件1221yy可知，其对偶问题无解；又因TX)0,0,0(是原问题的可行解。由对偶定理可知原线性规划问题最优解为无界。5东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产能力分别为120、160、100万t。公司同3个城市签订了下年度的供货合同：城市1-110万t，城市2-150万t，城市3-70万t，但城市3表示愿购买剩余的全部煤炭。另有城市4虽未签订合同，但也表示只要公司有剩余煤炭，愿全部收购。已知从各矿至4个城市的煤炭单位运价见表。将此问题归结为运输问题，列出相应的产销平衡表与单位运价表。（10分）单位运价表单位：元/t城市煤矿1234吉祥平安双福856724513235解：该问题的运输问题产销平衡表与单位运价表为城市煤矿1233/4/产量吉祥平安双福虚设矿山856M724M513M5130235012016010050销量1101507050506已知下列五名运动员各种姿势的游泳成绩(各为50m，单位：s)如表所示。试问如何从中选拔一个4×50m混合泳的接力队，使预期的比赛成绩为最好。（10分）赵钱张王周仰泳蛙泳蝶泳自由泳37.743.433.329.232.933.128.526.438.842.238.929.637.034.730.428.535.441.833.631.1解：原问题用匈牙利算法求解为：（第3页）000001.315.286.294.262.296.334.309.385.283.338.417.342.421.334.434.350.378.389.327.37C变换后：000007.41.22.308.21.59.14.1008.47.86.11.903.105.21.49.508.41C再变换为：0006.101.35.06.102.15.33.08.802.31.705.707.89.05.23.402.32C再变换：09.005.202.25.05.003.06.23.09.703.22.606.608.705.24.303.23C再变换为：3.02.108.202.25.02.0006.23.06.700.22.603.605.705.21.300.24C∴0010000001000100100010000*XZ*=127.87分别用破圈法和避圈法求下图的最小部分树。（10分）解：用破圈法求最小部分树为：W（Tmin）=18注意有多重解用避圈法求最小部分树为：W（Tmin）=188用标号法求下图中v1至各点的最短路。（10分）2222222233335514v1v6v5v7v3v2198v4285741037322222222333355142222222233335514（第4页）解：标号过程如图所示：由图可得：v1→v2L=9v1→v3L=8v1→v2→v4L=11v1→v2→v5L=10v1→v2→v4→v6L=14v1→v2→v5→v7L=139现有8名青工，要分配给3个采矿队，每队限最多分5名，每个采矿队增加不同青工后产量增加如下表，如何分配才能使产量增加最大？试建立其动态规划求解模型。（10分）增加青工数采矿队012345第一采矿队第二采矿队第三采矿队0001610122514173016213217223317.522.5解：根据题意，原问题用动态规划求解模型为：（1）按作业班组分为3阶段，K=（1，2，3，4），k=4为终了阶段；（2）xk：第k阶段初拥有待分配新工人数；有：X1={8}，X2={8,7,6,5,4,3}，X3={5,4,3,2,1,0}，X={0}。（3）uk：第k阶段分配给第k作业班组的新工人数；有：U1={0,1,2,3,4,5}，U2={0,1,2,…,x2}(x25)；U2={x2-5,…,5}(x25)，U3={x3}。（4）状态转移方程：kkkuxx1；（5）阶段指标：见表，如：14)2,3(2d；12)1,2(3d；（6）递推方程：)(),(max)(11kkkkkUukkxfuxdxfkk（7）边界条件：0)(44xf。10某书店希望订购最新出版的图书出售。根据以往经验，新书的销售量可能为50、100、150或200本。假定每本书的订购价为4元，销售价为6元，剩书处理价为每本2元。分别依据悲观主义、乐观主义、等可能性、最小机会损失决策准则决定该书店应订购新书的数量。（10分）解：（1）根据题意该问题的益损值表为：Sjαi50100150200501001502001000-100-2001002001000100200300200100200300400（2）悲观准则：ijjdminmax100200,100,0,100max∴1*乐观准则：ijjdmaxmax400400,300,200,100max∴4*v1v6v5v7v3v2198v42857410373（0,v1）（14,v4）（13,v5）（11,v2）（10,v2）（9,v1）（8,v1）（第5页）等可能准则：ndjijmax150100,150,150,100max∴32*或最小机会损失准则：损失矩阵为：0100200300100010020020010001003002001000D则ijjdmaxmin200300,200,200,300min∴32*或