數學規劃在測繪工作中的應用

于祖國YU Zu-guo

（昆明理工大學國土資源學院，昆明 650000）

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

0 引言

測繪是國民經濟建設和發展的重要基礎性前期工作。隨著經濟的發展，現代測繪的生產規模日益擴大，分工越來越細，要求測繪生產組織必須具有高度計劃性。將數學規劃的方法運用于測繪工作中，對測繪工作實施過程中各種錯綜復雜的數量關系進行研究，并歸結成一定的數學模型，用數學方法找到最合理的工作方案，在保證工程要求和精度要求的前提下，可以達到提高工作效率，減少生產消耗的人力、物力、財力的目的。

1 線性規劃的應用

在測繪經營管理中，經常要解決兩類問題：一類是對于某項確定的生產任務，如何使用最少的資源，保質保量的完成測繪任務；另一類是對于有限的資源，如何安排使其最大限度的發揮作用，取得更多的測繪成果。對于這些問題，都可以應用線性規劃的方法，通過建立數字模型、求解、應用，科學合理地解決。這里以一例說明線性規劃問題在測繪工作中的應用。

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

在本問題中，根據已有條件可以設：下月進行建筑物放線x1件，1:500竣工測量x2件，根據線性規劃的理論，可以建立模型。

則希望獲得的最大產值的目標函數為：

約束條件為：

在上述數學模型中加入松弛變量，得到以下標準形式：Max z'=720x1+1600x2

用單純形法求出上述問題的最優解，得到最終表為：

表1

通過單純形表可以求出此線性規劃問題的最優解，即建筑物放線15件，1:500竣工測量35幅。

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

2 人工變量法

在實際測繪工作中，并不是所有的時候都如上述問題一樣，約束條件都是“≤”式，而有可能出現“≥”式或“=”式，這是很有可能的。當約束條件是“≥”式或“=”式時，將建立的線性規劃模型的一般形式化為標準形式后，約束條件系數矩陣中就不包含有單位矩陣。這種情況下我們需要使用人工變量法，通過加入人工變量的方式，人為的構造一個單位矩陣來求解問題。這里我們通過大M法求解。

依然沿用線性規劃中的例子，如果根據實際工作情況，要求內業工天不小于為220工天，檢查工天恰好為90工天，此時應如何安排工作使收益最大。

此問題的數學模型就變成

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

這里M是一個任意大的正數。

通過單純形法可以求出此線性規劃問題的最優解，即建筑物放線30件，1:500竣工測量30幅。

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

3 靈敏度分析

當線性規劃的系數aij、bi、cj發生變化時，最優解也可能會隨之發生變化。雖然通過重新使用線性規劃的單純形法能夠求解，但是這樣既麻煩又沒有必要。通過靈敏度分析的方法則可以比較方便的求出這些參數的變化對最優解的影響。

3.1 技術系數aij的變化 在實際的測繪工作中，由于生產規范、人員變動、技術發展乃至天氣變化等等因素，都可能導致技術系數aij發生變化。依然沿用上例，但是由于測量工作要求，生產時間發生變化，現在放線需要外業2工天，內業2工天，檢查1工天。此時就是技術系數aij發生了變化。應如何安排工作。

代入表1，并通過單純形法計算，可得x1=30，x2=30。說明當技術系數發生變化時，最優解也隨之發生變化。

3.2 資源系數bi變化 在實際測繪工作中，在根據問題建立數學模型時，若將生產能力、儀器、設備等等視作資源，那么當這些資源發生變化，例如新購置一批儀器、增加了新的工作人員等等時，資源系數會發生變化。仍以上例為例，假設由于該測繪單位生產能力增加。現總的外業工天增加40工天，內業工天增加40工天，檢查工天增加20工天。此時顯然資源系數bi發生了變化。那么應如何安排工作。

②計算Δb'和b'+Δb'

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

3.3 價值系數cj變化 由于市場條件是在不斷變化的，因此在實際工作當中，價值系數cj也是會不斷發生變化的，這會對原來的決策變量發生影響。

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

根據要求，設增加線路工程測量的計劃產量為x6，則它的價值系數c6=1200，對應的技術向量P6=(532)T

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

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

顯然，此收益是大于之前只安排兩項工作時的收益。因此，應該安排線路測量工作。

4 整數規劃

在前面的線性規劃，目標規劃中，求出的最優解都有可能包含小數或分數。而在實際測繪生產工作中，由于人員、儀器設備、控制點個數甚至工時工天都只能是整數而不能使小數或分數。此時如果簡單的將求得的最優解進行四舍五入取整，得到的結果可能不符合約束條件，或者即使滿足約束條件，卻不是最優解。此時，需要通過整數規劃的方法進行最優解的求解。

仍以上文中的例子為例，假設由于該測繪單位擴大生產能力，內業工作時間增加了10工天，總共有230工天。

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

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

將要求解的整數規劃問題稱為問題A，其對應的線性規劃問題稱為整數B。

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

得到最優解如表2所示。

繼續對問題B1和B2進行分解，因為z1＞z2，故先分解

表2

B1為兩支。分別增加條件x2≤32和x2≥33，得到問題B3和問題B4，進行第二次迭代，得到最優解如表3所示。

表3

可見，問題B3和問題B4的解都已經是整數解。

而問題B2的目標函數值z2=68080，所以可能在67920≤z*≤68080之間有整數解，因此繼續對問題B2進行分解。得到問題B5和B6。（表4）

由于問題B5的目標函數值大于所有的整數解，繼續對問題B5進行分解。（表5）

此時可以判斷問題B4的解x1=21，x2=33為最優整數解。此時最大收益max Z=z*=67920（元）。

本文以一個實例為基礎，分析了線性規劃、靈敏度分析、整數規劃等數學規劃方法在測繪工作中的應用，討論了如何應用數學規劃的方法，對測繪生產工作進行組織安排，以提高生產效率。除此以外，數學規劃在測繪工作中還可以有其他更多的應用，由于篇幅有限，本文不一一討論了。

表4

表5

[1]甘應愛等.運籌學（第三版）[M].清華大學出版社，2005（6）.

[2]鄭肇葆等.數學規劃在測繪運籌學中應用（第二版）[M].測繪出版社，2003.

[3]龔強.測繪運籌學導論[J].東北測繪，1998，21(3).

[4]龔強.略論測繪運籌學模型及建模基本原則[J].黑龍江測繪，1997，20(1).