基于植樹問題的建模分析與再求解

曹迎槐

武警海警學院 情報偵察系 浙江 寧波 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]之結果相同。

因水平所限制，不妥之處敬請廣大讀者批評指正。