[农学]广东工业大学《运筹学课件》.ppt

运筹学演示课件;目 录;第一章 线性规划;线性规划模型;线性规划的图解;可行域的性质;线性规划的基本概念;;基变量x1、x2、x3，非基变量x4、x5、x6;基变量x1、x2、x4，非基变量x3、x5、x6;基变量x1、x2、x5，非基变量x3、x4、x6;基变量x1、x2、x6，非基变量x3、x4、x5;基变量x2、x3、x4，非基变量x1、x5、x6;基变量x1、x2、x3，非基变量x4、x5、x6;基变量x1、x2、x3，非基变量x4、x5、x6;=;=;=;=;=;基础解、基础可行解;几何概念;单纯形表;求解线性规划问题;写出单纯形表;0;;;;;线性规划的矩阵表示;;;;CBTB-1aj-cj=zj-cj 称为非基变量的检验数（Reduced Cost） B-1aj=Yj， B-1b= ，CBTB-1b=z0;;第二章 对偶线性规划;一、对偶的定义;二、对偶问题的性质;min z=CTX s.t. AX≤b X ≥0;三、原始对偶关系;3、原始问题和对偶问题最优解之间的互补松弛关系 ;min z=CTX s.t. AX-XS=b X, XS ≥0;w1 wi wm wm+1 wm+j wn+m ;Kuhn-Tucher 条件;四、对偶单纯形法;单纯形表和对偶(1);min z=CTX s.t. AX-XS=b X, XS≥0;min z=CTX s.t. AX+XS=b X, XS≥0;min z=CTX s.t. AX+XS=b X, XS≥0;max z=CTX s.t. AX-XS=b X, XS≥0;max z=CTX s.t. AX-XS=b X, XS≥0;max z=CTX s.t. AX+XS=b X, XS≥0;max z=CTX s.t. AX+XS=b X, XS≥0;2、对偶单纯形法（初始解原始不可行的问题）;;;已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35;3、初始解原始、对偶都不可行的问题;解法1：先解决原始可行性;;在得到原始可行解时同时得到对偶可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17;解法2：先解决对偶可行性;;得到原始可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17;五、对偶的经济解释;2、对偶问题;3、资源影子价格的性质;w1 w2 wm;机会成本;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 -c