數(shù)學(xué)規(guī)劃在測(cè)繪工作中的應(yīng)用

于祖國(guó)YU Zu-guo

（昆明理工大學(xué)國(guó)土資源學(xué)院，昆明 650000）

（Facu1ty of Land Resources Engineering，Kunming University of Science and Techno1ogy，Kunming 650000，China）

0 引言

測(cè)繪是國(guó)民經(jīng)濟(jì)建設(shè)和發(fā)展的重要基礎(chǔ)性前期工作。隨著經(jīng)濟(jì)的發(fā)展，現(xiàn)代測(cè)繪的生產(chǎn)規(guī)模日益擴(kuò)大，分工越來(lái)越細(xì)，要求測(cè)繪生產(chǎn)組織必須具有高度計(jì)劃性。將數(shù)學(xué)規(guī)劃的方法運(yùn)用于測(cè)繪工作中，對(duì)測(cè)繪工作實(shí)施過(guò)程中各種錯(cuò)綜復(fù)雜的數(shù)量關(guān)系進(jìn)行研究，并歸結(jié)成一定的數(shù)學(xué)模型，用數(shù)學(xué)方法找到最合理的工作方案，在保證工程要求和精度要求的前提下，可以達(dá)到提高工作效率，減少生產(chǎn)消耗的人力、物力、財(cái)力的目的。

1 線性規(guī)劃的應(yīng)用

在測(cè)繪經(jīng)營(yíng)管理中，經(jīng)常要解決兩類(lèi)問(wèn)題：一類(lèi)是對(duì)于某項(xiàng)確定的生產(chǎn)任務(wù)，如何使用最少的資源，保質(zhì)保量的完成測(cè)繪任務(wù)；另一類(lèi)是對(duì)于有限的資源，如何安排使其最大限度的發(fā)揮作用，取得更多的測(cè)繪成果。對(duì)于這些問(wèn)題，都可以應(yīng)用線性規(guī)劃的方法，通過(guò)建立數(shù)字模型、求解、應(yīng)用，科學(xué)合理地解決。這里以一例說(shuō)明線性規(guī)劃問(wèn)題在測(cè)繪工作中的應(yīng)用。

現(xiàn)有某測(cè)繪單位為下月生產(chǎn)計(jì)劃做安排，該測(cè)繪單位計(jì)劃安排建筑物放線、1:500竣工測(cè)量?jī)煞N種測(cè)繪工作。已知該測(cè)繪單位生產(chǎn)的定額為：建筑物放線每件需要外業(yè)2工天，內(nèi)業(yè)3工天，檢查1天；1:500竣工測(cè)量每幅需要外業(yè)6工天，內(nèi)業(yè)5工天，檢查2工天。而該單位下月總得生產(chǎn)能力為：外業(yè)生產(chǎn)240工天，內(nèi)業(yè)生產(chǎn)220工天，生產(chǎn)檢查90工天。建筑物放線測(cè)繪獲利為720元/件，1:500竣工測(cè)量為1600元/幅。那么該測(cè)繪單位應(yīng)如何安排測(cè)繪工作以使收益最大？

在本問(wèn)題中，根據(jù)已有條件可以設(shè)：下月進(jìn)行建筑物放線x1件，1:500竣工測(cè)量x2件，根據(jù)線性規(guī)劃的理論，可以建立模型。

則希望獲得的最大產(chǎn)值的目標(biāo)函數(shù)為：

約束條件為：

在上述數(shù)學(xué)模型中加入松弛變量，得到以下標(biāo)準(zhǔn)形式：Max z'=720x1+1600x2

用單純形法求出上述問(wèn)題的最優(yōu)解，得到最終表為：

表1

通過(guò)單純形表可以求出此線性規(guī)劃問(wèn)題的最優(yōu)解，即建筑物放線15件，1:500竣工測(cè)量35幅。

最大收益為 max z=15×720+35×1600=66800（元）

2 人工變量法

在實(shí)際測(cè)繪工作中，并不是所有的時(shí)候都如上述問(wèn)題一樣，約束條件都是“≤”式，而有可能出現(xiàn)“≥”式或“=”式，這是很有可能的。當(dāng)約束條件是“≥”式或“=”式時(shí)，將建立的線性規(guī)劃模型的一般形式化為標(biāo)準(zhǔn)形式后，約束條件系數(shù)矩陣中就不包含有單位矩陣。這種情況下我們需要使用人工變量法，通過(guò)加入人工變量的方式，人為的構(gòu)造一個(gè)單位矩陣來(lái)求解問(wèn)題。這里我們通過(guò)大M法求解。

