第16次课-图与网络分析

第16次课--图与网络分析第一页，共77页。指派问题的解法：第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。（1）从系数矩阵的每行元素减去该行的最小元素；（2）再从所得的系数矩阵的每列元素中减去该列的最小元素。若该行（列）已有0元素，那就不必再减了。五.指派问题第二页，共77页。第二步：进行试指派，以寻求最优解经第一步变换后，系数矩阵中每行每列都有了0元素，但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵(xij)中元素为1，其余为0。这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素。若n较大时，就必须按一定的步骤去找。五.指派问题第三页，共77页。试指派步骤：（1）从只有一个0元素的行（列）开始，给这个0元素加圈，记作：◎。这表示对这行所代表的人，只有一种任务可指派，或这列所代表的任务，只有一人可指派。然后划去◎所在列（行）的其他0元素，记作：Φ。这表示这列所代表的任务已指派完，或这行所代表的人已指派。（2）给只有一个0元素的列（行）的0元素加圈，记作：◎，然后划去◎所行（列）的0元素，记作：Φ。（3）重复（1）（2）步骤，直到所有0元素都被圈出和划掉。五.指派问题第四页，共77页。（4） 若仍有没有加圈的0元素，且同行（列）的0元素至少有两个（表示对这人可以从两项任务中指派其一），这可用不同的方案去试探。从剩有0元素的最少行（列）开始，比较这行（列）各0元素所在列（行）中0元素的数目，选择0元素少的那列（行）的这个0元素加圈（表示选择性多的要“礼让”选择性小的。），然后划掉同行同列的其它0元素。可以反复进行。直到所有的0元素都已圈出和划掉为止。五.指派问题第五页，共77页。（5）若◎元素的数目m等于矩阵的阶数n，则这指派问题的最优解已得到。若m<n，则转入下一步，进一步处理。五.指派问题第六页，共77页。五.指派问题第三步：作最少的直线覆盖所有0元素。（以确定该系数矩阵中能找到最多的独立0元素个数）。为此按以下步骤进行：（1）对没有◎的行打√号；（2）对已打√号的行中所含元素的列打√号；（3）再对打有√号的列中所含◎元素的行打√号；（4）重复(2)(3)直到不能得到新打√行、列为止；（5） 对没有打√号的行划一横线，有打√号的列划一纵线。第七页，共77页。这就得到了覆盖所有0元素的最少直线数，设为l。若l<n说明必须再变换当前的系数矩阵，才能找到n个独立的0元素，为此转第四步。若l=n而m<n应回到第二步（4），另行试探。（说明还能找到更多的独立0元素）。五.指派问题第八页，共77页。第四步：对矩阵②进行变换，目的是增加0元素。（1）在没有被直线覆盖的部分中找出最小元素；（2）打√的行中各元素都减去这最小元素；（3）打√的列中各元素都加上这最小元素这样在保证原来0元素不变的情况下，得到一个新系数矩阵（它的最优解和原问题相同）。对新系数矩阵重新进行指派，若得到n个独立的0元素，则已得到最优解，否则回到第三步重复进行。五.指派问题第九页，共77页。以上讨论限于极小化的指派问题。对于极大化的问题，即求：maxz=ΣΣcijxij

。可令bij=M-cij，其中M是足够大的常数（如选cij中最大元素M即可），此时系数矩阵可变换为B=(bij)。五.指派问题第十页，共77页。第十章图与网络分析一、图的基本概念

二、树

三、最短路问题

四、网络最大流问题

五、最小费用最大流问题

六、中国邮递员问题第十一页，共77页。第一节图的基本概念你能从A出发，仅经过所有7座桥一次，回到A吗？从B,C,D出发呢？Koenigsberg七桥问题第十二页，共77页。第一节图的基本概念1.陆地用“点”表示2.桥用“连线”表示问题->模型抽象第十三页，共77页。第一节图的基本概念第十四页，共77页。第一节图的基本概念关键点：每个点和多少个边相连？能找到一条“回路”吗？

Euler’ssolution（1736）：如果这样的图要存在这样的回路，当且仅当图中无奇点！一笔画问题第十五页，共77页。第一节图的基本概念如何建设代价最小？这是典型的最小生成树问题。

