运筹学全套课件.pptx

运筹学;第一章线性规划;线性规划模型;;可行域的性质;线性规划的基本概念;;;;;;;;;;;;;;几何概念;单纯形表;求解线性规划问题;;;线性规划的矩阵表示;;CBTB-1aj-cj=zj-cj称为非基变量的检验数（ReducedCost）

B-1aj=Yj，B-1b=，CBTB-1b=z0;;第二章对偶线性规划;一、对偶的定义;二、对偶问题的性质;;;3、原始问题和对偶问题最优解之间的互补松弛关系

;minz=CTX

s.t. AX-XS=b

X,XS≥0;;;四、对偶单纯形法;单纯形表和对偶(1);minz=CTX

s.t.AX-XS=b

X,XS≥0;minz=CTX

s.t.AX+XS=b

X,XS≥0;minz=CTX

s.t.AX+XS=b

X,XS≥0;maxz=CTX

s.t.AX-XS=b

X,XS≥0;maxz=CTX

s.t.AX-XS=b

X,XS≥0;maxz=CTX

s.t.AX+XS=b

X,XS≥0;maxz=CTX

s.t.AX+XS=b

X,XS≥0;2、对偶单纯形法（初始解原始不可行的问题）;;;已获得最优解：

（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）minz=35

对偶问题的最优解为：

（w1,w2,w3,w4,w5,w6）=（-1,5,7,0,0,0）maxy=35;3、初始解原始、对偶都不可行的问题;解法1：先解决原始可行性;;在得到原始可行解时同时得到对偶可行解，已获得最优解：

（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）minz=17

对偶问题的最优解为：

（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）maxy=17;解法2：先解决对偶可行性;;得到原始可行解，已获得最优解：

（x1,x2,x3,x4,x5,x6）=（5,7,6,0,0,0）minz=17

对偶问题的最优解为：

（w1,w2,w3,w4,w5,w6）=（-7,5,10,0,0,0）maxy=17;五、对偶的经济解释;2、对偶问题;3、资源影子价格的性质;;;5、互补松弛关系的经济解释;第四章运输问题;2;运输问题线性规划模型;运输问题的表格表示;初始基础可行解—西北角法;初始基础可行解—最小元素法（1）;最小元素法（2）;最小元素法（3）;最小元素法（4）;最小元素法（5）;最小元素法（6）;-5;-5;-5;-5;-5;-5;非基变量xij的检验数zij-cij—对偶变量法(1);对偶变量法(2);对偶变量法(3);对偶变量法(4);对偶变量法(5);对偶变量法(6);对偶变量法(7);对偶变量法(8);对偶变量法(9);对偶变量法(10);对偶变量法(11);对偶变量法(12);对偶变量法(13);选择进基变量,确定离基变量;调整运量,重新计算检验数,确定进基、离基变量;调整运量,重新计算检验数;第五章网络优化;网络的基本概念;回路（Circuit）

起点和终点重合的路径称为回路

μ={(1,2),(2,4),(4,1)}

回路中各条边方向相同;连通图

任意两个节点之间至少有一条链的图称为连通图;树的性质;网络的生成树;网络的生成树的变换;网络的生成树和线性规划的关系;网络最小费用流问题;;确定非基变量x24和x34;求x24的检验数z24-c24闭回路法;求x34的检验数z34-c34闭回路法;变量x34进基，确定离基变量;确定非基变量x24和x56;计算x24和x56的检验数z24-c24、z56-c56;最优解;网络最大流问题;

边的容量和流量

容量uij，流量xij

可行流

满足以下条件的流称为可行流：

1、每一个节点流量平衡

2、0≤xij≤uij;;;给出一个初始的可行流xij=0;找到所有的不饱和边，以及各边可以调整流量的方向;找到一条从1到7的不饱和链;调整流量，f=1。继续求出网络的不饱和边;求出一条从1到7的不饱和链;调整流量，继续求出网络的不饱和边;求出一条从1到7的不饱和链;调整流量，继续求出网络的不饱和边;;调整流量，继续求出网络的不饱和边;求出一条从1到7的不饱和链;调整流量，继续求出网络的不饱和边;;