02运筹学第一章.ppt

运筹学基础 第一节 线性规划问题及其数学模型 2） 场地租用问题 二、线性规划问题的数学模型 3）线性规划的数学模型的表示 4）线性规划的数学模型的其它表示方式 三、线性规划问题的标准格式 2）化一般线性规划问题为标准格式的方法 松弛变量 一个最有代表性的例子 一个最有代表性的例子 一个最有代表性的例子 一个最有代表性的例子 一个最有代表性的例子 第二节 图解法 例二 max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 二、解的可能情况 利润 Max z=x1+3x2 s.t. x1+ x2≤6 x1 +2x≤8 x1 ≥0, x2≥0 二、线性规划解的可能情况 第三节 单纯形法原理 二、 凸集及其顶点 二、 凸集及其顶点 三、 线性规划解的几个重要定理 四、 单纯形法迭代原理 第四节 单纯形法计算步骤 第四节 单纯形法计算步骤 第四节 单纯形法计算步骤 第四节 单纯形法计算步骤 例三 单纯形法具体步骤： 一、大M法 引入人工变量 xn+i ≥ 0 （i = 1 , … , m）及充分大正数 M 。得到： 显然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解。对应的基是单位矩阵。 结论：若得到的最优解满足 xn+i = 0 i = 1 , … , m 则是原问题的最优解；否则，原问题无可行解。 二、两阶段法 引入人工变量 xn+i ≥ 0，i = 1 ,…, m； 构造: Max z = - xn+1 - xn+2 - … - xn+m s.t. a11x1+a12x2+ … +a1nxn+xn+1 = b1 a21x1+a22x2+ … +a2nxn+xn+2 = b2 . . . am1x1+am2x2+ … +amnxn+xn+m = bm x1,x2 ... xn ,xn+1,…,xn+m ≥ 0 第一阶段求解上述问题： 显然，xj = 0 j=1, … , n ; xn+i = bi i =1 , … , m 是基本可行解,它对应的基 是单位矩阵。 Max z = 5x1 + 2x2 + 3x3 - x4 s.t. x1 + 2x2 + 3x3 = 15 2x1 + x2 + 5x3 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 0 第一阶段问题（LP - 1） Max z = - x5 - x6 s.t. x1 + 2x2 + 3x3 + x5 = 15 2x1 + x2 + 5x3 + x6 = 20 x1 + 2x2 + 4x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0 注意：单纯形法中 1、每一步运算只能用矩阵初等行变换； 2、表中第3列(b列)的数总应保持非负（≥0）； 3、当所有检验数均非正（≤0）时，得到最优单纯形表。若直接对目标求最小，要求所有检验数均非负； 4、当最优单纯形表存在非基变量对应的检验数为零时，存在无穷多解； 5、关于退化和循环。如果在一个基本可行解的基变量中至少有一个分量xBi=0 (i=1,2,…,m)，则称此基本可行解是退化的基本可行解。一般情况下，退化的基本可行解（极点）是由若干个不同的基本可行解（极点）在特殊情