巧用Excel規(guī)劃求解最短路徑
2013-12-29 00:00:00周忠林許大宏
中國(guó)信息技術(shù)教育 2013年11期
● Excel規(guī)劃求解的功能概述
Excel具有規(guī)劃求解的基本功能，包括線性規(guī)劃和非線性規(guī)劃。對(duì)于常規(guī)的線性規(guī)劃問(wèn)題，Excel就可以給出求解結(jié)果。借助規(guī)劃求解，可求得工作表上某個(gè)單元格中公式的最優(yōu)值。規(guī)劃求解將對(duì)直接或間接與目標(biāo)單元格中公式相關(guān)聯(lián)的一組單元格中的數(shù)值進(jìn)行調(diào)整，最終在目標(biāo)單元格公式中求得期望的結(jié)果。
● 加載規(guī)劃求解功能
在Excel2003版本中，通過(guò)點(diǎn)擊菜單“工具→宏→加載宏”，加載規(guī)劃求解加載項(xiàng)，便可加載該宏。在Excel2007版本中，通過(guò)點(diǎn)擊Office按鈕，點(diǎn)擊“Excel選項(xiàng)→加載項(xiàng)→轉(zhuǎn)到Excel加載項(xiàng)”，然后加載規(guī)劃求解加載項(xiàng)，便可以加載規(guī)劃求解的宏。在Excel2010版本中，通過(guò)點(diǎn)擊“文件”選項(xiàng)卡打開(kāi)“Excel選項(xiàng)”對(duì)話框，單擊左側(cè)“加載項(xiàng)”標(biāo)簽，在右側(cè)單擊“轉(zhuǎn)到”按鈕，打開(kāi)“加載宏”對(duì)話框，勾選“規(guī)劃求解加載項(xiàng)”復(fù)選框，單擊“確定”按鈕，即可在工具欄的“數(shù)據(jù)”選項(xiàng)卡中出現(xiàn)“分析”選項(xiàng)組，菜單上面就有了“規(guī)劃求解”按鈕。
● 案例
王老師從學(xué)校A到學(xué)校I參加會(huì)議，途中需要經(jīng)過(guò)一些學(xué)校，學(xué)校之間的距離和線路已在圖1中標(biāo)明，請(qǐng)幫王老師規(guī)劃一下，在不影響去學(xué)校I最短距離的情況下，順便探訪其他學(xué)校，請(qǐng)將路線描述出來(lái)。
1.Dijkstra算法描述及C語(yǔ)言函數(shù)實(shí)現(xiàn)
為了求出最短路徑，Dijkstra就提出了以最短路徑長(zhǎng)度遞增，逐次生成最短路徑的算法。即如果存在一條從i到j(luò)的最短路徑（Vi...Vk，Vj），Vk是Vj前面的一個(gè)頂點(diǎn)，那么（Vi...Vk）也必定是從i到k的最短路徑。例如，對(duì)于源頂點(diǎn)V0，首先選擇其直接相鄰的頂點(diǎn)中長(zhǎng)度最短的頂點(diǎn)Vi，那么通過(guò)已知可得從V0到Vj頂點(diǎn)的最短距離dist[j]=min{dist[j]，dist[i]+matrix[i][j]}。根據(jù)這種思路，假設(shè)存在G=
/*Dijkstra算法代碼C語(yǔ)言實(shí)現(xiàn)：*/
void DijkstraPath（MGraph g，int *dist，int *path，int v0） //v0表示源頂點(diǎn)
{
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的前一個(gè)頂點(diǎn) } else { dist[i]=INT_MAX； //若i不與v0直接相鄰，則權(quán)值置為無(wú)窮大 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“規(guī)劃求解”功能實(shí)現(xiàn)最短路徑 （1）可將學(xué)校A到學(xué)校I的距離與邏輯關(guān)系通過(guò)以下表表示。 （2）新建工作簿，將上表各節(jié)點(diǎn)的邏輯關(guān)系用下Excel工作表表示（如圖2）。 “節(jié)點(diǎn)關(guān)系”這一欄僅用于描述各節(jié)點(diǎn)之間的關(guān)系，僅以B點(diǎn)來(lái)說(shuō)（+代表此點(diǎn)出發(fā)，-代表以此點(diǎn)進(jìn)），進(jìn)入方向?yàn)锳，出發(fā)為C、E、F。所以B=-AB+BC+BE+BF，以此類推。真正反映數(shù)量關(guān)系的是F欄的“數(shù)量（邏輯關(guān)系）”，同樣以B節(jié)點(diǎn)為例，F(xiàn)19中公式關(guān)系是=-D18+D21+D22+D23，通過(guò)D欄各線段是否在最短路徑（o表示“不在”，1表示“在”）上，迭代產(chǎn)生。最短路徑設(shè)置在G31，使用公式“=SUMPRODUCT（C18：C31，D18：D31）”，通過(guò)對(duì)D欄、F欄進(jìn)行規(guī)劃求解來(lái)設(shè)置相應(yīng)的約束條件以生成最短距離。 3.規(guī)劃求解 點(diǎn)擊“數(shù)據(jù)→規(guī)劃求解”，目標(biāo)單元格G31為最短路徑，通過(guò)函數(shù)SUMPRODUCT（C18：C31，D18：D31）進(jìn)行求和。因?yàn)檫x取的是最短路徑，所以在“最小值”選項(xiàng)打標(biāo)記。從下頁(yè)圖3可看出規(guī)劃求解通過(guò)調(diào)整所指定的可更改的單元格（可變單元格）D18：D31中的值，可以從目標(biāo)單元格公式中求得所需的結(jié)果。約束條件是在D18：D31中只能是0、1的兩種，結(jié)束條件是節(jié)點(diǎn)條件的取值與目標(biāo)值對(duì)應(yīng)。 由于規(guī)劃求解過(guò)程是一個(gè)迭代過(guò)程，有的值可能達(dá)到1E-9左右，約為0，將“是否為最短路徑”和“數(shù)量（邏輯關(guān)系）”設(shè)置成數(shù)值格式，并取消“小數(shù)位”。 從上例創(chuàng)建模型的過(guò)程中，我們看到可以對(duì)規(guī)劃求解模型中的可變單元格數(shù)值應(yīng)用約束條件（約束條件：“規(guī)劃求解”中設(shè)置的限制條件），約束條件可以引用其他影響目標(biāo)單元格公式的單元格的值。 Excel不僅是一個(gè)小型的數(shù)據(jù)庫(kù)軟件，更是一個(gè)操作極為方便的工作數(shù)據(jù)表，幾乎能勝任數(shù)據(jù)處理的各種要求，功能強(qiáng)大、使用靈活。讓我們共同使用好Excel，提高工作效率。 資訊 便攜辦公利器——華碩PU500商務(wù)筆記本 全能輕薄的商務(wù)本 華碩PU500作為主流15.6英寸商務(wù)本，重量為1.96Kg，厚度只有22mm，擁有深色發(fā)絲拉紋設(shè)計(jì)。屏幕采用防眩光霧面屏。電源適配器體積比傳統(tǒng)適配器小20%，加入電源插接報(bào)警，當(dāng)適配器插頭未完全插入時(shí)系統(tǒng)會(huì)自動(dòng)彈出窗口報(bào)警，保護(hù)電腦安全。 動(dòng)力強(qiáng)勁的商務(wù)本 華碩PU500采用i5-3317U處理器，配備4GB DDR3 1600MHz內(nèi)存，Intel? HD Graphics 4000顯示芯片。PU500采用“SSD+HDD”的混合硬盤模式（選配），既保持了SSD快速讀取的優(yōu)勢(shì)，又具有傳統(tǒng)機(jī)械硬盤的超高性價(jià)比。 接口配備齊全包括兩個(gè)USB2.0接口、一個(gè)支持關(guān)機(jī)充電的USB3.0接口，同時(shí)還配備投影展示常用的VGA視頻輸出接口，HDMI等接口。 最為安全的商務(wù)本 華碩PU500以金屬支架強(qiáng)化硬盤周圍的結(jié)構(gòu)保護(hù)硬盤安全，周圍輔以減震海綿墊防止筆記本電腦在運(yùn)送過(guò)程中如果發(fā)生沖擊或掉落，可確保數(shù)據(jù)的安全。 同時(shí)，該機(jī)型還設(shè)置了專屬ASUS HDD Protection，可利用內(nèi)建的重力傳感器（G-sensor），偵測(cè)出加速度的變化，當(dāng)加速度達(dá)到一定程度時(shí)，觸發(fā)硬盤保護(hù)機(jī)制將硬盤讀寫磁頭與硬盤盤片分離，從而保護(hù)硬盤。 ASUS HDD Protection允許用戶自定義硬盤保護(hù)敏感級(jí)別，更加方便外出攜帶隨時(shí)調(diào)整機(jī)器安全防護(hù)等級(jí)。
