第3章線性規劃3.1約束目標標準型3.2從無窮到有限之基解3.3

單純形法3.4對偶問題3.5運輸問題3.6典型案例

3.1約束目標標準型

3.1.1線性規劃的一般形式

定義3-1線性規劃(LinearProgramming,LP)是一種凸規劃問題,它的目標函數為最大化(或者最小化)決策變量的線性多項式,約束條件為決策變量的線性不等式(或者等式),其一般形式為

若記

則其一般形式可以表示為

3.1.2線性規劃的標準形式

定義3-2線性規劃的標準形式為

則標準形式可以記為

定理3-1線性規劃的一般形式可以轉換為等價的標準形式。

對于目標函數,可以通過將系數向量取負,將最大化和最小化目標函數進行互化。對于約束條件來講,不等式可以通過增加輔助決策變量的方法進行轉換,遵循以下轉換規則:

(1)對于小于不等式,在左側加上一個輔助決策變量。

(2)對于大于不等式,在左側減去一個輔助決策變量。

例3-1對于如下線性規劃模型的一般形式,將其轉換為標準形式。

先通過將系數向量取負,將目標函數轉換為最小化,然后增加一個輔助決策變量將約束條件不等式轉換為等式,得到如下標準形式

3.1.3-整數線性規劃

定義3-3-如果線性規劃的所有決策變量都必須是整數,那么這個問題稱為整數規劃問題。

例3-2有三種物品A、B、C,單位物品的重量分別為1、2、3,單位物品的價值分別為15、33、50,背包的最大載重為4,請問可裝入背包的物品的最大價值是多少?

設裝入背包的三種物品的數量分別為x1,x2,x3,則可以建立一般形式的線性規劃模型

其中目標函數代表最大化裝入背包中物品的價值,第一個約束條件代表裝入背包中的物品總重量不能超過背包的最大載重4,第二個約束條件代表裝入背包中物品的數量不能為負,第三個約束條件代表裝入背包中物品的數量為整數

定義3-4如果線性規劃的所有決策變量只能取0或者1,則稱之為0-1整數規劃。

3.2從無窮到有限之基解

3.2.1可行解

定義3-5可行解是滿足約束條件的解。所有可行解的集合稱作可行域。

首先,線性規劃標準形式約束條件的主體是一個線性方程組,另外加一個非負條件。

若先不考慮非負條件,這個線性方程組可變為

與線性規劃問題的可行域有如圖3-1所示對應關系。

圖3-1線性規劃可行域與線性方程組解集之間的對應關系

定理3-2線性規劃標準形式的可行域等于其約束條件組成的線性方程組的非負解集。

根據線性方程組解的理論,線性方程組的解有以下幾種情況:

(1)無解,R(A)<R(A,b)。

(2)唯一最優解,R(A)=R

(A,b)=n。

3)無窮多最優解,R(A)=R(A,b)<n。其中,A=[aij

];b=[bi

];i=1,…,m;j=1,…,n;R(·)代表矩陣的秩。

因此,根據定理3-2,可以有以下結論:

(1)若線性規劃標準形式約束條件構成的線性方程組無解,則線性規劃問題無解。

(2)若此線性方程組有唯一非負解,則這個解是線性規劃問題可行解也是最優解;若此線性方程組有唯一解,但是負數,則線性規劃問題無解。

(3)若此線性方程組有無窮多非負解,則線性規劃問題有可能有無窮多可行解,這種情況是線性規劃研究的重點。

3.2.2基解

在這種情況下,根據生成測試范例的樸素優化思想,我們可以往可解的方向碰碰運氣。如果令任意n-m個變量取特定值(如取0),把它們看作常量,移動到等式的右邊,得

這樣方程組就可解了。

定義3-6如果將n-m個變量取值為0,對線性規劃標準形式約束條件構成的線性方程組求解,若能得到唯一解,則稱此解為線性規劃問題的基解,如果基解滿足非負條件,則稱為基可行解,取值為0的n-m個決策變量稱為非基變量,等式左邊的m個決策變量稱為基變量,基變量對應的系數矩陣的列稱為基向量,基向量組成的矩陣稱為線性規劃問題的基。

例如,對于線性方程組(3-1),若有唯一解,則其所對應的線性規劃問題的基為

其中,Pi為基向量,與基向量Pi相應的變量xi為基變量,否則稱為非基變量。

3.2.3-基解三定理

定理3-3-若線性規劃問題存在可行域,則一定是凸集。

定理3-4若線性規劃問題的可行域有界,則一定可在此凸集的頂點上達到最優。

定理3-5線性規劃的可行域的頂點與基可行解一一對應

(2)若X不是基可行解,則X一定不是可行域的頂點。

3.2.4基解的枚舉

這樣,由于最優解一定是基解,基解的數量是有限的,因此可以使用枚舉法求解線性規劃標準形式,步驟為:

步驟1:在n個決策變量中,選擇m個決策變量作為基變量,其他變量取0,求線性規劃標準形式隱含的線性規劃方程組,若得到唯一解,則此唯一解就是基解,若非負,則是基可行解。

步驟2:循環執行步驟1直到找出所有的基可行解,對比其目標函數,使目標函數達到最優的即為最優解。

例3-4對如下的線性規劃一般形式的模型:

(1)將其可行域在二維坐標系中表示出來。

(2)將一般形式轉換為標準形式,并計算其所有的基解。

(3)對比基解與可行域在二維坐標系中的頂點的關系。

因為每個約束條件不等式都代表二維平面上的一個半平面,因此,這些半平面的交集構成線性規劃問題的可行域,利用軟件QMforWindows畫出來的可行域如圖3-2所示。圖3-2圖解法實例

將其轉換為標準形式為

利用基解的求解方法可得,基解、基可行解及其對應的目標函數值如表3-1所示。

3.2.5基解的啟發尋優

