【正文】 街道兩側(cè)，現(xiàn)計劃在某些路口安置消防設(shè)施，使得每一街道的居民在必要時都可在該街道的某一路口得到設(shè)施利用。問題：如何利用盡可能少的設(shè)施達(dá)到以上目標(biāo)？消防設(shè)施的設(shè)置問題：若干條街道構(gòu)成一個居民小區(qū)，居民樓分布在街道兩側(cè)，現(xiàn)計劃在某些路口安置消防設(shè)施，使得每一街道的居民在必要時都可在該街道的某一路口得到設(shè)施利用。問題：如何利用盡可能少的設(shè)施達(dá)到以上目標(biāo)？一． 模型建立以所有路口作為頂點集，在有街道直接連接的相鄰路口連邊，構(gòu)成一圖，不妨以記邊集，表示所有的街道，則所關(guān)心問題歸結(jié)為求頂點集的一個包含頂點數(shù)最少的子集，使得對，均，滿足關(guān)聯(lián)。l 圖的覆蓋、最小覆蓋、覆蓋數(shù)二． 模型求解（算法）l 性質(zhì)： 是圖的一個覆蓋的關(guān)聯(lián)矩陣中的各頂點對應(yīng)的行形成的子矩陣，每列至少存在一個元素。l 一個（貪婪）算法（頂點度數(shù)大者優(yōu)先考慮）：（1） 設(shè)是圖的關(guān)聯(lián)矩陣，；（2） ，若，輸出，停；（3） 選，，修正，對，若，令；轉(zhuǎn)（2）。例、設(shè)某街區(qū)按照前面提及的思路可以抽象為如下無向圖下面組圖說明了如上（貪婪）算法的具體實現(xiàn)： 即為該算例的一個覆蓋，當(dāng)然我們不難發(fā)現(xiàn)它也是該算例的最小覆蓋，進(jìn)而該算例的覆蓋數(shù)為3。l 如下算例表明，以上所給算法非最優(yōu)：（算法結(jié)果：；最優(yōu)結(jié)果：）問題二：監(jiān)獄看守的設(shè)置 一座監(jiān)獄的幾間牢室有通道相連，監(jiān)獄的看守要設(shè)在通過道路能直接監(jiān)視到所有牢室的地方。問題，如何設(shè)置盡可能少的哨崗達(dá)到以上目標(biāo)？監(jiān)獄看守的設(shè)置問題：一座監(jiān)獄的幾間牢室有通道相連，監(jiān)獄的看守要設(shè)在通過道路能直接監(jiān)視到所有牢室的地方。問題，如何設(shè)置盡可能少的哨崗達(dá)到以上目標(biāo)？一． 模型建立以所有牢室作為頂點集，在有通道相連接的牢室間連邊，構(gòu)成一圖，不妨以記邊集，表示所有的通道，則所關(guān)心問題歸結(jié)為求頂點集的一個包含頂點數(shù)最少的子集，使得對，均，滿足鄰接。l 圖的控制集、最小控制集、控制數(shù)二．模型求解（算法）l 性質(zhì)： 是圖的一個控制集的鄰接矩陣中的各頂點對應(yīng)的行形成的子矩陣，每列至少存在一個元素。l 一個（貪婪）算法（頂點度數(shù)大者優(yōu)先考慮）：(1) 設(shè)是圖的鄰接矩陣，,；(2) ，若，,輸出，停；(3) 選，，；修正，對，若，令，；轉(zhuǎn)（2）。l 以上算法非最優(yōu)，可以如下算例加以驗證：167。 循環(huán)比賽的排名問題問題：支球隊參加循環(huán)比賽，兩兩交鋒，一場決勝，不容平局，“0、1”打分。如何排名？1． 競賽圖：每對頂點之間有且只有一條有向邊相連的有向圖；有向邊指向負(fù)方。2． 路徑與完全路徑：稱有向圖的一個頂點序列為圖的一條步長為的路徑，若滿足：對，均有；若還滿足，則稱之為圖的一條步長為的回（或閉）路徑。而若頂點集的一個全排列構(gòu)成圖的一條路徑，也稱之為圖的一條完全路徑。l 圖1中：、l 子路徑、閉的完全路徑3． 定理：任一階競賽圖都存在完全路徑。證明（數(shù)學(xué)歸納法）：：時，如圖30，命題真；：設(shè)時命題真；：當(dāng)時，設(shè)為頂點集，記，為圖關(guān)于的生成子圖；由歸納假設(shè)，在中存在完全路徑，不失一般性，設(shè)為中的一條完全路徑，考慮頂點與的鄰接關(guān)系，有如下三種情形：圖31：為中的一條完全路徑；圖32：為中的一條完全路徑圖33：為中的一條完全路徑。4． 定理：存在唯一完全路徑的階競賽圖在同構(gòu)的意義下唯一。進(jìn)一步講，若設(shè)為中的唯一的一條完全路徑，則。證明（數(shù)學(xué)歸納法）：：時，如圖31，命題真； ：設(shè)時命題真；：當(dāng)時，設(shè)為頂點集，不妨設(shè)為中的唯一的一條完全路徑；記，為圖關(guān)于的生成子圖；此時為中的唯一的一條完全路徑，否則，由（）的論證可得不同于的中的另一條完全路徑，這與題設(shè)矛盾；以下只須證明負(fù)于任意：（反證）設(shè)勝某，如下圖，可以找到一條不同于的中的另一條完全路徑，這同樣與題設(shè)矛盾。l 這一性質(zhì)表明，利用完全路徑法進(jìn)行競賽圖排名是不可行（完善）的。5． 簡單積分法：簡單積分法與完全路徑法排名在完全路徑唯一的情形下二者是一致的。以下試圖通過低階的競賽圖說明簡單積分法的缺陷：l 在以上組圖的每一幅圖的下方所標(biāo)示向量既表示該圖各頂點的簡單積分，同時，對于4階競賽圖，在同構(gòu)的意義下可以作為該類圖的標(biāo)識。我們通過簡單分析發(fā)現(xiàn)圖按照簡單積分的方法對各頂點排序是不合適的：假設(shè)不然（即簡單積分是適用的），、同時；這時看，按照簡單積分法二者均只得1分，但其份量不同，所得1分為其勝，按照簡單積分法，為一弱隊；但所得1分為其勝，按照簡單積分法，為一強(qiáng)隊——因此，通常認(rèn)為強(qiáng)于。類似分析，可以得出強(qiáng)于。l 盡管在以上組圖中，除了圖外，我們看不出簡單積分法的缺陷，但隨著競賽圖階數(shù)的增加，簡單積分的局限將尤為凸顯。6． 雙向連通圖：稱有向圖為雙向連通的，若對任意兩個不同頂點，在該有向圖中既有從頂點到頂點的有向路徑，也有從頂點到頂點的有向路徑。7． 雙向連通圖的鄰接矩陣為素陣：即存在整數(shù)，使得。8． PerronFrobenius定理：素陣的最大特征根為正單根，對應(yīng)正特征向量，且有（為所有分量均為1的維向量，也可以被表示為）。l 對以上定理的理解可以參見層次分析法一章中對正互反矩陣性質(zhì)的討論。9． 對于雙向連通的競賽圖，可以計算其鄰接矩陣的最大特征根以及相應(yīng)的正特征向量，按照該特征向量分量的數(shù)值大小對各個頂點（參賽隊）排名。 下面是一個雙向連通的四階競賽圖，通過前面的討論，該算例不論完全路徑法還是簡單積分法均不適宜，我們分別采用與對之進(jìn)行分析考察——不難發(fā)現(xiàn)，的分量表示以相應(yīng)頂點為起點產(chǎn)生的步長為的路徑數(shù)，而的分量則表示以相應(yīng)頂點為起點產(chǎn)生的步長不超過的路徑數(shù)。如下圖，從不同頂點（作為最底層）出發(fā)，只要存在以該頂點為起點的有向邊，則向上生長出枝杈，將響應(yīng)邊的終點畫在第二層，在以第二層上的點為基點向第三層生長，如此直到無窮，將最終得到四棵“參天大樹”，直觀上，的分量為表示相應(yīng)頂點生長出的“樹”介于第層與第層之間的枝杈數(shù)，而的分量為表示相應(yīng)頂點生長出的“樹”在第層下方部分的枝杈數(shù)。顯然，一個“有實力的頂點（參賽隊）”對應(yīng)的“樹”應(yīng)當(dāng)更為粗壯。 按照PerronFrobenius定理，只要足夠大，可以將作為實力向量來對各個頂點排序，通過具體計算，，事實上反映出完全相同的結(jié)果——這正是PerronFrobenius定理在競賽圖排名中的應(yīng)用。10． 從直觀上講，以作為一個實力向量用于競賽圖排名將更為適宜，當(dāng)然我們在這里愿意強(qiáng)調(diào)具有如下的優(yōu)點：l 它并不只局限于雙向連通的競賽圖；l 從對競賽圖的分析看，計算需要一直計算到，之后從排名的角度講，的值才算穩(wěn)定下來；而的計算在時就具備如上提及的特點。l 你能從中發(fā)掘有關(guān)值更多的優(yōu)點嗎？嘗試著準(zhǔn)確表述你的發(fā)現(xiàn)或猜想，能從理論上加以論證嗎？167。 紅綠燈調(diào)節(jié)問題：圖1所示的十字路口共有六條車道，其中是4條直道，是2條左轉(zhuǎn)彎道，每條車道設(shè)有紅綠燈，制定其調(diào)節(jié)方案。1． 相容圖與區(qū)間圖相容圖：用圖中的頂點表示交通流，當(dāng)兩條交通流相容時將代表交通流的兩頂點連接而得到的圖。區(qū)間圖：稱圖G=（V，E）為區(qū)間圖，若存在從頂點到區(qū)間的對應(yīng)關(guān)系，使得對于任意的，有。2． 可行調(diào)節(jié)：通過刪除（非）區(qū)間圖某些邊，構(gòu)造一個區(qū)間圖子圖。3． 有效性調(diào)節(jié)：對于給定的子圖所對應(yīng)的交通流，設(shè)計有效的紅綠燈調(diào)節(jié)程序（比方使在一個紅綠燈調(diào)節(jié)周期中總的綠燈時間最長），盡可能利于路口的車輛通行。4． 在要求滿足條件1）一個紅綠燈調(diào)節(jié)周期=60秒；2） 四個時段；3） 六個車流流量；4）每一車流連續(xù)通行時間不少于10秒，可得如下線性規(guī)劃模型：第十章 線性規(guī)劃建模167。 線性規(guī)劃引例（生產(chǎn)規(guī)劃問題）：某廠利用a、b、c三種原料生產(chǎn)A、B、C三種產(chǎn)品，已知生產(chǎn)每種產(chǎn)品在消耗原料方面的各項技術(shù)條件和單位產(chǎn)品的利潤，以及可利用的各種原料的量（具體數(shù)據(jù)如下表），試制訂適當(dāng)?shù)纳a(chǎn)規(guī)劃使得該廠的總的利潤最大。 產(chǎn)品原料生產(chǎn)每單位產(chǎn)品所消耗的原料現(xiàn)有原料的量ABCa34260b21240c13280單位產(chǎn)品利潤243l 以、分別表示生產(chǎn)A、B、C三種產(chǎn)品的量，稱之為決策變量。l 目標(biāo)函數(shù)：利潤最大化、成本最小化，表現(xiàn)為決策變量的一個函數(shù)；l 約束條件：資源、工期等，表現(xiàn)為決策變量的一些等式或不等式。1． 線性規(guī)劃問題：在滿足由一些線性等式或不等式組成的約束條件下，求決策變量的一組具體取值，使得一個線性目標(biāo)函數(shù)實現(xiàn)最優(yōu)（大或?。┗? l 決策變量；l 、（， ）均為常數(shù)；l 整數(shù)規(guī)劃：決策變量限取整數(shù)值的最優(yōu)化問題；l 非線性規(guī)劃：目標(biāo)函數(shù)或存在約束條件函數(shù)是決策變量的非線性函數(shù)的最優(yōu)化問題2． 線性規(guī)劃方法建模：決策變量的提取，目標(biāo)函數(shù)的合理構(gòu)造，約束條件的理清。例（紙張的切割問題）：設(shè)有60個單位長的標(biāo)準(zhǔn)玻璃紙，現(xiàn)需將其裁剪為三種小規(guī)格（28，20，15）的紙張，市場對三種小規(guī)格玻璃紙的需求量（30，60，80）卷，問題：用盡可能少的標(biāo)準(zhǔn)玻璃紙，通過適當(dāng)?shù)牟眉舴绞揭詽M足市場的需求。3． 線性規(guī)劃的標(biāo)準(zhǔn)型：稱如下形式的線性規(guī)劃問題為具有標(biāo)準(zhǔn)型的線性規(guī)劃l 稱矩陣為以上具有標(biāo)準(zhǔn)型的線性規(guī)劃問題的單純形表，其中，l 若記，則以上具有標(biāo)準(zhǔn)型的線性規(guī)劃問題可記為 4． 所有線性規(guī)劃問題可以標(biāo)準(zhǔn)型化：（1） 。（2） 且；（3） 且；（4） 等價于以取代，則，等價于以取代，則；（5） ，即無取值限制,這等價于以取代，且附加條件；稱（2）、（3）中的分別為剩余、松弛變量.5． 線性規(guī)劃的典型形l 所有線性規(guī)劃問題均可以典型形化：（1） ；（2） 且6． 線性規(guī)劃的幾何特征設(shè) 滿足線性規(guī)劃問題全部約束條件，則稱之為此線性規(guī)劃問題的一個可行解；稱由所有可行解組成的集合為該線性規(guī)劃問題的可行域，用表示；使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解稱為此線性規(guī)劃問題的一個最優(yōu)解；稱最優(yōu)解的目標(biāo)函數(shù)值為該線性規(guī)劃問題的最優(yōu)值。（1） 可行域為凸集：幾個典型的凸集（區(qū)域）幾個典型的非凸集（區(qū)域）（2） 若線性規(guī)劃有最優(yōu)解，則必在可行域邊界達(dá)到；若可行域為有界閉集，則最優(yōu)解必在的某一頂點達(dá)到。例 . 求解 l 圖解法: 上圖中紅色區(qū)域為該線性規(guī)劃的可行域，一條（藍(lán)色）有向線段表示目標(biāo)函數(shù)的梯度向量，幾條藍(lán)色平行線表示目標(biāo)函數(shù)的一簇等值線，考慮問題是求目標(biāo)函數(shù)的最大值，從直觀上不難發(fā)現(xiàn)可行域右方的頂點為該問題的解。（3） 線性規(guī)劃解的存在性（考慮典型形）i . 最優(yōu)解存在且唯一的情形:左圖對應(yīng)可行域為一有界閉集的情形，左圖為一無界集ii. 最優(yōu)解存在但不唯一；左圖對應(yīng)可行域為一有界閉集的情形，左圖為一無界集iii. ，可行解存在但目標(biāo)函數(shù)值在內(nèi)無下界；這一情形只發(fā)生在可行域為一無界區(qū)域的時候iv. ，可行解不存在。1l 滿足約束條件的任一均為其解；5． 改進(jìn)的線性規(guī)劃模型：一個合理的調(diào)節(jié)方案應(yīng)當(dāng)使為每一車流分配的有效通行時間與它的實際流量相適應(yīng)，簡言之，那些相對繁忙的車流應(yīng)當(dāng)有更為充足的通行時間，不妨設(shè)表示六個車流在單位時間內(nèi)的車流量，則得如下的改進(jìn)模型：11l 適當(dāng)選取，使得，不難得到是相應(yīng)的最優(yōu)解；但若進(jìn)一步設(shè)想，適當(dāng)選取的另外一組值，使得，不難得到依舊是改變了的問題的解——這一現(xiàn)象事實上暴露了線性模型在處理紅綠燈調(diào)節(jié)問題的缺陷，即盡管在改進(jìn)模型是在考慮了各個交通流流量的差異，但由于線性模型的特點使得這一改進(jìn)模型更為周全的考慮幾乎沒有發(fā)揮任何作用。它是在以滿足大多數(shù)車流最低通行時間要求為代價，將剩余的時間極端的滿足車流最繁忙的某一車流，而不管這種相對繁忙的具體程度。6． 構(gòu)造一個合理的目標(biāo)函數(shù)：前面的論述說明，用最優(yōu)化方法解決一個實際應(yīng)用問題時，目標(biāo)函數(shù)的選擇是需要仔細(xì)推敲的。下面就紅綠燈調(diào)節(jié)問題給出可供選擇的幾個目標(biāo)函數(shù)形式，當(dāng)然我們?nèi)糇屑?xì)分析，還會發(fā)現(xiàn)其中第一個目標(biāo)函數(shù)存在的缺陷：（1）（其中、你可以借助幾何直觀來思考該目標(biāo)函數(shù)的意義）；（2）167。 線性規(guī)劃的求解—單純形法l 本節(jié)討論具有標(biāo)準(zhǔn)型形式的線性規(guī)劃:這里，目標(biāo)函數(shù)表達(dá)式中較一些流行運籌學(xué)教材多了常數(shù)項 , 記 ，表示 維列向量，而以 表示 維向量空間，余者：， ， ；l 具有標(biāo)準(zhǔn)型形式的線性規(guī)劃模型可簡記為：，顯然它與分塊矩陣 一一對應(yīng)，稱 為線性規(guī)劃 的單純形表。1．線性規(guī)劃的等價：稱二線性規(guī)劃 與 等價，若它們具有相同的可行域，且對任一可行解均有相同的目標(biāo)函數(shù)值，即滿足： , 其中 、分別為線性規(guī)劃與 的可行域； 對任意 均有 。2． 設(shè) 為 階可逆方陣，為 維列向量，則線性規(guī)劃與線性規(guī)劃 等價。證明： 記 、分別為線性規(guī)劃 與 的可行域，對任意 ，即 且 ，因為 為 階可逆方陣，所以等價于 且 ，即且 ，進(jìn)而 ；反之亦然，故。 對任意 , 因為, 所以, 即線性規(guī)劃 與 在可行解 有相同的目標(biāo)函數(shù)值。 綜合 、, 定理得證。l 該定理表明求解具有標(biāo)準(zhǔn)型形式的線性規(guī)劃, 可以對它的單純形表 作如下的初等行變換: 對它的前 行 作任意的初等行變換, 而對最后一行 可以加上前 左乘一可逆方陣 。我們也將滿足這樣特點的初等變換稱為線性規(guī)劃的等價變換.3．幾個簡單的具有標(biāo)準(zhǔn)型形式的線性規(guī)劃例：