第16次課-圖與網(wǎng)絡(luò)分析

第16次課--圖與網(wǎng)絡(luò)分析第一頁，共77頁。指派問題的解法：第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。（1）從系數(shù)矩陣的每行元素減去該行的最小元素；（2）再從所得的系數(shù)矩陣的每列元素中減去該列的最小元素。若該行（列）已有0元素，那就不必再減了。五.指派問題第二頁，共77頁。第二步：進行試指派，以尋求最優(yōu)解經(jīng)第一步變換后，系數(shù)矩陣中每行每列都有了0元素，但需找出n個獨立的0元素。若能找出，就以這些獨立0元素對應(yīng)解矩陣(xij)中元素為1，其余為0。這就得到最優(yōu)解。當n較小時，可用觀察法、試探法去找出n個獨立0元素。若n較大時，就必須按一定的步驟去找。五.指派問題第三頁，共77頁。試指派步驟：（1）從只有一個0元素的行（列）開始，給這個0元素加圈，記作：◎。這表示對這行所代表的人，只有一種任務(wù)可指派，或這列所代表的任務(wù)，只有一人可指派。然后劃去◎所在列（行）的其他0元素，記作：Φ。這表示這列所代表的任務(wù)已指派完，或這行所代表的人已指派。（2）給只有一個0元素的列（行）的0元素加圈，記作：◎，然后劃去◎所行（列）的0元素，記作：Φ。（3）重復(fù)（1）（2）步驟，直到所有0元素都被圈出和劃掉。五.指派問題第四頁，共77頁。（4） 若仍有沒有加圈的0元素，且同行（列）的0元素至少有兩個（表示對這人可以從兩項任務(wù)中指派其一），這可用不同的方案去試探。從剩有0元素的最少行（列）開始，比較這行（列）各0元素所在列（行）中0元素的數(shù)目，選擇0元素少的那列（行）的這個0元素加圈（表示選擇性多的要“禮讓”選擇性小的。），然后劃掉同行同列的其它0元素?？梢苑磸?fù)進行。直到所有的0元素都已圈出和劃掉為止。五.指派問題第五頁，共77頁。（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，則這指派問題的最優(yōu)解已得到。若m<n，則轉(zhuǎn)入下一步，進一步處理。五.指派問題第六頁，共77頁。五.指派問題第三步：作最少的直線覆蓋所有0元素。（以確定該系數(shù)矩陣中能找到最多的獨立0元素個數(shù)）。為此按以下步驟進行：（1）對沒有◎的行打√號；（2）對已打√號的行中所含元素的列打√號；（3）再對打有√號的列中所含◎元素的行打√號；（4）重復(fù)(2)(3)直到不能得到新打√行、列為止；（5） 對沒有打√號的行劃一橫線，有打√號的列劃一縱線。第七頁，共77頁。這就得到了覆蓋所有0元素的最少直線數(shù)，設(shè)為l。若l<n說明必須再變換當前的系數(shù)矩陣，才能找到n個獨立的0元素，為此轉(zhuǎn)第四步。若l=n而m<n應(yīng)回到第二步（4），另行試探。（說明還能找到更多的獨立0元素）。五.指派問題第八頁，共77頁。第四步：對矩陣②進行變換，目的是增加0元素。（1）在沒有被直線覆蓋的部分中找出最小元素；（2）打√的行中各元素都減去這最小元素；（3）打√的列中各元素都加上這最小元素這樣在保證原來0元素不變的情況下，得到一個新系數(shù)矩陣（它的最優(yōu)解和原問題相同）。對新系數(shù)矩陣重新進行指派，若得到n個獨立的0元素，則已得到最優(yōu)解，否則回到第三步重復(fù)進行。五.指派問題第九頁，共77頁。以上討論限于極小化的指派問題。對于極大化的問題，即求：maxz=ΣΣcijxij

?？闪頱ij=M-cij，其中M是足夠大的常數(shù)（如選cij中最大元素M即可），此時系數(shù)矩陣可變換為B=(bij)。五.指派問題第十頁，共77頁。第十章圖與網(wǎng)絡(luò)分析一、圖的基本概念

二、樹

三、最短路問題

四、網(wǎng)絡(luò)最大流問題

五、最小費用最大流問題

六、中國郵遞員問題第十一頁，共77頁。第一節(jié)圖的基本概念你能從A出發(fā)，僅經(jīng)過所有7座橋一次，回到A嗎？從B,C,D出發(fā)呢？Koenigsberg七橋問題第十二頁，共77頁。第一節(jié)圖的基本概念1.陸地用“點”表示2.橋用“連線”表示問題->模型抽象第十三頁，共77頁。第一節(jié)圖的基本概念第十四頁，共77頁。第一節(jié)圖的基本概念關(guān)鍵點：每個點和多少個邊相連？能找到一條“回路”嗎？