采用啟發式算法尋找最優解的基本流程如圖3-3所示。圖3-3-基解的啟發尋優過程框架

3.3-單純形法

3.3.1起點單純形法可以選擇任意基可行解作為搜索的起點。為了方便,可以直接在系數矩陣中找出或者通過初等變換得到一個單位子矩陣,其所對應的變量作為初始可行基變量。

3.3.2鄰域中的改進解

1.換入基的確定

根據約束條件,非基變量可以使用基變量來表示。因此,在約束條件中,將非基變量移動到等式右邊,求得基變量的表達形式為

換入基操作:利用非基變量表示目標函數,非基變量xj的系數σj作為檢驗數,即

檢驗數σj為正的非基變量進基．

2.換出基的確定

換出基操作:確定了換入基變量之后,利用

確定換出基變量xl。

3.3.3-終止

當所有的檢驗數σj均小于等于0的時候,非基變量無法進基,目標函數無法得到進一步的改進,算法終止。

3.3.4算例

例3-5對于如下的線性規劃標準形式:

系數矩陣為

步驟2:通過換入基和換出基操作,得到一個改進的基可行解。所有與基x3,x4相鄰的基如表3-3所示。

將以上計算過程的數據整理到單純形表中,如表3-4所示。

將換入基變量x2和換出基變量x4進行調換,得到表3-5。

步驟3:通過換入基和換出基操作,得到下一個改進的基可行解。所有與基x3,x2相鄰的基如表3-6所示。

根據約束條件中基變量與非基變量之間的關系,使用非基變量表示目標函數得

從換基的效果來講,選擇x1進基可以使目標函數值增加,x4進基可以使目標函數值降低。因此選擇x1進基,當前待換入基變量為x1。

將換入基變量x1和換出基變量x3進行調換,得到表3-8。

步驟4:通過換入基和換出基操作,得到下一個改進的基可行解。所有與基x1,x2相鄰的基如表3-9所示。

根據約束條件中基變量與非基變量之間的關系,使用非基變量表示目標函數得

從換基的效果來講,選擇x3或者x4進基均使目標函數值降低,因此算法停止。

對表3-9進行初等變換,令基變量對應的系數列向量為單位向量,并重新計算檢驗數

從而得到表3-10。

此時的基可行解為最優解:

3.4對偶問題

3.4.1機會成本與影子價格定義3-7機會成本是當投資者、個人或企業決策時選擇某種方案而不是另一種方案時,錯過或放棄的收益。

例3-6假設你的公司使用A和B兩種原料生產C、D兩種油漆,表3-11提供了基本數據。

請問怎么確定最好的C、D油漆產品混合,使你的日總利潤最大?

假設生產C、D油漆的數量分別為x1和x2,則上述問題可以建立以下線性規劃模型

利用單純形法可以很容易求得問題的最優解為x1=3,x2=1.5,z=21。

但是僅就獲取利潤來講,如果另外一個經理時刻關注著原材料的市場價格y1和y2,當市場價格達到某個水平時,他可以選擇不生產,而直接賣掉原材料,卻可以獲得更大的利潤,這個多獲得的利潤就是用原材料進行生產而不是直接賣掉的機會成本。例如,原材料1和原材料2的價格滿足以下約束:

則自己生產的利潤是要小于直接把原材料賣掉所獲得的利潤的,辛辛苦苦生產的還不如將原材料直接賣掉的企業掙得多,如圖3-4所示。

圖3-4影子價格

影子價格使用如下模型求得

而這個模型,由于和原線性規劃模型有著十分漂亮和規整的關系,稱為原線性規劃問題的對偶問題。

3.4.2對偶問題的模型

一般地,對于如下線性規劃模型

其對偶問題模型為

更為一般地,任意形式的線性規劃都可以通過以下變換規則得到其對應的對偶問題。

(1)原問題的約束條件和對偶問題的決策變量一一對應,原問題約束條件的右端常數作為對偶問題的目標函數系數;

(2)原問題的決策變量和對偶問題的約束條件一一對應,原問題的目標函數系數作為對偶問題約束條件的右端常數項,原問題的系數矩陣轉置后等于對偶問題的系數矩陣;

(3)原問題為最大化(最小化),則對偶問題為最小化(最大化);

(4)約束與變量之間對應的不等式方向的變換規則如表3-12所示。

3.5運輸問題

3.5.1真假運輸問題1.真運輸問題本章所述的運輸問題,是最簡單的運輸問題,運輸的貨物是單一無差別的,不同的產地產量不同,不同的銷地需求量不同,不同產地和銷地之間的運輸費用也不同,在這樣的情況下,確定不同產地到不同銷地之間的供應量,使運輸費用最小。

例3-7三個煉油廠的日煉油能力分別為600萬升、500萬升和800萬升,所供應三個分銷區域的日需求量分別為400萬升、800萬升和700萬升。汽油通過輸油管線被運送到分銷區域。管線每公里運送1萬升的運費為100元。表3-13給出了煉油廠到分銷區域的里程表。其中煉油廠1與分銷區域3-不相連。

例3-8為確保飛行安全,飛機發動機需定時更換進行大修。現有三個航修廠和四個機場。三個航修廠A1、A2、A3-的月修復量分別為7臺、4臺、9臺;四個機場B1、B2、B3、B4的月需求量為3臺、6臺、5臺、6臺。各航修廠到各機場的單位運價(萬元)如表3-14所示。問應如何調運發動機完成運輸任務而使運費最省。

2.假運輸問題

有一些問題雖然表面上看著不是運輸問題,但是可以建立運輸問題的類比模型,因此,我們稱之為假運輸問題。

