02-2求解线性规划的单纯形法1

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

2、择单元阵作为初始基：A = 1110 = (a , a , a , a )1201 1234B = 10 = (a , a )0134 令非基变量 x1= x2 = 0得：X0 = ( 0，0，3，4)T求解线性规划的单纯形法Q2：最优性检验 非最优：增加非基变量的值，可以使 得目标函数Z值增加 基变量在目标函数中的系数为0 非基变量在目标函数中的系数=0求解线性规划的单纯形法Q3：如何找下一个相邻的基本可行解确定进基变量 迭代步骤1：确定移动的方向例：z = 2x1 + 3x2 选择 x1 ？Z的增长率=2 选择 x2 ？Z的增长率=3 32，选择x2！ 进基变量的选择： 选择非基变量的系数

3、最大的！检验数的绝对值哦求解线性规划的单纯形法Q3：如何找下一个相邻的基本可行解确定离基变量 迭代步骤2：确定在何处停下增加x2 的值， x1 =0x1 +x2+ x3= 3x3 = 3 - x2x1 + 2x2+ x4=4x4= 4 - 2x2所有变量非负x= 3 - x 0 x 3 = 3最小比值法3221x= 4 - 2x 0 x 4 =24222 令x2 =2，从而x4 =0 离基变量的选择：最小比值法求解线性规划的单纯形法Q3：如何找下一个相邻的基本可行解 迭代步骤3：确定新的基本可行解初始BF解新的BF解非基变量（Non-basics）x1 =0，x2 =0x1 =0，x4 =0基

4、变量（Basics）x3 =3，x4 =4x3 =1，x2 =2？u 原方程u 新方程Z - 2x1-3x2=0Z - x1 /2+ 3x4 /2=6x1 +x2+ x3= 3x1 /2+ x3- x4 / 2= 1初等数学变换x1 + 2x2+ x4=4x1 /2+x2+ x4 /2=22非最优解！ 寻找新的基本可行解：X*=（0, 2, 1, 0）非基变量x1的系数是正数！ 初等数学变换Z*=6+ x1/2- 3x4/26求解线性规划的单纯形法 第2次迭代 确定进基变量x1 确定离基变量非基变量x4=0x1/2+ x3-x4 /2= 1x3= 1 - x1 / 2 + x4/ 2 0x1/

5、2 + x2+x4 /2=2x2 = 2 - x1 / 2 - x4/ 2 0x1 2x 4x1 = 2确定x3为离基变量Z*=7,X*=(2,1,0,0)1x3 = 0 初等行变换非基变量系 数0，最优！Z - x1 /2+ 3x4 /2=6初等Z+ x3+ x4=7x1 /2+ x3 - x4 / 2= 1x+ 2x- x= 21342x /2+x+ x /2=2行变换x-x+ x=1124234求解线性规划的单纯形法目标函数的情况用单纯形法求解以下线性规划模型。min z=-x1-2x2s.t.-x1+x21x22x1,x20求解线性规划的单纯形法首先标准化，令z=-z，引入松弛变量x3

6、, x4max z=x1+2x2s.t.-x1+x2+x3=1x2+x4=2x1,x2,x3,x40最优性检验：一切j 0 ？然后确定初始基本可行解X0 = (0, 0, 1, 2)Tz0 = 0当前解 X0 非优；须由X0 转化为另一个基本可行解 X1。思路：让X0 中的一个非基变量进基，去替换原来的一个基变量（离基）。-x1-x1-2x2=00+ x2+x3=1x2+x4=2z () 求解线性规划的单纯形法w 进基（最小检验数规则）：在负检验数中选择最小的进基。min jj0 = k xk 进基min -1，-2 = -2= 2 x2 进基x1仍为非基变量，其值为0。由 有 0xx33 =

7、 1-x2 = x2 1/1x4 = 2 -x2 0 x2 2/1w 离基（最小比值规则） ： x2 min 1/1，2/1 = 1 x2 = min 1/1，2/1 = 1x3为离基变量X1 =( 0,1,0,1)T求解线性规划的单纯形法按最小比值规则确定主方程和主元素，以及离基变量。进基()z - x1- x1主方程x2=0+ 1 x2+x3 离基=21=1- 2x2+x4主列主元比值1min 2以主列中正值元素为分母，同行右端常数为分子，求比值；求解线性规划的单纯形法-2z- x1x2=00换基运算 () -x1x2+x3=1 方程组的初等变换+ 11用换基运算x2+x4=2目的是把主列变为 单位向量：主元变为1，其余变为0。将X0 转化为另一个基本 可行解 X1。X0 =(0,0,1,2)Tz0 = 0z-3x1-x1 x1+2x3+x3-x30= 20()+1x2=10+ x4=1得X1 =(0,1,0,1)Tz0 = 2称为单纯形法的一次迭代。求解线性规划的单纯形法z-3x1+2x3= 20比值11-1()x1 +x2+x3=-x1参数=0x1 = 1+ x3 -x4=0X* = ( 1, 2, 0, 0 )Tz* = 5求解线性规划的单纯形法X22