北京交通大学 运筹学 教案3——单纯形原理(改)

《北京交通大学 运筹学 教案3——单纯形原理(改)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§3单纯形法第一轮：选择初始的基变量x3、x4、x5可以得到初始的基可行解通过初等变换把约束方程写成，方程左边是一个基变量，右边是非基变量的形式x3＝8－x1－2x2x4＝16－4x1x5＝12－4x2代入目标函数，将目标函数用非基变量来表达令非基变量为零，得到基可行解X（0）＝（0，0，8，16，12）TZ=2x1+3x2在目标函数的表达式中，只要非基变量的系数是正数，就说明目标值还有增加的可能，也就是说目前的基可行解还不是最优解。就需要将非基变量与基变量进行对换。一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定

2、基变量中有一个要换出来成为非基变量。可按以下方法来确定换出变量。当将x2定为换入变量后，必须要从x3、x4、x5中换出一个，并要保证其余的都是非负，即x3、x4、x5≥0。当x1＝0时，x3＝8－2x2≥0x4＝16≥0x5＝12－4x2≥0只有选择x2＝min（8/2，－，12/4）＝3时当x2＝3时，x5＝0，这就决定了x5为换出变量，用x2去替换x5。第二轮x2与x5互换，即x2为基变量，x5为非基变量，为了求得新的基本可行解，并将目标函数z用非基变量x1、x5表示以判别所求的基本可行解是否为最优解,需将约束方程组进行初等变换，使方程左边是一

3、个基变量，右边是非基变量的形式x3＝2－x1+1/2x5x4＝16－4x1x2＝3－1/4x5令非基变量为零，得到基可行解X（1）＝（0，3，2，16，0）Tz=9+2x1－3/4x5即目前的基本可行解不是最优解，x1应为换入变量。在方程组中，用各方程负的x1的系数（如果x1在方程的左边，则用正的x1系数）去除对应的常数项，选最小者，x1＝min（2/1，16/4，－）＝2第三轮x1与x3互换。将第二轮的方程组进行初等变换，使得由基变量x1、x4、x2所构成的基为单位矩阵。x1＝2－x3+1/2x5x4＝8+4x3－2x5x2＝3－1/4x5X（2

4、）＝（2，3，0，8，0）Tz=13－1/2x3+1/4x5x5与x4互换。将约束方程组进行初等变换，使得每个约束方程只含一个基变量且基变量的系数为1。第四轮：x1＝4－1/4x4x5＝4＋2x3－1/2x5x2＝2－1/2x3＋1/8x4X（3）＝（4，2，0，0，4）Tz=14－3/2x3-1/8x4§4单纯形法的计算步骤4．1单纯形表用表格法求解LP，规范的表格——单纯形表如下：检验数的表达形式最优性判别定理：若基可行解对应的检验数0(j=1，2，…,n)，则此解是最优解，否则不是最优解。用单纯形方法求解maxz=40x1+45x2+24x

5、3s.t.用单纯形方法求解maxz=40x1+45x2+24x3s.t.用单纯形方法求解maxz=40x1+45x2+24x3s.t.2300012100400100400102300000081612x3x4x54-32300021010-1/2-92000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)T，z0=0用单纯形方法求解maxz=40x1+45x2+24x3s.t.2300012100400100400102300000081612x3x4x54-32300021010-1/2-9

6、2000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)T，z0=02300021010-1/2-1300-201/4203x1x4x2-412301001/4800-4122300021010-1/2-92000-3/4003x3x4x224-301001/41640010()X(1)=(0，3，2，16，0)T，z1=9用单纯形方法求解maxz=40x1+45x2+24x3s.t.2300012100400100400102300000081612x3x4x54-32300021010-1/

7、2-92000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)T，z0=02300021010-1/2-1300-201/4203x1x4x2-412301001/4800-4122300021010-1/2-92000-3/4003x3x4x224-301001/41640010()X(1)=(0，3，2，16，0)T，z1=9用单纯形方法求解maxz=40x1+45x2+24x3s.t.2300012100400100400102300000081612x3x4x54-32300021010

8、-1/2-92000-3/4003x3x4x224-()301001/41640010X(0)=(0，0，8，16，12)