例3-9一種小型發動機未來五個月的需求量分別為200臺、150臺、300臺、250臺、480臺。生產商對這五個月的生產能力估計為180臺、230臺、430臺、300臺、300臺。不允許延期交貨,但在必要的情況下生產商可安排加班滿足當前需求。每個月的加班生產能力是正常生產能力的一半。五個月的單位生產費用分別為100元、96元、116元、102元、106元。加班生產的費用比正常生產的費用高50%。如果當月生產的發動機在以后月使用,則每臺發動機每個月的額外儲存費用為4萬元。為問題建立一個運輸模型并確定每個月正常生產和加班生產發動機的數量。

3.5.2運輸問題模型

1.線性規劃模型

設xij和cij為產地i到銷地j的物品運輸量和單位運價,si為產地i的產量,dj為銷地j的需求量,則運輸問題的線性規劃模型如下:

其系數矩陣具有如下形式:

2.表模型

運輸表模型,就是在運輸費用表的基礎上,拓展而成的一個表,其基本框架如表3-15所示。

因此,例3-7就可以建立如表3-16所示的運輸表模型．

例3-8的運輸表模型如表3-17所示。

對于例3-9來講,要建立運輸表模型,就要確定產地、銷地、單位運價以及供應量和需求量等表中的基本要素。產地和銷地分別有五個,代表五個月份,i月到j月的單位運價就是i月生產一個發動機j月用的總的費用,這個總的費用要包含正常生產費用、加班費用、儲存費用等因素。其中,空白區域對應的產地和銷地無法到達,所建立的運輸表模型如表3-18所示。

3.圖模型

所謂圖模型,就是將產地和銷地用圖上的點來表示,點上有數字代表供應量或者需求量,使產地和銷地之間的邊來表示運輸關系,邊上的權重表示單位運價。

例3-7的運輸圖模型如圖3-5所示,其中從s點到煉油廠的邊上的容量為煉油廠的產量,單位運價為0;從分銷區域到t的邊上的容量為分銷區域的需求量,單位運價為0;從煉油廠到分銷區域的其他邊上的容量沒有限制,單位運價為兩者之間的單位運價。

圖3-5例3-7的運輸問題圖模型

例3-8的運輸圖模型如圖3-6所示。其中從s點到航修廠的邊上的容量為月修復量,單位運價為0;從機場到t的邊上的容量為機場的需求量,單位運價為0;從航修廠到機場的其他邊上的容量沒有限制,單位運價為兩者之間的單位運價。

圖3-6例3-8的運輸問題圖模型

例3-9的運輸圖模型如圖3-7所示。其中從s點到煉油廠的邊上的容量為煉油廠的產量,單位運價為0;從分銷區域到t的邊上的容量為分銷區域的需求量,單位運價為0;從煉油廠到分銷區域的其他邊上的容量沒有限制,單位運價為兩者之間的單位運價。

圖3-7例3-9的運輸問題圖模型

3.5.3-運輸問題算法

1.貪婪啟發式算法

1)最小元素法

最小元素法中的元素,指的就是運價,也就是為產地和銷地之間的貨物制訂匹配運輸關系時,優先選擇可運輸的全局最小運價。最小元素法屬于貪婪啟發式算法,不能保證得到最優解,但是可以得到一般意義下的較優解。

例如,表3-16的表模型中,運用最小元素法的計算運輸方案過程如下:

(1)在運價表中選擇最小元素,并最大化地滿足其對應的產銷地的剩余產銷量,從而得到表3-19。

(2)在運價表中選擇供需均大于0的最小元素,并最大化地滿足其對應的產銷地的剩余產銷量,從而得到表3-20。

(3)在運價表中選擇供需均大于0的最小元素,并最大化地滿足其對應的產銷地的剩余產銷量,從而得到表3-21。

(4)再一步迭代計算得到表3-22。

(5)繼續迭代計算得到表3-23。

(6)所有的供應量和均為0,算法結束,得到最后結果如表3-24所示,其中括號中的數量為對應產地和銷地之間的運量方案。

2)伏格爾法

最小元素法是貪婪算法,特點是只顧眼前。伏格爾法的考慮往前更進了一步,如果一個物品不能按照最小的費用運輸,而是按照次小的費用運輸,這就有一個差額,不妨令gsi代表產地i的差額,gjd代表銷地j的差額。將這個差額作為一種啟發信息,對于差額大的產地或者銷地,優先安排最小元素,這樣有可能會降低貪婪的成本。

步驟4:若產銷地均無余量可形成運輸指派,也即

則算法結束,否則轉步驟2。

2.最優性條件

定理3-6對于貪婪啟發式算法得到的除最后一個0+之外的m+n-1個變量為基變量(包括取值為正以及0+的所有變量),這樣給出的解是運輸問題的基解。

證明:首先,算法每使一個產地的產量或者銷地的需求歸0,就會增加一個變量,因此,使所有的產量及銷量歸0,總共增加的變量的個數為m+n,而算法最后一步加上的變量的值為0+,除去這個變量之外的m+n-1個變量構成基變量。

在使用貪婪啟發式算法確定第一個變量xi1j1,它對應的系數列向量為

其中,ei1是第i1個元素為1的單位列向量。

例3-10檢驗例3-7的結果(見表3-25)是不是最優解。

因為基變量的檢驗數為0,所以有

可見,非基變量的檢驗數有非負的,即

3.5.4從不平衡到平衡

例3-11在例3-7的基礎上,假設煉油廠3的日生產能力增大為1000萬升,那么必然有銷地得不到完全滿足,在這種情況下,建立相應的運輸模型,使三個煉油廠的煉油最大化地運輸,并且總的運費最小。

可以建立一個虛擬的銷地,其銷量為200萬升,并設煉油廠到此虛擬銷地的運價取較大的數,例如1000000,可建立運輸問題的表模型如表3-27所示。

3.6典型案例

3.6.1投資方案的規劃1.問題描述良好的投資規劃,對國民生產產生直接推動作用,對國民收入有著正相關的積極影響。在投資方案的規劃過程中既要考慮實現投資方案的可行性,又要考慮投資方案的盈利率。這里考慮一個經過抽象和定義過的案例。

