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

1、求解线性规划的单纯形法求解线性规划的单纯形法单纯形法思路YES停顿求解线性规划的单纯形法求解线性规划的单纯形法 Q1：初始基本可行解如何找？：初始基本可行解如何找？ 标准型标准型 基本解基本解 Q2：怎样判断最优？：怎样判断最优？ 最优性条件最优性条件 Q3：如何找下一个相邻的基本可行解？：如何找下一个相邻的基本可行解？ 确定移动的方向确定移动的方向 确定在何处停下确定在何处停下 确定新的基本可行解确定新的基本可行解关键问题求解线性规划的单纯形法求解线性规划的单纯形法例：用单纯形法求解以下线性规划问题求解线性规划的单纯形法求解线性规划的单纯形法首先将模型转化成标准形式求解线性规划的单纯形法求解

2、线性规划的单纯形法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

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

4、离基变量确定离基变量1233212442 + 3 3 + 2 + =4 42 xxxxxxxxxx32242233 0 314420 =22xxxxxx最小比值法Q3：如何找下一个相邻的基本可行解求解线性规划的单纯形法求解线性规划的单纯形法迭代步骤迭代步骤3：确定新的基本可行解：确定新的基本可行解原方程原方程 寻找新的基本可行解：寻找新的基本可行解：初等数学变换初等数学变换121231242 -3 =0 + 3 + 2 + =4 Zxxxxxxxx初等数学初等数学变换变换初始初始BF解解新的新的BF解解非基变量（Non-basics）x1 =0，x2 =0 x1 =0，x4 =0基变量（Bas

5、ics）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 确

6、定确定x3x3为离基变量为离基变量 初等行变换初等行变换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用单纯形法求解以下线性规划模型。求解线性规划的单纯形法求解线性规划的单纯形法最优性检验：最优性检验：然后确定初始基本可行解 X0 = (0,

7、 0, 1, 2)T z0 = 0 当前解当前解 X0 非优；非优；须由须由X0 转化为另一个基本可行解转化为另一个基本可行解 X1。首先标准化，令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 离基最小比值规则）离基最小比值规则） ：w x2 min 1/1，2/1 = 1w x2 = min 1/1，2/1 = 1 x3x3为离基变量为离基变量w 进基最小检验数规则）：进基最小检验数

8、规则）：w 在负检验数中选择最小的进基。在负检验数中选择最小的进基。w min jj0 = k xk 进进基基w min -1，-2 = -2= 2 x2 进基进基z - x1 -2x2 = 0 - x1 + x2 +x3 = 1 x2 +x4 = 2 ()0由由 有有求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法求解线性规划的单纯形法 1主列主列进基进基主元主元 z - x1 - 2 x2 = 0- x1 + x2 - x1 + x2 +x3 = 1 +x3 = 1 1 x2 +x4 = 2 ()min以主列中正值元素为分母，同行右端常数为分子，求比值；以主列中正值元素为

9、分母，同行右端常数为分子，求比值；按最小比值规则确定主方程和主元素，以及离基变量。按最小比值规则确定主方程和主元素，以及离基变量。求解线性规划的单纯形法求解线性规划的单纯形法() -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用换基运算用换基运算将将X0 转化为转化为另一个基本另一个基本可行解可行解 X1。求解线性规划的单纯形法求解线性规划的单纯形法() - 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限制！求解线性规划的单纯形法求解线性规划的单纯形法目