依然沿用線性規(guī)劃中的例子，如果根據(jù)實(shí)際工作情況，要求內(nèi)業(yè)工天不小于為220工天，檢查工天恰好為90工天，此時(shí)應(yīng)如何安排工作使收益最大。

此問(wèn)題的數(shù)學(xué)模型就變成

在約束條件中分別加入松弛變量x4、剩余變量x5、人工變量 x6、x7，得到 Max z=720x1+1600x2+0x3+0x4-Mx5-Mx6

這里M是一個(gè)任意大的正數(shù)。

通過(guò)單純形法可以求出此線性規(guī)劃問(wèn)題的最優(yōu)解，即建筑物放線30件，1:500竣工測(cè)量30幅。

最大收益為 max z=30×720+30×1600=69600（元）

3 靈敏度分析

當(dāng)線性規(guī)劃的系數(shù)aij、bi、cj發(fā)生變化時(shí)，最優(yōu)解也可能會(huì)隨之發(fā)生變化。雖然通過(guò)重新使用線性規(guī)劃的單純形法能夠求解，但是這樣既麻煩又沒(méi)有必要。通過(guò)靈敏度分析的方法則可以比較方便的求出這些參數(shù)的變化對(duì)最優(yōu)解的影響。

3.1 技術(shù)系數(shù)aij的變化 在實(shí)際的測(cè)繪工作中，由于生產(chǎn)規(guī)范、人員變動(dòng)、技術(shù)發(fā)展乃至天氣變化等等因素，都可能導(dǎo)致技術(shù)系數(shù)aij發(fā)生變化。依然沿用上例，但是由于測(cè)量工作要求，生產(chǎn)時(shí)間發(fā)生變化，現(xiàn)在放線需要外業(yè)2工天，內(nèi)業(yè)2工天，檢查1工天。此時(shí)就是技術(shù)系數(shù)aij發(fā)生了變化。應(yīng)如何安排工作。

代入表1，并通過(guò)單純形法計(jì)算，可得x1=30，x2=30。說(shuō)明當(dāng)技術(shù)系數(shù)發(fā)生變化時(shí)，最優(yōu)解也隨之發(fā)生變化。

3.2 資源系數(shù)bi變化 在實(shí)際測(cè)繪工作中，在根據(jù)問(wèn)題建立數(shù)學(xué)模型時(shí)，若將生產(chǎn)能力、儀器、設(shè)備等等視作資源，那么當(dāng)這些資源發(fā)生變化，例如新購(gòu)置一批儀器、增加了新的工作人員等等時(shí)，資源系數(shù)會(huì)發(fā)生變化。仍以上例為例，假設(shè)由于該測(cè)繪單位生產(chǎn)能力增加?，F(xiàn)總的外業(yè)工天增加40工天，內(nèi)業(yè)工天增加40工天，檢查工天增加20工天。此時(shí)顯然資源系數(shù)bi發(fā)生了變化。那么應(yīng)如何安排工作。

②計(jì)算Δb'和b'+Δb'

由于b'+Δb'≥0，原最優(yōu)解仍為最優(yōu)解。否則用對(duì)偶單純形法迭代。這里最大收益為即建筑物放線20件，1:500竣工測(cè)量40幅。

3.3 價(jià)值系數(shù)cj變化 由于市場(chǎng)條件是在不斷變化的，因此在實(shí)際工作當(dāng)中，價(jià)值系數(shù)cj也是會(huì)不斷發(fā)生變化的，這會(huì)對(duì)原來(lái)的決策變量發(fā)生影響。

繼續(xù)引用前文線性規(guī)劃中的例子，由于該測(cè)繪單位業(yè)務(wù)拓展，現(xiàn)在可以新增一種線路工程測(cè)量工作。已知該工作每千米需要外業(yè)5工天，內(nèi)業(yè)3工天，檢查2工天。線路工程測(cè)量的收益為1200元/千米。顯然，此時(shí)價(jià)值系數(shù)cj發(fā)生了變化。是否增加該工作？

根據(jù)要求，設(shè)增加線路工程測(cè)量的計(jì)劃產(chǎn)量為x6，則它的價(jià)值系數(shù)c6=1200，對(duì)應(yīng)的技術(shù)向量P6=(532)T

由于σ6＞0，因此需要按照單純形法繼續(xù)迭代。

代入表1并通過(guò)單純形法計(jì)算可得，x1=22，x2=26，x6=8，此時(shí)收益為 max z=22×720+26×1600+8×1200=67040（元）

顯然，此收益是大于之前只安排兩項(xiàng)工作時(shí)的收益。因此，應(yīng)該安排線路測(cè)量工作。