2.問題分析

單從收益率來講,計劃B具有明顯的優勢,因此,根據啟發式規則,我們要將盡量多的錢投入B計劃中。投資周期為三年,B計劃以兩年為周期,因此在三年的周期中,計劃B只能投資一次,若第一年全部投到B計劃中,則在第二年末收回本金和收益共計300萬元之后,還剩下一年,只能投資于A計劃,到第三年末總共收益321萬元。

為了讓B計劃能有更多的資金,獲取更高的收益,我們可以讓100萬元第一年先投資于A計劃,第二年得到總計107萬元之后,再將其全部投入B計劃中,這樣第三年末得到的總收入是321萬元。

3.建立模型

設決策變量如表3-28所示。

表3-28決策變量及其含義

整理得如下線性規劃模型:

4.求解

應用Matlab的線性規劃求解函數linprog,求解的代碼及得到的最優解如下所示:

5.單純形表求解

利用單純形法進行計算,首先要將線性規劃轉化成標準形式如下:

(1)列出初始單純形表如表3-29所示。

(2)選定檢驗數σj最大的非基變量之一作為進基變量,這里可選擇x1B進基,在其所在的列,按照換出基確定的規則,可選擇y1或者y2作為出基變量,這里不妨選y1作為出基變量,從而得到表3-30。

(3)通過初等變換,將x1B所在的列變為單位向量,更新檢驗數基右端常數項,從而得到表3-31。

(4)同樣地,選定檢驗數σj最大的非基變量x2B進基,在其所在的列,按照換出基確定的規則,選擇y2作為出基變量,從而得到表3-32。

(5)通過初等變換,將x2B所在的列變為單位向量,更新檢驗數基右端常數項,從而得到表3-33。

(6)選定檢驗數σj最大的非基變量x1A進基,在其所在的列,按照換出基確定的規則,選擇x1B

作為出基變量,從而得到表3-34。

(7)通過初等變換,將x1A所在的列變為單位向量,更新檢驗數基右端常數項,從而得到表3-35。

(8)選定檢驗數σj最大的非基變量x3A進基,在其所在的列,按照換出基確定的規則,選擇y3作為出基變量,從而得到表3-36。

6.討論

模型不考慮盈利率波動,以及資金的時間價值等在實際的投資中會考慮的一些重要因素。

軟件計算和使用單純形表手工計算得出來的分配方案并不相同,但是最優目標函數值是一樣的,這說明模型的最優解不唯一。

3.6.2防御兵力的部署

1.問題描述

藍軍試圖入侵由紅軍防御的領地。紅軍有三條防線和200個正規戰斗單位,并且還能抽調出200個預備單位。藍軍計劃進攻兩條前線(南線和北線);紅軍設置三條東西防線

(Ⅰ、Ⅱ、Ⅲ),防線Ⅰ和防線Ⅱ各自要至少阻止藍軍進攻4天以上,并盡可能延長總的戰斗持續時間。藍軍的前進時間由下列經驗公式估計得到:

戰斗持續天數的經驗公式的系數如表3-37所示。

紅軍的預備單位能夠且只能用在防線Ⅱ上,藍軍分配到三條防線的單位數由表3-38給出。

紅軍應如何在北線/南線和三條防線上部署他的軍隊?

2.問題分析

定義八個決策變量xij(i=1,2;j=1,2,3),分別表示各個防線上的正規兵力部署數量,yij表示部署在防線Ⅱ上的預備兵力的數量。那么我們就可以依據經驗公式計算各個防線上的戰斗持續時間。

案例要求盡可能延長總的戰斗持續時間,這只是戰術要求的具體量化抽象,在不同的戰術場景中,對總的戰斗持續時間也有不同的具體計算方式。

以下的目標函數適合類似“拖延戰”的戰術場景,也就是作戰的目的是拖住敵方的兵力,使其無法騰出手來攻擊其他目標。

3.建立模型

兵力的分配要受到以下約束:

正規戰斗單位總數為200個,因此有

4.求解

采用目標函數一的時候,數學模型是線性規劃模型,可以使用Matlab求解。

5.討論

線性規劃的模型和算法都很標準化、程序化,可以快速方便地求解很多復雜和大型的問題。但是,我們仍然需要在心里牢記,這并不能替代優化決策系統過程中的其他環節。

3.6.3-火車站售票的規劃

1.問題描述

從城市A到城市B開通了一條新的客運鐵路,總共有N個站點,各站點依次編號,A市站點編號1,B市站點編號N。這列火車的最大載客量是n人。為提高客運能力,增加收益,在對歷史數據進行了統計分析以及對未來一段時間進行了預測的基礎上,得出了不同站點之間客運需求的數量。如果因客運量限制而不能接受所有訂單,則會拒絕部分訂單。現在要根據這些數據,確定鐵路售票的規劃,使可能的總收益最大化,一個已接受訂單的收益是訂單中乘客人數和火車票價格的乘積。總收益是所有已接受訂單的收益之和。

例如,假設從城市A到城市B的站點數目為N=6,火車最大載客量n=2000,不同站點之間的客運需求已知數據如表3-39所示。

2.問題分析與建模

3.求解

3.6.4武器目標分配問題

1.問題描述

在時刻t,某單位有3個武器系統,每個武器系統均有2個目標通道,要射擊6批目標,武器系統對目標的射擊有利度數據如表3-41所示,要進行目標分配,使總的射擊有利度達到最大,請建立數學模型。

2.問題分析與建模

為了簡化起見,將上述模型進行轉化,每個通道視為一個單獨的武器,建立武器目標分配問題的射擊有利度矩陣如表3-42所示。第4章網絡最優化4.1最小支撐樹問題4.2最短路問題4.3最大流問題4.4

最小費用流問題4.5二分匹配問題

