劉冬華，鄧俊謙，郭瓊瓊

(鄭州鐵路職業(yè)技術(shù)學(xué)院，河南 鄭州 450052)

1 問題的提出與分析

某區(qū)政府在圖1所示的區(qū)域修建一條從A到B的直線型公路，由于涉及到路面拆遷等因素，各地段建設(shè)費用有所不同，圖1中的數(shù)字代表區(qū)域公路單位建設(shè)費用(單位:百萬元).未標(biāo)明數(shù)字的任何地方單位建設(shè)費用均為1;每個網(wǎng)格邊界上的費用按該地區(qū)最小單位費用計算.圖1中每個網(wǎng)格長與寬都為1個單位.要解決的問題是:按建設(shè)部門的如下具體要求，從建設(shè)費用最省的角度，給出最優(yōu)方案:

圖1 區(qū)域內(nèi)公路單位建設(shè)費用

(1)公路至多只能有1個轉(zhuǎn)彎點，且轉(zhuǎn)彎點只能建在圖1中所示的網(wǎng)格點上.

(2)公路至多可以有2個轉(zhuǎn)彎點，且轉(zhuǎn)彎點只能建在圖1中所示的網(wǎng)格點上.

從圖1可以看出，線段AB左下側(cè)中各小區(qū)域的單位建設(shè)費用均大于右上側(cè)中對稱小區(qū)域的單位建設(shè)費用，所以，要使從A到B的直線型公路的建設(shè)費用最省，轉(zhuǎn)彎點應(yīng)該選AB的右上側(cè)區(qū)域.

對于所要解決的問題1和問題2，由于要求轉(zhuǎn)彎點只能建在網(wǎng)格點上，因此，求解的思路是:首先，設(shè)出轉(zhuǎn)彎點的坐標(biāo)并表示出各公路段的直線方程，然后求出網(wǎng)格線與各公路段的交點坐標(biāo)，并表示出從A到B的總建設(shè)費用，其次，利用Matlab編程，分別計算出轉(zhuǎn)彎點取遍各網(wǎng)格點時的總建設(shè)費用，從中篩選出使總建設(shè)費用最小的轉(zhuǎn)彎點.

為了建立建設(shè)費用的最優(yōu)化模型，根據(jù)問題所給的條件及實際公路建設(shè)的一般原則作出如下假設(shè):

(1)圖1中各小區(qū)域的單位建設(shè)費用是真實可靠的;

(2)每個區(qū)域的建設(shè)費用只與該區(qū)域的公路長度和單位建設(shè)費用有關(guān)，不考慮意外損壞等其他相關(guān)費用;

(3)對于有兩個轉(zhuǎn)彎點的公路，建設(shè)的直線型公路段為:A→左轉(zhuǎn)彎點→右轉(zhuǎn)彎點→B.

2 問題1的模型建立與求解

問題1要求至多有一個轉(zhuǎn)彎點，所以可以分沒有轉(zhuǎn)彎點和恰好有一個轉(zhuǎn)彎點兩種情況來計算總建設(shè)費用.顯然，沒有轉(zhuǎn)彎點時，公路AB的建設(shè)費用為

下面來討論恰好有一個轉(zhuǎn)彎點時的建設(shè)費用.

觀察圖1所示各網(wǎng)格區(qū)域的單位建設(shè)費，可以看出:線段AB左下側(cè)中各小區(qū)域的單位建設(shè)費用均大于右上側(cè)中對稱小區(qū)域的單位建設(shè)費用，且所有區(qū)域上的數(shù)值關(guān)于y=x對稱.因此，設(shè)直線型公路的唯一轉(zhuǎn)彎點P在AB右上側(cè)的網(wǎng)格點上，坐標(biāo)為(m，n)，公路PA→PB的總建設(shè)費用為Z，并且用反證法易證下面的引理.

引理 若P(m，n)是使總建設(shè)費用最省的轉(zhuǎn)彎點，則P關(guān)于y=x的對稱點P'(n，m)也一定是使總建設(shè)費用最省的轉(zhuǎn)彎點.

根據(jù)引理，我們只需求出其中一個，即可利用對稱性得到第二個.

將公路段PA、PB與各網(wǎng)格線的交點按橫坐標(biāo)由小到大排序，坐標(biāo)依次記為(xi，yi)(i=1，…，N，其中N為交點的個數(shù)).這些交點將公路分成N－1個小公路段，第i個小公路段的左端點記為(xi，yi)，長度記為li(i=1，…，N－1)，其所對應(yīng)的網(wǎng)格區(qū)域用右上角網(wǎng)格點的坐標(biāo)標(biāo)記，記為(gxi，gyi)(i=1，…，N －1).并且

記圖1中各小區(qū)域的單位建設(shè)費用為cij(i=1，…，9，j=1，…，9，分別為相應(yīng)區(qū)域右上角網(wǎng)格點的坐標(biāo)).下面分四種情形，表示公路的總建設(shè)費用.

情形1 轉(zhuǎn)彎點P在網(wǎng)格點C

此時，總建設(shè)費用為Z=18.顯然，該建設(shè)費用大于沒有轉(zhuǎn)彎點時的建設(shè)費用，因此，舍去這種情形.

情形2 轉(zhuǎn)彎點在線段AC上的網(wǎng)格點且不同于點C

其中cgxi，gyi為公路段PB被圖1中網(wǎng)格線所分成的第i個小公路段所在網(wǎng)格區(qū)域的單位建設(shè)費用;li、gxi、gyi的意義與式(1)相同.

情形3 轉(zhuǎn)彎點P在線段BC上的網(wǎng)格點且不同于點C

其中cgxi，gyi為公路段PA被圖1中網(wǎng)格線所分成的第i個小公路段所在網(wǎng)格區(qū)域的單位建設(shè)費用;li、gxi、gyi的意義與式(1)相同.

情形4 P既不在線段AC又不在BC上的網(wǎng)格點

其中cgxi，gyi為公路段PA和PB被圖1中網(wǎng)格線所分成的第i個小公路段所在網(wǎng)格區(qū)域的單位建設(shè)費用;li、gxi、gyi的意義與式(1)相同.

以直達(dá)公路AB的建設(shè)費用14.9907百萬元為總建設(shè)費用的初始值，根據(jù)式(1)～(4)，利用MATLAB編程計算轉(zhuǎn)彎點在不同網(wǎng)格點上時，公路的總建設(shè)費用，并比較它們的大小，求出最小建設(shè)費用，此時所對應(yīng)的轉(zhuǎn)彎點即為最優(yōu)設(shè)計方案的轉(zhuǎn)彎點.運行所編程序，得轉(zhuǎn)彎點為P(6，5)時最小總建設(shè)費用Z=14.7068.結(jié)合引理1可知:使得總建設(shè)費用最少的轉(zhuǎn)彎點為點(6，5)或點(5，6)，最小總建設(shè)費用為14.7068百萬元.建設(shè)費用最省的公路設(shè)計方案如圖2所示.

圖2 問題1的最優(yōu)設(shè)計方案

3 問題2的模型建立與求解

問題2要求至多有兩個轉(zhuǎn)彎點，即分為兩種情形:至多有一個轉(zhuǎn)彎點(即問題1的情形)和恰好有兩個轉(zhuǎn)彎點.因此，我們只需再研究:恰有兩個轉(zhuǎn)彎點時的最優(yōu)設(shè)計方案，并將其最小建設(shè)費用與問題1的最小總建設(shè)費用比較，兩者中最小值即為問題2的最小建設(shè)費用，所對應(yīng)的設(shè)計方案即為問題2的最優(yōu)設(shè)計方案.

根據(jù)假設(shè)(3)，設(shè)左轉(zhuǎn)彎點為P1(m，n)，右轉(zhuǎn)彎點為 P2(s，q)，其中 m ＜s，且 P1、P2均在 AB 右上側(cè)的網(wǎng)格點上.與問題1的方法類似，下面分情形來討論恰有兩個轉(zhuǎn)彎點時的總建設(shè)費用.

情形1 P1在AC上、P2在BC上

此時，P1A的建設(shè)費用為m，P2B的建設(shè)費用為q.P1P2的直線方程為，用與前面相似的方法，可得 P1P2得的建設(shè)費用為

cgxi，gyi·li.于是，公路的總建設(shè)費用為

其中 li、gxi、gyi的意義與式(1)相同.

情形2 P1在AC上、P2不在BC上

此時，P1A的建設(shè)費用為m，P1P2的方程為y=，P2B的方程為.相似的方法可以求出公路段P1P2和P2B的建設(shè)費用.于是，可得公路的總建設(shè)費用為

其中 li、gxi、gyi的意義與式(1)相同.

情形3 P1不在AC上、P2在BC上

這種情形下，P2B的建設(shè)費用為q，P1A的方程為.用與前面相同的方法可求出公路段P1A的建設(shè)費用為

其中 li、gxi、gyi的意義與式(1)相同.

公路段P1P2的建設(shè)費用，要分兩種情況來求.當(dāng)n≠q時，P1P2的方程為，用與前面相同的方法可求出公路段P1P2的建設(shè)費用.當(dāng)n=q時，P1P2在網(wǎng)格線上，單位建設(shè)費用應(yīng)取該地區(qū)最小單位費用，根據(jù)題意和圖1中的數(shù)據(jù)特點，這時，應(yīng)取 gxi=［xi］+1，gyi=［yi］+1.于是，公路段P1P2的建設(shè)費用為其中當(dāng)n≠q時，gxi，gyi的表達(dá)式與式(1)相同;當(dāng)n=q時，gxi=［xi］+1，gyi=［yi］+1.

綜上所述，在情形3下，公路的總建設(shè)費用為

情形4 P1不在AC上、P2也不在BC上

這種情形下，P1A的方程為，用與前面相同的方法可得P1A的建設(shè)費用Z1與式(7)相同.P2B的方程為，類似的方法可得P2B的建設(shè)費用為P1P2的方程為的建設(shè)費用需分三種情形來求.

(1)當(dāng)n＞q時，用與前面相同的方法可得P1P2的建設(shè)費用為其中 li、gxi、gyi的意義與式(1)相同.

(2)當(dāng)n=q時，用與情形3相似的方法，可得P1P2的建設(shè)費用為

其中 gxi=［xi］+1，gyi=［yi］+1.

(3)當(dāng)n＜q時，線段P1P2是上升的，此時，應(yīng)取gxi=［xi+1］，gyi=［yi+1］.于是，公路段 P1P2的建設(shè)費用為

其中 gxi=［xi+1］，gyi=［yi+1］.

綜上所述，在情形4下，公路的總建設(shè)費用為

根據(jù)式(5)～(14)，利用MATLAB編程計算:兩轉(zhuǎn)彎點在不同網(wǎng)格點上時，公路的總建設(shè)費用，并比較它們的大小，求出最小建設(shè)費用及所對應(yīng)的轉(zhuǎn)彎點.運行所編程序，得兩轉(zhuǎn)彎點分別為(7，4)和(4，7)，最小建設(shè)費用為14.6241.顯然，這個建設(shè)費用小于問題1中所求的最小建設(shè)費用，因此，對于問題2，建設(shè)費用最省時的轉(zhuǎn)彎點分別為(7，4)和(4，7)(公路的最優(yōu)設(shè)計方案如圖3所示)，此時的最小建設(shè)費用為14.6241.

圖3 問題2的最優(yōu)設(shè)計方案

4 模型的評價與改進方向

本文建立了轉(zhuǎn)彎點均在網(wǎng)格點上，并且至多有一個轉(zhuǎn)彎點或至多有兩個轉(zhuǎn)彎點情形下，使得城區(qū)公路的建設(shè)費用最省的最優(yōu)設(shè)計模型，并利用廣度搜索方法和Matlab軟件編程，求出了兩種情形下的最優(yōu)設(shè)計方案，對于實際的生產(chǎn)建設(shè)具有較好的指導(dǎo)意義.

在實際生產(chǎn)建設(shè)中，轉(zhuǎn)彎點還可以在網(wǎng)格線或區(qū)域的任何位置上.因此，我們還可以繼續(xù)研究下列情形下的最優(yōu)設(shè)計方案:

(1)公路至多只能有2個轉(zhuǎn)彎點，且轉(zhuǎn)彎點只能建在圖1中所示的網(wǎng)格線上.

(2)公路至多只能有2個轉(zhuǎn)彎點，且轉(zhuǎn)彎點只能建在圖1中所示區(qū)域的任何位置上.

［1］韓中庚.數(shù)學(xué)建模實用教程［M］.北京:高等教育出版社，2012.

［2］費浦生.數(shù)學(xué)建模及其基礎(chǔ)知識詳解［M］.武漢:武漢大學(xué)出版社，2006.