单纯形法基本原理及实例演示

1、单纯形法求解动态演示v在求解LP问题时,有人给出了图解法,但对多维变量时,却无能为力,v美国数学家GBDantgig(丹捷格)发明了一种“单纯形法”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。);,(21ncccCTnxxx),(21X一、关于标准型解的若干基本概念一、关于标准型解的若干基本概念基矩阵基矩阵 示例:012233. .23max32143214321xxxxxxxtsxxxxz000032020001010 x1 x2x4x3001300321=目标函数约束条件行列式0基矩阵X1,x2,x3为基变量为基变量,x4为非基变量为非基变量 XT = (XB , XN

2、) T =（ B-1b , 0) T Z = CB B-1b 为了矩阵形求逆计算方便，一般将B转化为单位矩阵。将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量计算各非基变量xj的检验数的检验数 j=Cj-CBPj ，若所有，若所有 j0，则问题已得到，则问题已得到最优解，停止计算，否则转入下步。最优解，停止计算，否则转入下步。在大于在大于0的检验数中，若某个的检验数中，若某个 k所对应的系数列向量所对应的系数列向量Pk0，则此问题，则此问题是无界解，停止计算，

3、否则转入下步。是无界解，停止计算，否则转入下步。根据根据max j j0= k原则，确定原则，确定xk为换入变量为换入变量(进基变量进基变量)，再按，再按 规则计算：规则计算： =minbi/aik| aik0=bl/ aik 确定确定xBl为换出变量。建立新的为换出变量。建立新的单纯形表，此时基变量中单纯形表，此时基变量中xk取代了取代了xBl的位置。的位置。以以aik为主元素进行迭代，把为主元素进行迭代，把xk所对应的列向量变为单位列向量，即所对应的列向量变为单位列向量，即aik变为变为1，同列中其它元素为，同列中其它元素为0，转第，转第 步。步。 2、单纯形法的计算步骤、单纯形法的计算步

4、骤 线性规划的例子子0,40025005 . 2516002234max211212121xxxxxxxxxz线性规划-标准化v引入变量：s1,s2,s3121231211222312123max501000003002400250,0zxxsssxxsxxsxsx x s s s25040030032121100100101200111sssxx3020102100150maxsssxxz提取系数，填入表格：s.t.3212100010050maxsssxxzC向量CBCNXBXN基BN jjjzc Zj=CBNj每个非基变量的检验值初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值1

5、Zj=CBNjZ=CBB-1biijbajjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值1Zj=CBNjZ=CBB-1biijbajjjzc 目标函数系数区目标函数系数区约束条件系数区右端系数右端系数检验系数区检验系数区基变量区基变量区初始单纯形表迭代次数基变量CBx1x2s1s2s3b比值501000001Zj=CBNjZ=CBB-1b2iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000000111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 初始单纯形表迭代次数基变量CBx1x2s1s

6、2s3b比值501000001111003002101040001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 初始单纯形表迭代次数基变量CBx1x2s1s2s3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNjZ=02iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000001S10111003

7、00S2021010400S3001001250Zj=CBNj00000Z=02iiabjjjzc 00000初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=01000002iiabjjjzc 50初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000001S1011100300S2021010400S3001001250Zj=CBNj00000Z=0501000002iiabjjjzc 125014001300初始单纯形表迭代次数基变量CBx1X2s1s2

8、 S3b比值501000002S1011100300S2021010400 x201001250Zj=CBNjZ=CBB-1b2iiabjjjzc 125014001300初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 125014001300初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 12

9、5014001300初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000002S1011100300S2021010400 x210001001250Zj=CBNjZ=CBB-1b2iiabjjjzc 125014001300初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNjZ=250002iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000002S101010-150S202001-1150 x210001001250Zj=

10、CBNj010000100Z=250002iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000

11、002S101010-150S202001-1150 x210001001250Zj=CBNj010000100Z=2500050000-1002iiabjjjzc 2150150初始单纯形表迭代次数基变量CBx1X2s1s2 S3b比值501000003S101010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc x150 x150初始单纯形表迭代次数基变量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 初始单纯形表迭代次数基变量CBx1x2s1s2 S3b比值501000003x1501010-150S202001-1150 x210001001250Zj=CBNj2iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNjZ=275002iiabjjjzc 初始单纯形表迭代次数基变量CBx1X2s1s2S3b比值501000003x1501010-150S2000-21150 x210001001250Zj=CBNj5010050050Z=275002iiabjjjzc 初始单纯形表迭代次