Euler’ssolution（1736）：如果這樣的圖要存在這樣的回路，當且僅當圖中無奇點！一筆畫問題第十五頁，共77頁。第一節(jié)圖的基本概念如何建設(shè)代價最??？這是典型的最小生成樹問題。

第十六頁，共77頁。第一節(jié)圖的基本概念第十七頁，共77頁。第一節(jié)圖的基本概念經(jīng)常用點及點與點的聯(lián)線所構(gòu)成的圖去反映實際生活中某些對象之間的某個特定關(guān)系。通常用點代表研究的對象，用點與點的聯(lián)線表示這兩個對象之間有特定的關(guān)系。第十八頁，共77頁。第一節(jié)圖的基本概念第十九頁，共77頁。

運籌學中的“圖”模型同一名詞在不同領(lǐng)域中的含義是有所區(qū)別的，一般大同小異，“小異”決定了術(shù)語的含義。運籌學中的“圖”只關(guān)心圖中點的個數(shù)以及點之間的關(guān)系。模型是現(xiàn)實問題一定程度的抽象，“圖”是對事物以及事物之間關(guān)系的抽象。第一節(jié)圖的基本概念第二十頁，共77頁。管理科學信息與計算機科學化學生物學社會學心理學……

圖論得到了廣泛應(yīng)用第一節(jié)圖的基本概念第二十一頁，共77頁。復(fù)雜網(wǎng)絡(luò)的例子—澳大利亞堪培拉的社會關(guān)系網(wǎng)絡(luò)A.S.Klovdahl第二十二頁，共77頁。復(fù)雜網(wǎng)絡(luò)的例子—internet上部分IP地址連接結(jié)構(gòu)示意圖W.R.Cheswick第二十三頁，共77頁。復(fù)雜網(wǎng)絡(luò)的例子—蛋白質(zhì)相互作用網(wǎng)絡(luò)結(jié)構(gòu)示意圖H.Jeong第二十四頁，共77頁。第一節(jié)圖的基本概念1.1圖的定義1.2圖的一些基本概念1.3圖的聯(lián)通與割集第二十五頁，共77頁。第一節(jié)圖的基本概念1.1圖的定義第二十六頁，共77頁。第一節(jié)圖的基本概念1.1圖的定義第二十七頁，共77頁。第一節(jié)圖的基本概念1.1圖的定義第二十八頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念最大次最小次第二十九頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十一頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十二頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十三頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十四頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十五頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十六頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十七頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第三十八頁，共77頁。第一節(jié)圖的基本概念練習題n個人參加象棋賽，已賽完n+1局，試證至少有一人賽完3局。1.2圖的一些基本概念第三十九頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第四十頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第四十一頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第四十二頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第四十三頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第四十四頁，共77頁。第一節(jié)圖的基本概念1.2圖的一些基本概念第四十五頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第四十六頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第四十七頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第四十八頁，共77頁。第一節(jié)圖的基本概念若有則矛盾1.3圖的連通與割集第四十九頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第五十頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第五十一頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第五十二頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第五十三頁，共77頁。第一節(jié)圖的基本概念1.3圖的連通與割集第五十四頁，共77頁。第二節(jié)樹第五十五頁，共77頁。第二節(jié)樹512340第五十六頁，共77頁。第二節(jié)樹第五十七頁，共77頁。第二節(jié)樹第五十八頁，共77頁。第二節(jié)樹第五十九頁，共77頁。第二節(jié)樹第六十頁，共77頁。第二節(jié)樹第六十一頁，共77頁。第二節(jié)樹第六十二頁，共77頁。第二節(jié)樹第六十三頁，共77頁。第二節(jié)樹第六十四頁，共77頁。第二節(jié)樹第六十五頁，共77頁。第二節(jié)樹第六十六頁，共77頁。第二節(jié)樹第六十七頁，共77頁。第二節(jié)樹

最小支撐樹公路網(wǎng)設(shè)計電話網(wǎng)（互聯(lián)網(wǎng)）設(shè)計第六十八頁，共77頁。第二節(jié)樹

最小支撐樹公路網(wǎng)設(shè)計電話網(wǎng)（互聯(lián)網(wǎng)）設(shè)計第六十九頁，共77頁。21457323542145732354第二節(jié)樹第七十頁，共77頁。第二節(jié)樹第七十一頁，共77頁。第二節(jié)樹第七十二頁，共77頁。避圈法：開始選一條最小權(quán)的邊，以后每一步中，總從未被選取的邊中選一條權(quán)最小的邊，并使之與已選取的邊不構(gòu)成圈，直至選足|V|-1條邊為止。最小支撐樹214573