运筹学教程课程.ppt

文档介绍：运筹学课件
天津工业大学
目录
第一章 线性规划
第二章 对偶
第三章 整数规划
第四章 运输问题
第五章 网络优化
第六章 动态规划
第一章线性规划
线性规划模型
线性规划的图解
可行域的性质
线性规划的基本概念
基础解、基础可行解
单纯形表
线性规划的矩阵表示
线性规划模型
线性规划模型的结构
目标函数:max,min
约束条件:≥,=,≤
变量符号::≥0, unr, ≤0
线性规划的标准形式
目标函数:min
约束条件 :=
变量符号 :≥0
线性规划的图解
max z=x1+3x2
. x1+ x2≤6
-x1+2x2≤8
x1 ≥0, x2≥0
可行域
目标函数等值线
最优解
6
4
-8
6
0
x1
x2
可行域的性质
线性规划的可行域是凸集
线性规划的最优解在极点上
凸集
凸集
不是凸集
极点
线性规划的基本概念
线性规划的基矩阵、基变量、非基变量
=
=
目标函数
约束条件
行列式≠0
基矩阵
右边常数
基变量x1、x2、x3,非基变量x4、x5、x6
基础解为(x1,x2,x3,x4,x5,x6)=(5,3,1,0,0,0)
是基础可行解,表示可行域的一个极点。
目标函数值为:z=20
基变量x1、x2、x4,非基变量x3、x5、x6
基础解为
(x1,x2,x3,x4,x5,x6)=(27/5,12/5,0,2/5,0,0)
是基础可行解,表示可行域的一个极点。
目标函数值为:z=18