《运筹学复习》PPT课件.ppt

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