2010运筹最大流.pptVIP

下载本文档

1
0
约小于1千字
约 19页
2018-05-16 发布于河南
举报
版权申诉

2010运筹最大流.ppt

1、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
4、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
5、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
6、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
7、VIP文档为合作方或网友上传，每下载1次，网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

2010运筹最大流

第五节网络的最大流 * ① ② ③ ④ ⑤ ⑥ 4 8 4 4 1 2 2 6 7 9 容量：在某时期内弧(i，j)上的最大通过能力。记为C (i，j)或Cij。在上图中，C12=4，C13＝8，C23＝4等，怎样安排运输方案，才能使在某一时期内从v1运到v6的物资最多，这样的问题就是最大流问题，网络中所有流起源于一个叫做发点的节点（源）所有的流终止于一个叫做收点的节点其余所有的节点叫做中间点（转运点）通过每一条弧的流只允许沿着弧的箭头方向流动目标是使得从发点到收点的总流量最大 1、流量：弧(i，j)的实际通过量，记为f (i，j)或f ij 可行流：如果f ij满足： 1.对于所有弧(i，j)有0≤f ij≤Cij 2.对于发点vs有： 3.对于收点vt有：则称流量集合｛f ij｝为网络的一个可行流，简记为 f , v称为可行流的流量或值，记为v(f). 4.对于中间点vm有： 2、最大流模型【定理】最大流量等于最小截集的截量。所有截量中此截量最小且等于最大流量，此截集称为最小截集。可行流是最大流当且仅当不存在发点到收点的增广链 *