4.1最小支撐樹問題

定義4-3連通圖G=(V,E)的最小支撐樹T(G)就是圖的權重之和最小的支撐樹。

其中,cij是邊(i,j)的權重。

例4-1某公司中標為“一帶一路”上某國家的六個居民點提供寬帶建設服務,圖4-1給出了鋪設通信線路的可能情況及相應距離。請確定最經濟的通信線路鋪設方案,使六個居民點可以連接起來。

圖4-1寬帶網絡拓撲結構設計問題的輸入

記六個居民點及相應的可能連接方式組成的圖為G=(V,E),設xij為決策變量,xij=1代表點i與點j之間鋪設的通信線路,否則不鋪設。此問題可以表示為以下線性規劃模型

本問題可以使用線性規劃求解,但是對于點的數量較多的問題,使用線性規劃求解的話就不可行了。例如,對于有60個點的圖,要用線性規劃模型求解最小支撐樹,需要的約束條件數量比地球上的原子數量還多。

支撐樹使用了最少數量的邊連通了圖的所有點,從數量方面是網絡連通優化設計問題的最優方案,而最小支撐樹是邊的總長度之和最小的支撐樹,因此,從數量和質量方面都是最優的網絡連通設計方案。

4.1.2兩個屬性

1.Cut屬性

在最小支撐樹的線性規劃模型中,式(4-2)代表連通性約束,不等式左側的表達式表示圖的截集中至少有一條邊要保留。

定義4-4-圖G=(V,E)中,對于?S?V,所有的一端在S中、一端不在S中的邊構成的集合稱為圖的截集。

例4-2圖4-1的截集數量為6!/2,其中兩個如圖4-2所示。圖4-2圖的截集示例

最小支撐樹的Cut屬性:連通圖G任意截集的最小邊必屬于最小支撐樹。

2.Cycle屬性

最小支撐樹的另外一個屬性是無圈的,因此,任意圈上肯定有一條邊不屬于最小支撐樹,依據“貪婪法”的啟發式規則,我們猜測圈上的最大邊不屬于最小支撐樹。

最小支撐樹的Cycle屬性:圖中圈上若只有單一最大邊,則此最大邊一定不屬于最小支撐樹;若有多條最大邊,則去掉任意一條最大邊,不影響得到最小支撐樹。總之,去掉圈上一條最大邊,仍然可以得到最小支撐樹。

算法的步驟如下:

例4-3利用Prim算法求解圖4-1的最小支撐樹。

步驟1:首先令S={6},則Cut(S)={(6,3),(6,4)},E(T)=?,得到最小邊為emin=(6,4),如圖4-3所示。

步驟2:(6,4)是最小支撐樹上的邊,令E(T)=E(T)∪emin={(6,4)},S=S∪V(emin)={6,4},則

Cut(S)={(6,3),(4,1),(4,2),(4,3),(4,5)}

得到最小邊emin=(4,2),如圖4-4所示。

圖4-3例4-3求解步驟1的結果

圖4-4-例4-3求解步驟2的結果

步驟3:(4,2)是最小支撐樹上的邊,令E(T)=E(T)∪emin={(6,4),(4,2)},S=S∪V(emin)={6,4,2},則

Cut(S)={(6,3),(4,1),(4,3),(4,5),(2,1),(2,3),(2,5)}

得到最小邊emin=(1,2),如圖4-5所示。

圖4-5例4-3求解步驟3的結果

步驟4:(1,2)是最小支撐樹上的邊,令E(T)=E(T)∪emin={(6,4),(4,2),(1,2)},S=S∪V(emin)={6,4,2,1},則

Cut(S)={(6,3),(4,3),(4,5),(2,3),(2,5),(1,3),(1,5)}

得到最小邊有三條,emin=(2,3)、(2,5)、(4,3),如圖4-6所示。

圖4-6例4-3求解步驟4的結果

步驟5:可以任選一條最小邊加入E(T),如(2,3)。令E(T)=E(T)∪emin

={(6,4),(4,2),(1,2),(2,3)},S=S∪V(emin

)={6,4,2,1,3},則

Cut(S)={(4,5),(2,5),(1,5)}

得到最小邊emin

=(2,5),如圖4-7所示。

圖4-7例4-3求解步驟5的結果

步驟6:(2,5)是最小支撐樹上的邊。令E(T)=E(T)∪emin

={(6,4),(4,2),(1,2),(2,3),(2,5)},S=S∪V(emin

)={6,4,2,1,3,5},算法結束,如圖4-8所示。圖4-8例4-3求解步驟6的結果

2.Kruskal算法

從構造的角度考慮,在選擇一部分邊時,只要避免將圈上的最大邊選上就可以了。

Kruskal從構造的角度提出了尋找最小支撐樹的方法。

Kruskal法將所有的邊從圖中取出來,從小到大依次考慮重新加回到圖中,如果不產生圈則留下,否則拋棄掉,這也是一種“貪婪算法”。

例4-4-利用Kruskal算法求解圖4-1的最小支撐樹。

步驟1:令E(T)=?,當前圖中的最小邊為

如圖4-9所示。圖4-9例4-4求解步驟1的結果

步驟2:(1,2)選作最小支撐樹上的邊,令E(T)=E(T)∪emin={(1,2)},E=E-{(1,2)},剩下圖中的最小邊為圖4-10例4-4求解步驟2的結果

步驟3:(6,4)選作最小支撐樹上的邊,令E(T)=E(T)∪emin

={(1,2),(6,4)},E=E-{(6,4)},剩下圖中的最小邊為

如圖4-11所示。圖4-11例4-4求解步驟3的結果

步驟4:(2,4)選作最小支撐樹上的邊,令E(T)=E(T)∪emin

={(1,2),(6,4),(2,4)},E=E-{(2,4)},剩下圖中的最小邊有三條,emin

