运筹学教程课程天津工业大学.pptVIP

目 录 第一章 线性规划 第二章 对偶 第三章 整数规划 第四章 运输问题 第五章 网络优化 第六章 动态规划 第一章 线性规划 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示 线性规划的图解 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） 网络最大流问题 找到一条从1到7的不饱和链 调整流量，f=1。继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 已求得最大流 链的间隙为：? = min{8,3,1,8}=1 调整链的流量：xij’=xij+ ? 2 3 5 4 6 7 1 f=0 f=0 u=6 u=2 u=4 u=3 u=7 u=4 u=3 u=1 u=7 u=9 u=8 u=8 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 ?=3 ?=1 ?=8 ?=8 x=0 2 3 5 4 6 7 1 f=1 f=1 u=6 u=2 u=4 u=3 u=7 u=4 u=3 u=1 u=7 u=9 u=8 u=8 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1 x=1 x=1 x=1 2 3 5 4 6 7 1 f=1 f=1 u=6 u=2 u=4 u=3 u=7 u=4 u=3 u=1 u=7 u=9 u=8 u=8 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=0 x=1 x=1 x=1 x=1 ?=1 ?=6 ?=9 ?=7 ?=min {7,1,6,9}=1, 调整流量 xij’=xij+1, f’=f+1=2 2 3 5 4 6 7 1 f=2 f=2 u=6 u=2 u=4 u=3 u=7 u=4 u=3 u=1 u=7 u=9 u=8 u=8 x=1 x=0 x=0 x=1 x=0 x=0 x=0 x=1 x=1 x=1 x=1 x=0 对偶变量法(7) u1+v1=c11 u1=-4 对偶变量法(8) z12-c12=u1+v2-c12=(-4)+6-7=-5 -5 对偶变量法(9) z13-c13=u1+v3-c13=(-4)+4-5=-5 -5 -5 对偶变量法(10) z14-c14=u1+v4-c14=(-4)+0-3=-7 -7 -5 -5 对偶变量法(11) z24-c24=u2+v4-c24=(-2)+0-7=-9 -9 -5 -5 -7 对偶变量法(12) z31-c31=u3+v1-c31=6+10-5=11 11 -5 -5 -7 -9 对偶变量法(13) z32-c32=u3+v2-c32=6+6-9=+3 +3 -5 -5 -7 -9 11 选择进基变量,确定离基变量 x31进基, min{x21