淺析圖論在某地區(qū)電網(wǎng)規(guī)劃中利用及MATLAB程序最優(yōu)分析

高怡

摘要：“圖”是指某類具體事物和這些事物之間的聯(lián)系，圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解，本文利用圖論的分析方法，對于某電網(wǎng)規(guī)劃問題進行最近點與最優(yōu)點進行分析并利用MATLAB程序?qū)D進行驗證，有助于某電網(wǎng)的規(guī)劃應(yīng)用，且為某電網(wǎng)提供了一種分析理論基礎(chǔ)。

關(guān)鍵詞：圖 圖論 電網(wǎng)規(guī)劃 最優(yōu)分析

中圖分類號：O157.5 文獻標(biāo)識碼：A 文章編號：1007-9416（2014）08-0212-01

圖與網(wǎng)絡(luò)是運籌學(xué)（Operations Research）中的一個經(jīng)典和重要的分支，而其中的最短路問題、最大流問題、最小費用流問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題。而電網(wǎng)規(guī)劃中在必須確定考慮何時、何地投建何種類型的輸電線路進，考慮其各項技術(shù)指標(biāo)費用最小的前提下才能對電力系統(tǒng)進行建設(shè)，而本文將利用圖與網(wǎng)絡(luò)的特點來解決系統(tǒng)中的問題，比用線性規(guī)劃等其他模型來求解往往要簡單、有效得多。

1 某地區(qū)電網(wǎng)的現(xiàn)狀

某地區(qū)高壓配電網(wǎng)以兩座330kV變電站為中心向全地區(qū)環(huán)狀或雙回線供電。供電可靠性高，運行靈活。網(wǎng)內(nèi)運行110kV公網(wǎng)變電站13座。其中330kV通過雙回線連接兩個變電站，而110kV主網(wǎng)架，通過8座110kV變電站受330kV變電站直接相連。

2 某部分電網(wǎng)的網(wǎng)絡(luò)分析

利用點與線之間的關(guān)系，把某部分電網(wǎng)利用幾個頂點（vertex）或節(jié)點（node）用弧線連接起來一個非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。如圖1所示。

3 某部分電網(wǎng)的有向圖規(guī)劃

利用圖論之間的關(guān)系，結(jié)合受電側(cè)與送電側(cè)之間，把某電網(wǎng)規(guī)劃成二維有向圖，即由一個非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點集或節(jié)點集，中的每一個元素稱為該圖的一個頂點或節(jié)點；稱為圖的弧集（arc set），中的每一個元素（即中某兩個元素的有序?qū)Γ┯洖榛?，被稱為該圖的一條從到的弧（arc）。

在利用圖論在MALAB編程應(yīng)用就可以分析出電網(wǎng)的最小路徑走向，這樣一來即可以節(jié)約資金也可也可以減小電纜的走向，使電網(wǎng)回路雙線數(shù)達到最小。而本篇幅將利用某部分電網(wǎng)的走向路徑重新利用程序從而獲得最佳電網(wǎng)的規(guī)劃路徑，使其利用率達到最大流。

4 利用MATLAB程序?qū)ι鲜鲭娋W(wǎng)進行分析

建立數(shù)學(xué)模型對電網(wǎng)進行有向圖的規(guī)劃，在利用Ford和Fulkerson在1957年提出的標(biāo)號法對最大流進行分析與計算。標(biāo)號法是為了尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止分為以下兩個過程：A.標(biāo)號過程：通過標(biāo)號過程尋找一條可增廣軌。B.增流過程：沿著可增廣軌增加網(wǎng)絡(luò)的流量。

其兩個分析方法將可以分為以下具體步驟：

（A）標(biāo)號過程：

（i）給發(fā)點標(biāo)號為。

（ii）若頂點已經(jīng)標(biāo)號，則對的所有未標(biāo)號的鄰接頂點按以下規(guī)則標(biāo)號：

①若，且時，令，

則給頂點標(biāo)號為，若，則不給頂點標(biāo)號。

②，且，令，則給標(biāo)號為，若，則不給標(biāo)號。

（iii）不斷地重復(fù)步驟（ii）直到收點被標(biāo)號，或不再有頂點可以標(biāo)號為止。當(dāng)被標(biāo)號時，表明存在一條從到的可增廣軌，則轉(zhuǎn)向增流過程（B）。如若點不能被標(biāo)號，且不存在其它可以標(biāo)號的頂點時，表明不存在從到的可增廣軌，算法結(jié)束，此時所獲得的流就是最大流。

（B）增流過程。

（i）令。

（ii）若的標(biāo)號為），則；若的標(biāo)號為，則。

（iii）若，把全部標(biāo)號去掉，并回到標(biāo)號過程（A）。否則，令，并回到增流過程（ii）。

求網(wǎng)絡(luò)中的最大流的算法的程序設(shè)計具體步驟如下：

對每個節(jié)點，其標(biāo)號包括兩部分信息

該節(jié)點在可能的增廣路中的前一個節(jié)點，以及沿該可能的增廣路到該節(jié)點為止可以增廣的最大流量。

在回歸到最大問題的解決過程中，根據(jù)電網(wǎng)規(guī)劃過程中的最大流定理，則可以總體上回歸到一個線性歸劃問題中。

5 結(jié)語

本文通過利用一種數(shù)學(xué)方法，對電力系統(tǒng)網(wǎng)絡(luò)通過建模，在利用MATLAB輔助程序?qū)λ?guī)劃的圖，進行有向圖的分析，使得達到最大流，由于電網(wǎng)是多元多匯網(wǎng)絡(luò)，為了建模與計算方便，本文將把多元多匯網(wǎng)絡(luò)化成多個單元單匯網(wǎng)絡(luò)進行求解，從而把非線性的問題總結(jié)并規(guī)劃到線性問題上進行求解，解決了最大流問題的解決文案。endprint

摘要：“圖”是指某類具體事物和這些事物之間的聯(lián)系，圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解，本文利用圖論的分析方法，對于某電網(wǎng)規(guī)劃問題進行最近點與最優(yōu)點進行分析并利用MATLAB程序?qū)D進行驗證，有助于某電網(wǎng)的規(guī)劃應(yīng)用，且為某電網(wǎng)提供了一種分析理論基礎(chǔ)。

關(guān)鍵詞：圖 圖論 電網(wǎng)規(guī)劃 最優(yōu)分析

中圖分類號：O157.5 文獻標(biāo)識碼：A 文章編號：1007-9416（2014）08-0212-01

圖與網(wǎng)絡(luò)是運籌學(xué)（Operations Research）中的一個經(jīng)典和重要的分支，而其中的最短路問題、最大流問題、最小費用流問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題。而電網(wǎng)規(guī)劃中在必須確定考慮何時、何地投建何種類型的輸電線路進，考慮其各項技術(shù)指標(biāo)費用最小的前提下才能對電力系統(tǒng)進行建設(shè)，而本文將利用圖與網(wǎng)絡(luò)的特點來解決系統(tǒng)中的問題，比用線性規(guī)劃等其他模型來求解往往要簡單、有效得多。

1 某地區(qū)電網(wǎng)的現(xiàn)狀

某地區(qū)高壓配電網(wǎng)以兩座330kV變電站為中心向全地區(qū)環(huán)狀或雙回線供電。供電可靠性高，運行靈活。網(wǎng)內(nèi)運行110kV公網(wǎng)變電站13座。其中330kV通過雙回線連接兩個變電站，而110kV主網(wǎng)架，通過8座110kV變電站受330kV變電站直接相連。

2 某部分電網(wǎng)的網(wǎng)絡(luò)分析

利用點與線之間的關(guān)系，把某部分電網(wǎng)利用幾個頂點（vertex）或節(jié)點（node）用弧線連接起來一個非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。如圖1所示。

3 某部分電網(wǎng)的有向圖規(guī)劃

利用圖論之間的關(guān)系，結(jié)合受電側(cè)與送電側(cè)之間，把某電網(wǎng)規(guī)劃成二維有向圖，即由一個非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點集或節(jié)點集，中的每一個元素稱為該圖的一個頂點或節(jié)點；稱為圖的弧集（arc set），中的每一個元素（即中某兩個元素的有序?qū)Γ┯洖榛颍环Q為該圖的一條從到的?。╝rc）。

在利用圖論在MALAB編程應(yīng)用就可以分析出電網(wǎng)的最小路徑走向，這樣一來即可以節(jié)約資金也可也可以減小電纜的走向，使電網(wǎng)回路雙線數(shù)達到最小。而本篇幅將利用某部分電網(wǎng)的走向路徑重新利用程序從而獲得最佳電網(wǎng)的規(guī)劃路徑，使其利用率達到最大流。

4 利用MATLAB程序?qū)ι鲜鲭娋W(wǎng)進行分析

