算法合集之《浅谈信息学竞赛中线性规划——简洁高效单纯形法实现应用》.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个约束 总结 总结 优美的单纯形法 * 最优匹配 网络流 最短路 有更好的特殊解法 只有线性规划 构造模型 解线性规划 一劳永逸 复杂 因题而异 简单 构造模型 解线性规划 源点1 源点2 汇点1 汇点2 要求流量 目标函数要求最大化 所有的变量都有非负限制 所有的限制条件都是小于等于的 m n a c b 最优值在某一顶点上 用调整法，从一个顶点出发，不断寻找目标函数更大的点，直到到达一个最优值。 初始化：首先找到一个顶点 最优化：不断调整，直到最优 顶点 松弛形式 一个顶点对应一个松弛形式 n维空间中的一个顶点 n个数的坐标 n个n元一次方程组的解 n个不等式取等号 x1=0 xn=0 … x1=0 xn=0 xn+j=0 … 第i个不等式取等号时就是xi=0 n维空间中的一个顶点 n个不等式取等号 n个变量取0 点 点 松弛形式 松弛形式 n-1个等式确定一条边 调换N中的某一个元素 沿着另外n-1个等式所确定的边到达另一个点 顶点的个数远不到这么多 调整法“爬”得很快，经过很少的点以后就达到了最优 17个空行 12行注释 18个“{” 14行读入、输出 UVA10498，没有初始化步骤的单纯形法 速度？ 558 336 5396 操作数 （Pivot） 1 1 8 时间（秒） LINDO 优化程序 普通程序 578 349 5310 操作数 （Pivot） 1 1 11 时间（秒） LINDO 优化程序 普通程序 1369 947 18243 操作数 （Pivot） 7 7 105 时间（秒） LINDO 优化程序 普通程序 线性约束 线性函数的最优值 单纯形法 非多项式级别，但是速度很快 简单的优化，非常好的效果 * * * *