运筹学教程2课件.ppt

目 录 第一章 线性规划 第二章 对偶 第三章 整数规划 第四章 运输问题 第五章 网络优化 第六章 动态规划 第七章 排 队 论 第一章 线性规划 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示 线性规划的图解 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 可行域的性质 线性规划的可行域是凸集 线性规划的最优解在极点上 线性规划的基本概念 线性规划的基矩阵、基变量、非基变量 进基变量、离基变量、基变换 基础解、基础可行解 max z=x1+3x2 D s.t. x1+ x2+x3 =6 B -x1+2x2 +x4 =8 x4=0 C x3=0 x1, x2,x3,x4≥0 x1=0 E O x2=0 A 单纯形表 线性规划的矩阵表示 第二章 对偶线性规划 对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的关系—互补松弛关系 最优解的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 最优解 网络最大流问题 找到一条从1到7的不饱和链 调整流量，f=1。继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 已求得最大流 b2=-2 b4=3 b3=5 b5=-6 b6=-5 b1=5 x46=5 x13=3 x35=6 x34=2 x12=2 2 3 4 5 6 1 z24 -c24 =(c34+c13-c12)-c24=(4+3-6)-5= -4 z56 -c56 =(c46+c34-c35)-c56=(1+4-2)-4= -1，获得最优解 b2=-2 b4=3 b3=5 b5=-6 b6=-5 b1=5 c24=5 c46=1 c13=3 c35=2 c56=4 c34=4 c12=6 2 3 4 5 6 1 最优解的目标函数值为：min z=6?2+3?3+4?2+2?6+1?5=46 b2=-2 b4=3 b3=5 b5=-6 b6=-5 b1=5 x46=5 x13=3 x35=6 x34=2 x12=2 2 3 4 5 6 1 2 3 5 4 6 7 1 f f u25=6 u42=2 u45=4 u23=3 u13=7 u34=4 u46=3 u36=1 u65=7 u57=9 u67=8 u12=8 边的容量和流量 容量uij，流量xij 可行流 满足以下条件的流称为可行流： 1、每一个节点流量平衡 2、0≤xij ≤uij 边的容量和流量、可行流 2 1 xij=5 uij=5 2 1 xij=3 uij=5 饱和边、不饱和边、流量的间隙 （1，2）是饱和的 2、如果xijuij，边从i到j的方向是不饱和的； （1，2）是不饱和的 间隙为?12=u12-x12=5-3=2 1、如果xij=uij，边从i到j的方向是饱和的； 2 1 xij=0 uij=5 2 1 xij=5 uij=5 3、如果xij=0，边从j到i的方向是饱和的； （2，1）是饱和的 如果xij0，边从j到i的方向是不饱和的； （2，1）是不饱和的 间隙为?1