求解线性规划的单纯形法(1)课件.ppt
求解线性规划的单纯形法求解线性规划的单纯形法NO找到相邻的基本可行解最优性检验当前的CPF是最优解吗？开始找到初始的基本可行解单纯形法思路YES停止求解线性规划的单纯形法求解线性规划的单纯形法 Q1：初始基本可行解如何找？ 标准型 基本解 Q2：怎样判断最优？ 最优性条件 Q3：如何找下一个相邻的基本可行解？ 确定移动的方向 确定在何处停下 确定新的基本可行解关键问题求解线性规划的单纯形法求解线性规划的单纯形法例：用单纯形法求解以下线性规划问题求解线性规划的单纯形法求解线性规划的单纯形法首先将模型转化成标准形式求解线性规划的单纯形法求解线性规划的单纯形法Q1：确定初始的基本可行解 选择原点：选择原点： 令决策变量 x1= x2 = 0得：得：X0 = ( 0，0，3，4)T 选择单元阵作为初始基：选择单元阵作为初始基：令非基变量 x1= x2 = 0得：得：X0 = ( 0，0，3，4)T12341 110(,)1201Aa a a a3410(,)01Ba a求解线性规划的单纯形法求解线性规划的单纯形法 非最优：增加非基变量的值，可以使得目标函数Z值增加 基变量在目标函数中的系数为0 非基变量在目标函数中的系数=0Q2：最优性检验检验数求解线性规划的单纯形法求解线性规划的单纯形法 迭代步骤迭代步骤1：确定移动的方向：确定移动的方向 例：例：z = 2x1 + 3x2 选择 x1 ？Z的增长率=2 选择 x2 ？Z的增长率=3 32，选择x2！ 进基变量的选择： 选择非基变量的系数最大的！Q3：如何找下一个相邻的基本可行解确定进基变量确定进基变量检验数的绝对值哦求解线性规划的单纯形法求解线性规划的单纯形法 迭代步骤迭代步骤2：确定在何处停下：确定在何处停下 增加x x2 2 的值， x1 =0 所有变量非负 令x2 =2，从而 x4 =0 离基变量的选择： 最小比值法确定离基变量确定离基变量1233212442 + 3 3 + 2 + =4 42 xxxxxxxxxx32242233 0 314420 =22xxxxxx最小比值法Q3：如何找下一个相邻的基本可行解求解线性规划的单纯形法求解线性规划的单纯形法迭代步骤迭代步骤3：确定新的基本可行解：确定新的基本可行解u原方程 寻找新的基本可行解： 初等数学变换121231242 -3 =0 + 3 + 2 + =4 Zxxxxxxxx初等数学初等数学变换变换初始初始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的系数是正数！非最优解！14134124/2 + 3 /2 =6 /2 + - /2 1 /2 + 2 + /2 =2 Zxxxxx xxx求解线性规划的单纯形法求解线性规划的单纯形法 第第2次迭代次迭代 确定进基变量确定进基变量x1 确定离基变量确定离基变量3142141/2/202/2/20 xxxxxx 134124/2 - /2 1/2 + + /2 =2xxxxxx1124xx非基变量x4=012x 30 x 确定确定x x3 3为离基变量为离基变量 初等行变换初等行变换14134124/2 + 3 /2 =6 /2 + - /2 1 /2 + 2 + /2 =2 Zxxxxx xxx初等初等行变换行变换34134234 + + =7 2 - 2 - + =1 Zxxxxx xxx非基变量系数0，最优！Z*=7,X*=(2,1,0,0)求解线性规划的单纯形法求解线性规划的单纯形法目标函数无界的情况min z=-x1-2x2 s.t.-x1+x21 x22 x1,x20用单纯形法求解以下线性规划模型。求解线性规划的单纯形法求解线性规划的单纯形法最优性检验：最优性检验：j 0 ？然后确定初始基本可行解 X0 = (0, 0, 1, 2)T z0 = 当前解当前解 X0 非优；非优；须由须由X0 转化为另一个基本可行解转化为另一个基本可行解 X1。：让：让X0 中的一个中的一个非基变量非基变量进基进基，去替换原来的一个，去替换原来的一个（离基离基）。）。首先标准化，令z=-z，引入松弛变量x3, x4max z=x1+2x2 s.t.-x1+x2+x3 =1 x2 +x4=2 x1,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 jj0 = k xk 进基进基 min - -1，- -2 = - -2= 2 x2 进基进基z - x1 -2x2 = - x1 + x2 +x3 = 1 x2 +x4 = 2 ()0由由 有有求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法 1主列主列进基进基主元主元 z - - x1 - - 2 x2 = 0- - x1 + x2 +x3 = 1 1 x2 +x4 = 2 ()min以以主列主列中中为为，同行，同行为为，求，求；按按确定确定和和，以及，以及。求解线性规划的单纯形法求解线性规划的单纯形法 () -x1 + x2 +x3 = 1 得得称为单纯形法的一次称为单纯形法的一次迭代迭代。z- - x1 - -2x2 = 0 - - x1+ x2 +x3 = 1 1 x2 +x4 = 2 ()10 x1 -x3 + x4 = 1 z-3x1 +2x3 = 20的的是把是把变为变为变变为为1，其余变为，其余变为0。用用将将X0 转化为转化为另一个基本另一个基本可行解可行解 。求解线性规划的单纯形法求解线性规划的单纯形法() - x1 + x2 +x3 = 1 1x1 -x3 + x4 = 1 z-3x1 +2x3 = 20min() z -x3 +3x4 = 5x2 + x4 = 2 x1 -x3 + x4 = 1 0得得 参数=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
