运筹学教程课件1.ppt

第一章 线性规划 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示 线性规划的图解 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 可行域的性质 线性规划的可行域是凸集 线性规划的最优解在极点上 进基变量、离基变量、基变换 单纯形表 第二章 对偶线性规划 对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的互补松弛关系 最优解的Kuhn-Tucher条件 对偶可行基对偶单纯形法 对偶的经济解释 一、对偶的定义 原始问题 min z=CTX s.t. AX≥b X ≥0 第四章 运输问题 运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 西北角法、最小元素法 非基变量的检验数 闭回路法、对偶变量法 确定进基变量，调整运量，确定离基 变量 运输问题网络图 运输问题线性规划模型 运输问题的表格表示 初始基础可行解—西北角法 第五章 网络优化 网络的基本概念 网络最小费用流问题 网络最大流问题 最短路径问题 网络的基本概念 节点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j） 网络最小费用流问题 初始基础可行解—生成树 确定非基变量x24和x34 求x24的检验数z24-c24 圈法 求x34的检验数z34 -c34 圈法 变量x34进基，确定离基变量 确定非基变量x24和x56 计算x24和x56的检验数z24 -c24 、z56-c56 最优解 网络最大流问题 35 26 38 41 30 10 11 13 7 4 27 12 15 5 13 3 48 14 6 10 9 2 35 11 7 12 8 1 4 3 2 1 35 6 38 4 22 5 30 -3 -2 -9 -11 +5 +14 用闭回路法求各非基变量的检验数 35 26 38 41 30 10 11 13 7 4 27 12 15 5 13 3 48 14 6 10 9 2 35 11 7 12 8 1 4 3 2 1 35 6 38 4 22 5 30 -3 -2 -9 -11 +5 +14 +9 用闭回路法求各非基变量的检验数 35 26 38 41 30 10 11 13 7 4 27 12 15 5 13 3 48 14 6 10 9 2 35 11 7 12 8 1 4 3 2 1 35 6 38 4 22 5 30 -3 -2 -9 -11 +5 +14 +9 +4 用闭回路法求各非基变量的检验数 35 26 38 41 30 10 11 13 7 4 27 12 15 5 13 3 48 14 6 10 9 2 35 11 7 12 8 1 4 3 2 1 35 6 38 4 22 5 30 -3 -2 -9 -11 +5 +14 +9 +4 +2 用闭回路法求各非基变量的检验数 10 11 13 7 4 12 15 5 13 3 14 6 10 9 2 11 7 12 8 1 4 3 2 1 35 6 38 4 22 5 30 v4=0 v3=3 v2=7 v1=6 u1=2 u2=3 u3=12 u4=10 对于基变量xij，有ui+vj=cij 用对偶变量法求各非基变量的检验数 10 11 13 7 4 12 15 5 13 3 14 6 10 9 2 11 7 12 8 1 4 3 2 1 35 6 38 4 22 5 30 -3 -2 -9 -11 +5 +14 +9 +4 +2 v4=0 v3=3 v2=7 v1=6 u1=2 u2=3 u3=12 u4=10 非基变量xij的检验数：zij-cij=ui+vj-cij，与闭回路法的结果相同 用对偶变量法求各非基变量的检验数 35 26 38 41 30 10 11 13 7 4 27 12 15 5 13 3 48 14 6 10 9 2 35 11 7 12 8 1 4 3 2 1 35 6 38 4 22 5 30 -3 -2 -9 -11 +5 +14 +9 +4 +2 j i 路径（Path） 前后相继并且方向相同的边序列 P={(1,2),(2,3),(3,4)} 4 2 3 1 4 2 3 1 网络由节点和边组成 回路（Circuit） 起点和终点重合的路径称为回路 μ={(1,2),(2,4),(4,1)} 回路中各条边方向相同 4 2 3 1 链（Chain） 前后相继并且方向不一定相同的边序列