建立數(shù)學(xué)模型對電網(wǎng)進行有向圖的規(guī)劃，在利用Ford和Fulkerson在1957年提出的標(biāo)號法對最大流進行分析與計算。標(biāo)號法是為了尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止分為以下兩個過程：A.標(biāo)號過程：通過標(biāo)號過程尋找一條可增廣軌。B.增流過程：沿著可增廣軌增加網(wǎng)絡(luò)的流量。

其兩個分析方法將可以分為以下具體步驟：

（A）標(biāo)號過程：

（i）給發(fā)點標(biāo)號為。

（ii）若頂點已經(jīng)標(biāo)號，則對的所有未標(biāo)號的鄰接頂點按以下規(guī)則標(biāo)號：

①若，且時，令，

則給頂點標(biāo)號為，若，則不給頂點標(biāo)號。

②，且，令，則給標(biāo)號為，若，則不給標(biāo)號。

（iii）不斷地重復(fù)步驟（ii）直到收點被標(biāo)號，或不再有頂點可以標(biāo)號為止。當(dāng)被標(biāo)號時，表明存在一條從到的可增廣軌，則轉(zhuǎn)向增流過程（B）。如若點不能被標(biāo)號，且不存在其它可以標(biāo)號的頂點時，表明不存在從到的可增廣軌，算法結(jié)束，此時所獲得的流就是最大流。

（B）增流過程。

（i）令。

（ii）若的標(biāo)號為），則；若的標(biāo)號為，則。

（iii）若，把全部標(biāo)號去掉，并回到標(biāo)號過程（A）。否則，令，并回到增流過程（ii）。

求網(wǎng)絡(luò)中的最大流的算法的程序設(shè)計具體步驟如下：

對每個節(jié)點，其標(biāo)號包括兩部分信息

該節(jié)點在可能的增廣路中的前一個節(jié)點，以及沿該可能的增廣路到該節(jié)點為止可以增廣的最大流量。

在回歸到最大問題的解決過程中，根據(jù)電網(wǎng)規(guī)劃過程中的最大流定理，則可以總體上回歸到一個線性歸劃問題中。

5 結(jié)語

本文通過利用一種數(shù)學(xué)方法，對電力系統(tǒng)網(wǎng)絡(luò)通過建模，在利用MATLAB輔助程序?qū)λ?guī)劃的圖，進行有向圖的分析，使得達到最大流，由于電網(wǎng)是多元多匯網(wǎng)絡(luò)，為了建模與計算方便，本文將把多元多匯網(wǎng)絡(luò)化成多個單元單匯網(wǎng)絡(luò)進行求解，從而把非線性的問題總結(jié)并規(guī)劃到線性問題上進行求解，解決了最大流問題的解決文案。endprint

摘要：“圖”是指某類具體事物和這些事物之間的聯(lián)系，圖論為任何一個包含了一種二元關(guān)系的離散系統(tǒng)提供了一個數(shù)學(xué)模型，借助于圖論的概念、理論和方法，可以對該模型求解，本文利用圖論的分析方法，對于某電網(wǎng)規(guī)劃問題進行最近點與最優(yōu)點進行分析并利用MATLAB程序?qū)D進行驗證，有助于某電網(wǎng)的規(guī)劃應(yīng)用，且為某電網(wǎng)提供了一種分析理論基礎(chǔ)。

關(guān)鍵詞：圖 圖論 電網(wǎng)規(guī)劃 最優(yōu)分析

中圖分類號：O157.5 文獻標(biāo)識碼：A 文章編號：1007-9416（2014）08-0212-01

圖與網(wǎng)絡(luò)是運籌學(xué)（Operations Research）中的一個經(jīng)典和重要的分支，而其中的最短路問題、最大流問題、最小費用流問題和匹配問題等都是圖與網(wǎng)絡(luò)的基本問題。而電網(wǎng)規(guī)劃中在必須確定考慮何時、何地投建何種類型的輸電線路進，考慮其各項技術(shù)指標(biāo)費用最小的前提下才能對電力系統(tǒng)進行建設(shè)，而本文將利用圖與網(wǎng)絡(luò)的特點來解決系統(tǒng)中的問題，比用線性規(guī)劃等其他模型來求解往往要簡單、有效得多。

1 某地區(qū)電網(wǎng)的現(xiàn)狀

某地區(qū)高壓配電網(wǎng)以兩座330kV變電站為中心向全地區(qū)環(huán)狀或雙回線供電。供電可靠性高，運行靈活。網(wǎng)內(nèi)運行110kV公網(wǎng)變電站13座。其中330kV通過雙回線連接兩個變電站，而110kV主網(wǎng)架，通過8座110kV變電站受330kV變電站直接相連。

