基于植樹(shù)問(wèn)題的建模分析與再求解

曹迎槐

武警海警學(xué)院 情報(bào)偵察系 浙江 寧波 315801

引言

筆者在《基于植樹(shù)問(wèn)題的建模分析與求解》一文中，已詳細(xì)介紹了“基于人員數(shù)量的求解”和“基于完成模式的求解”兩種思路，本文將繼續(xù)介紹另外兩種分析角度。

1 植樹(shù)問(wèn)題的想定描述

為了對(duì)比分析不同求解思路之優(yōu)劣，植樹(shù)問(wèn)題想定依然保持不變。即：某單位組織植樹(shù)活動(dòng)，其中有男同志M1人，女同志M2人。一般植樹(shù)活動(dòng)涉及挖坑、填土和澆水三個(gè)步驟，因男女體能等區(qū)別完成各步能力差異較大。假設(shè)男生可單獨(dú)挖坑a（或填土b，或澆水c）個(gè)，而女生可單獨(dú)挖坑d（或填土e，或澆水f）個(gè)。試問(wèn)：如何安排每名同志的具體任務(wù)分工可使最后完成的植樹(shù)總棵數(shù)最多？

同樣要求，植樹(shù)過(guò)程中每棵樹(shù)都必須經(jīng)過(guò)挖坑、填土和澆水三個(gè)步驟才能完成；允許一個(gè)人承擔(dān)多項(xiàng)工作，諸如挖幾個(gè)坑之后，再澆幾棵樹(shù)等；且任意一個(gè)坑的挖坑過(guò)程只能由一個(gè)人獨(dú)立完成，填土和澆水也類(lèi)似。也即，挖坑、填土和澆水這三個(gè)工作不可再細(xì)分，它們都已經(jīng)是最基本的工作單位[1]。

2 基于工作單元數(shù)量的分配求解

2.1 思路分析

既然挖坑、填土和澆水這三個(gè)工作不可再細(xì)分，它們都已是最基本的工作單位，所以，最直接的想法就是分別設(shè)這些基本工作的分配情況。于是可設(shè)，男同志挖坑總數(shù)為：x1；男同志填土總數(shù)為：x2；男同志澆水總數(shù)為：x3；女同志挖坑總數(shù)為：x4；女同志填土總數(shù)為：x5；女同志澆水總數(shù)為：x6；植樹(shù)總棵數(shù)為：x7。

值得注意的是，我們?cè)O(shè)的是男同志挖坑的總數(shù)，而不是挖坑的男同志人數(shù)，雖然兩者之間有關(guān)系，可以直接相互轉(zhuǎn)換，但含義是不同的。

既然男同志挖坑總數(shù)為x1，所以可知挖坑的男同志人數(shù)即x1 / a；同理，填土的男同志人數(shù)即x2 / b、澆水的男同志人數(shù)即x3 / c。

容易理解，在男同志中，“挖坑的人數(shù)”+“填土的人數(shù)”+“澆水的人數(shù)”，不能超過(guò)M1，即， x1 / a + x2 / b + x3 /c ≤ M1。

同樣道理，對(duì)于女同志而言，也可得出類(lèi)似的結(jié)論。即，在女同志中，“挖坑的人數(shù)”+“填土的人數(shù)”+“澆水的人數(shù)”，不能超過(guò)M2，所以有：x4 / d + x5 / e + x6 / f ≤ M2。

接著，再考慮“挖坑”的情況。因?yàn)?，男同志挖坑總?shù)為x1，女同志挖坑總數(shù)為x4，共植樹(shù)總棵數(shù)為x7，顯然，最后的總棵數(shù)不會(huì)大于男、女同志挖坑之和，不然就意味著有幾個(gè)坑最后沒(méi)種上樹(shù)，存在工作浪費(fèi)顯現(xiàn)，說(shuō)明工作分配不合理，未達(dá)最優(yōu)。

于是應(yīng)存在：x7 ≤ x1 + x4 。

同理，依次分析“填土”的情況。因?yàn)椋型咎钔量倲?shù)為x2，女同志填土總數(shù)為x5，共植樹(shù)的總棵數(shù)為x7，顯然，最后總棵數(shù)不會(huì)大于男同志、女同志填土數(shù)之和，不然同樣存在浪費(fèi)顯現(xiàn)，所以應(yīng)該有：x7 ≤ x2 + x5。

繼續(xù)分析“澆水”情況，做類(lèi)似分析，因男同志澆水總數(shù)為x2，女同志澆水總數(shù)為x5，共植樹(shù)的總棵數(shù)為x7，故最后的總棵數(shù)不會(huì)大于男女澆水之和，即：x7 ≤ x3 + x6。

對(duì)于我們?cè)谇懊娑x的各個(gè)決策變量，顯然都應(yīng)該取非負(fù)，即：

該問(wèn)題目標(biāo)追求明確，為使最后植樹(shù)的總棵數(shù)最多，應(yīng)有，max Z = x7。

2.2 匯總LP模型

歸納前面的諸多分析，匯總之可得出如下LP模型：

依然取想定數(shù)據(jù)為：a=10，b=15，c=20，d=5，e=10，f=15，且M1=30，M2=20，將其代入上述LP模型，標(biāo)準(zhǔn)化之，并用大M法求解，得對(duì)應(yīng)之初始單純形表如表1所示。

經(jīng)過(guò)9次旋轉(zhuǎn)迭代運(yùn)算，最后可得其最終單純形表如表2所示。

表2 植樹(shù)問(wèn)題之最終單純形表

2.3 結(jié)果分析

由最終單純形表2可知，該問(wèn)題之最優(yōu)解為：

植樹(shù)的總棵數(shù)為：x7=3900/19≈205.3（棵）。

具體任務(wù)分工為：男同志：挖坑3900/19≈205.27個(gè)；填土2700/19≈142.11個(gè)；女同志：填土1200/19≈63.16個(gè)；澆水3900/19≈205.27個(gè)。

顯然與《基于植樹(shù)問(wèn)題的建模分析與求解》一中的兩種求解結(jié)果相一致。[2]。

3 基于男女體能差異的分配求解

觀察具體的想定數(shù)據(jù)可以看出，在種樹(shù)的三項(xiàng)分工中，無(wú)論是挖坑、填土還是澆水，男同志的工作能力都要強(qiáng)于女同志，但男女的工作能力差在三項(xiàng)分工中并不一樣。男同志挖坑的工作能力是10，女同志的工作能力是5，這相當(dāng)于2個(gè)女同志等于1個(gè)男同志的工作能力，而填土則是3個(gè)女同志等于2個(gè)男同志的工作能力，澆水是4個(gè)女同志等于3個(gè)男同志的工作能力。而我們又不能不分配給女同志勞動(dòng)任務(wù)，所以女同志應(yīng)優(yōu)先考慮澆水，而男同志應(yīng)優(yōu)先考慮挖坑。

根據(jù)該植樹(shù)問(wèn)題之想定案例中的數(shù)據(jù)，我們假設(shè)男同志全部挖坑，一共可以挖300個(gè)坑，假設(shè)女同志全澆水，一共可以澆300棵樹(shù)的水。不妨從男同志挖坑的30人中抽出X人填土，從女同志澆水的20人抽出Y人填土，以使最后能滿足‘挖坑數(shù)=填土數(shù)=澆水?dāng)?shù)’的要求，如此便可完成分配任務(wù)。即：10（30 -x）= 15 x + 10 y = 15（20- y）。

x和y均應(yīng)非負(fù)，且有：1≤x≤30；1≤ y≤20。

基于VC++6的編程即可輕松解決該不定方程問(wèn)題，如圖1，其運(yùn)行結(jié)果如圖2。

當(dāng)然，我們必須注意到，圖2并未直接給出如同前面三種解法中那樣的精確結(jié)果，但我們從圖2不難看出，當(dāng)男同志抽出9人去填土（可填135個(gè)），剩下的11人都去挖坑，所以共挖坑可達(dá)210。女同志根據(jù)男同志可挖坑210來(lái)計(jì)算保留澆水的人數(shù)為14人，故可抽出6人去填土（可填60個(gè)），所以，填土的總數(shù)為135+60=195個(gè)。就是說(shuō)，挖坑的男同志分配多了，澆水的女同志也分配多了。根據(jù)想定案例給定的數(shù)據(jù)可知，只需從挖坑的男同志和澆水的女同志中各抽出1人，再做進(jìn)一步的細(xì)分處理方可[3]。

如此，男同志實(shí)為20人挖坑，共可挖200個(gè)；女同志實(shí)為13人澆水，共可澆195個(gè)；男同志9人填土135個(gè)，女同志6人填土60個(gè)，共填土195個(gè)。于是，問(wèn)題進(jìn)一步簡(jiǎn)化成：1名男同志和1名女同志，在已有200個(gè)坑，195個(gè)已填土，195個(gè)已澆水的基礎(chǔ)，如何分配二人的體能，在挖坑、填土和澆水之間做取舍，以使得總植樹(shù)數(shù)最多。其實(shí)，接下來(lái)的思路依然是男同志盡量考慮挖坑，而女同志則盡量考慮澆水，不妨做如下考慮。

設(shè)，該男同志挖坑x1個(gè)，填土x2個(gè)，該女同志填土y1個(gè)，澆水y2個(gè)，應(yīng)使最后的挖坑、填土和澆水總數(shù)盡量接近即可。故有： 200+ x1 ≈ 195+x2+y1 ≈ 195+y2

顯然該問(wèn)題沒(méi)有精確的整數(shù)解，所以，近似是必然的。為實(shí)現(xiàn)對(duì)最后這1男1女的任務(wù)精細(xì)化分配，同樣可借助編程實(shí)現(xiàn)之。只需考慮該男同志的挖坑數(shù)從1—10遍歷，進(jìn)而考慮他的剩余體能轉(zhuǎn)去填土，根據(jù)他填土的情況，轉(zhuǎn)而計(jì)算最后這名女同志的填土和澆水情況，然后記錄這種分配的挖坑、填土和澆水的相近程度，記錄下這個(gè)相近程度，等遍歷完成后，看看哪個(gè)相近程度最小，那便是最優(yōu)解。其代碼如圖3所示，運(yùn)行結(jié)果如圖4所示[4]。

圖4 圖3中VC程序代碼之運(yùn)行結(jié)果

仔細(xì)觀察圖4之運(yùn)行結(jié)果可以看出，在最后1名男同志先挖5個(gè)坑之后，再利用剩余體力填土7個(gè)。至此，挖坑一共200+5=205個(gè)，填土已達(dá)195+7=202個(gè)。于是，最后1名女同志只好根據(jù)這205個(gè)坑和202個(gè)填土數(shù)，為使總填土數(shù)與總挖坑數(shù)盡量接近，她應(yīng)該填土3個(gè)，剩下的體力全部用于澆水，還可再澆10個(gè)，加上原來(lái)已有的195個(gè)，正好也是205。

于是，問(wèn)題得解，分配方案不僅與前文的解法結(jié)果一致，也與文獻(xiàn)[1]之結(jié)果相同。

因水平所限制，不妥之處敬請(qǐng)廣大讀者批評(píng)指正。