第十六页，共77页。第一节图的基本概念第十七页，共77页。第一节图的基本概念经常用点及点与点的联线所构成的图去反映实际生活中某些对象之间的某个特定关系。通常用点代表研究的对象，用点与点的联线表示这两个对象之间有特定的关系。第十八页，共77页。第一节图的基本概念第十九页，共77页。

运筹学中的“图”模型同一名词在不同领域中的含义是有所区别的，一般大同小异，“小异”决定了术语的含义。运筹学中的“图”只关心图中点的个数以及点之间的关系。模型是现实问题一定程度的抽象，“图”是对事物以及事物之间关系的抽象。第一节图的基本概念第二十页，共77页。管理科学信息与计算机科学化学生物学社会学心理学……

图论得到了广泛应用第一节图的基本概念第二十一页，共77页。复杂网络的例子—澳大利亚堪培拉的社会关系网络A.S.Klovdahl第二十二页，共77页。复杂网络的例子—internet上部分IP地址连接结构示意图W.R.Cheswick第二十三页，共77页。复杂网络的例子—蛋白质相互作用网络结构示意图H.Jeong第二十四页，共77页。第一节图的基本概念1.1图的定义1.2图的一些基本概念1.3图的联通与割集第二十五页，共77页。第一节图的基本概念1.1图的定义第二十六页，共77页。第一节图的基本概念1.1图的定义第二十七页，共77页。第一节图的基本概念1.1图的定义第二十八页，共77页。第一节图的基本概念1.2图的一些基本概念最大次最小次第二十九页，共77页。第一节图的基本概念1.2图的一些基本概念第三十页，共77页。第一节图的基本概念1.2图的一些基本概念第三十一页，共77页。第一节图的基本概念1.2图的一些基本概念第三十二页，共77页。第一节图的基本概念1.2图的一些基本概念第三十三页，共77页。第一节图的基本概念1.2图的一些基本概念第三十四页，共77页。第一节图的基本概念1.2图的一些基本概念第三十五页，共77页。第一节图的基本概念1.2图的一些基本概念第三十六页，共77页。第一节图的基本概念1.2图的一些基本概念第三十七页，共77页。第一节图的基本概念1.2图的一些基本概念第三十八页，共77页。第一节图的基本概念练习题n个人参加象棋赛，已赛完n+1局，试证至少有一人赛完3局。1.2图的一些基本概念第三十九页，共77页。第一节图的基本概念1.2图的一些基本概念第四十页，共77页。第一节图的基本概念1.2图的一些基本概念第四十一页，共77页。第一节图的基本概念1.2图的一些基本概念第四十二页，共77页。第一节图的基本概念1.2图的一些基本概念第四十三页，共77页。第一节图的基本概念1.2图的一些基本概念第四十四页，共77页。第一节图的基本概念1.2图的一些基本概念第四十五页，共77页。第一节图的基本概念1.3图的连通与割集第四十六页，共77页。第一节图的基本概念1.3图的连通与割集第四十七页，共77页。第一节图的基本概念1.3图的连通与割集第四十八页，共77页。第一节图的基本概念若有则矛盾1.3图的连通与割集第四十九页，共77页。第一节图的基本概念1.3图的连通与割集第五十页，共77页。第一节图的基本概念1.3图的连通与割集第五十一页，共77页。第一节图的基本概念1.3图的连通与割集第五十二页，共77页。第一节图的基本概念1.3图的连通与割集第五十三页，共77页。第一节图的基本概念1.3图的连通与割集第五十四页，共77页。第二节树第五十五页，共77页。第二节树512340第五十六页，共77页。第二节树第五十七页，共77页。第二节树第五十八页，共77页。第二节树第五十九页，共77页。第二节树第六十页，共77页。第二节树第六十一页，共77页。第二节树第六十二页，共77页。第二节树第六十三页，共77页。第二节树第六十四页，共77页。第二节树第六十五页，共77页。第二节树第六十六页，共77页。第二节树第六十七页，共77页。第二节树

最小支撑树公路网设计电话网（互联网）设计第六十八页，共77页。第二节树

最小支撑树公路网设计电话网（互联网）设计第六十九页，共77页。21457323542145732354第二节树第七十页，共77页。第二节树第七十一页，共77页。第二节树第七十二页，共77页。避圈法：开始选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈，直至选足|V|-1条边为止。最小支撑树214573