运筹学精品课件.ppt

目 录 第一章 线性规划 第二章 整数规划 第三章 动态规划 第四章 图与网络 第五章 决 策 论 第六章 矩阵对策 第一章 线性规划 数学模型 图解法 可行域的性质 单纯形法 单纯形表 单纯形法的矩阵描述 对偶规划 运输问题 数学模型 线性规划模型的结构 目标函数：max，min max z(min f)=∑cjxj 约束条件：≥,=,≤ ∑aijxj ≤(=, ≥) bi (i=1,2, …n) 变量符号：≥0,unr,≤0 xj ≥0 (j=1,2, …n) 线性规划的标准形式 目标函数：max max z=∑cjxj 约束条件 ：= ∑aijxj = bi (i=1,2, …n) 变量符号 ：≥0 xj ≥0 (j=1,2, …n) 线性规划的图解 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 可行域的性质 线性规划的最优解在极点上 线性规划的可行域是凸集 单纯形法的引例 单纯形表 单纯形法的矩阵描述 矩阵描述之初始单纯形表 先取初始单位阵I作为初始基阵B，得 初始单纯形表： 矩阵描述之迭代单纯形表 对偶规划 原规划与对偶规划的线性关系 运输问题 运输问题的表示 网络图、线性规划模型、运输表 初始基础可行解 最小元素法、差值法 判别最优方案 位势法 运输问题网络图 运输问题线性规划模型 运输问题的表格表示 最小元素法（1） 最小元素法（2） 最小元素法（3） 最小元素法（4） 最小元素法（5） 最小元素法（6） 表上作业法——差值法(1) 差值法(2) 差值法(3) 差值法(4) 差值法(5) 差值法(6) 差值法(7) 判别最优方案——位势法 位势法(2) 位势法(3) 位势法(4) 位势法(5) 第二章 整数规划 分枝定界法 0-1型整数规划 分配问题 分枝定界法 例1：讨论纯整数规划 max z=x1+2x2 s.t. 2x1+5x2≤15 2x1－2x2≤5 x1 , x2≥0且为整数 分枝定界法(1) 不考虑x1,x2为整数的限制条件，得规划（0）对应的最优解与最优值为 分枝定界法（2） 考察X的某一分量，不妨选x2= ,因为1x22,为了使x2整数化,剔除1x22对应的可行域.为此,增加约束条件x2≤1及x2≤2,于是可行域R0可分解成两个小可行域R1和R2.原规划(0)分解成规划(1)与规划(2): 分枝定界法(3) 仿上求解，得规划（1）、（2）对应的最优解与最优值为： 分枝定界法(4) 考察(1)、(2)，因规划（2）的z值优于规划（1）的z值，故先分解规划（2）。仿上，R2分解成R3与R4=Ф。规划（2）分解成规划（3）与规划（4）： 分枝定界法(5) 仿上求解，得规划（1）、（2）对应的最优解与最优值为： 分枝定界法(6) 考察(1)、(3)，因规划（3）的z值优于规划（1）的z值，故先分解规划（3）。仿上，R3分解成R5与R6。规划（3）分解成规划（5）与规划（6）： 分枝定界法(7) 0—1型整数规划(1) 显枚举法： 例：求解下列0—1规划 max z=3x1－2x2＋5x3 s.t. x1＋2x2—x3≤2 x1＋4x2＋x3≤4 x1＋3x2 ≤3 4x2＋3x3≤6 0—1型整数规划(2) 0—1型整数规划(3) 分配问题 一般最小分配问题的数学模型为: min f=∑∑cijxij s.t. ∑xij=1 (i=1,2,…,n) ∑xij=1 (j=1,2,…,n) xij=0或1 (i,j=1,2,…,n) 目标函数最大的分配问题可化为目标函数最小的分配问题来求解。可取一个比所有cij都大的整数k，令 c’ij=k－cij即可。以cij为价值系数求最大分配就等价于以c’ij为价值系数求最小分配。 分配问题解法——匈牙利法 1、缩减矩阵 匈牙利法（2）