4 整數(shù)規(guī)劃

在前面的線性規(guī)劃，目標(biāo)規(guī)劃中，求出的最優(yōu)解都有可能包含小數(shù)或分?jǐn)?shù)。而在實(shí)際測(cè)繪生產(chǎn)工作中，由于人員、儀器設(shè)備、控制點(diǎn)個(gè)數(shù)甚至工時(shí)工天都只能是整數(shù)而不能使小數(shù)或分?jǐn)?shù)。此時(shí)如果簡(jiǎn)單的將求得的最優(yōu)解進(jìn)行四舍五入取整，得到的結(jié)果可能不符合約束條件，或者即使?jié)M足約束條件，卻不是最優(yōu)解。此時(shí)，需要通過(guò)整數(shù)規(guī)劃的方法進(jìn)行最優(yōu)解的求解。

仍以上文中的例子為例，假設(shè)由于該測(cè)繪單位擴(kuò)大生產(chǎn)能力，內(nèi)業(yè)工作時(shí)間增加了10工天，總共有230工天。

在這種情況下，依據(jù)線性規(guī)劃的理論，利用單純形法可求得，安排生產(chǎn)22.5件建筑物放線，32.5幅1:500竣工測(cè)量時(shí)，可獲得最大收益68200元。

如果簡(jiǎn)單的通過(guò)四舍五入來(lái)取整，即安排建筑物放線23件，1:500竣工33幅，那么它破壞了約束條件，即超出了實(shí)際生產(chǎn)能力。為了確定最優(yōu)方案，這里通過(guò)分支定界解法求解。

將要求解的整數(shù)規(guī)劃問(wèn)題稱為問(wèn)題A，其對(duì)應(yīng)的線性規(guī)劃問(wèn)題稱為整數(shù)B。

可將原問(wèn)題分解為兩個(gè)子問(wèn)題B1、B2（即兩支），給每支增加一個(gè)約束條件。這并不影響問(wèn)題A的可行域，不考慮整數(shù)條件解問(wèn)題B1、B2，稱此為第一次迭代。

得到最優(yōu)解如表2所示。

繼續(xù)對(duì)問(wèn)題B1和B2進(jìn)行分解，因?yàn)閦1＞z2，故先分解

表2

B1為兩支。分別增加條件x2≤32和x2≥33，得到問(wèn)題B3和問(wèn)題B4，進(jìn)行第二次迭代，得到最優(yōu)解如表3所示。

表3

可見(jiàn)，問(wèn)題B3和問(wèn)題B4的解都已經(jīng)是整數(shù)解。

而問(wèn)題B2的目標(biāo)函數(shù)值z(mì)2=68080，所以可能在67920≤z*≤68080之間有整數(shù)解，因此繼續(xù)對(duì)問(wèn)題B2進(jìn)行分解。得到問(wèn)題B5和B6。（表4）

由于問(wèn)題B5的目標(biāo)函數(shù)值大于所有的整數(shù)解，繼續(xù)對(duì)問(wèn)題B5進(jìn)行分解。（表5）

此時(shí)可以判斷問(wèn)題B4的解x1=21，x2=33為最優(yōu)整數(shù)解。此時(shí)最大收益max Z=z*=67920（元）。

本文以一個(gè)實(shí)例為基礎(chǔ)，分析了線性規(guī)劃、靈敏度分析、整數(shù)規(guī)劃等數(shù)學(xué)規(guī)劃方法在測(cè)繪工作中的應(yīng)用，討論了如何應(yīng)用數(shù)學(xué)規(guī)劃的方法，對(duì)測(cè)繪生產(chǎn)工作進(jìn)行組織安排，以提高生產(chǎn)效率。除此以外，數(shù)學(xué)規(guī)劃在測(cè)繪工作中還可以有其他更多的應(yīng)用，由于篇幅有限，本文不一一討論了。

表4

表5

[1]甘應(yīng)愛(ài)等.運(yùn)籌學(xué)（第三版）[M].清華大學(xué)出版社，2005（6）.

[2]鄭肇葆等.數(shù)學(xué)規(guī)劃在測(cè)繪運(yùn)籌學(xué)中應(yīng)用（第二版）[M].測(cè)繪出版社，2003.

[3]龔強(qiáng).測(cè)繪運(yùn)籌學(xué)導(dǎo)論[J].東北測(cè)繪，1998，21(3).

[4]龔強(qiáng).略論測(cè)繪運(yùn)籌學(xué)模型及建?；驹瓌t[J].黑龍江測(cè)繪，1997，20(1).