单纯形法原理(1)一松弛变量的表示 D max z=XfX, st.x1+x2≤3 X12X2≥0 引进松弛变量 B max z=X1+2X2 S.t. X1+X2+X3 +xA=1 2,X3,X4≥0 A
－ ＋ ＋ － 单纯形法原理（1）—松弛变量的表示 max z=x1+2x2 s.t. x1+x23 x2 1 x1 , x20 max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1 , x2 , x3 , x40 x2=0 x1=0 x3=0 x4=0 O A B C D － ＋ ＋ － 引进松弛变量
单纯形法思路 1、找到一个初始基和相应基可行解,并将目标 函数和基变量分别用非基变量表示。 ·2、根据目标函数用非基变量表示的式中的系数, 选择一个非基变量,使其值从0开始增大,z随之 变大,这个变量称为进基变量(一般选系数大的) 若任何一个非基变量的值增加都不能使z增大,则 当前基可行解为最优解。 3、在基变量用非基变量表出的式中,首先减少 到0的称为离基变量 若进基变量值增加时,所有基变量值都不减少, 则无界。 ·4、确定新的基、基可行解,返回2
单纯形法思路 • 1、找到一个初始基和相应基可行解，并将目标 函数和基变量分别用非基变量表示。 • 2、根据目标函数用非基变量表示的式中的系数， 选择一个非基变量，使其值从0开始增大，z随之 变大，这个变量称为进基变量（一般选系数大的） • 若任何一个非基变量的值增加都不能使z增大，则 当前基可行解为最优解。 • 3、在基变量用非基变量表出的式中，首先减少 到0的称为离基变量 • 若进基变量值增加时，所有基变量值都不减少， 则无界。 • 4、确定新的基、基可行解，返回2
max z=x +2x max z=x+2X St.x1+x,<3 S.t. x,+X+ X1,X2≥0 0 第一次叠代: 2=1成为基变量, 目标函数和基变量分别用 0成为非基变量 非基变量表示 当前基可行解 z=X1+2 X12x2Xx2X4)=(0,1,2,0) 选择x进基 B x2进基,从0开始增加 ,x3,x4随之减少 2=0为非基变量 A >0为基变量 当前基可行解: (x1x2x32X4)=(0,0,3,1
x2=0 x1=0 x3=0 x4=0 O A B C x1 ,x2=0为非基变量 x3 ,x4>0为基变量 当前基可行解： (x1 ,x2 ,x3 ,x4)=(0,0,3,1 ) z=0 x2进基,从0开始增加 ，x3 ,x4随之减少 第一次叠代： 目标函数和基变量分别用 非基变量表示： z=x1+2x2 选择x2进基 x3 =3-x1-x2 x4=1 -x2 x2=1成为基变量， x4=0成为非基变量 当前基可行解： (x1 ,x2 ,x3 ,x4)=(0,1,2,0) z=2 单m s 纯.t a .x x 形z=x法1+2原x2 理(2)—第一次叠代 1+x23 x2 1 x1 , x20 max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1 , x2 , x3 , x40
确定离基变量的进一步讨论 设非基变量为x1、x2,基变量为x3、x4、X,进基变量为x2 =5-x1-4X2 5/4=1.25 min{5/4,4/3,2/1}=5/4 4-2x1-3x2 4/3=1.33 当x2增加到1.25时 =2-3x1-x2 2/1=2 0离基 =5-x1+4x2 增加 min{4/3,2/1}=4/3 =4-2x1-3 4/3=1.33 当x2增加到13时 2-3x 41-A2 2/1=2 x4=0离基 X1+4x 增加 min{2/1}=2/1 4-2x1+3x 增加 当x2增加到2时 2-3x1 2/1=2 0离基 1+4x2 x增加 可以无限增加,可 4-2x1+3x2 x增加 行域是开放区域,目 2-3x1+ xs增加 标函数无界
确定离基变量的进一步讨论 设非基变量为x1、x2，基变量为x3、x4、x5，进基变量为x2 x3 =5- x1-4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2 5/4=1.25 4/3=1.33 2/1=2 min{5/4,4/3,2/1}=5/4 当x2增加到1.25时 x3＝0离基 x3 =5- x1+4x2 x4 =4-2x1-3x2 x5 =2-3x1- x2 x3增加 4/3=1.33 2/1=2 min{4/3,2/1}=4/3 当x2增加到1.33时 x4＝0离基 x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1- x2 x3增加 x4增加 2/1=2 min{2/1}=2/1 当x2增加到2时 x5＝0离基 x3 =5- x1+4x2 x4 =4-2x1+3x2 x5 =2-3x1+ x2 x3增加 x4增加 x5增加 x2可以无限增加，可 行域是开放区域，目 标函数无界
=3-X 单纯形法原理(3)一第二次叠代 1-X x12成为基变量, x3=0成为非基变量 第二次叠代 当前基可行解: 目标函数和基变量分别用非 (1,x2,x3,x4)=(2,1,0,0) 基变量表示: 4 z=2+x1-2x 选择X1进基 x进基,从0开始增 3 2-x1+x4 加,基变量x2保持不 变,x3从2开始减少 B 当前基可行解: A (x1x2,x32x4)=(0,1,2,0) O X2=0 2
x2=0 x1=0 x3=0 x4=0 O A B C 第二次叠代： 目标函数和基变量分别用非 基变量表示： z=2+x1-2x4 选择x1进基 x3 =2-x1+x4 x2=1 -x4 当前基可行解： (x1 ,x2 ,x3 ,x4)=(0,1,2,0) z=2 单纯形法原理（3）—第二次叠代 x1进基，从0开始增 加，基变量x2保持不 变，x3从2开始减少 x1=2成为基变量， x3=0成为非基变量 当前基可行解： (x1 ,x2 ,x3 ,x4)=(2,1,0,0) z=4 x3 =3-x1 -x2 x4=1 -x2