第7章線性規(guī)劃問題與網(wǎng)絡(luò)流

7.1概述在生產(chǎn)管理和經(jīng)營活動中，經(jīng)常會遇到兩類問題：一類是如何合理地使用現(xiàn)有的勞動力、設(shè)備、資金等資源，以得到最大的收益；另一類是為了達到一定的目標，應(yīng)該如何組織生產(chǎn)，或管理安排工藝流程使得所消耗的資源最少；P211如：配載問題：某種交通工具的容積和載重一定(約束)，運輸若干物資，如何運輸可以使得運輸工具裝載的物資最多(目標函數(shù))。

物資調(diào)運問題：

將這些約束條件和目標函數(shù)都是決策變量的線性函數(shù)的規(guī)劃問題稱為線性規(guī)劃問題。第7章線性規(guī)劃問題與網(wǎng)絡(luò)流17.1.1一般線性規(guī)劃問題的描述為了解決這類問題：首先，需要確定問題的決策變量；然后，確定問題的目標，并將目標表示為決策變量的線性函數(shù);最后，找出問題所有約束，并將其表示為決策變量的線性方程.P214:變量滿足約束條件的一組值稱為線性規(guī)劃問題的一個可行解。使目標函數(shù)取得極值的可行解稱為最優(yōu)解。在最優(yōu)解處目標函數(shù)的值稱為最優(yōu)值。2線性規(guī)劃問題一般用單純形算法求解；

單純形算法是由1947年喬治.丹捷格發(fā)明的一種求解線性規(guī)劃問題的方法。

例題1解：將線性規(guī)劃問題轉(zhuǎn)化為約束標準型如下：

令3由約束標準形式可知：x1,x5,x6是基本變量，x2,x3,x4是非基本變量，建立初始單純形表如表7-2所示。由此可得，基本可行解為X(0)=（7,0,0,0,12,10），z’=0。由表7-2可知：x3為入基變量，x5為離基變量，根據(jù)迭代公式得出如表7-3所示的單純形表3。由此可得，基本可行解為X(1)=（10,0,3,0,0,1）,z’=94由表7-3可知：x2為入基變量，x1為離基變量，根據(jù)迭代公式迭代得如表7-4所示的單純形表4。由此可得，基本可行解為X(2)=（0,4,5,0,0,11）,z’=11。同時，由表7-4可知，所有檢驗數(shù)均小于等于0，故X(2)=（0,4,5,0,0,11）為該線性規(guī)劃問題的唯一最優(yōu)解，其最優(yōu)值z=-11。練習：5舉例：

設(shè)有一個水管網(wǎng)絡(luò)該網(wǎng)絡(luò)有進水口與出水口，每個管道的粗細作為該管道的權(quán)值，反映該管道的最大流量；則在該水流網(wǎng)絡(luò)中，進一步加大流量由于受到水管網(wǎng)絡(luò)的限制，加到一定流量后，再也加不進去，這就是此水管網(wǎng)絡(luò)的最大流量。7.2最大網(wǎng)絡(luò)流問題61基本概念和術(shù)語

（1）網(wǎng)絡(luò)G是一個簡單有向圖，G=(V,E)，V={1，2，…，n}。在V中指定一個頂點s，稱為源和另一個頂點t，稱為匯。有向圖G的每一條邊(v,w)∈E，對應(yīng)有一個值cap(v,w)≥0，稱為邊的容量。這樣的有向圖G稱作一個網(wǎng)絡(luò)。（2）網(wǎng)絡(luò)流網(wǎng)絡(luò)上的流是定義在網(wǎng)絡(luò)的邊集合E上的一個非負函數(shù)flow={flow(v,w)}，并稱flow(v,w)為邊(v,w)上的流量。7（3）最大流最大流問題即求網(wǎng)絡(luò)G的一個可行流flow，使其流量f達到最大。即flow滿足：0≤flow(v,w)≤cap(v,w)，(v,w)∈E；且8（5）增廣路設(shè)flow是一個可行流，P是從s到t的一條路，若P滿足下列條件：在P的所有向前邊(v,w)上，flow(v,w)<cap(v,w)，即P+中的每一條邊都是非飽和邊；在P的所有向后邊(v,w)上，flow(v,w)>0，即P-中的每一條邊都是非零流。則稱P為關(guān)于可行流flow的一條可增廣路。對于最大網(wǎng)絡(luò)流問題一般使用一種叫增廣路算法來求解。97.2.2增廣路算法增廣路定理：設(shè)flow是網(wǎng)絡(luò)G的一個可行流，如果不存在從s到t關(guān)于flow的可增廣路P，則flow是G的一個最大流.增廣路算法（1）初始化為0流（2）找關(guān)于當前可行流的可增廣路，若找到，轉(zhuǎn)3；否則，當前可行流為網(wǎng)絡(luò)的最大流。（3）沿增廣路增流。因此，增廣路算法主要包括兩個過程：找增廣路和沿增廣路增流。對于最大網(wǎng)絡(luò)流問題一般使用一種叫增廣路算法來求解。10可采用標號法找可增廣路。對網(wǎng)絡(luò)中的每個節(jié)點j，其標號包括兩部分信息（pred(j)，maxl(j)），其中pred(j)表示節(jié)點j在可能的增廣路中的前一個節(jié)點，maxl(j)表示沿該可能的增廣路到節(jié)點j為止可以增加的最大流量。具體步驟為：步驟1：源點s的標號為（0，+∞）。步驟2：從已標號而未檢查的點v出發(fā)，對于邊<v，w>，如果flow(v，w)<cap(v，w)，則w的標號為(v，maxl(w))，maxl(w)=min{maxl(v),cap(v，w)-flow(v，w)}；對于邊<w，v>，flow(w，v)>0，則w的標號為(-v，maxl(w))，maxl(w)=min{maxl(v)，flow(w，v)}。步驟3：不斷重復(fù)步驟2，直到已經(jīng)不存在已標號未檢查的點或標到了匯點結(jié)束。如果不存在已標號未檢查的點，則說明不存在關(guān)于當前可行流的可增廣路，當前流就是最大流。如果標到了匯點，則找到了一條可增廣路，需要沿著該可增廣路進行增流，轉(zhuǎn)過程（2）。沿增廣路增流具體方法

11例題用增廣路算法找出如下圖所示的網(wǎng)絡(luò)及可行流的最大流，其中，頂點1為源點，頂點6為匯點，邊上的權(quán)為（cap，flow）12標號法找增廣路

沿著增廣路增流

13標號法找增廣路

沿著增廣路