国家集训队2007论文集6.李宇骞《浅谈信息学.ppt

浅谈信息学竞赛中的线性规划 简洁高效的单纯形法实现与应用 浙江省杭州第二中学浙江省杭州第二中学 李宇骞李宇骞引子最优匹配网络流最短路资源优化配置问题最佳物资供给问题多物网络流引子最优匹配网络流最短路有更好的特殊解法资源优化配置问题最佳物资供给问题多物网络流只有线性规划引子 无论作为替代解法或者唯一解法构造模型解线性规划 一劳永逸复杂因题而异简单概览 定义与简单应用 单纯形法简介 实现构造模型解线性规划定义 线性规划：在满足一些 线性等式或者不等式 的条件下，最优化一个 线性函数 。 x1+x2+x3+x4 -2x1+8x2+0x3+10x4 = 50 x1 =0 x2= 0 目标函数要求最大化所有的变量都有非负限制所有的限制条件都是小于等于的