《管理运筹学》02-2求解线性规划的单纯形法.ppt
第二节第二节 单纯形法单纯形法Simplex Method求解线性规划的单纯形法求解线性规划的单纯形法单纯形法思路YES停止求解线性规划的单纯形法求解线性规划的单纯形法Q1：初始基本可行解如何找？标准型基本解Q2：怎样判断最优？最优性条件Q3：如何找下一个相邻的基本可行解？确定移动的方向确定在何处停下确定新的基本可行解关键问题求解线性规划的单纯形法求解线性规划的单纯形法例：用单纯形法求解以下线性规划问题求解线性规划的单纯形法求解线性规划的单纯形法首先将模型转化成标准形式求解线性规划的单纯形法求解线性规划的单纯形法Q1：确定初始的基本可行解选择原点：选择原点：令决策变量 x1=x2=0得：得：X0=(0，0，3，4)T选择单元阵作为初始基：选择单元阵作为初始基：令非基变量 x1=x2=0得：得：X0=(0，0，3，4)T求解线性规划的单纯形法求解线性规划的单纯形法非最优：增加非基变量的值，可以使得目标函数Z值增加基变量在目标函数中的系数为0非基变量在目标函数中的系数=0Q2：最优性检验检验数求解线性规划的单纯形法求解线性规划的单纯形法迭代步骤迭代步骤1：确定移动的方向：确定移动的方向 例：例：z=2x1+3x2选择 x1？Z的增长率=2选择 x2？Z的增长率=332，选择x2！进基变量的选择：选择非基变量的系数最大的！Q3：如何找下一个相邻的基本可行解确定进基变量确定进基变量检验数的绝对值哦求解线性规划的单纯形法求解线性规划的单纯形法迭代步骤迭代步骤2：确定在何处停下：确定在何处停下增加x x2 2 的值，x1=0所有变量非负 令x2=2，从而 x4=0离基变量的选择：最小比值法确定离基变量确定离基变量最小比值法Q3：如何找下一个相邻的基本可行解求解线性规划的单纯形法求解线性规划的单纯形法迭代步骤迭代步骤3：确定新的基本可行解：确定新的基本可行解u原方程 寻找新的基本可行解：初等数学变换初等数学初等数学变换变换初始初始BF解解新的新的BF解解非基变量（Non-basics）x1=0，x2=0 x1=0，x4=0基变量（Basics）x3=3，x4=4x3=？，x2=21X*=（0,2,1,0）Z*=6+x1/2-3x4/26u新方程Q3：如何找下一个相邻的基本可行解非基变量x1的系数是正数！非最优解！求解线性规划的单纯形法求解线性规划的单纯形法第第2次迭代次迭代 确定进基变量确定进基变量x1 确定离基变量确定离基变量非基变量x4=0确定确定x x3 3为离基变量为离基变量 初等行变换初等行变换初等初等行变换行变换非基变量系数0，最优！Z*=7,X*=(2,1,0,0)求解线性规划的单纯形法求解线性规划的单纯形法目标函数无界的情况minz=-x1-2x2s.t.-x1+x21x22x1,x20用单纯形法求解以下线性规划模型。求解线性规划的单纯形法求解线性规划的单纯形法最优性检验：最优性检验：一切一切一切一切 j 0？然后确定初始基本可行解 X0=(0,0,1,2)T z0=0 0 当前解当前解 X0 非优；非优；须由须由X0 转化为另一个基本可行解转化为另一个基本可行解 X1。思路思路思路思路：让：让X0 中的一个中的一个非基变量非基变量进基进基，去替换原来的一个，去替换原来的一个基变量基变量基变量基变量（离基离基）。）。首先标准化，令z=-z，引入松弛变量x3,x4maxz=x1+2x2s.t.-x1+x2+x3=1x2+x4=2x1,x2,x3,x40 x1仍为非基变量，其值为仍为非基变量，其值为0。x3=1-x2x4=2 -x2 x2 1/1 x2 2/1w 离基离基离基离基（最小比值规则最小比值规则最小比值规则最小比值规则）：x2 min 1/1，2/1 =1 x2 =min 1/1，2/1 =1 x3x3为为离基变量离基变量w 进基进基（最小检验数规则最小检验数规则最小检验数规则最小检验数规则）：）：在在负检验数负检验数负检验数负检验数中选择中选择最小的最小的最小的最小的进基进基。min j j0 =k xk 进基进基 min-1，-2=-2=2 x2 进基进基 0 0 0 0=X1=(0,1,0,1)Tz-x1 -2x2 =0 0 -x1+x2 +x3 =1 x2 +x4 =2 ()0由由 有有求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法主方程主方程主方程主方程 1主列主列进基进基主元主元 z-x1 -2 x2 =0-x1 +x2 +x3 =1 1 x2 +x4 =2 ()1 12比值比值比值比值min离基离基离基离基以以主列主列中中正值元素正值元素正值元素正值元素为为分母分母分母分母，同行，同行右端常数右端常数右端常数右端常数为为分子分子分子分子，求，求比值比值比值比值；按按最小最小最小最小比值比值比值比值规则规则规则规则确定确定主方程主方程主方程主方程和和主元素主元素主元素主元素，以及，以及离基变量离基变量离基变量离基变量。求解线性规划的单纯形法求解线性规划的单纯形法X X0 0 =(0,0,1,2)=(0,0,1,2)T T z z0 0 =0=0 ()-x1+x2 +x3 =1 得得X X1 1=z z0 0 =2=2称为单纯形法的一次称为单纯形法的一次迭代迭代。z-x1 -2x2 =0 -x1+x2 +x3 =1 1 x2 +x4 =2 ()10 x1 -x3 +x4 =1 z-3x1 +2x3 =20(0,0,1,1,0,0,1 1)T T换基运算换基运算换基运算换基运算方程组方程组方程组方程组的的初等变换初等变换初等变换初等变换目的目的目的目的是把是把主列主列主列主列变为变为单位向量单位向量单位向量单位向量：主元：主元：主元：主元变变为为1，其余变为，其余变为0。用用换基运算换基运算换基运算换基运算将将X0 转化为转化为另一个基本另一个基本可行解可行解 X X1 1。0 01 10 0求解线性规划的单纯形法求解线性规划的单纯形法()-x1+x2 +x3 =1 1x1 -x3 +x4 =1 z-3x1 +2x3 =20比值比值比值比值-1 1min()z -x3 +3x4 =5x2 +x4 =2 x1 -x3 +x4 =1 0得得X X*=(1,2,1,2,0,0,0 0 )T T z*z*=5 5参数=0 x1=1+x3-x4=0 x2、x1不受x3限制！求解线性规划的单纯形法求解线性规划的单纯形法目标函数无界的线性规划问题目标函数无界的线性规划问题练习：用单纯形法求解下列线性规划问题求解线性规划的单纯形法求解线性规划的单纯形法s.t.x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5 =36 x1 ，x2 ，x3，x4，x5 0 max z=3x1+5x2
