《管理运筹学》02-2求解线性规划的单纯形法.ppt

《《管理运筹学》02-2求解线性规划的单纯形法.ppt》由会员分享，可在线阅读，更多相关《《管理运筹学》02-2求解线性规划的单纯形法.ppt（19页珍藏版）》请在三一办公上搜索。

1、第二节 单纯形法,Simplex Method,求解线性规划的单纯形法,单纯形法思路,求解线性规划的单纯形法,Q1：初始基本可行解如何找？标准型基本解Q2：怎样判断最优？最优性条件Q3：如何找下一个相邻的基本可行解？确定移动的方向确定在何处停下确定新的基本可行解,关键问题,求解线性规划的单纯形法,例：用单纯形法求解以下线性规划问题,求解线性规划的单纯形法,首先将模型转化成标准形式,求解线性规划的单纯形法,Q1：确定初始的基本可行解,选择原点：令决策变量 x1=x2=0得：X0=(0，0，3，4)T选择单元阵作为初始基：令非基变量 x1=x2=0得：X0=(0，0，3，4)T,求解线性规划的单纯

2、形法,非最优：增加非基变量的值，可以使得目标函数Z值增加基变量在目标函数中的系数为0非基变量在目标函数中的系数=0,Q2：最优性检验,检验数,求解线性规划的单纯形法,迭代步骤1：确定移动的方向 例：z=2x1+3x2选择 x1？Z的增长率=2选择 x2？Z的增长率=332，选择x2！进基变量的选择：选择非基变量的系数最大的！,Q3：如何找下一个相邻的基本可行解,确定进基变量,检验数的绝对值哦,求解线性规划的单纯形法,迭代步骤2：确定在何处停下增加x2 的值，x1=0所有变量非负 令x2=2，从而 x4=0离基变量的选择：最小比值法,确定离基变量,最小比值法,Q3：如何找下一个相邻的基本可行解,

3、求解线性规划的单纯形法,迭代步骤3：确定新的基本可行解原方程 寻找新的基本可行解：初等数学变换,初等数学变换,1,X*=（0,2,1,0）,Z*=6+x1/2-3x4/26,新方程,Q3：如何找下一个相邻的基本可行解,非基变量x1的系数是正数！,非最优解！,求解线性规划的单纯形法,第2次迭代 确定进基变量x1 确定离基变量,非基变量x4=0,确定x3为离基变量,初等行变换,初等行变换,非基变量系数0，最优！,Z*=7,X*=(2,1,0,0),求解线性规划的单纯形法,目标函数无界的情况,用单纯形法求解以下线性规划模型。,求解线性规划的单纯形法,最优性检验：,一切j 0？,然后确定初始基本可行解

4、 X0=(0,0,1,2)T z0=0,当前解 X0 非优；,须由X0 转化为另一个基本可行解 X1。,思路：让X0 中的一个非基变量进基，去替换原来的一个基变量（离基）。,首先标准化，令z=-z，引入松弛变量x3,x4,x1仍为非基变量，其值为0。,x2 1/1 x2 2/1,离基（最小比值规则）：x2 min 1/1，2/1=1 x2=min 1/1，2/1=1,x3,x3为离基变量,进基（最小检验数规则）：在负检验数中选择最小的进基。min jj0=k xk 进基 min-1，-2=-2=2 x2 进基,0,0,=,X1=,(,0,1,0,1,)T,由 有,求解线性规划的单纯形法,求解线

5、性规划的单纯形法,主方程,1,主列,主元,z-x1-2 x2=0,-x1+x2+x3=1,1 x2+x4=2,(),12,比值,min,以主列中正值元素为分母，同行右端常数为分子，求比值；,按最小比值规则确定主方程和主元素，以及离基变量。,求解线性规划的单纯形法,X0=(0,0,1,2)T z0=0,(),-x1+x2+x3=1,得,X1=,z0=2,称为单纯形法的一次迭代。,x1-x3+x4=1,(,0,1,0,1,)T,换基运算方程组的初等变换目的是把主列变为单位向量：主元变为1，其余变为0。,用换基运算将X0 转化为另一个基本可行解 X1。,010,求解线性规划的单纯形法,(),-x1+x2+x3=1,1x1-x3+x4=1,比值,-1,min,(),z-x3+3x4=5,x2+x4=2,x1-x3+x4=1,0,得,X*=(1,2,0,0)T,z*=5,参数0!进基！,x2=2-x4=0,x1=1+x3-x4=0,x2、x1不受x3限制！,求解线性规划的单纯形法,目标函数无界的线性规划问题,练习：用单纯形法求解下列线性规划问题,求解线性规划的单纯形法,