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

1、X1X1,X2,X2,X3,X4,X5,X6,X71用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还就是无可行解。min z2x13x2s.t.4x-|6x264x12X24X1,X20解:图解过程见下图*t有:X (1.5,0)(1该问题有无穷多最优解。（10 分）2将下列线性规划问题化为标准形式，并列出初始单纯形表。min z3x1X22X3s.t.2x13x24X3124x1X22X383x1X23x35，试将表中空白处数字填上。X10, X2无约束X 0解:原问题标准化为：max z3x1X2X22x3s.t.2x13x23x24X3X4124%X2X22

2、X3X5X683x1X2X23X3X75其初始单纯形表为Cj-3-11-20000XjX1X/2X2X/3X4X5X6X70X41223-3410000X6841-1-20-1100X753-11-30001Cj-zj-3-11-200003已知某线性规划问题用单纯形法迭代时得到中间某两步的单纯形表如表所示0X629/35/304-2/301Cj-Zj-1/304-5/30011I115X250/4101015/418/41-10/414X362/41001-6/415/414/413X189/41100-2/41-12/4115/41Cj-Zj000-45/41-24/41-11/414已知

3、线性规划问题：max z x1x221（10 分）s.t.X1 X2 X32x1 x2 x30XX2,X3试应用对偶理论证明上述线性规划问题最优解为无界。 解:原问题的对偶问题为：mi nw 2y1y2s.t.y12y2y1y2y1y1, y2y20由约束条件 2 y2 1 原线性规划问题最优解为无界。可知，其对偶问题无解；又因X（o,o,o）T就是原问题的可行解。由对偶定理可知5东兴煤炭公司下属吉祥、平安、双福三个煤矿，年生产能力分别为120、160、100万t。公司同3个城市签订了下年度的供货合同：城市1-110万t,城市2-150万t,城市3-70万t,但城市3表示愿购买剩余的全部煤炭。

4、另有 城市4虽未签订合同，但也表示只要公司有剩余煤炭，愿全部收购。已知从各矿至4个城市的煤炭单位运价见表。将此问题归结为运输问题，列出相应的产销平衡表与单位运价表。（10 分）单位运价表单位:元/t城市煤矿1234吉祥8752平安5213双福6435解:该问题的运输问题产销平衡表与单位运价表为f j城市煤矿1233/4/产量吉祥87552120平安52113160双福64335100虚设矿山MMM0050销量1101507050506已知下列五名运动员各种姿势的游泳成绩（各为50m,单位:s）如表所示。试问如何从中选拔一个4 x 50m混合泳的接力队，使预期的比赛成绩为最好。（10分）赵钱张王

5、周仰泳37、732、938、837、035、4蛙泳43、433、142、234、741、8蝶泳33、32& 538、930、433、6自由泳29、226、429、628、531、1解:原问题用匈牙利算法求解为3.204.32.50.92.303.42.508.707.507.17.806.606.23.208.80.33.5再变换:C32.307.90.32.61.201.60.53.10.300.50.52201 600002 500 902.003.12.50000017.506.306.2000102.007.60.32.6* X01000Z*=127、8000.20.52.210000

6、02.801.20.3001000000（10 分）0 0再变换为：C4再变换为：C20 0 037.732.938.837.035.44.8055.94.12.543.433.142.234.741.810.3019.11.68.733.328.538.930.433.6变换后：G4.8010.41.95.129.226.429.628.531.12.803.22.14.7C07分别用破圈法与避圈法求下图的最小部分树。解:用破圈法求最小部分树为用避圈法求最小部分树为：W(Tmi n)=188用标号法求下图中 vi至各点的最短路。（10 分）V37V6解:标号过程如图所示由图可得:v V2L=

7、9vi t V3L=8V1 t V2T V4L = 11V1 t V2T V5L = 10V1 t V2T V4T V6L = 14V1 t V2T V5T V7L = 139现有8名青工，要分配给3个采矿队，每队限最多分5名，每个采矿队增加不同青工后产量增加如下表，如何分配才能使产量增加最大？试建立其动态规划求解模型。(10分)曽加青工数采矿队012345第一采矿队01625303233第二采矿队01014161717、5第三采矿队01217212222、5解:根据题意，原问题用动态规划求解模型为：(1) 按作业班组分为 3阶段,K=(1,2,3,4),k=4为终了阶段；(2) xk：第k阶

8、段初拥有待分配新工人数；有：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,-xg( X2 5);U2= x2-5,5( x25),U3= x3。状态转移方程：Xk1Xk Uk；(5)阶段指标：见表，如:d2(3,2)14 ;d3(2,1)12;递推方程:fk(xQmax dk(xk,Uk)fk1(XkJUk Uk边界条件:f4(X4)0 o10某书店希望订购最新出版的图书出售。根据以往经验，新书的销售量可能为50、100、150或200本。假定每本书的订购价为4元，销售价为6元，剩书处理价为每本2元。分别依据悲观主义、乐观主义、等可能性、最 小机会损失决策准则决定该书店应订购新书的数量。(10分)解：(1)根据题意该问题的益损值表为：a50100150200501001001001001000200200200150-100100300300200-2000200400悲观准则：maxm.in dijmax 100,0, 100, 200100乐观准则：maxmax dHmax 100,200,300,400400jdij