《运筹学复习.ppt》由会员分享，可在线阅读，更多相关《运筹学复习.ppt（19页珍藏版）》请在三一文库上搜索。
1、2019/5/11,运筹学复习,绍兴文理学院 工学院计算机系,2019/5/11,运筹学 期末复习提纲,线性规划的单纯形法、图解法 线性规划的对偶规划对偶单纯形法 运输问题及其初始解、最优解 整数规划 组合优化问题 排序与统筹 对策论的最优纯对策 搜索论,模型、算法、计算,2019/5/11,线性规划的图解法,适用范围 可行解集凸多边形 半平面的确定 无可行解的情况 目标函数的等高线 线性规划问题的图解方法 无有限最优解的情况 有唯一最优解的情况 最优解不唯一的情况,2019/5/11,约束条件 目标函数,x1+ x2300 2x1+x2400 x2250 x10 , x20 max f=50
2、x1+100x2,线性规划问题(1),我们用图解法：x1+ x2300 的几何意义是半平面。,2019/5/11,图解线性规划问题(1),2x1+x2=4,最优解(0.5,2.5),目标函数 f = 50x1+100x2 =275,x1+x2=3,x2=2.5,可行解区域,2019/5/11,约束条件 目标函数,2x1+9x218 2x1+4x210 3x1+2x212 x10 , x20 max f=3x1+4x2,线性规划问题(2),2019/5/11,线性规划问题(2),2x1+9x2=18,最优解(3.5,0.75),目标函数 f = 3x1+4x2 =13.5,3x1+2x2=12,
3、2x1+4x2=10,可行解区域,2019/5/11,线性规划的单纯形,解法思路 标准型的线性规划问题，标准化 初始基可行解的寻找 基、基向量、非基向量 基变量、非基变量 最优性的检验 检验数、最优解的判别定理:i非正 迭代 入基变量和出基变量的确定 单纯形表的设计,2019/5/11,对偶规划,对偶规划的由来及用途 对称型的对偶规划问题 一般线性规划问题的对偶规划 要求能写出(P),(D) 知道对偶规划的有关结论 会用对偶单纯形法解题,2019/5/11,运输问题,产销平衡的运输问题 表上作业法 初始基可行解的求法： 最小元素法、西北角法、沃格尔法 检验数的求法 闭回路法、位势法 解的最优性
4、的判别 迭代： 进基变量、出基变量的确定,2019/5/11,最大流最小树,不计费用的和最小费用的最大流问题 最大流问题的网络图论解法 求最大流问题的基本算法 最小费用最大流问题的网络图论解法 求最小费用最大流问题的基本算法 最小生成树问题 避圈法、Prim法,2019/5/11,用Kruskal算法求最小树,用Kruskal算法(避圈法)求赋权连通图G的最小树,最小树的权为24，最小树为T=v1v2,v1v3,v2v5,v5v6,v6v7,v6v4,2019/5/11,用Prim算法求最小树,用Prim算法(就近法)求赋权连通图G的最小树,最小树的权为24，最小树为Tree=v1v2,v1v
5、3,v2v5,v5v6,v6v7,v6v4,T=v1,S=v2,v3,v4,v5,v6,v7,T=v1,v2,T=v1,v2,v3,T=v1,v2,v3,v5,T=v1,v2,v3,v5,v6,T=v1,v2,v3,v5,v6,v7,T=v1,v2,v3,v5,v6,v7,v4,2019/5/11,求最小生成树,求下图的最小 生成树,2019/5/11,最大流问题,最大流为:10，解为,2019/5/11,排序与统筹,一台机器n个零件加工的排序问题 两台机器n个零件加工的排序问题 PERT图 计划网络图 最早开始时间、最晚开始时间 缓冲时间 关键路径,2019/5/11,对策论的最优纯对策,对策论的基本概念 局中人 策略集 一局势策略的益损值 矩阵对策 何时有最优纯对策 最优纯对策的求法,2019/5/11,搜索论,求函数零点的方法： 对分法 切线法 弦线法 联合法 求函数极值的方法： 0.618法 瞎子爬山法 用Excel的“规划求解”求解,2019/5/11,“规划求解”的用法,计算器的使用 计算机的使用 Excel的使用 公式的使用 单变量求解 规划求解,