基于植树问题的建模分析与再求解

曹迎槐

武警海警学院 情报侦察系 浙江 宁波 315801

引言

笔者在《基于植树问题的建模分析与求解》一文中，已详细介绍了“基于人员数量的求解”和“基于完成模式的求解”两种思路，本文将继续介绍另外两种分析角度。

1 植树问题的想定描述

为了对比分析不同求解思路之优劣，植树问题想定依然保持不变。即：某单位组织植树活动，其中有男同志M1人，女同志M2人。一般植树活动涉及挖坑、填土和浇水三个步骤，因男女体能等区别完成各步能力差异较大。假设男生可单独挖坑a（或填土b，或浇水c）个，而女生可单独挖坑d（或填土e，或浇水f）个。试问：如何安排每名同志的具体任务分工可使最后完成的植树总棵数最多？

同样要求，植树过程中每棵树都必须经过挖坑、填土和浇水三个步骤才能完成；允许一个人承担多项工作，诸如挖几个坑之后，再浇几棵树等；且任意一个坑的挖坑过程只能由一个人独立完成，填土和浇水也类似。也即，挖坑、填土和浇水这三个工作不可再细分，它们都已经是最基本的工作单位[1]。

2 基于工作单元数量的分配求解

2.1 思路分析

既然挖坑、填土和浇水这三个工作不可再细分，它们都已是最基本的工作单位，所以，最直接的想法就是分别设这些基本工作的分配情况。于是可设，男同志挖坑总数为：x1；男同志填土总数为：x2；男同志浇水总数为：x3；女同志挖坑总数为：x4；女同志填土总数为：x5；女同志浇水总数为：x6；植树总棵数为：x7。

值得注意的是，我们设的是男同志挖坑的总数，而不是挖坑的男同志人数，虽然两者之间有关系，可以直接相互转换，但含义是不同的。

既然男同志挖坑总数为x1，所以可知挖坑的男同志人数即x1 / a；同理，填土的男同志人数即x2 / b、浇水的男同志人数即x3 / c。

容易理解，在男同志中，“挖坑的人数”+“填土的人数”+“浇水的人数”，不能超过M1，即， x1 / a + x2 / b + x3 /c ≤ M1。

同样道理，对于女同志而言，也可得出类似的结论。即，在女同志中，“挖坑的人数”+“填土的人数”+“浇水的人数”，不能超过M2，所以有：x4 / d + x5 / e + x6 / f ≤ M2。

接着，再考虑“挖坑”的情况。因为，男同志挖坑总数为x1，女同志挖坑总数为x4，共植树总棵数为x7，显然，最后的总棵数不会大于男、女同志挖坑之和，不然就意味着有几个坑最后没种上树，存在工作浪费显现，说明工作分配不合理，未达最优。

于是应存在：x7 ≤ x1 + x4 。

同理，依次分析“填土”的情况。因为，男同志填土总数为x2，女同志填土总数为x5，共植树的总棵数为x7，显然，最后总棵数不会大于男同志、女同志填土数之和，不然同样存在浪费显现，所以应该有：x7 ≤ x2 + x5。

继续分析“浇水”情况，做类似分析，因男同志浇水总数为x2，女同志浇水总数为x5，共植树的总棵数为x7，故最后的总棵数不会大于男女浇水之和，即：x7 ≤ x3 + x6。

对于我们在前面定义的各个决策变量，显然都应该取非负，即：

该问题目标追求明确，为使最后植树的总棵数最多，应有，max Z = x7。

2.2 汇总LP模型

归纳前面的诸多分析，汇总之可得出如下LP模型：

依然取想定数据为：a=10，b=15，c=20，d=5，e=10，f=15，且M1=30，M2=20，将其代入上述LP模型，标准化之，并用大M法求解，得对应之初始单纯形表如表1所示。

经过9次旋转迭代运算，最后可得其最终单纯形表如表2所示。

表2 植树问题之最终单纯形表

2.3 结果分析

由最终单纯形表2可知，该问题之最优解为：

植树的总棵数为：x7=3900/19≈205.3（棵）。

具体任务分工为：男同志：挖坑3900/19≈205.27个；填土2700/19≈142.11个；女同志：填土1200/19≈63.16个；浇水3900/19≈205.27个。

显然与《基于植树问题的建模分析与求解》一中的两种求解结果相一致。[2]。

3 基于男女体能差异的分配求解

观察具体的想定数据可以看出，在种树的三项分工中，无论是挖坑、填土还是浇水，男同志的工作能力都要强于女同志，但男女的工作能力差在三项分工中并不一样。男同志挖坑的工作能力是10，女同志的工作能力是5，这相当于2个女同志等于1个男同志的工作能力，而填土则是3个女同志等于2个男同志的工作能力，浇水是4个女同志等于3个男同志的工作能力。而我们又不能不分配给女同志劳动任务，所以女同志应优先考虑浇水，而男同志应优先考虑挖坑。

根据该植树问题之想定案例中的数据，我们假设男同志全部挖坑，一共可以挖300个坑，假设女同志全浇水，一共可以浇300棵树的水。不妨从男同志挖坑的30人中抽出X人填土，从女同志浇水的20人抽出Y人填土，以使最后能满足‘挖坑数=填土数=浇水数’的要求，如此便可完成分配任务。即：10（30 -x）= 15 x + 10 y = 15（20- y）。

x和y均应非负，且有：1≤x≤30；1≤ y≤20。

基于VC++6的编程即可轻松解决该不定方程问题，如图1，其运行结果如图2。

当然，我们必须注意到，图2并未直接给出如同前面三种解法中那样的精确结果，但我们从图2不难看出，当男同志抽出9人去填土（可填135个），剩下的11人都去挖坑，所以共挖坑可达210。女同志根据男同志可挖坑210来计算保留浇水的人数为14人，故可抽出6人去填土（可填60个），所以，填土的总数为135+60=195个。就是说，挖坑的男同志分配多了，浇水的女同志也分配多了。根据想定案例给定的数据可知，只需从挖坑的男同志和浇水的女同志中各抽出1人，再做进一步的细分处理方可[3]。

如此，男同志实为20人挖坑，共可挖200个；女同志实为13人浇水，共可浇195个；男同志9人填土135个，女同志6人填土60个，共填土195个。于是，问题进一步简化成：1名男同志和1名女同志，在已有200个坑，195个已填土，195个已浇水的基础，如何分配二人的体能，在挖坑、填土和浇水之间做取舍，以使得总植树数最多。其实，接下来的思路依然是男同志尽量考虑挖坑，而女同志则尽量考虑浇水，不妨做如下考虑。

设，该男同志挖坑x1个，填土x2个，该女同志填土y1个，浇水y2个，应使最后的挖坑、填土和浇水总数尽量接近即可。故有： 200+ x1 ≈ 195+x2+y1 ≈ 195+y2

显然该问题没有精确的整数解，所以，近似是必然的。为实现对最后这1男1女的任务精细化分配，同样可借助编程实现之。只需考虑该男同志的挖坑数从1—10遍历，进而考虑他的剩余体能转去填土，根据他填土的情况，转而计算最后这名女同志的填土和浇水情况，然后记录这种分配的挖坑、填土和浇水的相近程度，记录下这个相近程度，等遍历完成后，看看哪个相近程度最小，那便是最优解。其代码如图3所示，运行结果如图4所示[4]。

图4 图3中VC程序代码之运行结果

仔细观察图4之运行结果可以看出，在最后1名男同志先挖5个坑之后，再利用剩余体力填土7个。至此，挖坑一共200+5=205个，填土已达195+7=202个。于是，最后1名女同志只好根据这205个坑和202个填土数，为使总填土数与总挖坑数尽量接近，她应该填土3个，剩下的体力全部用于浇水，还可再浇10个，加上原来已有的195个，正好也是205。

于是，问题得解，分配方案不仅与前文的解法结果一致，也与文献[1]之结果相同。

因水平所限制，不妥之处敬请广大读者批评指正。