2 某部分電網(wǎng)的網(wǎng)絡(luò)分析

利用點與線之間的關(guān)系，把某部分電網(wǎng)利用幾個頂點（vertex）或節(jié)點（node）用弧線連接起來一個非空有限集合和中某些元素的無序?qū)蠘?gòu)成的二元組，記為。如圖1所示。

3 某部分電網(wǎng)的有向圖規(guī)劃

利用圖論之間的關(guān)系，結(jié)合受電側(cè)與送電側(cè)之間，把某電網(wǎng)規(guī)劃成二維有向圖，即由一個非空有限集合和中某些元素的有序?qū)蠘?gòu)成的二元組，記為。其中稱為圖的頂點集或節(jié)點集，中的每一個元素稱為該圖的一個頂點或節(jié)點；稱為圖的弧集（arc set），中的每一個元素（即中某兩個元素的有序?qū)Γ┯洖榛?，被稱為該圖的一條從到的弧（arc）。

在利用圖論在MALAB編程應(yīng)用就可以分析出電網(wǎng)的最小路徑走向，這樣一來即可以節(jié)約資金也可也可以減小電纜的走向，使電網(wǎng)回路雙線數(shù)達到最小。而本篇幅將利用某部分電網(wǎng)的走向路徑重新利用程序從而獲得最佳電網(wǎng)的規(guī)劃路徑，使其利用率達到最大流。

4 利用MATLAB程序?qū)ι鲜鲭娋W(wǎng)進行分析

建立數(shù)學(xué)模型對電網(wǎng)進行有向圖的規(guī)劃，在利用Ford和Fulkerson在1957年提出的標(biāo)號法對最大流進行分析與計算。標(biāo)號法是為了尋找可增廣軌，使網(wǎng)絡(luò)的流量得到增加，直到最大為止分為以下兩個過程：A.標(biāo)號過程：通過標(biāo)號過程尋找一條可增廣軌。B.增流過程：沿著可增廣軌增加網(wǎng)絡(luò)的流量。

其兩個分析方法將可以分為以下具體步驟：

（A）標(biāo)號過程：

（i）給發(fā)點標(biāo)號為。

（ii）若頂點已經(jīng)標(biāo)號，則對的所有未標(biāo)號的鄰接頂點按以下規(guī)則標(biāo)號：

①若，且時，令，

則給頂點標(biāo)號為，若，則不給頂點標(biāo)號。

②，且，令，則給標(biāo)號為，若，則不給標(biāo)號。

（iii）不斷地重復(fù)步驟（ii）直到收點被標(biāo)號，或不再有頂點可以標(biāo)號為止。當(dāng)被標(biāo)號時，表明存在一條從到的可增廣軌，則轉(zhuǎn)向增流過程（B）。如若點不能被標(biāo)號，且不存在其它可以標(biāo)號的頂點時，表明不存在從到的可增廣軌，算法結(jié)束，此時所獲得的流就是最大流。

（B）增流過程。

（i）令。

（ii）若的標(biāo)號為），則；若的標(biāo)號為，則。

（iii）若，把全部標(biāo)號去掉，并回到標(biāo)號過程（A）。否則，令，并回到增流過程（ii）。

求網(wǎng)絡(luò)中的最大流的算法的程序設(shè)計具體步驟如下：

對每個節(jié)點，其標(biāo)號包括兩部分信息

該節(jié)點在可能的增廣路中的前一個節(jié)點，以及沿該可能的增廣路到該節(jié)點為止可以增廣的最大流量。

在回歸到最大問題的解決過程中，根據(jù)電網(wǎng)規(guī)劃過程中的最大流定理，則可以總體上回歸到一個線性歸劃問題中。

5 結(jié)語

本文通過利用一種數(shù)學(xué)方法，對電力系統(tǒng)網(wǎng)絡(luò)通過建模，在利用MATLAB輔助程序?qū)λ?guī)劃的圖，進行有向圖的分析，使得達到最大流，由于電網(wǎng)是多元多匯網(wǎng)絡(luò)，為了建模與計算方便，本文將把多元多匯網(wǎng)絡(luò)化成多個單元單匯網(wǎng)絡(luò)進行求解，從而把非線性的問題總結(jié)并規(guī)劃到線性問題上進行求解，解決了最大流問題的解決文案。endprint