=(2,3)、(2,5)、(4,3),如圖4-12所示。圖4-12例4-4求解步驟4的結果

步驟5:可以任選一條最小邊加入E(T),如(2,3)。令E(T)=E(T)∪emin={(1,2),(6,4),(2,4),(2,3)},E=E-{(2,3)},剩下圖中的最小邊有兩條,emin=(2,5)、(4,3),如圖4-13所示。圖4-13例4-4求解步驟5的結果

步驟6:可以任選一條最小邊加入E(T),如(2,5)。令E(T)=E(T)∪emin

={(1,2),(6,4),(2,4),(2,3),(2,5)},E=E-{(2,5)},剩下圖中的最小邊為emin

=(4,3),如圖4-14所示。圖4-14-例4-4求解步驟6的結果

步驟7:此時,E(T)中已經有5條邊滿足支撐樹點數和邊數的關系,算法停止。可以看到,此時,若再加入任意邊,都會產生圈。

算法的步驟可以總結為口訣:“一邊一邊地連,先連最小邊,不能產生圈”。

3.破圈法

破圈法是指利用Cycle屬性,逐步去掉圈上的最大邊,最終得到最小支撐樹。其步驟總結為口訣:“一圈一圈地破,破掉圈上最大邊”。

對于連通圖G=(V,E),破圈法的步驟總結如下:

4.1.4-拓展應用:k－聚類分析

聚類就是一種尋找數據之間一種內在結構的技術。聚類把全體數據實例組織成不同的組,處于相同分組中的數據實例彼此相近,處于不同分組中的實例彼此相遠。對一個集合

V={v1,v2,…,vn}中的對象,在已知對象之間差異性度量的情況下,將其分為由類似的對象組成的多個類Vi的過程,稱為聚類分析,其中

使用最小支撐樹進行k－聚類分析的步驟如下:

步驟1:將聚類的對象集合V看作圖G=(V,E)的點集,將對象之間的差異性dij作為點之間邊(i,j)∈E的權重。

