(3.2.1)--线性规划的单纯形法（NO4）.pdf
1 运运 筹筹 学学 第第4 4讲讲 线性规划的单纯形法线性规划的单纯形法 2 单纯形法是单纯形法是1947年由美国数学家年由美国数学家Dantig.Z提出的，是提出的，是解线性规划最有效和最常用的算法，许多规划问题如整解线性规划最有效和最常用的算法，许多规划问题如整数规划、非线性规划、目标规划、网络最大流问题等最数规划、非线性规划、目标规划、网络最大流问题等最后都化为线性规划来求解，主要是基于单纯形法的有效后都化为线性规划来求解，主要是基于单纯形法的有效性和简捷性。正是因为单纯形法的提出，使线性规划得性和简捷性。正是因为单纯形法的提出，使线性规划得到了突飞猛进的发展，也极大地推动了运筹学的应用和到了突飞猛进的发展，也极大地推动了运筹学的应用和发展。发展。解线性规划的单纯形法解线性规划的单纯形法 单纯形计算方法单纯形计算方法(Simplex Method)是先求出一个初始基是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或判断无最优解。它是一行解并判断，直到得出最优解或判断无最优解。它是一种逐步逼近最优解的迭代方法。种逐步逼近最优解的迭代方法。3 线性规划问题的单纯形法 1.解LP问题单纯形法的基本思路：求出一个初始基可行解 y 判别此基可行解是否 最 优 解 换基迭代 N 求出使目标函数值得到 改善的基可行解 停 LP问题的标准形 4),.,2,1(0.11221122111111njxbxaxaxbxaxaxbxaxaxjmnmnmmmmnnmmnnmm将目标函数改写为：Z-c1x1-c2x2-cnxn=0 把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：2.单纯形法的计算步骤（表格形式）（1）建立初始单纯形表，假定B=I，b0 设 maxZ=c1x1+c2x2+cnxn 5 Z x1 x2 xm xm+1 xn b 0 1 0 0 a1m+1 a1n b1 0 0 1 0 a2m+1 a2n b2 0 0 0 1 amm+1 amn bm 1 c1 c2 cm cm+1 cn 0 以非基变量表示基变量形式n1mjjijiixabx，代入Z中的基变量,有 minmjnmjjjjijiixcxabcZ111)(miminmjnmjjjjjiiiixcxacbc1111)(minmjjmiijijiixaccbc111)(6 再令 miijijjjjacczc1 则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B）Cj C1Cm cm+1cn CB xB b x1xm xm+1xn i C1 x1 b1 10 a1m+1a1n C2 x2 b2 00 a2m+1a2n：Cm xm bm 01 amm+1amn -Z-Z0 00 m+1n j检验数行 7 1234512312412512345max3500020160210.3432,0Zxxxxxxxxxxxstxxxx x x x x例如：例如：列出生产计划问题的单列出生产计划问题的单纯形表纯形表 cj 3 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 X4 x5 16 10 32 2 0 1 0 0 0 2 0 1 0 3 4 0 0 1 -Z 0 3 5 0 0 0 8 （3）当前目标值01miiiZc b ，检验数1(1,.,)mjjjjiij jiczcc ajmn 上述初始单纯形表可确定初始可行基和初始基可行解：B=(P1,P2,Pm)=I,X=(b1,b2,bm,00)T 从初始单纯形表建立的过程可以看到以下事实：（1）凡LP模型中约束条件为“”型，在化为标准型后必有B=I，如果b0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数中非基变量的系数也填入检验数行各相应位置。（2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。9（2）判别最优解 1 在T(B)中，若所有的检验数j0(j=1,2,n)则B为最优基，相应的基可行解为最优解，停止计算。2 在T(B)中，若有k0(1kn)，且xk的系数列向量Pk0，则该问题无界，停止计算。否则转入（3）（3）换基迭代（基变换）1 先确定进基变量Xk:k=minj|j0，即检验数行从左至右选择正数所对应的变量进基。LKaKPLkLikikiabaab0|min2 按最小比值原则确定出基变量xL：3 以 为主元，进行初等行变换（又称旋转变换）即将列向量 变换为单位列向量：从而保证下一个基解可行 iklkliiaabbb 10 0,26232432.t.s34Zmaxxxxxxxxx21212121解：引进松驰变量x3,x4，化为标准形得：0,26232432.t.s0034Zmaxxxxxxxxxxxxxxx43214213214321从标准形中可看出存在可行基B=（P3，P4）=I，基变量为X3，X4；非基变量为X1，X2。建立初始单纯形表得：例例1 求解下列线性规划问题求解下列线性规划问题 11 cj 4 3 0 0 CB XB b x1 x2 x3 x4 0 0 x3 x4 24 26 2 3 1 0 3 2 0 1 12 26/3 -Z 0 4 3 0 0 由于X1，X2的检验数均为正，且X1的检验数最大，选取X1为进基变量；再按最小比值=min（24/2，26/3）=26/3，因此选取X4为出基变量，进行换基迭代。cj 4 3 0 0 CB XB b x1 x2 x3 x4 0 4 x3 x1 20/3 26/3 0 5/3 1 -2/3 1 2/3 0 1/3 4 13 -Z-104/3 0 1/3 0 -4/3 ii12 cj 4 3 0 0 CB XB b x1 x2 x3 x4 3 4 x2 x1 4 6 0 1 3/5 -2/5 1 0 -2/5 3/5 -Z-36 0 0 -1/5 -6/5 表中最后一行的所有检验数均为非正数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4)T=（6，4，0，0)T，最优值为Z=36 例例2 求解下列线性规划问题 0,1826224.t.s3Zmaxxxxxxxxxxx2121212121i13 解：化标准形，建立初始单纯形表解：化标准形，建立初始单纯形表 cj 3 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 4 2 18 1 1 1 0 0 4 -1 1 0 1 0 -6 2 0 0 1 3 -Z 0 3 1 0 0 0 经过一次迭代得到最优表如下经过一次迭代得到最优表如下 cj 3 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 3 x3 x4 x1 1 5 3 0 2/3 1 0 -1/6 3/2 0 4/3 0 1 1/6 15/3 1 1/3 0 0 1/6 9 -Z-9 0 0 0 0 -1/2 最优解为最优解为X=(x1,x2,x3,x4,x5)T=(3,0,1,5,0)T,maxZ=9。但是在这个问。但是在这个问题中，非基变量题中，非基变量x2的检验数为的检验数为0，说明此问题有多重最优解。，说明此问题有多重最优解。以以x2为进基变量，再迭代一次，得到另一个最优解。结果如下表。为进基变量，再迭代一次，得到另一个最优解。结果如下表。jj14 cj 3 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 3 x2 x4 x1 3/2 3 5/2 0 1 3/2 0 -1/4 0 0 -2 1 1/2 1 0 -1/2 0 1/4 Z-9 0 0 0 0 -1/2 此表对应的最优解为此表对应的最优解为X=(x1,x2,x3,x4,x5)T=(5/2,3/2,0,3,0)T,maxZ=9 15 例题例题3 求解下列线性规划问题求解下列线性规划问题 0,536322.max32132132121xxxxxxxxxtsxxZ cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 4 6 -2 2 3 1 0 -3 1 -1 0 1 -Z 0 1 1 0 0 0 解：解：化标准形，列出其初始单纯形表为化标准形，列出其初始单纯形表为 从表中可以看出，从表中可以看出，x1所对应的检验数为正但列向量均为负所对应的检验数为正但列向量均为负数，因此，此问题存在无界解，即目标函数数，因此，此问题存在无界解，即目标函数+。16 练习：练习：求解下列线性规划问题求解下列线性规划问题 0,6242.2max32121321321xxxxxxxxtsxxxZ其最优表为：其最优表为：cj -1 2 1 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x4 x5 4 6 2 1 1 1 0 1 2 0 0 1 Z 0 -1 2 1 0 0 17 cj -1 2 1 0 0 CB XB b x1 x2 x3 x4 x5 1 2 x3 x2 1 3 3/2 0 1 1 -1/2 1/2 1 0 0 1/2 Z-7 -7/2 0 0 -1 -1/2 cj -1 2 1 0 0 CB XB b x1 x2 x3 x4 x5 0 2 x4 x2 1 3 3/2 0 1 1 -1/2 1/2 1 0 0 1/2 Z-6 -2 0 1 0 -1 最优解为最优解为X=(x1,x2,x3,x4,x5)T=(0,3,1,0,0)T，最优值为：，最优值为：maxZ=7 18 3、无界解：在单纯形表中，若有一个变量的检验数、无界解：在单纯形表中，若有一个变量的检验数 ，但是对应的系数列均为非正数，但是对应的系数列均为非正数 ，则对应的线，则对应的线 性规划问题目标函数性规划问题目标函数 ，此时对应的线性规划问，此时对应的线性规划问题无解。题无解。总结：在单纯形表中判别线性规划解的各种情况总结：在单纯形表中判别线性规划解的各种情况 2、多重最优解：在单纯形表中，当至少有一个非基变量的、多重最优解：在单纯形表中，当至少有一个非基变量的 检验数检验数 ，则说明该线性规划问题有多重最优解。，则说明该线性规划问题有多重最优解。0 j 0j 0 ijaZ1、唯一解：在单纯形表中，当非基变量的所有检验数、唯一解：在单纯形表中，当非基变量的所有检验数 则该线性规划问题具有唯一最优解。则该线性规划问题具有唯一最优解。0j 19 敬请指教！谢谢！
