文档介绍：第二节第二节单纯形法单纯形法 Simplex Method Simplex Method 求解线性规划的单纯形法单纯形法思路 YES 停止求解线性规划的单纯形法? Q1 :初始基本可行解如何找? ?标准型?基本解? Q2 :怎样判断最优? ?最优性条件? Q3 :如何找下一个相邻的基本可行解? ?确定移动的方向?确定在何处停下?确定新的基本可行解关键问题求解线性规划的单纯形法例:用单纯形法求解以下线性规划问题求解线性规划的单纯形法首先将模型转化成标准形式求解线性规划的单纯形法 Q1:确定初始的基本可行解?选择原点: –令决策变量 x 1=x 2 = 0得: X 0 = (0,0,3,4) T ?选择单元阵作为初始基: ?令非基变量 x 1=x 2 = 0得: X 0 = (0,0,3,4) T 1 2 3 4 1 1 1 0 ( , , , ) 1 2 0 1 A a a a a ? ?? ?? ?? ? 3 4 1 0 ( , ) 0 1 B a a ? ?? ?? ?? ?求解线性规划的单纯形法?非最优:增加非基变量的值,可以使得目标函数 Z值增加–基变量在目标函数中的系数为 0 –非基变量在目标函数中的系数<=0 . (注意:目标函数形式 z = 2x 1 + 3x 2) –若目标函数为方程形式: z - 2 x 1 - 3 x 2 =0 ,则需非基变量的系数>=0 Q2:最优性检验检验数求解线性规划的单纯形法?迭代步骤 1:确定移动的方向例: z = 2x 1+ 3x 2–选择 x 1 ?Z的增长率=2 –选择 x 2 ?Z的增长率=3 –3>2,选择 x 2! ?进基变量的选择: –选择非基变量的系数最大的! Q3:如何找下一个相邻的基本可行解确定进基变量检验数的绝对值哦~~~ 求解线性规划的单纯形法?迭代步骤 2:确定在何处停下–增加 x 2 的值, x 1 =0 –所有变量非负?令x 2 =2 ,从而 x 4 =0 ?离基变量的选择: –最小比值法确定离基变量 1 2 3 3 2 1 2 4 4 2 + 3 3 + 2 + =4 4 2 x x x x x x x x x x ? ????? ?? 3 2 2 4 2 2 3 3 0 3 14 4 2 0 =2 2 x x x x x x ? ?????? ????最小比值法最小比值法 Q3:如何找下一个相邻的基本可行解求解线性规划的单纯形法?迭代步骤 3:确定新的基本可行解?原方程?寻找新的基本可行解: –初等数学变换 1 2 1 2 3 1 2 4 2 -3 =0 + 3 + 2 + =4 Z x x x x x x x x ?? ?初等数学变换初等数学变换初始 BF 解新的 BF 解非基变量( Non-basics )x 1 =0 ,x 2 =0x 1 =0 ,x 4 =0 基变量( Basics )x 3 =3 ,x 4 =4x 3=?,x 2 =2 1X*=(0, 2, 1, 0 ) Z*= 6+ x 1 /2- 3x 4 /2=6 ?新方程 Q3:如何找下一个相邻的基本可行解非基变量 x 1的系数是正数! 非最优解! 1 4 1 3 4 1 2 4 /2 + 3 /2 =6 /2 + - / 2 1 /2 + 2 + /2 =2 Z x x x x x x x x ?? ?