最大流最小截问题属于一个组合优化问题,经过多年的研究,获得了大量的的研究成果。同时最大流最小截问题在大量实际生活中的网络都取得了广泛的应用,并且很多的的工期优化、流程控制等管理学科的问题以及图像处理中图割问题都可以转化最大流最小截问题模型求解。本文主要研究两种最大流最小截问题的求解算法及其应用,做出了如下成果:1.提出了一种改进最短增广链算法。在改进算法中删除了原网络中在增广过程中达到饱和弧。从而优化了算法中的构建剩余分层网络的过程。实验结果显示:改进算法的效率优于传统算法。2.提出了最大流最小截问题的遗传算法解法。在算法中主要设计了算法中个体编码解码方法、初始群体生成方法、适应度计算方法和选择交叉变异算子。实验结果表明:该算法能够在稳定计算最大流最小截问题,并且算法效率优于传统算法。3.介绍了最大流最小截问题在图割技术中的应用。描述了图割问题与最大流最小截问题模型之间的转换。最后通过实验,对图像进行分割。