《运筹学：教案3 单纯形原理（改)》由会员分享，可在线阅读，更多相关《运筹学：教案3 单纯形原理（改)（26页珍藏版）》请在金锄头文库上搜索。
1、3 3 单纯形法单纯形法第一轮第一轮 ： 选择初始的基变量选择初始的基变量x x3 3、x x4 4、x x5 5可以得到初始的基可行解可以得到初始的基可行解通过初等变换把约束方程写成，方程左边是一个基变量，右边是非基变量的形式x x3 38 8 x x1 12x2x2 2x x4 416164x4x1 1 x x5 512124x4x2 2 代入目标函数，将目标函数用非基变量来表达代入目标函数，将目标函数用非基变量来表达令非基变量为零，得到基可行解令非基变量为零，得到基可行解X X（0 0） （0 0，0 0，8 8，1616，1212）T TZ= 2 x1+3 x2 在目标函数的表达式中，
2、只要非基变量的系数是正数，在目标函数的表达式中，只要非基变量的系数是正数，就说明目标值还有增加的可能，也就是说目前的基可行解就说明目标值还有增加的可能，也就是说目前的基可行解还不是最优解。还不是最优解。 就需要将非基变量与基变量进行对换。一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量。可按以下方法来确定换出变量。 当将x2定为换入变量后，必须要从x3、x4、x5中换出一个，并要保证其余的都是非负，即x3、x4、x5 0。 当当x10时，时， x382x2 0x416 0 x5124x2 0 只有选择只有选择x x2 2min
3、min（8/28/2，12/412/4）3 3时时 当x23时，x50，这就决定了x5为换出变量，用x2去替换x5。 第二轮x2与 x5互换，即x2为基变量，x5为非基变量，为了求得新的基本可行解，并将目标函数z用非基变量x1、 x5表示以判别所求的基本可行解是否为最优解 ,需将约束方程组进行初等变换，使方程左边是一个基变量，右边是非基变量的形式x32 x1+1/2x5x4164x1 x231/41/4x5 令非基变量为零，得到基可行解X X（1 1） （0 0，3 3，2 2，1616，0 0）T Tz= 9+2 xz= 9+2 x1 1 3/4x 3/4x5 5即目前的基本可行解不是最优解
4、，x1应为换入变量。在方程组中，用各方程负的x1的系数（如果x1在方程的左边，则用正的x1系数）去除对应的常数项，选最小者， x1min（2/1，16/4，）2第三轮第三轮 x1与 x3互换。将第二轮的方程组进行初等变换，使得由基变量x1、x4、x2所构成的基为单位矩阵。 x x1 12 2 x x3 3+1/2x+1/2x5 5x x4 48+4x8+4x3 32 x2 x5 5 x x2 23 31/4x1/4x5 5 X X（2 2） （2 2，3 3，0 0，8 8，0 0）T T z = 13 z = 131/2 x1/2 x3 3+1/4x+1/4x5 5 x5与 x4互换。将约束
5、方程组进行初等变换，使得每个约束方程只含一个基变量且基变量的系数为1。第四轮： x x1 14 41/4x1/4x4 4 x x5 54 42x2x3 31/2 x1/2 x5 5 x x2 22 21/2x1/2x3 31/8x1/8x4 4 X X（3 3） （4 4，2 2，0 0，0 0，4 4）T T z = 14 z = 143/2 x3/2 x3 3-1/8x-1/8x4 4 44单纯形法的计算步骤单纯形法的计算步骤41 单纯形表单纯形表用表格法求解LP，规范的表格单纯形表如下：检验数的表达形式检验数的表达形式最优性判别定理：最优性判别定理：若若基基可可行行解解对对应应的的检检验
6、验数数 0 ( j=1，2，,n),n)，则此解是最优解，否则不是最优解。则此解是最优解，否则不是最优解。用单纯形方法求解用单纯形方法求解 max z =4040x1+45x2+24x3 s.t. 用单纯形方法求解用单纯形方法求解 max z =4040x1+45x2+24x3 s.t. 用单纯形方法求解用单纯形方法求解 max z =4040x1+45x2+24x3 s.t. 2 3 0 0 01 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-32 3 0 0 02 1 0 1 0 -1/2- 9 2 0 0 0 -3/4003
7、x3x4x224-( )3 0 1 0 0 1/416 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0用单纯形方法求解用单纯形方法求解 max z =4040x1+45x2+24x3 s.t. 2 3 0 0 01 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-32 3 0 0 02 1 0 1 0 -1/2- 9 2 0 0 0 -3/4003x3x4x224-( )3 0 1 0 0 1/416 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，
8、1616，12)12)T T， z z0 0 =0=02 3 0 0 02 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-4123 0 1 0 0 1/48 0 0 -4 1 22 3 0 0 02 1 0 1 0 -1/2-9 2 0 0 0 -3/4003x3x4x224-3 0 1 0 0 1/416 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1 1 =9=9用单纯形方法求解用单纯形方法求解 max z =4040x1+45x2+24x3 s.t. 2 3 0 0 01 2 1 0 0 4 0
9、 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-32 3 0 0 02 1 0 1 0 -1/2- 9 2 0 0 0 -3/4003x3x4x224-( )3 0 1 0 0 1/416 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=02 3 0 0 02 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-4123 0 1 0 0 1/48 0 0 -4 1 22 3 0 0 02 1 0 1 0 -1/2-9 2 0 0 0 -3/4003x3x4x224-
10、3 0 1 0 0 1/416 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1 1 =9=9用单纯形方法求解用单纯形方法求解 max z =4040x1+45x2+24x3 s.t. 2 3 0 0 01 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-32 3 0 0 02 1 0 1 0 -1/2- 9 2 0 0 0 -3/4003x3x4x224-( )3 0 1 0 0 1/416 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)
11、12)T T， z z0 0 =0=02 3 0 0 02 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-4123 0 1 0 0 1/48 0 0 -4 1 22 3 0 0 02 1 0 1 0 -1/2-9 2 0 0 0 -3/4003x3x4x224-3 0 1 0 0 1/416 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1 1 =9=92 3 0 0 02 1 0 1 0 -1/2-13 0 0 -2 0 1/4203x1x4x2-4123 0 1 0 0 1/48 0 0 -4 1
12、2( )2 3 0 0 04 1 0 0 1/4 0-14 0 0 -1.5 -1/8 0203x1x5x22 0 1 1/2 -1/8 04 0 0 -2 1/2 1 X X(2)(2)=(2=(2，3 3，0 0，8 8，0)0)T T， z z2 2 =13=13 X X(3)(3)=(4=(4，2 2，0 0，0, 4)0, 4)T T， z z3 3 =14=14计算步骤计算步骤(1).找出初始可行基，确定初始基可行解，建立初始单纯形表。(2).检验各非基变量xj的检验数，若j 0，j=m+1，n；则已得到最优解，可停止计算，否则转入下一步。(3).在j 0，j=m+1，n中，若有某个k对应xk的系数列向量Pk0，则此问题是无界解，停止计算。否则，转入下一步。(4).根据max(max( j 0) = k，确定xk为换入变量，按 规则计算 = =minbminbi i/ /a aikik a aikik00可确定第l行的基变量为换出变量。转入下一步。
