资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3,第一轮 ：,选择初始的基变量,x,3,、,x,4,、,x,5,可以得到初始的基可行解,1,通过初等变换把约束方程写成，方程左边是一个基变量，,右边是非基变量的形式,x,3,8,x,1,2x,2,x,4,16,4x,1,x,5,12,4x,2,代入目标函数，将目标函数用非基变量来表达,令非基变量为零，得到基可行解,X,（,0,）,（,0,，,0,，,8,，,16,，,12,）,T,Z= 2 x,1,+3 x,2,2,在目标函数的表达式中，只要非基变量的系数是正数，,就说明目标值还有增加的可能，也就是说目前的基可行解,还不是最优解。,就需要将非基变量与基变量进行对换。一般选择正系数,最大的那个非基变量,x,2,为换入变量，将它换入到基变量中去，,同时还要确定基变量中有一个要换出来成为非基变量。,可按以下方法来确定换出变量。,当将,x,2,定为换入变量后，必须要从,x,3,、,x,4,、,x,5,中换出一个，,并要保证其余的都是非负，即,x,3,、,x,4,、,x,5, 0,。,当,x,1,0,时，,x,3,8,2x,2, 0,x,4,16, 0,x,5,12,4x,2,0,只有选择,x,2,min,（,8/2,，,12/4,）,3,时,3,当,x,2,3,时，,x,5,0,，这就决定了,x,5,为换出变量，用,x,2,去替换,x,5,。,第二轮,x,2,与,x,5,互换，即,x,2,为基变量，,x,5,为非基变量，,为了求得新的基本可行解，并将目标函数,z,用非基变量,x,1,、,x,5,表示以判别所求的基本可行解是否为最优解,需将约束方程组进行初等变换，使,方程左边是一个基变量，右边是非基变量的形式,x,3,2,x,1,+1/2x,5,x,4,16,4x,1,x,2,3,1/4,x,5,令非基变量为零，得到基可行解,X,（,1,）,（,0,，,3,，,2,，,16,，,0,）,T,z= 9+2 x,1,3/4x,5,4,即目前的基本可行解不是最优解，,x,1,应为换入变量。,在方程组中，用各方程负的,x,1,的系数（如果,x,1,在方程的左边，,则用正的,x,1,系数）去除对应的常数项，选最小者，,x,1,min,（,2/1,，,16/4,，）,2,第三轮,x,1,与,x,3,互换。将第二轮的方程组进行初等变换，,使得由基变量,x,1,、,x,4,、,x,2,所构成的基为单位矩阵。,x,1,2,x,3,+1/2x,5,x,4,8+4x,3,2 x,5,x,2,3,1/4x,5,X,（,2,）,（,2,，,3,，,0,，,8,，,0,）,T,z = 13,1/2 x,3,+1/4x,5,5,x,5,与,x,4,互换。将约束方程组进行初等变换，,使得每个约束方程只含一个基变量且基变量的系数为,1,。,第四轮：,x,1,4,1/4x,4,x,5,4,2x,3,1/2 x,5,x,2,2,1/2x,3,1/8x,4,X,（,3,）,（,4,，,2,，,0,，,0,，,4,）,T,z = 14,3/2 x,3,-1/8x,4,6,4,单纯形法的计算步骤,7,4,1,单纯形表,用表格法求解,LP,，规范的表格,单纯形表,如下：,8,检验数的表达形式,最优性判别定理：,若基可行解对应的检验数,0 ( j=1,，,2,，,n),，则此解是最优解，否则不是最优解。,9,用单纯形方法求解,max,z =,40,x,1,+,45,x,2,+,24,x,3,s.t,.,10,用单纯形方法求解,max,z =,40,x,1,+,45,x,2,+,24,x,3,s.t,.,11,用单纯形方法求解,max,z =,40,x,1,+,45,x,2,+,24,x,3,s.t,.,12,2 3 0 0 0,1,2,1 0 0,4,0,0 1 0,0,4,0 0 1,0 2,3,0 0 0,0,0,0,8,16,12,x,3,x,4,x,5,4,-,3,2 3 0 0 0,2,1,0,1 0,-1/2,- 9,2,0 0 0 -3/4,0,0,3,x,3,x,4,x,2,2,4,-,( ),3,0,1 0 0,1/4,16,4,0 0 1,0,X,(0),=(0,，,0,，,8,，,16,，,12),T,，,z,0,=0,13,用单纯形方法求解,max,z =,40,x,1,+,45,x,2,+,24,x,3,s.t,.,14,2 3 0 0 0,1,2,1 0 0,4,0,0 1 0,0,4,0 0 1,0 2,3,0 0 0,0,0,0,8,16,12,x,3,x,4,x,5,4,-,3,2 3 0 0 0,2,1,0,1 0,-1/2,- 9,2,0 0 0 -3/4,0,0,3,x,3,x,4,x,2,2,4,-,( ),3,0,1 0 0,1/4,16,4,0 0 1,0,X,(0),=(0,，,0,，,8,，,16,，,12),T,，,z,0,=0,15,2 3 0 0 0,2,1,0,1,0,-1/2,-,13 0 0 -2 0,1/4,2,0,3,x,1,x,4,x,2,-,4,12,3,0,1,0,0,1/4,8,0,0,-4,1,2,2 3 0 0 0,2,1,0,1 0,-1/2,-9,2,0 0 0 -3/4,0,0,3,x,3,x,4,x,2,2,4,-,3,0,1 0 0,1/4,16,4,0 0 1,0,( ),X,(1),=(0,，,3,，,2,，,16,，,0),T,，,z,1,=9,16,用单纯形方法求解,max,z =,40,x,1,+,45,x,2,+,24,x,3,s.t,.,17,2 3 0 0 0,1,2,1 0 0,4,0,0 1 0,0,4,0 0 1,0 2,3,0 0 0,0,0,0,8,16,12,x,3,x,4,x,5,4,-,3,2 3 0 0 0,2,1,0,1 0,-1/2,- 9,2,0 0 0 -3/4,0,0,3,x,3,x,4,x,2,2,4,-,( ),3,0,1 0 0,1/4,16,4,0 0 1,0,X,(0),=(0,，,0,，,8,，,16,，,12),T,，,z,0,=0,18,2 3 0 0 0,2,1,0,1,0,-1/2,-,13 0 0 -2 0,1/4,2,0,3,x,1,x,4,x,2,-,4,12,3,0,1,0,0,1/4,8,0,0,-4,1,2,2 3 0 0 0,2,1,0,1 0,-1/2,-9,2,0 0 0 -3/4,0,0,3,x,3,x,4,x,2,2,4,-,3,0,1 0 0,1/4,16,4,0 0 1,0,( ),X,(1),=(0,，,3,，,2,，,16,，,0),T,，,z,1,=9,19,用单纯形方法求解,max,z =,40,x,1,+,45,x,2,+,24,x,3,s.t,.,20,2 3 0 0 0,1,2,1 0 0,4,0,0 1 0,0,4,0 0 1,0 2,3,0 0 0,0,0,0,8,16,12,x,3,x,4,x,5,4,-,3,2 3 0 0 0,2,1,0,1 0,-1/2,- 9,2,0 0 0 -3/4,0,0,3,x,3,x,4,x,2,2,4,-,( ),3,0,1 0 0,1/4,16,4,0 0 1,0,X,(0),=(0,，,0,，,8,，,16,，,12),T,，,z,0,=0,21,2 3 0 0 0,2,1,0,1,0,-1/2,-,13 0 0 -2 0,1/4,2,0,3,x,1,x,4,x,2,-,4,12,3,0,1,0,0,1/4,8,0,0,-4,1,2,2 3 0 0 0,2,1,0,1 0,-1/2,-9,2,0 0 0 -3/4,0,0,3,x,3,x,4,x,2,2,4,-,3,0,1 0 0,1/4,16,4,0 0 1,0,( ),X,(1),=(0,，,3,，,2,，,16,，,0),T,，,z,1,=9,22,2 3 0 0 0,2,1,0,1,0,-1/2,-13 0 0 -2 0,1/4,2,0,3,x,1,x,4,x,2,-,4,12,3,0,1,0,0,1/4,8,0,0,-4,1,2,( ),2 3 0 0 0,4,1,0,0,1/4,0,-14 0 0 -1.5 -1/8,0,2,0,3,x,1,x,5,x,2,2,0,1,1/2,-1/8,0,4,0,0,-2,1/2,1,X,(2),=(2,，,3,，,0,，,8,，,0),T,，,z,2,=13,X,(3),=(4,，,2,，,0,，,0, 4),T,，,z,3,=14,23,计算步骤,(1).,找出初始可行基，,确定初始基可行解,，建立初始单纯形表。,(2).,检验,各非基变量,x,j,的检验数，若,j,0,，,j=m+1,，,，,n,；则,已得到,最优解,，可停止计算，否则转入下一步。,(3).,在,j, 0,，,j=m+1,，,，,n,中，若有某个,k,对应,x,k,的系数列向量,P,k,0,，则此问题是,无界解,，停止计算。否则，转入下一步。,(4).,根据,max(,j, 0) =,k,，,确定,x,k,为换入变量,，按,规则计算,=minb,i,/a,ik,a,ik,0,可,确定,第,l,行的基变量为,换出变量,。转入下一步。,24,
展开阅读全文