《算法合集之《信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《信息学竞赛中的线性规划——简洁高效的单纯形法实现与应用》.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、浅谈信息学竞赛中的线性规划浅谈信息学竞赛中的线性规划简洁高效的单纯形法实现与应用简洁高效的单纯形法实现与应用 浙江省杭州第二中学浙江省杭州第二中学 李宇骞李宇骞引子最优匹配网络流最短路资源优化配置问题最佳物资供给问题多物网络流引子最优匹配网络流最短路有更好的特殊解法资源优化配置问题资源优化配置问题最佳物资供给问题最佳物资供给问题多物网络流多物网络流只有线性规划引子无论作为替代解法或者唯一解法构造模型解线性规划一劳永逸复杂复杂因题而异简单简单概览定义与简单应用单纯形法简介实现构造模型解线性规划定义线性规划：在满足一些线性等式或者不线性等式或者不等式等式的条件下，最优化一个线性函数线性函数。x1+
2、x2+x3+x4-2x1+8x2+0 x3+10 x4=50 x1=0 x2=4x1+5=x2多物网络流源点1源点2汇点1汇点2要求流量要求流量多物网络流k个物品，那么对每个边，设k个变量，分别代表该物品在此边上的流量。最优化的目标函数：无只求可行解约束：所有物品流量和不超过边容量限制每个物品的流都满足流量平衡条件流量平衡条件每个物品总流量达到它的要求流量单纯形法标准形式统一问题的描述主程序主程序调整法调整法松弛形式方便程序中点的表示转轴操作最核心的调整操作单纯形法标准形式(Standard form)最大化 x1+x2+x3+x4满足：x1+2x2+3x3=3x4=0目标函数要求最大化目标函
3、数要求最大化所有的变量都有非负限制所有的变量都有非负限制所有的限制条件所有的限制条件都是小于等于的都是小于等于的单纯形法标准形式(Standard form)mnacb单纯形法标准形式(Standard form)最大化共n+m个约束，除了n个变量的非负限制外，还满足m个约束，第j个约束为单纯形法形象的理解最优值在某一顶点上用调整法，从一个顶点出发，不断寻找目标函数更大的点，直到到达一个最优值。单纯形法主程序初始化：首先找到一个顶点最优化：不断调整，直到最优单纯形法顶点松弛形式一个顶点对应一个松弛形式单纯形法n维空间中的一个顶点n个数的坐标n个n元一次方程组的解n个不等式取等号单纯形法松弛形式
4、（Slack form)将n+m个不等式和n+m个变量一一对应x1=0 xn=0 x1=0 xn=0 xn+j=0第第i个不等式取等号时就是个不等式取等号时就是xi=0单纯形法松弛形式（Slack form）n维空间中的一个顶点n个不等式取等号n个变量取0单纯形法松弛形式（Slack form）点点松弛形式松弛形式单纯形法转轴操作（Pivot）n-1个等式确定一条边调换N中的某一个元素沿着另外n-1个等式所确定的边到达另一个点单纯形法时间复杂度最多有 个松弛形式顶点的个数远不到这么多顶点的个数远不到这么多调整法调整法“爬爬”得很快，经过得很快，经过很少的点以后就达到了最优很少的点以后就达到了最
5、优实现细节决定成败系数矩阵的表示以退为进初始化中X0的处理被忽略的关键贪心的优化小改动带来速度上的大飞跃实现编程复杂度200行行110行行17个空行12行注释18个“”14行读入、输出UVA10498，没有初始化，没有初始化步骤的单纯形法步骤的单纯形法实现优化贪心：每一次调整使目标函数变得尽量大！贪心：每一次调整使目标函数变得尽量大！普通的最优化过程25行加优化以后的过程35行速度？测试200个变量、200个约束普通程序优化程序LINDO时间（秒）811操作数（Pivot）5396336558测试300个变量、200个约束普通程序优化程序LINDO时间（秒）1111操作数（Pivot）5310349578测试300个变量、300个约束普通程序优化程序LINDO时间（秒）10577操作数（Pivot）182439471369总结线性约束线性函数的最优值单纯形法非多项式级别，但是速度很快简单的优化，非常好的效果总结优美的单纯形法希望大家觉得线性规划更简单，更美希望大家觉得线性规划更简单，更美