露天采矿的最优方案.doc

理工大学暑期数学建模强化训练专题五露天采矿的最优方案学员： 曹 阳 许佳利 倪迪杭 学院： 通信工程学院 时间：2010.08.20露天采矿的最优方案摘 要公司在一块一定面积的方形土地上露天采矿，需要建立一个模型以帮助决定采矿方案，使得公司获得最大的经济效益。本文针对采矿方案的优化问题，建立两个不同的数学模型，均找到了最优的采矿方案，为公司的决策提供切实有效的建议。模型1，运用“转移矩阵”，将两元（收入和费用）问题转化为一元（盈亏值）问题，大大简化了分析过程；模型2，建立一个的三维矩阵，将三个不同层长方形块的值的矩阵用同一个扩充矩阵来表示，结合规划，考虑各层长方形块之间的联系，建立了单目标线性规划模型，并通过LINGO软件的求解，得到了最优的采矿方案。通过模型1和模型2的求解，均找到了最优的采矿方案，使得收入与费用（即纯收入）之差最大，其值为1.75万元。具体的最优采矿方案见正文。关键词:转移矩阵，单目标线性规划，规划，扩充矩阵一、问题的提出1、背景某公司获准在一块200m x 200m的方形土地上露天采矿。因为土石滑坡，控坑的坑边坡度不能陡于45。公司已得到不同位置不同深度处的矿砂所含纯金属的百分数的估计值。考虑到坡度角对挖坑工作所加限制，公司决定将问题作为长方形块的挖取问题加以处理。2、问题每个长方形水平尺寸为50m x 50m，铅直尺寸为25m。若在一个深度上挖了四块，则在下一层还可以挖一块；俯视这块的水平位置关系，将是如图所示的情形（实线为上一层块，虚线为下一层块）。（图）这样一来，所能挖取的块数，第一层最多为16块，第二层最多为块，第三层最多块，第四层最多块。不能再往深处挖取。所有这些可能挖取的块，按已得到的估计值，将各块含纯金属的百分数作为块的值，这个块的值如下：1.51.51.50.751.52.01.50.751.01.00.750.50.750.750.50.25 第一层（地表层） 第二层（深25m）4.04.02.03.03.01.02.02.00.512.06.05.04.06.0 第三层（深50m）第四层（深75m）挖取费用随深度增加。第一层中各块的挖取费用为0.3万元，第二层为0.6万元，第三层为0.8万元，第四层为1.0万元。挖取一块的收入同该块的值成正比；一个值为的块可得收入为0.2万元。试建立一个模型以帮助决定挖取那些块，使得收入与费用之差为最大。二、问题的分析题目的要求是通过建立数学模型制定最优挖掘方案，使得收入与费用之差为最大，即纯收入最大，这是一个典型的优化模型的问题。根据题目条件，只有在一个深度上挖了四块，才能在下一层再挖一块。最多的挖掘块数为第一层最多为16块，第二层最多为块，第三层最多块，第四层最多块。可以逆向思维，若挖取第四层的那块长方形块，则必须挖取所有的长方形块。而若该公司采用这种挖取方案，则可以根据题目中给出的各块长方形块的价值和挖取费用，计算出其总收入为（万元），其总挖取费用为（万元），两者之差为万元，说明若采用这种挖取方案，该公司将损失万元。按照常理考虑，公司采矿的目的是为了盈利，该公司不会采用这种挖取方案。所以，第四层的那块长方形块不挖取。因此，我们在考虑建立模型的时候，只需研究前三层的长方形块。三、模型假设1、该公司采矿的目的是为了盈利；2、按照公司采用的土块划分方法，不会导致土石滑坡。四、模型的建立及求解1、符号说明 各长方形块的价值矩阵 转移矩阵 三维扩充矩阵 三维矩阵 采矿的收入 采矿的费用 采矿的盈利2、模型建立2.1模型1：“转移矩阵”模型2.1.1模型的分析问题的分析中已经分析说明无论该公司采用何种方案采矿，都不会挖取第四层的那块长方形块，因此在研究最优采矿方案中只考虑前三层的长方形块。根据题目条件，挖取深层次的长方形块的前提是必须先挖取其前一层次相对应的长方形块。例如，若挖取第二层的第一块长方形块，则必须先挖取第一层的左上角的四块长方形块。因为深层次的长方形块具有是否挖取前一层次相对应的长方形块的权力，所以称深层的长方形块为“高层长方形块”。逆向思考，先确定高层长方形块的挖取是否能盈利，而后再确定低层长方形块是否挖取。2.1.2模型的建立求解首先给各层的长方形块编号，其示意图分别如图2、图3和图4所示。12345678910111213141516 图2 第一层123456789图3 第二层1234图4 第三层根据各块含纯金属的百分数作为块的值建立其价值矩阵为，分别代表第一层、第二层和第三层的价值矩阵。根据题中给出的数据，得到：；.公司纯收入大于0时为盈利，小于0时为亏损。下面单独考虑每一个长方形块的盈利和亏损情况。根据题中条件，第一层中各块的挖取费用为0.3万元，第二层为0.6万元，第三层为0.8万元；而一个价值挖取一块的收入同该块的值成正比，一个值为的块可得收入为0.2万元。因此，可以根据每一个长方形块的盈亏情况，将每一个长方形的值转移为其盈亏情况，建立“转移矩阵” ，即表示每一个长方形块的盈亏值，其计算公式为每一长方形块的值乘以，减去每一层的挖取费。计算得到：；.从矩阵中可以观察到，第一层中只有第6块长方形块能够盈利，得到以下推论：1、在挖取多个层（二或三）的长方形块的时候若要盈利，必须在“高层长方形块”选择盈利的长方形块（至少不亏损），否则必将亏损。2、在考虑同一层的长方形块时，挖取盈利的长方形块后，若挖取亏损的长方形块，则总盈利必将减少，甚至亏损。推论的证明（反证法）：推论1的证明：假设在挖取多个层（二或三）的长方形块的时候，挖取亏损的长方形块。第三层没有亏损的长方形块，故不用考虑。即在挖第二层的时候，挖取第3或第6或第7或第8或第9块长方形块，而其在第一层所相对应的长方形块的盈利值都是小于0的，故若在挖第二层的时候，挖取第3或第6或第7或第8或第9块长方形块，必将亏损。推论1证毕。推论2的证明：假设在考虑同一层的长方形块时，挖取盈利的长方形块后，挖取亏损的长方形块。第三层没有亏损的长方形块，故也不用考虑。第一层的证明较简单，盈利的只有第6块长方形块，在挖取第6块之后，若在挖取其它任何一块亏损的长方形块，其总盈利必将减少。在证明第二层时，最大的盈利值仅为0.2，而最小的亏损值也为0,2，且亏损的长方形块在第一层所对应的长方形块的盈亏值都是小于0的，所以若挖取盈利的长方形块后，若挖取亏损的长方形块，则总盈利必将减少。推论2证毕。下面利用这两个推论，开始研究挖取方案。逆向思考，从第三层开始挖取。先考虑挖取一块的情况。例如挖取第三层第4块，则必须挖取第二层的第5、6、8和9块长方形块以及第一层的第6、7、8、10、11、12、14、15和16块长方形块，则其盈亏值之和为-2.1万元。用同样的方法得到第三层各块长方形块的盈亏值如表1所示。表1 第二层各块长方形块的盈亏值长方形块1234盈亏值（万元）1.75-0.65-0.95-2.1由表1容易得到，只有在挖取第1块长方形块的时候盈利，其他情况下都亏损，若第三层挖取两块、三块或四块时，根据推论2，其盈利值必然减少，故不用考虑。故若最优采矿方案中挖取第三层，则只挖取第1块，其收入为1.75万元。若最优采矿方案中第三层都不挖取，从第二层开始挖取，采用如上述同样的方法，则可得到第二层各块长方形块的盈亏值如表2所示。表2 第二层各块长方形块的盈亏值长方形块123456789盈亏值（万元）0.30.3-0.5-0.1-0.15-0.9-0.5-0.8-1.3由表2得到，第二层只挖取一块的方案能获得的最大收入为0.3万元。所以这种方案不是最优的。若第二层挖取两块，观察，只有第1和2块的盈利值大于0，其他长方形块都不盈利，必然挖取第11和12块，其盈亏值为0.5万元，亦不是最优方案；挖取三块或更多块的时候，由推论2其盈亏值都只会更小，故也无需考虑。若第二层也都不挖取，只挖取第一层的长方形块，显然只有挖取第22块会盈利，其值为0.1万元，亦不是最优方案。综上所述，挖取第三层第1块长方形块的时候，收入是最大的，其值为1.75万元。这就是纯收入最大的采矿方案，即该公司应该挖取第一层的第1、2、3、5、6、7、9、10、11块，第二层的第1、2、4、5块和第三层的第1块长方形块时，收入与费用（即纯收入）之差最大，其值为1.75万元。2.2模型2：单目标线性规划模型2.2.1模型的分析对于本题，一个较为简单的方法就是利用穷举法来实现，即利用计算机模拟出所有的挖取方案，然后求解出其收入和费用之差，最后确定挖取方案，但这种方法运算比较繁杂，容易出错。为此，根据题目的要求设计提出了一种可行的推算挖取方案的算法倒推法。（1）算法的思想根据题目中的条件，在挖取某一层中的一块时必须把上一层对应的四块全部挖取（第一层除外），根据这个条件，采取倒推的方法在算法中会相对容易实现，算法中用矩阵来确定对应块是否挖取，并通过各层之间的联系，算出各层的挖取方案，最终计算出收入与费用之差最大的挖取方案。（2）算法的基本步骤步骤1 建立一个三维扩充矩阵，其元素为，分别表示第一、二、三层，分别表示各层各长方形块的坐标，表示各长方形块的值。同时建立一个三维矩阵，其元素为，如果表示第层的坐标为块不挖取，如则表示挖取。步骤2 确定三维矩阵的值。根据倒退法，如果挖取第层中的坐标为的长方形块，则它所对应的第层坐标为的长方形块必须被挖取，即其三维矩阵对应的值为1。步骤3 根据步骤二中的矩阵计算收入，其值为所有被挖取的长方形块的值乘以后求和。步骤4 根据步骤二中的矩阵计算费用，其值等于所有被挖取的长方形块的挖取费用之和。步骤5 求出收入与费用之差的最大值。2.1.2模型的建立求解分析题中所设定的长方形块的水平位置关系，其俯视图为如图5所示的情形。图5 长方形块水平位置关系俯视图为了表达清晰，易于模型推广，将三个不同层长方形块的值的矩阵用同一个扩充矩阵来表示，建立一个的三维扩充矩阵，其元素为，分别表示第一、二、三层，分别表示各层各长方形块的坐标。根据题中所给数据，可以得到：，.同时建立一个的三维矩阵，其元素为，。用表示第层的坐标为的长方形块不挖取，则表示挖取。根据倒退法，如果挖取第层中的坐标为的长方形块，则它所对应的第层坐标为的长方形块必须被挖取，即其三维矩阵，所对应的值必为1。根据夹逼准则，它们应该满足以下关系：设该公司采矿得到的收入为万元，则有：.设该公司采矿所花的费用为万元，则有：，其中表示各层的挖取费:.设该公司采矿的盈利为万元，则:.综上所述，得到单目标线性规划模型：利用LINGO软件编程求解（具体程序见附录1），求得结果如下：，.由矩阵中的值（0表示不挖取，1表示挖取），可以得到结论：该公司最优的采矿方案是挖取第一层的第1、2、3、5、6、7、9、10、11块，第二层的第1、2、4、5块和第三层的第1块长方形块。采用这种采矿方案能获得最大的纯收入为1.75万元。具体的采矿方案如图6所示（铲子表示挖取）。第二层第一层 第三层第四层图6 采矿方案示意图五、模型的评价本文针对采矿方案的优化问题，建立了两个不同的数学模型，找到了采矿的最优方案，对公司的决策具有很强的现实指导意义。模型1的方法比较原始，简单易懂，但本文使用了“转移矩阵”的方法，使得最优方案的求解过程大大简化。模型1的缺点是其方法难以推广，但模型2可以很好的弥补这个缺陷。如果改变开采条件,如各块的值、各块的费用等，只要更改相应矩阵的数据，就能很快地得到最优方案。六、模型的进一步探讨采用微分的思想，将各块长方形块进行划分，例如将每块长方形块等分成八份，即长宽高各平分成两份，则新的长方形块的水平尺寸为25m x 25m，铅直尺寸为12.5m。那么，第一层将含有个块，假设纯金属在矿砂中平均分布，则各块的值变为如表3所示：表3 第一层各块的值1.51.51.51.51.51.50.750.751.51.51.51.51.51.50.750.751.51.52.02.01.51.50.750.751.51.52.02.01.51.50.750.751.01.01.01.00.750.750.50.51.01.01.01.00.750.750.50.50.750.750.750.750.50.50.250.250.750.750.750.750.50.50.250.25建立新的扩充矩阵，按照模型2的思路，就可以解出新的最优解。通过计算得到最大收入为1.127万元。这说明，这种方法不能给公司带来更多的收入。其具体程序见附录2。参考文献1.袁新生 邵大宏等 LINGO和excel在数学建模中的应用科学出版社 2007年1月出版附录1MODEL:sets: wei/1.9/:b; kk/1.3/:c; w(kk,wei,wei):b,m; ww(wei,wei):aa;endsetsdata:m=0，0，0，0，0，0，0，0，00，1.5，0，1.5，0，1.5，0，0.75，00，0，0，0，0，0，0，0，00，1.5，0，2，0，1.5，0，0.75，00，0，0，0，0，0，0，0，00，1，0，1，0，0.75，0，0.5，00，0，0，0，0，0，0，0，00，0.75，0，0.75，0，0.5，0，0.25，00，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，00，0，4，0，4，0，2，0，00，0，0，0，0，0，0，0，00，0，3，0，3，0，1，0，00，0，0，0，0，0，0，0，00，0，2，0，2，0，0.5，0，00，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，00 ，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，00，0，0，12，0，6，0，0，00，0，0，0，0，0，0，0，00，0，0，5，0，4，0，0，00，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0;c=0.3 0.6 0.8;enddatafor(w(k,i,j):b(k,i,j)=0;b(k-1,i+1,j+1)-b(k,i,j)=0;b(k-1,i-1,j-1)-b(k,i,j)=0;b(k-1,i-1,j+1)-b(k,i,j)=0;);zp=0.2*sum(w(k,i,j):m(k,i,j)*b(k,i,j);zc=sum(w(k,i,j):c(k)*b(k,i,j);max=zp-zc;end附录2MODEL:sets:wei/1.17/:s;kk/1.8/:c;w(kk,wei,wei):b,m;ww(wei,wei):aa;endsetsdata:m=0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，1.5，0，1.5 0，1.5 0，1.5，0，1.5，0，1.5，0，0.75，0，0.75，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，1.5，0，1.5 0，1.5 0，1.5，0，1.5，0，1.5，0，0.75，0，0.75，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，1.5，0，1.5 0，2，0，2，0，1.5，0，1.5，0，0.75，0，0.75，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，1.5，0，1.5 0，2，0，2，0，1.5，0，1.5，0，0.75，0，0.75，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，1，0，1，0，1，0，1，0，0.75，0，0.75，0，0.5，0，0.5，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，1，0，1，0，1，0，1，0，0.75，0，0.75，0，0.5，0，0.5，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0.75，0，0.750，0.750，0.75，0，0.5，0，0.5，0，0.25，0，0.25，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0.75 0 0.750，0.750，0.75，0，0.5，0，0.5，0，0.25，0，0.25，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，1.5 0，1.5，0，1.50，1.5，0，1.5，0，1.125，0，0.75，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，1.5 0，1.5，0，1.750，1.625，0，1.5，0，1.125，0，0.75，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，1.5 0，1.750 2，0，1.75，0，1.5，0，1.125，0，0.75，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，1.250，1.3750 1.5，0，1.3125，0，1.125，0，0.875，0 0.6250，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，1，0，1，0，1，0，0.875，0，0.75，0，0.625，0，0.5，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0.8750，0.8750，0.875，0，0.75，0，0.625，0，0.5，00.375，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0.750，0.750 0.750，0.625，0，0.5，0，0.375，0，0.25，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，4，0，4，0，4，0，4，0，2，0，2，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，4，0，4，0，4，0，4，0，2，0，2，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，3，0，3，0，3，0，3，0，1，0，1，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，3，0，3，0，3，0，3，0，1，0，1，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，2，0，2，0，2，0，2，0，0.5，0，0.5，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，2，0，2，0，2，0，2，0，0.5，0，0.5，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，4，0，4，0，4，0，3，0，2，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，3.5，0，3.50，3.5，0，2.5，0，1.5，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，3，0，3，0，3，0，2，0，1，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，2.5，0，2.50，2.5，0，1.625，0，0.75，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，2，0，2，0，2，0，1.25，0，0.5，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，12 0，12，0，6，0，6，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，12 0，12，0，6，0，6，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，5，0，5，0，4，0，4，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，5，0，5，0，4，0，4，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，12，0，9，0，6，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，8.50，6.75，0，5，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，5，0，4.5，0，4，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，00，0，0，0