《运筹学》课程教学资源（PPT课件讲稿）第一讲 线性规划 1.3 单纯形法

1-3单纯形法 方,有数、题

1－3 单纯形法

图解法的局限性? 1947年 GBDantzig提出的单纯 形法提供了方便、有效的通用算法求 解线性规划

图解法的局限性？ 1947年G.B.Dantzig提出的单纯 形法提供了方便、有效的通用算法求 解线性规划

单纯形法的基本思想 1、顶点的還步转移 即从可行域的一个顶点(基本可行 解)开始,转移到另一个顶点(另一个 基本可行解)的迭代过程,转移的条件 是使目标函数值得到改善(逐步变优), 当目标函数达到最优值时,问题也就得 到了最优解

一、单纯形法的基本思想 1、顶点的逐步转移 即从可行域的一个顶点（基本可行 解）开始，转移到另一个顶点（另一个 基本可行解）的迭代过程，转移的条件 是使目标函数值得到改善（逐步变优）， 当目标函数达到最优值时，问题也就得 到了最优解

顶点转移的依据? 。根据线性规划问题的可行域是凸多边形 或凸多面体,一个线性规划问题有最优解, 就一定可以在可行域的顶点上找到 于是,若某线性规划只有唯一的一个最 优解,这个最优解所对应的点一定是可行域 的一个顶点;若该线性规划有多个最优解, 那么肯定在可行域的顶点中可以找到至少 个最优解

根据线性规划问题的可行域是凸多边形 或凸多面体，一个线性规划问题有最优解， 就一定可以在可行域的顶点上找到。 于是，若某线性规划只有唯一的一个最 优解，这个最优解所对应的点一定是可行域 的一个顶点；若该线性规划有多个最优解， 那么肯定在可行域的顶点中可以找到至少一 个最优解。 顶点转移的依据？

转移条件? 转移结果? 使目标函数值得到改善 得到LP最优解,目标函数达到最优值 (单纯形法的由来?) 2.需要解决的问题: (1)为了使目标函数逐步变优,怎麽转移? (2)目标函数何时达到最优 判断标准是什麽?

转移条件？ 转移结果？ 使目标函数值得到改善 得到LP最优解，目标函数达到最优值 （单纯形法的由来？ ） 2．需要解决的问题： (1)为了使目标函数逐步变优，怎麽转移？ (2)目标函数何时达到最优—— 判断标准是什麽？

二、单纯形法原理(用代数方法求解LP 例1-6 maxZ=2x,+3x2+3x3 x1+x,+x3≤3 (劳动力约束) sx1+4x,+7x2≤9 (原材料约束) X.X.X 0

二、单纯形法原理（用代数方法求解LP） 例1-6       + +  + +  = + + , , 0 4 7 9 3 ( ) . . max 2 3 3 1 2 3 1 2 3 1 2 3 1 2 3 x x x x x x x x x st Z x x x （原材料约束） 劳动力约束

第一步:引入非负的松弛变量xx,将该 LP化为标准型 maxZ=2x1+3x2+3x3+0x4+0x5 x1+x2+x2+x=3 (劳动力约束) S.x,+4x2+7x2+x:=9 (原材料约東) Xu.x 1523455

第一步：引入非负的松弛变量x4 ,x5 , 将该 LP化为标准型       + + + = + + + = = + + + + , , , , 0 4 7 9 3 ( ) . . max 2 3 3 0 0 1 2 3 4 5 1 2 3 5 1 2 3 4 1 2 3 4 5 x x x x x x x x x x x x x st Z x x x x x （原材料约束） 劳动力约束

第二步:寻求初始可行基,确定基变量 10 B =(14,15 1470 对应的基变量是x,x; 第三步:写出初始基本可行解和相应 的目标函数值

第二步：寻求初始可行基，确定基变量         = 1 4 7 0 1 1 1 1 1 0 A ( )         = = 0 1 1 0 , B P4 P5 对应的基变量是 x4，x5； 第三步：写出初始基本可行解和相应 的目标函数值

雨个吴键的基本森达式: ①用非基变量表示基变量的表达式 4÷3-x1-x2=x3 9-x1-4 Zx 初始基本可行解X0=(0,0,0,39)

两个关键的基本表达式： ①用非基变量表示基变量的表达式 T X x x x x x x x x (0,0,0,3,9) 9 4 7 3 (0) 5 1 2 3 4 1 2 3 =     = − − − = − − − 初始基本可行解

②用旅基变量表示目标画数的 表达式 z=2x1+3x2+3x3 当前的目标函数值z()=0 请解释结果的经济含义 不生产任何产品,资源全部节余(x4-3, xs=9),三种产品的总利润为0!

②用非基变量表示目标函数的11111 表达式 请解释结果的经济含义 —— 不生产任何产品，资源全部节余（x4=3， x5=9），三种产品的总利润为0！ Z = 2x1 +3x2 +3x3  0 (0) 当前的目标函数值 Z =