步驟2:求解G的最小支撐樹T=(V,E')。

步驟3:去掉T上的k-1條最大邊,得到k個相互不連通的連通子圖Gi=(Vi,Ei

')i=1,…,k,則Vi是第i類的點集合。

例4-5某電子企業需要在10臺機器上生產15種電子零件。企業準備將機器分成若干組,使零件在不同機器上生產的“差異”最小。零件i在機器j上生產的“差異”定義為

其中,nij表示機器i和機器j上都可以生產的零件數量;mij表示只能在機器i和機器j其中之一生產的零件數量。根據表4-1給出的數據,求將機器分成兩組和三組的解。

步驟1:將不同機器生產的零件按照表4-1所示的對應關系輸入Matlab的cell結構變量中,可以得到:

步驟2:按照差異的定義,計算dij:

步驟3:將d作為鄰接矩陣,求解圖的最小支撐樹:

結果如圖4-15所示。

圖4-15機器差異性最小支撐樹

步驟4:若要將機器分成2組,則去掉最小支撐樹上的一條最大邊就可以達到目的(見圖4-16(a)),若要將機器分成3組,再去掉一條最大邊即可(見圖4-16(b)),以此類推。圖4-16利用最小支撐樹對圖上的點進行2－聚類和3－聚類

4.1.5拓展應用:戰備通信節點的建設問題

1.問題描述

構建將N個城市作為節點的有線通信網絡,在每個城市內設置一架專用網絡連接設備,請設計通信網絡的最經濟連接方案。同時,為了增加抗毀性,可以在N個城市之外的地方構建一定數量的戰備節點,戰備節點平時不工作,當出現應急突發情況、通信網絡中斷時,可以啟用戰備節點,迅速地恢復通信網絡的連通性,請設計戰備節點的建設方案。設計時應充分考慮經濟性和抗毀性。經濟性是指要考慮節省網絡連接的總費用,而抗毀性是指要提高網絡在節點故障的情況下仍然保持連通的能力。

現已知138個城市(見圖4-17)建設網絡節點的選址的經緯度坐標,請為通信網絡的優化設計提供優化方法。圖4-17需要建立通信網絡連接的138個節點分布

2.問題分析

若只考慮經濟性指標,這是一個網絡最優化決策中的最小支撐樹問題(參見4.1節),輸入是點以及點之間的連接費用。給定的N個城市作為網絡上的點,點之間的通信連接費用可以用點之間的通信連接長度來代替。

3.最經濟的連通方案

根據已知通信網絡節點的選址經緯度坐標,可以計算相互之間的距離,這是一種簡要的代替節點之間通信連接建設費用的方法。然后利用網絡最優化中的最小支撐樹求解算

法,求解通信線路總長度最短的建設方案。假設將N個城市的經緯度坐標(度)存儲到N×2維變量Cord中,其第一列存儲的是點的緯度信息,第二列存儲的是經度信息,共有N行,每行對應一個城市選址點,可得到:

求得的以距離度量的最經濟的通信線路建設方案如圖4-18所示。

圖4-18以距離度量的最經濟的通信線路建設方案

4.最經濟的恢復方案

預備建設戰備節點的集合為Nb,使通信節點Nd?V被破壞的情景下,網絡G'=(V-Nd

,E-E(Nd

)),可以對網絡進行連通性分析

例如,去掉第53、56和105個城市之后,網絡分成相互不連通的4個部分,如圖4-19所示。Matlab代碼如下:

圖4-19破壞掉3個節點后,通信網絡分成4個獨立的部分

4.2最短路問題4.2.1線性規劃模型在網絡G=(V,E)中,邊(i,j)∈E的權值(長度、時間、費用等的抽象)為cij,尋找從起點s∈V到終點t∈V的最短路P,就稱為最短路問題。目標函數是位于最短路上的邊的總長度最短,即其中,xij∈{0,1}是決策變量,xij=1代表邊(i,j

)是最短路上的邊,否則不是。

約束條件是,對于起點s來講

對于終點t來講

對于網絡中的其他點k∈V-s-t來講

4.2.2最優性條件

在圖G=(V,E)上,為每個點vj引入一個標號{dj,vj},dj代表從s出發到達vj的某條已知道路的長度,vi是這條道路上與vj鄰接的上一個點。

最優性條件:如果圖上的所有的點的標號滿足以下條件:

則圖上任意點vi的標號dj都代表從s點到當前點vi的最短路長度。

4.2.3標號法

1.標號更新操作

假設對于圖上的某個邊(vi,vj

),其長度為cij,兩個端點的標號分別為{di,vi1},{dj,vj1},如圖4-20所示。曲線邊代表從s到箭頭端點的某條路,值代表這條路的長度;直線邊代表圖上的邊,值代表這條邊的長度。

若

可以執行標號更新操作

代表的含義是從s出發到點vj,找到了一條更短的路。

圖4-20標號示意圖

2.標號固定操作

假設圖上的邊的長度均非負,那么在任意時刻,圖上的最小標號對應的點為

此時,可以將vmin的標號固定下來,不再考慮更新,也可稱其為永久標號。因為根據標號更新操作的條件,永久標號不可能再更新。對于任意其他點的標號,有

不可能存在標號更新條件:

直觀理解就是,從s出發到任意其他與vj鄰接的點vi,再經過邊(vi,vj)到永久標號點vj,都不可能更短了。但是確定永久標號的前提是cij≥0,當圖中有負邊的時候,不能確定永久標號。

3.標號設定法

所謂標號設定法(Dijkstra算法),就是針對圖上不存在負值邊的G,在求解最短路的時候,每次更新標號后,都確定一個最小的標號點作為永久標號點,不再考慮標號的更新,直到所有的標號都固定下來后,算法結束。標號設定法的步驟如下:

例4-6在圖4-21中,求解從S=1到t=5的最短路。圖4-21例4-6圖

步驟1:設起點的標號為(0,?),其他點的標號為(∞,?),

S={v1},如圖4-22所示。圖4-22例4-6求解步驟1的結果

步驟2:更新{vj|(vi,vj)∈E,vi∈S}的標號,找到最小標號vmin=v2,將其標號固定下來,令S=S∪{vmin}={v1,v2},如圖4-23所示。圖4-23例4-6求解步驟2的結果

步驟3:更新{vj|(vi,vj)∈E,vi∈S}的標號,找到最小標號vmin=v3,將其標號固定下來,S=S∪{vmin}={v1,v2,v3},如圖4-24所示。圖4-24-例4-6求解步驟3的結果

步驟4:更新{vj|(vi,vj)∈E,vi∈S}的標號,找到最小標號vmin=v4,將其標號固定下來,令S=S∪{vmin}={v1,v2,v3,v4},如圖4-25所示。圖4-25例4-6求解步驟4的結果

步驟5:更新{vj|(vi,vj)

∈E,vi∈S}的標號,找到最小標號vmin=v5,將其標號固定下來,令S=S∪{vmin}={v1,v2,v3,v4,v5}。S=V,算法停止,如圖4-26所示。圖4-26例4-6求解步驟5的結果

4.標號更新法

所謂標號更新法,是指在求解最短路的時候,迭代地應用標號更新操作,直到所有的點的標號都無法更新為止,也就是滿足dj≤di+cij。標號更新法的步驟如下:

步驟1:設起點的標號為{0,?},其他點的標號為{∞,?}。

步驟2:更新{vj|(vi,vj)∈E}的標號。

步驟3:如果沒有標號可以更新,則算法停止,否則轉步驟2。

例4-7在圖4-27中,求解從S=1到t=5的最短路。圖4-27例4-7圖

步驟1:設起點的標號為{0,?},其他點的標號為{∞,?},如圖4-28所示。圖4-28例4-7求解步驟1的結果

步驟2:更新{vj|(vi,vj)∈E}的標號,如圖4-29所示。圖4-29例4-7求解步驟2的結果

步驟3:更新{vj|(vi,vj)∈E}的標號,沒有標號可更新,算法停止,如圖4-30所示。圖4-30例4-7求解步驟3的結果

4.2.4-拓展應用:數據約減

1.問題描述

數據包含信息,但是并不代表數據越多信息量越多。因此,對數據進行約減,可方便信息的存儲、讀取、分析等,同時,數據所包含的信息量沒有損失或者損失最小化,這個問題稱為數據約簡問題。

假設vi和vj(i<j)之間的點都被約減掉,那么,節省的存儲空間可以度量為

2.模型建立

如果要完全地羅列出圖G的所有弧,由于點的總數N很大,因此為了存儲所有的弧所需的空間仍然很大。為了降低計算對存儲空間的需求,可以采用降度的思路,迭代完成數據的約減,每步迭代只構造圖G的部分弧。

3.計算實例分析

假設有一組按時間序列記錄的數據,三個參數分別為A、B和C,數據如表4-2所示。

首先對數據進行無量綱化處理,得到的結果如圖4-31所示。圖4-31對飛參數據進行無量綱化處理后的數據

按照間隔為2的跨度建立最短路問題模型,則對于這個樣本數據來講,無損數據約減后(令α=1,β=1000000)剩余33個點,也就是有5個點是完全信息量意義下的冗余點(見圖4-32),這5個點的序號分別是17,18,19,20,21。

圖4-32無損數據約減后得到的數據序列,使用*標識

如果信息可以有損失,則可以有更多的點被約減掉,令α=1,則隨著β值的變化,被約減的點的數量統計如圖4-33所示。

圖4-33α=1情況下,隨著β值的增加,可以約減飛參數據的個數

4.3最大流問題

4.3.1線性規劃模型在圖G=(V,E)中,邊(i,j)∈E帶有容量uij和流量xij兩個參數,最大流問題就是求解從起點s到終點t可以通過的最大流量。

目標函數是網絡流量的最大化,也就是從s發出的流量最大,或者流入t的流量最大,即

對于圖上的點k∈V-{s,t},滿足以下流量守恒約束

任意邊上的流量還要滿足容量約束

4.3.2剩余容量圖

為了更加直觀地在圖上使用標號法求解圖的最大流,將容量流量標號變換為剩余容量標號。從容量流量標號到剩余容量標號的方法如圖4-34所示。圖4-33α=1情況下,隨著β值的增加,可以約減飛參數據的個數

4.3.3增廣鏈法

利用剩余容量圖法,計算圖上從s到t的最大流的步驟如下:

步驟1:將圖G=(V,E)的邊都轉化為剩余容量標號。

步驟2:在剩余容量圖上找到一條從s到t的任意路p,若找不到,則轉步驟4;否則計算

例4-8在圖4-35所示的容量圖中,求從S到t的最大流。圖4-35例4-8圖

步驟1:將圖G=(V,E)的邊都轉化為剩余容量標號,在剩余容量圖上找到一條從s到t的任意路p,并計算最大可擴充流量rmin=5,如圖4-36所示。圖4-36例4-8求解步驟1的結果

步驟2:在p上擴充流量,即執行以下運算:

結果如圖4-37所示。

圖4-37例4-8求解步驟2的結果

步驟3:在剩余容量圖上找到一條從s到t的任意路p,并計算最大可擴充流量,如圖4-38所示。圖4-38例4-8求解步驟3的結果

步驟4:在p上擴充流量,即執行以下運算:

結果如圖4-39所示。圖4-39例4-8求解步驟4的結果

步驟5:在剩余容量圖上找不到一條從s到t的路p,算法停止,將剩余容量圖上所有的邊,轉換為容量流量標號。也就是對于邊(i,j),其容量為uij,流量xij=rji=uij-rij,得到網絡最大流為6,結果如圖4-40所示。圖4-40例4-8求解步驟5的結果

4.3.4-拓展應用:彈藥目標最大化匹配問題

不同類型的彈藥適合轟炸不同類型的目標,如果匹配不得當,轟炸效果會大打折扣。在某次空中進攻作戰任務規劃中,有A、B、C、D、E五類彈藥各一個單位,計劃打擊6個

目標。6個目標最適合使用的彈藥如表4-3所示。

請問最多能打擊幾個目標?

將待打擊目標和彈藥都看作圖上的點,彈藥和目標之間有一條邊,容量為1,代表彈藥目標的匹配關系,增加一個虛擬的起始點s和一個虛擬的終點t,建立最大流模型如圖4-41所示,則圖上的從s到t的任意一個單位流,都代表一個彈藥目標匹配,最大流是由單位流組成的,代表最大的匹配關系。

圖4-41彈藥目標匹配問題的最大流

步驟1:根據表4-3建立圖模型:

步驟2:求解圖上的最大流,得到最優匹配方案:

4.3.5拓展應用:最大投送能力評估問題

最大投送能力是機動能力的重要度量。現假定需要從三個倉庫6、7、8將后勤物資運送到目的地1。道路上的容量取決于這條路上可用運輸工具的數量、容量以及往返次數。表

4-4給出了相應路線上的每天的最大運輸能力,也就是容量。請評估三個倉庫到目的地的最大投送能力。

若將倉庫和目的地都看作圖上的點,倉庫到目的地之間的道路投送容量設為邊上的容量值,為圖4-42增加一個虛擬的起點s連接到所有的倉庫,增加一個虛擬的終點t連接到所有的營地,則可以使用最大流模型進行求解。

步驟1:建立容量網絡,將表4-4的數據存儲到CapacityA矩陣中,在Matlab中建立有向圖模型:

結果如圖4-42所示。圖4-42投送能力評估的容量圖模型

步驟2:求解從9到1的最大流:

求得結果如圖4-43所示。

圖4-43最大投送能力的解

4.4-最小費用流問題4.4.1線性規劃模型在圖G=(V,E)中,邊(i,j)∈E上的參數包括容量uij、單位流量費用cij和實際流量xij,一些稱為源點或者匯點的點上具有參數bi,代表點上純供應流量或者純消耗流量,供應點的供應流量要流經網絡到達需求點滿足其需求,最小費用流問題就是求解從源點s到匯點t的最小費用流方案。可以表示為以下線性規劃模型

4.4.2三個最優性條件

1.負圈最優性條件

定理4-1一個網絡流方案是最小費用流的充分必要條件是,剩余容量圖中不存在單位流量費用為負的增廣圈。

證明:首先證明必要性。若剩余容量圖中存在增廣圈,且其擴充流量的費用為負,則可以在這個圈上擴充流量,總的費用下降,因此,必要性得證。

2.勢差最優性條件

定理4-2對每個點增加一個勢值π(i),i∈V,如果存在一組勢值使以下不等式成立

則網絡上的可行流為最小費用流,且可稱

的勢差。

證明:對于網絡上的可行流x*,若存在勢值使勢差c

成立,則網絡上任意增廣圈W上的勢差之和,即

不存在負值增廣圈。因此,根據負圈最優性條件,充分性得證。

3.互補松弛最優性條件

定理4-3一個網絡流方案x*是最小費用流的充分必要條件是,存在這么一組勢值使以下條件成立:

4.4.3兩個算法

1.負圈消除算法

根據負圈最優性條件,不含負圈的可行流即為最小費用流,因此,可以通過消除負圈的辦法,找到最小費用流。算法的步驟如下:

2.連續最短路算法

記網絡上的一個非飽和可行流x={xij|0≤xij≤uij},假設存在一組勢π,使其滿足勢差最優性條件。令d代表從某個點s在剩余容量圖上到其他點的最短路(邊(i,j)的長度用cπij表示),則以下性質成立: