巧用Excel規劃求解最短路徑

● Excel規劃求解的功能概述

Excel具有規劃求解的基本功能，包括線性規劃和非線性規劃。對于常規的線性規劃問題，Excel就可以給出求解結果。借助規劃求解，可求得工作表上某個單元格中公式的最優值。規劃求解將對直接或間接與目標單元格中公式相關聯的一組單元格中的數值進行調整，最終在目標單元格公式中求得期望的結果。

● 加載規劃求解功能

在Excel2003版本中，通過點擊菜單“工具→宏→加載宏”，加載規劃求解加載項，便可加載該宏。在Excel2007版本中，通過點擊Office按鈕，點擊“Excel選項→加載項→轉到Excel加載項”，然后加載規劃求解加載項，便可以加載規劃求解的宏。在Excel2010版本中，通過點擊“文件”選項卡打開“Excel選項”對話框，單擊左側“加載項”標簽，在右側單擊“轉到”按鈕，打開“加載宏”對話框，勾選“規劃求解加載項”復選框，單擊“確定”按鈕，即可在工具欄的“數據”選項卡中出現“分析”選項組，菜單上面就有了“規劃求解”按鈕。

● 案例

王老師從學校A到學校I參加會議，途中需要經過一些學校，學校之間的距離和線路已在圖1中標明，請幫王老師規劃一下，在不影響去學校I最短距離的情況下，順便探訪其他學校，請將路線描述出來。

1.Dijkstra算法描述及C語言函數實現

為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。即如果存在一條從i到j的最短路徑（Vi...Vk，Vj），Vk是Vj前面的一個頂點，那么（Vi...Vk）也必定是從i到k的最短路徑。例如，對于源頂點V0，首先選擇其直接相鄰的頂點中長度最短的頂點Vi，那么通過已知可得從V0到Vj頂點的最短距離dist[j]=min{dist[j]，dist[i]+matrix[i][j]}。根據這種思路，假設存在G=，源頂點為V0，U={V0}，dist[i]記錄V0到i的最短距離，path[i]記錄從V0到i路徑上的i前面的一個頂點。那么可從V-U中選擇使dist[i]值最小的頂點i，將i加入到U中；更新與i直接相鄰頂點的dist值（dist[j]=min{dist[j]，dist[i]+matrix[i][j]}）；直到U=V，停止。

/*Dijkstra算法代碼C語言實現：*/

void DijkstraPath（MGraph g，int *dist，int *path，int v0） //v0表示源頂點

{

int i，j，k；

bool *visited=（bool *）malloc（sizeof（bool）*g.n）；

for（i=0；i

{

if（g.matrix[v0][i]>0&&i！=v0）

{

dist[i]=g.matrix[v0][i]；

path[i]=v0； //path記錄最短路徑上從v0到i的前一個頂點

}

else

{

dist[i]=INT_MAX； //若i不與v0直接相鄰，則權值置為無窮大

path[i]=-1；

}

visited[i]=false；

path[v0]=v0；

dist[v0]=0；

}

visited[v0]=true；

for（i=1；i

{

int min=INT_MAX；

int u；

for（j=0；j

{

if（visited[j]==false&&dist[j]

{

min=dist[j]；

u=j；

}

}

visited[u]=true；

for（k=0；k

{

if（visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]

{

dist[k]=min+g.matrix[u][k]；

path[k]=u；

}

}

}

}

2.Excel“規劃求解”功能實現最短路徑

（1）可將學校A到學校I的距離與邏輯關系通過以下表表示。

（2）新建工作簿，將上表各節點的邏輯關系用下Excel工作表表示（如圖2）。

“節點關系”這一欄僅用于描述各節點之間的關系，僅以B點來說（+代表此點出發，-代表以此點進），進入方向為A，出發為C、E、F。所以B=-AB+BC+BE+BF，以此類推。真正反映數量關系的是F欄的“數量（邏輯關系）”，同樣以B節點為例，F19中公式關系是=-D18+D21+D22+D23，通過D欄各線段是否在最短路徑（o表示“不在”，1表示“在”）上，迭代產生。最短路徑設置在G31，使用公式“=SUMPRODUCT（C18：C31，D18：D31）”，通過對D欄、F欄進行規劃求解來設置相應的約束條件以生成最短距離。

3.規劃求解

點擊“數據→規劃求解”，目標單元格G31為最短路徑，通過函數SUMPRODUCT（C18：C31，D18：D31）進行求和。因為選取的是最短路徑，所以在“最小值”選項打標記。從下頁圖3可看出規劃求解通過調整所指定的可更改的單元格（可變單元格）D18：D31中的值，可以從目標單元格公式中求得所需的結果。約束條件是在D18：D31中只能是0、1的兩種，結束條件是節點條件的取值與目標值對應。

由于規劃求解過程是一個迭代過程，有的值可能達到1E-9左右，約為0，將“是否為最短路徑”和“數量（邏輯關系）”設置成數值格式，并取消“小數位”。

從上例創建模型的過程中，我們看到可以對規劃求解模型中的可變單元格數值應用約束條件（約束條件：“規劃求解”中設置的限制條件），約束條件可以引用其他影響目標單元格公式的單元格的值。

Excel不僅是一個小型的數據庫軟件，更是一個操作極為方便的工作數據表，幾乎能勝任數據處理的各種要求，功能強大、使用靈活。讓我們共同使用好Excel，提高工作效率。

資訊

便攜辦公利器——華碩PU500商務筆記本

全能輕薄的商務本

華碩PU500作為主流15.6英寸商務本，重量為1.96Kg，厚度只有22mm，擁有深色發絲拉紋設計。屏幕采用防眩光霧面屏。電源適配器體積比傳統適配器小20%，加入電源插接報警，當適配器插頭未完全插入時系統會自動彈出窗口報警，保護電腦安全。

動力強勁的商務本

華碩PU500采用i5-3317U處理器，配備4GB DDR3 1600MHz內存，Intel? HD Graphics 4000顯示芯片。PU500采用“SSD+HDD”的混合硬盤模式（選配），既保持了SSD快速讀取的優勢，又具有傳統機械硬盤的超高性價比。

接口配備齊全包括兩個USB2.0接口、一個支持關機充電的USB3.0接口，同時還配備投影展示常用的VGA視頻輸出接口，HDMI等接口。

最為安全的商務本

華碩PU500以金屬支架強化硬盤周圍的結構保護硬盤安全，周圍輔以減震海綿墊防止筆記本電腦在運送過程中如果發生沖擊或掉落，可確保數據的安全。

同時，該機型還設置了專屬ASUS HDD Protection，可利用內建的重力傳感器（G-sensor），偵測出加速度的變化，當加速度達到一定程度時，觸發硬盤保護機制將硬盤讀寫磁頭與硬盤盤片分離，從而保護硬盤。

ASUS HDD Protection允許用戶自定義硬盤保護敏感級別，更加方便外出攜帶隨時調整機器安全防護等級。