《算法合集之《浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》.ppt

浅谈信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用  浙江省杭州第二中学 李宇骞 引子 最优匹配 网络流 最短路 资源优化配置问题 最佳物资供给问题 多物网络流 引子 资源优化配置问题 最佳物资供给问题 多物网络流 引子 无论作为替代解法或者唯一解法 概览 定义与简单应用 单纯形法简介 实现 定义 线性规划：在满足一些线性等式或者不等式的条件下，最优化一个线性函数。 x1+x2+x3+x4 -2x1+8x2+0x3+10x4 = 50 x1 =0 x2=4 x1+5=x2 多物网络流 多物网络流 k个物品，那么对每个边，设k个变量，分别代表该物品在此边上的流量。 最优化的目标函数：无——只求可行解 约束： 所有物品流量和 不超过 边容量限制 每个物品的流都 满足 流量平衡条件 每个物品总流量 达到 它的要求流量 单纯形法 标准形式——统一问题的描述 主程序——调整法 松弛形式——方便程序中点的表示 转轴操作——最核心的调整操作 单纯形法 标准形式(Standard form) 最大化 x1+x2+x3+x4 满足： x1+2x2+3x3 = 3 x4 = 5 x1,x2,x3,x4 = 0 单纯形法 标准形式(Standard form) 单纯形法 标准形式(Standard form) 最大化 共n+m个约束，除了n个变量的非负限制外，还满足m个约束，第j个约束为 单纯形法 形象的理解 单纯形法 主程序 单纯形法 单纯形法 单纯形法 松弛形式（Slack form) 将n+m个不等式和n+m个变量一一对应 单纯形法 松弛形式（Slack form） 单纯形法 松弛形式（Slack form） 单纯形法 转轴操作（Pivot） 单纯形法 时间复杂度 最多有 个松弛形式 实现 细节决定成败 系数矩阵的表示——以退为进 初始化中X0的处理——被忽略的关键 贪心的优化——小改动带来速度上的大飞跃 实现 编程复杂度 200行 110行 实现 优化 贪心：每一次调整使目标函数变得尽量大！ 普通的最优化过程——25行 加优化以后的过程——35行 测试 200个变量、200个约束 测试 300个变量、200个约束 测试 300个变量、300个约束 总结 总结 优美的单纯形法 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 最优匹配 网络流 最短路 有更好的特殊解法 只有线性规划 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 构造模型 解线性规划 一劳永逸 复杂 因题而异 简单 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 构造模型 解线性规划 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 源点1 源点2 汇点1 汇点2 要求流量 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty